Capacitated arc routing problem: Difference between revisions

Revision as of 03:09, 30 October 2022

Latest revision as of 11:23, 25 August 2025

(12 intermediate revisions by 6 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 7:

The CARP is [[NP-hardness|NP-hard]] [[arc routing problem]].

==Large-scale capacitated arc routing problem==

The CARP can be solved with combinatorial optimization including [[convex hull]]s.

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.

TheYi [[large-scaleMei capacitatedet arcal. routingpublished problem]]an (LSCARP)algorithm isfor asolving variantthe of thelarge-scale capacitated arc routing problem thatusing appliesa tocooperative hundredsco-evolution of edges and nodes to realistically simulate and model large complex environmentsalgorithm.<ref name=":0">{{Cite journal |lastlast1=Mei |firstfirst1=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 |bibcode=2014ITEC...18..435M |s2cid=4851980 |issn=1089-778X }}</ref>

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>

The LSCARP can also be solved with an iterative local search that improves on upper and lower bounds of other methods.<ref>{{Cite journal |last1=Martinelli |first1=Rafael |last2=Poggi |first2=Marcus |last3=Subramanian |first3=Anand |date=2013-08-01 |title=Improved bounds for large scale capacitated arc routing problem |journal=Computers & Operations Research |language=en |volume=40 |issue=8 |pages=2145–2160 |doi=10.1016/j.cor.2013.02.013 |issn=0305-0548 |doi-access=free }}</ref>

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 |journal=IEEE Transactions on Cybernetics |volume=52 |issue=8 |pages=8286–8299 |doi=10.1109/TCYB.2020.3043265 |pmid=33531309 |s2cid=231787553 |issn=2168-2275 }}</ref>

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 |pages=1195–1202 |doi=10.1109/CEC.2019.8790042 |isbn=978-1-7281-2153-6 |s2cid=199508674 }}</ref> The LSCVRP can be solved with an evolutionary method based on local search.<ref>{{Cite journal |last1=Xiao |first1=Jianhua |last2=Zhang |first2=Tao |last3=Du |first3=Jingguo |last4=Zhang |first4=Xingyi |date=19 November 2019 |title=An Evolutionary Multiobjective Route Grouping-Based Heuristic Algorithm for Large-Scale Capacitated Vehicle Routing Problems |journal=IEEE Transactions on Cybernetics |volume=51 |issue=8 |pages=4173–4186 |doi=10.1109/TCYB.2019.2950626 |pmid=31751261 |s2cid=208227740 |issn=2168-2275 }}</ref> Solving the LSCVRP can be done by integrated support vector machines and random forest methods.<ref>{{Cite book |last1=Cavalcanti Costa |first1=Joao Guilherme |last2=Mei |first2=Yi |last3=Zhang |first3=Menzjie |title=2021 IEEE Symposium Series on Computational Intelligence (SSCI) |chapter=Learning Penalisation Criterion of Guided Local Search for Large Scale Vehicle Routing Problem |date=December 2012 |chapter-url=https://ieeexplore.ieee.org/document/9659939 |pages=1–8 |doi=10.1109/SSCI50451.2021.9659939|isbn=978-1-7281-9048-8 |s2cid=246288885 |url=https://figshare.com/articles/conference_contribution/Learning_Penalisation_Criterion_of_Guided_Local_Search_for_Large_Scale_Vehicle_Routing_Problem/21085249 }}</ref>

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>

== References ==

Line 15 ⟶ 32:

[[Category:Graph theory]]

[[Category:Graph algorithms]]

[[Category:Path planning]]

[[Category:Combinatorial optimization]]