多郵差的中國郵差問題之演算法

Abstract

多個郵差的中國郵差問題(K-CPP) ，是典型中國郵差問題(CPP) 的一個推廣; 它被 應用在許多實際生活中的網路運輸問題上。多郵差的中國郵差問題可分為兩種型式 : 一是minisum 的多郵差中國郵差問題; 另一則是minimax 的多郵差中國郵差問題 。minisum 的多郵差中國郵差問題是要求出一組涵蓋整個服務地區的郵差路徑，且 這些路徑距離的總和最短; 而minimax 的多郵差中國郵差問題則是要求出一組涵蓋 整個服務地區的郵差路徑，並使這組路徑中最長的路徑距離最短。minisum 的多郵 差中國郵差問題可由polynominal-time bounded的演算法求得最佳解。但minimax 的多郵差中國郵差問題則已被證實其為一個複雜度相當高(NP-complete) 的問題。 在本篇論文中所討論的是minimax 的多郵差中國郵差問題。首先研究有閒本問題的 相關理論及存在的近似演算法，然後提出兩個新的演算法，以求得更精確的近似解 。最後，測試新的演算法並與目前已存在的演算法作比較，並對測試結果做分析。