Content deleted Content added
Citation bot (talk | contribs) Added bibcode. Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 372/1032 |
|||
(2 intermediate revisions by 2 users not shown) | |||
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|url-access=subscription }}</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 10:
A large-scale capacitated arc routing problem (LSCARP) is a variant of the CARP that covers 300 or more edges to model complex arc routing problems at large scales.
Yi Mei et al. published an algorithm for solving the large-scale capacitated arc routing problem using a cooperative co-evolution algorithm.<ref name=":0">{{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
LSCARP can be solved with a divide and conquer algorithm applied to route cutting off decomposition.<ref>{{Cite journal |last1=Zhang |first1=Yuzhou |last2=Mei |first2=Yi |last3=Zhang |first3=Buzhong |last4=Jiang |first4=Keqin |date=2021-04-01 |title=Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition |url=https://www.sciencedirect.com/science/article/pii/S0020025520310975 |journal=Information Sciences |language=en |volume=553 |pages=208–224 |doi=10.1016/j.ins.2020.11.011 |arxiv=1912.12667 |s2cid=209516398 |issn=0020-0255}}</ref>
Line 18:
An LSCARP algorithm has been applied to waste collection in Denmark with a fast heuristic named FAST-CARP.<ref>{{Cite journal |last1=Wøhlk |first1=Sanne |last2=Laporte |first2=Gilbert |date=2018-12-02 |title=A fast heuristic for large-scale capacitated arc routing problems |url=https://doi.org/10.1080/01605682.2017.1415648 |journal=Journal of the Operational Research Society |volume=69 |issue=12 |pages=1877–1887 |doi=10.1080/01605682.2017.1415648 |s2cid=58021779 |issn=0160-5682}}</ref>
The algorithm is also often referred to as the Time Capacitated Arc Routing Problem often referred to as TCARP. The TCARP can be solved with a metaheuristic in a reasonable amount of time. The TCARP often arises when volume constraints do not apply for example meter reading<ref>{{Cite journal |last1=de Armas |first1=Jesica |last2=Keenan |first2=Peter |last3=Juan |first3=Angel A. |last4=McGarraghy |first4=Seán |date=2019-02-01 |title=Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics |url=https://doi.org/10.1007/s10479-018-2777-3 |journal=Annals of Operations Research |language=en |volume=273 |issue=1 |pages=135–162 |doi=10.1007/s10479-018-2777-3 |s2cid=59222547 |issn=1572-9338 |access-date=2022-07-14 |archive-date=2022-07-14 |archive-url=https://web.archive.org/web/20220714234626/https://link.springer.com/article/10.1007/s10479-018-2777-3 |url-status=live |url-access=subscription }}</ref>
Zhang et al. created a metaheuristic to solve a generalization named the large-scale multi-depot CARP (LSMDCARP) named route clustering and search heuristic.<ref>{{Cite journal |last1=Zhang |first1=Yuzhou |last2=Mei |first2=Yi |last3=Huang |first3=Shihua |last4=Zheng |first4=Xin |last5=Zhang |first5=Cuijuan |date=2021 |title=A Route Clustering and Search Heuristic for Large-Scale Multidepot-Capacitated Arc Routing Problem
An algorithm for the LSCARP named Extension step and statistical filtering for large-scale CARP (ESMAENS) was developed in 2017.<ref>{{Cite journal |last1=Shang |first1=Ronghua |last2=Du |first2=Bingqi |last3=Dai |first3=Kaiyun |last4=Jiao |first4=Licheng |last5=Xue |first5=Yu |date=2018-06-01 |title=Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems |url=https://doi.org/10.1007/s11047-016-9606-x |journal=Natural Computing |language=en |volume=17 |issue=2 |pages=375–391 |doi=10.1007/s11047-016-9606-x |s2cid=12045910 |issn=1572-9796 |access-date=2022-07-14 |archive-date=2022-07-14 |archive-url=https://web.archive.org/web/20220714234627/https://link.springer.com/article/10.1007/s11047-016-9606-x |url-status=live |url-access=subscription }}</ref>
The LSCARP can be extended to a large-scale capacitated vehicle routing problem with a hierarchical decomposition algorithm.<ref>{{Cite book |last1=Zhuo |first1=Er |last2=Deng |first2=Yunjie |last3=Su |first3=Zhewei |last4=Yang |first4=Peng |last5=Yuan |first5=Bo |last6=Yao |first6=Xin |title=2019 IEEE Congress on Evolutionary Computation (CEC) |chapter=An Experimental Study of Large-scale Capacitated Vehicle Routing Problems |date=June 2019
An algorithm to solve LSCARP based on simulated annealing named FILO was developed by Accorsi et al.<ref>{{Cite journal |last1=Accorsi |first1=Luca |last2=Vigo |first2=Daniele |date=2021-07-01 |title=A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems |url=https://pubsonline.informs.org/doi/abs/10.1287/trsc.2021.1059 |journal=Transportation Science |volume=55 |issue=4 |pages=832–856 |doi=10.1287/trsc.2021.1059 |hdl=1871.1/afb5bb43-3ee8-4e81-8698-0e45644f89be |s2cid=234370340 |issn=0041-1655 |access-date=2022-07-14 |archive-date=2022-07-14 |archive-url=https://web.archive.org/web/20220714234626/https://pubsonline.informs.org/doi/abs/10.1287/trsc.2021.1059 |url-status=live |hdl-access=free }}</ref>
Line 32:
[[Category:Graph theory]]
[[Category:Graph algorithms]]
[[Category:Path planning]]
|