1. 赛题背景与核心挑战解析2023年的MathorCup高校数学建模挑战赛B题题目是“城市轨道交通列车时刻表优化问题”。乍一看这似乎是一个经典的运筹学问题很多同学可能会立刻想到用遗传算法、模拟退火或者整数规划去套。但如果你真这么做了大概率会陷入“调参地狱”或者得到一个理论上很美、但实际毫无用处的“花瓶”解。我带着团队完整地做了一遍这道题最大的感受是这道题的精髓不在于炫技而在于对现实业务逻辑的深度理解和建模。它考察的不仅仅是数学工具的使用更是将复杂的现实约束转化为清晰数学模型的能力以及如何平衡“最优解”与“可解释性”、“可落地性”的工程思维。这道题的核心是为一组城市轨道交通列车比如地铁在一条线路上含多个站点编制一张运行时刻表。听起来简单不就是安排一下每趟车几点从起点发车中间每个站停多久最后到终点嘛。但题目给出的约束和目标函数瞬间就把问题复杂度提升了好几个数量级。你需要考虑不同时段如早高峰、平峰、晚高峰的乘客需求OD矩阵即从哪个站到哪个站的人流量是动态变化的列车有最小和最大发车间隔限制列车在站台的停站时间有上下限列车运行有追踪间隔防止追尾线路有折返能力限制车到了终点站需要掉头回来甚至还要考虑乘客的等待时间和在车内的拥挤程度。目标是在满足所有这些硬约束的前提下最小化所有乘客的总旅行时间包括等车时间和乘车时间同时尽可能让列车满载率均衡避免有的车挤成沙丁鱼罐头有的车空荡荡。这本质上是一个大规模、多目标、带复杂时空约束的组合优化问题。变量多每一趟车在每一个站点的到达、出发时间都是变量约束耦合性强一趟车的延误会影响后续所有车目标函数非线性乘客等待时间与发车间隔不是简单线性关系。直接暴力求解或者套用标准模型库如单纯形法基本是行不通的必须进行合理的问题分解、模型简化和算法设计。2. 解题思路的顶层设计从业务逻辑到数学框架面对这样一个庞然大物一上来就埋头写公式、编代码是兵家大忌。我们的第一步是花了大量时间“读题”和“画图”把文字描述的运营规则翻译成我们自己能理解的物理世界图景。2.1 关键约束的物理意义解读首先我们梳理了所有约束并赋予它们具体的业务含义发车间隔约束这不只是数学上的不等式。最小间隔如2分钟是由信号系统和线路通过能力决定的物理极限是安全红线。最大间隔如10分钟是服务水平的底线超过这个时间乘客就要骂娘了。在高峰时段你肯定希望间隔接近最小值以输送大客流在平峰时段则可以适当拉大间隔以节省运营成本。停站时间约束为什么要有最小停站时间如20秒因为要保证乘客上下车的基本时间。为什么有最大停站时间如60秒因为停久了会影响后续列车降低线路整体通行效率。这个时间不是固定的它应该和上下车乘客数量正相关。题目没有直接给出这个关系但这恰恰是建模时可以创新的地方。追踪间隔约束这是确保安全的核心。它要求同一方向、相邻两列列车在任意时刻、任意地点不仅仅是车站都必须保持一个最小的安全距离通常用时间来表示如90秒。这意味着你安排时刻表时不能只考虑车站的点还要考虑区间线。一个常见的简化方法是将追踪间隔转化为在车站的“到达-出发”时间间隔约束但这需要基于线路区间的运行时分来谨慎推导。折返约束列车到达终点站后需要清客、换端司机换到另一头驾驶室、 maybe 简单检修然后再从终点站作为起点发车。这个过程需要时间这个时间就限制了这条线路上最多能有多少列车在同时跑线路配车数也限制了终点站的最大发车频率。如果你忽略折返时间可能会排出一个“车还没回来发车时刻又到了”的不可行表。2.2 模型框架的选择时空网络 vs. 事件驱动在数学上这类问题通常有两种建模范式时空网络模型将时间和空间都离散化形成一个巨大的网络图。节点代表“在某个时刻位于某个站点”弧代表列车运行或停站等操作。然后在这个网络上建立流量模型。这种方法非常直观能清晰地刻画列车的每一步移动但缺点是变量和约束规模会极其庞大时间离散粒度细一点变量数就指数级增长对求解器要求极高。事件驱动模型不显式地对所有时空点建模而是直接以列车的“到达事件”和“出发事件”为决策变量。每个事件包含两个属性列车ID和车站ID以及事件发生的时间。约束则表示为这些事件时间之间的线性或非线性关系。这种方法变量相对较少更紧凑。我们团队经过讨论选择了事件驱动模型作为基础框架。原因在于题目中大部分约束如发车间隔、停站时间、追踪间隔本质上是事件之间的时间关系。例如“列车i在站s的出发时间”减去“列车i在站s的到达时间”就是停站时间这个值必须在[最小停站最大停站]之间。这很容易写成约束。但事件驱动模型有一个难点乘客流的计算。乘客不是跟着某一趟固定列车走的而是会选择最先到来的那趟车。这涉及到“乘客分配”问题它与时刻表是耦合的——时刻表决定了乘客的等待时间乘客的选择又影响了列车的负载进而可能影响停站时间上下车人多停站就久。这是一个典型的“均衡”问题。我们的策略是解耦迭代先假设一个初始的时刻表基于这个时刻表将乘客OD流量分配到各趟列车上这是一个相对独立的网络流或随机用户均衡问题计算出每趟车在每个站的上下客人数。然后根据这个上下客人数我们可以更精确地设定停站时间例如设定停站时间 基础时间 人均上下车时间 * 人数再反过来优化时刻表。如此反复迭代直到时刻表和乘客分配结果基本稳定。这种方法虽然不能保证找到全局最优但在可接受的计算时间内能得到一个非常不错的、符合业务逻辑的可行解。3. 核心模型构建与关键细节处理在确定了事件驱动框架和解耦迭代思路后我们开始构建具体的数学模型。3.1 决策变量定义我们定义了两组核心决策变量arr[i, s]: 列车i在车站s的到达时间。dep[i, s]: 列车i在车站s的出发时间。 这里i遍历所有列车班次比如从早6点到晚12点计划开行的所有车次s遍历线路上所有车站从起点站到终点站。所有其他的量几乎都可以由这两组变量推导出来。比如列车i在区间(s, s1)的运行时间 arr[i, s1] - dep[i, s](题目通常给定运行时分可作为常数或微小调整)。列车i在站s的停站时间 dep[i, s] - arr[i, s]。列车i和列车i1在站s的发车间隔 dep[i1, s] - dep[i, s]。3.2 约束条件的数学表达列车运行顺序约束这是最基本的一辆车必须依次经过各个车站。arr[i, s] dep[i, s] arr[i, s1]对所有i, s成立。发车间隔约束最小发车间隔 dep[i1, s] - dep[i, s] 最大发车间隔。 这里有个关键点这个约束需要对所有车站s都成立吗理论上是的但实践中只要在起点站和几个大客流站严格满足其他站由于运行时分微小差异间隔会自然波动但通常也会在范围内。我们在建模时对所有站都加了此约束以确保鲁棒性。停站时间约束最小停站时间 dep[i, s] - arr[i, s] 最大停站时间。 如前所述最大停站时间后期可以与估算的上下车人数关联进行动态调整。追踪间隔约束简化版 这是难点。严格的追踪间隔约束需要在区间内任意点满足这会导致大量约束。一个广泛使用的简化方法是“车站间隔约束”即在任何一个车站同向相邻两列车的到达时间间隔必须大于等于最小追踪间隔。arr[i1, s] - arr[i, s] 最小追踪间隔。 同时出发间隔也要满足dep[i1, s] - dep[i, s] 最小追踪间隔。 这个简化在大多数情况下是保守且安全的因为它保证了即使在区间内后车追上了前车至少在车站点它们也是安全的。我们采用了这个简化。折返约束 假设列车i到达终点站S_end的时间是arr[i, S_end]它完成折返后可以作为列车j从终点站此时作为起点站再次出发出发时间为dep[j, S_start]。那么必须有dep[j, S_start] - arr[i, S_end] 折返所需时间。 同时列车j和列车i可能是同一组车底也可能不是这涉及到车底运用计划题目通常简化处理只要求时刻表在折返能力上可行不一定指定具体车底。我们将其建模为在任何一个时间窗口内到达终点站的列车数量不能超过折返线在相同时间内能处理的数量。这可以转化为一系列复杂的资源约束。我们采用了更直接的表达为每一趟可能折返的列车事件显式地关联其前续列车并加上时间差约束。3.3 目标函数的构建总旅行时间最小化目标函数是“最小化所有乘客的总旅行时间”。总旅行时间 等车时间 乘车时间。乘车时间这部分相对固定。一旦乘客上了某趟车他从上车站到下车站的乘车时间就等于该列车在这两个站点之间的运行时间之和含中间站停站时间。这部分时间由时刻表决定但乘客无法选择。等车时间这是优化的重点。乘客的等车时间取决于他到达车站的时间以及列车的发车时刻表。假设乘客到达是均匀的题目通常这样简化那么对于发车间隔为H的列车乘客的平均等待时间就是H/2。因此目标函数可以写成Minimize: Σ (乘客流量_od * 乘车时间_od) Σ (在车站s等待去往方向d的乘客数 * 平均等待时间_sd)其中第二项等待时间是难点因为它依赖于时刻表决定的发车间隔。更精确的写法需要引入0-1变量表示乘客选择哪一趟车但这会使模型变成复杂的混合整数非线性规划。我们的处理方法是在迭代中近似在固定时刻表的情况下用“最短等待时间”原则将乘客分配到具体的车次上。这样每个乘客的等车时间就是确定的他选择的车次的发车时间减去他的到达时间。计算这个分配下的总旅行时间作为当前时刻表的目标值。优化调整时刻表微调arr和dep目标就是最小化这个基于当前分配计算出来的总旅行时间。由于乘客分配是固定的此时目标函数关于时刻表变量是线性的乘车时间是变量的线性函数等车时间对于已分配乘客是常数。用新的时刻表重新分配乘客重复上述过程。这样我们将一个复杂的均衡问题分解为一系列相对简单的时刻表优化线性或二次规划和客流分配子问题交替求解。4. 算法实现与求解策略模型建立后如何求解这个大规模优化问题是另一个挑战。直接调用商业求解器如Gurobi, Cplex求解完整的混合整数非线性模型对于实际规模的问题几十趟车几十个站几乎不可能在比赛时间内完成。4.1 基于启发式的两阶段算法我们设计了一个两阶段启发式算法第一阶段生成初始可行时刻表目标快速得到一个满足所有硬约束间隔、追踪、折返的时刻表不关心目标函数好坏。 方法采用“向前滚动生成”的方法。从第一趟车开始确定它在起点站的发车时间比如早6:00。然后根据给定的区间运行时分和最小停站时间计算出它到达后续各站的最早可能时间。这就得到了一个“最快运行”的时刻表基线。对于后续列车根据最小发车间隔和追踪间隔约束在前一趟车的基础上逐站确定其最早可能的出发时间。同时在终点站检查折返约束如果折返时间不够就延迟后续列车的发车。这个过程像铺轨一样一趟车一趟车地排下去能确保得到一个绝对可行的时刻表。这个时刻表通常很“紧凑”发车间隔都是最小值但可能不是最优的因为它没有考虑乘客需求波动。第二阶段在可行解基础上局部优化目标在保持可行性的前提下调整列车在关键车站的停站时间和发车时刻以最小化总旅行时间。 方法这时我们采用模拟退火算法。为什么不用更精确的梯度方法因为我们的模型包含大量离散约束搜索空间是非凸的模拟退火这种元启发式算法更适合。状态当前完整的时刻表所有arr[i, s],dep[i, s]。邻域动作随机选择一趟列车的一个车站微调其到达或出发时间例如在允许的停站时间范围内增加或减少5-10秒。或者随机选择相邻的两趟列车在某个车站交换它们的到发时间顺序需要检查是否违反追踪间隔。评价函数就是我们的总旅行时间目标。每次生成新状态后需要用当前时刻表快速重新分配乘客并计算总时间。这里客流分配算法必须非常高效我们采用了“时间前向加载”的确定性分配方法假设乘客总是乘坐最早能到达其目的地的列车。降温过程标准模拟退火流程接受劣解的概率逐渐降低。这个两阶段方法保证了我们能从一个可行解出发逐步向更优解搜索避免了在不可行域浪费时间。4.2 编程实现与技巧我们使用Python进行编程主要用到以下工具和技巧建模PuLP或ortools库用于构建和求解第一阶段中某些小的线性规划子问题比如检查局部调整后的可行性。算法核心自己实现模拟退火算法框架。关键在于邻域动作的设计和评价函数的快速计算。客流分配这是性能瓶颈。我们预先计算了所有OD对之间所有可能车次的旅行时间根据当前时刻表然后对于每一个按时间顺序到达的“乘客包”我们将连续时间离散化为小的时间片每个时间片内的乘客同时到达使用一个优先队列堆来快速查找最早可乘坐的车次。这样可以将分配复杂度从O(N^2)降低到接近O(N log N)。数据存储时刻表用一个Pandas DataFrame存储非常方便行是车次列是车站两个表分别存储到达和出发时间。方便进行向量化计算比如计算所有车次的发车间隔一行代码df.diff()就能完成。一个重要的调试技巧在优化过程中每迭代一定次数就完整检查一遍所有约束是否满足。我们写了一个check_feasibility()函数专门验证发车间隔、停站时间、追踪间隔、折返时间等一旦发现违反立刻拒绝这个解并记录日志。这能帮你快速定位邻域动作设计中可能产生的漏洞。5. 结果分析与模型评价的维度得到优化后的时刻表工作只完成了一半。如何评价这个时刻表的好坏并在论文中清晰地展示出来同样至关重要。不能只说“总旅行时间降低了X%”这太单薄了。5.1 多维度的效果评估我们从多个维度对优化前后的时刻表进行了对比分析核心指标总旅行时间。这是题目明确的目标。要给出绝对值的减少和百分比提升。同时可以拆分为“等待时间节省”和“乘车时间节省”并分析节省主要来源于哪个部分。通常优化主要减少的是等待时间。运营指标列车利用率与均衡度。满载率曲线绘制每趟列车在整个运行里程上的平均满载率乘客数/定员变化曲线。优化的时刻表应该使曲线更加平滑避免出现极端高峰拥挤和极端低谷空载。断面不均衡系数统计线路中最拥挤断面通常是靠近市中心某些区间的客流量与最宽松断面客流量的比值。优化后这个比值应该降低。车底运用效率计算完成全天运营所需的最少列车数与折返时间和发车间隔有关。更优的时刻表可能在不降低服务水平的条件下减少用车数。服务指标乘客体验。平均等待时间分布分车站、分时段统计乘客的平均等待时间。优化后高峰时段大客流车站的等待时间应有明显改善。最长等待时间统计所有乘客中最长的等待时间这个指标对乘客体验影响很大。换乘衔接如果题目涉及如果有多条线路分析优化后时刻表是否改善了换乘站的等待时间。5.2 灵敏度分析与策略解读一个优秀的模型不应该只是一个“黑箱”求解器还要能提供业务洞察。我们做了以下灵敏度分析发车间隔弹性分析如果允许高峰期的最大发车间隔再缩短30秒意味着投入更多车总旅行时间能改善多少这种改善的边际效益是递增还是递减这能为运营方是否加开列车提供决策依据。停站时间弹性分析如果通过优化上下车组织将最小停站时间从30秒压缩到25秒对整个线路的通行能力提升有多大这能为车站管理改进提供量化支持。需求波动的影响如果早高峰客流量比预测值增加10%我们的时刻表性能会下降多少是否需要启动应急预案这体现了模型的鲁棒性。在论文中我们不仅给出了数据和图表更关键的是解读这些数字背后的业务含义。例如“如图所示优化后早高峰期间A站至B站区间的满载率从120%下降至95%虽然仍处于高负荷但已脱离超载危险区间显著提升了安全性和乘客舒适度。这主要是通过将A站前两趟列车的发车间隔从150秒调整至130秒实现的相当于在客流最高峰前增加了运力投放。”5.3 模型的不足与改进方向没有完美的模型。在论文的最后坦诚地讨论模型的局限性会让你的作品更显深度。我们的模型主要有以下不足乘客行为简化我们假设乘客总是乘坐第一趟可到达目的地的车且到达率均匀。现实中乘客可能因为车厢太挤而等待下一趟拥挤回避行为到达率也可能是随机的。确定性模型我们没有考虑列车运行中的随机延误如设备故障、乘客上下车延误。一个更鲁棒的模型应该是随机优化或鲁棒优化。单线独立优化我们只优化了一条线。现实中地铁是成网的换乘站的协同优化能带来更大效益。计算复杂度虽然我们的启发式算法能在可接受时间内求解但无法证明解的最优性甚至无法给出与最优解的差距。对应的改进方向也很明确引入更复杂的乘客选择模型Logit模型采用随机规划框架处理延误研究网络化时刻表协同优化尝试结合列生成等精确算法框架来获得下界评估启发式解的质量。参加MathorCup这类比赛解题过程本身就是一个完整的项目实践。从理解业务、抽象模型、设计算法、编程实现到分析结果每一个环节都考验着团队的综合能力。B题尤其如此它像一个微缩版的交通运营优化项目。赢下比赛的关键往往不是用了多高深的算法而是对问题本质的把握、对细节的严谨处理以及将复杂现实清晰表述为数学语言的能力。这份经历对于未来从事运筹优化、数据分析、智能交通等相关领域的工作是一笔宝贵的财富。