高如虎，牛惠民

(兰州交通大学 交通运输学院，甘肃 兰州 730070)

在高速铁路(以下简称高铁)运输组织中，当现有列车服务难以满足突发增长的客流需求时，需要在原有运营列车时刻表的基础上，规划新增列车的时刻表。对于新增列车条件下的时刻表优化是“列车运行调整”问题，但实质也属于列车时刻表优化范畴。列车时刻表问题(Train Timetabling Problem, TTP)是轨道交通领域中的经典问题。列车时刻表问题涉及数量众多的车站和列车，模型中所含决策变量数目随问题规模呈指数式增长，属于典型的NP-hard问题，很难在多项式时间内找到一种有效算法对其精确求解。尤其对于不同速度等级列车共线运行的情况，还需要处理列车越行时间和位置选择问题，使得问题更加复杂。如何设计可靠有效的求解方法，始终是列车时刻表问题的主要挑战[1-2]。

构建整数规划模型并利用商业优化软件求解列车时刻表问题，是近年来兴起的一种方法。文献[3-5]构建列车时刻表的混合整数规划模型，并利用优化软件CPLEX求解。文献[6]以总的乘客等待时间最少为优化目标，研究了时变客流需求条件下列车时刻表的优化问题，建立了带有线性约束的非线性整数规划模型并利用通用优化软件GAMS求解模型。不同速度等级列车共线运行情况下，还需要处理列车的越行问题，该情形改变了列车的发车顺序。因此，模型中除了列车到发时刻变量外，还需要表示列车发车顺序的0-1变量，这使得决策变量和约束条件的数量急剧增大[7-8]。……