Column Generation Algorithm For The Time Dependent Chinese Postman Problem

The Chinese Postman Problem is one of the classical problems in graph theory.It has received much research because of its wide range of applications, for example, garbage collection, milk or mail delivery, school bus transportation, parking meter collection, electric meter reading, electrical lines and gas mains inspection, etc.With the rapid development of computer networks, communication and Intelligent Transportation Systems (ITS), problems in time-dependent networks become more realistic than the classical problems. 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. CPPTW and CPPTDC have received much better research than CPPTDT because CPPTDT is very hard to formulate. However, in this paper, we consider CPPTDT.In this paper, we first exhibite the difference between the algorithms of traditional Chinese Postman Problems and Time Varing Chinese Postman Problems, and then, introduce the theory of Column Generation and its applications on solving the time varing routing problems. The main parts of this paper include that solving the Time Dependent Chinese Postman Problem (TDCPP) by using Integer linear programming and column generation algorithm. In order to formulate the TDCPP problem as an Integer linear problem, each feasible chinese tour can be seen as a sequence of circuits in the time dependent network.Therefore, we propose a integer linear programming for TDCPP problem with basic circuits as its decision variables, the number of which is proved to be bounded as m-n+1. Due to the huge scale of integer programming, we design a column generation algorithm to solve this integer programming. However, the methods proposed above is only able to solve the special instances of TDCPP problem with all circuits passing through the origin. To this end, we formulate the TDCPP as another integer linear programming with the level paths as the decision variables, which can solve all the instances of TDCPP problem without any limits. Finally we give a theoritically analysis for the upper bound of the integer programming, and the the correctness of the formulation is verified by a small example.