Journal Home >

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.

Abstract
Full text
Outline

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

Show Author's information Wei Yu1( )
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.
[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. 22nd 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. 23rd 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. 21st 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
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