Algorithms for the Chinese postman problem on mixed networks
Algorithms for the Chinese postman problem on mixed networks
复制标题
混合网络上中国邮递员问题的算法
DOI：
10.1016/0305-0548(94)00036-8
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
C. M. Liu
中科院分区：
文献类型：
--
作者：
W. Pearn;C. M. Liu
混合网络上的中国邮递员问题（MCPP）是经典中国邮递员问题（CPP）的一个推广，具有广泛的实际应用。MCPP已被证明是NP完全的。因此，很难准确地解决这个问题。为此，启发式求解程序已被提出来近似地解决这个问题。在本文中，我们首先回顾了Edmonds和约翰逊[Math.Prog.5，88-124（1973）]和Frederickson [J. Assoc. Comput. Mach.26，538-554（1979）]，然后引入两个新的算法来近似最优地求解MCPP。所提出的新算法进行了测试，并与现有的解决方案的程序进行比较。计算结果表明，这两个新算法显着优于现有的解决方案的程序。
The Chinese postman problem on mixed networks (MCPP), is a practical generalization of the classical Chinese postman problem (CPP), which has many real-world applications. The MCPP has been shown to be NP-complete. Therefore, it is difficult to solve the problem exactly. For this reason, heuristic solution procedures have been proposed to solve the problem approximately. In this paper, we first review two existing solution procedures proposed by Edmonds and Johnson [Math. Progr.5, 88–124 (1973)], and Frederickson [J. Assoc. Comput. Mach.26, 538–554 (1979)], then introduce two new algorithms to solve the MCPP near optimally. The proposed new algorithms are tested and compared with the existing solution procedures. Computational results showed that the two new algorithms significantly outperformed the existing solution procedures.