Improved solutions for the Chinese postman problem on mixed networks

W.l. Pearn*, J. B. Chou

*Corresponding author for this work

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

The Chinese postman problem (CPP) is that of finding the shortest postman tour covering all the roads in the network. The CPP is polynomial-time solvable on totally directed or undirected networks, but is NP-complete on mixed networks (MCPP). Several heuristic solution procedures including Mixed-1, Mixed-2, Modified Mixed-1, and Modified Mixed-2 algorithms, have been proposed to solve the problem approximately. In this paper, we briefly review these four existing algorithms, then propose two improvement procedures to improve the solutions. The proposed procedures are tested and compared with the four existing algorithms. The results show that the proposed procedures significantly improve the existing solutions. Scope and purpose Given a road network, the Chinese postman problem (CPP) is to find the shortest postman tour covering all the roads in the network. The CPP is polynomial-time solvable on directed or undirected networks, but is NP-complete on mixed networks (MCPP). On mixed networks, some roads are allowed to be traversed in both directions, and others may be traversed in one specified direction only. Applications of the MCPP include routing of mail-delivery vehicles, parking-meter coin collection or household refuse collection vehicles, street sweepers, snow plows, school buses; inspection of electric power or oil lines, and reading electric meters. The purpose of this paper is to review the existing solution procedures, and introduce two new procedures to improve the existing solutions.

Original languageEnglish
Pages (from-to)819-827
Number of pages9
JournalComputers and Operations Research
Volume26
Issue number8
DOIs
StatePublished - 1 Jul 1999

Keywords

  • Combinatorial optimization
  • Network routing

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

  • Cite this