﻿ 求解中国邮递员问题的圈生成算法 Cycle Generating Algorithm for Solving Chinese Postman Problem

Modeling and Simulation
Vol. 11  No. 01 ( 2022 ), Article ID: 48274 , 12 pages
10.12677/MOS.2022.111018

Cycle Generating Algorithm for Solving Chinese Postman Problem

Yunting Cui, Shengxue He*

Business School, University of Shanghai for Science and Technology, Shanghai

Received: Dec. 15th, 2021; accepted: Jan. 19th, 2022; published: Jan. 26th, 2022

ABSTRACT

Chinese Postman Problem (CPP) is an important basic problem in the field of operations research and computer application, and has a wide range of practical applications. For the CPP on directed graph, a new nonlinear integer-programming model that can solve the final loop directly is presented, and an accurate algorithm with polynomial time computation complexity is proposed. Firstly, by calculating the shortest paths between all arcs, a cost matrix with path non-service time as non-diagonal element is obtained. Then, all arcs are regarded as the agents and at the same time tasks of a special assignment problem, and an assignment problem is obtained based on the cost matrix obtained above. Then, by solving the assignment problem above, circles covering all arcs of the network are obtained. Finally, by searching the common nodes between circles, all circles are combined into a large circle, so as to obtain the final service route of the postman. The convergence and the computational complexity of polynomial time of the algorithm are proved by theoretical and numerical analysis. Finally, how to solve the CPP on a mixed graph is discussed, and the corresponding solution process is given.

Keywords:Chinese Postman Problem, Assignment Problem, Graph Theory, Polynomial Time, Arc Routing Problem

1. 引言

2. 模型

2.1. 主要参变量

$G\left(V,A\right)$ 表示一个连通的有向图，包含节点集合V和有向弧段集合A。

$A$ 表示所有需要服务的街道，即有向弧段，构成的集合，其集合势 $|A|=n$

${a}_{1},{a}_{2},{a}_{3}\in A$ 表示邮递员需要服务的三条典型街道，即A内的三条典型有向弧段。

$i,j\in V$ 表示网络中联接街道的两个交叉口，即网络中的两个代表节点。

${{t}^{\prime }}_{a}$ 表示邮递员途经弧段a并服务a所需要的时间，即弧段a的服务时间。

${t}_{a}$ 表示邮递员途经街道a但无需收集和派送邮件所需要的时间，即弧段a的非服务时间。

${x}_{a}$ 表示邮递员选择的最终回路经过街道a的次数。

${A}_{i}^{+}$ 表示进入节点i的所有街道构成的集合。

${A}_{i}^{-}$ 表示从节点i离开的所有街道构成的集合。

${t}_{a,b}$ 表示从弧段a的头节点到弧段b的尾节点的最短路径的非服务行程时间。

${x}_{a,b}\in \left\{0,1\right\}$ 指示邮递员是否相继服务弧段a和弧段b。

${y}_{a,b}\in \left\{0,1\right\}$ 表示以 $a\in A$ 为代理，以 $b\in A$ 为任务时，两者间是否存在指派关系。

$s\left(a\right)\in \left\{1,2,3,\cdots ,n\right\}$$\forall a\in A$ 表示在邮递员所走回路中弧段a作为被服务弧段时的序号。

${t}_{s\left(a\right),s\left(b\right)}$ 表示如果在最终回路中邮递员相继服务弧段a和b，其值为 ${t}_{a,b}$ ；否则，其值为0。

$Q$ 表示由特定指派问题的解对应的由服务街道形成的圈的集合，其势 $|Q|=m$

${Q}_{p},{Q}_{q}\in Q$ 表示圈集合Q内的两个典型的圈。

2.2. CPP模型

$\mathrm{min}{\sum }_{a}{t}_{a}\left({x}_{a}-1\right)$ (1)

$\underset{a\in {A}_{i}^{+}}{\sum }{x}_{a}=\underset{a\in {A}_{i}^{-}}{\sum }{x}_{a},\forall i\in V$ (2)

${x}_{a}\in {ℤ}^{+},a\in A$ (3)

$\mathrm{min}\underset{a\in A}{\sum }\underset{b\in A}{\sum }\text{ }{t}_{a,b}{x}_{a,b}$ (4)

$s\left({a}_{1}\right)\ne s\left({a}_{2}\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall {a}_{1}\in A,\text{\hspace{0.17em}}\text{\hspace{0.17em}}{a}_{2}\in A,\text{\hspace{0.17em}}\text{\hspace{0.17em}}{a}_{1}\ne {a}_{2}$ (5)

${x}_{a,b}=\left\{\begin{array}{ll}1,\hfill & \text{if}s\left(a\right)+1=s\left(b\right)\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}s\left(a\right)=n,\text{\hspace{0.17em}}s\left(b\right)=1\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$ (6)

$s\left(a\right)\in \left\{1,2,3,\cdots ,n\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall a\in A$ (7)

3. 求解算法

3.1. 圈生成算法的基本思路

3.2. 算法的求解步骤

Figure 1. The flow chart of cycle generating algorithm

$\mathrm{min}\underset{a\in A}{\sum }\underset{b\in A}{\sum }\text{\hspace{0.17em}}{c}_{a,b}{y}_{a,b}$ (8)

$\underset{a\in A}{\sum }\text{\hspace{0.17em}}{y}_{a,b}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall b\in A$ (9)

$\underset{b\in A}{\sum }\text{\hspace{0.17em}}{y}_{a,b}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall a\in A$ (10)

${y}_{a,b}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall a\in A,\text{\hspace{0.17em}}\text{\hspace{0.17em}}b\in A$ (11)

Figure 2. The bipartite graph of assignment problem

Figure 3. The sketch of combining two cycles

3.3. 算法的性质定理

4. 算例分析

Figure 4. Network with 6 nodes

Figure 5. The matrix of shortest non-service times between links

Figure 6. Network with 23 nodes

Table 1. The travel time of links in Figure 6

5. 混合CPP的网络变幻求解

6. 结论

Cycle Generating Algorithm for Solving Chinese Postman Problem[J]. 建模与仿真, 2022, 11(01): 202-213. https://doi.org/10.12677/MOS.2022.111018

1. 1. 管梅谷. 奇偶点图上作业法[J]. 数学学报, 1960, 10(3): 263-266.

2. 2. 管梅谷. 关于中国邮递员问题研究和发展的历史回顾[J]. 运筹学学报, 2015, 19(3): 1-7.

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

4. 4. Gutin, G., Muciaccia, G. and Yeo, A. (2013) Parameterized Complexity of k-Chinese Postman Problem. Theoretical Computer Science, 513, 124-128. https://doi.org/10.1016/j.tcs.2013.10.012

5. 5. Ali, S. and Ali, H. (2015) Generalized Maximum Benefit Multiple Chinese Postman Problem. Transportation Research Part C, 55, 261-272. https://doi.org/10.1016/j.trc.2015.01.017

6. 6. Nossack, J., Golden, B., Pesch, E. and Zhang, R. (2017) The Windy Rural Postman Problem with a Time-Dependent Zigzag Option. European Journal of Operational Research, 258, 1131-1142. https://doi.org/10.1016/j.ejor.2016.09.010

7. 7. Gutin, G., Jones, M., Sheng, B., Wahlström, M. and Yeo, A. (2017) Chinese Postman Problem on Edge-Colored Multigraphs. Discrete Applied Mathematics, 217, 196-202. https://doi.org/10.1016/j.dam.2016.08.005

8. 8. Corberán, Á., Erdoğan, G., Laporte, G., Plana, I. and Sanchis, J.M. (2018) The Chinese Postman Problem with Load-Dependent Costs. Transportation Science, 52, 370-385. https://doi.org/10.1287/trsc.2017.0774

9. 9. Majumder, S., Kar, S. and Pal, T. (2019) Uncertain Multi-Objective Chinese Postman Problem. Soft Computing, 23, 11557-11572. https://doi.org/10.1007/s00500-018-03697-3

10. 10. Nilofer, M. (2020) Rizwanullah. An Implementation of Chinese Postman Problem with Priorities. Journal of Intelligent & Fuzzy Systems, 38, 3301-3305. https://doi.org/10.3233/JIFS-190035

11. 11. 包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.

12. 12. 费蓉, 崔杜武. 中国邮递员问题的动态规划算法研究[J]. 计算机研究与发展, 2005, 42(2): 294-299.

13. 13. 冯俊文. 中国邮递员问题的整数规划模型[J]. 系统管理学报, 2010, 19(6): 684-688.

14. 14. Corberán, Á., Plana, I., Rodríguez-Chía, A.M. and Sanchis, J.M. (2013) A Branch-and-Cut Algorithm for the Maximum Benefit Chinese Postman Problem. Mathematical Programming, 141, 21-48. https://doi.org/10.1007/s10107-011-0507-6

15. 15. Sun, J., Meng, Y. and Tan, G. (2015) An Integer Programming Approach for the Chinese Postman Problem with Time-Dependent Travel Time. Journal of Combinatorial Optimization, 29, 565-588. https://doi.org/10.1007/s10878-014-9755-8

16. 16. 马宇红, 田贵龙, 李宪. 基于动态拓扑网络的混合中国邮递员问题[J]. 西北师范大学学报(自然科学版), 2015, 51(1): 17-23.

17. 17. Ma, Y., Tian, G. and Li, X. (2015) Genetic Algorithm for the Capacitated Chinese Postman Problem on Mixed Networks. Applied Mechanics and Materials, 701-702, 44-49. https://doi.org/10.4028/www.scientific.net/AMM.701-702.44

18. 18. Keskin, M.E. and Yılmaz, M. (2019) Chinese and Windy Postman Problem with Variable Service Costs. Soft Computing, 23, 7359-7373. https://doi.org/10.1007/s00500-018-3382-8

19. 19. Çodur, M.K. and Yılmaz, M. (2020) A Time-Dependent Hierarchical Chinese Postman Problem. Central European Journal of Operations Research, 28, 337-366. https://doi.org/10.1007/s10100-018-0598-8

20. 20. Siloi, I., Carnevali, V., Pokharel, B., Fornari, M. and Di Felice, R. (2021) Investigating the Chinese postman problem on a quantum annealer. Quantum Machine Intelligence, 3, Article No. 3. https://doi.org/10.1007/s42484-020-00031-9

21. 21. 韩爱丽, 朱大铭. 基于一种新的边权编码方案的中国邮递员问题的DNA计算模型[J]. 计算机研究与发展, 2007 , 44(6): 1053-1062.

22. 22. 李玮, 王雷. 中国邮递员问题的DNA计算[J]. 计算机应用, 2009, 29(7): 1880-1883.

23. 23. Kundeti, V., Rajasekaran, S. and Dinh, H. (2012) An Effi-cient Algorithm For Chinese Postman Walk On Bi-Directed De Bruijn Graphs. Discrete Mathematics, Algorithms and Applications, 4, Article ID: 1250019, 16 p. https://doi.org/10.1142/S179383091250019X

24. 24. Wang, Z., Bao, X. and Wu, T. (2021) A Parallel Bioinspired Algorithm for Chinese Postman Problem Based on Molecular Computing. Computational Intelligence and Neuroscience, 2021, Article ID: 8814947, 13 p. https://doi.org/10.1155/2021/8814947

25. 25. Granot, D., Granot, F. and Ravichandran, H. (2014) The k-Centrum Chinese Postman Delivery Problem and a Related Cost Allocation Game. Discrete Applied Mathematics, 179, 100-108. https://doi.org/10.1016/j.dam.2014.07.021

26. 26. Platz, T.T. and Hamers, H. (2015) On Games Arising from Multi-Depot Chinese Postman Problems. Annals of Operations Research, 235, 675-692. https://doi.org/10.1007/s10479-015-1977-3

27. NOTES

*通讯作者。