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

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

中国邮递员问题(Chinese Postman Problem—CPP)是1960 年由中国数学家管梅谷先生首先提出的[1]。

经过60 年的发展， CPP 不仅成为一个经典的基础图论问题， 而且衍生了许多有重要实用和研究价值的路径问题[2] [3]。依据网络特征，基本的CPP 可分为有向CPP、无向CCP 和混合CPP。其中有向CPP 和无向CPP 所对应的网络分别为有向图和无向图。这两类问题已被证实可在多项式时间计算复杂度条件下求得最优解[3]。混合CPP 问题对应的网络中既包含有向弧段，也包括无向边。混合CPP 属于NP-complete问题[3]。近年来，基于经典CPP，衍生了许多重要的弧路径问题，并在现实中得到了广泛的应用。本文将针对有向CPP 给出一种可直接求解最终回路的整数规划模型， 并给出一种求解有向CPP 的具有多项式时间计算复杂度的算法，并对如何将该算法应用于混合CPP 加以说明。

下面对中国邮递员问题(CPP)的研究做一个简介。

文献[1]给出了求解CPP 问题的一种数值求解方法， 即奇偶图上作业法。文献[2]对中国邮递员问题的提出与研究历史做了回顾。文献[3]总结了中国邮递员问题50 年研究的历史。在对CPP 的拓展方面，文献[4]证明了多人中国邮递员问题属于NP 完全问题，且具有固定参数的可处理特征。文献[5]提出一般化最大收益下的多人中国邮递员问题，并给出了混合整数规划模型，并将理论应用于网络的安全巡视。文献[6]针对在给定时间窗内可同时服务部分街道的两侧的情景，构建了相关乡下邮递员问题的混合整数规划模型。文献[7]证明了在边着色图上定义的CPP 依然可以在多项式时间复杂度条件下求得问题最优解。文献[8]针对弧段费用依赖于弧段长度和车辆当前荷载的扩展中国邮递员问题，分析了问题求解的复杂度，建立了相应的优化模型。文献[9]针对最大化收益和最小化旅行时间的多目标中国邮递员问题给出了对应的期望值模型。

文献[10]分析了部分弧段具有遍历优先权的CPP。文献[11]给出了一类CPP 的拓展问题——混合图上最小最大圈覆盖问题的近似算法。从上述文献简介可以看出，目前针对CPP 研究主要是对经典CPP 的扩展，如考虑多人问题和多目标问题。而扩展后的CPP 问题多数转变为NP-hard 问题，但是更加切合相关的具体实践。

在对CPP 相关问题的求解方面，研究者分别从经典的整数规划算法、元启发式算法、生物学相关算