ALGORITHMS FOR THE CHINESE POSTMAN PROBLEM ON MIXED NETWORKS

Scope and Purpose---Given an undirected street network, the celebrated Chinese postman problem (CPP) is that of finding a shortest postman tour covering all the edges (streets) in the network. The Chinese postman problem on mixed networks (MCPP), is an extension of the CPP, in which some streets from the network are allowed to be traversed in both directions, and others may be traversed in one specified direction only. Applications of the MCPP include: routing of newspaper or mail delivery vehicles, parking meter coin collection or household refuse collection vehicles, street sweepers, snow plows, and school buses; spraying roads with salt, inspection of electric power lines, or oil or gas pipelines, and reading electric meters. The MCPP has been shown to be NP-complete, and heuristic solution procedures have been proposed to solve the problem approximately. The purpose of this paper is to review the existing solution procedures, and present wo modifications of the existing methods to obtain better problem solutions. Abstract--The Chinese postman problem on mixed networks (MCPP), is a practical generalization f the classical Chinese postman problem (CPP), which has many real-world applications. The MCPP has been shown to be NP-complete. Therefore, it is difficult to solve the problem exactly. For this reason, heuristic solution procedures have been proposed to solve the problem approximately. In this paper, we first revie