Approximate solutions for the Maximum Benefit Chinese Postman Problem
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
822 | en_US |
dc.citation.issue |
13 | en_US |
dc.citation.spage |
815 | en_US |
dc.citation.volume |
36 | en_US |
dc.citation.woscount |
6 | |
dc.contributor.author |
Pearn, WL | en_US |
dc.contributor.author |
Chiu, WC | en_US |
dc.contributor.department |
工業工程與管理學系 | zh_TW |
dc.contributor.department |
Department of Industrial Engineering and Management | en_US |
dc.date.accessioned |
2014-12-08T15:18:12Z | |
dc.date.available |
2014-12-08T15:18:12Z | |
dc.date.issued |
2005-10-20 | en_US |
dc.description.abstract |
The Maximum Benefit Chinese Postman Problem (MBCPP) is an interesting and practical generalization of the classical Chinese Postman Problem, which has many real-world applications. Each arc on the MBCPP network is associated with a service cost for the traversal with service, a deadhead cost for the traversal with no service, and a set of benefits. Each time an arc is traversed, a benefit is generated. The objective of the MBCPP is to find a postman tour traversing a selected set of arcs with the total net benefit maximized. Such a generalization reflects real-world situations more closely. The MBCPP has been shown to be more complicated than the Rural Postman Problem, which is an NP-hard problem. Therefore, it is difficult to find polynomial-time bounded algorithms to solve the problem exactly. In this paper, we first review an existing exact solution procedure, and introduce several heuristic algorithms including the Branch-Scan algorithm, the Connection algorithm with various connection strategies, and the Directed Tree algorithm, to solve the MBCPP approximately. We also apply one-opt, two-opt, component exchange, and component-drop procedures to improve the solutions. The proposed algorithms are tested and compared. Extensive computational results are provided and analysed. | en_US |
dc.identifier.doi |
10.1080/00207720500282292 | en_US |
dc.identifier.issn |
0020-7721 | en_US |
dc.identifier.journal |
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1080/00207720500282292 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/13160 | |
dc.identifier.wosnumber |
WOS:000233776700004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
approximate solutions | en_US |
dc.subject |
Maximum Benefit Chinese Postman Problem | en_US |
dc.subject |
algorithms | en_US |
dc.title |
Approximate solutions for the Maximum Benefit Chinese Postman Problem | en_US |
dc.type |
Article | en_US |
檔案
- 000233776700004.pdf (166.8 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Pearn, W., & Chiu, W. (2005). Approximate solutions for the Maximum Benefit Chinese Postman Problem. INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 36(13), 815–822. https://doi.org/10.1080/00207720500282292
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/13160