Algorithms for the rural postman problem

W.l. Pearn*, T. C. Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

The rural postman problem (RPP) is a practical extension of the well-known Chinese postman problem (CPP), in which a subset of the edges (streets) from the road network are required to be traversed at a minimal cost. The RPP is NP-complete if this subset does not form a weakly connected network. Therefore, it is unlikely that polynomial-time bounded algorithms exist for the problem. In this paper, we review the existing heuristic solution procedures, then present two new algorithms to solve the problem near-optimally. Computational results showed that the proposed new algorithms significantly outperformed the existing solution procedures.

Original languageEnglish
Pages (from-to)819-828
Number of pages10
JournalComputers and Operations Research
Volume22
Issue number8
DOIs
StatePublished - 1 Jan 1995

Fingerprint

Dive into the research topics of 'Algorithms for the rural postman problem'. Together they form a unique fingerprint.

Cite this