Busca avançada
Ano de início
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A hybrid approach based on genetic algorithm and nearest neighbor heuristic for solving the capacitated vehicle routing problem

Texto completo
de Araujo Lima, Stanley Jefferson [1] ; de Araujo, Sidnei Alves [1] ; Triguis Schimit, Pedro Henrique [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Nove Julho, Programa Posgrad Informat & Gestao Conhecimento, Rua Vergueiro 235-249, BR-01504001 Sao Paulo, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Citações Web of Science: 0

This work presents a hybrid approach called GA-NN for solving the Capacitated Vehicle Routing Problem (CVRP) using Genetic Algorithms (GA) and Nearest Neighbor heuristic (NN). The first technique was applied to determine the groups of customers to be served by the vehicles while the second is responsible to build the route of each vehicle. In addition, the heuristics of Gillett \& Miller (GM) and Downhill (DH) were used, respectively, to generate the initial population of GA and to refine the solutions provided by GA. In the results section, we firstly present experiments demonstrating the performance of the NN heuristic for solving the Shortest Path and Traveling Salesman problems. The results obtained in such experiments constitute the main motivation for proposing the GA-NN. The second experimental study shows that the proposed hybrid approach achieved good solutions for instances of CVRP widely known in the literature, with low computational cost. It also allowed us to evidence that the use of GM and DH helped the hybrid GA-NN to converge on promising points in the search space, with a small number of generations. (AU)

Processo FAPESP: 17/12671-8 - Laboratório de dinâmicas populacionais
Beneficiário:Pedro Henrique Triguis Schimit
Linha de fomento: Auxílio à Pesquisa - Regular