Branch And Bound Algorithm For The Time Dependent Chinese Postman Problem

Chinese postman problem is a classic graphic problem, it is widely applied by fields such as software tested, mail delivered. Time dependent Chinese postman problem is extend of the Chinese postman problem, it consider the time and have more advantage than Chinese in problem with time factor, such as real time software test.We introduce the classification, the study situation and application of the Chinese postman problem in the classic static networks; then we analyze the disadvantages of the classic Chinese postman problem, and then the advantages of the Chinese postman problem in time varying environment compare to the classic Chinese postman problem, and the study situation ,difficulty and meaning of the Chinese postman problem in time varying environment; make base for future study. In this paper:(1) Give the reason why traditional methods unuseful: the varying cost of edge. We give an example that can't be used in time varying environment to understand it more clearly.(2) Propose several characteristic and branch-bound algorithms for time dependent Chinese postman problem (TDCPP). we propose several theories that can be applied to the time varying environment for directed and undirected networks, prove it to confirm the correction, branch and bound algorithms based on these properties are designed.(3) Particularly, for the FIFO (first in first out) time varying network, we also give special characteristic to improve the algorithm. The FIFO cut-condition can be used for more effective branch and bound algorithm.(4) Test and analyze the algorithm. We construct the tree of solution space to understand the problem; then, we list the results of the algorithms by table, and analyze the algorithms further on base of the results.In this paper, we solve the TDCPP by branch-bound algorithm for the first time. The problem became very difficult when consider the time factor. By the result, we found that, our algorithm is useful for simple TDCPP.