Thread: Chinese Postman Problem

Hi,

does anybody know how to solve chinese postman problem as maximal network flow problem?

thanks!

Originally Posted by rory1982

Hi,

does anybody know how to solve chinese postman problem as maximal network flow problem?

thanks!

I have never heard of "chinese postman problem".
It is anything like the american postman problem?

Is is possible for you to state the problem?
It is clear that you want the result to be a "maximal network flow" approach.

I don't know 'cause i never heard of american postman problem

Chinese postman problem:
A postman has to deliver mail along all the streets in the town. Assume that on one-way street the mail boxes are all on one side of the street, whereas for two-way streets, there are mail boxes on both sides of street. The postman wishes to minimize the distance he has to travel in order to deliver all the mail and return home to his starting point.

So, we can model the problem by a directed graph and a weight function, where set of vertices are intersection of streets, and arcs model the streets. A 2-cycle corresponds to a two-way street. The weight of an arc corresponds to the lenght of the corresponding street. Optimal route corresponds to a closed walk which traverses each arc at least once.

So it can be solved as a minimum cost problem. But i don't know how to draw a network with source and sink and how to solve it as maximal flow problem?

thanks!