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

Autor(es)

Maximo, Vinicius R. ; Cordeau, Jean-Francois ; Nascimento, Maria C. V.

• Tipo de documento: Artigo Científico
• Fonte: INFORMS JOURNAL ON COMPUTING; v. 36, n. 4, p. 13-pg., 2024-07-29.

Resumo

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. (AU)

• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/22067-6 - Estratégias de aprendizado para busca heurística em problemas de otimização combinatória
• Beneficiário: Mariá Cristina Vasconcelos Nascimento Rosset
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs