编组站静态配流的约束传播和启发式回溯算法  

Constraint Propagation and Heuristics Backtracking Algorithm for Static Wagon-Flow Allocation at a Marshalling Station

作　　者：马亮[1] 郭进[1] 陈光伟 

机构地区：[1]西南交通大学信息科学与技术学院,四川成都610031 [2]铁道部信息技术中心,北京100860

出　　处：《西南交通大学学报》2014年第6期1116-1122,共7页Journal of Southwest Jiaotong University

基　　金：铁道部科技研究开发计划重点课题(2010X010-F);铁道部科技研究开发计划重大项目(2012X003-A)

摘　　要：为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.In order to improve the efficiency of stage planning, a hybrid algorithm was designed to solve the lexieographic multl-objective cumulative scheduling model of the static wagon-flow allocation problem at a marshalling station. The proposed algorithm is based on iteration method, constraint propagation technique and heuristic backtracking. The whole model is divided into three layers according to the lexicographical order of the multi-objective. The total priorities of the on-time outbound trains is maximized in the first sub-model, minimizing the total number of the inbound trains providing cars to each outbound trains is the objective in the second sub-model, while, the average dwell time of railcars in the station should be decreased as possible in the final sub-model. Firstly, each sub-model is simplified and the search space is reduced by constraint propagation algorithm. Then, the optimal solution is searched fast by the combined algorithm of heuristic backtracking and constraint propagation. In the lower sub-model, the optimal solution of the upper sub-model is considered as the initial solution, and the constraint is added to avoid degradation of the optimal value of the upper objective, so that the whole model is solved by the iteration algorithm. Experiment results from a marshalling station show that the total running time of the algorithm is less than 20 s, which meets the real-time requirements of scheduling in the field, and the algorithm can solve a better wagon- flow allocation solution compared with other algorithms.

关 键 词：编组站 静态配流 约束传播 启发式回溯 约束满足问题 

分 类 号：U292.16[交通运输工程—交通运输规划与管理]