鄉村型郵差問題之演算法則

Abstract

鄉村型郵差問題比中國郵差問題更具一般性及實用性, 是要在最低 成本的考量下, 走過網路中所給定必需要走的路徑; 它被應用在真實世 界的許多網路運輸問題上; 這類問題的網路型式若不連通, 則會有很高 的複雜度, 因此不容易求得最佳解; 基於這項理由, 我們提出近似演算 法則來解這一類的網路問題. 鄉村型郵差問題之所以比中國郵差問題更具一般性及實用性, 是因 為此類型的網路運輸問題可以只針對網路中的部份路徑進行運輸, 不像 中國郵差問題須考量到網路中的所有路徑, 因此鄉村型郵差問題較能反 應實際生活中的運輸問題. 由於鄉村型郵差問題的適用性較廣, 相對的 , 處理的步驟及方法往往較為複雜, 經常不容易做成最佳的處理; 因此 如何尋求一個可以令人接受而又有效的處理方法, 便成為本論文努力的 目標. 在本論文中, 我們首先研究相關的理論並探討其求解過程, 然後提 出兩個新的演算法則, 以求得更精確的近似解; 針對新的演算法做測試 , 結果顯示新的演算法有較好的執行成效. The rural postman problem is a practical extension of the well-known Chinese postman problem, in which a subset of the (strees) from the road network are required to be traversed at minimal cost. The rural postman problem is NP-complete if this subset does not form a weakly connected graph. Therfore. it is unlikely that polynomial-time bounded algorithms exist for the problem. In this paper, we review the existing heuristic solution procedures, then present two new algorithms to solve the problem near-optimally. Computational results showed that the new algorithms significantly outperformed the existing solution procedures.