Revision as of 05:30, 13 February 2023 edit Citation bot (talk \| contribs) Bots 5,871,187 edits Alter: url. URLs might have been anonymized. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. \| Use this bot. Report bugs. \| Suggested by Corvus florensis \| #UCB_webform 293/3500 ← Previous edit		Revision as of 03:14, 27 June 2023 edit undo Iljhgtn (talk \| contribs) Event coordinators, Extended confirmed users, New page reviewers, Pending changes reviewers, Rollbackers 77,531 edits m Spelling/grammar/punctuation/typographical correction Tag: Visual edit Next edit →
Line 1: 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.<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> Line 9: The CARP can be solved with combinatorial optimization including [[convex hull]]s. 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.<ref>{{Cite journal \|last1=Mei \|first1=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=https://ieeexplore.ieee.org/document/6595573 \|journal=IEEE Transactions on Evolutionary Computation \|volume=18 \|issue=3 \|pages=435–449 \|doi=10.1109/TEVC.2013.2281503 \|s2cid=4851980 \|issn=1089-778X}}</ref> == References ==

Capacitated arc routing problem: Difference between revisions