Title: | ALGORITHMS FOR THE RURAL POSTMAN PROBLEM |
Authors: | PEARN, WL WU, TC 工業工程與管理學系 Department of Industrial Engineering and Management |
Issue Date: | 1-Oct-1995 |
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. |
URI: | http://hdl.handle.net/11536/1710 |
ISSN: | 0305-0548 |
Journal: | COMPUTERS & OPERATIONS RESEARCH |
Volume: | 22 |
Issue: | 8 |
Begin Page: | 819 |
End Page: | 828 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.