张正坤 朱昌锋 马文虎

（兰州交通大学交通运输学院 兰州730070)

0 引 言

列车在正常情况下按图定计划运行，当列车受不确定因素干扰而偏离计划时，需要对列车秩序进行调整，其目的是控制列车晚点传播效应，使列车尽可能快地复序运行[1]。列车运行调整的关键是合理确定列车在各站的到发时间及其对运行区间的占用次序，从而有效疏解相邻列车间的冲突关系[2]。在此过程中，因列车运行调整是基于列车实时状态，故而对调整措施具有较强的时效性要求。相比于其他线路，单线铁路因上下行列车共用1套固定设备而使得冲突疏解变得复杂[3]。因此，单线铁路上的列车运行调整问题成为众多学者研究和关注的重点。

最小化列车晚点时间是列车运行调整的主要优化目标[4]。Sotskov等[5]和Gholami等[6]将列车运行调整抽象为一类特殊的、具有阻塞特性的生产调度问题，其数学模型具备NP-hard特性，求解比较困难。D'Ariano等[7]和Lamorgese等[8]通过图论分析了列车调整过程中的潜在冲突关系，构建了混合整数规划模型，并设计局部搜索算法和主从分解算法，但忽略了车站能力对列车运行调整的影响。为体现列车占用区间的时序性，Yang等[9]和Meng等[10]从时空网络角度建立列车运行调整的优化模型，但因时空网络难以刻画列车属性及其在技术站的作业类型，故而实用性略显不足。以上研究本质上属于列车运行调整的静态优化，其优点是通过建立数学模型，利用现有的求解软件或设计相应算法便可获得质量较高的调整计划[11-12]，但求解效率较为低下，难以满足列车运行调整的时效性需求。……