What's the cheapest round trip?
The (Chinese) Postman Problem, also called Postman Tour or Route Inspection Problem, is a famous problem in Graph Theory: The postman's job is to deliver all of the town's mail using the shortest route possible. In order to do so, he (or she) must pass each street once and then return to the origin.
We model this problem using a directed graph. Edges and nodes represent streets and intersections, respectively. The length of a street is represented by the weight of the corresponding edge. By using directed edges, it's possible to also account for one-way-streets etc in the graph.
|Edge with a weight of 50|
You can open another browser window to read the description in parallel.
Each node is labeled with the difference of its Out- and In-Degrees. Nodes with a difference different from 0 are called "imbalanced". Knoten mit der Differenz ungleich 0 sind unbalanciert.
On the Left: The bipartite Matching Graph with all imbalanced nodes. Here, we can determine between which nodes we can insert new paths. On the Right: The graph after inserting the new paths.
The matching edges determine, where new paths must be inserted.
Newly Inserted Edge.
The dotted line represents edges that are traversed multiple times.
The different colors label the different subtours taken by the Hierholzer method.
The standard example for this problem is a postman who needs to traverse all streets of a town and then return to the origin. It's his goal to walk the minimum distance possible. We can model this problem using a graph: A (directed) path (or dipath) is a sequence of edges where each edge's origin node is the ending node of the previous edge. A path is called closed if it ultimately terminates in its origin node (the origin node of the first edge).
A closed path is called Euler Tour, if it contains all edges of the graph exactly once. Thus, the postman problem consists of finding a closed path (Round Tour) in the graph, such that all edges are traversed at least once and the sum of edge weights in the path (Cost of the Round Tour) is minimal.
First of all, since any nodes without incoming or outgoing edges do not influence the problem, we can assume that no such edges exist. The problem has a solution if and only if the graph is strongly connected (each node can be reached from every other node) and contains no negative cycles (closed paths with negative total edge weight). If the graph is not strongly connected, then no round tour can exist; if there is a negative cycle somewhere, then the optimal cost will be infinitely small. The problem can be reduced to finding an Euler Tour in the graph. If an Euler Tour exists, it must be the optimal tour, since each edge is traversed exactly once. Otherwise, one or more edges will have to be visited multiple times. This situation can be modeled by adding additional Edges to the graph that represent edges used multiple times (and have the same weight as the original edge). Then the round trip using the edge multiple times will have the same cost as the corresponding Euler Tour in the new graph. Now, we are only left with the problem of identifying the edges that will be used multiple times in the optimal solution.
The number of incoming edges at a vertex is called the In-Degree of that vertex, the number of outgoing ones its Out-Degree. A theorem in graph theory states that a graph has an Euler Tour if and only if the In- and Out-degrees are the same for all vertices of the graph. Therefore, it is sufficient to add additional paths to the graph, such that In- and Out-Degrees match for all nodes after inserting the new paths. The sum of the edge weights of these paths should be minimal. We will specify which paths to add in the Matching-Phase of the algorithm.
After making sure that the graph contains an Euler Tour, we still have to find it. To do so, we may use any appropriate algorithm, such as the Hierholzer method. The cost of the optimal round trip then is exactly the sum of all edge weights in the Euler Tour.
We need to insert paths from those nodes with too few outgoing edges to those nodes with too few incoming edges. Since we aim to minimize our costs, these should be shortest paths. One way to find those shortest paths is to use the algorithm of Floyd-Warshall. The Floyd-Warshall Algorithm happens to be especially useful here, as it simultaneously finds the shortest paths between all pairs of vertices. We will then use the costs of the shortest paths in the Matching Phase in order to determine the optimal set of shortest paths to use.
By inserting additional paths, we aim to balance In- and Out-degrees for all vertices of the graph, as only then an Euler Tour will exist. Let \(\delta_v\) be the difference of out- and in-degrees of node v. We call all nodes v with \(\delta_v \neq 0 \) imbalanced. In order to determine which paths to add, we need a mapping from nodes with negative \(\delta_v\) to those with positive \(\delta_v\). Here \(\delta_v\) specifies the number of new paths that need to start or end in v. Adding a path will increase \(\delta_o\) by 1 in its origin o, and decrease \(\delta_d\) by 1 in its destination d.
The weight of the additional paths must be minimized. In order to reach this goal, we can create a new bipartite graph that contains all imbalanced nodes. We partition the imbalanced vertices into two sets: those with negative and those with positive \(\delta_v\)). \(\delta_v\) determines, how often the vertex v will appear in the new bipartite graph. As an example, a vertex v with \(\delta_v=3\) will have exactly 3 copies in this Matching-graph. For sake of readability, each imbalanced node has only been drawn once in the visualization of the algorithm. Therefore the vertices in the visualization of the matching graph may lie on more than one matching edge (as determined by \(\delta_v\) ).
The weight of an edge in the matching graph represents the length of the shortest path from its origin node (that with negative \(\delta_v\)) to its destination node (that with positive difference). The sum of all in- and out-degrees of any graph will always be balanced. Thus the same is true for the sums of positive and negative \(\delta_v\)s. We therefore end up with a complete bipartite graph. Now, we can use an algorithm for finding optimal weighted matchings (such as the Hungarian Method). This will then yield the optimal matching and we can proceed to add the additional paths. The edges of these paths then represent the edges which will appear multiple times in the optimal Round Trip.
After adding these additional paths, the in- and out-degrees of all vertices in the graph will be balanced. Then a Euler Tour must exist in the graph and it can be found using the Hierholzer method. The cost of the optimal round trip is given by the sum of all edge weights of this Euler Tour.
The algorithm will run as normal but stop every once in a while. Then you will have to decide what would be the next step.
Hint: Read the description of the algorithm one more time before trying.
You can open another browser window to read the description in parallel.
You can open another browser window for reading the description in parallel.
Input: Weighted, directed graph G=(V,E) Output: Length of a shortest round trip that contains all edges (if such a solution exists.)
BEGIN 1. Check for solvability 2. Find imbalanced nodes 3. Determine additional paths 4. Insert additional paths 5. Determine the Euler Tour END
The speed of an algorithm is the total number of individual steps which are performed during the execution.
These steps are for example:
Since it can be very difficult to count all individual steps, it is desirable to only count the approximate magnitude of the number of steps. This is also called the running time of an algorithm. Particularly, it is interesting to know the running time of an algorithm based on the size of the input (in this case the number of the vertices and the edges of the graph).
The optimal round tour can be transformed into an Euler tour by adding to the graph (the appropriate number of) copies of the edges that are used multiple times. Thus the problem can be reduced to extending the graph to an Euler graph (a graph that contains an Euler tour.)
The cheapest Extension is the shortest round trip that we aim to find. This subproblem is solved using the Matching step in the algorithm. Finally, the Euler tour will be found. Therefore the algorithm correctly solves the postman problem.
Other graph algorithms are explained on the Website of Chair M9 of the TU München.
Furthermore there is an interesting book about shortest paths: Das Geheimnis des kürzesten Weges
Studying mathematics at the TU München answers all questions about graph theory (if an answer is known).
Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the optimization of mathematical problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the research conducted daily at the chair reaches far beyond that point). This page shall provide the possibility pupils and students to understand and fully comprehend the algorithms (which are of importance also in daily life).
To cite this page, please use the following information: