标题: 多郵差在有向網路中之運輸問題
The Minimax k-CPP on Directed Networks
作者: 洪志勳
Hong, Jr-Shiun
彭文理
Pearn Wen-Lea
工業工程與管理學系
关键字: 中國郵差問題;有向網路;多郵差問題;運輸問題;最大成本極小化;CPP;directed networks;k-CPP;Transportation problem;minimax
公开日期: 1995
摘要: 多郵差在有向網路中之運輸問題 (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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT840030013
http://hdl.handle.net/11536/60028
显示于类别:Thesis