Algorithms for the Chinese postman problem on mixed networks

W.l. Pearn*, C. M. Liu

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Scopus citations

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.

Original languageEnglish
Pages (from-to)479-489
Number of pages11
JournalComputers and Operations Research
Volume22
Issue number5
DOIs
StatePublished - 1 Jan 1995

Fingerprint Dive into the research topics of 'Algorithms for the Chinese postman problem on mixed networks'. Together they form a unique fingerprint.

  • Cite this