OPTIMIZATION ALGORITHMS FOR THE SYMMETRIC AND ASYMMETRIC ELECTRIC TRAVELING SALESMAN PROBLEM

The Electric Traveling Salesman Problem (ETSP) is a variant of the traditional TSP in which the vehicle is assumed to be equipped with limited battery. Therefore, the vehicle needs to be recharged along the route, and, for this purpose, a set of recharge stations is provided. The aim is to visit all the customers once, minimizing the overall cost of recharged energy. We consider both the symmetric and asymmetric versions of the problem. We propose an extended formulation for the symmetric problem and a column generation algorithm to solve it, where columns correspond to station-to-station paths. When dealing with the asymmetric version, we consider the possibility of negative cost arcs in the underlying graph. This corresponds to traveling along downhill roads with vehicles that can recharge their batteries. We propose an adaptation of the previous extended formulation, with its branch-and-price algorithm, and a compact formulation, solved with a branch-and-cut algorithm. The last part of the thesis is focused on a data-driven approach for the feasibility of the Resource Constrained Shortest Path Problem (RCSPP).