Journal: 中国铁道科学

Key Words: 城市轨道交通; 列生成算法; 大规模邻域搜索算法; 车底运用计划;

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

Co-author: 宋瑞,何世伟,李晋

First Author: 何必胜

Indexed by: Journal articles

Discipline: Engineering

Document Type: J

Volume: 35

Issue: 1

Page Number: 122-129

Translation or Not: no

Date of Publication: 2014-01-15