Capacitated arc routing problem: Difference between revisions

Revision as of 23:14, 14 July 2022

Revision as of 23:15, 14 July 2022

Line 3:

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.

The CARP is [[NP-hardness|NP-hard]].

The CARP can be solved with combinatorial optimization including [[Convex hull|convex hulls]].

The Large Scale Capacitated Arc Routing Problem 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.<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>