Application Of Column Generation Technology On The Time Dependent Chinese Postman Problem

Since the Chinese Postman Problem (CPP) was proposed, it has been studied in depth by many specialists and scholars. They not noly developed algorithms for solving the CPP, but also proposed some new extensions of CPP, such as MCPP,WCPP,RPP etc. The above researches all concerned static networks, that is to say, they considered the costs of travel time on each arc as constant. But in the real life the cost on each arc changes with time which is not constant and time dependent. Therefore, the traditional theory has been unable to meet the actual demand, So we need to make the study about CPP in the Time-Dependent Network.Comared with the static network, time-dependent Chinese Postman Problem(TDCPP) is more of profound theoretical and practical significance, it can be applied to many fields including Software real-time Testing,traffic,communication and so on. Yet because of the addition of time factor, the problem becomes considerably more difficult. Now there are some solutions but all have their limits,for example, they cann't solve the large-scale problems. For the above situations, this paper give a colunm generation algorithm for it, and enrich time-dependent network theories.This paper summarizes some results of CPP, TDCPP and column generation algorithms, Then, this paper introduces the basic concepts and the properties of time-dependent network, on these bases, giving the definition of TDCPP. Then this paper combines the property of CPP and TDCPP on the directed graph to give a integer programming formulation which let the path-circle as basic variable,but it has a lot of constraints and decision variable which is unfavorabloe to directly solve. Considering the advantage of Column Generation algorithm in solving huge linear progranmming, the author decided to choose column Generation algorithm to solve the path-circle model. According to the path-circle model, this paper bulid the restrict main problem, then generate the sub problem by D-W Decomposition Technique. Then On the basis of implementing three key problems in the column generation model(how to get the initial solution, how to solve the sub problem and how to get the integer solutions), designning a column generation algorithm to slove TDCPP. And in order to optimize algorithm, this paper introduces the column management pool into the algorithm. We then implement the algorithm and obtain the correct experimental results. By the results, we found that our algorithm is useful for the TDCPP.