编组站静态配流的约束传播和启发式回溯算法
doi: 10.3969/j.issn.0258-2724.2014.06.027
Constraint Propagation and Heuristics Backtracking Algorithm for Static Wagon-Flow Allocation at a Marshalling Station
-
摘要: 为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.Abstract: In order to improve the efficiency of stage planning, a hybrid algorithm was designed to solve the lexicographic multi-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.
-
王慈光. 用表上作业法求解编组站配流问题的研究[J]. 铁道学报,2002,24(4): 1-5. WANG Ciguang. Study on wagon-flow allocating problem in a marshalling station by using calculating method on-table[J]. Journal of the China Railway Society, 2002, 24(4): 1-5. 王慈光. 编组站静态配流网络模型[J]. 交通运输工程与信息学报,2003,1(2): 67-71. WANG Ciguang. Network model of static wagon-flow allocation in a marshalling station[J]. Journal of Transporta- tion Engineering and Information, 2003, 1(2): 67-71. 景云,王慈光,王如义,等. 运用学习规则求解编组站静态配流问题的研究[J]. 铁道运输与经济,2010,32(1): 22-26. JING Yun, WANG Ciguang, WANG Ruyi, et al. Study on resolving static wagon-flow allocation by using learning rules[J]. Railway Transport and Economy, 2010, 32(1): 22-26. 薛锋,王慈光,罗建. 双向编组站静态配流的优化[J]. 西南交通大学学报,2008,43(2): 159-164. XUE Feng, WANG Ciguang, LUO Jian. Optimization for static wagon-flow allocation in bidirectional marshalling station[J]. Journal of Southwest Jiaotong University, 2008, 43(2): 159-164. 赵军,彭其渊. 单向编组站配流与调机运用综合问题[J] .铁道学报,2012,34(11): 1-9. ZHAO Jun, PENG Qiyuan. Integrated wagon-flow allocation and shunting locomotive scheduling problem at single-direction marshalling station[J]. Journal of the China Railway Society, 2012, 34(11): 1-9. 王世东,郑力,张智海,等. 编组站阶段计划自动编制的数学模型及算法[J]. 中国铁道科学,2008,29(2): 120-124. WANG Shidong, ZHENG Li, ZHANG Zhihai, et al. Mathematical model and algorithm for automatically programming the stage plan of marshalling station[J]. China Railway Science, 2008, 29(2): 120-124. HOOKER J N. Logic, optimization, and constraint programming[J]. Informs Journal on Computing, 2002, 14(4): 295-321. 纪昌明,段国圣,冯尚友.多目标动态规划分层解法与Pareto最优解[J]. 系统工程理论与实践,1995(6): 76-80. JI Changming, DUAN Guosheng, FENG Shangyou. The hierarchical optimization criteria and pareto solution of multiobjective dynamic programming[J]. Systems Engineering-Theory & Practice, 1995(6): 76-80. 王明慧. 字典序多目标多阶段决策问题的嘉量解法[J]. 西南交通大学学报,2005,40(3): 390-393. WANG Minghui. Application of jar-metric principle for solving lexicographic order multiobject and multistage decision problems[J]. Journal of Southwest Jiaotong University, 2005, 40(3): 390-393. OJHA A K, BISWAL K K. Lexicographic multi-objective geometric programming problems[J]. IJCSI International Journal of Computer Science Issues, 2009, 6(2): 20-24. 刘露. 基于约束传播技术的资源受限项目调度问题求解算法[D]. 沈阳:东北大学,2011: 10-30. ROSSI F, BEEK P V, WALSH T. Handbook of constraint programming[M]. Pisa: Elsevier, 2006: 27-78, 206-235, 541-580, 778-781. 刘士新,郭哲,唐加福. 具有优先关系的累积调度问题的约束传播算法[J]. 自动化学报,2010,36(4): 603-609. LIU Shixin, GUO Zhe, TANG Jiafu. Constraint propagation for cumulative scheduling problems with precedences[J]. Acta Automatica Sinica, 2010, 36(4): 603-609. 张居阳. 基于约束的现代调度系统研究[D]. 长春:吉林大学,2006. LHOMME O. Consistency techniques for numeric CSPs[M]. San Francisco: Morgan Kaufmann Publishers, 1998: 232-238.
点击查看大图
计量
- 文章访问数: 812
- HTML全文浏览量: 54
- PDF下载量: 401
- 被引次数: 0