On the maximum benefit Chinese Postman Problem

W.l. Pearn*, K. H. Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

The Maximum Benefit Chinese Postman Problem (MBCPP) is a practical generalization of the classical Chinese Postman Problem (CPP), which has many real-world applications. In this paper, we consider the MBCPP on undirected networks, and show that the MBCPP is more complex than the Rural Postman Problem (RPP). We present a sufficient condition for the MBCPP solution to cover the whole network, and provide an upper bound. Based on the upper bound, we propose an efficient solution procedure to solve the MBCPP approximately. The proposed algorithm applies the minimal spanning tree and the minimal-cost matching algorithms, which performs well on problems satisfying the sufficient condition.

Original languageEnglish
Pages (from-to)269-273
Number of pages5
JournalOmega
Volume31
Issue number4
DOIs
StatePublished - 1 Aug 2003

Keywords

  • Chinese Postman Problem
  • Rural Postman Problem
  • Upper bound

Fingerprint Dive into the research topics of 'On the maximum benefit Chinese Postman Problem'. Together they form a unique fingerprint.

Cite this