 The Chinese Postman Problem for Mixed NetworksEdward Minieka
Management Science, 1979, vol. 25, issue 7, 643-648 Abstract: 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 modelled as Chinese postman problems. This paper 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. Some of the additional arcs in this network have gain factors (i.e., the flow leaving these arcs equals the flow entering times the gain factor) and the flows are required to be integer valued. Keywords: networks/graphs; transportation; mathematics: combinatorics (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:25:y:1979:i:7:p:643-648 Access Statistics for this article More articles in Management Science from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.