ALGORITHMS FOR THE RURAL POSTMAN PROBLEM

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.