Clustering-based Search in a Memetic Algorithm for the Vehicle Routing Problem with Time Windows

Autor(es)

Coral, Daniel Bustos ; Santos, Maristela Oliveira ; Toledo, Claudio ; Fernando Nino, Luis ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2018-01-01.

Resumo

This paper addresses the vehicle routing problem with time windows (VRPTW), aiming to minimize the total travel time. A simple memetic algorithm (MA) is proposed for solving this problem. At the beginning of the search, a clustering procedure is applied to customers' spatial information. The search procedure consists of relocating customers between close routes, seeking to minimize detour costs associated with the relocations. The information gathered by the clustering procedure is used to identify which routes lie close to each other. Computational experiments on the Solomon's benchmark set show the effectiveness of the proposed approach, which produces competitive solutions and outperforms four out of six solution approaches considered for comparison regarding the travel cost attained over all the instances of the benchmark set. (AU)

• 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