首页 | 本学科首页   官方微博 | 高级检索  
     


Approximate solutions for the maximum benefit chinese postman problem
Authors:W L Pearn  W C Chiu
Affiliation:1. Department of Industrial Engineering &2. Management , National Chiao Tung University , 1001 Tahsueh Rd, Hsinchu, ROC, Taiwan roller@cc.nctu.edu.tw;4. Institute of Industrial Engineering, National Tsing Hua University , 101, Section 2, Kuang Fu Road, Hsinchu, ROC, Taiwan
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.
Keywords:Approximate solutions  Maximum Benefit Chinese Postman Problem  Algorithms
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号