铁路编组站动态配流的约束传播和多点构建性搜索的混合算法  

Hybrid Algorithm of Constraint Propagation and Multi-point Constructive Search for the Dynamic Wagon-flow Allocation Problem at a Railway Marshalling Station

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

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

出　　处：《信息与控制》2015年第2期230-237,共8页Information and Control

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

摘　　要：为了提高动态配流模型的通用性和稳定性,基于约束程序累积调度和字典序多目标优化,以作业之间实施逻辑和优先级关系、班计划和列车编组计划要求、资源容量限制等为约束,按照配流成功的出发列车优先级总和最大、车辆平均中停时最小和资源利用率最高3个目标的优先级,建立适应于不同解体方式的动态配流字典序多目标累积调度的3层模型.为提高算法效率,设计了约束传播和多点构建性搜索混合的带初始解迭代算法,每层先通过约束传播算法化简模型,再通过带约束传播的多点构建性搜索算法快速求解,以决策出优化的作业排程和配流方案.实验表明,模型扩展性更强、更稳定、更符合现场实际;算法效率高,能够满足现场对计划编制和调整的实施性需求.To improve the versatility and stability of the dynamic wagon-flow allocation model,the dynamic wagon-flow allocation lexicographic multi-objective cumulative scheduling model is set up to maximize the sum of priority of the departure trains,minimize the average residence time of the cars,and maximize the resource utilization,based on the theory of constraint programming cumulative scheduling and lexicographic multi-objective optimization.In this model,the precedence and logical relationship among traffic jobs,the demands of the train shift plan and the train formation plan,and the capacity limit of the resources are all taken into account as constraints.The model is then be adapted for different disassembly modes and is divided into three sub-layers,according to the lexicographic or-der of the three objectives.Then,the optimized schemes of job scheduling and wagon-flow allocation are received by solving the model iteratively,using the hybrid algorithm of constraint propagation and multi-point constructive search.In each sub-layer,the search space is initially reduced by constraint propagation and then the solution is a-chieved by a multi-point constructive search algorithm with constraint propagation.This new model′s instance vali-dation results indicated that this algorithm is more scalable,realistic,and stable.Furthermore,this algorithm is proved to be very efficient,with solve times that are potentially appropriate for real-time applications.

关 键 词：编组站 动态配流 约束程序 约束传播 多点构建性搜索 

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