標題: ALGORITHMS FOR THE CHINESE POSTMAN PROBLEM ON MIXED NETWORKS
作者: PEARN, WL
LIU, CM
工業工程與管理學系
Department of Industrial Engineering and Management
公開日期: 1-五月-1995
摘要: 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
期刊: COMPUTERS & OPERATIONS RESEARCH
Volume: 22
Issue: 5
起始頁: 479
結束頁: 489
顯示於類別:期刊論文


文件中的檔案:

  1. A1995QR56300002.pdf