Hybrid genetic algorithm for the open capacitated arc routing problem

Autor(es)

Arakaki, Rafael Kendy ^[1] ; Usberti, Fabio Luiz ^[1]

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

^[1] Univ Estadual Campinas, Inst Comp, Av Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 90, p. 221-231, FEB 2018.
• Citações Web of Science: 8

Resumo

The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard arc routing problem where, given an undirected graph, the objective is to find the least cost set of routes that services all edges with positive demand (required edges). The routes are subjected to capacity constraints in relation to edge demands. The OCARP differs from the Capacitated Arc Routing Problem (CARP) since OCARP does not consider a depot and routes are not constrained to form cycles. A hybrid genetic algorithm with feasibilization and local search procedures is proposed for the OCARP. Computational experiments conducted on a set of benchmark instances reveal that the proposed hybrid genetic algorithm achieved the best upper bounds for almost all instances. (C) 2017 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 16/00315-0 - Formulações e Algoritmos para Problemas de Roteamento em Arcos
• Beneficiário: Rafael Kendy Arakaki
• Modalidade de apoio: Bolsas no Brasil - Doutorado