標題: 風向郵差問題之演算法Algorithms for the Windy Postman Problem 作者: 黎茂琳Mao Lin Li彭文理Dr. Wen Lea Pearn工業工程與管理學系 關鍵字: 風向郵差問題;中國郵差問題;混合型中國郵差問題;線性時間配對演算法;最小成本流量演算法;尤拉圖;Windy Postman Problem;Chinese Postman Problem;Mixed Chinese Postman Problem 公開日期: 1992 摘要: 風向郵差問題(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. URI: http://140.113.39.130/cdrfb3/record/nctu/#NT810030001http://hdl.handle.net/11536/56580 顯示於類別： 畢業論文