Hits:

Indexed by:会议论文

Date of Publication:2011-08-19

Included Journals:EI、Scopus

Page Number:955-960

Abstract: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.