Route inspection problem

The Postman Problem is a term from graph theory. Here, the transmitted image of a postman which discharges via the shortest route letters, use is: A postman to deliver the letters (on both sides of the road at the same time ) in a road network (city).

His English name (Chinese postman problem) received the postman problem by Alan Goldman after the Chinese mathematician Mei Ko Kwan, the first time in 1962 investigated the problem. A solution was given in 1973 by Jack Edmonds and Ellis L. Johnson.

Modeling of the problem with graph

Is modeled by means of the problem graph. Here, roads are modeled as edges and junctions as nodes. The edge is assigned the length of the corresponding road. What is needed is now a shortest cycle that goes through all the streets at least once.

Solution of the problem

The solution of the problem depends on the resulting graph. In Eulerian graph ( connected graph with straight node degrees ) corresponds to the shortest route of each edge exactly once continuous Euler tour. In trees, each edge must be traversed exactly twice. General can be solved by making the graph at minimum cost by inserting additional edges Euler tour and thus returns the problem of finding an Euler tour problem. If a connected graph is Eulerian not, he has nodes with odd degree nodes. Since nodes occur in any graph with odd degree only in even numbers is even. If you connect two nodes odd node degree by an additional way to be straight, while the even node degrees remain just the odd node degrees. Must be inserted into the graph to make the graph Euler tour for a total additional ways.

For minimum cost expansion of the graph is a complete graph is created to the nodes with odd degree. As the edge weights are selected in each case the distance of the shortest path ( determined for example with the matrix multiplication or the Tripelalgorithmus ) between the two corresponding nodes in the original graph. In this complete graph, a minimum-cost perfect pairing is then searched with matching edges. The edges of the respective shortest path between the two nodes are then matching for each edge in the original graph is duplicated. On these edges of the original graph of the letter carrier must so run along exactly twice. Each Euler tour in the graph is extended so then an optimal solution of the postman problem.

Example

It is a city with streets fourteen and nine intersections 1, ..., given 9. The corresponding graph ( see the first figure ) has four nodes ( 1,3,6 and 9) with odd degree nodes and is therefore not Euler tour. Wanted is now a cost- minimal Euler's extension of the graph in order to specify an Euler tour can. If you were to double, for example, the two edges {1,3 } and { 6,9 }, the resulting graph would Euler tour since then all nodes have even degree. The corresponding Euler tour would be but for the postman not necessarily the shortest tour. To determine the shortest extension of the complete graph is the node with odd degree nodes created (second figure). As edge weight, the length of the shortest path between any two nodes is respectively removed. The minimum matching in this case from the edges { 1,6 } and { 3,9 } with total length. The corresponding edges of the shortest path from 1 to 6 and from 3 to 9 are then in the original graph also entered (third figure). An Euler tour and hence minimum postman round trip would be, for example, the sequence of nodes ( 1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1 ). The streets that meet the additionally inserted red edges, thereby doubly traversed by the postman.