铁路列车运行图优化技术研究综述

Review of Research on Optimization Technology of Railway Train Working Diagram

摘要

铁路列车运行图是铁路运输组织的核心，其编制质量直接影响铁路运输系统的服务水平。随着铁路网络的不断扩大和运输需求的持续增长，铁路列车运行图优化技术日益成为研究热点。首先系统地回顾了目前铁路列车运行图优化的主要研究方向，分别对列车运行图独立编制以及列车运行图与天窗方案、动车组运用方案等要素一体化优化的现有研究成果进行了分析和归纳；其次，根据铁路列车运行图铺画方式的不同，分别总结了非周期运行图和周期运行图的建模方式；最后，对铁路列车运行图优化的求解算法进行了综述，探讨了不同算法的优缺点及应用实例。通过对现有研究成果的梳理和未来方向的展望，为后续铁路列车运行图优化研究提供了良好基础。

Abstract

The railway train working diagram is the core of the railway transportation organization, and its compilation quality directly affects the service level of the railway transportation system. With the continuous expansion of the railway network and the sustained growth of transportation demands, the optimization technology of the railway train working diagram has increasingly become a research focus. This paper first systematically reviewed the current primary research directions of railway train working diagram optimization and summarized the existing research achievements in both isolated train working diagram compilation and the integrated optimization with critical factors such as maintenance window schemes and electric multiple unit (EMU) utilization plans. Secondly, according to the different railway train working diagram scheduling methods, it summarized modeling approaches for non-periodic and periodic working diagrams, respectively. Finally, this paper comprehensively reviewed solution algorithms for railway train working diagram optimization, discussing the advantages, disadvantages, and applications of different algorithms. By systematically organizing the existing research and prospects for future directions, this research provides a solid foundation for subsequent research on railway train working diagram optimization.

Graphical abstract

关键词

铁路列车运行图 / 优化技术 / 研究现状 / 模型 / 求解算法

Key words

Railway Train Working Diagram / Optimization Technology / Research Status / Model / Solution Algorithm

0　引言

铁路作为综合交通运输体系的重要交通方式，是国民经济平稳运行的有力保障之一。《新时代交通强国铁路先行规划纲要》^[1]指出，要推动效率变革提升，创新列车运行图编制，提高调度指挥水平，优化运输产品结构，高效配置运力资源。这需要进一步提升铁路客货运输能力、服务品质和运行效率，对铁路运输组织工作提出了更高要求。列车运行是铁路运输生产过程中的复杂环节，需要各部门、各工种、各项作业之间互相协调配合，才能保证行车安全并提高运输效率^[2]。列车运行图作为铁路运输组织的重要技术文件，包括了列车在区间运行以及在车站到发时刻，是全路组织列车运行的基础^[3]，其编制质量是提高运营效率、运输服务水平和保障列车按图行车的关键。我国列车运行图编制采用中国国家铁路集团有限公司(以下简称“国铁集团”)和铁路局集团公司两级管理体制，涵盖运输、客运、机务、车辆等多个部门，其中国铁集团负责制定列车开行方案，各铁路局集团公司则负责具体铺画运行线，并在运行图编制结果的基础上确定动车组运用计划、机车交路、乘务计划等。

由于列车运行图在铁路运输组织中的重要性，列车运行图优化问题吸引了大量国内外学者从事相关研究，从运行图结构^[4]、协同优化^[5-7]、变量约束^[8-10]、建模体系^[8，11]、求解算法^[12-14]等多个方面进行了积极探索，涌现了丰富的研究成果。本研究从运行图优化研究方向、模型构建、求解算法3个角度对国内外列车运行图优化技术研究进行综合分析与总结。

1　运行图优化研究

列车运行图编制问题的本质是大规模组合优化问题，其求解为NP难问题^[4]，该问题持续吸引着运筹学与交通运输领域学者的广泛关注，并积累了丰富的研究成果和经验。根据优化对象是否仅限于列车运行图，可分为列车运行图独立编制和列车运行图一体化优化编制^[15]。

1.1　列车运行图独立编制

传统的列车运行图编制是指在开行方案给定的前提下，确定列车在运行区段内各站的到达和出发时刻，对列车运行图进行编制与优化。需考虑的约束条件主要包括区间运行时分约束、停站时间约束、车站间隔时间约束、车站到发线约束和动车组接续时间约束等。此类问题的优化方向主要可分为以下3类：列车运行效率、运行图抵抗延误能力以及运输服务质量，列车运行图独立编制研究方向分类如图1所示。

1.1.1　列车运行效率

列车运行效率提升是路网能力高效运用的保证，是列车运行图优化问题的基本目标。该方向研究在列车运行图优化领域起步较早，早期的单目标运行图优化研究大多以列车运行效率为目标，具体体现为旅行时间最小化^[9，16]与旅行速度最大化^[17-18]。在既有研究中，Amit等^[16]首次将列车运行图编制视为大规模非线性规划问题，以列车在车站的到发点为决策变量，考虑了股道通过能力和停站时间约束，以总旅行时间最短为优化目标设计启发式算法。同样以旅行时间最小化为优化目标，Szpigel^[10]则将列车运行图编制问题转化为Job-Shop模型，为后续研究^[8]提供了新的建模思路。孙焰等^[9]提出三重问题转化理论框架，将非追踪货物列车运行图的优化问题划归为工序统筹、逆序最优排序及最优匹配问题，进一步验证了单线区段计算机编图的可行性。彭其渊等^[18]在此基础上，以旅行速度最大化为优化目标提出局域滚动逐步优化算法，显著提升了求解效率。针对复杂路网场景，彭其渊等^[19]将单线区段货物列车运行图模型推广到双线区段，进一步构建了以车站为节点、区间为弧的有向网络，提出通用的列车运行图优化编制模型，实现了单线区段、多线区段以及网状线路和枢纽背景下的列车运行图一致性建模方法和高效分解算法。史峰等^[17]提出多阶段分解算法，将NP难问题转化为递进式优化子问题，将每阶段的优化目标设定为提高列车旅行速度，通过按时间循环迭代逐步达到整体最优状态，显著降低了求解难度。综上所述，在列车运行图优化研究体系中，列车运行效率提升作为一个重要的研究方向，通过建模方法创新、应用场景拓展和求解算法优化等层面的持续突破，为后续的研究提供了重要的理论支撑。随着研究问题的不断扩展与复杂化，考虑鲁棒运行图与客货运需求的优化已成为列车运行图优化领域的重要研究方向。

1.1.2　运行图抵抗延误能力

列车运行图抵抗延误能力是指在编制阶段考虑运行图执行过程中的不确定性，以抵抗可能发生的延迟或提高恢复能力为优化目标。现有研究中将可靠性、鲁棒性等作为衡量这种能力的重要指标，这2个指标都描述了列车按图运行的可能性，可靠性更注重以实现既定的客户服务水平为目标，而鲁棒性则体现为通过加入缓冲时间来抵抗延迟的能力。

运行图的可靠性是对运行图抗干扰能力的量化表征，即列车在实际运行时与计划时刻表维持一致的概率^[20]。Högdahl等^[21]认为铁路运输服务的2个重要特性是旅行时间短和可靠性高，为此提出了一种模拟-优化相结合的方法，以预定行程时间和期望延误的加权和最小化为目标，解决了短行程时间和高可靠性之间的冲突问题；Vromans等^[22]则认为增加可靠性的方法之一是减少由列车之间的相互依赖导致的延误传播，通过减少每个区段的运行时间差创建更均衡的列车运行图来减少上述相互依赖。目前，关于列车运行图可靠性的优化研究较少，但这一概念对铁路旅客运输以及货物运输来说都是一个重要的绩效衡量指标。

运行图的鲁棒性则是指列车运行图在延误发生后仍具有完成既定列车运营计划的能力。编制鲁棒运行图的常用方法是在规划阶段引入缓冲时间，用来吸收可能发生的晚点^[23]。而为了在乘客服务质量和延迟抵抗能力之间取得良好的折中，缓冲时间的分布规律和大小成为一个重要的研究方向。Andersson等^[24]将临界点的概念引入鲁棒运行图研究，并定义了临界点鲁棒性(Robustness in Critical Points，RCP)，以此来准确地判断插入缓冲时间的位置，以提高运行图鲁棒性。在此研究的基础上，Solinen等^[25]为了弥补RCP理论与实践之间的差距，提出将临界点的理论概念应用于实际列车运行图规划方案，并提出了新的RCP选择规则来优化时刻表以增强运行图鲁棒性。Dewilde等^[26]在列车运行图计划阶段定义了2个列车之间的最小时间跨度，作为导致列车在区间发生冲突的最小延迟，提出一种基于禁忌搜索的迭代方法来逐步优化运行图鲁棒性。Bešinović等^[27]认为目前的大多数模型只考虑了宏观路网，而忽略了微观基础设施，例如信号定位、信号开关等因素的影响，为此提出了一种结合微观和宏观的层次化列车运行图建模方法，对列车运行和最小追踪间隔时间进行迭代调整，直至在微观层面生成可行且稳定的列车运行图。

在上述研究中，为提升列车运行图鲁棒性以达到理想的准时性，可能会加入大量的冗余时间，降低了运行图的通过能力，如Cacchiani等^[28]指出必须考虑运行图效率和鲁棒性目标之间的权衡，保证轻微干扰下列车运行图方案仍然可行，也要尽量提高线路资源的有效利用率。为解决此类问题，Lee等^[29]提出了一种基于仿真的方法，嵌入线性规划模型，有效地调整列车运行图中的缓冲时间，以减少平均延迟，该方法可以量化运行图效率和鲁棒性之间的关系。Liebchen等^[30]同样认为在列车运行图编制时通过加入一定比例缓冲时间来提高运行图鲁棒性的方法是以牺牲部分运行能力为代价的，为此定义了可恢复鲁棒性的概念，若加入了缓冲时间的运行图能够通过恢复算法在有限时间内降低鲁棒性代价，则认为该运行图具备可恢复鲁棒性。在此基础上，刘敏等^[31]采用恢复算法构建了列车运行图可恢复鲁棒性优化模型，应用给定的恢复策略计算时刻表，使操作阶段的延迟影响受到限制。

1.1.3　运输服务质量

除列车运行效率、抵抗延误能力外，运输服务质量也是列车运行图优化领域的重要优化目标，主要体现于以满足运输需求为导向优化运行图编制。传统列车运行图编制模式将运输需求仅作为开行方案制定的静态约束，再将制定完成的开行方案作为编制列车运行图的约束条件，这种模式在提高运输供需匹配度、优化运输服务质量方面存在双重局限：一是未在列车运行图编制过程中直接考虑运输需求，可能导致运输供需匹配效率低下，具体表现为列车间换乘时间较长等问题；二是旅客和货物运输需求复杂多变，仅考虑其静态特征不足以反映实际需求，可能导致时变运输需求无法得到满足。

为突破传统列车运行图编制模式的局限性，近年来，国内外学者从满足运输需求的角度出发，逐渐将动态需求嵌入到列车运行图编制过程。黄鉴等^[32]针对时变客流，引入了列车服务频率偏差的概念，增加考虑了服务频率约束和始发时间域约束，将减少列车服务频率偏差作为优化目标之一，建立了客运专线列车运行图优化模型，有效解决了列车服务频率与需求不相匹配的问题。Barrena等^[33]通过将时间离散化，假设每个时间间隔内的旅客到达服从均匀分布，以最小化乘客的平均等待时间(Average Waiting Time，AWT)为求解目标，通过分支定界法进行精确求解；结合客流需求的动态特征，Barrena等^[34]又进一步提出了2种非线性规划模型，将总旅客等待时间用黎曼和表示，设计自适应大邻域搜索(Adaptive Large Neighborhood Search，ALNS)元启发式算法，为快速求解大规模问题提供了新思路。Niu等^[35]同样以最小化车站乘客等待时间为目标，基于时变OD客流需求矩阵优化城际列车时刻表，首次提出了适应不同粒度客流需求的非线性混合整数规划列车时刻表优化模型，通过案例验证了该模型能有效协调复杂时空需求分布场景下的列车运行图。

上述文献均是基于列车直达场景，未考虑旅客出行的换乘方案。为优化换乘服务质量，李天琦等^[36]建立了基于换乘接续优化的多目标模型，通过引入换乘服务频率约束，同步优化总旅行时间、总换乘接续时间和换乘服务缺口值，在换乘频率、动态接续、换乘时间等方面显著优化了京沪高速铁路(北京南—上海虹桥)周期列车运行图编制。周文梁等^[37]研究了列车运行图与旅客乘车选择的相互影响，在优化列车运行图时考虑了城际客流均衡分配，构建了城际列车运行图优化的双层规划模型，将换乘等待时间与旅客始发终到时间满意度纳入目标函数，案例证明该模型能够精准刻画旅客乘车行为。针对客流需求过饱和场景下的高速铁路走廊问题，Tian等^[38]在基础时空网络模型的基础上，引入基于客流分配的整数变量，结果显示较优化前的模型能够有效缩短乘客总旅行时间。

相比客运，以货运需求为导向的研究较少。高如虎等^[39]在时变需求驱动下，聚焦高铁快运箱运达时间，构建了新增快运专列时刻表和装配方案综合优化模型，从运输组织优化的角度提升高铁快运运输效能。此外，Qi等^[40]将客运需求和货运需求相结合，从优化列车编组模式的角度优化列车运行图结构，通过考虑多种类型的客货混运车厢编组，灵活制定满足时变客货需求的运输方案。

1.2　列车运行图一体化优化编制

传统运输组织模式采用分层优化，其核心特征为分阶段独立决策：开行方案编制作为前置环节确定列车运行区段、停站方案等列车运行图编制的输入条件；列车运行图与天窗方案编制采用分段编制模式^[41]；车站作业计划、动车组运用计划、机车交路计划、乘务计划等计划的编制作为运行图编制的后置环节，直接依赖运行图编制的输出结果。这种分阶段决策的模式在编制列车运行图时，优化目标仅考虑运行图编制阶段的指标和属性，优化对象只针对运行图本身的要素，在一定程度上可以降低问题复杂度，但存在显著局限性：一是存在目标局限性，仅聚焦运行图阶段的单一目标及要素，割裂了多阶段指标间的关联性；二是整体协同性缺失，未构建开行方案、天窗方案、动车组运用等子系统的耦合机制，导致全局优化目标失准。近年来，随着运筹模型和求解算法的不断迭代优化，相关研究逐渐趋向多要素协同优化，其中，列车运行图与开行方案、天窗方案以及动车组运用计划的一体化优化为重点研究方向，列车运行图一体化优化编制主要研究方向如图2所示。

1.2.1　列车运行图与开行方案一体化优化

列车开行方案是铁路运输服务供给的核心决策内容之一，包括列车运行区段、列车开行频率、停站方案等要素。在传统的列车运行图编制过程中，开行方案编制在运行图编制之前进行，其编制结果作为运行图编制的输入条件，运行图单向依赖于开行方案编制结果，未能形成反馈回路，限制了运行图编制质量的提升。

近年来，列车运行图与开行方案的一体化优化成为运行图领域的研究重点。周文梁等^[42]以企业效益最大化为目标，分别基于开行方案和运行图进行客流分配，建立旅客列车开行方案与运行图综合优化的双层规划模型，上层模型以企业效益最大化为目标，协同优化运行图与开行方案；下层模型根据列车时刻表进行客流分配，以此结果衡量各列车服务质量和运营效益，这种双层规划模型实现了开行方案与列车运行图优化的有效结合。

停站方案作为开行方案的重要组成部分，是一体化优化的重点对象。在客运研究领域，一方面从停站次数角度进行协同优化，Yang等^[6]将停站计划指标作为重要决策变量，将满足站点预测客运需求作为约束，提出协同优化列车时刻表和停站方案的建模方法；Yue等^[7]在考虑各站点客运需求和供给能力的基础上，又增加考虑了停站次数对列车利润的影响，建立需求覆盖约束下的运营利润最大化模型。另一方面从旅客满意度角度进行协同优化，田小鹏等^[43]提出双目标优化模型，以小时OD客流作为输入，同步优化列车供给效率与旅客时间满意度，以提升城际列车出行品质。在货运研究领域，针对铁路集装箱运输特性，韩涛等^[44]提出集装箱班列的停站方案与列车运行图协同优化模型，将列车停站方案约束嵌入到列车运行图编制过程中，实现铁路集装箱运输成本最小化。

1.2.2　列车运行图与天窗方案一体化优化

天窗方案与列车运行计划存在相互制约的关系，天窗的设置会压缩列车可用运行时段，而运行线的不合理铺画可能压缩天窗作业的可用时间窗口。如何平衡运输组织与设施维护的时空冲突，成为列车运行图与天窗协同优化的核心命题^[45]。

国内外学者对列车运行图与天窗方案的协同优化进行了大量研究。聂磊等^[46]针对客运专线夜间天窗开设难题，首先以天窗影响列车OD数最小为优化目标，对最佳矩形天窗位置问题进行求解，对于求解结果中受天窗影响的列车，从动车组运行速度层面提出调整措施。Vansteenwegen等^[5]提出一种考虑维修作业时间与列车运行时间均衡的方法，尽量降低列车停运的次数，以提高列车运行图的鲁棒性。Luan等^[47]利用基于网络累积流量变量方法和基于虚拟列车的建模方法，构建了列车运行图与维修天窗的一体化优化模型，协同优化列车运行线路、站序、时刻及天窗作业。石贇等^[48]针对天窗引发的跨线列车扰动问题，提出一种列车运行图与维修天窗计划一体化编制模型，同步优化本线列车时刻、跨线列车时刻及天窗计划，实现旅行时间压缩与时刻偏差控制的双重增益。张天伟等^[49]对比了供电区间与行车区间的异同，揭示供电区间对高速铁路天窗设置的制约机制，构建到发时刻满意度和对天窗干扰度双目标导向的线性规划模型，对高速铁路夜间运行图与天窗方案进行协同优化，验证了基于供电区间协同优化的必要性。

1.2.3　列车运行图与动车组运用一体化优化

动车组运用计划与列车运行图一体化优化的本质是运输成本综合管控，需在满足运输需求的前提下，协同优化动车组调度、检修作业与运行图时空资源的匹配。为实现列车运行图编制过程中动车组运用效率的提升，Chen等^[50]提出了高速铁路列车运行图与动车组运用计划一体化编制模型，通过改进蚁群算法优化列车接续逻辑与检修周期配置，实验结果显示该模型在列车接续、动车组检修及追踪运行的鲁棒性方面优于传统独立编制模型。王超等^[51]基于车辆路线问题理论，提出了高速铁路列车运行图与动车组运用的一体化优化模型，利用GAMS求解器实现开行方案约束下的动车组运用成本最优。史峰等^[52]提出多约束耦合模型，增加考虑动车组终点站接续时间间隔约束，构建旅行时间与接续时间双目标最小化的时空网络模型，突破了单一资源优化局限。Li等^[53]引入反馈修正机制协调动车组数量、动车组检修任务数量与列车旅行时间，建立动车组周转与时刻表联合优化模型，通过帕累托前沿分析揭示运营成本与服务质量间的边际替代规律。

除此之外，列车运行图一体化优化方面的研究还包括列车运行图与车站作业计划一体化优化^[54]、列车运行图与机车交路一体化优化^[55]、列车运行图与乘务计划一体化优化^[56]等。总的来说，相较于列车运行图独立编制优化，一体化优化能够消除运输组织各环节的决策割裂，实现列车运行与资源分配的协同，其优势具体体现在3个方面：一是效率提升，通过时空资源协同配置压缩动车组周转时间；二是成本控制优化，减少移动装备空置与冗余调度；三是服务升级，增强铁路运输系统的适应性和竞争力，以满足日益增长的运输需求。现阶段，运行图一体化优化模型因其建模和求解复杂度高，在实际应用中面临重大挑战，难以快速得到高质量解，目前主要处于理论研究阶段。未来随着算力的提升，求解效率和质量将显著提高，一体化优化将成为运行图优化问题的重要方向。

2　模型与求解算法

2.1　模型

按照铺画方式的不同，铁路列车运行图可分为非周期运行图和周期运行图，在编制优化运行图时2种建模方式也有所不同。非周期运行图优化中，常见的建模方法有直接建模和时空网络模型；周期运行图优化中，主要的建模方法为周期事件规划问题(Periodic Event Scheduling Problem，PESP)模型以及基于PESP的改进模型。

2.1.1　非周期运行图编制模型

对于非周期列车运行图(Non-Cyclic Train Timetable)编制问题，根据建模思路的不同，主要分为直接建模和时空网络模型。早期研究以直接建模为主，孙焰等^[9]在研究单线区段货车运行图的优化问题时，通过将列车的运行线铺画视为一类特殊的工序统筹问题，以上下行列车的出发到达时刻为变量，以区间运行时分、停站时间、车站间隔时间、区间被占用情况、到发线占用情况为约束，用总旅行时间、列车接续时间、机车使用台数作为衡量运行图编制质量的指标，构建了多目标线性整数规划模型，是我国列车运行图自动编制问题的经典案例。在其研究的基础上，彭其渊等^[18]增加考虑了列车追踪间隔约束以及天窗约束，取旅行速度作为优化目标，对单线区段货物列车运行图进行优化；对于网络化列车运行图编制问题，彭其渊等^[19]构造了基于路网的列车运行图优化模型，增加考虑了列车越行约束，进一步扩大了计算机编制运行图的适用范围；史峰等^[17]将列车运行图编制模型分解为阶段优化模型，针对单线铁路列车运行图的冲突疏解问题，最早提出了冲突优化方法；Zhou等^[8]采用了与Job-Shop问题类似的建模方法，视区间和车站的通过能力为有限资源，将列车运行图编制问题转化为广义资源受限问题。在传统Job-Shop模型基础上，Burdett等^[57]将列车运行图描述为不带存储约束的Job-Shop调度问题，增加考虑了列车长度、停站时间、车头时距等运行图编制的特征变量，更加符合编图实际情况。针对客运专线列车运行图，许红等^[58]在既定的客运专线运输组织模式下，提出列车运行图铺画的分层叠加数学模型，以列车总运行时间、运行图均衡性、运行图可调整性3类指标来评价运行图编制质量；黄鉴等^[32]在其基础上，定义了区间服务频率偏差，用多目标非线性整数规划模型体现不同时间段客运需求差别，并提出基于循环布线的列车运行图模拟退火优化方法求解。

现有直接建模的研究在建模方式上存在宏观、宏观与微观结合2种主要方式，列车运行图优化技术研究中直接建模方式的比较如表1所示。在宏观层面对列车运行图优化问题进行建模时，通常将线路简化为车站区域和车站间的区间区域。然而，这种简化方式会忽略列车在车站内部和区间内部的实际运行过程，当需要实现列车运行图的精细描述与优化时，存在局限性。为此提出了宏观与微观结合的建模方法。现有宏观列车时刻表优化研究的主要研究场景为单一线路，其中较为特殊的研究场景考虑了线路上的跨线列车^[48]。宏观与微观结合的研究场景则会集中在多条线路构成的网络化线路上。不同的建模方式下设定的约束条件也不同，绝大部分研究会涵盖列车运行图优化通用的基础约束，包括到发时间约束、区间运行时间约束、停站约束、间隔约束、车头时距等，其中的少部分建模过程会考虑越行约束^[21]。在此基础上，对于特定的研究场景会通过增加约束和调整目标函数来建模，如在提升列车运行图抗干扰能力的研究中，针对实际运营与理想时刻表的动态偏差问题，设置了路径选择、延误时间等约束，并建立弹性缓冲时间分配策略以增强系统鲁棒性；在考虑客货运需求的研究中会额外增加乘客服务约束^[48]、客流分布约束、货流分布约束^[40]、列车载客能力约束^[43]等；在多要素的一体化研究中，协同优化时刻表与维修计划时则会考虑天窗时间约束、维修占用区段约束以及维修任务相关约束等。

由上述研究可知，直接建模方法的决策变量主要包括列车经由各站的到发时间，在研究停站和越行问题时，则会考虑列车在站顺序，增加0-1变量。但此类建模方法构建的混合整数规划模型为NP难问题，求解过程比较困难，无法找到精确解，只能通过启发式算法寻找可行解。因此一部分学者倾向于选择时空网络模型，时空网络建模示意图如图3所示，该图展示了基础的时空网络建模方式，横轴为时间，纵轴为列车在不同时间节点所处的状态，这种建模思路下，通过用点和弧来表示列车活动和事件，使得一些复杂的约束可以嵌入到离散的时空网络中，连接时间与空间维度则形成了通过、运行、等待、维修4种类型的弧，直观地展示了列车运行图固有的时空特性。

基于时空网络的建模方法可以将物理网络与表征时间状态的列车运行图相结合，来刻画铁路网络中的动态时空变化特性。为此，Caprara等^[4]提出了一种用有向多重图来描述列车运行图问题的方法，其节点对应给定时间点下某一车站的出发或到达事件。彭其渊等^[19]基于列车运行图网络模型特点，将车站视为节点，车站到发线以及与车站相关的进路作为约束条件，构建了简化的铁路网络模型。这一阶段的研究停留在由节点和边构成的图的概念中，没有明确提出时空网络模型的概念，而为了更好地刻画物理网络和时空网络之间的关键联系，Yang等^[11]将路段和车站能力视为有限资源，把运行线的动态规划公式表示为包含2种类型弧段的时空网络，以最小化列车总旅行时间为目标研究了单线铁路列车时刻表问题。在此基础上，Tian等^[38]创建了类似的离散时空网络，将每个中间站抽象为2个独立的到发站，并以较小的时间粒度离散规划时域［0，T］，生成时空顶点，根据列车的运行和停站要求，通过关联顶点进一步建立时空弧，以求解总运营成本最小的列车运行图方案。针对高速铁路列车运行图规模庞大、难以精确求解的问题，An等^[61]采用有向时空网络对列车运行图进行刻画，通过引入不相容弧段集合，将最小车头时距、列车越行等约束合并为互斥弧段约束构建整数规划模型。

2.1.2　周期运行图编制模型

对于周期列车运行图的编制，大都是基于PESP模型和圈周期模型(Cycle Periodicity Formulation，CPF)的建模。1989年，Serafini等^[62]首次提出PESP模型，原始模型并未设置明确的目标函数，将求解目标设定为确定周期性事件发生的时间点，即寻找可行的周期运行方案。模型约束主要是周期性限制，具体约束形式如下。

l_a\le {\pi }_k-{\pi }_j+T·p_{jk}\le u_a(1)

式中：l_a，u_a为时间窗的下边界和上边界；{\pi }_k，{\pi }_j为事件k，j的发生时刻；T为周期时间；p_{jk}为模变量。

由于该问题与周期列车运行图铺画问题极为相似，Voorhoeve^[63]首次将PESP模型用于研究荷兰铁路的周期运行图编制问题，设计了基于约束传播和回溯思想的周期运行图模型求解算法。考虑到原模型缺少明确的优化方向，Nachtigall^[14]引入“周期网络”概念，将费用最小和旅客等待时间最小作为优化目标，完善了PESP模型框架。Peeters^[64]在PESP模型的基础上，引入了位势和势能差的概念，将建模对象从事件发生时刻转为事件发生间隔，首次提出了CPF模型，分别以最小化旅行时间、提高列车运行图鲁棒性和减少动车组使用数量为优化目标，对列车运行图进行优化。Liebchen等^[65]在Peeters的研究基础上，进一步分析了CPF模型的圈基(Cycle Base)类型，并对比分析了主要的圈基搜索算法。Liebchen等^[66]进一步对比分析了PESP模型与CPF模型用于周期运行图求解的优缺点，并基于遗传算法设计了周期运行图的求解算法。

国内对周期运行图的研究起步较晚，绝大多数是基于PESP模型及其变形的拓展优化。汪波等^[67]在PESP模型的基础上，利用周期约束图建立了周期势差模型，降低实际问题的求解难度，并以京津城际铁路(北京南—天津)进行案例研究，验证了模型有效性。谢美全等^[68]结合国内客运专线实际情况，在PESP模型基础上，针对运营情况复杂线路，提出基于定序的周期列车运行图模型，该模型以最小总旅行时间为目标，约束条件考虑了列车区间弹性运行时间、不同停站时间、到发安全间隔、发车频率等。郭根材等^[69]为避免约束图圈基的重复搜索，提出分类整数圈基，并从决策变量、目标函数、约束条件3方面改进CPF模型，建立了适合备选列车接续的周期列车运行图编制模型(Potential Connection & Cycle Periodicity Formulation，PCCPF)。李得伟等^[70]对PESP传统模型进行改造，考虑了可变区间运行时分，通过有效不等式改进了PESP模型，实现了对大规模高速铁路周期运行图编制问题的求解。张新等^[71]基于事件-活动网络(Event-Activity Network，EAN)和PESP模型，以最小化周期时间、列车停站次数和总旅行时间为目标函数，构建了基于能力提升的周期模式列车停站方案调整模型，并使用该模型求解优化了京沪高速铁路周期列车开行方案。李海琳等^[72]从周期化水平、客流直达率、一次换乘时间3个角度评价周期运行图，建立基于列车服务频率的列车开行方案优化模型，分别对沪宁城际铁路(上海—南京)和京沪高速铁路开展实例研究，为定量优化周期长度提供了方法。

综上所述，以PESP模型为基础的周期运行图编制理论方法体系已趋于成熟，但由于我国周期化列车运行图运营经验少，上述研究的应用场景大都局限于单线周期化运行图问题，缺少对网络化周期列车运行图的研究。

2.2　求解算法

针对列车运行图编制面临的规模大、场景复杂、求解困难的问题，现有研究中提出了众多的高性能求解算法，从算法的设计原理出发，可将其归纳为精确求解算法、启发式算法^[73]及对偶分解算法，求解算法分类框架如图4所示。其中精确算法通常用于求解中小规模组合优化问题，启发式算法通常用于求解难以得到精确解的大规模问题，对偶分解算法主要用于求解复杂的优化问题，通过将对偶问题分解为更小的子问题来求解。这些算法之间相互联系，如分支定界和列生成算法的结合可以形成分支定价算法；对偶分解算法允许根据问题的特性选择子问题的求解方法，既可与精确算法协同保证解的质量，也可与启发式算法结合提升效率。

2.2.1　精确求解算法

在现有列车运行图优化研究中，精确求解算法在中小规模问题求解中具有优势，常用的精确求解算法包括分支定界算法、列生成、行生成、分支定价算法等。

分支定界算法的核心思想是将混合整数规划问题分解为线性规划问题，并在求解过程中记录原问题的上界(最优可行解)和下界(最优线性松弛解)，主要用于解决离散和组合优化问题，作为一种典型的树状搜索方法，通过系统地遍历搜索空间内所有可能的列车运行图方案，达到求解最优运行图的目的。为缩小求解的范围，Nachtigall^[14]在求解周期列车运行图问题时，用搜索树方法分解搜索空间，再用分支定界算法在简化后的解空间里寻找最优解。Zhou等^[8]在求解单线铁路的运行图编制问题时，提出高效的分支定界求解方法，使用拉格朗日松弛问题的下界，较基础算法提升了求解速度和精度。Liu等^[74]在研究复杂铁路网络下的鲁棒旅客列车运行图问题时，使用了广度优先的分支定界算法框架，为解决每个搜索树节点上的问题，同样将启发式算法分别应用于主问题和子问题的求解，极大提升了分支收敛速度。分支定界算法虽然搜索范围比较全面，能够保证找到全局最优解，但在求解规模较大时计算效率低下。

列生成算法常用于求解大规模线性规划问题，本质上是单纯形法的一种形式，通过把问题分解为限制主问题和价格子问题，逐步迭代求解主、子问题，能够快速逼近最优解，具有与其他算法结合的灵活性，如与分支定界结合用于求解列车运行图问题。Cacchiani等^[13]运用列生成算法，通过在非周期列车运行图中解决线性规划松弛问题，显著简化了原始问题，快速寻找最优方案。在此基础上，Martin等^[75]考虑了列车运行时间、运行图网络规模以及允许的时间间隔，为有效地处理这种多变量问题，利用列生成算法，其中每一列代表一条线路上的列车路径，并在定价阶段整合对称性和频率约束，减少了主问题所需的约束数量，显著提升了求解效率。面对列生成框架下定价子问题无法通过标准动态规划算法求解的挑战，Tian等^[76]提出用单站依赖的变量替换原有的双重变量，设计了具有分支定价切割框架的双变量列生成求解方法，以动态消除运行图编制问题中的不可分割性，选择了特定的有效不等式组来缩小受限主问题中的可行解范围，该方法有效解决了越行条件下以需求为导向的列车运行图问题。

与列生成算法类似的行生成算法也是以同样的原理求解大规模复杂问题，如兰泽康等^[77]运用行生成算法对到发线数量等约束进行分解从而减少约束的数量，快速求得最优解。廖正文^[78]通过对列车宏观运行与微观运行的一致性进行深入分析，设计了一种面向粒度自适应的行生成算法，能够缩小问题规模，提高求解效率，并得到满足区间、车站以及动车组运用等多方面约束条件的运行图。

分支定价算法是分支定界算法与列生成算法的结合体，特别适用于大规模变量的整数规划问题，在列车运行图编制领域，分支定价算法可以有效地处理具有大量决策变量和复杂约束条件的问题。He等^[79]在求解基于网络流的列车运行图优化编制模型时，为避免陷入局部最优解对求解效率的影响，在定价问题中运用启发式算法生成新解，加速分支定价树的搜索过程，有效提高了算法收敛速度和求解精度。Wang等^[80]在其基础上，针对分支定价算法的易退化、定价子问题耗时久、分支困难等问题，分别从预处理阶段、限制主问题求解阶段、子问题求解阶段、分支阶段和后处理阶段对分支定价算法提出相应的加速策略，在保证精度的前提下进一步提高算法效率，但仍然面临着设计和实现过程复杂、对算力依赖性强等问题。

2.2.2　启发式算法

相较于精确算法，启发式算法能快速为复杂的列车运行图编制问题提供近似最优解，大大提高了编制效率，满足铁路运输系统对运行图快速生成的需求。另一方面，启发式算法可以灵活处理各种实际约束条件，如列车运行时间、停站时间、线路通过能力等，使生成的列车运行图更具实用性。常用的启发式求解算法包括贪心算法、遗传算法、模拟退火算法、禁忌搜索算法、人工智能算法等。

贪心算法是一种在每一步决策中都采取当前状态下最好或最优的选择策略。周政铎等^[81]基于贪心算法设计了列车运行图冗余时间布局优化方法，通过增加单位关键冗余时间，从而实现旅客到达晚点总时间期望最小的目标，该算法计算效率较高，但可能陷入局部最优解。

遗传算法通过模仿自然选择和遗传学的原理来进行优化搜索，该算法具有较强的全局搜索能力。王仲峰等^[82]通过分析列车运行图的特点，利用遗传算法对计算机辅助铺画的列车运行图进行了优化，从而提高编制列车运行图的效率。由于传统的遗传算法具有局限性，石贇等^[48]使用了基于二维排序编码的NSGA-II算法，该算法在复杂性、运行速度和解集收敛性方面都有所改进，因此被广泛应用于多目标优化问题的求解，其在算法的解码部分使用了运行线冲突疏解方法和广度搜索法进行运行线的铺画，交叉和变异部分使用了多列顺序交叉、未交叉部分重新生成及随机越行的交叉策略。

模拟退火算法(Simulated Annealing，SA)是一种通用的概率优化算法，常用于在大规模搜索空间中寻找全局最优解或接近最优解，算法相对灵活，通过调整参数可以在搜索精度和时间之间进行平衡。史峰等^[83]建立了能够降低出行费用的优化模型，基于模拟退火算法设计了优化求解算法。简星等^[84]以列车服务质量及停站率作为约束，建立了优化停站方案模型，通过模拟退火算法进行求解，相较于传统运筹学方法提高了求解效率，但算法性能受参数设置影响较大，需要根据问题进行参数调整。

禁忌搜索算法(Tabu Search，TS)是一种用于解决组合优化问题的启发式算法，通过引入禁忌机制来避免陷入局部最优解，并促进算法的多样化探索。徐长安等^[45]设计了一个两阶段的求解算法，目的是最小化天窗对列车运行图铺画的影响，在综合优化阶段，算法通过维护一个禁忌列表来避免循环，并在搜索过程中寻找更优的解决方案，从而提高铁路运输的效率，减少列车在车站的等待时间。Dewilde等^[26]提出了一种迭代方法，用于优化列车运行图的列车进路，该方法构建由最小时间跨度组成的受限候选列表，并使用禁忌搜索算法避免求解过程陷入循环。

近年来，随着人工智能理论的进步和应用拓展，一些学者开始探索将这些技术应用于列车运行图编制领域，与传统启发式算法相比，强化学习等智能算法展现出自动化、高效率和持续学习能力等优势。蒋辉等^[3]提出了应用人工智能技术的新型编图体系框架，并且指出下一步需要突破的关键技术。Li等^[85]提出了一种基于多智能体深度强化学习的列车运行图优化方法，通过利用Actor-Critic算法框架，将组合决策空间分解，该方法适用于单线和双线铁路场景，得到的解决方案优于现有方法。Khadilkar等^[86]提出一种基于强化学习的算法，能够有效解耦状态空间与问题规模，该算法还能够自适应学习不同线路特征和运行条件，与精确算法相比，具有更强的可扩展性，与传统启发式方法相比，能够有效提高解的质量。为了提升求解效率，范文天等^[87]提出了一种基于强化学习的高速铁路列车运行图编制模型优化方法，能够在列车运行图编制过程中快速消解冲突，从而提高列车运行图编制和调整的效率。使用人工智能、大数据等新兴技术解决运行图优化问题是目前的发展趋势，这类方法在求解速度上优于精确算法及传统启发式算法，但是仍然存在计算资源消耗巨大、求解质量不稳定、缺乏可解释性等问题。基于人工智能的算法在运行图编制领域的应用尚处于探索阶段，但凭借其可扩展性，未来在大规模路网场景下将具有显著的应用潜力。

前述内容分别探讨了精确算法与启发式算法在列车运行图编制优化中的应用。而在实际问题中，单一算法往往存在局限性，部分研究工作结合精确算法与启发式算法，将求解过程分成多个阶段，在不同阶段使用不同的求解算法。Liu等^[74]针对客货一体化优化问题中货物列车出发时间不确定的情况，构建了两阶段随机优化模型，设计了内置拉格朗日松弛启发式算法和标签算法的分支定界算法对模型进行分段求解。张春田等^[88]在研究列车运行图与停站方案一体化优化问题时，将一体化优化模型分解为2个阶段，第一阶段借助基于最短路的启发式算法求解，而第二阶段直接使用GUROBI优化求解器求解，这种混合方法充分利用了启发式算法的快速性和精确算法的精确性，以达到更优的求解效果。

2.2.3　对偶分解算法

随着列车运行图编制场景的多样化，运行图编制优化模型约束和变量也不断复杂化，为高效求解此类问题，需先将复杂的原问题分解为若干个相对容易求解的子问题，通过求解子问题进而获得原问题的较优解^[89]。对偶分解算法利用拉格朗日对偶性，将原问题分解为多个子问题，并通过协调对偶变量进行求解。

当原问题是凸优化问题且满足强对偶性时，对偶问题的解等于原问题的最优解，拉格朗日松弛方法能保证得到全局最优解，属于精确算法。Zhang等^[12]通过扩展时空网络提出了一种整数线性规划模型，该模型包含多个耦合约束，采用拉格朗日松弛和交替方向乘子法两种对偶分解方法，不断迭代原始问题和对偶问题的框架，能够快速找到最优解。

当原问题非凸时，拉格朗日对偶可能存在对偶间隙，即对偶问题的解与原问题的最优解不一致，此时算法无法保证全局最优性，结果可能为近似解。Yue等^[7]提出了一种综合考虑停站和列车运行图编制的模型，为简化问题采用拉格朗日松弛方法将其转化为一个更易处理的线性规划问题，提升了求解速度。Jiang等^[90]以提高旅客列车开行对数为目标，将基于拉格朗日的启发式算法引入铁路旅客列车运行图问题中。值得注意的是，拉格朗日松弛算法得到的解为原问题的下界，有可能无法满足原问题的约束，因而需要在此基础上重新构造可行解^[89]。

总体而言，上述算法各有特点，在实际应用中，研究人员会根据具体问题的需求选择合适的算法，甚至将多种算法结合使用，从而提高求解效率和质量。通过这些算法的应用能够有效地优化列车运行图的编制。

3　结论与展望

3.1　结论

研究对目前铁路列车运行图编制的相关研究文献进行了综述，从运行图优化研究方向、模型构建方法以及求解算法3方面进行了探讨。列车运行图优化技术方面的理论已非常丰富，但仍存在一些问题需要进一步探讨和完善。

（1）模型与实际应用层面存在差距。为便于建模和求解，仅对列车运行图编制过程中遇到的问题进行简化，忽略了实际应用中存在的客观限制，如股道运用、车站技术作业、列车出发到达偏好时间窗等问题。建模环节与实际问题脱节，导致很难将列车运行图编制方面的理论研究成果直接应用到实际编图工作中。

（2）算法求解规模受限，难以适用复杂网络化运营场景。随着铁路网络化运营，如何对不同线路开行的列车进行协同优化，以及如何降低跨线车对于本线车的影响，以达到系统最优的目标，是未来重要的研究主题。不同于单一线路的列车运行图优化问题，路网运行图编制问题规模庞大、复杂性极高，现有算法难以求解，不仅需要在建模技巧上有所创新，还需要提出求解速度更快、精度更高的算法。

（3）运行图编制质量的评价指标存在局限性。列车运行图编制是铁路运输组织的重要组成部分，在优化过程中不应局限于将运行图本身的要素指标作为优化目标。目前大多数关于列车运行图优化的研究中，主要以最小化旅行时间、最大化通过能力、最大化旅行速度、最小化乘客等待时间、最小化加权延误等作为目标函数对列车运行图编制方案进行优化，未考虑运行图编制与运行图实施、客运方案制定等环节之间的相互影响。

3.2　展望

未来的研究可以从以下几个方面开展。

（1）为实现理论研究与实际应用的结合，可以在列车运行图一体化优化模型中增加考虑一些更符合实际应用场景的建模要素和约束条件，如股道运用规则、车站技术作业时间标准、列车出发到达偏好时间窗等；此外，列车运行图的一体化优化也不应局限于单纯考虑列车运行图与开行方案、天窗方案、动车组运用计划等要素中某一要素的协同优化。在今后的研究中，可以同时考虑列车运行图与开行方案、动车组运用计划等多个要素的协同优化，以得到更具现实意义的研究成果。

（2）针对网络化场景下面临的巨大运算量以及难以求解的问题，强化学习、深度学习等人工智能前沿技术的发展，为列车运行图编制优化研究提供了新的技术路线。将智能化方法与分支定界、分支定价等传统运筹学算法有效结合，来提升列车运行图编制效率以及模型求解精度是值得探究的问题。此外，量子计算是一种能突破经典算力瓶颈的新型计算模式，为解决某些经典计算机难以处理的复杂问题提供了新的可能性，在之后的研究中也可以尝试利用量子计算方法解决运行图优化中遇到的大规模求解问题。

（3）衡量一张运行图的质量需要从多部门、多层级、多角度综合考虑。对于编制人员来说，运行图质量主要体现为最大化能力利用率；对于旅客来说，运行图质量体现在最短的期望旅行时间、最小的行程延误等方面；对于运营部门来说，运行图质量主要体现在实现运营利润最大化。通过综合考虑旅行时间、通过能力、运营利润等构建多目标的运行图优化方案，是一个有价值的研究方向。

通过对铁路列车运行图编制优化现有研究进行分析，进一步梳理了目前主要的模型构建方法，总结了不同求解算法的应用实例及其优缺点，完善了列车运行图优化理论和方法体系，促进运行图编制理论与技术向纵深发展。

参考文献

[1] 新时代交通强国铁路先行规划纲要[EB/OL].(2022-08-12)[2025-04-24]

[2] 杨　浩. 铁路运输组织学(第三版) [M].北京：中国铁道出版社，2011.

[3] 蒋　辉，李　博，贺俊源. 基于人工智能的列车运行图智能编制技术体系框架研究[J]. 铁道运输与经济，2024，46(1)：1-9.

[4] JIANG Hui， LI Bo， HE Junyuan. Research on the Framework of Intelligent Train Working Diagram Compilation Technology System Based on Artificial Intelligence[J]. Railway Transport and Economy，2024，46(1)：1-9.

[5] CAPRARA A， FISCHETTI M， TOTH P. Modeling and Solving the Train Timetabling Problem[J]. Operations Research，2002，50(5)：851-861.

[6] VANSTEENWEGEN P， DEWILDE T， BURGGRAEVE S，et al. An Iterative Approach for Reducing the Impact of Infrastructure Maintenance on the Performance of Railway Systems[J]. European Journal of Operational Research，2016，252(1)：39-53.

[7] YANG L X， QI J G， LI S K，et al. Collaborative Optimization for Train Scheduling and Train Stop Planning on High Speed Railways[J]. Omega，2016，64：57-76.

[8] YUE Y X， WANG S F， ZHOU L S，et al. Optimizing Train Stopping Patterns and Schedules for High Speed Passenger Rail Corridors[J]. Transportation Research Part C：Emerging Technologies，2016，63：126-146.

[9] ZHOU X S， ZHONG M. Single-Track Train Timetabling with Guaranteed Optimality：Branch-and-Bound Algorithms with Enhanced Lower Bounds[J]. Transportation Research Part B：Methodological，2007，41(3)：320-341.

[10] 孙　焰，李致中. 单线区段货物列车运行图的一种优化方法[J]. 铁道学报，1991，13(1)：60-71.

[11] SUN Yan， LI Zhizhong. A Method of Optimizing Wagon Diagram for Single-Track Line[J]. Journal of the China Railway Society，1991，13(1)：60-71.

[12] SZPIGEL B ．Optimal Train Scheduling on a Single Track Railway[J]．Operational Research，1973，72(1)：343-352.

[13] YANG L X， ZHOU X S. Constraint Reformulation and a Lagrangian Relaxation-Based Solution Algorithm for a Least Expected Time Path Problem[J]. Transportation Research Part B：Methodological，2014，59：22-44.

[14] ZHANG Y X， PENG Q Y， YAO Y，et al. Solving Cyclic Train Timetabling Problem through Model Reformulation：Extended Time-Space Network Construct and Alternating Direction Method of Multipliers Methods[J]. Transportation Research Part B：Methodological，2019，128：344-379.

[15] CACCHIANI V， CAPRARA A， TOTH P. A Column Generation Approach to Train Timetabling on a Corridor[J]. 4OR，2008，6(2)：125-142.

[16] NACHTIGALL K. Periodic Network Optimization with Different Arc Frequencies[J]. Discrete Applied Mathematics，1996，69(1-2)：1-17.

[17] 牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息，2021，21(5)：114-124.

[18] NIU Huimin. Literature Review on Rail Train Timetabling Problems[J]. Journal of Transportation Systems Engineering and Information Technology，2021，21(5)：114-124.

[19] AMIT I， GOLDFARB D ．The Timetable Problem for Railways[J]．Developments in Operations Research，1971，2：379-387.

[20] 史　峰，黎新华，秦　进，等. 单线列车运行图铺划的时间循环迭代优化方法[J]. 铁道学报，2005，27(1)：1-5.

[21] SHI Feng， LI Xinhua， QIN Jin，et al. A Timing-Cycle Iterative Optimizing Method for Drawing Single-Track Railway Train Diagrams[J]. Journal of the China Railway Society，2005，27(1)：1-5.

[22] 彭其渊，杨明伦，聂勋煌. 单线区段实用货物列车运行图的优化模型及算法[J]. 铁道学报，1995，17(3)：15-20.

[23] PENG Qiyuan， YANG Minglun， NIE Xunhuang. Optimization Model and Its Algorithm for Making-Wagon Diagram on Single-Track Lines[J]. Journal of the China Railway Society，1995，17(3)：15-20.

[24] 彭其渊，朱松年，王　培. 网络列车运行图的数学模型及算法研究[J]. 铁道学报，2001，23(1)：1-8.

[25] PENG Qiyuan， ZHU Songnian， WANG Pei. Study on a General Optimization Model and Its Solution for Railway Network Train Diagram[J]. Journal of the China Railway Society，2001，23(1)：1-8.

[26] HIGGINS A ．Optimisation of Train Schedules to Minimise Transit Time and Maximise Reliability[D]．Queensland University of Technology，1996.

[27] HÖGDAHL J， BOHLIN M. A Combined Simulation-Optimization Approach for Robust Timetabling on Main Railway Lines[J]. Transportation Science，2023，57(1)：52-81.

[28] VROMANS M J C M， DEKKER R， KROON L G. Reliability and Heterogeneity of Railway Services[J]. European Journal of Operational Research，2006，172(2)：647-665.

[29] PARBO J， NIELSEN O A， PRATO C G. Passenger Perspectives in Railway Timetabling：A Literature Review[J]. Transport Reviews，2016，36(4)：500-526.

[30] ANDERSSON E V， PETERSON A， TÖRNQUIST KRASEMANN J. Quantifying Railway Timetable Robustness in Critical Points[J]. Journal of Rail Transport Planning & Management，2013，3(3)：95-110.

[31] SOLINEN E， PALMQVIST C W. Development of New Railway Timetabling Rules for Increased Robustness[J]. Transport Policy，2023，133：198-208.

[32] DEWILDE T， SELS P， CATTRYSSE D，et al. Improving the Robustness in Railway Station Areas[J]. European Journal of Operational Research，2014，235(1)：276-286.

[33] BEŠINOVIĆ N， GOVERDE R M P， QUAGLIETTA E，et al. An Integrated Micro-Macro Approach to Robust Railway Timetabling[J]. Transportation Research Part B：Methodological，2016，87：14-32.

[34] CACCHIANI V， TOTH P. Nominal and Robust Train Timetabling Problems[J]. European Journal of Operational Research，2012，219(3)：727-737.

[35] LEE Y， LU L S， WU M L，et al. Balance of Efficiency and Robustness in Passenger Railway Timetables[J]. Transportation Research Part B：Methodological，2017，97：142-156.

[36] LIEBCHEN C， LÜBBECKE M， MÖHRING R，et al ．The Concept of Recoverable Robustness，Linear Programming Recovery，and Railway Applications[M]．Berlin：Springer Berlin Heidelberg，2009.

[37] 刘　敏，韩宝明. 列车运行图可恢复鲁棒性优化模型[J]. 铁道学报，2013，35(10)：1-8.

[38] LIU Min， HAN Baoming. Recoverable Robust Timetabling Models for Railways[J]. Journal of the China Railway Society，2013，35(10)：1-8.

[39] 黄　鉴，彭其渊. 基于分时客运需求的客运专线列车运行图优化[J]. 铁道科学与工程学报，2012，9(6)：66-71.

[40] HUANG Jian， PENG Qiyuan. Train Diagram Optimization of Passenger Dedicated Line Based on Passenger Transport Demand in Different Time[J]. Journal of Railway Science and Engineering，2012，9(6)：66-71.

[41] BARRENA E， CANCA D， COELHO L C，et al. Exact Formulations and Algorithm for the Train Timetabling Problem with Dynamic Demand[J]. Computers & Operations Research，2014，44：66-74.

[42] BARRENA E， CANCA D， COELHO L C，et al. Single-Line Rail Rapid Transit Timetabling under Dynamic Passenger Demand[J]. Transportation Research Part B：Methodological，2014，70：134-150.

[43] NIU H M， ZHOU X S， GAO R H. Train Scheduling for Minimizing Passenger Waiting Time with Time-Dependent Demand and Skip-Stop Patterns：Nonlinear Integer Programming Models with Linear Constraints[J]. Transportation Research Part B：Methodological，2015，76：117-135.

[44] 李天琦，聂　磊，谭宇燕. 基于换乘接续优化的高铁周期性列车运行图编制研究[J]. 铁道学报，2019，41(3)：10-19.

[45] LI Tianqi， NIE Lei， TAN Yuyan. Study on Cyclic Timetable Generation of High Speed Rail Based on Transfer Connection Optimization[J]. Journal of the China Railway Society，2019，41(3)：10-19.

[46] 周文梁，张先波，屈林影，等. 基于客流均衡分析的城际铁路列车运行图优化[J]. 铁道科学与工程学报，2019，16(1)：231-238.

[47] ZHOU Wenliang， ZHANG Xianbo， QU Linying，et al. Optimization of Intercity Railway Train Schedule Based on Passengers Equilibrium Analysis[J]. Journal of Railway Science and Engineering，2019，16(1)：231-238.

[48] TIAN X P， NIU H M. Optimizing Train Timetable under Oversaturated Demand Conditions：A Variable-Splitting Lagrangian Approach for Big-M Constraints[J].IEEE Transactions on Intelligent Transportation Systems，2024，25(7)：7265-7280.

[49] 高如虎，牛惠民，杨喜梅. 面向时变需求的高铁快运专列时刻表和配装方案综合优化研究[J]. 交通信息与安全，2020，38(4)：122-131.

[50] GAO Ruhu， NIU Huimin， YANG Ximei. Coordinating Train Timetable and Demand Assignment for Express Delivery with High Speed Railway with Time-Dependent-Oriented Demand[J]. Journal of Transport Information and Safety，2020，38(4)：122-131.

[51] QI J G， ZHOU Y R， MENG F T，et al. Joint Optimization of Train Stop Planning and Timetabling with Time-Dependent Passenger and Freight Demands in High Speed Railway[J]. Transportation Research Part C：Emerging Technologies，2025，172：105025.

[52] 杨皓男，倪少权，潘金山，等. 铁路天窗方案与列车运行图协同优化研究综述[J]. 铁道运输与经济，2024，46(11)：71-81.

[53] YANG Haonan， NI Shaoquan， PAN Jinshan，et al. Integrated Optimization of Railway Maintenance Window Plan and Train Working Diagram[J]. Railway Transport and Economy，2024，46(11)：71-81.

[54] 周文梁，史　峰，陈　彦，等. 客运专线网络列车开行方案与运行图综合优化方法[J]. 铁道学报，2011，33(2)：1-7.

[55] ZHOU Wenliang， SHI Feng， CHEN Yan，et al. Method of Integrated Optimization of Train Operation Plan and Diagram for Network of Dedicated Passenger Lines[J]. Journal of the China Railway Society，2011，33(2)：1-7.

[56] 田小鹏，牛惠民，韩　瑛. 面向需求的城际列车时刻表与停站方案同步优化[J]. 交通运输系统工程与信息，2023，23(2)：197-207.

[57] TIAN Xiaopeng， NIU Huimin， HAN Ying. Collaborative Optimization of Demand-Oriented Train Timetabling and Stop Planning for Intercity Railways[J]. Journal of Transportation Systems Engineering and Information Technology，2023，23(2)：197-207.

[58] 韩　涛，魏玉光，王怀相，等 ．铁路集装箱客运化班列停站方案与运行图协同优化研究[J]．铁道科学与工程学报，2024，21(1)：82-93.

[59] HAN Tao， WEI Yuguang， WANG Huaixiang，et al ．Integrated Optimization of Stop Planning and Timetabling for Railway Container Trains under Passenger Transport Mode [J]．Journal of Railway Science and Engineering，2024，21(1)：82-93.

[60] 徐长安，倪少权，陈钉均. 基于两阶段算法的运行图与天窗协同优化[J]. 西南交通大学学报，2020，55(4)：882-888.

[61] XU Chang'an， NI Shaoquan， CHEN Dingjun. Collaborative Optimization for Timetable and Maintenance Window Based on Two-Stage Algorithm[J]. Journal of Southwest Jiaotong University，2020，55(4)：882-888.

[62] 聂　磊，胡必松，付慧伶，等 ．客运专线夜间行车与天窗的相互影响分析[J]．交通运输系统工程与信息，2010，10(5)：66-72.

[63] NIE Lei， HU Bisong， FU Huiling，et al ．Interaction Analysis between Night Train Operation and Maintenance Time on Passenger Dedicated Railway Line[J]．Journal of Transportation Systems Engineering and Information Technology，2010，10(5)：66-72.

[64] LUAN X， MIAO J， MENG L，et al ．Integrated Optimization on Train Scheduling and Preventive Maintenance Time Slots Planning[J]．Transportation Research Part C：Emerging Technologies，2017，80(7)：329-359.

[65] 石　贇，牟海波，黄志鹏，等 ．考虑跨线列车的运行图与天窗一体化模型与算法[J]．铁道科学与工程学报，2024，21(5)：1761-1773.

[66] SHI Yun， MU Haibo， HUANG Zhipeng，et al ．Integrated Optimization Model and Algorithm for Timetable and Maintenance Window Considering Cross-Line Trains[J]．Journal of Railway Science and Engineering，2024，21(5)：1761-1773.

[67] 张天伟，梁　巍，佟　璐 ．高速铁路夜行列车运行与天窗设置协同优化线性规划模型[J]．铁道学报，2024，24(6)：1-14.

[68] ZHANG Tianwei， LIANG Wei， TONG Lu ．Linear Programming Collaborative Optimization Model on Operation of Over-Night Train and Setting of Maintenance Time Window[J]．Journal of the China Railway Society，2024，24(6)，1-14.

[69] CHEN R， ZHOU L， YUE Y，et al ．The Integrated Optimization of Robust Train Timetabling and Electric Multiple Unit Circulation and Maintenance Scheduling Problem[J]．Advances in Mechanical Engineering，2018，10(3)：1-16.

[70] 王　超，王淑姗，王　鹏，等 ．高速铁路列车运行图与动车组运用一体化优化模型与算法研究[J]．铁道运输与经济，2018，40(9)：92-97.

[71] WANG Chao， WANG Shushan， WANG Peng，et al ．A Study on the Optimization Model and Algorithm for the Integration of High Speed Train Operating Diagram and EMU Utilization[J]．Railway Transport and Economy，2018，40(9)：92-97.

[72] 史　峰，魏堂建，周文梁，等 ．考虑动车组周转和到发线运用的高速铁路列车运行图优化方法[J]．中国铁道科学，2012，33(2)：1-8.

[73] SHI Feng， WEI Tangjian， ZHOU Wenliang，et al ．Optimization Method for Train Diagram of High Speed Railway Considering the Turn over of Multiple Units and the Utilization of Arrival-Departure Tracks[J]．China Railway Science，2012，33(2)：1-8.

[74] LI W J， NIE L ．Coordinated Optimisation Problem Integrating EMU Circulation and Timetabling for High Speed Railway[J]．IET Intelligent Transport Systems，2017，11(10)：695-704.

[75] CAREY M， CRAWFORD I ．Scheduling Trains on a Network of Busy Complex Stations[J]．Transportation Research Part B：Methodological，2007，41(26)：159-178.

[76] BACH L， GENDREAU M， WOHLK S ．Freight Railway Operator Timetabling and Engine Scheduling[J]．European Journal of Operational Research，2015，241(2)：309-319.

[77] 杨立兴，王恩泰，高自友，等 ．一种城市轨道交通网络列车运用与乘务计划协同优化方法：CN119313067A[P]．2025-01-14.

[78] BURDETT R， KOZAN E ．A Sequencing Approach for Creating New Train Timetables[J]．OR Spectrum，2010，32(1)：163-193.

[79] 许　红，马建军，龙建成 ．客运专线列车运行图编制模型及计算方法的研究[J]．铁道学报，2007，29(2)：1-7.

[80] XU Hong， MA Jianjun， LONG Jiancheng ．Research on the Model and Algorithm of the Train Working Diagram of Dedicated Passenger Line[J]．Journal of the China Railway Society，2007，29(2)：1-7.

[81] GOVERDE R， BEŠINOVIĆ N， BINDER A，et al ．A Three-Level Framework for Performance-Based Railway Timetabling[J]．Transportation Research Part C：Emerging Technologies，2016，67：62-83.

[82] ZHANG Y， ARIANO A， HE B，et al ．Microscopic Optimization Model and Algorithm for Integrating Train Timetabling and Track Maintenance Task Scheduling[J]．Transportation Research Part B：Methodological，2019，127：237-278.

[83] AN L， MENG X， GAO R，et al ．Optimization of High Speed Railway Train Timetabling Based on Lagrange Relaxation and Fuzzy Subgradient Optimization[J]．IAENG International Journal of Applied Mathematics，2024，54(5)：877-886.

[84] SERAFINI P， UKOVICH W ．A Mathematical Model for Periodic Scheduling Problems[J]．SIAM Journal on Discrete Mathematics，1989，2(4)：550-581.

[85] VOORHOEVE M ．Rail Scheduling with Discrete Sets[R].Netherlands：Eindhoven University of Technology，1993.

[86] PEETERS L ．Cyclic Railway Timetable Optimization[D]．Rotterdam：The Netherlands TRAIL Research School，2003.

[87] LIEBCHEN C， PEETERS L ．Integral Cycle Bases for Cyclic Timetabling[J]．Discrete Optimization，2009，6(1)：98-109.

[88] LIEBCHEN C， WAGNER F ．Performance of Algorithms for Periodic Timetable Optimization[M]．Berlin：Springer Berlin Heidelberg，2008.

[89] 汪　波，杨　浩，牛　丰，等 ．周期运行图编制模型与算法研究[J]．铁道学报，2007，29(5)：1-6.

[90] WANG Bo， YANG Hao， NIU Feng，et al ．Study on Model and Algorithm of Periodic Train Diagram Generation[J]．Journal of the China Railway Society，2007，29(5)：1-6.

[91] 谢美全，聂　磊 ．周期性列车运行图编制模型研究[J]．铁道学报，2009，31(4)：7-13.

[92] XIE Meiquan，NIE Lei，Model of Cyclic Train Timetable[J]．Journal of the China Railway Society，2009，31(4)：7-13.

[93] 郭根材，聂　磊，佟　璐，等 ．基于备选列车接续的周期性列车运行图编制模型研究[J]．铁道学报，2016，38(8)：8-15.

[94] GUO Gencai， NIE Lei， TONG Lu，et al ．A New Cyclic Timetabling Model for Potential Connections[J]．Journal of the China Railway Society，2016，38(8)：8-15.

[95] 李得伟，丁世顺 ．基于改进的PESP模型编制高速铁路周期性列车运行图的研究[J]．中国铁道科学，2017，38(1)：132-137.

[96] LI Dewei， DING Shishun ．Research on Establishment of Periodic Train Working Diagram for High Speed Railway Based on Improved PESP Model[J]．China Railway Science，2017，38(1)：132-137.

[97] 张　新，范家铭，王宝杰，等 ．面向能力运用的京沪高速铁路列车停站方案与运行图协同优化研究[J]．铁道运输与经济，2022，44(10)：1-8.

[98] ZHANG Xin， FAN Jiaming， WANG Baojie，et al ．Collaborative Optimization of Train Stop Plan and Timetable of Beijing-Shanghai High Speed Railway Based on Capacity Utilization[J]．Railway Transport and Economy，2022，44(10)：1-8.

[99] 李海琳，聂　磊，付慧伶 ．高速铁路周期化运行图列车开行模式优化设计[J]．铁道学报，2023，45(8)：18-26.

[100] LI Hailin， NIE Lei， FU Huiling ．Optimal Design of Train Operation Mode of High Speed Railway Cyclic Timetable[J]．Journal of the China Railway Society，2023，45(8)：18-26.

[101] CACCHIANI V， GALLI L， TOTH P ．A Tutorial on Non-Periodic Train Timetabling and Platforming Problems[J]．EURO Journal on Transportation and Logistics，2015，4(3)：285-320.

[102] LIU L， DESSOUKY M ．Stochastic Passenger Train Timetabling Using a Branch and Bound Approach[J]．Computers & Industrial Engineering，2019，127：1223-1240.

[103] MARTIN B， ROPKE S ．A Column-Generation-Based Matheuristic for Periodic and Symmetric Train Timetabling with Integrated Passenger Routing[J]．European Journal of Operational Research，2022，297(2)：511-531.

[104] TIAN X P， NIU H M ．Optimization of Demand-Oriented Train Timetables under Overtaking Operations：A Surrogate-Dual-Variable Column Generation for Eliminating Indivisibility[J]．Transportation Research Part B：Methodological，2020，142：143-173.

[105] 兰泽康，何世伟，黎浩东，等 ．考虑维修天窗和到发线数量的复线铁路列车运行图优化[J]．北京交通大学学报，2018，42(3)：30-36.

[106] LAN Zekang， HE Shiwei， LI Haodong，et al ．Optimization for Double-Track Railway Train Timetabling Considering the Maintenance Skylight and the Number of Arrival-Departure Tracks[J]．Journal of Beijing Jiaotong University，2018，42(3)：30-36.

[107] 廖正文 ．基于资源的铁路运输能力理论与计算方法[D]．北京：北京交通大学，2021.

[108] HE B S， SONG R， HE S W，et al ．High Speed Rail Train Timetabling Problem：A Time-Space Network Based Method with an Improved Branch-and-Price Algorithm[J]．Mathematical Problems in Engineering，2014，2014(1)：1-15.

[109] WANG J， ZHOU L S， YUE Y X，et al ．Optimizing High Speed Railroad Timetable with Passenger and Station Service Demands：A Case Study in the Wuhan-Guangzhou Corridor[J]．Journal of Advanced Transportation，2018，2018：1-18.

[110] 周政铎，周　黎，李　博 ．面向旅客到达晚点最小的高速铁路列车运行图冗余时间布局优化研究[J]．铁道运输与经济，2023，45(2)：25-32.

[111] ZHOU Zhengduo， ZHOU Li， LI Bo ．Optimization of Buffer Time Layout of High Speed Railways' Train Working Diagram for Minimizing Passengers' Arrival Delay[J]．Railway Transport and Economy，2023，45(2)：25-32.

[112] 王仲峰，张　巍，高　林，等 ．遗传算法在编制列车运行图中的运用[J]．铁道运输与经济，2005，27(4)：82-84.

[113] WANG Zhongfeng， ZHANG Wei， GAO Lin，et al ．The Application of Genetic Algorithm in Establishing Train Diagram[J]．Railway Transport and Economy，2005，27(4)：82-84.

[114] 史　峰，黄铮诚，周文梁，等 ．基于用户平衡分析的旅客列车始发时间分布优化[J]．铁道科学与工程学报，2008，5(6)：69-75.

[115] SHI Feng， HUANG Zhengcheng， ZHOU Wenliang，et al ．Optimization on Departure Time Distribution of Passenger Trains Based on User Equilibrium Analysis[J]．Journal of Railway Science and Engineering，2008，5(6)：69-75.

[116] 简　星，闫海峰，张守帅 ．基于能力利用的高速铁路列车停站方案优化模型[J]．交通运输工程与信息学报，2019，17(2)：146-152.

[117] JIAN Xing， YAN Haifeng， ZHANG Shoushuai ．High Speed Railway Stopping Schedule Optimization Model Based on Capacity Utilization[J]．Journal of Transportation Engineering

[118] Information and，2019，17(2)：146-152.

[119] LI W Q， NI S Q ．Train Timetabling with the General Learning Environment and Multi-Agent Deep Reinforcement Learning[J]．Transportation Research Part B：Methodological，2022，157(3)：230-251.

[120] KHADILKAR H ．A Scalable Reinforcement Learning Algorithm for Scheduling Railway Lines[J]．IEEE Transactions on Intelligent Transportation Systems，2019，20(2)：727-736.

[121] 范文天，曾勇程，郭一唯，等 ．基于强化学习的高铁列车运行图编制模型优化方法研究[J]．铁道运输与经济，2025，47(1)：70-81.

[122] FAN Wentian， ZENG Yongcheng， GUO Yiwei，et al ．Optimization Method of Train Working Diagram Compilation Model of High Speed Railways Based on Reinforcement Learning[J]．Railway Transport and Economy，2025，47(1)：70-81.

[123] 张春田，戚建国，杨　凯，等 ．基于两阶段分布鲁棒优化的列车停站方案与时刻表协同研究[J]．控制与决策，2023，38(4)：1065-1073.

[124] ZHANG Chuntian， QI Jianguo， YANG Kai，et al ．Two-Stage Distributionally Robust Optimization for Integrated Train Stop Planning and Timetabling[J]．Control and Decision，2023，38(4)：1065-1073.

[125] 高珅盈泽，张玉召，冀　璇 ．高速列车运行图节能优化研究现状及展望[J]．铁道运输与经济，2024，46(8)：24-36.

[126] GAO Shenyingze， ZHANG Yuzhao， JI Xuan ．Research Status and Prospects of Energy-Saving Optimization on High Speed Train Timetable[J]．Railway Transport and Economy，2024，46(8)：24-36.

[127] JIANG F， CACCHIANI V， TOTH P ．Train Timetabling by Skip-Stop Planning in Highly Congested Lines[J]．Transportation Research Part B：Methodological，2017，104：149-174.

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(P2024X007)

中国铁道科学研究院集团有限公司科研项目(2023YJ160)