AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem

Vinícius R. Máximo (), Jean-François Cordeau () and Mariá C. V. Nascimento ()
Additional contact information
Vinícius R. Máximo: Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos-SP 12247-014, Brazil
Jean-François Cordeau: HEC Montreal, Montreal, Quebec H3T 2A7, Canada; GERAD, Montreal, Quebec H3T 2A7, Canada
Mariá C. V. Nascimento: Divisão de Ciência da Computação (IEC), Instituto Tecnológico de Aeronáutica (ITA), São José dos Campos-SP 12228-900, Brazil

INFORMS Journal on Computing, 2024, vol. 36, issue 4, 974-986

Abstract: 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.

Keywords: combinatorial optimization; capacitated vehicle routing problem (CVRP); adaptive iterated local search (AILS); learning in metaheuristics; large-scale instances (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:4:p:974-986

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().