Jump to content

Capacitated arc routing problem

Add links
From Wikipedia, the free encyclopedia

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.[1]

Solving the CARP involves the study of graph theory, arc routing, operations research, and geographical routing algorithms to find the shortest path efficiently.

The CARP is NP-hard arc routing problem.

Large-scale capacitated arc routing problem

[edit]

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.[2]

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

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

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

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

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

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

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

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

References

[edit]
  1. ^ Prins, Christian (2015-02-05), "Chapter 7: The Capacitated Arc Routing Problem: Heuristics", Arc Routing, MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics, pp. 131–157, doi:10.1137/1.9781611973679.ch7, ISBN 978-1-61197-366-2, retrieved 2022-07-14
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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.

References

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Capacitated_arc_routing_problem&oldid=1285183824"