Research On Intelligent Algorithms Of Time-Dependent Chinese Postman

The Chinese Postman Problem (CPP) was first proposed by the Chinese mathematician Meigu Guan in 1960. It is one of the classical problems in graph theory. It says that a postman picks up mails at the post office, delivers it along a set of streets, and returns to the post office. Since it must cover over every street at least once, the CPP is referring to investigate how to cover every street and return to the post office under the least cost. A number of Scholars have researched in this field and proposed some new extensions of CPP.In recent years, people concern time-dependent property increasingly. Problems in time-dependent networks become more realistic than the classical problems. Time-Dependent Shortest Path Problem (TDSPP), Time-Dependent Travel Salesman Problem (TDTSP) and Time-Dependent Vehicle Routing Problem (TDVARP) have received in-depth researches. TSP and VRP are both Nod-Routing problem, but the important Edge-Routing problem Chinese Postman Problem (CPP) combining Time-Dependent network has not been researched in the world. What's more, the classical algorithms can't work in the time-dependent circumstance, so we propose the model of Time-Dependent Chinese Postman Problem (TDCPP). Due to the efficient algorithms for TDVRP, this paper researches high efficient algorithm for it. The paper has enriched time-dependent network theory.This paper summarizes some results of branches of Chinese Postman Problem. This paper also introduces the results of TDVRP in detail and Intelligent algorithms. Then, this paper introduces basic concepts and properties of time-dependent networks. By means of researching the properties of TDCPP, this paper also compares TDCPP with Static Chinese Postman Problem, and then, this paper proves TDCPP is NP-hard problem and gives a kind of time-dependent networks which can be solved by the classical algorithms of CPP. Finally, two layers SA/GA algorithm (simulated annealing/ genetic algorithm) is proposed, this approach is tested on some random generated data, the Computational results are analyzed by comparing with lower bound of the problem. The experiment shows that the algorithm is efficient.