Column Generation Approach for the Time Dependent Chinese Postman Problem
This paper studies the Chinese Postman Problem with Time Dependent Travel Times. This problem is motivated by hybrid system testing where the timing of each transition is crucial. We give a new formulation to the problem as a set covering problem with partial order, whose linear relaxation can be solved tractably by column generation. Feasible columns are added by solving the minimal successor (predecessor) circuit subproblems with genetic algorithms. Computational results on the medium-sized instances with random time dependent travel times are reported, which show that the gap associated with the upper bound and the relaxation bound obtained by the column generation algorithm is almost less than 5.98％.
Chinese Postman Problem Time Dependent Col- umn Generation Set Covering with partial order
Jinghao Sun Guozhen Tan Guangjian Hou Baocai Wang
School of Computer Science and Technology, Dalian University of Technology, Dalian, 116023, China
国际会议
昆明、丽江
英文
450-454
2011-04-15（万方平台首次上网日期，不代表论文的发表时间）