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

牛惠民

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

0 引言

努力向旅客提供高质量的空间位移服务，并以列车时刻表的形式向社会公布，是轨道交通运输组织的核心。在轨道交通内部，列车时刻表的时空图示形式又称为列车运行图，它规定了列车占用区间的次序，以及在每一个车站的到达、出发和通过时刻。列车运行图是轨道运营企业最重要的技术文件，是协调不同部门、环节进行运输生产活动的基础，以及轨道线路能力查定的依据[1-3]。对于社会而言，列车时刻表则是连接运营商和出行者的桥梁，以及乘客安排出行活动的依据。

其他公共交通方式，如城市公交、民用航空、客运轮渡、城际道路客运等，都涉及时刻表问题。当公共交通系统的基础设施(如线路、车站、码头、航站等)、或运输装备(牵引、制动、通讯、容量等)产生了变化、或客流需求(大小、时空分布)出现了较大波动时，都需要根据变化的运营环境或客流需求，重新设计新的运营时刻表。相比较而言，由于轨道交通特有的封闭性和排他性约束，使得列车时刻表问题更加复杂。轨道列车时刻表的设计，是一类具有广泛应用背景的调度优化问题。

列车时刻表问题(Train Timetabling Problem)，最大的困难是如何处理不同列车占用轨道资源引发的时空冲突，这种时空冲突与列车运行追踪、越行、交汇耦合在一起，构成了复杂的约束条件。该类问题的优化，是在特定的时空网络中，为每个列车确定一条合理的运行路径，使基于用户的度量指标(如乘客候车时间)、或企业的度量指标(如运营费用)等实现最优，并满足严格的运行安全要求。轨道列车时刻表的优化，数学上是典型的大规模、多目标、强耦合的整数或0-1规划问题，其中加入需求因素并嵌入旅客行为，将使问题变得异常复杂。根据不同的运营环境和实践要求，构建列车时刻表合理的数学模型、设计有效可靠的求解算法，是一类非常具有挑战性的科学难题。

广泛的应用场景和复杂的计算挑战，使得轨道列车时刻表问题，多年来一直是国际交通运输及运筹管理学界的热点研究问题[4-10]。特别值得一提的是，该问题具有表述简单明确、不需要太多的专门知识；包容性强、可以融合多个子问题，如列车停站、动车组调度、客流控制等；数学模型是典型的大规模NP问题，可以结合问题背景，设计求解模型的多种启发式方法。正是由于这些原因，在一些著名的国际交通运输类期刊上，如Transportation Research Part B、Part C、Transportation Science 等，以及运筹管理类期刊，如Operations Research、European Journal of Operational Research等，经常可以见到研究列车时刻表问题的论文。

1 研究问题

1.1 列车时刻表问题

按照荷兰学者Goossens等[11]的观点，列车时刻表设计是整个轨道交通运营规划的一个子问题，向上是线路规划问题(Line Planning Problem)，向下则是动车组调度问题(Rolling Stock Scheduling Problem)。

单纯的列车时刻表问题，是在一条轨道交通线路或走廊上，确定所有列车在每一个车站的到达、出发和通过时刻，也称为基于线路的列车时刻表(Line-Based Train Timetable)。在直角坐标平面内，以时间为横轴、空间为纵轴，可以组成二维时空平面。在时空平面中，按照一定的比例关系，将列车运行轨迹用若干条线段连接起来，就可得到相应的列车运行线。对于所考虑的轨道线路，全体列车运行线的总体，称为该线路的列车运行图。

需要特别指出的是，在研究轨道列车时刻表及相关问题时，为了直观地展示所研究的内容，通常会画出列车运行图的简化形式。其中仍然以时间和空间为维度，但不必硬性规定横轴与纵轴的具体所指(时间、空间)；最重要的是，不深究各类对象的准确坐标，而重点关注它们之间的时空逻辑关系，如两个节点之间相对的左右、上下位置，这样得到的列车运行时空图示，称为列车运行时空网络(Space-Time Network)。

线路规划问题，就是具体确定列车运行区段、种类、停站方案、时段发车频率、编组长度等，这些内容大部分和旅客需求相关。换言之，线路规划是根据客流需求特征，确定的列车轮廓运行计划，体现了客流需求对列车服务的基本诉求。在随后的列车时刻表阶段，则把线路规划中的内容作为给定的输入，使待求解问题在相对简单的环境下进行。在我国学术和企业界，线路规划常用另一个含义基本相同的概念“列车开行方案”所代替。

动车组调度问题，是在已经设计好的列车时刻表上，为每条列车运行线(或称为任务)指派一个动车组(或车底)，要求每个任务有且只有一个动车组来完成，该问题也称为动车组运用问题或车底交路问题。动车组运用所产生的费用，是轨道交通运营阶段所耗费的主要支出。因此，当所研究问题涉及企业运营成本时，则一般需要考虑动车组使用情况。通过在时空网络上进行适当的变换，动车组调度问题等价于多车场车辆调度问题(Multiple-Depot Vehicle Scheduling Problem)。

在列车时刻表问题中，通过把线路规划中的某些内容松弛为决策变量，或者在构模阶段直接考虑客流需求，可以生成更高质量的列车服务产品；此外，也可以在列车时刻表优化阶段，同步考虑动车组调度问题，以获得运营成本更低的方案。目前列车时刻表领域的研究选题，大部分都是这样融合的结果。

1.2 新增列车运行线问题

这个问题来自于现实。由于旅客需求发生了明显变化，或线路基础设施如信号联锁系统进行了改造，既有的列车时刻表不再满足新环境的要求，需要在现有的列车运行图中，增加新的列车运行线，并对已有的运行线进行同步调整。在已有的运行图中插入新的列车运行线，这一思想在我国有着广泛的应用。时至今日，我国客货共线的列车运行图，都是先编制旅客列车运行图，然后插入尽可能多的货物列车运行线。然而，该问题在理论研究层面，却是欧洲学者的工作更有系统性，其中意大利学者的研究成果最有影响。

新增列车运行线问题，包含新列车运行线插入和既有列车运行线调整，两部分内容关联在一起，使得问题十分复杂。博洛尼亚大学Caprara 教授等[8]针对一条铁路走廊，在固定列车停站和越行模式、允许部分列车调整到发时刻及停站时间的条件下，构建了线性整数规划模型，用以解决新增列车运行线的问题。随后，Caprara等[12]进一步考虑了信号系统、车站能力、运营维修等因素对该问题的影响，开发了相应的计算机软件系统，在意大利铁路(RFI)的运能分配和时刻表编制中得到了广泛应用。2009年，昆士兰理工大学Burdett 等[13]将新增列车运行线问题刻画为一个带有时间窗约束的车间作业调度(Job-shop Scheduling)问题，以保证即有和新增运行线的有效融合，并在特制的分离图上运用元启发式算法求解模型。2010年，博洛尼亚大学Cacchiani 等[14]考虑了在旅客列车时刻表中插入货物列车运行线的问题，其中旅客列车运行线固定，目标是优化货物列车时刻表和停站方案，模型对每个货物列车预先指定理想时刻表，然后在迭代过程中不断修改调整。最近，Jiang等[15]以我国京沪高铁为背景，根据客流需求的特征，研究了如何在现有列车运行图中插入新的列车运行线，特别考虑了优化过程中允许部分列车增加停站、取消停站、延长停站时间等问题。

1.3 列车实时调度问题

列车实时调度，是指当前的列车运行受到非正常或随机干扰后，计划的列车时刻表不再可行，需要对部分或全部列车的运行计划进行实时调整，以获得新的列车运行方案。从本质上讲，列车实时调度就是根据变化的运营环境，重新设计或修改一个新的列车时刻表。研究该问题，可以将原有的计划列车时刻表作为理想时刻表，并将当前与理想时刻表之间的偏差最小作为优化目标。长期以来，轨道列车实时调度调整，始终是本领域一个热门研究选题，引起了众多学者的关注。

列车运行必须受限于当前车站、线路的状态，是研究实时调度问题的基本要求，荷兰代尔夫特理工大学Corman等[16]针对时空网络中存在的瓶颈路径，提出了基于“绿波”实时控制策略的替代图模型，采用分支定界算法进行求解，该方法在运营区段稍短、列车速度差较小、车站能力充足条件下具有很强的适用性。Lusby等[17]以最小化现实与计划之间的列车运行偏离为目标，将枢纽站列车实时调度描述为集合覆盖问题。2011年，孟令云和周学松[18]以单线铁路为背景，在列车运行时间及干扰持续时间不确定的情况下，基于不同的干扰场景建立随机优化模型，采用滚动时域算法求解列车实时调度问题。挪威学者Lamorgese等[19]把列车调度调整问题分解为线路列车运行调整及车站列车运行调整两个子问题，前者在保证列车不同时占用不兼容线路的前提下，最小化与计划列车时刻表之间的偏差；后者优化列车在车站的路径和到发时刻，建立混合整数规划模型，利用近似Benders 方法进行求解，所研发的列车时刻表优化系统于2014年在挪威Jærbane铁路线上开始应用。

1.4 列车时刻表和停站协同优化

在列车时刻表问题中融入线路规划的某些内容，可以产生许多延伸问题，最著名的是列车时刻表与停站协同优化问题。表面上看，列车停站应嵌套于时刻表问题中，因为根据列车在一个站的到达和出发时刻，就可以决定列车是否在该站停车。但从分层规划的视角看，列车停站属于上层的线路规划问题，而在单纯的时刻表问题中，总是假设列车停站模式已经给定。数学上，如需在时刻表问题中考虑列车停站，则在构模阶段，由于受列车最小停站时间的约束，必须设置新的0-1停站变量，才能构建时刻表和停站的协同优化模型。

北京交通大学杨立兴等[20]针对一条高速铁路走廊，把列车停站决策作为约束条件嵌入到时刻表问题中，以总的列车停站时间和延误时间最小为目标函数，构建了时刻表和停站协同优化的多目标线性整数规划模型，并运用CPLEX 求解模型。2017年，法国Altazin等[21]研究了城市轨道交通列车调整问题，其中嵌入了列车停站选择变量，在考虑动车组约束条件下，通过最小化系统恢复时间和乘客等待时间，构建了线性整数规划模型。商攀等[22]在一条超拥挤的地铁线路上，运用多维时空网络建模方法，研究了基于乘客候车公平的列车停站优化问题。需要特别指出的是，在列车时刻表和停站协同优化中，只有直接或间接考虑了客流需求，才有可能得出有价值的研究成果。

1.5 列车时刻表和动车组调度协同优化

列车时刻表优化目的，主要在于提高旅客服务质量，而最小化运营成本则是动车组调度的首要目标，将两者结合起来寻找服务与成本之间最佳妥协，是该领域多年来另一个热门研究选题。2014年，荷兰鹿特丹大学Kroon 等[23]在构建周期化列车时刻表PESP(Periodic Event Scheduling Problem)模型时，考虑了动车组与乘客之间的柔性接续问题，即预先不指定两个列车之间的链接关系，而是通过求解所构建的数学模型，得到期望的列车时刻表和动车组周转方案，他们开发的列车运行图自动编制DONS(Designer Of Network Schedules)系统，成功应用于荷兰铁路运营管理决策。2018年，丹麦理工大学Fonseca等[24]为了方便乘客在不同轨道线路上的换乘，研究了列车时刻表和动车组调度的协同优化，以最小化旅客换乘费用和企业运营成本为目标函数，构建了双目标混合整数规划模型，通过调整列车出发时间和延后列车停站时间，设计了求解模型的元启发式算法。荷兰埃因霍芬理工大学Veelenturf等[25]考虑了列车及动车组、乘务组实时调度协同优化问题，在考虑动车组能力约束的条件下，以最小化取消和延误列车数量为目标，构建线性整数规划模型。

1.6 面向需求列车时刻表优化

实际上，客流需求是列车时刻表设计最重要的考虑因素。从本质上讲，尽可能实现客流需求与列车运行线时空分布的最佳匹配，使列车服务的提供者和使用者共同受益，是列车时刻表优化的终极目标。然而，客流需求具有明显的连续与时变特点，而列车运行线则有离散与稳定属性，将两者有效地耦合为一个整体，确实是一件非常艰巨的任务。早期列车时刻表问题的研究，为了简化模型和求解，构模阶段不直接使用客流需求数据，而将重点放在如何处理股道占用冲突和列车运行安全上，相应的问题常称为面向供给的列车时刻表(Supply-Oriented Train Timetable)优化。

值得注意的是，许多研究列车时刻表问题的文献，尽管没有直接使用客流需求，但通过在上层线路规划中设置相关参数，间接地考虑了客流需求。如列车在始发站的出发时间范围、理想出发时刻，以及时段内开行的列车数、车站最少停站列车数等，基本上都是客流需求影响的结果。使用这些参数，就是在列车时刻表问题中间接地考虑了客流需求。在列车时刻表问题中，直接使用时变的OD需求，是该领域近年来的研究热点。根据统计时间单位选择的不同，可以生成不同的OD客流需求。在列车时刻表问题中，最常用的是基于小时(Hour-Dependent)和基于分钟(Minute-Dependent)的OD需求。

2013年，Niu 和周学松[26]研究了时变和超拥挤条件下城市轨道列车时刻表的优化问题，从理论上揭示了轨道列车与乘客的耦合关系，建立了动车组数量给定条件下面向需求列车时刻表非线性整数规划模型。加拿大蒙特利尔大学Barrena等[27]对于时变需求下的列车时刻表问题，提出了两种非线性规划模型，目的是最小化每个时段旅客的平均等待时间，通过反复删除或添加列车运行线，建立了基于自适应邻域搜索的快速迭代算法。Hassannayebi等[28]在列车能力和股道资源约束下，以一条城市轨道交通线路为背景，以乘客的平均等待时间最小为目标函数，构建基于路径变量的非线性整数规划模型，设计了求解模型的拉格朗日松弛算法，得到了期望的列车时刻表。2018年，石俊刚等[29]针对超拥挤的城市轨道交通系统，研究时变需求环境下列车时刻表和客流控制的协同优化问题，目标函数为最小化乘客在车站的候车时间，最后计算结果在得到最优列车时刻表的同时，还给出了避免站台拥挤的客流控制策略。

2 建模方法

2.1 决策变量

合理设置问题的决策变量，是正确构建列车时刻表数学模型的关键。在研究列车时刻表问题时，现有文献通常将时间轴按1 min(0.5 min或更小)进行等间隔划分，并假定系统中所有活动都发生在这些整数分割点上。基于这一事实，通过引入整数变量表示列车在车站的到达和出发时间，可以完整地刻画列车时刻表模型，但这种方法仅适用于没有列车越行的城市轨道交通或短距离城际铁路。如果考虑列车越行，则需要设置用以描述列车在车站出发顺序的0-1变量，才能正确地构建模型。如在Liu等[30]、Shafia 等[31]、许红等[62]构建的列车时刻表模型中，均使用了表示列车出发顺序的逻辑变量。当然，如果在列车时刻表问题考虑列车停站优化，则需要设置列车在车站是否停站的0-1 决策变量，如Yang等[20]、Altazin等[21]研究文献中均设置了这样的逻辑变量。

利用0、1 组成的变量序列，可以表示离散、时变的事件状态，其中在事件未发生前的时间点变量取值为0(或1)、而在事件发生及以后的时间点取值为1(或0)，这样的变量序列称为累积0-1 变量。运用累积0-1 变量，可以刻画许多复杂的时变系统。2013年，Niu和周学松[26]用累积0-1变量的方法刻画面向需求的列车时刻表问题，此后又有多篇文献(Meng 等[32]，Shi 等[33])用该方法构建轨道列车调度问题。需要特别指出的是，当使用商用优化软件(如CPLEX)求解0-1 整数规划模型时，如果模型中0-1变量的数目过多，将严重降低算法求解效率。

如上文所述，轨道列车运行线可以视为时空网络中的列车运行路径。以此为基础，通过使用0-1逻辑变量，可以构建基于路径的列车时刻表模型。通常有两种变量设置方法：一种是直接设置0-1 路径变量，如Cacchiani 等[34]、Fischetti[35]等研究文献，均定义了0-1 路径变量；另一种是不直接使用路径变量，而用0-1 路段变量间接表示时空网络中路径的选择结果，如Caprara 等[8,12]、Cacchiani 等[14]、江峰等[60]均利用了0-1 路段变量，构建了相应的列车时刻表模型。但不管是哪一种设置，后续使用算法都不直接求解所构建的0-1 规划问题，而是选择对偶分解技术，将其转化为多列车最短路径问题来求解。

2.2 约束条件

轨道列车时刻表问题，需要考虑多种复杂的约束条件，以保证列车运行安全及不同要素间的合理耦合等，主要包括：描述单列车车站到达和出发时刻、车站停留时间、区间运行时间的关联方程；反映多列车车站出发、到达间隔时间约束，以及列车越行耦合约束；基于车站股道占用、列车载客人数的能力约束。面向需求的列车时刻表问题，还要考虑客流需求和列车之间的关联匹配约束。一般而言，如果在列车时刻表问题中嵌入了其他问题(如列车停站)，都需要考虑不同变量间的关联约束。

为顺利求解列车时刻表这类复杂的离散优化问题，约束条件中还通常包括缩小列车活动空间的限制约束，如列车在始发站出发时间窗约束等。必须承认的是，缩小列车的活动范围是一种无奈选择，如何使这类约束设置既相对合理，又不影响随后的模型求解，是一件非常有意义的工作，高如虎和Niu[36]对此做了新的尝试。

2.3 优化目标

轨道列车时刻表设计，可以从运营者和乘客两个角度设置优化目标。从运营者角度来考虑，总是希望成本及消耗性指标最小，或列车运行尽可能接近某种理想的方案，具体的目标函数包括，基于列车走行时间或动车组运用的费用成本最小(Zhou等[47,54])，基于列车运行和停站的能源消耗最少(Huang等[37]，Yin等[38-39])，现实与理想列车时刻表之间的偏离最小(Burdett等[13]，Caprara等[8,12])。从乘客角度来考虑，优化目标包括乘客在车站等候时间最小(Niu等[26]，Barrena等[27]，李得伟等[59])、车内拥挤费用最少(Niu 等[50])，以及乘客的旅行时间最小(Sparing 等[40]，田小鹏和Niu[10]，廖正文等[61]，朱宇婷等[63])等。

基于以上考虑，可以构建列车时刻表问题的数学模型。迄今为止，这些模型均为线性整数或0-1规划问题。由于某些特殊原因，模型中有时会出现非线性表达式，利用通常的数学转换，可得到等价的线性模型，如石俊刚等[29]就采用这种方法处理模型中的非线性项。特别注意的是，如果在列车时刻表问题中考虑了时变的OD需求，就会导致目标函数中出现2次项(Niu等[46])。

3 求解算法

列车时刻表问题优化具有明确的应用背景，数学模型是大规模的NP 问题，任何无实质性数值测算的理论研究，科学意义都非常有限。学术界的基本共识是，算法设计是列车时刻表问题最为重要和困难的部分。以下4类算法，是目前求解列车时刻表问题文献中最常用的方法。

3.1 智能搜索方法

由于列车时刻表问题固有的离散性，运用智能搜索方法，如遗传算法(GA)等，就成为解决此类问题的首选，特别是对于不考虑越行情况的列车时刻表问题，智能算法的求解效率非常高。

1997年，德国学者Nachtigall 等[41]在研究周期性列车时刻表时，运用基于模糊逻辑的复合遗传算法求解所构建的双目标模型。Robenek等[42]提出面向用户的列车时刻表，新时刻表继承了周期运行图的规则性和非周期运行图的灵活性，用模拟退火算法求解问题，算法的核心思想是在保持乘客满意度最大的条件下，逐渐消除多个列车之间可能的时空冲突。2017年，Huang等[37]考虑了乘客旅行时间和列车运行中能源消耗，构建了列车时刻表优化的多目标规划模型，设计了禁忌搜索算法求解模型。2019年，Nitisiri等[43]以最小化乘客等待时间和列车运营成本为目标，构建了非越行环境下列车调度的双目标整数规划模型，提出了求解模型的并行多目标遗传算法，其中使用了混合抽样策略和基于学习的变异操作。

对于包含有越行情况的列车时刻表问题，由于不同变量之间的强耦合特征，使得智能搜索算法的求解效率明显降低。此外，智能算法有一个难以克服的缺陷，就是不能准确地度量当前解与最优解的偏离程度。需要指出的是，对于确实没有更好方法的列车时刻表问题，选择智能算法仍然不失为一个明智之举。

3.2 模型修改方法

基于模型修改的启发式方法，始终是求解列车时刻表问题最重要的方法。这类算法的核心是，对原始模型(或相应架构)进行适当修改或简化，然后使用商用优化求解软件(如GAMS 等)并结合其他优化技术，直接求解更新后的模型。

蒙特利尔大学Barrena 等[44]在求解列车时刻表问题时，通过重新定义一组客流变量，将非线性的乘客等待时间转化为线性表达式，得到了与原问题等价的线性整数规划模型，然后利用CPLEX 设计了求解模型的启发式算法。王义惠等[45]在研究地铁列车实时调度问题时，针对模型中存在非光滑、非凸函数的事实，通过修改模型设计了基于梯度的2 次规划序列迭代求解算法。2016年，杨立兴等[20]在研究列车时刻表和停站协同优化问题时，通过引入列车出发顺序的0-1 变量，来刻画列车安全间隔及列车越行约束，通过线性加权及约束修改的方法得到了单目标混合整数规划模型，最后利用CPLEX优化软件求解模型。

列车时刻表问题的极端复杂性，对求解算法提出了更高要求，任何在算法方面的改进尝试都是一件非常有意义的工作。2017年，荷兰代尔夫理工大学Sparing 等[40]针对周期性列车时刻表设计问题，提出了一种问题导向的预处理技术用以缩减解的搜索空间，结合CPLEX 求解器设计了一种启发式的迭代求解策略。对于列车实时调度问题，Fischetti等[35]提出了对约束条件的定界策略和对决策变量的压缩策略，以获得更加紧凑缩减的解空间，然后利用CPLEX 求解修改后的混合整数规划模型。Niu 等[46]对于面向需求的列车时刻表问题，根据基于分钟和小时的客流需求，分别构建了问题的2 次和拟2 次整数规划模型，针对不同情形引入了新的变量，修改构建了数学上严格、计算上易处理的非线性混合整数规划模型，提出了基于优化软件GMS的求解方法。

3.3 直接分解方法

列车时刻表问题具有明显的离散选择特征，数学上可以表示为整数规划模型。从算法设计的角度讲，利用一些已有的分解方法，直接将这类复杂问题分解为容易求解的多个子问题，然后逐步求解，最后得到期望的最优解。分支定界和动态规划算法，是该领域两类最常见的分解方法。

分支定界(Branch and Bound)是求解整数规划问题的常用算法，该方法是一种迭代搜索方法，主要思路是把可行解空间反复地分割为越来越小的子集，称为分支；对每个子集内的解集计算一个目标下界(最小值问题)，称为定界；每次分枝后，凡是界限超出已知可行解目标值的那些子集不再进一步分枝，从而缩小搜索范围，称为剪枝；反复实施上述过程直至找出最优解。分支定界算法由于其良好的分解能力和收敛特性，在列车时刻表问题研究中广泛使用。2005年，亚利桑那州立大学周学松教授[47]在研究多级列车共线运行下列车时刻表问题时，构建了高等级列车出发时间与理想出发时刻偏离最小，以及所有列车旅行时间最少的双目标模型；根据两种优先权规则，将第2 个目标对应的模型分解为单列车时刻表问题，并将其转化为带有资源限制的项目调度问题；提出带有有效支配准则的分支定界算法，以获得原多目标问题的帕累托解；为了提高算法效率及获得具有代表性的非支配解集，提出带有效用评价准则的束搜索策略。

代尔夫特理工大学D'Ariano 等[48]将列车实时调度抽象为车间作业调度问题，然后利用分支定界算法消解列车之间可能的冲突，并将一系列启发式规则嵌入到算法中以加快求解速度。挪威学者Mannino等[49]利用分支定界算法求解地铁列车实时调度问题，通过隐枚举法将可行的路径加入到活动节点集合中，将每个节点得到的可行目标值作为上界，同时利用最小费用流模型求解下界。Shafia等[31]利用分支定界算法求解列车时刻表问题，每个搜索节点对应一个可能的列车时刻表，并通过节点选择策略逐步更新下界。Liu等[30]建立了列车时刻表的两阶段优化模型，设计了基于分支定界的启发式求解框架，构造的搜索树节点表示主问题和对应的系列子问题，设计了基于领域搜索的分支策略，并通过预定阈值对问题定界。

动态规划(Dynamic Programming)算法，是求解列车时刻表问题另一类常用的分解算法，该算法的核心思想是，根据离散及多阶段特征，将待求解问题分解为若干个子问题，然后按顺序求解子问题，并用前一子问题的解向后一问题提供信息；在求解每个子问题时，通过决策保留能够达到最优的局部解；依次求解子问题，最后得到原问题的最优解。

Niu 等[50]在求解考虑换乘的列车时刻表时，运用动态规划获取问题的最优解；算法执行过程中，视列车为决策阶段，列车在始发站的出发时刻为搜索状态，乘客在站等待时间和在车拥挤度作为状态的评价函数。阴佳腾等[38]利用动态规划求解列车调度调整问题，将列车在车站之间的移动作为待决策阶段，以乘客延误时间、旅行时间和列车能源消耗为评价指标函数，并通过近似化指标函数加速问题的求解效率。对于一个拥挤的公共交通系统，Chen等[51]在研究车辆车头距和编组长度优化时，利用了动态规划算法，其中以离散的时间节点作为决策阶段，乘客排队长度为状态变量，能耗成本和等待时间为指标函数，为避免“维数灾”的影响，迭代中不断加入有效不等式，以缩减状态空间、加快求解速度。

3.4 对偶分解方法

在问题分解过程中，充分利用对偶信息，称为对偶分解算法。拉格朗日松弛算法(Lagrangian Relaxation)是最著名的对偶分解算法，该方法被广泛应用于求解各类运筹优化问题，如车辆路径、设施选址、任务调度等问题，美国宾夕法尼亚大学教授、著名运筹学家Fisher[52]对该方法有详细的分析和精辟的点评。拉格朗日方法的核心是将“多智能体耦合约束”进行松弛，得到多个易求解的子问题，然后应用对偶信息进行迭代，并随时计算评估当前解距离最优解的偏离程度，直到找到问题的满意解为止。在列车时刻表优化问题中，“股道能力约束”要求相关的列车群在同一区间必须满足最小安全间隔，用拉格朗日方法松弛该能力约束，就可以将复杂的列车时刻表问题分解为一系列最短路径问题。

1998年，瑞典皇家理工学院Brannlund 等[9]在求解列车时刻表问题时，首次应用拉格朗日松弛方法，将一段轨道线路划分为若干个闭塞区间，要求两个列车在任意时刻不能占用同一区间，通过松弛区间能力约束，将原问题分解为多个单列车路径子问题。由于时刻表模型中包括海量的区间能力约束，导致拉格朗日松弛方法难以应对大规模问题求解的需要。基于此，Caprara 教授团队[8,12]通过构建独特的时空网络，将列车时刻表问题描述为一类多商品网络流问题，通过引入不兼容弧来限制股道能力约束，建立仅依赖于时空节点的能力约束模型，避免了拉格朗日乘子过多的影响。沿着这一思路，Cacchiani 等[14,53]应用拉格朗日松弛方法，通过松弛股道能力约束，求解货物及鲁棒列车时刻表优化问题。2007年，周学松教授[54]将列车时刻表优化描述为一个广义资源受限调度问题，其中区段和车站能力作为受限资源，通过松弛这两类资源约束，将原问题分解为一系列的单列车路径子问题，采用动态规划算法求解子问题，其中为了得到期望的整数解，将分枝定界策略嵌入搜索过程，以生成可行的下界。

城市轨道交通一般采取相对简单的运行模式，不需要考虑列车之间的越行，股道能力约束较为简单，在利用拉格朗日算法求解这类时刻表问题时，可以考虑松弛其他耦合约束条件。 如Hassannayebi 等[28]在研究列车时刻表问题时，同步考虑了动车组运用，通过松弛列车接续约束，将对偶问题分解为两类独立的时刻表子问题。阴佳腾等[39]在求解基于能耗的列车时刻表问题时，利用拉格朗日方法松弛乘客加载与列车运行耦合约束，将问题分解为单纯的列车时刻表问题和客流分配问题。杨立兴等[55]通过构建时空网络，研究了网络条件下地铁末班列车协同优化问题，通过松弛乘客与列车间的关联约束，将问题分解为乘客路径子问题和列车路径子问题。

需要指出的是，在利用拉格朗日方法求解列车时刻表及延伸问题时，松弛约束条件的类型和数量将严重影响算法效率。通常而言，总是希望松弛的约束条件越少越好，而且相互之间没有其他可能的依赖关系，否则会导致不同拉格朗日算子之间互相影响并降低算法效率。为了尽量消除这一问题的影响，Mahmoudi 和周学松[56]于2016年提出多维时空网络的概念，该方法可以将一些复杂约束条件，如车辆容量、时间窗和乘客上下车约束等，自然嵌入到时空网络中，从而剔除一些不必要的约束，使多商品流模型减少对应的拉格朗日乘子，加快了模型的求解速度。近期发表的部分轨道列车调度文献，如地铁列车停站问题[22]、动车组维修和补给问题[57]，均使用了多维时空网络构模技术。

列生成算法(Column Generation)是另一类著名的对偶分解方法，它将原问题分解为限制主问题和价格子问题，通过反复求解两类子问题，以获得问题的最优解。值得注意的是，列生成算法在大多数情况下，需要进一步集成“分支-切割”技术以获得期望的整数解[57]。2008年，Cacchiani教授等[34]在研究列车时刻表问题时，用列车路径为决策变量建立了集合覆盖模型，通过列生成算法及分枝定界技术获得了最后的满意解。2020年，田小鹏和Niu[10]在基于小时的OD需求环境中，研究了含有越行的列车时刻表优化，通过重新定制一组客流加载约束，以匹配列车停站和乘客上下车过程，并通过使用单车站代理对偶变量的方法，消除价格子问题中的不可分割性(Indivisibility)或强耦合性。

4 结论与展望

本文全面总结了轨道列车时刻表问题的研究现状，基于深刻的文献分析与解读，详细讨论了国际学术界在该领域重点关注的研究选题、主要的建模方法和常用的求解算法，评述了相关研究成果的科学意义和应用价值。必须指出的是，这些研究轨道列车时刻表的文献，还存在着一些问题和不足，主要表现在：

(1)理论研究和实际应用之间缺乏深度融合。轨道列车时刻表优化是一个有明确实践背景和巨大理论挑战的问题，这需要所开展的研究既能全面细致、适合应用，又能适度简化、方便求解。然而，该领域现有的理论研究总有一些曲高和寡、偏离实际的感觉，缺少与运营企业深层次的信息交流及合作攻关。

(2)缺少对一些重要实践问题的深层次理论探索。在该领域的应用层面，长期存在着一些难以完成的操作任务，如需要为每个列车在始发站预先指定一个出发时间窗，对于拥挤的铁路走廊，实践中很难实现这一设置；类似这样的具体问题，往往背后隐藏着复杂的理论挑战，现有研究文献缺乏深入的分析和探究。

作为交通管理和运筹优化领域重要的理论和实践问题，轨道列车时刻表问题的研究热度和广度还将持续较长的时间，未来可能的研究选题包括：

(1)现有列车时刻表问题的研究文献，主要集中在单线路或单走廊情形，关于轨道交通网络列车时刻表问题，鲜有大影响、高亮点的研究成果。研究该类问题，需要重点解决不同线路上列车之间的衔接及旅客的换乘问题，这会产生相当多的困难和挑战，将是一个非常有意义的研究选题。

(2)将现有列车时刻表问题的研究成果，通过与线路规划、动车组调度和其他实际需要(如维修天窗)，以及时变票价和客票分配等因素之间进行深度融合，研究轨道列车时刻表集成优化问题。

(3)由于轨道列车时刻表问题特有的大规模和NP难特性，研究该类问题有效可靠的求解算法，始终具有重要的理论和实践意义。利用已有求解架构，结合不同问题的特点，设计针对性的启发式算法，或借鉴其他相关学科研究成果，构建新的求解算法或架构，都是值得继续探索的研究选题。

(4)最后，根据所获得的优化理论和方法，通过与轨道企业的深度合作，开发能够完全应用于实际运营、具有商业意义的系统软件，将是一件非常有意义的工作。