The maximum benefit Chinese postman problem (MBCPP) is a practical generalization of the Chinese postman problem. A distinctive feature of MBCPP is that the postman can traverse each edge arbitrary times and obtains a benefit for each traversal of an edge, which depends on the number of times that the edge has been traversed. (Pearn and Wang, Omega 31 (2003) 269–273) discussed MBCPP under the assumption that the benefits of each edge is a non-increasing function of the number of traversals. They showed that MBCPP under this assumption is NP-hard, and proposed a heuristic algorithm which applies the minimum spanning tree and the minimal-cost T-join algorithms. (Corberán, Plana, Rodríguez-Chía and Sanchis, Math. Program. 141 (2013) 21–48) presented an integer programming formulation and a branch-and-cut algorithm for MBCPP without the assumption on the benefits. This is based on the idea of integrating the benefits of each edge into two benefits, each representing that the edge is traversed an odd or even number of times. In this paper, by applying the idea of Corberán et al., we improve the heuristic algorithm of Pearn and Wang. Our algorithm applies to the general case with no assumption on the benefits, and can perform better even if the benefits are non-increasing. We then analyze the efficiency of our heuristic algorithm in theory and in practice, and prove that it finds the optimal solution when the benefits satisfy a certain property.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022044
Keywords: Combinatorial optimization, maximum benefit Chinese postman problem, heuristic algorithm, spanning tree, $$-join
@article{RO_2022__56_3_1283_0,
author = {Matsuura, Shiori and Takazawa, Kenjiro},
title = {An improved heuristic algorithm for the maximum benefit {Chinese} postman problem},
journal = {RAIRO. Operations Research},
pages = {1283--1291},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {3},
doi = {10.1051/ro/2022044},
mrnumber = {4431922},
zbl = {1493.90239},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022044/}
}
TY - JOUR AU - Matsuura, Shiori AU - Takazawa, Kenjiro TI - An improved heuristic algorithm for the maximum benefit Chinese postman problem JO - RAIRO. Operations Research PY - 2022 SP - 1283 EP - 1291 VL - 56 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022044/ DO - 10.1051/ro/2022044 LA - en ID - RO_2022__56_3_1283_0 ER -
%0 Journal Article %A Matsuura, Shiori %A Takazawa, Kenjiro %T An improved heuristic algorithm for the maximum benefit Chinese postman problem %J RAIRO. Operations Research %D 2022 %P 1283-1291 %V 56 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022044/ %R 10.1051/ro/2022044 %G en %F RO_2022__56_3_1283_0
Matsuura, Shiori; Takazawa, Kenjiro. An improved heuristic algorithm for the maximum benefit Chinese postman problem. RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1283-1291. doi: 10.1051/ro/2022044
[1] , and , Privatized rural postman problems. Comput. Oper. Res. 33 (2006) 3432–3449. | Zbl | DOI
[2] , and , Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196 (2009) 886–896. | MR | Zbl | DOI
[3] , Worst-case analysis of a new heuristic for the travelling salesman problem, Management Sciences Research Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1976). | MR | Zbl
[4] , , and , A branch-and-cut algorithm for the maximum benefit Chinese postman problem. Math. Program. 141 (2013) 21–48. | MR | Zbl | DOI
[5] , Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. Sect. B 69 (1965) 125–130. | MR | Zbl | DOI
[6] , The Chinese postman’s problem. Bull. Oper. Res. Soc. Am. 13 (1965) 73.
[7] and , Matching, Euler tours and the Chinese postman. Math. Program. 5 (1973) 88–124. | MR | Zbl | DOI
[8] , Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. thesis, Department of Computer Science, Stanford University, Stanford, California (1973).
[9] , Graphic programming using odd or even points. Acta Math. Sin. 10 (1960) 263–266. | MR | Zbl
[10] and , Combinatorial Optimization-Theory and Algorithms, 6th ed., Springer, Heidelberg (2018). | Zbl | MR
[11] , Combinatorial Optimization: Networks and Matroids, edited by Holt, Rinehart and Winston. New York (1976). | MR | Zbl
[12] and , On general routing problems. Networks 6 (1976) 593–597. | MR | Zbl | DOI
[13] and , The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem. Eur. J. Oper. Res. 65 (1993) 218–234. | Zbl | DOI
[14] and , On the maximum benefit Chinese postman problem. Omega 31 (2003) 269–273. | DOI
[15] and , Approximate solutions for the maximum benefit Chinese postman problem. Int. J. Syst. Sci. 36 (2005) 815–822. | MR | Zbl | DOI
[16] , Combinatorial Optimization-Polyhedra and Efficiency. Springer, Heidelberg (2003). | MR | Zbl
[17] , Algorithms in C, Part 5: Graph Algorithms, 3rd ed., Addison-Wesley, (2002). | Zbl | MR
[18] and , Generalized maximum benefit multiple Chinese postman problem. Transp. Res. Part C Emerg. Technol. 55 (2015) 261–272. | DOI
Cité par Sources :
