The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows

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.