On the Maximum Benefit Chinese Postman Problem

W. L. Pearn and K. H. Wang

Omega, 2003, vol. 31, issue 4, 269-273

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.

Keywords: Chinese; Postman; Problem; Rural; Postman; Problem; Upper; bound (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(03)00051-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:31:y:2003:i:4:p:269-273

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().