Hits:

Indexed by:会议论文

Date of Publication:2011-04-15

Included Journals:EI、Scopus

Page Number:450-454

Abstract: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 subproblems 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%. ? 2011 IEEE.