Graph transformation algorithm for the time dependent Chinese Postman Problem with Time Windows

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.