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 |
|
|