What is the Chinese Postman Problem?

The Chinese

Postman Problem is named after the Chinese mathematician, Kwan Mei-Ko, who

discovered it in early 1960’s. The background of Chinese postman problem is

interesting. It is the problem that the Chinese Postman faces: he wishes to

travel along every road in a city in order to deliver letters, with the least

possible distance.

The Chinese

Postman Problem or Route Inspection Problem is about visiting

each route between cities at least once while returning to the original city

and taking the shortest route among all possible routes that fulfill this

criterium (if such a route exists). A solution that takes each route exactly

once is automatically optimal and called an Eulerian Cycle. Finding such a

cycle is easily possible. The true problem, however is how to find a shortest

closed walk of the graph in which each edge is traversed at least once,

rather than exactly once. In graph theory, an Euler cycle in a connected,

weighted graph is called the Chinese Postman problem. However, the Chinese

Postman Problem differs from Euler circuit problems.

How do they differ?

The difference between Euler’s

circuit, which involved crossing each edge once and once only in order to be

solved, and the Chinese Postman problem, which allowed an edge to be crossed

more than once, however, the weight of the circuit is considered instead. This

problem differs as well from the problem of the travelling salesman.

The travelling salesman needs to

visit every node (or vertex) whereas the Postman needs to travel along each arc

(or edge). Therefore, it is required that the network is traversable

(Eulerian). The problem is therefore to obtain “a closed trail of minimum weight

containing every arc. Another way to put it is to “find a route of minimum

weight which traverses every edge at least once, returning to the start

vertex”.

Examples (A):

Here are two graphs, one

which can be solved with a Euler circuit and one that is considered as a

Chinese Postman Problem. The Euler circuit does not have a numerical weight on

it, and therefore its required to be solved by going over every edge once and

once only. The Chinese Postman problem, however, includes a numerical weight on

each individual edge, and must be solved by having the lowest possible weight,

all while being able to visit each vertex and then return to the starting

vertex.