route-inspection

Chinese postman problem

What is the Chinese postman problem?

• The route inspection problem is also known as the Chinese postman problem

• You are required to find the route of least weight that traverses every edge in the graph such that the route starts and finishes at the same vertex

• Some edges may need to be traversed twice and the challenge is to minimise the total weight of these repeated edges

• Variations to the route inspection problem could involve

  • the start and finish vertices being different

  • certain edges being disregarded

    • e.g. a road closure

  • the route requiring repetition

    • e.g. a road sweeper covering both sides of the road

Networks with 0 or 2 odd nodes

How do I solve the Chinese postman problem?

• If the graph is Eulerian

  • all of the vertices in the graph are even

    • i.e. 0 odd nodes

  • it will be possible to find an Eulerian circuit

    • i.e. a route that traverses each edge once only, starting and finishing at the same vertex

  • no route/edges will need repetition 

  • the shortest route will be the sum of the weights of the edges in the network

• If the graph is semi-Eulerian

  • there will be one pair of odd vertices

    • i.e. 2 odd nodes

  • if the route has to start and end at the same vertex

    • the shortest path between the two odd nodes will need to be found

      • the edges making that route will need to be repeated

    • the shortest route will be the sum of the weights of the edges in the network plus the weight of the repeated edges

  • if the route starts at one of the odd vertices and ends at the other

    • no edges will need repetition

    • the shortest route will be the sum of the weights of the edges in the network

What are the steps of the Chinese postman algorithm?

• STEP 1
  Inspect the degree of all of the vertices and identify any odd nodes

• STEP 2
  If all of the vertices are even go to STEP 3 If there is one pair of odd nodes, find the shortest path between them – the edges making this path will need repeating so add them to the graph

• STEP 3
  Write down an Eulerian circuit of the adjusted graph to find a possible route

  • Find the sum of the edges traversed to find the total weight