Extended Formulations for the Electric Asymmetric TSP

The Electric Traveling Salesman Problem (ETSP) is a variant of the traditional TSP in which the vehicle is assumed to be equipped with a battery of limited capacity. Therefore, the vehicle needs to be recharged along the route and, for this purpose, a set of recharge stations is given. Each station has potentially different unit cost for energy and multiple visits to the same station are allowed. The aim is to visit all the customers once, minimizing the overall cost of the recharged energy. We consider the asymmetric version of the ETSP (EATSP). We also consider the possibility that traveling along some arcs of the underlying graph implies a negative consumption of energy. This corresponds to traveling along downhill roads with vehicles that can recharge their batteries. We propose an extended formulation for the problem, having one variable for each possible sequence of customers which can be visited with no recharges from one station to another. Furthermore, we modify such a formulation in a less intuitive form that requires fewer variables and constraints. We compare these two approaches theoretically and experimentally.