Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

An efficiency-based path-scanning heuristic for the capacitated arc routing problem

Full text
Arakaki, Rafael Kendy [1] ; Usberti, Fabio Luiz [1]
Total Authors: 2
[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil
Total Affiliations: 1
Document type: Journal article
Source: Computers & Operations Research; v. 103, p. 288-295, MAR 2019.
Web of Science Citations: 1

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)

FAPESP's process: 16/00315-0 - Formulations and Algorithms for Arc Routing Problems
Grantee:Rafael Kendy Arakaki
Support type: Scholarships in Brazil - Doctorate