Improved solutions for the Chinese postman problem on mixed networks
檔案
- 000079830400006.pdf (119.1 KB, Adobe PDF)
日期
1999-07-01
類型
系所
期刊名稱
COMPUTERS & OPERATIONS RESEARCH
卷期與頁次
第 26 卷第 8 期,頁 819–827
ISSN
0305-0548
語言
英文
摘要
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. (C) 1999 Elsevier Science Ltd. All rights reserved.