城市轨道交通车底运用计划编制优化模型求解的混合列生成算法

摘要

以车底需要担当的运输任务和虚拟车场为节点,以2个运输任务间的衔接以及运输任务与虚拟车场间的衔接关系为弧,构建不固定区段运营的城市轨道交通车底运用网络图.在满足相关约束条件下,以车底总运营费用最低为目标,建立城市轨道交通车底运用计划编制优化模型,并设计模型求解的混合列生成算法.该算法的原理是:在分支定价算法的基础上,再采用大规模邻域搜索算法,以当前最优整数解为初始解进行邻域搜索得到新的解,将此新解作为新增列加入到列生成算法中,避免出现退化问题;同时,根据此新解对搜索树上界进行更新,运用更有效的上界进行减枝,从而提升模型求解的效率.应用实例证明,提出的混合列生成算法在求解大规模的车底运用计划编制问题时,可以获得较高质量的求解结果.