Latest revision as of 19:45, 24 April 2016

Chinese postman problem

Introduction

The Chinese postman problem, also known as the route inspection problem, is to find a circuit in a connected, undirected graph that visits each edge at least once. Additionally, a correct solution minimizes the total cost of the circuit. If all vertices of the graph have even degree, then the optimal solution is the Euler circuit of the graph. In this case, the cost of the solution is the sum of all edge weights in the graph.

In the case where the graph has some odd edges, the solution is more complicated. First, identify all nodes with odd degree. Next, pair up the odd nodes such that the sum of the weights of the shortest paths between pairs is a minimum. Then, take all the edges from the paths in the previous step, and duplicate them. This ensures that all nodes now have even degree, while adding the minimum possible weight to the graph. Finally, the solution is the Euler circuit of the modified graph, and the cost is the sum of all edge weights in the original graph plus the sum of the weights of the duplicated edges.

The three main steps (find odd nodes, find minimum paths, and find Euler circuit) can all be solved in polynomial time, so this problem can be solved in polynomial time.

History

During the Great Leap Forward movement period in Chinese history (1958-1960), President Mao of China encouraged scientists to solve real-world problems in order to accelerate the transformation of the Chinese economy. At that time, many mathematics researchers focused on problems like transportation and production planning. Shandong province, as a center of early Chinese mathematics research, is where the Chinese Postman Problem was created. (Grotschel & Yuan, 2010).

The Chinese Postman Problem was discovered by Chinese mathematician Kwan Mei-Ko. The problem described a situation that a Chinese postman would face every day. The exact problem was defined in Kwan's paper as, "A postman has to deliver letters to a given neighborhood. He needs to walk through all the streets in the neighborhood and back to the post-office. How can he design his route so that he walks the shortest distance?"

Then, he generalized the problem by counting the number of edges linked to a node as, "Given a connected graph where 2n of the nodes are odd and all other nodes are even. Suppose we need to add some edges to the graph with the following property: the number of edges added to any odd node is odd and that added to any even node is even. We need to minimize the total length of the added edges."

Then, he solved this problem by his theorem, which is also in his paper, "For a set of added edges it is necessary and sufficient to be an optimal solution for the above problem if the following two conditions hold:

1. Between any two nodes, no more than one edge is added,
2. In any cycle of the extended graph, the total length of the added edge is not greater than half of the total length of the cycle."

Real-world applications

An early example of an application is that a postman delivering letters in a village may wish to know a circuit that traverses each street (by minimizing the total traveled distance), starting and returning to his office. (Thimbleby, 2003) This is a graph theoretic problem: roads are connected edges, and the joint point of streets are vertices. The postman requires a Chinese Postman Tour(CPT).

Conventional applications of the Chinese Postman Problem (CPP) are concerned with routing in a more general way, as in planing snow ploughs or street maintenance. Nowadays, the CPP and CPT are more widely used in network algorithm checking.

Imagine trying to understand your mobile phone. Pressing buttons takes the phone to a new state, and corresponds to travelling an "edge". After some considerable work, one might obtain a map of how the phone works. However one doesn't know if the map is correct or not, and the map may be too difficult or complex to test systematically. Given the map, a CPT will provide a systematic test sequence that will exercise each transition. (Thimbleby, 2003) As a concrete example, the Nokia 2110 mobile phone has a menu subsystem of 88 menu-items and 274 actions (Nokia 2110 User's Guide, 1996). The optimal CPT takes 515 button presses plus 79 presses to check presses that has no functional ability. In comparison, the shortest trip that visits each vertex at least once, to check that each menu item function corresponds correctly to its name, is only 98 button presses. (Thimbleby, 2003) This is a much easier method to check the functionality.

Another example is the mobile robot exploration problem, where a robot has to explore a network by exploring every edge and vertex of the network before it knows the entire map. For a network of m arcs, an algorithm has been found that takes at most $ m \phi^{O(\log \phi)} $ steps, where $ \phi $ is the deficiency of the graph, which is a measure of the ease of use of a system. (Albers & Henzinger, 1997) We will see that the algorithm for the CPT also determines the deficiency. (Thimbleby, 2003)

Variations

Multiroute Chinese Postman

Imagine a mailman is responsible for delivering mail to all houses in a large district each week. Since there are too many houses to cover in a single day, the mailman must instead devise several smaller, approximately equal routes that fit within his work day.

This variation introduces significant challenges in defining a precise algorithm for finding a solution, since instead of simply "fixing" a given graph to make it Eulerian then defining an Euler circuit, one must divide the graph into several subgraphs, Eulerize the subgraphs, then check that the Euler circuits for the subgraphs are approximately equal in length. (Larson, 1999).

An imprecise algorithm for finding a solution to such a graph is given below:

1. Eulerize the input graph.
2. Draw rough closed boundaries to define each subgraph, taking care that the total edge length enclosed by each boundary are approximately equal.
3. Ensure all vertices within a subgraph have even degree by growing or shrinking boundary edges to include or exclude nearby vertices.

Eulerized Input Graph

Graph with rough boundaries

Vertices with odd edges highlighted in red

Adjusted boundaries

Eulerized subgraphs

There are several other variations on the Chinese Postman Problem with each name more imaginative than the last, like the New York Street Sweeper (directed graphs) and the Windy Chinese Postman (edges have different weights based on direction).

Example

Chinese Postman Algorithm (Pearson, 2004)

1. List all odd vertices.
2. List all possible pairings of odd vertices.
3. For each pairing, find the edges that connect the vertices with the minimum weight.
4. Find the pairings such that the sum of the weights is minimized.
5. On the original graph, add the edges that have been found in Step 4.
6. The length of an optimal Chinese postman route is the sum of all the edges added to the total found in Step 4.
7. A route corresponding to this minimum weight can then be easily found.

We will apply the above algorithm in the following example to find a minimum Chinese postman route.

1. 1 B, C, F and D are odd vertices.
2. BC-FD, BF-CD and BD-CF are possible pairings of odd vertices.
3. For each pairing find the edges that connect the vertices with the minimum weight: BC-FD: 8+11=19. BF-CD: 9+10=19. BD-CF: 17+18=35.
4. Find the pairings such that the sum of the weights is minimized: BC-FD and BF-CD.
5. On the original graph add the edges that have been found in Step 4. (See following graph)

1. Total weight should be 79+19=98.
2. A possible route of this weight can be AFEDFEDCFBCBA

References

Grotschel, M., & Yuan, Y. X. (2010). Euler, Mei-ko Kwan, Konigsberg, and a Chinese postman. Documenta Math, 43-50.

H. Thimbleby, The Directed Chinese Postman Problem, Practice and Experience, 2003, Vol.33(11), pp.1081-1096.

Kwan, M. K. (1960). Programming method using odd or even pints, Acta Mathematica sinica, 10, 263-266.

Larson, Richards, & Odomi, Amadeo. (1999). Multiroute Chinese Postman Problem. In "Urban Operations Research". Retrieved from

Nokia Mobile Phones, Nokia 2110 User’s Guide, Issue 5, 1996.

Pearson, David. (2004) Decision Maths 1. London : Heinemann.

S. Albers & M. R. Henzinger, Exploring Unknown Environments, Digital Systems Research Center, SRC Technical Note 1997-014, 1997.