Hits:

Indexed by:期刊论文

Date of Publication:2012-12-01

Journal:INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL

Included Journals:SCIE

Volume:15

Issue:12A,SI

Page Number:5279-5286

ISSN No.:1343-4500

Key Words:Time Dependent; Time Window; Graph Transformation; Generalized Postman Problem; 0/1 Linear Program

Abstract:In this paper we deal with a generalization of the Rural 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 sets of 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.