中国邮递员问题50年

Abstract

Abstract: We introduce the general postman problem firstly, involving issues such as serving and traversing cost, sides of serving, turn cost and serving hierarchy and so on. We then survey briefly the research on the Chinese postman problem, the Chinese postman problem on directed graphs, postman problems on mixed graphs, on graphs with wind and on rural districts, focusing on their linear programming formulations and the structures of the corresponding polyhedra, addressing the models of problems, exact algorithms and their time complexities, and the approximation approaches and their performance.

Key words: Chinese postman problem, heuristic, computational complexity, performance ratio

GAO Jingzhen, GAO Bo. Chinese postman problem over 50 years[J]. Operations Research Transactions, 2013, 17(1): 17-28.

References

管梅谷. 奇偶点图上作业法[J]. 数学学报, 1960, 10(3): 263-266.
Kwan Mei-Ko. Graphic programming using odd or even points [J]. Chinese Mathematics, 1962,   1: 273- 277.
Edmonds J. The Chinese postman problem [J]. Operations Research, 1965,    13 Suppl. 1: B73.
管梅谷. 中国投递员问题综述[J]. 数学研究与评论， 1984, 4(1): 113-119.
Irnich S. Solution of real-world postman problems [J]. European Journal of Operational Research, 2008, 190(1): 52-67.
Irnich S. Undirected postman problems with zigzagging option: A cutting-plane approach [J]. Computers & Operations Research, 2008, 35(12): 3998-4009.
Edmonds J, Johnson E L. Matching， Euler tour and the Chinese postman [J]. Mathematical Programming, 1973, 5: 88-124.
Cabral E A, Gendreau M, Ghiani G, Laporte G. Solving the hierarchical Chinese postman problem as a rural postman problem [J]. European Journal of Operational Research, 2004, 155(1): 44-50.
Ghiani G, Improta G. An algorithm for the hierarchical Chinese postman problem [J]. Operations Research Letters, 2000, 26(1): 27-32.
Korteweg P, Volgenant T. On the hierarchical Chinese postman problem with linear ordered classes [J]. European Journal of Operational Research, 2006, 169(1): 41-52.
Raspaud A. Postman tours and cycle covers [J]. Discrete Mathematics, 1993, 111(1-3): 447-454.
Lin Y X, Zhao Y C. A new algorithm for the directed Chinese postman problem [J]. Computers & Operations Research, 1988, 15(6): 577-584.
Guan M G. On the windy postman problem [J]. Discrete Applied Mathematics, 1984, 9(1): 41-46.
Win Z. On the windy postman problem on Eulerian graphs [J]. Mathematical Programming, 1989, 44: 97-112.
Pearn W L， Li M L. Algorithms for the windy postman problem [J]. Computers & Operations Research, 1994, 21(6): 641-651.
Grotschel M, Win Z. A cutting plane algorithm for the windy postman problem [J]. Mathematical Programming, 1992, 55: 339-358.
Zaragoza Martinez F J. Series-parallel graphs are windy postman perfect [J]. Discrete Mathematics, 2008, 308(8): 1366-1374.
Corberan A, Marti R, Sanchis J M. A GRASP heuristic for the mixed Chinese postman problem [J].   European Journal of Operational Research, 2002, 142(1): 70-80.
Ralphs T K. On the mixed Chinese postman problem [J]. Operations Research Letters, 1993, 14(3): 123-127.
Frederickson G N. Approximation algorithms for some postman problems [J]. Journal of ACM, 1979, 26: 538-554.
Pearn W L, Liu C M. Algorithms for the Chinese postman problem on mixed networks [J].   Computers & Operations Research,   1995,   22(5): 479-489.
Pearn W L, Chou J B. Improved solutions for the Chinese postman problem on mixed networks [J]. Computers & Operations Research, 1999,   26(8): 819-827.
Holmberg K. Heuristics for the rural postman problem [J]. Computers & Operations Research, 2010, 37(5): 981-990.
Corberan A, Sanchis J M. A polyhedral approach to the rural postman problem [J]. European Journal of Operational Research, 1994, 79(1): 95-114.
Pearn W L, Wu T C. Algorithms for the rural postman problem [J]. Computers & Operations Research, 1995, 22(8): 819-828.
Christofides N, Campos V, Corberan A, Mota E. An algorithm for the rural postman problem [R]. Imperil College Report, 1981,   81(5).
Ghiani G, Lagana D, Musmanno R. A constructive heuristic for the undirected rural postman problem [J]. Computers & Operations Research, 2006, 33(12): 3450-3457.

[1]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[2]	LIU Yafeng. Two optimization problems in wireless communication system design and related optimization methods [J]. Operations Research Transactions, 2019, 23(3): 47-62.
[3]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[4]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[5]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.
[6]	FU Tianwen, TU Zhuozhuo, WEI Boyang. Portfolio selection models with new negative exponential expected utilities [J]. Operations Research Transactions, 2016, 20(1): 1-18.
[7]	GUAN Meigu. A historical review on the research and development [J]. Operations Research Transactions, 2015, 19(3): 1-7.
[8]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.
[9]	REN Qingjuan, XU Baoguang. k-partitioning problem with items' type restriction [J]. Operations Research Transactions, 2012, 16(3): 93-99.
[10]	XU Jian-Teng, ZHANG Yu-Zhong, BAI Qing-Guo. A Polynomial Time Algorithm for the Economic Lot-size Problem with Multiple Suppliers and Multiple Retailers [J]. Operations Research Transactions, 2011, 15(4): 102-114.

Chinese postman problem over 50 years

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments