Chinese Postman Problem - pgRouting/pgrouting GitHub Wiki

Definiton :

The Chinese postman problem is a mathematical problem of Graph theory. It is also known as route inspection problem. Suppose there is a mailman who needs to deliver mail to a certain neighborhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighborhood, that meets the following criteria:

• It is a closed circuit (it ends at the same point it starts).
• He needs to go through every street at least once.

If the graph traveled has an Eulerian Circuit, this circuit is the ideal solution.

Best explained: http://www.youtube.com/watch?v=fke5x0rmhpA