Route Inspection Problems (AS)

Introduction to Route Inspection Problems

Route Inspection Problems are also known as Chinese Postman Problems. They are problems where one needs to find the shortest possible route/circuit travelling along each edge at least once.
Edges that are visited more than once are referred to as repeated edges. The repeated edges form a set of shortest possible paths linking the odd vertices in pairs (the routes).
They are applied in various real-world scenarios such as garbage collection, mail delivery and street sweeping.

A Euler circuit is a route that starts and finishes at the same vertex and includes every edge once.
A Euler path exists when there are exactly two vertices of odd order (which are the start and end nodes), and all other vertices are of even order in a connected graph or multigraph.

Step 1: Identify the odd and even vertices. A vertex is odd if it has an odd number of edges coming from it.
Step 2: If all vertices are even then start at any vertex and draw the circuit. This is a Euler circuit.
Step 3: If there are exactly two odd vertices, start at one of them and draw the circuit - this is a Euler path.
Step 4: If there are more than two odd vertices, then key routes need to be created between the odd vertices so that all vertices become even. This also involves creating duplicate edges.
Step 5: The duplicate edges should make the total weight of the graph as small as possible. Start the circuit from any vertex and try to avoid using the duplicate edges until it’s not possible to avoid them.
Step 6: You will end up with a Eulerian circuit which includes every edge at least once with the smallest possible total weight (the solution).

The total weight of the graph with routes is called the total route weight.
If there are more than two odd vertices, a perfect matching should minimize the weight of the duplicate edges.
Route inspection is a question that often crops up on exams, so understanding these processes can lead to easy marks.