Capacitated arc routing problem: Difference between revisions

Revision as of 22:16, 22 May 2025

Latest revision as of 11:23, 25 August 2025

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 |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 |s2cidbibcode=4851980 |issn=1089-778X |access-date=2022-07-14 |archive-date=2022-06-15 |archive-url=https://web2014ITEC.archive.org/web/20220615183634/http://ieeexplore.ieee18.org/document/6595573/.435M |url-statuss2cid=live4851980 |url-accessissn=subscription1089-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>

Line 20:

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 |url=https://ieeexplore.ieee.org/document/9345509 |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 |access-date=2022-07-14 |archive-date=2022-07-14 |archive-url=https://web.archive.org/web/20220714234625/https://ieeexplore.ieee.org/abstract/document/9345509 |url-status=live |url-access=subscription }}</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 |chapter-url=https://ieeexplore.ieee.org/document/8790042 |pages=1195–1202 |doi=10.1109/CEC.2019.8790042 |isbn=978-1-7281-2153-6 |s2cid=199508674 |access-date=2022-07-14 |archive-date=2022-07-14 |archive-url=https://web.archive.org/web/20220714234625/https://ieeexplore.ieee.org/abstract/document/8790042 |url-status=live }}</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 |url=https://ieeexplore.ieee.org/document/8906244 |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 |access-date=14 July 2022 |archive-date=14 July 2022 |archive-url=https://web.archive.org/web/20220714234625/https://ieeexplore.ieee.org/abstract/document/8906244 |url-status=live |url-access=subscription }}</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>