The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows

Christian Doppstadt*, Achim Koberstein, Daniele Vigo

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


In this paper, we extend the Hybrid Electric Vehicle – Traveling Salesman Problem (HEV-TSP) that deploys hybrid electric vehicles for customer delivery tours, by considering that customers must be served within given time windows. This feature makes the problem very difficult to solve. We developed a Variable Neighborhood Search based heuristic solution method, which is able to handle hybrid electric vehicle problems with a realistic number of customers. We introduce a large set of benchmark instances, representing typical delivery areas for small package shipping companies. Exact solutions for instances with a small number of customers are calculated by formulating the problem as an integer linear program and solving the instances with the standard solver CPLEX. The proposed heuristic achieves optimal solutions on the small and good quality solutions on larger instances. Furthermore, the results show that the profitability of hybrid electric vehicles highly depends on the structure of the delivery area and the number of customers to serve. Therefore, our heuristic does not only serve to support decision makers in the daily tour planning, but also in the evaluation of the profitability of hybrid electric vehicles for a specific delivery area structure.

Original languageEnglish
Pages (from-to)675-692
Number of pages17
JournalEuropean Journal of Operational Research
Issue number2
Early online date27 Dec 2019
Publication statusPublished - 16 Jul 2020


  • Hybrid Electrical Vehicles
  • Small package shipping
  • Time windows
  • Traveling Salesman


Dive into the research topics of 'The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows'. Together they form a unique fingerprint.

Cite this