Research On Chinese Postman Problem In Time-dependent Networks

Compared with the static network, Chinese Postman Problem(CPP) research in dynamic network is more applicable, especially for many complicated applications including Intelligent Transportation System(ITS), computer network and communication, etc. Though traditional network model and associated Chinese Postman Problem algorithms already have efficient algorithms, the traditional algorithm is impractical when the network is time-dependent. Due to the efficient algorithm for the time-dependent VRP problem, we can bring in the theory to solve the problem. Therefore, the research of new network model and associated high efficient algorithm for Chinese Postman Problem in time-dependent networks become an important problem to be solved urgently, which is also the goal of this paper.This paper summarizes some results of branches of Chinese Postman Problem. This paper also introduces Static Chinese Postman Problem as well as it's solutions in detail. Then, this paper introduces basic concept, the linear programming model, the FIFO characteristic of Time-Dependent network, also NP hard of the problem is proved, and has given theory foundation for the shortest-path algorithm of time dependent network. This paper also compares Time-Dependent Chinese Postman Problem with Static Chinese Postman Problem, and analyzes sick instances which the static algorithms in dynamic networks. Finally, this paper produces dynamic programming algorithm and Nearest-Neighbor Heuristic algorithm for Time-Dependent network Eulerian Problem.Then this paperpresent a branch-cut-plane algorithm and an algorithm based on an Ant Colony System using a time-dependent pheromones space. Finally randomly generated problems are tested to illustrate how the algorithm can be applied.The time-dependent network model and the Chinese Postman Problem provide a wholly new method to effectively implement the Chinese Postman Problem for dynamic network. The advantages of Chinese Postman Problem in time-dependent network algorithm express not only on the wide use in many practical areas, but also on the great efficiency to solve the problem, which is very important for many applications.