Abstract: The time-dependent network Chinese postman problems(丁DCPP) have more applications than the classical Chinese postman problem(CPP). Many transportation and communication systems can be represented by network with travel times that arc timcdependent. When the arc traveling time of system model is timcdependent, the problem becomes considerably more difficult Firstly, it was proved that the standard CPP algorithms can not be used to solve the TDCPP. Then according to the properties for the TDCPP, a branch and bound algorithm for undirected timcdepended Chinese postman problem was derived. While, particularly, for the FIFO time varying network, a branch and bound algorithm was proposed which can solve the problem more effective. Finally, experiment was implemented on micro computo and results show that the algorithm can solve the TDCPP successfully.

Key words: Time-dependent network, Chinese postman problem, Branch and bound, FIFO