標題: ALGORITHMS FOR THE RURAL POSTMAN PROBLEM
作者: PEARN, WL
WU, TC
工業工程與管理學系
Department of Industrial Engineering and Management
公開日期: 1-Oct-1995
摘要: 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
期刊: COMPUTERS & OPERATIONS RESEARCH
Volume: 22
Issue: 8
起始頁: 819
結束頁: 828
Appears in Collections:Articles


Files in This Item:

  1. A1995RE79600005.pdf

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.