Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates

Abstract

The electric travelling salesman problem with time windows (ETSPTW) is an extension of the well-known travelling salesman problem with time windows (TSPTW). The ETSPTW additionally considers recharging operations of the electric vehicle at identical charging stations. However, different charging technologies used at public or private stations result in different charging times of the electric vehicles. Therefore, this study extends the ETSPTW by additionally considering charging operations at customer locations with different charging rates, called hereafter the electric travelling salesman problem with time windows and mixed charging rates (ETSPTW-MCR). To the best of our knowledge, this is the first study that considers both private and public charging stations for the ETSPTW. In addition to the extended version of the ETSPTW, this paper introduces a new and effective hybrid Simulated Annealing/Tabu Search (SA/TS) algorithm to solve the ETSPTW-MCR problem efficiently. Distinct from the existing hybridization of SA and TS, the proposed hybrid SA/TS algorithm employs efficient search procedures based on the TSPTW restrictions, a modified solution acceptance criterion, and an advanced tabu list structure. Moreover, an improved dynamic programming procedure is integrated to optimally find the charging station visits in shorter computational times. The proposed hybrid SA/TS is tested on several TSPTW and ETSPTW benchmark problems and compared with well-known solution approaches. Results of these experiments show that the proposed algorithm outperforms the other considered competitor algorithms both with regard to solution quality and computational time. Furthermore, 26 new best results are obtained for the ETSPTW instances. In addition, the hybrid algorithm is applied to a new problem set generated for the ETSPTW-MCR by extending the ETSPTW problems found in the literature. Comparisons with the ETSPTW results show that significant distance savings are found for most of the instances by charging the electric vehicle at customer locations. As a result of the computational studies, it should be concluded that the proposed algorithm is capable of finding efficient and more realistic route plans for the electric vehicles.