列车运行图的编制问题是轨道交通系统组织的核心问题之一，是轨道交通系统运行的基础。以高铁为例，高铁运营特点是运行速度、开行密度、正点率、安全性等均处于“高点”状态。同时，高铁车站技术作业简单，与传统既有线路相比，高速铁路上开行的动车组拥有双向运行能力，列车到站后不需要进行机车的摘挂、转向等作业，也不必每次都入库检修，故高铁列车停站时间较短。列车运行图上预留的施工、检修等时间称为“天窗”。我国高铁一般只在白天运营，晚上则对线路、供电设备、信号设备以及动车组进行施工或检修。高铁一般利用凌晨0点至6点检修，称为“矩形天窗”。

对于城市轨道交通来说，地铁的行车指挥工作交由控制中心（operating control center，OCC）负责。OCC是地铁运营生产的调度指挥部门，指挥管理每条地铁线路的行车、电力、消防、环控等工作，并负责运营突发事件的应急处理。随着地铁路网密度的加大以及逐年攀升的客流量，行车调度指挥效率显得越发重要。

广泛应用于我国地铁信号系统的列车运行图就是利用坐标原理对列车运行的时间与空间关系进行图解的实例。它规定了各次列车占用区间的顺序、列车在一个车站到达和出发的时刻、列车区间运行时分、站停时分、折返作业时间等，是行车组织工作的基础。

总之，在编制列车运行图时，需要综合考虑地铁线路的列车运行参数、线路参数、信号系统行车能力、客流分布情况等因素。其中，前三个因素属于固定因素，一旦地铁线路建成，一般不会有变动；最后一个客流分布因素则会随着运营而出现变化，属于变动因素。客流分布的变化既可以是空间分布的变动，也可以是时间分布的变动。一条线路开通后，会随着网络化线路的完善或者线路周边的发展变化，出现客流的调整。比如，从单一线路的运营发展到网络化运营时，路网换乘站的客流将会明显增加。再比如，线路上的某个车站开通初期由于与周边商业中心等建筑物有结建关系，只能开放部分出入口。当远期车站出入口全部开放后，由于这些商业中心的带动，也会增加车站的客流。根据多年的运营经验，乘客集中出行的时间在一周内呈现工作日与周末不同的分布特点，在一天内也会有早高峰、晚高峰、平峰的分布特点。

在制订运行图时，在固定因素一定的情况下，需要充分考虑客流需求，力争使运行图提供的运能与实际需求相匹配，最大化地铁的社会效益。

1.列车运行图表示法

列车运行图是在坐标轴内对列车运行过程的一种图解表示，它规定了列车占用区间的顺序，以及列车在各个车站的出发、到达或者通过时刻。具体的图解形式有两种：一种用横坐标代表距离，纵坐标代表时间，欧洲国家主要使用这种形式；另一种用横坐标代表时间，纵坐标代表距离，我国采用的是这种表示方法。

在我国列车运行图中，规定不同种类的列车使用不同符号和颜色表示，其中旅客列车用红单线表示。根据具体使用情况的不同，列车运行图的时间划分格式也不相同，主要有三种格式：

（1）二分格运行图。相邻（细）竖线间隔为2 min，其中小时格的竖线（如1、2、3…）较粗，主要用于新运行图的编制，如图5-1所示。

（2）十分格运行图。相邻竖线间隔为10 min，其中半小时格为虚线，小时格为较粗竖线，主要用于日常调度工作中调度调整计划的编制以及实绩运行图的绘制，如图5-2所示。

（3）小时格运行图。相邻竖线间隔为1 h，主要用于机车周转图和旅客列车方案的编制，如图5-3所示。

图5-1　列车二分格运行图

图5-2　列车十分格运行图

图5-3　列车小时格运行图

图5-1至图5-3中，1、2、3…表示小时（h），A、B…表示列车所经过的车站或线路中心线，斜线表示列车运行线。

2.列车运行基本要素

列车运行图的基本要素包括列车区间运行时分、列车在中间站的停站时间、折返站停留时间、起停车附加时分、车站间隔时间、追踪列车间隔时间、维修天窗开设时间［59］。

1）列车区间运行时分

列车区间运行时分是指列车在两相邻车站（线路所）之间的运行时间标准。一般由机务部门采用牵引计算和实际试验相结合的方法进行查定，按车站中心线或线路所通过信号机之间的距离计算。列车运行时分应按照列车上下行方向分别查定，同时还应区分列车在每一区间两个车站上不停车通过和停车通过两种情况。列车不停车通过两个相邻车站所需的区间运行时分称为纯运行时分。

2）列车在中间站的停站时间

列车在中间站的停站时间指列车在中间站上办理必要作业所停留的最小时间，主要包括在中间站办理相关技术作业时间、办理客运作业时间、列车待避等待时间等。

3）折返站停留时间

折返站停留时间是指机车在折返站办理必要作业所需要的最小时间。折返站停留时间标准需要机务部门根据折返站作业内容和流程，采用作业过程分析和实际查标相结合的方法确定。

4）起停车附加时分

起停附加时分是指由于列车启动或者停车而使区间运行时分比纯区间运行时分延长的时分。编制列车运行图时，一般列车的起停附加时分都是给定的常量，其值根据实际情况牵引计算确定。

5）车站间隔时间

车站间隔时间是指在车站上相邻两列车的到达、出发或通过作业所需要的最小间隔时间。在确定车站间隔时间时，应遵守有关规章的规定及车站技术作业时间标准，以保证行车安全和最有效地利用区间通过能力。

6）追踪列车间隔时间

追踪列车间隔时间是指追踪运行的两列车之间的最小间隔时间。追踪列车间隔时间的确定取决于列车的起动制动性能、列车控制系统的技术、车站信联闭设备、线路的坡度等因素。

7）维修天窗开设时间

维修天窗时间是指用于检修维护车辆、机车及线路等铁路技术设备所用的时间。高速铁路的天窗时间一般安排在0：00—6：00之间，白天一般不设置固定维修天窗。

3.列车运行图编制基本要求

1）确保行车安全

列车运行图的编制必须符合铁路相关规定，严格执行各项技术作业程序，严格遵守各种作业时间标准。

2）适应市场需求

高效便捷运输旅客：客运部门研究提出运行图运行期间的客流密度预测、列车开行方案、动车组交路计划、停站完成旅客乘降或其他技术作业的时间标准。

3）充分利用铁路通过能力

合理运用动车组：列车运行线的铺划应尽量减少不必要的停车时间，努力提升列车的旅行速度；要经济合理地运用动车组，使之发挥出最大的效益。

4）确保列车运行图的调整弹性

编制列车运行图时，合理控制区间通过能力利用率，保证列车运行图具有调整弹性，满足列车运行秩序发生变化时的调整需求。

5）保证列车分布与客流需求相适应

列车运行线的数量及分布需以旅客需求为基础，最大化地满足旅客需求，同时，列车运行图的编制还需具有一定的预见性，对市场需求的发展变化进行预测，以便提高运输效率。

6）实现车站与区间列车均衡运行

列车运行图的编制要考虑列车运行的均衡性，尽量做到各时间段内车站列车均衡到发，以充分利用车站到发线及区间通过能力，提高铁路运输能力。

7）合理安排工作人员作息时间

合理安排列车工作人员的作息时间，保证工作人员的良好精神状态，是保障列车安全运行的重要环节。

4.列车运行数学模型

在列车运行数学模型中，首先必须对模型进行假设，再明确约束条件，最后确定目标函数。以高铁运行为例展开介绍。(www.daowen.com)

1）模型假设

（1）适用于单条复线高速铁路，线路上开行不同等级的列车。

（2）假设高速铁路上行方向和下行方向的列车相互完全独立，彼此之间不会影响，建模时只需考虑单个方向。

（3）假设单个方向线路上的所有车站均可以同时接发列车。

（4）只考虑列车在单个方向线路上经过的径路。

（5）同向列车在区间运行时，假设同等级列车不发生越行，高等级列车可以越行低等级列车，低等级在一个车站最多被越行两次。

（6）高铁列车开行方案的数据（包括开行区间、列车等级、列车数量、停站方案等）都是确定且已知的，车站的到发线数量也是已知的。

（7）列车运行的各类安全间隔时间标准、在车站的时间起停附加时分、停站时间、区间纯运行时分等都是已知的，且同等级标准一致。

（8）忽略列车运行图铺划时考虑的一些因素，例如动车组运用车底数、客流变化、换乘需求等。

2）约束条件

（1）列车通过区间顺序约束。必须按照规定的区间先后顺序运行，即

式中，表示列车在车站的到达时刻，表示列车在车站的出发时刻。l∈L表示列车经过车站的集合，L表示线路中所有列车集合，L=｛l1，l2，l3，…，ln｝；s∈rl，rl=｛|1≤i≤ml，l∈L，∈S｝；S表示线路上的车站集合，S=｛s1，s2，s3，…，sm｝。

（2）列车发车间隔约束。列车运行时，某一闭塞区间在同一时间最多允许一辆列车进入，即列车同向运行时，后行列车lj需要在前行列车li出发运行一段时间之后才能出发，即前后列车应该满足一定的发车间隔。

（3）列车到达间隔约束。同向列车运行时，前行列车li与后行列车lj应该满足一定的到达间隔。

（4）列车区间运行时分约束。规定列车在区间的实际运行时间需要大于或等于标准的列车区间运行时分。列车区间运行时分包括纯运行时分和起停车附加时分。

（5）车站停站时间约束。规定列车在车站停留时间，一方面应不小于满足旅客乘降作业及相应技术作业所需的最小停车时间下限，另一方面为了不影响后续列车及提高运行图效率，不能超过停车时间的上限。

（6）天窗时间约束。由于高速铁路采用夜间维修的矩形天窗，在天窗范围内不允许行车。

（7）发车时间范围约束。列车的发车时间要受到有效时间带的制约，不同开行方案的列车，其合理的发车范围也会有区别，尤其对于跨线列车，需要考虑其合理开行时间范围。

（8）车站到发线约束。在列车运行过程中，列车占用的到发线数量均不得超过该站用于接发该类列车的到发线数量。

（9）越行约束。在后行高等级列车lj的速度大于前行低等级列车li时，高等级列车需要越行低等级列车。

3）目标函数

铁路出行需求从提高运行图运输能力的角度，以极小化列车运行线占用运行图时间为优化目标。列车运行线占用运行图时间是指列车在各车站占用时间之和的最大值。

用分别表示车站s的最早到达时间、最晚到达时间、最早发车时间、最晚发车时间。则最早和最晚占用车站的时间分别为

则优化目标列车运行线占用运行图时间最少min Z1可以表示为

为了提高编图质量，应尽可能减少列车总旅途时间，故一个优化目标为极小化列车总旅途时间min Z2为

式中，下标ml表示列车途经车站数量，表示列车的始发站，表示列车的终到站。

对于多目标优化问题，可以采用目标加权的方法，给不同的优化目标函数赋予不同的权重系数ω1、ω2，将多目标优化问题转化为单目标优化问题。模型的总体目标函数为

5.模型求解基本算法

算法可以归纳为两大类：确定性最优化方法；启发式方法。

确定性优化方法是指以传统的数学规划方法为基础，运用运筹学理论来建立数学模型，对模型进行精确求解从而获得最优解的方法。此类算法通常都是基于枚举思想，通过全局搜索来获得最优解，对于规模较小的调度问题能够取得比较满意的结果，但是对于较大规模的复杂调度问题，全局搜索的计算量会十分巨大，很难求得满意的结果，比较常用的有分支定界法和动态规划法等。

启发式方法是以启发推理为基础，通过局部搜索或邻域搜索的方式来获得最优解。常用的方法有遗传算法、禁忌搜索算法、模拟退火算法、神经网络算法等。

1）遗传算法特点

遗传算法是一种根据自然界遗传选择和自然淘汰的生物进化过程而发展起来的高度并行、随机、自适应搜索算法［60］。遗传算法基本思想是“适者生存”，将问题的解表示成“染色体”，通过对染色体群进行一系列的遗传操作，使之一代代不断进化，最终得到“最适应环境”的个体，即为问题的最优解。由于其思想简单、易于实现以及表现出来的鲁棒性，使得遗传算法作为重要的智能计算技术，在科学研究、生产制造等众多领域广泛应用。

遗传算法作为一种通用的搜索算法，具有一般搜索算法的基本特征：首先产生初始候选解；根据约束条件来计算候选解的适应度值；根据适应度值选择留下某些候选解，舍弃其他候选解；通过对留下的候选解进行操作，产生新的候选解。

遗传算法将一般搜索算法的基本特征以特殊的方式组合在一起，使之与普通搜索算法区别开来，形成了其独有的特点：

（1）遗传算法对问题参数的编码进行操作。传统的优化算法一般对问题参数的实际值进行计算，而遗传算法是对问题参数的某种形式的编码进行运算处理，算法本身具有高度的灵活性，能在广泛的问题求解中发挥作用。

（2）遗传算法从问题解集开始搜索，而不是从单一解开始。其具有并行搜索特性和自适应性。传统算法一般是从单个初始解开始进行搜索，但是容易进入局部极值点且效率不高。遗传算法则是从多个个体组成的初始解群开始进行搜索，搜索范围广，可以有效避免进入局部极值点，能够更好地进行全局择优。

（3）遗传算法直接以适应度作为搜索信息，不需要其他辅助信息。传统搜索算法为了确定搜索方向，除了需要目标函数值外，还需要一些辅助信息（如目标函数导数值等）。遗传算法主要根据适应度来确定搜索方向，而个体适应度的计算可以不依靠目标函数的精准估值，具有广泛的应用范围。

（4）遗传算法使用概率搜索技术。很多传统搜索算法往往使用确定性的搜索方法，即通过确定的转移关系与方式来转移搜索点，其局限性在于容易陷入局部极值点。遗传算法使用概率搜索机制，具有不确定性，即以一定的概率性来进行选择、交叉、变异等操作，从而扩大搜索范围，具有全局最优性［61］。

2）遗传算法的基本原理及流程

遗传算法解决优化问题时，首先将可行解按照一定规则进行编码形成染色体，然后产生多个初始染色体组成一个初始种群，在此基础上遵循“适者生存，优胜劣汰”的原则进行后续操作。

遗传算法根据个体的适应度值对种群进行筛选，适应度值高的个体被选中的概率更高。同时，通过选择、交叉、变异等操作形成的下一代种群。不断循环迭代，直到满足终止准则时，得到最优解。

遗传算法的一系列操作更好地保持了种群多样性，求解过程不易陷入局部极值点，具有较强的全局搜索能力，优秀个体可以得到保留并不断进化。

遗传算法是通过循环迭代寻找最优解，其基本流程如图5-4所示［62］。

图5-4　遗传算法基本流程图