碩士 / 國立交通大學 / 工業工程研究所 / 84 / 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.
| Identifer | oai:union.ndltd.org:TW/084NCTU0030013 |
| Date | January 1996 |
| Creators | Hong, Jr-Shiun, 洪志勳 |
| Contributors | Pearn Wen-Lea, 彭文理 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | zh-TW |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 29 |
Page generated in 0.0117 seconds