The Electric Traveling Salesman Problem with Time Windows

R. Roberti*, M. Wen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

75 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)32-52
Number of pages21
JournalTransportation Research Part E: Logistics and Transportation Review
Volume89
DOIs
Publication statusPublished - 1 May 2016

Keywords

  • Dynamic Programming
  • Electric vehicles
  • General Variable Neighborhood Search
  • Green logistics
  • Time windows
  • Traveling Salesman

Cite this