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

A Hybrid Column Generation Approach for Solving Rolling Stock Assignment Optimization Model of Urban Rail Transit

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

An urban rail transit rolling stock assignment network with no fixed operational section is proposed,in which the nodes are the transport tasks for the rolling stock and anti depot nodes,and the arc connects the two transport task nodes or the transport task node with anti depot node.Urban rail transit rolling stock assignment mathematical model aims to minimize the total operation cost with the relevant requirements.A hybrid column generation algorithm is designed to solve the model.The algorithm combines the branch-and-price algorithm with the large scale neighborhood search algorithm.The large scale neighborhood search algorithm is adopted to update a newly acquired initial integer solution.The integer solution is implemented as the new columns into the column generation algorithm to avoid the degenerate problem.Meanwhile,the newly acquired integer solution can update the upper bound of the branch-and-price search tree.Therefore,a more powerful upper bound is used to the branch-and-price search tree to speed up the algorithm process.Numerical results show that our approach can solve large-scale rolling stock assignment problems,and result in more effective solutions.