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

İlker Küçükoğlu, R.R.H. Dewil, Dirk Cattrysse

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)279-303
Number of pages25
JournalExpert Systems with Applications
Volume134
Publication statusPublished - 2019

Fingerprint

Traveling salesman problem
Tabu search
Simulated annealing
Electric vehicles
Dynamic programming

Keywords

  • Traveling salesman problem
  • Electric vehicles
  • Metaheuristics
  • Dynamic Programming

Cite this

@article{4ef13e063f6c4135a66debc40dd88e27,
title = "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.",
keywords = "Traveling salesman problem, Electric vehicles, Metaheuristics, Dynamic Programming",
author = "İlker K{\"u}{\cc}{\"u}koğlu and R.R.H. Dewil and Dirk Cattrysse",
year = "2019",
language = "English",
volume = "134",
pages = "279--303",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier",

}

Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates. / Küçükoğlu, İlker; Dewil, R.R.H.; Cattrysse, Dirk.

In: Expert Systems with Applications, Vol. 134, 2019, p. 279-303.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Küçükoğlu, İlker

AU - Dewil, R.R.H.

AU - Cattrysse, Dirk

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Traveling salesman problem

KW - Electric vehicles

KW - Metaheuristics

KW - Dynamic Programming

M3 - Article

VL - 134

SP - 279

EP - 303

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

ER -