CHINESE POSTMAN PROBLEM FOR MIXED NETWORKS

The Chinese postman problem is to find a least cost way to traverse each arc of a network at least once and to return to the vertex from which you started. Diverse problems such as the routing of road crews, police patrol scheduling, garbage collection and the programming of computer map printers can be modeled as Chinese postman problems. This study surveys available solution techniques for the Chinese postman problem for totally undirected networks (when all streets are two-way streets) and for totally directed networks (when all streets are one-way streets). A known solution technique for networks with both directed and undirected arcs (both one-way and two-way streets) in which the degree of each vertex is an even number is also reviewed. A solution technique for these mixed networks in which some vertices have odd degree is presented. This technique is based on the before mentioned technique and requires the solution of a minimum cost flow problem on a network that is an extension of the original network. This work is also pertinent to transportation.