A Branch‐and‐Price Algorithm for the Symmetric Electric Traveling Salesman Problem

The Electric Traveling Salesman Problem (ETSP) is a variant of the well-known TSP in which an electric vehicle must visit a set of customers minimizing the total cost of its route. The vehicle is assumed to be equipped with a battery of limited capacity that may need to be recharged along the route. A set of available recharge stations is given, where recharges can be done at given energy prices. The objective is to minimize the total cost of the energy consumed. We consider the symmetric version of the problem, we introduce a mathematical programming formulation, and we solve it with a branch-and-price algorithm, where columns correspond to station-to-station paths.