论文成果
Graph Transformation Method for Time Dependent Rural Postman Problem with Time Windows
- 点击次数：
- 论文类型：期刊论文
- 发表时间：2012-12-01
- 发表刊物：INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL
- 收录刊物：SCIE
- 文献类型：J
- 卷号：15
- 期号：12A,SI
- 页面范围：5279-5286
- ISSN号：1343-4500
- 关键字：Time Dependent; Time Window; Graph Transformation; Generalized Postman
Problem; 0/1 Linear Program
- 摘要：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.
