A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem

Autor(es)

Maximo, Vinicius R. ^[1] ; Nascimento, V, Maria C.

Afiliação do(s) autor(es)

^[1] V, Univ Fed Sao Paulo, UNIFESP, Inst Ciencia & Tecnol, Av Cesare MG Lattes 1201, BR-12247014 Sao Jose Dos Campos, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 294, n. 3, p. 1108-1119, NOV 1 2021.
• Citações Web of Science: 0

Resumo

Metaheuristics are widely employed to solve hard optimization problems, like vehicle routing problems (VRP), for which exact solution methods are impractical. In particular, local search-based metaheuristics have been successfully applied to the capacitated VRP (CVRP). The CVRP aims at defining the minimum cost delivery routes for a given set of identical vehicles since each vehicle only travels one route and there is a single (central) depot. The best metaheuristics to the CVRP avoid getting stuck in local optima by embedding specific hill-climbing mechanisms such as diversification strategies into the solution methods. This paper introduces a hybridization of a novel adaptive version of Iterated Local Search with PathRelinking (AILS-PR) to the CVRP. The major contribution of this paper is an automatic mechanism to control the diversity step of the metaheuristic to allow it to escape from local optima. The results of experiments with 100 benchmark CVPR instances show that AILS-PR outperformed the state-of-the-art CVRP metaheuristics. (c) 2021 Elsevier B.V. All rights reserved. (AU)

• 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