列车运行图自动生成系统：建模、算法与工程实践拆解

简介：面向铁路调度与交通仿真方向学习者，这份C++源码工程实现了列车运行图自动生成系统的完整设计。系统划分菜单栏与运行图显示两大模块，支持列车时刻表查询、晚点信息登记，并在发生晚点时自动更新时刻表内容、动态调整运行图上的列车斜线；绿线固定表示时间与车站轴线，红蓝斜线则依据时刻表数据实时绘制，直观展示列车交路关系。压缩包共28个文件，含9个cpp与9个h源码文件、工程设计文档、运行说明文本以及演示视频(avi)，整体约8.27MB，既便于阅读核心逻辑，也能通过视频快速了解界面效果。已有3477人学习下载，适合作为课程设计、毕业设计或铁路调度系统入门开发的参考实现，可借此掌握MFC/Windows界面编程与数据联动更新的设计思路。

1. 列车运行图自动生成：从手工铺画到算法出图的跨越

一条城际线，16 个站、40 多对列车，开行方案一旦调整，排图师傅要在图上逐条跑线、反复找冲突、前后腾挪，一版图花两三天是常态，赶上早晚高峰和天窗叠加，返工次数更多。列车运行图自动生成系统的设计，要解决的就是这件事：把线路数据、开行方案、信号间隔这些规则交给程序，由算法自动铺出满足约束的列车运行线和到发时刻，再由调度员在界面上做局部微调。本文会从建模、算法选型、系统架构到实际踩坑记录，完整拆解一个可落地的自动生成系统是怎么做出来的，适合正在规划排图工具、或者想从手工排图切换到自动化流程的团队参考。

2. 先建模还是先铺画：把运行图生成变成可计算的问题

自动生成系统能不能落地，第一道坎不是写算法，而是问题描述。很多团队拿到题目就急着写搜索程序，结果算了半天，连哪些约束没满足都说不清楚。建模阶段要做两件事：把运行图的合法条件变成可校验的约束集合，把“好看、好用”变成可计算的目标函数。这两件事定了，后面的算法和架构才有明确依据。

2.1 核心约束清单：区间运行时分、停站时分与间隔关系

列车运行图本质上是一张时间表：每个列车在每个车站有到达时刻和出发时刻，相邻车站之间有一个由区间运行时分决定的走行时间，车站停站时分决定出发时刻与到达时刻的关系。真正让问题变复杂的，是列车之间的“间隔”约束，这是自动生成系统建模时最重要的部分。

区间运行时分是从设计文件和实绩统计中取的：新车或新线没有历史数据时，用牵引计算出来的理论时分；有实绩数据后，我一般会把 P95 作为下限，再在后续调参阶段加冗余。停站时分则要区分大站小站，大站按客流高峰加额外停留时间，小站只保留最低作业时分。追踪间隔取决于信号系统，不同制式差异很大，建模时把它作为全局参数传入，而不是写死在程序里。

2.2 目标函数怎么设：均衡性、冗余与接续

满足约束只是前提，一张能用的运行图还得“顺眼”。排图师傅的经验里，顺眼意味着：同一方向相邻列车的发车时刻尽量均匀，不要出现两列车挤在一起、后面空一大段的情况；每个站的到发分布不要太集中，否则站台和到发线压力会很大；跨线接续和换乘要留出足够时间，但不是越多越好，接续太松会让旅客等待时间变长。

把这些经验写成目标函数，常见做法是加权求和：发车间隔方差、到发线占用峰值、总旅行时间、接续冗余量，每个项乘一个权重。权重怎么给，不同线路不一样——城际线更看重发车间隔均衡，市域线更看重接续顺畅。建议第一版把权重做成配置文件，而不是写死在代码里，这样系统交付后，排图师傅自己就能调。

需要提醒的是：目标函数不要一上来就追求“全局最优”，那会让求解时间失控。自动生成系统先保证输出可行图，再在可行图集合里做局部优化，这是工程上比较稳妥的路线。排图师傅真正认可一张图，凭的是“看着舒服、改起来方便”，而不是数学上的最优值。

2.3 为什么不能直接套用流水线排程

有人会把列车运行图生成类比成车间作业调度：列车是工件，区间和车站是机器。这个类比在单线上勉强成立，换到多站多交路的网络就失效了。车间调度里，工件之间一般不要求保持严格顺序；列车运行图里，同向列车在同一区间不能越行，前后顺序必须保持不变，这就把问题从“安排开始时间”变成了“安排时间同时安排顺序”。

还有一个差异是空间资源：车间调度里一台机器一次处理一个工件，而车站到发线是成组资源，列车到达、出发、折返会跨多个时间段占用同一组站线；如果只按“机器加工时间”建模，到发线冲突会被完全漏掉。多对列车、多个车站交织在一起，到发事件数量会快速膨胀，超过几千个节点后，精确求解器往往在限时内连可行解都给不出来。所以运行图自动生成系统通常不会直接套用通用调度模板，而是在事件活动图的基础上做定制建模，把时间和空间资源统一表达。

3. 求解算法选型与最小实现：先跑通，再谈最优

建模完成之后，下一步是选求解方法。这个环节最容易犯的错是迷信算法：一听说自动生成，就上遗传算法或强化学习，结果问题定义不清晰，跑了三天三夜产出不可行的图。正确的顺序是先搭一个能跑通的最小框架，把铺画、冲突消解、校验这条链路走通，再根据效果逐步引入更复杂的优化策略。

3.1 精确算法与启发式的边界在哪里

数学模型上，列车运行图生成是一个带大量时间窗和资源约束的整数规划问题。小规模场景——比如单线、三五个车站、十几列车——用数学规划求解器可以在秒级得到最优解；但现实线路往往是几十对列车、十几个车站，到发事件数量轻松过千。事件数量超过几千之后，精确求解器的表现会很不稳定，有时候两小时还在找可行解。

工程上的判断标准我一般这样定：问题规模小、约束相对干净、求解时限宽裕时用精确算法；到发事件超过 3000 个，或者要求秒级出图时，走“约束校验 + 启发式铺画 + 局部搜索”的路子。启发式不保证最优，但能在一个可接受的时间内给出可用的可行图，这对实际生产更重要。两者不是非此即彼，很多系统会把精确算法当作小规模试探工具，或者用来做局部子问题的重优化。

自动生成系统的核心价值是把“能出一版图”的速度从几天压缩到几分钟，所以算法选择的核心指标是“在可用时间内给出可用解”，而不是“最优性”。实战中，我很少遇到有人真的关心 0.5 分钟和 1 分钟最优解的差距，大家更关心：这版图能不能直接交给调度员看，会不会在某个角落藏着一个没查出来的冲突。

3.2 用 Python 跑通一个逐列铺画 + 间隔消解的最小框架

下面给一个最简可运行的示例：单线区段、A 到 B 到 C 三个站，列车按序铺画。每列车给定 A 站出发时刻、AB 区间运行时分、B 站停站时分、BC 区间运行时分。铺画时逐列与前车检查四个位置的最小间隔——A 站出发、B 站到达、B 站出发、C 站到达，任一间隔不满足就把整列车顺延。

# -*- coding: utf-8 -*- # 最小铺画示例：逐列铺画 + 冲突整体顺延 # 时刻统一用"分钟"整数表示，避免浮点误差 def generate_timetable(trains, headway=5): """ trains: 列车列表，每项含 dep 出发分钟、run_ab、dwell_b、run_bc headway: 追踪间隔，单位分钟 返回: 铺画后的到发时刻字典列表 """ timetable = [] # 按出发时刻排序，先铺早发的车 for tr in sorted(trains, key=lambda x: x["dep"]): dep_a = tr["dep"] arr_b = dep_a + tr["run_ab"] dep_b = arr_b + tr["dwell_b"] arr_c = dep_b + tr["run_bc"] # 与所有已铺列车检查间隔，不满足则整体顺延 for prev in timetable: # A 站出发间隔不足 if dep_a - prev["dep_a"] < headway: shift = headway - (dep_a - prev["dep_a"]) dep_a += shift arr_b += shift dep_b += shift arr_c += shift # B 站到达间隔不足 if arr_b - prev["arr_b"] < headway: shift = headway - (arr_b - prev["arr_b"]) dep_a += shift arr_b += shift dep_b += shift arr_c += shift # B 站出发间隔不足 if dep_b - prev["dep_b"] < headway: shift = headway - (dep_b - prev["dep_b"]) dep_a += shift arr_b += shift dep_b += shift arr_c += shift # C 站到达间隔不足 if arr_c - prev["arr_c"] < headway: shift = headway - (arr_c - prev["arr_c"]) dep_a += shift arr_b += shift dep_b += shift arr_c += shift timetable.append({ "id": tr["id"], "dep_a": dep_a, "arr_b": arr_b, "dep_b": dep_b, "arr_c": arr_c, }) return timetable if __name__ == "__main__": trains = [ {"id": "G1001", "dep": 360, "run_ab": 12, "dwell_b": 2, "run_bc": 15}, {"id": "D2002", "dep": 364, "run_ab": 14, "dwell_b": 3, "run_bc": 16}, {"id": "T3003", "dep": 366, "run_ab": 18, "dwell_b": 4, "run_bc": 20}, ] result = generate_timetable(trains, headway=5) for r in result: print(r)

这段代码的逻辑是：按出发时间依次铺画每列车，铺完一辆后与前面所有已铺列车做间隔检查，间隙不够就整列顺延。整体顺延是保守策略，能保证后移后的列车与前车不会再产生新的不满足——因为所有相关时刻都同步后移，间隔只会变大。实际生产环境里，顺延还会触发后续车站的到发线占用检查和折返约束，这里为了演示只保留了最核心的间隔消解。

参数说明：headway是追踪间隔，取多少取决于信号制式，常见区间是 3～6 分钟，城市轨道交通有时压到 2 分钟以下。trains里的run_ab、run_bc是区间运行时分，实际系统中应来自 2.1 节提到的线路数据库。这个示例没有检查越行——也就是后车速度更快时不允许超车，真实建模中要对同类线路做顺序保持约束，否则同一区间会出现后车追上前车的荒谬结果。

3.3 三个必调参数：出发顺序、缓冲冗余与迭代次数

第一个参数是铺画顺序。按出发时间先后铺画，得到的图均匀性好；按列车等级铺画，先铺重点列车，能保证高等级列车时刻不被挤占，但低等级列车可能被压得很惨。我通常的做法是“时间排序 + 等级动态调整”：先按时间排一个初始顺序，再在冲突消解时给重点列车更高的优先级，让慢车让快车。

第二个参数是缓冲冗余。区间运行时分直接按最小值用，生成图对晚点非常敏感；但冗余加太多，图面时间长，旅速下降。经验区间是单线区段加 1～2 分钟冗余，双线快线加 0.5～1 分钟。这个参数和生产调度方式强相关，建议把它单独拎出来做成全局配置，方便不同线路套用。

第三个参数是迭代次数。跑完一轮铺画之后，如果冲突没有完全消解，需要重新尝试多次搜索。问题是：迭代 50 次和迭代 500 次的差距往往没有想象中大。我一般会设置“连续 N 代无改进即停”的终止条件，N 通常取 20～30，避免白烧 CPU。判断是否改进，看两条指标：剩余冲突数、目标函数值，两者都不再变化就可以停了。

4. 系统架构与数据流：自动生成能力如何落到工程里

能跑通算法只是第一步，真正在团队里可用的系统，需要把数据管理、算法、校验和人工调整串成一个闭环。架构设计上有一个容易被忽略的原则：自动生成系统不是用来替代调度员的，而是给调度员提供更好的起点。因此架构里必须有人工干预的接口，否则图再“最优”，调度员不认账，系统就废了。

4.1 模块划分：数据、铺画、校验、调整如何协作

一个典型的列车运行图自动生成系统包含六个模块，每个模块的职责和输入输出如下表：

模块之间的数据流是单向加回环：基础数据先准备好，开行方案定义要跑哪些车，铺画引擎生成初版，校验器检查合法性，人工调整后如果有改动需要重新校验一边，最后输出。铺画引擎和校验器之间往往要迭代好几轮，不是一次成型。

实际开发时，我建议把数据管理单独做成服务，而不是和算法耦合在一起。原因很朴素：线路数据更新频率高，新线开通、信号制式升级都会影响区间时分和间隔参数；如果数据和算法代码耦合太紧，每次改数据都要重新部署程序，会把人逼疯。

4.2 时刻表数据结构与冲突检测的内部表示

运行图程序的内部数据结构直接决定冲突检测的效率和可维护性。我惯用的表示是“事件活动图”：每个到发事件是一个节点，事件之间用活动弧连接——区间走行弧、停站弧、折返弧、追踪间隔弧。校验冲突就是沿着弧检查时间差是否满足阈值。

# 列车事件数据结构的精简示例 train = { "id": "G1001", # 车次号 "type": 1, # 1 高铁，2 动车，3 普速 "direction": 0, # 0 下行，1 上行 "stops": [1, 1, 1], # 每个车站是否停站，n 站长度 "run_times": [12, 15], # 区间运行时分，分钟 "dwell_times": [2, 2], # 停站时分，分钟 "departure": 360, # 始发站出发时刻，分钟 } # 校验一条间隔约束的示例伪函数 def check_headway(prev_event, cur_event, min_gap): gap = cur_event["time"] - prev_event["time"] return gap >= min_gap

为什么时刻要用整数分钟？这是从实际事故里换来的教训：用小数小时表示时刻，浮点误差会在几百次叠加后产生 1 秒级偏差，而排图系统的最小时间粒度通常就是 1 分钟，浮点误差会让“正好压线满足约束”变成“差一点不满足”。内部全部用整数分钟，输出时才转换成人可读的 HH:mm 格式，这是最省心的做法。

冲突检测的复杂度也要提前算清楚。简单实现是两两列车对检查，复杂度是 O(n²)，40 对列车就是 1600 次比较，没问题；但到几百对列车时，每次都全量两两比较会明显拖慢迭代。后续优化方向是按车站和时间建索引，比如把每个车站的到发事件按时间排序，只检查相邻的几列车，能省掉大量无效比较。

4.3 人工干预接口：锁定、微调与重铺的工作流

自动生成的图和最终可用的图之间，永远有一层人工调整。原因很简单：模型里没有写进去的隐性规则，调度员心里有。比如某个站高峰时段要避开某条客车进路，或者某列车固定要等某位重要旅客，这些很难在模型里表达全，只能靠人去调。

人工干预接口的设计上，最重要的是“锁定”功能。调度员在界面上选中某几列车，点击“锁定时刻”，就把这些列车的到发时刻固定住；系统再对剩余列车做重铺时，锁定列车变成固定约束，铺画引擎只能绕着它们安排其他列车。实现时，把锁定列车的到发时刻写入输入数据，并在铺画和校验流程中跳过这些列车的时刻修改，同时它们仍然参与间隔检查，防止后续列车给自己制造冲突。

锁定功能能否做好，直接决定这个系统在调度室能不能活下来。没有锁定功能的自动生成系统，调度员会觉得机器在“捣乱”，因为他手动调好的车全被算法冲掉了。有了锁定，系统变成“半自动，人主导”，调度员可以把精力放在真正需要经验判断的部分。

5. 避坑记录：列车运行图自动生成的 5 个典型事故

这一部分写的是我在类似系统实施过程中遇到的真实问题，每个问题都按“现象 → 原因 → 解决”整理。新手照着排雷，熟手也能对照检查自己的实现有没有埋着同样的隐患。

5.1 图上没问题，进调度系统就报间隔错误

现象：自动生成的运行图在自己的校验器里跑了一遍，显示无冲突；导出的文件送进调度系统，立刻报出十几个间隔违规，调度员直接打回。

原因：校验器里只检查了“到达间隔”和“出发间隔”，漏掉了“前车到达与后车出发”的追踪约束。同一个站，前车还没出清站内轨道，后车就放入站信号，虽然两车到达时刻拉开了，但后车出发时前车仍在站内，这种情况在实际信号联锁里是危险的。原因是把“追踪间隔”理解成单一数值，没有按事件拆类。

解决：把间隔约束拆成三类：到达-到达、出发-出发、前车到达-后车出发。三类分别用不同的时间阈值建模，其中第三类通常和站内轨道区段长度有关，阈值比前两类更大。校验器里三类全查，输出报告里也把违规类型写清楚，方便排图师傅理解为什么被拦。

5.2 改一列车，整条线跟着乱

现象：调度员在界面上把某列车往前挪了 2 分钟，保存后系统自动重铺，结果这条线后半段的十几列车全部被带偏，原来调好的接续全乱了。调度员气得直接关掉界面。

原因：铺画引擎做冲突消解时使用了整体顺延策略，前车提前发车后，与后车的间隔变大，本来不需要动的后车被重铺算法重新执行了一遍全量铺画，导致连锁位移。整体顺延是保证可行性的保守策略，但它的副作用是会把微小扰动放大成全图级变化。

解决：重铺时引入“最小改动原则”——只在冲突涉及的局部范围内调整，未受影响的列车保持原时刻不动。实现上，冲突消解时记录顺延影响的车站范围，只对受影响列车做传播，其他的直接冻结。另一个实用技巧是，调整前先把手动调整的列车加入锁定列表，重铺时锁定列车不参与时刻修改，只作为约束参与检查。

5.3 多站交路的图怎么都解不出来

现象：单线区域生成的图很顺利，但把多个车站和多条交路加进去之后，算法长时间不出解，偶尔出一版还是有折返车在终到站堵住了，后车进不来。

原因：模型里只考虑了区间和停站约束，没有把车站“到发线占用”和“折返进路”纳进来。列车在中间站可以随到随走，但在终到站要占用站线等待折返，折返期间同方向后车无法接入同一股道，形成死锁。单纯靠顺延和重排解决不了这类资源冲突。

解决：在建模阶段把车站到发线抽象成容量资源，建模方式是给每个车站设置可用到发线数，列车占用站线的时间窗要满足重叠不超过容量。折返车要额外建模折返作业时间和占用道岔的时间。这一步不是可选项，只要系统要支持交路，就必须做。如果嫌建模复杂，折衷方案是不在求解器里建模到发线，而是作为后置校验器接入，冲突时提示调度员人工换线，但这只适合小站场景，大枢纽必须进模型。

5.4 遗传算法迭代后期不收敛

现象：某团队给系统上了遗传算法，早期迭代目标函数下降明显，到 100 代之后几乎停滞，生成的图里同一区间总是存在两列车相互越行的逻辑错误，怎么调参数都没用。

原因：交叉算子把两条线路的“到发时刻序列”直接拼接，破坏了列车在同一区间的前后顺序关系。遗传算法生成的新个体在时间维度上合法，但在空间顺序维度上混乱，适应度函数里又没把“顺序保持”放在足够高的权重上，导致算法在错误的解空间里空转。

解决：要么在交叉算子层面限制——只允许在同向列车顺序保持一致的前提下做交叉；要么更简单——别让遗传算法直接操作到发时刻，而是让它只搜索“铺画顺序”或“优先级参数”，每产生一个个体，就把这个个体交给确定性的铺画引擎去生成完整图，再做适应度评估。这种分层方式把随机搜索限制在人类可理解的维度上，收敛性和可控性都改善很多。

5.5 跨日时刻和浮点时分把数据搞崩

现象：系统跑生产数据时，某条凌晨 1 点的列车运行线在校验结果里时间错乱，明明应该在第 2 天的 01:20 到达，却被显示成前一天某个负值时刻；另一次整张图的到发时间普遍偏离正点约 30 秒。

原因：两个基础问题。第一，时刻表示用的是 HH:mm 字符串或模拟小时的小数，跨日时没有加日期偏移，凌晨时刻被当作负数处理；第二，区间运行时分用小数小时输入，经过几十个区间累加后，浮点误差叠加成秒级偏差，和调度系统分钟级精度要求相冲突。

解决：全系统统一使用整数分钟作为内部时刻表示，跨日列车在初始时刻加 1440 的倍数；区间时分同样以分钟整数存储，输入时做四舍五入。输出时再转换格式。这个修改看起来不起眼，但能避免掉大约三分之一的数据类事故。它应该在一个项目一开始就定下来，等数据结构写满再改，代价很大。

6. 成品验证与调参技巧：怎么确认系统出来的图能直接用

6.1 用历史图回测：一致性校验脚本怎么写

系统做完第一版，先别急着上生产，找一个历史运行图做回测：把历史图的线路数据和开行方案提取出来，喂给自动生成系统跑一遍，再逐项对比生成结果和历史人工图。校验脚本的思路很简单，把历史图逐列车逐站解析成事件列表，把生成图也解析成同样格式，然后逐对检查间隔和天窗是否满足约束，并统计两者的总旅行时间、发车间隔方差。

# 一致性校验的核心函数：比对两份运行图的事件间隔 def validate_pairs(events_a, events_b, headway): violations = [] for (ev_a, ev_b) in zip(events_a, events_b): gap = ev_b["time"] - ev_a["time"] if gap < 0 or gap < headway: violations.append({ "station": ev_a["station"], "train_a": ev_a["train_id"], "train_b": ev_b["train_id"], "gap": gap, }) return violations

回测出来的冲突数如果是 0，说明系统在约束层面基本合格；至于图的“可用性”，再对比总旅行时间和图面均衡度。我现在的习惯是：每次改完参数，先跑一遍历史图回测，确认没有新增违规，才把图拿给排图师傅看，这个习惯省掉了大量返工。

6.2 参数连动调整：迭代次数、缓冲冗余和权重怎么配合

参数之间是相互影响的，不能孤立地调。缓冲冗余加得越多，需要的迭代次数越少，因为列车之间的可用调整空间变大了；但图面时间变长，均衡性目标函数值会变差。所以调参的正确顺序是：先定追踪间隔和缓冲冗余，再调目标函数权重，最后才看迭代次数够不够。顺序反了，经常会出现一种“玄学”现象——算法参数改了，结果图毫无改善，其实不是算法问题，是前面的约束参数本身把解空间限制死了。

自动生成系统做到最后，拼的不是算法多炫，而是细节磨得够不够细。系统上线时某导师跟我反复交代过一句话：“自动生成的图，要让调度员改三笔以内就能用，而不是让他在两小时里重画一张。”这个标准现在还会出现在我的验收清单里。希望帮到你。

本文还有配套的精品资源，点击获取