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

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)