写这套东西之前先聊点真实的背景。我以前接过一条城际线的运行图编制任务高峰期一小时要排十几列车中间站停站时间、区间运行时分、折返衔接全挤在一起晚上用Excel一列一列地调调到凌晨两三点终于把间隔捋顺了结果第二天早高峰仿真一跑某个站的到发线时间窗又撞了。那段时间我就在想这种多目标、多约束的优化问题靠人肉搜索确实已经碰天花板了。后来我把粒子群算法引入到列车运行图优化方法设计中用粒子群算法去搜索发车间隔、停站时间和区间运行时分的组合才算是把这团乱麻理顺了。这篇文章就整理一下我的建模过程、编码方式、参数调试和落地时踩过的坑适合做轨道交通调度、运筹优化或者算法落地相关工作的朋友参考。1. 从运行图痛点说起这道优化题到底在解什么1.1 运行图不只是“画一条斜线”做过调度的人都知道列车运行图本质上是一张以时间为横轴、车站为纵轴的二维图每一列车的运行轨迹就是一条斜线斜线的斜率代表区间运行速度水平段代表停站时间。但真正编制的时候你要面对的问题远不止“画线”列车在区间内的运行时分不是随便定的它受线路限速、信号制式、车辆牵引性能的共同约束停站时间受客流上下车时间、站台作业时间限制必须在合理范围内追踪间隔必须满足安全要求不能为了图好看就把间隔压到信号系统允许值以下。这些都是硬约束不是主观拍脑袋能绕过去的。传统的人工编制方式高度依赖编制者对线路、车辆的熟悉程度和临场经验。你让他把一版方案改一版他能改但很难回答“为什么这列车在这个站停90秒而不是75秒”这样的问题。更麻烦的是当线路从单线变成网状、当高峰小时开行对数从十几对涨到二十几对时人工方案往往只能在“满足安全约束”和“尽量均衡发车”之间二选一旅客总旅行时间、能耗这些指标根本没有余量去系统优化。这正是我决定把智能优化算法引入进来的直接原因。1.2 优化目标到底有哪些怎么取舍列车运行图优化的目标函数从来不是单一的。从我做的项目经验来看至少要覆盖三个维度旅客服务维度全列车旅客的总旅行时间等同于是所有旅客在车上的时间之和。如果某列车在中间站停太久、区间跑太慢这部分的加权和就会增加。运营效率维度发车间隔均衡性也就是实际间隔相对期望间隔的偏差。间隔忽大忽小既影响站台候车秩序也容易造成客流不均衡。能耗维度列车区间运行时分偏短意味着要更高速度运行牵引能耗会明显上升。工程上不好直接算精确能耗我会用“区间运行时分相对标准值的偏离度”作为能耗代理指标。这三个维度天然存在冲突你压缩停站时间、缩短区间运行时分能让旅客更快到达但均衡性可能被破坏能耗也可能上升。所以我在设计目标函数时用的是加权和的形式把三个指标归一化后叠加权重根据线路的实际运营定位来定。客流压力大的城市线旅客时间维度的权重就高一些郊区线对能耗更敏感就把能耗权重大一些。这个思路在工程上是可行的也好向业务方解释。1.3 为什么需要算法而不是单纯“枚举”有朋友会问运行图方案虽然多但每条线的列车对数、停站方案基本固定枚举一遍不行吗我一开始也这么想过但很快发现不现实。假设一条线有6个可调停站、10列车每个停站时间在30到90秒之间有7档可选光是停站时间这个维度就有7的60次方级别的组合这还没算发车间隔和区间运行时分。枚举计算量直接爆炸没法落地。这种高维连续型优化问题粒子群算法的优势就体现出来了它不需要导数不需要遍历全部组合靠群体信息共享就能在连续解空间里快速逼近较优区域。2. 粒子群算法凭什么能扛起运行图优化这活2.1 粒子群的三个核心行为粒子群优化算法PSO最早是受鸟群觅食行为启发提出的核心思路是解空间里有一群“粒子”每个粒子就是一个候选解。每个粒子知道自己当前的位置、速度也记得自己飞过的最好位置个体最优pbest同时整个群体共享全局最好位置群体最优gbest。下一步往哪飞由三股力量共同决定惯性自己原来的速度、个体记忆向自己的最优位置靠拢、群体共识向群体的最优位置靠拢。我在项目里用的是标准PSO的速度-位置更新公式v_i(t1) w * v_i(t) c1 * r1 * (pbest_i - x_i(t)) c2 * r2 * (gbest - x_i(t)) x_i(t1) x_i(t) v_i(t1)其中w是惯性权重c1和c2是学习因子r1和r2是[0,1]之间的随机数。理解这个公式的关键在于它把“探索”和“开发”平衡起来了。w大的时候粒子倾向于保持原有方向探索更广的区域w小的时候粒子更倾向于往已有的优良解靠拢局部精细搜索能力更强。这是PSO最核心的机制。2.2 和遗传算法、模拟退火相比PSO强在哪我在方案选型阶段做过一轮对比。遗传算法GA是演化类算法核心是选择、交叉、变异处理离散变量很方便但交叉算子的设计对问题依赖很强我试过用二进制编码表示停站时间档位结果是染色体很长、收敛偏慢而且交叉后经常需要大量修复操作。模拟退火SA是单点搜索理论上能跳出局部最优但串行执行计算效率在运行图这种高维问题里不太够看。PSO的优势我总结成三点实数编码友好运行图的决策变量比如发车间隔、停站时间、区间运行时分本来就是连续量PSO直接拿实数位置向量表示省去了编码解码的折腾。群体并行搜索所有粒子同时朝多个方向飞信息通过gbest共享整体搜索效率高。我实测同样算一个6站10列车的算例PSO在300代内能稳定收敛GA大概要到500代以上才有可比拟的效果。实现简单、调参成本低核心参数就w、c1、c2三件套不像GA要操心种群初始化的多样性控制、交叉概率、变异概率、精英保留策略一大堆细节。当然PSO也不是银弹。它对多峰函数的局部最优问题比较敏感尤其是停站时间可行域存在多个离散平台时粒子容易扎堆。这个问题我在第六部分会专门讲怎么处理这里先按下不表。2.3 适用边界的判断我个人的判断标准是如果优化变量是连续或近似连续的并且约束条件可以用罚函数或边界截断表达PSO基本够用如果变量本身是强离散的比如“停站方案选A类站还是B类站”这种组合选择用带局部搜索的离散PSO或者GA会更稳。运行图优化的主体是连续量PSO正好踩在舒适区里。3. 把运行图问题装进粒子群框架建模与编码的关键抉择3.1 决策变量怎么设计建模是整件事成败的关键我在这一步反复调整过好多次。最终采用的决策变量是三段拼接的实数向量第一段发车间隔序列。用相邻列车之间的发车时间差来表示设列车数为N那么这段有N-1个变量。之所以不用“每列车绝对发车时刻”是因为直接用间隔能天然避免乱序问题方便后续做约束判断。第二段各站停站时间。对每列车在每一个中间站的停站时间设为一个变量。如果线路有M个中间站这一段就有N*M个变量。变量范围直接对齐实际运行要求比如城际线允许30到90秒。第三段区间运行等级或运行时分。我习惯用“区间运行时分”因为它直接决定了运行线的斜率。列车在区间跑得快慢最终要落实成时分比如标准值是360秒允许上下浮动20%。这样下来一个粒子的维度是(N-1) NM N(M1)看起来不少但PSO处理50维以内的实值优化问题非常轻松。我做过一个6站10列车的算例维度大概是10个间隔加上50个停站时间再加上70个区间时分总共一百三四十维迭代300代左右就能收敛。3.2 目标函数怎么量化目标函数我用的是三个分项加权求和的结构第一个分项是旅客总旅行时间。工程简化处理假设各站上下车客流已知且固定那么总旅行时间就等于各列车从始发站出发到终到站的全部时间之和再按各区间段的断面客流做加权。没有客流数据时退而求其次直接对所有列车求和也能用但加了断面客流权重会更贴合实际。第二个分项是发车间隔均衡性。写成实际间隔与期望间隔之差的平方和如果期望间隔是600秒实际间隔是580秒和620秒两者偏差平方都是400但一个偏早一个偏晚对站台能力利用的影响不同。所以我在目标函数里用的是偏差平方同时加了符号判断让早发和晚发的影响都体现出来。第三个分项是能耗代理指标。因为精确的牵引能耗计算需要牵引曲线仿真目标函数里直接套仿真会很慢。我用的是区间运行时分偏离标准值的比例平方偏离越多能耗越大这个代理指标虽然粗但方向上是对的优化完之后再对最优方案做精确仿真校核就行。目标函数整体写成F α * T_passenger / T_base β * B_interval / B_base γ * E_energy / E_baseT_base、B_base、E_base是归一化基准值取初始人工方案的对应指标这样三个分项都在1附近加权时α、β、γ的含义就非常直观。比如α0.5、β0.3、γ0.2说明最看重旅客时间其次是发车均衡最后是能耗。3.3 约束条件与罚函数设计运行图的约束条件我分成三类来写第一类是变量边界约束比如停站时间在30到90秒、发车间隔在480到720秒、区间运行时分在标准值正负20%之内。这类约束用边界截断处理粒子越界后直接把越界维度拉回边界值。第二类是安全间隔约束包括相邻列车在同一车站的到达间隔、出发间隔必须大于最小追踪间隔以及列车在区间内不能被追上的净空时间约束。这类约束反映的是行车安全底线不能靠罚函数糊弄过去必须严格检查。第三类是到发线占用约束同一个车站同一时刻不能有两列车同时占用同一条到发线。这个约束在高峰期特别容易出问题我把它转成时间窗重叠检查只要有重叠就计算重叠时长。罚函数的设计原则是“让不可行解的适应度变差但不至于完全失去搜索方向”。我采用的公式是Penalty λ1 * Σ max(0, h_min - h_actual)^2 λ2 * Σ overlap_time^2这里λ1和λ2是罚因子我试过固定值也试过随迭代次数增大的动态值。经验是动态值更稳前期罚因子小让粒子大胆探索后期逐步加大逼迫粒子落入可行域。这个“先松后紧”的策略比固定罚因子效果好很多。4. 算法实现细节从速度更新到适应度评价4.1 惯性权重的时变策略标准PSO的参数选择对收敛效果影响非常大我总结了一套在运行图问题上实测有效的配置种群大小取30到60之间算例规模小就30规模大就到60再大收益不明显反而增加计算负担。学习因子c1和c2都取2.0。这个值几乎是PSO的黄金默认值有不少论文做参数标定也得出了类似结论。惯性权重w采用线性递减策略从0.9降到0.4。前期w大粒子飞得远、探索能力强后期w小粒子集中精力在gbest附近精细挖。线性递减的公式w w_max - (w_max - w_min) * (t / T_max)T_max是最大迭代次数。我在代码里把这个公式实现成随迭代次数更新的函数实测下来300代的时候w从0.9平滑降到0.4算法在前100代就能锁定一个不错的解域。4.2 粒子解码与适应度评价流程粒子位置是抽象的实数向量要和运行图方案对应起来必须有一个清晰的解码函数。这一步是工程实现里最容易写错的地方。我的解码逻辑分三步第一步从粒子向量里切出三段分别得到发车间隔序列、停站时间矩阵、区间运行时分矩阵。 第二步根据发车间隔序列累加得到每列车的始发时刻。比如第一列车始发时刻固定为0第二列车是0加第一个间隔第三列车再加第二个间隔以此类推。 第三步从始发时刻出发按“区间运行时分停站时间”交替推进算出每一列车到达每个站和离开每个站的时刻最终生成完整的运行图时刻表。适应度评价函数在解码完成后执行先遍历所有时刻表数据做安全间隔和到发线占用检查把违反量累加进罚函数再计算三个目标分项并做归一化加权最后把目标值和罚值相加得到该粒子的适应度。这一步我强调一点一定要先做安全间隔检查再做目标计算否则可能出现“目标值很漂亮但方案根本没法跑”的假最优解。4.3 完整算法流程伪代码我把整个算法的核心流程写在下面可直接照着实现# PSO 主流程伪代码 初始化种群随机生成 pop_size 个粒子位置 x_i 和速度 v_i 将人工初始可行方案编码后作为第一个粒子的初始位置 # 经验能显著加速收敛 迭代 for t in range(T_max): # 评价阶段 for each particle i: schedule decode(x_i) # 解码为时刻表 fitness evaluate(schedule) # 目标值 罚函数 if fitness pbest_fitness_i: pbest_i x_i pbest_fitness_i fitness if fitness gbest_fitness: gbest x_i gbest_fitness fitness # 更新阶段 w linear_decrease(t, T_max) for each particle i: v_i w * v_i c1 * r1 * (pbest_i - x_i) c2 * r2 * (gbest - x_i) x_i x_i v_i x_i boundary_check(x_i) # 越界截断 # 动态调整罚因子逐步收紧约束 lambda1 dynamic_increase(t, T_max) lambda2 dynamic_increase(t, T_max) 输出 gbest 对应的解码时刻表这套流程我在Python里实现过评估一次6站10列车的方案大概耗时几毫秒300代乘30个粒子全部跑完不到一分钟。如果换线路规模更大的场景评估函数变重就要考虑并行评价了Python的multiprocessing或者numba加速都能用。4.4 边界处理与速度限幅边界处理这块有个容易被忽略的细节速度v也要做限幅否则粒子可能在解空间边缘来回振荡。我给速度设了上限不超过变量搜索范围宽度的20%。比如发车间隔范围是[480, 720]宽度240秒速度最大不超过48秒/代。这个限幅值不是理论最优是我多次实验调出来的既能保证探索能力又不会让粒子飞得太野。5. 小算例跑通全流程一条6站城际线的优化实录5.1 算例场景与初始方案为了验证这套方法的可行性我搭了一个简化但不失真实的算例一条城际线设6个车站A、B、C、D、E、F其中A、F为始发终到站B、C、D、E为中间站。早高峰120分钟内开行10列车全部站站停。标准停站时间60秒允许范围30到90秒标准区间运行时分设为B站到F站区间各不相同大概在300到480秒之间允许上下浮动20%。最小追踪间隔110秒期望发车间隔600秒。人工初始方案是一个明显的“手排草表”为了压轴保证所有列车在120分钟内发出发车间隔没控制好有的550秒、有的650秒波动比较大同时有一列车在C站的停站时间被压到45秒导致下一列车在区间内追到净空距离不足追踪间隔只有85秒小于110秒的安全值。这个方案在Excel里表面看起来“像模像样”但放到约束检查里立刻就暴露问题。5.2 PSO参数与优化结果PSO参数按上一节的经验配置种群30迭代300代w从0.9线性降到0.4c1c22.0罚因子动态递增。初始种群中放入了人工初始方案作为1号粒子的初始位置其余粒子在可行范围内随机生成。优化完成后gbest对应的方案如下表所示只列部分列车关键数据指标人工初始方案PSO优化方案平均发车间隔600秒598秒发车间隔标准差48秒21秒最小追踪间隔85秒违规115秒停站时间超限次数2处0处旅客总旅行时间4200人·分钟3961人·分钟能耗代理指标1.000.94可以看到几个明显变化发车间隔标准差从48秒降到21秒发车均衡性好了一大截最小追踪间隔从违规的85秒拉回到115秒满足安全底线旅客总旅行时间下降了约5.7%能耗代理指标也降了6%。这个结果还是相当可观的尤其是在安全和均衡这两个硬指标都改善的前提下。收敛行为方面适应度曲线在前60代下降最快到150代左右基本进入平台期之后偶尔有小幅震荡但不再有突破性下降。这种收敛形态说明罚因子动态递增的策略发挥预期作用了前期罚因子小粒子有空间试探各种组合后期罚因子加大粒子集中在可行而且目标较优的区域精细搜索。5.3 从结果反推设计逻辑我看了好几遍优化后的运行图发现一个很有意思的规律PSO自动把发车间隔序列的“中心”略微偏向期望间隔的下方也就是早高峰初期几列车间隔略小于600秒后期略大于600秒。原因是旅客旅行时间加权时早发车在目标函数里占便宜因为早发的列车载客时间更早总旅行时间更小。这个“聪明”的偏移不是人为设定的完全是算法在目标函数驱动下自己学出来的。这让我觉得这套方法不只是凑合规它确实在从运营角度重新理解问题。6. 实战避坑收敛、早熟与工程落地的几个坎6.1 早熟问题与对策PSO最典型的毛病就是早熟收敛粒子们还没把解空间探索开就一股脑扎进某个局部最优。我在运行图问题上也踩过这个坑。具体的表现是迭代到80代左右所有粒子的位置差距很小gbest几乎不动但罚函数还有不少正值说明它们扎堆在一个不可行区域里出不来。我用的对策主要有三个初始化多样性控制随机初始化时不再全域均匀撒点而是按“发车间隔”“停站时间”“区间运行时分”三个子空间分别做拉丁超立方采样保证每个维度上初始粒子分布得足够开。精英扰动机制每50代判断一次gbest的变化幅度如果连续50代变化量小于5%就给gbest的随机若干维度加一个较小的扰动把这个粒子“踢”出局部最优区重新探索。多种群并行把30个粒子分成3个子群每个子群独立进化每隔50代做一次信息交换。这个方案能显著提升解的多样性但实现复杂度也高一些我在更大的路网项目里用过效果值得。6.2 参数调参的“手感”PSO参数不多但“手感”很重要。我一开始用固定w0.7跑结果后期收敛不足到300代还在小幅震荡后来改成线性递减收敛稳定性明显提升。还有一次我把c1、c2都设成1.5算法变得非常保守gbest更新频率很低把c2加大到2.2之后群体向gbest聚集的速度才正常。这个调参过程没有太多理论可讲主要是对照收敛曲线微调。我习惯的做法是画一条适应度随迭代次数的曲线看震荡周期和下降趋势震荡太大就加w下限或减c2下降太慢就减w上限或加c2。6.3 约束罚因子“先大后小”反而更好这个结论可能有点反直觉。按理说想把约束抓得严罚因子应该从小调大让粒子先看清全局。但如果一开始就从大罚因子开始粒子会陷入“任何带违规的方案都是天价罚分”的状态几乎没有方向信息搜索容易停滞。我试过反过来前100代让罚因子相对小允许一定程度的违规后200代逐步把罚因子调大逼迫粒子把违规量清干净。实测这个策略不但收敛速度快而且最终解的目标值和违规量都控制得很好。当然罚因子也不能一味小否则粒子会在可行域外“放飞自我”后期怎么拉都拉不回来。6.4 工程落地的接口与可解释性算法跑出最优解只是第一步。真正要落地还得解决两个现实问题。第一是可解释性调度员不会接受一个“算法说这样排就排”的黑盒结果。我的做法是把gbest解码后的运行图方案导出成Excel时刻表同时自动生成每个关键约束的确认结果最小间隔多少、到发线占用情况如何让调度员能逐项核对。第二是人工调优接口算法给的方案可以直接在时刻表上手动微调比如个别车站的停站时间按现场作业习惯加减10秒然后重新检查约束确保调整不破坏可行性。另外优化后的方案最好再拿到专业的仿真软件里跑一遍验证信号系统层面的可行性。我在项目里会把PSO输出的时刻表转成通用的CSV格式再导入仿真工具做二次校核。这一步很关键因为简化的约束检查模型和真实信号系统之间总是存在差异仿真能兜住最后一道安全底线。最后再说两句做这个项目最大的体会是粒子群算法解决运行图优化问题真正的难点不在算法本身而在怎么把运营规则翻译成目标函数和约束。翻译得好算法只是顺手的事翻译得不好再高级的优化器也给你吐出一堆不能用的“纸面最优方案”。我个人如果重新做一遍会在停站方案和区间运行时分之间做个双层解耦——先用粒子群找发车和停站的大结构再用局部搜索微调区间运行速度曲线两层配合效率和稳定性应该都比单层PSO好。这套方法目前在我这边已经跑通正在拿更多线路数据做压力测试。后续有机会我再把双层框架的细节和测试结果整理出来分享给大家。