The Electric Traveling Salesman Problem with Time Windows

• We introduce the Traveling Salesman Problem with Time Windows for electric vehicles.
• A mathematical model able to solve to optimality small-size instances is proposed.
• A heuristic algorithm is proposed and tested on instances with up to 200 customers.

To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.