An improved sequential insertion algorithm and tabu search to vehicle routing problem with time windows
RAIRO - Operations Research · 2024-03 · 58 (2) · 1979-1999
DOI: 10.1051/ro/2024069 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Operations Research, online erschienen am 24.04.2024. Verfasst von Bin Yue und 4 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
The vehicle routing problem (VRP) is a well-researched problem in the operations re- search literature. This paper studies a vehicle routing problem with time windows. Based on Solomon’s research, an improved sequential initialization algorithm, Solomon i1 with DTWC (Solomon i1 with Dynamic Time Windows Compatibility), is proposed in this paper to construct feasible initial solutions with higher quality in less calculation time. A tabu search with VNS (Variable Neighborhood Search) and the Metropolis criterion is used to further optimize the solutions that the proposed initialization algorithm provides. We run computational experiments on cases of well-known problems. Results show that compared to the initialization method before the change, our improved initialization approach performs well in terms of providing a better feasible initialization solution in less time, with an average 10% improvement in solution quality and an average 34% computational time savings. The proposed initialization algorithm’s superiority is also demonstrated by the tabu search’s better performance on the initial solutions it produces.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Yue, B., Yang, J., Ma, J., Shi, J., & Shangguan, L. (2024). An improved sequential insertion algorithm and tabu search to vehicle routing problem with time windows. RAIRO - Operations Research, 58(2), 1979-1999. https://doi.org/10.1051/ro/2024069
Vancouver
Yue B, Yang J, Ma J, Shi J, Shangguan L. An improved sequential insertion algorithm and tabu search to vehicle routing problem with time windows. RAIRO - Operations Research. 2024;58(2):1979-1999. doi:10.1051/ro/2024069
BibTeX
@article{Yue2024,
author = {Yue, Bin and Yang, Jie and Ma, Junxu and Shi, Jinfa and Shangguan, Linjian},
title = {An improved sequential insertion algorithm and tabu search to vehicle routing problem with time windows},
journal = {RAIRO - Operations Research},
year = {2024},
volume = {58},
number = {2},
pages = {1979--1999},
doi = {10.1051/ro/2024069}
}
EUVIMED