Clustering-Based Crossover in an Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows

Autor(es)

Coral, Daniel Bustos ; Santos, Maristela Oliveira ; Motta Toledo, Claudio Fabiano ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 2017 IEEE 29TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2017); v. N/A, p. 8-pg., 2017-01-01.

Resumo

This paper addresses the Vehicle Routing Problem with Time Windows (VRPTW). A crossover operator which uses the information gathered by a clustering procedure is described. In the proposed approach, a hierarchical clustering procedure is applied to the customers' spatial data. The crossover procedure creates a new solution by removing and reinserting customers, and uses the clusters to identify the most promising reinsertion locations. Thus, the proposed operator avoids exhaustive search. Computational experiments show the effectiveness of the proposed operator, that produces competitive solutions and improves the overall performance of the evolutionary algorithm when compared against an approach based on exhaustive search. (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