Chinese postman problem

In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (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 smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time.

The problem was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962. The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to Alan J. Goldman or Jack Edmonds, both of whom were at the U.S. National Bureau of Standards at the time.

A generalization is to choose any set T of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of T. Such a set is called a T-join. This problem, the T-join problem, is also solvable in polynomial time by the same approach that solves the postman problem.

Solving the problem efficiently with different algorithms is important in many areas including mail delivery, garbage collection, snow removal with different teams and plows, school bus routing, Internet routing, package delivery and more. For example, Cristina R. Delgado Serna & Joaquín Pacheco Bonrostro applied approximation algorithms to find the best school bus routes in the Spanish province of Burgos secondary school system. The researchers minimized the number of routes that took longer than 60 minutes to traverse first. They also minimized the duration of the longest route with a fixed maximum number of vehicles.

Undirected solution and T-joins

The undirected route inspection problem can be solved in polynomial time by an algorithm based on the concept of a T-join. Let T be a set of vertices in a graph. An edge set J is called a T-join if the collection of vertices that have an odd number of incident edges in J is exactly the set T. A T-join exists whenever every connected component of the graph contains an even number of vertices in T. The T-join problem is to find a T-join with the minimum possible number of edges or the minimum possible total weight.

For any T, a smallest T-join (when it exists) necessarily consists of ${\tfrac {1}{2}}|T|$ paths that join the vertices of T in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum T-join can be obtained by constructing a complete graph on the vertices of T, with edges that represent shortest paths in the given input graph, and then finding a minimum weight perfect matching in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired T-join. Both constructing the complete graph, and then finding a matching in it, can be done in O(n³) computational steps.

For the route inspection problem, T should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the handshaking lemma it has an even number of odd vertices, so a T-join always exists. Doubling the edges of a T-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an Euler tour, a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.

Directed solution

On a directed graph, the same general ideas apply, but different techniques must be used. If the directed 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 can be solved as an instance of the minimum-cost flow problem in which there is one unit of supply for every unit of excess in-degree, and one unit of demand for every unit of excess out-degree. As such it is solvable in O(|V|²|E|) time. A solution exists if and only if the given graph is strongly connected.

Windy postman problem

The windy postman problem is a variant of the route inspection problem in which the input is an undirected graph, but where each edge may have a different cost for traversing it in one direction than for traversing it in the other direction. In contrast to the solutions for directed and undirected graphs, it is NP-complete.

Applications

Various combinatorial problems have been 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.

Snow Plows

In winter a common question is what set of routes has the smallest (minimum) maximum route length? Typically, this is assessed as an arc routing problem with a graph. The time it takes to travel a street, known as deadhead time, is faster than the time it takes to plow the snow from the streets (or deliver mail or drop off packages). Another aspect that must be considered when applying arc routing to snow plowing is the fact that on steep streets it is either difficult or impossible to plow uphill. The objective is a route that avoids plowing uphill on steep streets that completes the job faster by maximizing the deadhead time to get the location. This was modeled with a heuristic algorithm that approximates a lower bound by Dussault, Golden and Wasil. This is the Downhill Plow Problem (DPP). Snow teams prefer to plow downhill and deadhill uphill. This problem assumes that the conditions are severe enough that the streets are closed and there is no traffic.

The Downhill Plowing Problem ignores the Plowing with Precedence Problem (PPP), which is built on the reasonable assumption that if the snow is too deep the snow plow cannot deadhead an unplowed street. The DPP makes the assumption that the snow level is low enough that the streets that are not plowed can be deadheaded, but that the snow is deep enough that there is no traffic. If there is traffic on the roads, the assumption that it is impossible to plow uphill can no longer be held. The simulation for the DPP deadheaded unplowed street about 5% of the time, which is a topic for future graph theory and arc routing research.

Considering an undirected graph $G=\{V,A\}$ where $V$ is the set of vertices and nodes and $A$ is the set of arcs. Each arc represented by $(v_{i},v_{j})$ has four costs: $c_{ij}^{+}$, defined as the cost of plowing from $v_{i}$ to $v_{j}$, $c_{ji}^{+}$, the cost of plowing from $v_{j}$ to $v_{i}$, $c_{ij}^{-}$, the cost of deadheading from $v_{i}$ to $v_{j}$, and $c_{ji}^{-}$, the cost of deadheading from $v_{j}$ to $v_{i}$. The setup assumes that $v_{j}$ has a higher elevation $v_{i}$, which leads to the statement: $c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}$. In practice, downhill plowing time is two times as efficient as uphill plowing and deadheading is twice as efficient as plowing. The algorithm finds $k$ routes will each begin and end at the depot $v_{0}$, plow the arc two times because the left side and right side of the street take two passes to plow.

The best solution will minimize the maximum route length. Dussault, Golden, and Wasil found an algorithm that did not exceed the lower bound by 5.5% in over 80 test runs. The deviation increased as the complexity of the model increased because there are more unoptimized approximations than optimized approximation as the model grows. An improvement on Dussault et. al's DPP algorithm might have penalties for making U-turns and left hand turns, or going straight across an intersection, which take additional time and pushes snow into the middle of the intersection, respectively. (see The Directed Rural Postman Problem with Turn Penalties problem, often referred to as the DRPP-TP below).

Variants

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

• 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."
• 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.
• The "Rural Postman Problem": solve the problem with some edges not required.

See also

• Travelling salesman problem

External links

• Weisstein, Eric W., "Chinese Postman Problem", MathWorld
• Media related to Route inspection problem at Wikimedia Commons