AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem
INFORMS Journal on Computing · 2024-07 · 36 (4) · 974-986
DOI: 10.1287/ijoc.2023.0106 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2024-07. Verfasst von Vinícius R. Máximo und 2 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 15 Literaturangaben.
Abstract (Originalsprache)
A recent study on the classical capacitated vehicle routing problem (CVRP) introduced an adaptive version of the widely used iterated local search paradigm, hybridized with a path-relinking (PR) strategy. The solution method, called adaptive iterated local search (AILS)-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances suggest that PR is too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an AILS combined with mechanisms to handle large CVRP instances, called AILS-II. The computational cost of this implementation is reduced, whereas the algorithm also searches the solution space more efficiently. AILS-II is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best-known solutions. Moreover, AILS-II consistently outperforms the state of the art on larger instances with up to 30,000 vertices. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 2013/07375-0, 2019/22067-6, and 2022/05803-3] and the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309385/2021-0 and 403735/2021-1]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0106 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0106 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Zitieren
APA
Máximo, V. R., Cordeau, J., & Nascimento, M. C. V. (2024). AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem. INFORMS Journal on Computing, 36(4), 974-986. https://doi.org/10.1287/ijoc.2023.0106
Vancouver
Máximo VR, Cordeau J, Nascimento MCV. AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem. INFORMS Journal on Computing. 2024;36(4):974-986. doi:10.1287/ijoc.2023.0106
BibTeX
@article{Mximo2024,
author = {Máximo, Vinícius R. and Cordeau, Jean-François and Nascimento, Mariá C. V.},
title = {AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem},
journal = {INFORMS Journal on Computing},
year = {2024},
volume = {36},
number = {4},
pages = {974--986},
doi = {10.1287/ijoc.2023.0106}
}
EUVIMED