Abstract: The Chinese postman problem is one of the classical problems in graph theory and has been widely and deeply researched since it was proposed. It is applicable in a wide range of fields. With the rapid development of computer networks, computer communication and intelligent transportation system, problems in time-dependent networks become more realistic than the classical problems. First, we presented the definition of timcdependent Chinese postman problem (TDCPP) and the property of TDCPP. Then we showed that the classical algorithms of Chinese postman problem (CPP) can't work in the timcdependent circumstances. Finally, two layers SA/GA algorithm(simulated annealing/ genetic algorithm) was proposed, this approach was tested on some randomly generated data, the computational results were analyzed by comparing with lower bound of the problem.

Key words: Time-dependent,Chinese postman problem, Simulated annealing, Genetic algorithm