Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates. (15th November 2019)

• Record Type: Journal Article
• Authors: Küçükoğlu, İlker; Dewil, Reginald; Cattrysse, Dirk
• Is Part Of: Expert systems with applications. Volume 134(2019)
• Page Start: 279
• Page End: 303
• Publication Date: 2019-11-15
• Subjects: Travelling salesman -- Electric vehicles -- Metaheuristics -- Dynamic programming; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.05.037
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A new variant of ETSPTW is proposed by considering mixed charging rates at stations. A mathematical formulation of the problem is presented. A new hybrid algorithm based on SA and TS is integrated with dynamic programming. New best results for both the TSPTW and ETSPTW are obtained. Shorter paths are found by considering charging operations at customer sites. 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.