中国邮递员问题50年

摘要/Abstract

摘要： 首先介绍一般邮递员问题, 涉及费用、服务侧、衔接费用、次序等要素. 然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展, 突出问题的线性规划描述及相应的组合多面体结构, 着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比.

关键词: 中国邮递员问题, 算法, 计算时间复杂度, 性能比

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

高敬振，高勃. 中国邮递员问题50年[J]. 运筹学学报, 2013, 17(1): 17-28.

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

参考文献

管梅谷. 奇偶点图上作业法[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]	李鑫荣, 修乃华, 罗自炎. 低秩矩阵优化若干新进展[J]. 运筹学学报, 2020, 24(2): 23-41.
[2]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[3]	杨瑞琪, 徐大川, 杜东雷, 张冬梅. 次模函数最大化的流算法综述[J]. 运筹学学报, 2020, 24(2): 73-86.
[4]	简金宝, 杨林峰, 张晨. 电力系统机组组合问题的模型与优化方法[J]. 运筹学学报, 2020, 24(2): 87-102.
[5]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[6]	丁志伟, 刘艳云, 孔京, 张洪, 张一, 戴彧虹, 杨周旺. 感染人数期望值估计及新增确诊人数趋势预测的概率模型[J]. 运筹学学报, 2020, 24(1): 1-12.
[7]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[8]	耿晓路, 童小娇. 分布鲁棒机会约束优化问题的研究[J]. 运筹学学报, 2020, 24(1): 115-130.
[9]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[10]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[11]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[12]	黄培煌, 朱文兴. 移动传感器网络中的最大价值路径扫描覆盖算法[J]. 运筹学学报, 2019, 23(4): 155-164.
[13]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[14]	李建荣. 中国高考招生匹配市场中的算法设计及公平激励机制[J]. 运筹学学报, 2019, 23(2): 75-85.
[15]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.