Column Generation Approach for the Time Dependent Chinese Postman Problem

摘要

This paper studies the Chinese Postman Problem with Time Dependent Travel Times. This problem is motivated by hybrid system testing where the ``timing'' of each transition is crucial. We give a new formulation to the problem as a set covering problem with partial order, whose linear relaxation can be solved tractably by column generation. Feasible columns are added by solving the minimal successor(predecessor) circuit sub problems with genetic algorithms. Computational results on the medium-sized instances with random time dependent travel times are reported, which show that the gap associated with the upper bound and the relaxation bound obtained by the column generation algorithm is almost less than 5.98%.