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.
Solving the CARP involves the study of graph theory, arc routing, operations research, and geographical routing algorithms to find the
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between ...
efficiently.
The CARP is
NP-hard arc routing problem
Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing p ...
.
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.
References
{{Reflist
Graph theory