多郵差在有向網路中之運輸問題

Abstract

多郵差在有向網路中之運輸問題 (k-DCPP) 乃是中國郵差問題的推廣之 一. "總成本極小化" (minisum) 的問題是指每個郵差的服務成本總和要 求達到極小,這類問題已被證明為有限時間 內可解 (polynomial-time slovable) 並已有學者提出最佳解的演算法. 然而"最大成本極小化" (minimax) 的問題,是在每位郵差都必須服務的條件下,要求將成本最高之 郵差的服務成本極小化. 由於"最大成本極小化"的問題求解的複雜度很高 (NP-complete),因此不易求得最佳解. 於本論 中,我們先回顧多郵差在無 向網路中的"最大成本極小化"的問題之相關文獻,進而提出多郵差在有 向 網路中"最大成本極小化"之問題的近似最佳解演算法;並且提出一個求"下 界值" (lower bound) 的程序,以評估演算法求得之解的優劣.最後針對提 出的演算法做測試,結果顯示在無向網路中之 演算法當其應用在有向網路 中時,其優劣特性比較結果和在無向網路上之比較結果一致. The k-person Chinese postman problem on directed networks (k-DCPP), isan interesting generalization of the classical Chinese postman problem (CPP),which has many applications. The minisum k-DCPP is to find a set of k postman tours covering the service area with the total distance minimized, which can besolved optimally using polyminial-time bounded algorithms. The mimimax k-DCPP is to find a set of k postman tours covering the service area with the length ofthe longest postman tour minimized. The minimax k-DCPP is NP-complete. Therefore,it is difficult to slove the problem exactly. In this thesis,we introduce two algorithms to solve the k-DCPP approximately. In addition, a lower bound procedurefor the minimax k-DCPP is presented. The proposed algorithms are tested extensively.The computational results showed that the performance of the proposed algorithmsover the k-DCPP is similar to that over the k-CPP.