An efficiency-based path-scanning heuristic for the 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, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 103, p. 288-295, MAR 2019.
• Citações Web of Science: 1

Resumo

The capacitated arc routing problem (CARP) is an important combinatorial optimization problem that has been extensively studied in the last decades. The objective is to optimize routes that service demands located on the edges of a graph, given a fleet of homogeneous vehicles with limited capacity that starts and ends its routes at a specific node (depot). This work proposes a new path-scanning heuristic for the CARP which introduces the concept of efficiency rule. Given the current vehicle location, its traversed distance and the amount of serviced demand, the efficiency rule selects the most promising edges to service next. Computational experiments conducted on a set of benchmark instances reveal that the proposed heuristic substantially outperformed all previous path-scanning heuristics from literature. (C) 2018 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