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.

The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows

Vigo D.
Membro del Collaboration Group
2020

Abstract

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.
Doppstadt C.; Koberstein A.; Vigo D.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/796586
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact