轨道列车时刻表问题研究综述

摘要

广泛的实践应用和复杂的计算挑战,使得轨道列车时刻表优化问题,多年来一直是交通运输及运筹管理学界的热点研究问题.作为轨道交通运营规划的一个子阶段,列车时刻表向上与线路规划(或开行方案)、向下与动车组调度融合,可以得到多个延伸的研究选题.在特定的时空网络中,列车时刻表设计就是为每个列车确定一条无冲突的运行路径,使基于用户的度量指标如乘客候车时间,或企业的度量指标如运营费用达到最优.对于没有列车越行和停站模式给定的情况,通过整数变量可以完整地刻画列车时刻表模型,但如果考虑列车越行或列车停站决策,则需要引入列车在车站出发顺序或停车决策的0-1变量.一般而言,列车时刻表问题的数学模型是一类典型的大规模、多目标、强耦合的NP完全问题.算法设计是列车时刻表问题最为重要和困难的部分.对于问题较简单或规模较小的情况,常用方法是对原有复杂问题进行适当简化和(或)对难处理表达式进行合理修改,然后使用先进的计算架构和商用优化软件求解更新后模型.当然,分支定界和动态规划这两类直接分解算法,是求解列车时刻表问题的重要方法.对于问题复杂和规模庞大的情况,以拉格朗日和列生成为代表的对偶分解算法,则是求解列车时刻表问题的最佳选择.未来,探讨列车时刻表与各种现实需要(如设施维修),以及时变票价和客票分配等因素之间的深度融合,是一个有价值的研究方向;其次,研究网络环境下列车时刻表问题,将是一个非常有意义的研究选题;最后,应进一步设计集成了问题特点与现代优化技术的各类求解算法,开发能够完全应用于实际运营的商用软件.