Hybrid genetic search for the traveling salesman problem with hybrid electric vehicle and time windows

Abstract

The traveling salesman problem with time windows (TSPTW) is a variant of the classical traveling salesman problem (TSP), in which customers must be served within specific time windows. This work proposes a hybrid genetic search for the TSPTW con sidering a hybrid electric vehicle (HEV), which is more environmental friendly than con ventional vehicles and helps to decrease the emission of greenhouse gases. The developed approach includes a specific operator based on the order crossover (OX) to obtain im proved solutions, as well as a search limitation strategy and an efficient move evaluation scheme to speed up the local search phase. Extensive computational experiments were conducted on more than 200 benchmark instances. The proposed algorithm was revealed to be effective in systematically finding high-quality solutions when compared to those achieved by the best heuristic for the problem. Improved solutions were found, especially for the larger and more challenging cases, for which our algorithm performed, on average, 9 times faster than the quickest method available. Moreover, we examine the frequency distribution of the operation mode usage of the vehicle associated with the best solutions found.