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

摘要

为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.