Jump to content

Large-scale capacitated arc routing problem

Add links
From Wikipedia, the free encyclopedia

A large-scale capacitated arc routing problem (LSCARP) is a variant of the capacitated arc routing problem 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.[1]

LSCARP can be solved with a divide and conquer algorithm applied to route cutting off decomposition.[2]

The LSCARP can also be solved with an iterative local search that improves on upper and lower bounds of other methods.[3]

An LSCARP algorithm has been applied to waste collection in Denmark with a fast heuristic named FAST-CARP.[4]

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[5]

Zhang et al. created a metaheuristic to solve a generalization named the large-scale multi-depot CARP (LSMDCARP) named route clustering and search heuristic.[6]

An algorithm for the LSCARP named Extension step and statistical filtering for large-scale CARP (ESMAENS) was developed in 2017.[7]

The LSCARP can be extended to a large-scale capacitated vehicle routing problem with a hierarchical decomposition algorithm.[8] The LSCVRP can be solved with an evolutionary method based on local search.[9] Solving the LSCVRP can be done by integrated support vector machines and random forest methods.[10]

An algorithm to solve LSCARP based on simulated annealing named FILO was developed by Accorsi et al.[11]

References

[edit]
  1. ^ Mei, Yi; Li, Xiaodong; Yao, Xin (June 2014). "Cooperative Coevolution With Route Distance Grouping for Large-Scale Capacitated Arc Routing Problems". IEEE Transactions on Evolutionary Computation. 18 (3): 435–449. doi:10.1109/TEVC.2013.2281503. ISSN 1089-778X. S2CID 4851980. Archived from the original on 2022-06-15. Retrieved 2022-07-14.
  2. ^ Zhang, Yuzhou; Mei, Yi; Zhang, Buzhong; Jiang, Keqin (2021-04-01). "Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition". Information Sciences. 553: 208–224. arXiv:1912.12667. doi:10.1016/j.ins.2020.11.011. ISSN 0020-0255. S2CID 209516398.
  3. ^ Martinelli, Rafael; Poggi, Marcus; Subramanian, Anand (2013-08-01). "Improved bounds for large scale capacitated arc routing problem". Computers & Operations Research. 40 (8): 2145–2160. doi:10.1016/j.cor.2013.02.013. ISSN 0305-0548.
  4. ^ Wøhlk, Sanne; Laporte, Gilbert (2018-12-02). "A fast heuristic for large-scale capacitated arc routing problems". Journal of the Operational Research Society. 69 (12): 1877–1887. doi:10.1080/01605682.2017.1415648. ISSN 0160-5682. S2CID 58021779.
  5. ^ de Armas, Jesica; Keenan, Peter; Juan, Angel A.; McGarraghy, Seán (2019-02-01). "Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics". Annals of Operations Research. 273 (1): 135–162. doi:10.1007/s10479-018-2777-3. ISSN 1572-9338. S2CID 59222547. Archived from the original on 2022-07-14. Retrieved 2022-07-14.
  6. ^ Zhang, Yuzhou; Mei, Yi; Huang, Shihua; Zheng, Xin; Zhang, Cuijuan (2021). "A Route Clustering and Search Heuristic for Large-Scale Multidepot-Capacitated Arc Routing Problem". IEEE Transactions on Cybernetics. 52 (8): 8286–8299. doi:10.1109/TCYB.2020.3043265. ISSN 2168-2275. PMID 33531309. S2CID 231787553. Archived from the original on 2022-07-14. Retrieved 2022-07-14.
  7. ^ Shang, Ronghua; Du, Bingqi; Dai, Kaiyun; Jiao, Licheng; Xue, Yu (2018-06-01). "Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems". Natural Computing. 17 (2): 375–391. doi:10.1007/s11047-016-9606-x. ISSN 1572-9796. S2CID 12045910. Archived from the original on 2022-07-14. Retrieved 2022-07-14.
  8. ^ Zhuo, Er; Deng, Yunjie; Su, Zhewei; Yang, Peng; Yuan, Bo; Yao, Xin (June 2019). "An Experimental Study of Large-scale Capacitated Vehicle Routing Problems". 2019 IEEE Congress on Evolutionary Computation (CEC). pp. 1195–1202. doi:10.1109/CEC.2019.8790042. ISBN 978-1-7281-2153-6. S2CID 199508674. Archived from the original on 2022-07-14. Retrieved 2022-07-14.
  9. ^ Xiao, Jianhua; Zhang, Tao; Du, Jingguo; Zhang, Xingyi (19 November 2019). "An Evolutionary Multiobjective Route Grouping-Based Heuristic Algorithm for Large-Scale Capacitated Vehicle Routing Problems". IEEE Transactions on Cybernetics. 51 (8): 4173–4186. doi:10.1109/TCYB.2019.2950626. ISSN 2168-2275. PMID 31751261. S2CID 208227740. Archived from the original on 14 July 2022. Retrieved 14 July 2022.
  10. ^ Cavalcanti Costa, Joao Guilherme; Mei, Yi; Zhang, Menzjie (December 2012). "Learning Penalisation Criterion of Guided Local Search for Large Scale Vehicle Routing Problem". 2021 IEEE Symposium Series on Computational Intelligence (SSCI). pp. 1–8. doi:10.1109/SSCI50451.2021.9659939. ISBN 978-1-7281-9048-8. S2CID 246288885.
  11. ^ Accorsi, Luca; Vigo, Daniele (2021-07-01). "A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems". Transportation Science. 55 (4): 832–856. doi:10.1287/trsc.2021.1059. hdl:1871.1/afb5bb43-3ee8-4e81-8698-0e45644f89be. ISSN 0041-1655. S2CID 234370340. Archived from the original on 2022-07-14. Retrieved 2022-07-14.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Large-scale_capacitated_arc_routing_problem&oldid=1206210391"