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.[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
edit- ^ Prins, Christian (2015-02-05), "Chapter 7: The Capacitated Arc Routing Problem: Heuristics", Arc Routing, MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics, pp. 131–157, doi:10.1137/1.9781611973679.ch7, ISBN 978-1-61197-366-2, retrieved 2022-07-14
- ^ Mei, Yi; Li, Xiaodong; Yao, Xin (June 2014). "Cooperative Coevolution With Route Distance Grouping for Large-Scale Capacitated Arc Routing Problems". IEEE Transactions on Evolutionary Computation. 18 (3): 435–449. doi:10.1109/TEVC.2013.2281503. ISSN 1089-778X. S2CID 4851980.