The Undirected Capacitated Arc Routing Problem (UCARP or CARP), first introduced by Golden and Wong , considers an undirected network or graph where every edge has a nonnegative length or cost and some of the edges (also called the required edges) have a positive demand for service. A fleet of identical vehicles, each vehicle with limited capacity, is based at the depot. The aim in the UCARP is to find a set of vehicle tours of total minimum length, each tour starting and ending at the depot, such that every required edge is serviced in exactly one tour, and that the total load on each route does not exceed the vehicle capacity. Heuristic solution procedures, lower bounds, and exact methods for CARP were covered in Chapters 7, 8, and 9 of this book.
|Name||MOS-SIAM Series on Optimization|
|Publisher||Society for Industrial and Applied Mathematics (SIAM)|