Research On Cutting Plane And Ant Colony Algorithm For Rual Postman Problem With Time Dependent Travel Times

Chinese Postman problem is the arc routing problem and a classic problem in graph theory. As a variant of Chinese Postman problem, rural postal routes problem has been studied extensively. The problem in street sweeping, garbage collection, mail delivery route, school bus routes, the robot detects line route optimization and software test sequences.etc has important applications. So,it has attracted interest of many scholars.In recent years, with the intelligent transportation, hybrid systems and networking technology, testing of complex systems development, people's increasing emphasis on real-time system. However, the traditional Chinese Postman problems are studied in a static network, assuming that the weights on the network is static and unchanging, which often do not meet the actual situation. For example, changes in traffic conditions due to work, then the change in travel time will be followed. Therefore, time-dependent study of Chinese Postman problem becomes more urgent and significant. Chinese Postman Problem with time window(CPPTW), Chinese Postman Problem with time-dependent service cost (CPPTDC) and Chinese Postman Problem with time-dependent travel time (CPPTDT) are all problems in time-dependent networks.The first two have been studied before, but CPPTDT,because of the complexity of the problem, modeling difficulties, is studied by few people. Our laboratory examined CPPTDT before, but the problem of its variants rural postal routes have not been studied. Iin this paper we will focus on the problem of Rual Postman Problem with time-dependent travel time(RPPTDT).In this paper, the problem of traditional Chinese Postman and rural postal routes are summarized, Then set up an integer programming model:arc-the path model. Since large-scale integer programming problems is hard to solve, this paper designed a heuristic cutting plane algorithm.The experimental results show that we can get satisfactory the solution. Taking into account the cutting plane spenting a great time, we provide a meta-heuristic algorithms-the ant colony algorithm for solving the time-dependent rural postal problem. Ant colony algorithm can convergence to the optimal solution very well. Relative to the random initialization of pheromone, the use of linear programming solution of the linear relaxation initialize pheromone is more inclined to converge to the optimal solution.