点击次数：

论文类型：会议论文

发表时间：2011-08-19

收录刊物：EI、Scopus

页面范围：955-960

摘要：In this paper we deal with a generalization of the Chinese Postman Problem with Time Windows involving the added complexity of time dependent service times and travel times, which is motivated from hybrid system testing. In the literatures, several linear integer programs for this new problem have been studied intensively. However, there exists a large number B in the timing constraints, which always leads to a very weak linear relaxation. In order to avoid this drawback, this paper presents a graph transformation method with pseudo-polynomially bounded, through which the problem can be reformulated as a new 0/1 integer linear programming without any timing constraint. Computational results reported on 32 randomly generated instances show that medium-sized problems can be solved optimally by the graph transformation algorithm and CPLEX 12.0 within a reasonable time. ? 2011 IEEE.