Title: ALGORITHMS FOR THE CHINESE POSTMAN PROBLEM ON MIXED NETWORKS
Authors: PEARN, WL
LIU, CM
工業工程與管理學系
Department of Industrial Engineering and Management
Issue Date: 1-May-1995
Abstract: The Chinese postman problem on mixed networks (MCPP), is a practical generalization of the classical Chinese postman problem (CPP), which has many real-world applications. The MCPP has been shown to be NP-complete. Therefore, it is difficult to solve the problem exactly. For this reason, heuristic solution procedures have been proposed to solve the problem approximately. In this paper, we first review two existing solution procedures proposed by Edmonds and Johnson [Math. Progr. 5, 88-124 (1973)], and Frederickson [J. Assoc. Comput. Mach. 26, 538-554 (1979)], then introduce two new algorithms to solve the MCPP near optimally. The proposed new algorithms are tested and compared with the existing solution procedures. Computational results showed that the two new algorithms significantly outperformed the existing solution procedures.
URI: http://hdl.handle.net/11536/1969
ISSN: 0305-0548
Journal: COMPUTERS & OPERATIONS RESEARCH
Volume: 22
Issue: 5
Begin Page: 479
End Page: 489
Appears in Collections:Articles


Files in This Item:

  1. A1995QR56300002.pdf