Improved solutions for the Chinese postman problem on mixed networks

Abstract

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.