|
Capacitated arc routing problemIn 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.[1] Solving the CARP involves the study of graph theory, arc routing, operations research, and geographical routing algorithms to find the shortest path efficiently. The CARP is NP-hard arc routing problem. 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.[2] References
|