Route inspection 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. This area of graph theory is referred to by some authors as the area of arc routing problems. Gendreau defines this as, "In arc routing problems, the aim is to determine a least-cost traversal of a specified arc subset of a graph, with or without constraints." 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. Eulerian Circuits. The earliest documented reference to the area of arc routing problems is the classic bridges of Konigsberg challenge, which Euler proved to be impossible. The resident of Konigsberg, now part of Kaliningrad, wanted to find a way to cross all seven bridges over the river Pregel without backtracking or retracing their steps, that is crossing each bridge once and only once. In 1736, Euler reduced the problem to a question of nodes and edges and showed that the problem was impossible. In 1873, Hierholzer did more work on  the question of closed circuits. The work on the Eulerian circuits was popularized with Scientific American on July 1, 1953. This work was extended by Meigu Guan, also known as Kwan Mei-Ko at Shangtun Normal College. Meigu Guan was interested in a different question instead of determining a closed circuit. Guan worked to find out a minimum length walk that traversed every edge of the graph at least once. Guan described his goal in 1962: "A mailman has to cover his assigned segment before returning to the post office. The problem is to find the shortest walking distance for  the mailman." 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 formula_1 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. The windy postman problem is an arc routing problem (ARP) that contains the mixed chinese postman problem MCPP as a special case. The problem can be defined in the following manner:"Given an undirected and connected graph G=(V,E) with two non-negative costs formula_2 and formula_3  associated with each edge formula_4 corresponding to the cost of traversing it from i to j and from j to i, respectively, the WPP is to find a minimum cost tour on G traversing each edge at least once." This problem was introduced by Minieka. The WPP is NP-complete in general and can be solved in polynomial time if G is Eulerian, if the cost of two opposite orientations of every cycle in G in same or if G is a series-parallel graph. 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 formula_5 where formula_6 is the set of vertices and nodes and formula_7 is the set of arcs. Each arc represented by formula_8 has four costs: formula_9, defined as the cost of plowing from formula_10 to formula_11, formula_12, the cost of plowing from formula_11 to formula_10, formula_15, the cost of deadheading from formula_10 to formula_11, and formula_18, the cost of deadheading from formula_11 to formula_10. The setup assumes that formula_11 has a higher elevation formula_10, which leads to the statement: formula_23. In practice, downhill plowing time is two times as efficient as uphill plowing and deadheading  is twice as efficient as plowing. The algorithm finds formula_24 routes will each begin and end at the depot formula_25, 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. k-Chinese Postman Problem (k-CPP). The k-Chinese Postman can be stated as follows: "given a connected edge-weighted graph G and integers p and k, decide whether there are at least k closed walks such that every edge of G is contained in at least one of them and the total weight of the edges in the walks is at most p?" The process of  obtaining the solution to the k-CPP is NP complete. Gutin, Muciaccia, and Yeo proved in 2013 that the k-CPP is fixed-parameter tractable. The authors prove the k-CPP admits a kernel with formula_26 vertices and the directed version of the k-CPP is NP complete. Variants. A few variants of the Chinese Postman Problem have been studied and shown to be NP-complete.