Chinese Postman Problem

DOI: 10.4018/978-1-4666-2661-4.ch016

Abstract

One of the very popular applications of the graph theory in real world problems is related to the concept of Eulerian tours and trails introduced in Eulerian trail and tours chapter. There are many problems in which users should serve all the connections (edges in a graph, streets of a city, pipelines of a network and etc.) between nodes. In chapter 7 of this book, the existence of such trails and tours in graphs were discussed, and appropriate algorithms were introduced to find Eulerian trails and tour. But in the case a graph does not have such a tour or trail, it’s important to traverse some edges more than once, and this is what usually happens in real world applications. M.K. Kwan in 1962 was the first who introduced this problem as the Chinese postman problem (CPP). The question was that, given a postal zone with a number of streets that must be served by a postal carrier, how can one develop a tour that covers every street in the zone and brings the postman back to his or her point of origin, having traveled the minimum possible distance (Wang et al., 2008)? In this chapter, the Chinese postman problem is discussed, and different variations of it are introduced. Then the very early form of the CPP in which the graph is undirected is explained in more detail.
Chapter Preview
Top

Variations Of Chinese Postman Problem

There are many variations of CPP in the literature. The most popular variations of CPP are:

• Undirected CPP: The edges have no direction.

• Directed CPP: Each of the edges has a direction.

• Mixed CPP: Contains a combination of both directed and undirected edges.

• Rural CPP: A subset of the edges in the graph must be traversed.

• Capacitated CPP: Postmen has limited capacities.

• Time constrained CPP: The postman has time constraint for delivering the mails.

• Hierarchical CPP: Arcs are categorized into clusters and a precedence relation is defined.

• Open CPP: The postman doesn’t need to get back to the origin.

Here different variations of CPP with a brief explanation of them are presented and in the next section its simple and original form for undirected graphs will be discussed in more detail.

Undirected CPP

The special case in which the underlying graph is completely undirected (i.e. consists entirely of two-way streets) has been examined in detail and can be solved efficiently in polynomial time (Kwan, 1962). This is discussed in the last part of the chapter.

Directed CPP

Each of the edges in the directed CPP has a direction associated with it. A directed graph has a postman tour if and only if it is strongly connected. Therefore it is easy to decide whether a directed graph has a postman tour or not. Then obtaining that tour of a directed graph becomes a more interesting problem. This case can also be solved in polynomial time (Edmonds & Johnson, 1973). A special kind of CPP when the cost of an edge depends on the direction of traversal is called Windy Postman problem in some references (Martinez, 2008), but since they are modeled as directed graphs we do not classified them in another group.

Complete Chapter List

Search this Book:
Reset