Time Varying Network Chinese Postman Problem:Integer Programming Formulations And Algorithms

In this paper, a new kind of time-varying networks optimization problems called Chinese postman problems with time-varying networks are studied intensively for the first time. From the point of theoretical view, it can enrich the theory of time-varying networks optimization which will be further studied including computational complexity, theorems of problem properties, mathematical models, exact and heuristic algorithms. And the theory of time-varying Chinese postman problem includes three parts as follows.(1) Analyze the properties of the new problem including:â‘ Computational complexity: this paper proves that the time dependent network Chinese postman problem is NP-hard even if it is defined on an Eulerian and FIFO network.â‘¡Availability of the classical algorithm:The two-stage strategy and arc routing transformation, which are very successful in solving conven-tional CPP problems, can not be used to solve the time dependent network Chinese postman problem.â‘¢This paper proves two properties of the optimal time dependent network Chinese postman tour, which can be used in designing the algorithms optimally.(2) Found the integer programming theory of the time dependent network Chinese postman problem:â‘ three kinds of linear integer programming formulation are proposed for the time dependent network Chinese (rural) postman problem including:circuit formulation, alternative circuit formulation, arc formulation and arc-path formulation.â‘¡The polyhedral theory of the time dependent network Chinese postman problem is investigated, and the facet defined and valid inequalities are derived.(3) Proposed three kinds of algorithms for the time dependent network Chinese postman problem:â‘ The branch and bound algorithm and the dynamic programming algorithm are designed based on the FIFO property to solve the time dependent network Chinese postman problem optimally.â‘¡) Based on the circuit formulation and the arc-path formulation, the cutting plane algorithms are proposed to obtain the lower bound of the time dependent network Chinese (rural) postman problem.â‘¢Finally, a general formulation method is exhibited for all the three time varying Chinese postman problem including Chinese postman problem with time windows, Chinese postman problem with time dependent service costs and the Chinese postman problem with time dependent travel times based the theory of timed automata, and solve all these problem by the method of verification based on the timed automata model.