The Route Inspection Problem (Chinese Postman)

The Route Inspection Problem

The problem is to start from a node, travel along each and every arc and return to the starting point.  If it is possible to achieve this without going over the same arc twice, the minimum distance is just the sum of the arc lengths.  If it is necessary to cover some of the arcs twice, them we must select these in the most economic way.  This type of problem is called a Route Inspection Problem.  They are usually illustrated by gritter lorries or postmen, i.e. where all roads must be covered.

First we need to cover some network theory.

Node type – a n-node is a node where n arcs join

 

1-node, 3-node, … are called odd nodes

2-node, 4-node, … are called even nodes

In a network there must always be an even number of odd nodes.

Traversability – a network is said to be traversable if you can draw it without removing your pen from the paper and without retracing the same arc twice.

Looking at this network you will find you must start at one of the odd nodes and end at the other.

If you investigate other networks and note their node type numbers for each number you will find : For a network to be traversable it must have 0 or 2 odd nodes, and if we are to be able to start and finish at the same node it must have no odd nodes.  The implications of this result about traversability for route inspection problems are as follows.

If there are no odd nodes in the network, the network is traversable and the minimum distance is the sum of the arc distances.  Otherwise there will be an even number of odd nodes and the route inspection algorithm requires that we identify them and link them together in pairs in the most economic way.  The links selected will be repeated and the adding in of these extra arcs makes all the nodes even and the network traversable.

For more information on these procedures and the calculations behind them please see the previous posts on the route inspection problems.

Further Reading: http://residentialip.net/private-dedicated-proxies/