求解中国邮递员问题的圈生成算法

Cycle Generating Algorithm for Solving Chinese Postman Problem

摘要: 中国邮递员问题是运筹学与计算机应用邻域的一个重要的基础问题，有着广泛的现实应用。针对有向图上的中国邮递员问题，给出了一种全新的可以直接求解最终回路的非线性整数规划模型，同时提出了一种具有多项式时间计算复杂度的精确求解算法。首先，通过计算所有弧段间的最短路径，得到一个以路径非服务时间为非对角线元素的费用矩阵；接着，将所有弧段构成的集合同时视为一个特殊指派问题的代理与任务集合，并基于前面获得的费用矩阵得到一个指派问题；然后，通过求解上述指派问题，得到遍历网络所有弧段的圈集合；最后，通过搜索圈与圈之间的共用节点，将所有圈合并为一个大圈，从而得到邮递员的最终服务路线。通过理论证明和算例分析，证实了算法的收敛性和多项式时间的计算复杂性。最后对如何处理混合图上的中国邮递员问题进行了讨论，给出了具体求解思路。

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.