混向郵差問題解之改進

Abstract

中國郵差問題是在給定的街道圖中尋找一個最短的郵差工作路徑，該 路徑必須包含所有的街道。中國郵差問題在完全有方向或完全沒有方向的 網路上，可以用很快的速度(polynomial-time)求得最佳解，但是在混向 的網路上已經被證實是複雜度相當高(NP-complete)的問題。許多求近似 解的演算法已經被提出，包括Mixed-1, Mixed-2, 改良的Mixed-1, 和改 良的Mixed-2。在本論文中，我們先簡要的回顧這四種演算法，然後提出 四種新的方法來改善求解。針對這些方法，我們用許多組例子來檢測並和 Mixed-1, Mixed-2, 改良的Mixed-1, 以及改良的Mixed-2作比較，測試結 果顯新提出的方法顯著地改善目前現有的解法。 The Chinese postman problem (CPP) is that of finding a shortest postman tour covering all the edges in the road network. The CPP is polynomial-time solvable on directed or undirected networks, but the CPP on mixed networks (MCPP) has been shown to be NP-complete. Several heuristic solution procedures including Mixed-1, Mixed-2, Modified Mixed-1, and Modified Mixed-2 algorithms, have been proposed to solve the problem approximately. In this paper, we briefly review these four existing algorithms, thepropose four improvement procedures to improve the solutions. The proposed procedures are tested and compared with Mixed-1, Mixed-2, Modified Mixed-1, and Modified Mixed-2. The results showed that the proposed procedures significantly improved the existing solutions.