Route inspection problem

In graph theory, a branch of mathematics and computer science, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the fewest number of edges to add to the graph so that the resulting multigraph does have an Eulerian circuit.^[1]

Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962.^[2]

Eulerian paths and circuits

In order for a graph to have an Eulerian circuit, it will certainly have to be connected.

Suppose we have a connected graph G = (V, E), The following statements are equivalent:

All vertices in G have even degree.
G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
G has an Eulerian circuit.

1 → 2 can be shown by induction on the number of cycles.
2 → 3 can also be shown by induction on the number of cycles, and
3 → 1 is immediate.

An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence (degree).

T-joins

Let T be a subset of the vertex set of a graph. An edge set is called a T-join if in the induced subgraph of this edge set, the collection of all the odd-degree vertices is T. (Note that in a connected graph, a T-join will always exist as, due to the handshaking lemma, |T| will always be even.) The T-join problem is to find a smallest T-join. When T is the set of all odd-degree vertices, a smallest T-join leads to a solution of the postman problem. For any T, a smallest T-join necessarily consists of $\tfrac{1}{2}$ |T| paths, no two having an edge in common, that join the vertices of T in pairs. The paths will be such that the total length of all of them is as small as possible. A minimum T-join can be obtained using a weighted matching algorithm that uses O(n³) computational steps. As this is equivalent to a complete graph with an even number of vertices, it will always be a perfect matching^[3]^[4]

Solution

If a graph has an Eulerian circuit (or an Eulerian path), then an Eulerian circuit (or path) visits every edge, and so the solution is to choose any Eulerian circuit (or path).

If the graph is not Eulerian, it must contain vertices of odd degree. To solve the postman problem we first find a smallest T-join. We make the graph Eulerian by doubling of the T-join. The solution to the postman problem in the original graph is obtained by finding an Eulerian circuit for the new graph.^[4]

On Directed Graphs

On a directed graph, the same general ideas apply, but different techniques must be used. If the graph is Eulerian, one need only find an Euler cycle. If it is not, one must find T-joins, which in this case entails finding paths from vertices with an in-degree greater than their out-degree to those with an out-degree greater than their in-degree such that they would make in-degree of every vertex equal to its out-degree. This is reducible to the Transportation Problem and thus to finding a minimum cost Network Flow. As such it is solvable in O(|V|²|E|) time. Note that this case requires that the graph be strongly connected, not merely connected.^[4]^[5]

Applications

Various combinatorial problems are reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph and a minimum-mean length circuit in an undirected graph.^[6]

Variants

A few variants of the Chinese Postman Problem have been studied and shown to be NP-complete.^[7]

Minimize the Chinese postman problem for mixed graphs: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."^[8]
Minimize the k-Chinese postman problem: find k cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
Minimize the "Windy Postman Problem": solve the problem on a graph where the weight of an edge depends on the direction along which it is traveled. ^[9]
Minimize the "Rural Postman Problem": solve the problem with some edges not required. ^[9]

References

↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
↑ ""Chinese Postman Problem"". - NIST
↑ Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
1 2 3 Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem", Mathematical Programming 5: 88–124, doi:10.1007/bf01580113
↑ Eiselt, H. A.; Gendeaeu, Michel; Laporte, Gilbert. "Arc Routing Problems, Part 1: The Chinese Postman Problem". Operations Research. INFORMS. pp. 231–242. doi:10.1287/opre.43.2.231. Retrieved 2 December 2014.
↑ A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
↑ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 2008-10-22. Cite uses deprecated parameter |coauthors= (help)
↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829
1 2 Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems", Networks 11 (2): 221–227, doi:10.1002/net.3230110211

External links

Chinese Postman Problem

This article is issued from Wikipedia - version of the Saturday, September 19, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.