風向郵差問題之演算法

Abstract

風向郵差問題(WPP),是由典型的中國郵差問題(CPP)所衍生而來一有趣的 郵差問題,它被應用在真實世界的許多問題上。但風向郵差問題已被証實 是一個複雜度相當高(NP-complete)的問題,因此很不容易精確地求得最佳 解。基於這個原因,Guan(1984)及Win(1989)先後各提出了一個求解方式, 以求得近似解。本論文,我們首先研究這些現有有關風向郵差問題之理論 及其求解過程,然後提出兩個新的演算法,以求得更接近最佳解的近似解。 最後以計算的結果來証實新的演算法在某些特定性質的網路上確實比現有 的求解方法更接近最佳解。 The Windy Postman Problem (WPP), is an interesting generalization of the classical Chinese Postman Problem (CPP), which has many real-world applications. The WPP 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 the existing solution procedures, then introduce two new algorithms to solve the WPP near-optimally. Computational results show that the new algorithms outperform the existing solution procedures on some special class of networks.