Open Access
Issue
Published:
*19 May 2023*

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

300

Views

50

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

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

menu

Abstract

Full text

Outline

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

[1]

B. L. Golden and R. T. Wong, Capacitated arc routing problems, *Networks*, vol. 11, no. 3, pp. 305–315, 1981.

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

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

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

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

[6]

E. Fernández and J. Rodríguez-Pereira, Multi-depot rural postman problems, *TOP*, vol. 25, no. 2, pp. 340–372, 2017.

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

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

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

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

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

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

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

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

[15]

N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, *Operations Research Forum*, vol. 3, p. 20, 2022.

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

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

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

[20]

J. Blauth, V. Traub, and J. Vygen, Improving the approximation ratio for capacitated vehicle routing, in *Proc. 22*^{nd} Conf. Integer Programming and Combinatorial Optimization, Atlanta, GA, USA, 2021, pp. 1–14.

[21]

Z. Friggstad, R. Mousavi, M. Rahgoshay, and M. R. Salavatipour, Improved approximations for capacitated vehicle routing with unsplittable client demands, in *Proc. 23*^{rd} Conf. Integer Programming and Combinatorial Optimization, Eindhoven, The Netherlands, 2022, pp. 251–261.

[22]

M. Labbé, G. Laporte, and H. Mercure, Capacitated vehicle routing on trees, *Oper. Res.*, vol. 39, no. 4, pp. 616–622, 1991.

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

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

[25]

K. Jansen, Bounds for the general capacitated routing problem, *Networks*, vol. 23, no. 3, pp. 165–173, 1993.

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

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

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

[29]

B. Bhattacharya and Y. Hu, Approximation algorithms for the multi-vehicle scheduling problem, in *Proc. 21*^{st} Int. Symp. Algorithms and Computation, Jeju Island, Republic of Korea, 2010, pp. 192–205.

[30]

A. Corberán and G. Laporte, *Arc Routing: Problems, Methods, and Applications*. Philadelphia, PA, USA: SIAM, 2015.

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

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

Publication history

Copyright

Acknowledgements

Rights and permissions

Received: 23 June 2022

Revised: 03 October 2022

Accepted: 10 November 2022

Published:
19 May 2023

Issue date: October 2023

© The author(s) 2023.

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).

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/).