Research On Cutting Plane Algorithm For Directed Chinese Postman Problem With Time Dependent Travel Times

The Chinese Postman Problem (CPP) is a well-known problem in graphic theory as well as combination optimization and planning and management, which is significant in discipline of transportation, communication system, robot exploration, analyzing interactive system, web site usability and software testing. However, with the rapid development of communication and distributed processing, hybrid system testing and intelligent transportation system are coming into consideration of timing, that is, the cost of each arc on the network varies with time. Although those efficient solution algorithms which are proved to be very successful in the traditional CPP problems, they are no longer available for CPP defined in time dependent network. In the traditional CPP models, the cost of each arc is invariant and usually given beforehand, but it may be varying in the practical problems, for instance, the running time of a car cross a city block would be different according to the temporal traffic flow density caused by the accident or weather. Therefore, research on new model and associated high efficient algorithm for the Chinese Postman Problem in time dependent networks becomes an important practical problem to be solved urgently, which is also the goal of this paper.However, the new problem becomes more difficult to handle when the timing is considered. It's unwise to solve the directed CPP with time dependent travel times (TDDCPP) directly since it has been proved to be NP-Hard. From the perspective of mathematical programming optimal method, this paper first proposes an integer linear programming model for TDDCPP based on circuit covering theory. The model is linearized according to the step travel time function and the upper bound of model is also analyzed. Then, a model-based heuristic cutting plane algorithm is presented. Moreover, this paper presents several strong valid inequalities according to the step travel time function. Finally, the effectiveness of the new algorithm is estimated by computational results.The heuristic cutting plane algorithm proposed in this paper is a standard cutting plane algorithm with a new kind of heuristic embedded. Computational results show that this algorithm is not optimal but can solve 67% instance to optimality for small TDDCPP problems and the difference between the upper bound and lower bound of problem cannot exceed 20% averagely for middle TDDCPP problem. Therefore, this heuristic cutting plane algorithm which solves the TDDCPP fast with high quality solution expands the application fields of both the cutting plane optimal algorithm and heuristic. Moreover, the proposed TDDCPP model provides a wholly new method to effectively solve other CPP variants in time dependent networks.