Approximate solutions for the maximum benefit Chinese postman problem

W.l. Pearn*, W. C. Chiu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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.

Original languageEnglish
Pages (from-to)815-822
Number of pages8
JournalInternational Journal of Systems Science
Volume36
Issue number13
DOIs
StatePublished - 20 Oct 2005

Keywords

  • Algorithms
  • Approximate solutions
  • Maximum Benefit Chinese Postman Problem

Fingerprint Dive into the research topics of 'Approximate solutions for the maximum benefit Chinese postman problem'. Together they form a unique fingerprint.

Cite this