点击次数：

论文类型：会议论文

发表时间：2011-04-15

收录刊物：EI、Scopus

页面范围：450-454

摘要：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.