In mathematics, the capacitated arc routing problem (CARP) is that of finding the shortest tour with a minimum graph/travel distance of a mixed graph with undirected edges and directed arcs given capacity constraints for objects that move along the graph that represent snow-plowers, street sweeping machines, or winter gritters, or other real-world objects with capacity constraints.
The constraint can be imposed for the length of time the vehicle is away from the central depot, or a total distance traveled, or a combination of the two with different weighting factors.
There are many different variations of the CARP described in the book Arc Routing:Problems, Methods, and Applications by Ángel Corberán and Gilbert Laporte.
The CARP can be solved with combinatorial optimization including convex hulls.
The large-scale capacitated arc routing problem (LSCARP) is a variant of the capacitated arc routing problem that applies to hundreds of edges and nodes to realistically simulate and model large complex environments.