Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/36371
標題: On the Maximum Benefit Chinese Postman Problem
作者: Pearn, W.L.
王國雄
Wang, K.H.
關鍵字: Chinese Postman Problem;Rural Postman Problem;upper bound
Project: Omega-International Journal of Management Science
期刊/報告no:: Omega-International Journal of Management Science, Volume 31, Issue 4, Page(s) 269-273.
摘要: 
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. (C) 2003 Elsevier Science Ltd. All rights reserved.
URI: http://hdl.handle.net/11455/36371
ISSN: 0305-0483
DOI: 10.1016/s0305-0483(03)00051-3
Appears in Collections:應用數學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.