TheIn Capacitatedmathematics, Arcthe Routing'''capacitated Problemarc oftenrouting referred to asproblem (CARP)''' is a mathematical problem that focuses onof 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.<ref>{{Citation |last=Prins |first=Christian |title=Chapter 7: The Capacitated Arc Routing Problem: Heuristics |date=2015-02-05 |url=https://epubs.siam.org/doi/abs/10.1137/1.9781611973679.ch7 |work=Arc Routing |pages=131–157 |series=MOS-SIAM Series on Optimization |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611973679.ch7 |isbn=978-1-61197-366-2 |access-date=2022-07-14}}</ref>
Solving the CARP involves the study of graph theory, arc routing, operations research, and geographical routing algorithms to find the [[Shortest path problem|shortest path]] efficiently.
Line 7:
The CARP is [[NP-hardness|NP-hard]] [[arc routing problem]].
The CARP can be solved with combinatorial optimization including [[Convexconvex hull|convex hulls]]s.
The [[Large large-scale capacitated arc routing problem|Large Scale Capacitated Arc Routing Problem]]/ (LSCARP) is a variant of the Capacitatedcapacitated Arcarc Routingrouting Problemproblem that applies to hundreds of edges and nodes to realistically simulate and model large complex environments.<ref>{{Cite journal |last=Mei |first=Yi |last2=Li |first2=Xiaodong |last3=Yao |first3=Xin |date=June 2014 |title=Cooperative Coevolution With Route Distance Grouping for Large-Scale Capacitated Arc Routing Problems |url=http://ieeexplore.ieee.org/document/6595573/ |journal=IEEE Transactions on Evolutionary Computation |volume=18 |issue=3 |pages=435–449 |doi=10.1109/TEVC.2013.2281503 |issn=1089-778X}}</ref>
