Journal Home > Volume 28 , Issue 5
Tsinghua Science and Technology 2023, 28(5): 916-928 https://doi.org/10.26599/TST.2022.9010052
Open Access | Issue | Published: 19 May 2023

Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems

Show Author's Information Wei Yu1( ),  Yujie Liao1,  Yichen Yang2
School of Mathematics, East China University of Science and Technology, Shanghai 200237, China
Sabre Lab Research Team, Sabre Inc., Southlake, TX 76092, USA
Keywords:
approximation algorithm, vehicle routing problem, multi-depot, arc routing problem, rural postman problem
Cite this article:
Yu W, Liao Y, Yang Y. Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems. Tsinghua Science and Technology, 2023, 28(5): 916-928. https://doi.org/10.26599/TST.2022.9010052
Download citation
EndNote(RIS)
BibTeX

349

Views

54

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

In this work, we investigate a generalization of the classical capacitated arc routing problem, called the Multi-depot Capacitated Arc Routing Problem (MCARP). We give exact and approximation algorithms for different variants of the MCARP. First, we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version. Second, for the multi-depot rural postman problem, i.e., a special case of the MCARP where the vehicles have infinite capacity, we develop a (2-12⁢k+1)-approximation algorithm ( k denotes the number of depots). Third, we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line. Lastly, we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.


menu
Abstract
Full text
Outline
About this article

Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems

Show Author's information Wei Yu1( ), Yujie Liao1, Yichen Yang2
School of Mathematics, East China University of Science and Technology, Shanghai 200237, China
Sabre Lab Research Team, Sabre Inc., Southlake, TX 76092, USA

Abstract

In this work, we investigate a generalization of the classical capacitated arc routing problem, called the Multi-depot Capacitated Arc Routing Problem (MCARP). We give exact and approximation algorithms for different variants of the MCARP. First, we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version. Second, for the multi-depot rural postman problem, i.e., a special case of the MCARP where the vehicles have infinite capacity, we develop a (2-12⁢k+1)-approximation algorithm ( k denotes the number of depots). Third, we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line. Lastly, we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.

Keywords: approximation algorithm, vehicle routing problem, multi-depot, arc routing problem, rural postman problem

References(32)

[1]
B. L. Golden and R. T. Wong, Capacitated arc routing problems, Networks, vol. 11, no. 3, pp. 305–315, 1981.
DOI Google Scholar
[2]
H. A. Eiselt, M. Gendreau, and G. Laporte, Arc routing problems, part II: The rural postman problem, Oper. Res., vol. 43, no. 3, pp. 399–414, 1995.
DOI Google Scholar
[3]
J. Park and B. I. Kim, The school bus routing problem: A review, Eur. J. Oper. Res., vol. 202, no. 2, pp. 311–319, 2010.
DOI Google Scholar
[4]
E. Fernández, D. Fontana, and M. G. Speranza, On the collaboration uncapacitated arc routing problem, Comput. Oper. Res., vol. 67, pp. 120–131, 2016.
DOI Google Scholar
[5]
A. Hertz, G. Laporte, and M. Mittaz, A Tabu search heuristic for the capacitated arc routing problem, Oper. Res., vol. 48, no. 1, pp. 129–135, 2000.
DOI Google Scholar
[6]
E. Fernández and J. Rodríguez-Pereira, Multi-depot rural postman problems, TOP, vol. 25, no. 2, pp. 340–372, 2017.
DOI Google Scholar
[7]
A. Kansou and A. Yassine, A two ant colony approaches for the multi-depot capacitated arc routing problem, in Proc. of the 2009 Int. Conf. Computers & Industrial Engineering, Troyes, France, 2009, pp. 1040–1045.
DOI Google Scholar
[8]
H. Hu, T. Liu, N. Zhao, Y. Zhou, and D. Min, A hybrid genetic algorithm with perturbation for the multi-depot capacitated arc routing problem, J. Appl. Sci., vol. 13, no. 16, pp. 3239–3244, 2013.
DOI Google Scholar
[9]
H. Chen, T. Cheng, and J. Shawe-Taylor, A balanced route design for min-max multiple-depot rural postman problem (MMMDRPP): A police patrolling case, Int. J. Geogr. Inform. Sci., vol. 32, no. 1, pp. 169–190, 2018.
DOI Google Scholar
[10]
J. Zhao and F. Zhu, A multi-depot vehicle-routing model for the explosive waste recycling, Int. J. Prod. Res., vol. 54, no. 2, pp. 550–563, 2016.
DOI Google Scholar
[11]
E. Fernández, G. Laporte, and J. Rodríguez-Pereira, A branch-and-cut algorithm for the multidepot rural postman problem, Transport. Sci., vol. 52, no. 2, pp. 353–369, 2018.
DOI Google Scholar
[12]
D. Krushinsky and T. van Woensel, An approach to the asymmetric multi-depot capacitated arc routing problem, Eur. J. Oper. Res., vol. 244, no. 1, pp. 100–109, 2015.
DOI Google Scholar
[13]
T. Liu, Z. Jiang, and N. Geng, A genetic local search algorithm for the multi-depot heterogeneous fleet capacitated arc routing problem, Flex. Serv. Manuf. J., vol. 26, no. 4, pp. 540–564, 2014.
DOI Google Scholar
[14]
M. Haimovich and A. H. G. R. Kan, Bounds and heuristics for capacitated routing problems, Math. Oper. Res., vol. 10, no. 4, pp. 527–542, 1985.
DOI Google Scholar
[15]
N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Operations Research Forum, vol. 3, p. 20, 2022.
DOI Google Scholar
[16]
R. van Bevern and V. A. Slugina, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Hist. Math., vol. 53, pp. 118–127, 2020.
DOI Google Scholar
[17]
M. Haimovich, A. H. G. R. Kan, and L. Stougie, Analysis of heuristics for vehicle routing problems, in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad, eds. Amsterdam, The Netherlands: Elsevier, 1988, pp. 47–61.
[18]
K. Altinkemer and B. Gavish, Technical note—Heuristics for delivery problems with constant error guarantees, Transport. Sci., vol. 24, no. 4, pp. 294–297, 1990.
DOI Google Scholar
[19]
K. Altinkemer and B. Gavish, Heuristics for unequal weight delivery problems with a fixed error guarantee, Oper. Res. Lett., vol. 6, no. 4, pp. 149–158, 1987.
DOI Google Scholar
[20]
J. Blauth, V. Traub, and J. Vygen, Improving the approximation ratio for capacitated vehicle routing, in Proc. 22nd Conf. Integer Programming and Combinatorial Optimization, Atlanta, GA, USA, 2021, pp. 1–14.
DOI Google Scholar
[21]
Z. Friggstad, R. Mousavi, M. Rahgoshay, and M. R. Salavatipour, Improved approximations for capacitated vehicle routing with unsplittable client demands, in Proc. 23rd Conf. Integer Programming and Combinatorial Optimization, Eindhoven, The Netherlands, 2022, pp. 251–261.
DOI Google Scholar
[22]
M. Labbé, G. Laporte, and H. Mercure, Capacitated vehicle routing on trees, Oper. Res., vol. 39, no. 4, pp. 616–622, 1991.
DOI Google Scholar
[23]
Y. Wu and X. Lu, Capacitated vehicle routing problem on line with unsplittable demands, J. Comb. Optim., vol. 44, no. 3, pp. 1953–1963, 2022.
DOI Google Scholar
[24]
C. Archetti, D. Feillet, M. Gendreau, and M. G. Speranza, Complexity of the VRP and SDVRP, Transp. Res. Part C: Emerg. Technol., vol. 19, no. 5, pp. 741–750, 2011.
DOI Google Scholar
[25]
K. Jansen, Bounds for the general capacitated routing problem, Networks, vol. 23, no. 3, pp. 165–173, 1993.
DOI Google Scholar
[26]
R. van Bevern, S. Hartung, A. Nichterlein, and M. Sorge, Constant-factor approximations for Capacitated Arc Routing without triangle inequality, Oper. Res. Lett., vol. 42, no. 4, pp. 290–292, 2014.
DOI Google Scholar
[27]
S. Wøhlk, An approximation algorithm for the capacitated arc routing problem, Open Oper. Res. J., vol. 2, no. 1, pp. 8–12, 2008.
DOI Google Scholar
[28]
C. L. Li and D. Simchi-Levi, Worst-case analysis of heuristics for multidepot capacitated vehicle routing Problems, ORSA J. Comput., vol. 2, no. 1, pp. 64–73, 1990.
DOI Google Scholar
[29]
B. Bhattacharya and Y. Hu, Approximation algorithms for the multi-vehicle scheduling problem, in Proc. 21st Int. Symp. Algorithms and Computation, Jeju Island, Republic of Korea, 2010, pp. 192–205.
DOI Google Scholar
[30]
A. Corberán and G. Laporte, Arc Routing: Problems, Methods, and Applications. Philadelphia, PA, USA: SIAM, 2015.
DOI
[31]
W. Yu, Z. Liu, and X. Bao, Approximation algorithms for some min-max postmen cover problems, Ann. Oper. Res., vol. 300, no. 1, pp. 267–287, 2021.
DOI Google Scholar
[32]
Z. Xu, L. Xu, and B. Rodrigues, An analysis of the extended Christofides heuristic for the k-depot TSP, Oper. Res. Lett., vol. 39, no. 3, pp. 218–223, 2011.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 23 June 2022
Revised: 03 October 2022
Accepted: 10 November 2022
Published: 19 May 2023
Issue date: October 2023

Copyright

© The author(s) 2023.

Acknowledgements

The authors are grateful to the anonymous referees for their valuable and constructive comments. This research was supported by the National Natural Science Foundation of China (Nos. 11671135, 11871213, and 11901255), and the Natural Science Foundation of Shanghai (No. 19ZR1411800).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return