毛万华，陈亚茹

（1.中国铁路兰州局集团有限公司 调度所，甘肃 兰州 730000；2.中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081）

0 引言

列车运行图是用以表示列车在区间运行及在车站到发或通过时刻的技术文件，是全路组织列车运行的基础[1]。在实际运营过程中，由于突发事件或节假日客流激增，都需要组织临时加开列车，新增列车运行线可以应用于日常计划编制及列车运行图调整过程中。在新增列车运行线时，需要综合考虑原始列车及新增列车对运行图性能的影响，应在对原始列车影响程度最小的情况下，尽可能从需要新增的列车运行线备选集中加入更多的运行线，以满足客流出行需求。

目前，关于列车运行图新增列车运行线的调整问题研究相对较多。Burdett等[2]提出三阶段加线过程，通过固定或适当移动已铺画的列车运行线实现加线。Tan等[3]将列车加线问题分解为2个子问题，分别是列车重排序问题和列车顺序固定情况下的插线问题，并利用分支定界算法，设计迭代重排序策略求解。徐涵等[4]在周期列车运行图加线过程中，考虑灵活接续约束，实现列车接续与列车运行图的协同优化。江峰等[5]基于时空网络构建模型，考虑列车始发时刻和初始利润，目标函数为运行线总利润最大，设计基于拉格朗日松弛的启发式算法求解，进一步提高算法求解效率。刘敏[6]针对部分客运专线增开本线列车及调整列车开行方案，实现运力资源与需求的合理匹配，进一步优化运输资源配置。……