標題: Improved solutions for the Chinese postman problem on mixed networks
作者: Pearn, WL
Chou, JB
工業工程與管理學系
Department of Industrial Engineering and Management
關鍵字: combinatorial optimization;network routing
公開日期: 1-Jul-1999
摘要: 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.
URI: http://dx.doi.org/10.1016/S0305-0548(98)00092-6
http://hdl.handle.net/11536/31236
ISSN: 0305-0548
DOI: 10.1016/S0305-0548(98)00092-6
期刊: COMPUTERS & OPERATIONS RESEARCH
Volume: 26
Issue: 8
起始頁: 819
結束頁: 827
Appears in Collections:Articles


Files in This Item:

  1. 000079830400006.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.