多场景需求下半灵活公交设计：基于ALR‑ADMM的车辆路由优化

论文题目：Semi-flexible transit service optimization considering scenario-based demand fluctuations

第一作者：Yating Liu 清华大学硕士研究生，研究方向：公交服务优化。

E-mail：liuyt24@mails.tsinghua.edu.cn 

通讯作者：商攀 北京交通大学交通运输学院副教授 博士生导师，研究方向：交通运输规划与管理、物流工程与管理、运输组织理论与技术、运输与物流理论与技术、综合交通运输理论与技术等。

E-mail：shangpan@bjtu.edu.cn

多场景需求下半灵活公交设计：基于ALR‑ADMM的车辆路由优化

论文摘要

半灵活式公交（SFT）融合了固定线路与按需响应服务，特别适用于需求稀疏或波动较大的区域。然而既有研究往往分开设计固定线路和灵活线路，不能在不同需求场景下共同优化车辆规模、主线路和支线路，导致难以应对需求波动。本文将需求场景视为预订请求的时间聚合，以三维空间‑时间‑状态网络为基础建立统一的车路路由模型，在战术层同时确定车队规模与主线路，在运行层为各需求场景生成支线路。目标是最小化总运行成本，约束包括旅程时间、车辆容量、乘客时间窗及主／支线路一致性等。为解决该模型，作者提出增广拉格朗日‑交替方向乘子法（ALR‑ADMM） 的分解框架，将问题划分为主线路设计、支线路设计和服务时序三个子问题。在Sioux‑Falls网络上的实验表明，该算法在保持0.57％最优性差异的情况下使计算时间降低约94.93％。对车辆容量、惩罚参数和站点选择的敏感性分析表明，这些因素会影响计算效率与运营成本。在美国西约旦真实网络上的案例验证了该方法在大规模场景下的可行性和高效性。

一、研究背景与问题提出

1.1 城市出行挑战与半灵活式公交

• 固定线路公交提供确定的停靠站与时刻表，但难以适应空间分散或时间波动的需求，尤其在解决出行“首末公里”方面能力有限。
• 需求响应式公交（DRT）为预订用户提供个性化路线，却会带来绕路与行程时间增长的问题。
• 半灵活式公交结合固定主线路和可调支线路，在保证线路可识别性的同时适应需求波动，是一种兼具效率与灵活性的混合模式。固定线路提供基线覆盖，支线路针对预订需求动态调整。

下图展示了半灵活式公交的服务示意，其中主线路停靠固定站点，支线路根据乘客预订在主干道附近进行接驳。

1.2 研究问题与挑战

• 需求波动难以应对：现有模型通常针对单一需求场景或将主、支线路分开优化，无法保证在多场景下运营可行。
• 决策层次耦合：车队规模、主线路规划与支线路安排相互影响，需要在战术层与运营层联合决策。
• 求解复杂性高：引入多个场景及时间窗约束后，问题规模巨大，直接求解不可行。

二、模型构建与框架设计

2.1 三维空间‑时间‑状态网络

为了同时考虑道路拓扑、时间约束和车辆载客状态，作者采用三维空间‑时间‑状态（STS）网络表示路线。节点用  表示道路交叉点，时间步用  表示离散时间，状态  表示车辆在途中的载客量；弧  表示车辆在时间  从节点  行驶到节点 ，到达时间为 ，状态从  变化为 。构建网络时引入以下规则：

• 服务时间窗规则：车辆为乘客  提供服务的出发时间必须落在乘客预约的上车时间窗内。
• 车辆容量规则：任何时间点车辆的载客量  不得超过车辆容量 。
• 行驶时间规则：相邻时间步遵循 ，其中  为道路  的行驶时间，可扩展为时间依赖形式。

2.2 优化模型

模型决策变量  表示车辆  在给定场景下是否走过某一弧。引入补充车辆集合 ，当原定车辆不足时通过惩罚成本启用补充车辆。目标函数为最小化车辆行驶成本与补充车辆惩罚成本的总和：

其中  包括行驶时间成本和补充车辆的惩罚成本。主要约束包括：

• 流平衡约束：保证每辆车从起点出发并在终点结束，途中进出节点的弧数量相等。
• 状态转换约束：在有需求的道路上，车辆出入节点的载客差等于该需求停靠点的乘客数量；在无需求的道路上载客量保持不变。
• 主‑支线路一致性约束：支线路必须包含对应主线路上的道路，保证灵活调度时主线路作为骨干存在。

三、求解策略：ALR‑ADMM分解算法

3.1 分解思想

问题规模巨大且约束耦合，直接求解不可行。作者引入增广拉格朗日‑交替方向乘子法（ALR‑ADMM） 分解框架，将原问题划分为三个子问题：主线路规划、支线路规划和服务计划。通过松弛主‑支一致性及状态转换约束，将复杂问题分解为可迭代求解的线性子问题。

3.2 算法流程

• 初始化：设定拉格朗日乘子和惩罚系数，对主线路和支线路进行热启动。
• 下界计算：在增广拉格朗日模型中对主‑支一致性约束进行对偶化，将问题拆分为主线路子问题  和包含支线路与服务的子问题 ，进一步松弛状态转换约束得到支线路子问题  和服务子问题 。
• 上界构建：固定下界步骤得到的主线路，解耦支线路和服务得到可行解作为上界。
• 收敛判断：计算上下界差值，若差值或迭代次数满足条件则输出解，否则更新乘子并重复。

下图展示了作者提出的ALR‑ADMM分解框架，其中信息在主线路、支线路和服务层之间迭代传递。

3.3 技术亮点

• 三层分解：相较于两层方法，该框架单独处理支线路，使得固定主线路与灵活支线路之间的复杂耦合得到有效隔离。
• 增广拉格朗日惩罚：通过在目标函数中加入二次惩罚项缓解拉格朗日松弛的对称性问题，提高算法稳定性。
• 动态规划求解子问题：对每个车辆的支线路子问题采用动态规划求解，在给定场景下高效生成可行支线路。

四、案例分析与结果评估

4.1 Sioux‑Falls基准网络

实验首先选用24节点的Sioux‑Falls网络进行算法验证。车辆从共同起点出发，经过预定需求点后到达共同终点，设置4辆车和2个需求场景。每辆车容量为6，行驶时间限制为30单位时间。实验结果表明：

• ALR‑ADMM算法在第5次迭代、12.54秒内获得最优解，最终最优差距为1.18％。
• 与Gurobi求解相比，ALR‑ADMM计算时间降低了约95.93％。
• 所有40个乘客请求均在时间窗内得到服务，车辆支线路根据需求适度偏离主线路，保证载客率。

4.2 计算效率与敏感性分析

作者比较了不同场景与车辆数量下的计算效率，结果见表7。总体结论为：

• 计算时间优势明显：在13组实验中，ALR‑ADMM平均比Gurobi快一个数量级，时间减少范围在86.59％–98.69％之间。
• 最优性差异极小：在大多数实例中，ALR‑ADMM获得的目标值与Gurobi完全一致，差异最大的实例也仅为4.4％。
• 参数敏感性：适当选择惩罚系数、车辆容量和服务站点会影响算法收敛速度和成本。例如增大惩罚参数会缩短求解时间而不损失最优性。

4.3 西约旦真实网络案例

为检验算法在大规模真实网络上的适用性，作者将模型应用于美国犹他州西约旦城市，共152个节点、388条路段，105个乘客请求分布在16个候选站点。四辆车按照预定义走廊服务，行程限制为60分钟，车辆容量分别为8、10、6、8。主要结果包括：

• 在变量规模超过2.2×10⁹的情况下，ALR‑ADMM在第6次迭代、约583秒内取得1.51％的解差距，Gurobi因内存限制无法完成求解。
• 所有105个乘客请求均被满足，未启用额外车辆，说明容量设置匹配需求。
• 得到的主线路和支线路如图所示，走廊设计通过交叉区域提供冗余容量，提高了网络的灵活性和覆盖率。

下图展示了西约旦道路网络结构（左）以及算法在迭代过程中的上下界收敛曲线（右）。可见上下界迅速收敛，验证了算法效率。

五、创新点与学术贡献

• 场景化需求建模：通过将预订需求聚合为多个场景，提出了适用于日常决策的多场景SFT车辆路由问题，并在STS网络上统一描述空间拓扑、时间窗和载客状态。
• 主‑支线路联合优化：模型在战术层同时规划车队规模和主线路，在运行层为每个需求场景生成支线路，实现了固定与灵活成分的协同设计。
• 三层ALR‑ADMM框架：创新性地将增广拉格朗日松弛与交替方向乘子法结合，提出主线路、支线路和服务计划三层分解策略，提高求解效率。
• 高效求解与可扩展性：在中等规模网络上计算时间减少超过90％，在大规模网络上仍能快速收敛；算法可扩展到更复杂的道路拓扑与多场景需求。
• 实践启示：走廊设计和补充车辆策略可提升半灵活公交系统的适应性；通过适当设置惩罚参数可在保证服务质量的前提下优化运营成本。

六、结论与展望

半灵活式公交融合固定线路与按需接驳，为解决城市交通中首末公里难题提供了有效途径。然而仅有分离式或单场景优化无法满足实际运营需求。本文提出的基于需求场景的SFT优化模型将车队规模、主线路与支线路统一规划，通过ALR‑ADMM分解算法实现了高效求解，在Sioux‑Falls基准网络及西约旦实际网络上的实验验证了其优越性能：计算时间平均降低约95％，最优性差异不足1％。

作者指出未来研究可进一步探索实时动态调整模块，以处理临时预订或交通突发情况；将行驶时间扩展为场景和时间依赖，以更真实地反映拥堵环境；以及将模型推广到多出发地‑多目的地系统，以服务更复杂的城市网络。这些方向将进一步推动半灵活公交在智慧交通中的应用。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。