混合型網路上的中國郵差問題之近似演算法

Abstract

混合型網路上的中國郵差問題(MCPP), 是中國郵差問題(CPP)的一個推 廣; 它被應用在真實世界的許多網路運輸問題上。此問題已被證實為一複 雜度相當高(NP-Complete)的問題, 因此很不容易精確地求得最佳解。基 於此原因, 學者們所提出的求解方式大多為近似演算法。在本論文中, 我 們首先研究這些相關的理論及存在的近似演算法, 然後提出二個新的演算 法, 以求得更精確的近似解。最後我們測試新的演算法並與目前已存在的 一些演算法作比較, 測試結果顯示新演算法確實比原有演算法更接近最佳 解。