Approximate Solutions for the Capacitated Arc Routing Problem
01 January 1989
The Capacitated Arc Routing Problem (CARP), is a capacitated variation of the arc routing problems in which there is a capacity constraint associated with each vehicle. Due to the computational complexity of the problem, recent research has focused on developing and testing heuristic algorithms which solve the CARP approximately. In this paper, we review some of the existing solution procedures, analyze their complexity, and present two modifications of the existing methods to obtain near-optimal solutions for the CARP.