A partial tours based path-scanning heuristic for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is known to be NP-Hard combinatorial optimization problem, and hence is not expected to be resolved in polynomial time for the general case. Consequently numerous heuristics and metaheuristics approaches have been developed to solve it. In this paper an “partial tours” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy heuristics for this problem. The innovation consists basically of creating a partial tours set to determine the promising segments in all tours. The quality of this new approach was tested on nine standard datasets and the results were compared against two path-scanning heuristics. The empirical study indicate that the “partial tours” approach gives a good results.