The Capacitated Arc Routing Problem
(CARP)

Problem description:
Given a graph, G = (N,E,C,Q), and a fleet of capacitated vehicles initially located in a special Depot node, find a set of tours sch that
1) Each edge with positive demand is serviced by exactly one vehicle,
2) The vehicle capacities are respected, and
3) The total routing is minimized.

State of the Art (2005):

Computational Results:

Benchmark Instances: