基于逻辑的班德斯分解用于含车辆换乘的多周期线路规划

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Logic-based benders decomposition for multi-Period line planning with vehicle transfers

　　

•提出了一种基于逻辑的邦德斯分解框架，结合最大流重构以实现高效的可行性检测。
•引入了一种约束满足算法，通过迭代恢复流量平衡来实现精确可行性。
•通过广泛的计算实验证明，所提出的方法能够解决多达 99.1 的大型现实世界实例。

1. 引言

公共交通系统的设计从根本上依赖于线路规划问题（LPP），规划者在此问题中为给定的公共交通网络（PTN）确定一组路线及其对应的服务频率。这些决策共同定义了交通网络的运营配置，并对下游规划阶段产生重大影响，包括乘客分配、车辆调度和乘务员排班（Ceder and Wilson, 1986）。

关于 LPP 的早期研究集中在静态、不随时间变化的需求下的优化模型，旨在平衡运营成本与乘客旅行时间或不适感，对应于单一的起讫点（O-D）矩阵（Sch?bel, 2012）。尽管这些模型提供了有价值的见解和可处理的表述，但它们未能捕捉城市乘客流的时变特性。实证证据表明，需求在全天范围内剧烈波动，高峰时段集中了不成比例的每日出行量（Bornd?rfer et al., 2017, Wang et al., 2018, Zhou et al., 2023）。

为了克服这些局限性，后续研究通过将规划时间范围划分为多个离散的时间段来扩展 LPP，每个时间段都有其自己的 O-D 需求矩阵。这种划分能更准确地捕捉每日需求波动；然而，纳入多个时间段极大地增加了问题规模和计算复杂度，且由此产生的多周期问题已被证明是 NP 难的（?ahin et al., 2020, Schiewe et al., 2023）。增加车辆周转约束定义了一个进一步的变体，即含车辆周转的多周期线路规划问题（MPLPP-VR），其组合复杂度之高，以至于即使像 Gurobi 这样的高级商业求解器也无法在实际时间限制内解决中等规模的实例。?ahin et al. (2021) 因此采用了一种局部分支启发式算法，最初由 Fischetti 和 Lodi (2003) 提出，以生成 MPLPP-VR 的近似最优解。尽管该方法在中小型网络上表现有效，但它不能保证周期间车辆周转的可行性，且随着网络规模增加，其计算效率显著下降。

这一挑战凸显了对一种精确且具有可扩展性的优化框架的需求，该框架能够利用问题的内在结构。在现有的解决方案范式中，基于分解的方法最近已成为网络优化问题中特别有效的框架，因为它们通过将大型复杂模型划分为更小的、相互关联的组件来简化模型，这些组件可以迭代求解。尽管在线路规划文献中已经探索了多种基于分解的技术（见表 1），但据我们所知，没有研究将邦德斯分解（BD）应用于此类问题。

表 1. 文献中主要线路规划表述和解决方法综述。S 表示单周期模型，M 表示多周期模型，Y 表示显式包含车辆周转约束。

| 研究 | 年份 | 时间范围 | 周转 | LPP 变体 | 解决方法 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| Claessens et al. | 1998 | S | | 成本最优 | 分支定界 |
| Bussieck et al. | 2004 | S | | 近成本最优 | 分支切割 |
| Sch?bel and Scholl | 2004 | S | | 最小旅行时间 | 丹茨格 - 沃尔夫分解 |
| Goossens et al. | 2006 | S | | 多类型网络 | 带割的 MILP |
| Bornd?rfer et al. | 2007 | S | | 多商品设计 | 列生成 |
| Wang et al. | 2025 | S | | 公交接驳 | 标签设定和禁忌搜索 |
| Xiang et al. | 2025 | S | | 公交资源和接驳服务集成规划 | 增强ε约束法 |
| Yang et al. | 2020 | S | | 多频率设计 | 迭代优化 |
| Li et al. | 2024 | S | | 货运列车规划 | 基于 BD 的分支切割 |
| Feng et al. | 2024 | S | | 列车服务路线设计 | 对偶分解 |
| ?ahin et al. | 2020 | M | Y | 多周期 | 集成 MILP |
| ?ahin et al. | 2021 | M | Y | 多周期 | 局部分支 |
| Yan et al. | 2025 | M | Y | 多周期 | 双层优化 |
| 本研究 | M | Y | 多周期 LPP | LBBD | BD |

BD 提供了一种利用问题结构的系统化框架，通过将一个大规模模型划分为一个主问题（MP）和一个或多个子问题（SPs）进行迭代求解。在经典应用中，SPs 是线性的，允许通过 对偶性 推导可行性和最优性割，确保收敛和计算效率。然而，在 MPLPP-VR 中，周期间车辆周转引入了离散 SPs，无法线性化，使得标准 BD 无效。为了克服这一局限性，我们采用了基于逻辑的邦德斯分解（LBBD），这是 BD 的扩展，用逻辑推理取代了基于对偶的推断。

基于这一想法，本研究开发了一个 LBBD 框架，利用 MPLPP-VR 的结构来提高效率和可扩展性。该研究由三个主要研究问题指导：
1. 如何将 MPLPP-VR 分解为 MP–SP 结构，在保持周期间可行性的同时降低计算复杂度？
2. 如何生成有效的 BD 割以确保收敛并提高所提出 LBBD 框架的计算效率？
3. 与集成 MILP 表述相比，所提出的 LBBD 框架在解的质量和计算效率方面表现如何？

本文的其余部分组织如下。第 2 节回顾了 LPP 和 BD 的文献。第 3 节提出了 MPLPP-VR 的表述。第 4 节介绍了所提出的分解方案。第 5 节报告了计算结果。最后，第 6 节总结了结论并概述了未来研究方向。

2. 文献综述

关于 LPP 的研究沿着两种建模范式演进（Sch?bel, 2012）。第一种范式是面向乘客的模型，优先考虑服务质量，通过构建目标函数来最大化直接连接（Bussieck et al., 1997, Hu et al., 2024）、增加总运输需求（Klier and Haase, 2008）或最小化总旅行时间（Sch?bel and Scholl, 2004, Zhao and Ubaka, 2004）。第二种范式是面向成本的模型，采用运营商的视角，旨在满足预定义的服务或容量约束的同时最小化整体系统成本（Claessens et al., 1998, Goossens et al., 2006）。

尽管面向乘客和面向成本的模型强调不同的目标，但两种范式内绝大多数研究共享一个共同的结构简化：它们主要被表述为单周期优化问题，假设稳定、不随时间变化的乘客需求（Laporte and Mesa, 2020, Sch?bel, 2012）。这种表述在计算上是可处理的，适合长期战略规划，但它们忽略了实证文献中记录的日内乘客流、站点负载和线路利用率的变异（Bornd?rfer et al., 2017, Hu et al., 2024）。这些观察促使 LPP 转向多周期表述，显式捕捉需求和资源可用性的时间变化。这一研究流派涵盖了多周期交通规划的概念研究（Schrage, 2018）、带车辆周转的 LPP 特定模型（?ahin et al., 2020），以及最近集成车辆管理决策的双层优化方法（Yan et al., 2025）。

Sch?bel (2012) 表明，即使是 LPP 的基本单周期表述也是 NP 难的，突显了其固有的计算不可处理性。将模型扩展到多周期和车辆周转设置进一步加剧了这种复杂度，通过引入时间耦合、周期间依赖和资源连续性约束，将规划时间范围内的运营决策紧密联系在一起（?ahin et al., 2021, ?ahin et al., 2020）。这些扩展促使对大规模实例的可扩展和高效算法设计进行广泛研究。表 1 提供了文献中提出的主要算法框架的比较概览。

如表 1 所总结，早期研究集中在精确优化技术。Claessens et al. (1998) 开发了一个分支定界框架，通过减少和界定策略加速收敛，而 Bussieck et al. (2004) 引入了一种嵌入在分支切割框架内的变量固定启发式算法，结合有效不等式和系统预处理以提高计算效率。

后续研究越来越多地采用基于分解的方法来应对大规模 LPP 的可扩展性挑战。此类方法已被广泛应用于网络设计、设施选址和交通规划环境（Bucarey et al., 2022, Khatami et al., 2015, Lamontagne et al., 2024, Oliveira et al., 2022, Rahmaniani et al., 2017, Rahmaniani et al., 2024, Yuan et al., 2024）。在线路规划文献中，Sch?bel 和 Scholl (2004) 采用丹茨格 - 沃尔夫分解框架来利用块对角结构，而 Bornd?rfer et al. (2007) 通过列生成技术扩展了这一概念，通过集成有效不等式来加强下界。最近，Li et al. (2024) 为货运列车线路规划开发了一种基于 BD 的分支切割算法，证明分解算法在不牺牲最优性的情况下实现了计算可扩展性。此外，Feng et al. (2024) 使用对偶分解方法解决了一个集成整数规划模型，该模型同时确定城市轨道交通线路的列车服务路线和乘客流量分配，证明基于分解的方法在集成交通规划中的有效性。

BD 在大规模网络和交通优化中表现出强劲的性能，但其应用于 MPLPP-VR 受到 SP 整数结构的限制。多周期依赖和车辆周转约束创造了离散的、非凸的可行性空间，违反了生成 BD 割所需的对偶性假设。LBBD 通过用问题特定的推断取代对偶性，提供了一个更通用的分解框架。它通过域传播和逻辑蕴涵构建有效割，以组合方式连接 MP 和 SP 决策。这种机制产生了更紧的 MP 松弛并加速收敛，特别是当 SP 是离散的或基于约束的时候。LBBD 已应用于交通调度、集成规划和设施选址，在保持精确性的同时实现了高计算效率（Fischer and W?hlk, 2023, Hooker, 2007, Hooker and Ottosson, 2003, Roshanaei et al., 2017, Sun et al., 2019）。

在此背景下，我们的论文为 MPLPP-VR 开发了两种基于分解的算法。第一种是基于分离的算法，灵感来自 Pferschy 和 Staněk (2017)，它迭代求解一个简化了换乘约束的整数模型，随后重新引入被违反的约束。这种方法类似于旅行商问题中的子回路消除过程。虽然这种方法计算效率高，但检测被违反的换乘约束的分离步骤仍然很耗时。为了克服这一局限性，我们开发了第二种基于 LBBD 的更结构化算法，其中验证问题被重构为最大流/最小割模型，能够高效识别不可行性并实现更强的收敛行为。本文的主要贡献总结如下：
1. 我们识别周期间车辆流量守恒约束是 MPLPP-VR 中计算困难的主要来源，并提出了一种约束满足算法（CSA），通过可行性检查松弛并选择性重新引入这些约束。
2. 我们开发了一个 LBBD 框架，其中战略线路选择和服务频率决策由主问题处理，而换乘可行性在离散子问题中验证。
3. 我们将换乘可行性子问题重构为基于线路 - 时期节点的最大流和最小割问题，实现了多项式时间的可行性验证。
4. 我们从网络结构直接推导出特定问题的邦德斯可行性割，高效排除不可行主解并加速收敛。
5. 在真实和合成公共交通网络上的广泛计算实验证明，相对于单体 MILP 表述和基于 CSA 的方法，所提出的 LBBD-Max 框架具有可扩展性、鲁棒性和计算优势。

3. 问题表述

LPP 定义在直网络 PTN=(V, E) 上，其中 V 和 E 分别表示站点和直接连接的集合。规划时间范围被离散化为一个有序的时间段集合 T={t1, t2,…, t|T|}。对于每个时期 t ∈ T，边 e ∈ E 上的需求 d_te 是沿最短路径分配时期特定的 O–D 需求矩阵并聚合所有 O–D 对的结果流量而获得的。尽管这种分配在每个时期内是静态的，但它在时期之间变化；因此，需求波动是通过多周期结构而不是时期内动态路由来捕捉的（?ahin et al., 2020）。

候选线路集（线路池）表示为 L={l1, l2,…, l|L|}，其中每条线路表示 PTN 上的一条可行路径，并可服务于多条边。对于每条边 e ∈ E，子集 Le?L 包含遍历该边的所有线路。成本结构包括当线路运营时产生的固定开放成本 c_fl，以及与提供的服务水平相关的可变成本 c_sl。线路间的车辆换乘操作由 ρ_lk 参数化，它表示车辆从线路 l 移动到线路 k 的换乘持续时间，以时期为单位。表 2 总结了 MPLPP-VR 表述中使用的所有索引、参数和决策变量。

表 2.

模型公式化中使用的符号总结，包括集合、参数和决策变量。

**符号 | 描述**
**集合**
V | 车站集合。
E | 直接连接车站的链路集合。
??={??1,??2,…,??|??|} | 有序的时间周期集合。
??={??1,??2,…,??|??|} | 预定线路集合，这些线路是公共交通网络 (PTN) 上的路径。
???? | 包含链路 e 的线路子集合。

**参数**
?????? | 利用线路 l 所产生的固定成本。
?????? | 与线路 l 的服务能力相关的可变成本。
?????? | 周期 t 期间链路 e 上的乘客需求。
ρlk | 将车辆从线路 l 转移到线路 k 所需的周期数。
?? | 车辆的乘客容量。
?? | 系统中可用的车辆最大数量。
?? | 给定周期内一条线路上允许的最大车辆数。

**决策变量**
???? | 如果选择线路 l 运营则为 1，否则为 0。
?????? | 在周期 t 期间在线路 l 上运营的服务次数（频率或资源水平）。
??????,????????? | 在周期 ti 分配到线路 l 并在后续周期 tj 运营时转移到线路 k 的车辆数量（ti, tj?∈?T,?j?>?i）。

MPLPP-VR 包含三组决策：（i）线路选择决策，旨在确定规划视野内运营的最优线路子集，由 ?????∈?{0, 1} 表示；（ii）服务频率决策，确定每条活跃线路在每个周期运营的服务次数（或资源水平），由 ??????∈?+ 表示；以及（iii）车辆转移决策，控制车辆在线路和周期之间的周转，由 ??????,?????????∈?+ 表示，表示从周期 ti 的线路 l 转移到后续周期 tj 的线路 k 的车辆数量（ti, tj?∈?T,?j?>?i）。遵循 ?ahin 等人 (2020) 的方法，MPLPP-VR 被表述为以下整数规划模型：

(1a) minimize ∑??∈?????????????+∑??∈??∑??∈???????????????

(1b) subject to ∑??∈?????????????≥?????? ???∈??,???∈??,

(1c) ??????????????≥0 ???∈??,???∈??,

(1d) ∑??∈??0??????????≥0????????????,???????=?????? ???∈??,???∈??,

(1e) ∑??∈??0??????????≥0????????????,????????∑??∈??0??+???????≤|??|????,??+????????????=0 ???∈??0,???∈??,

(1f) ∑??∈??0∑??∈????0,????0???=??,

(1g) ∑??∈??0∑??∈??????,|??|+1?????0=??,

(1h) ????∈{0,1} ???∈??,

(1i) ??????∈?+ ???∈??,???∈??,

(1j) ????,???????∈?+ ???,??∈??0,???∈{0}∪??,???∈??∪{|??|+1},??
其中 ??0=??∪{??0} 且 l0 表示系统的初始状态，假设所有车辆从此开始。该虚拟线路用于对规划视野内车辆流的初始化和终止进行建模。

目标函数 (1a) 最小化总系统成本。约束 (1b) 保证所有时段内的出行需求得到满足。耦合约束 (1c) 确保仅在选定的线路上提供服务，其中 ?? 表示在单一周期内单条线路上可能运营的最大服务次数。约束 (1d) 建立了转移决策 w 与服务频率变量 v 之间的直接依赖关系。约束 (1e)-(1g) 代表车辆流量平衡关系，调节规划视野内线路和周期之间的车辆转移。具体而言，约束 (1e) 通过确保对于每条线路和每个时段，进入的车辆数量等于离开的车辆数量来强制实行按时段平衡，考虑到所有满足 tj?>?ti 的可行转移对 (ti, tj)。约束 (1f) 和 (1g) 保持车队一致性：在规划视野开始时恰好有 ?? 辆车从车库发出，且所有车辆都在结束时返回车库。最后，约束 (1h)-(1j) 定义了决策变量的定义域。

时刻表同步和换乘协调代表运营层面的决策，超出了本研究考虑的 Strategic 规划视野，因此未明确建模。相反，可行性是在周期聚合流量层面强制执行的，这支持了对车辆转移可行性的集中分析，并能够清晰地利用分解结构。第 6 节讨论这种建模选择的含义及可能的扩展。

**4. 解决方案算法**

在本节中，我们开发了两种算法来解决 MPLPP-VR：（i）CSA 和（ii）增强有最大流过程的 LBBD。CSA 提供了一种高效的精确算法，并作为评估 LBBD 框架的强基准。在此基础上，LBBD 整合了网络优化原理以提高计算效率。它不解决完整的基于优化的子问题，而是通过将可行性违规重新表述为等价的最大流问题来识别并解决它们。这些问题可以使用专门的网络算法高效求解，从而加速收敛并能够解决大规模实例。

**4.1. 约束满足算法**

提出的 CSA 基于经典的约束松弛范式，概念上受到 Dantzig 等人 (1954) 关于旅行商问题的开创性工作启发。在此算法中，首先通过松弛一组约束来求解原始问题的简化版本。然后，算法迭代地识别并重新引入松弛集合中被违反的约束，逐步细化可行域，直到收敛到可行且通常是最优的解。

虽然迭代约束强制的一般思想已被广泛应用于组合优化，但其正式的算法实现首次由 Pferschy 和 Staněk (2017) 阐述，他们通过系统地添加子回路消除约束证明了其对旅行商问题的有效性。此后，该范式已成功扩展到大规模应用，如公共交通网络设计 (Farzadnia and Lysgaard, 2021)、共享出行再平衡 (Chastre and Andrade, 2023) 和最后一英里配送优化 (Raghavan and Zhang, 2024)，确认了其对于以复杂可行性结构为特征的问题的可扩展性和适应性。

我们通过松弛车辆转移平衡约束 (1e) 将此范式适配到 MPLPP-VR。主问题 (MP) 同时优化线路选择、服务频率和车辆转移决策，对应于问题 1，但松弛了平衡约束。MP 使用商业求解器求解至最优。然后通过强制松弛转移约束的可行性子问题 (SP) 对所得解进行验证。任何检测到的违规都表示为可行性割，并迭代地纳入 MP 中，随后重新优化，直到满足所有转移平衡约束或达到预定的时间限制。

车辆转移平衡约束 (1e) 的验证是通过分析从 MP 获得的转移决策来完成的。在完美的流量守恒下，(1e) 中的每个约束求值为零，表明进入和离开每条线路 l 在周期 t 的车辆总数是平衡的。当 MP 解违反此平衡时，约束的左侧变为正值或负值，分别表示车辆过剩或不足。这些违规随后用于构建可行性割，以在后续迭代中恢复车辆平衡。

为了量化这些偏差，为每个 (l, t) 对引入了两个连续非负变量：?????? 和 ??′?????，分别表示车辆不足和过剩。如果 ??????>0，线路 l 在周期 t 存在车辆短缺，而 ??′?????>0 表示过剩。这些变量捕获不平衡的大小和方向，并构成了可行性问题的基础，表述为以下线性优化模型：

(2a) minimize ∑??∈??∑??∈??(??????+??′?????)

(2b) subject to ∑??∈??0??????????≥0?????????????????,????????∑??∈??0??+???????≤|??|?????????,??+????????????+?????????′?????=0 ???∈??0,???∈??,

(2c) ??????,??′?????≥0 ???∈??0,???∈??,

其中 ???????????,????????? 表示从 MP 获得的转移解。

目标函数 (2a) 最小化所有线路和时间周期的总不平衡。理想情况下，最优目标值等于零，表明每个车辆转移平衡约束都得到满足。正目标值意味着至少存在一个被违反的约束，其中 ??????>0（不足）或 ??′?????>0（过剩），从而识别偏离守恒的线路和时段。这些被违反的约束随后被重新引入 MP，并重新优化问题。该过程持续迭代，直到 (2a) 的目标值达到零，此时解满足所有转移平衡约束，对于完整的 MPLPP-VR 是可行的。图 1 说明了这种迭代过程。

下载：下载高分辨率图像 (149KB)
下载：下载全尺寸图像
图 1. 提出的 CSA 流程图。该过程迭代求解 MP 和可行性 SP，重新引入被违反的转移约束，直到满足所有平衡条件。

为了提高迭代过程的计算效率，CSA 采用了一种专用的可行性检查机制，在每次 MP 迭代后验证车辆平衡。该机制不直接求解 (2)，而是隔离被违反的约束并迭代地重新引入它们，如算法 1 所述。

该过程高效地检测 (1e) 中平衡约束的违规并将其重新引入 MP，确保收敛到可行且平衡的解。根据每次迭代的结果，发生以下两种情况之一：
1. 如果检测到违反的平衡约束，则将 (1e) 中的相应约束纳入当前的 MP 公式中。
2. 如果 (1e) 中的所有平衡约束都得到满足，则当前解 (y*, v*, w*) 被视为对原始 MPLPP-VR 可行，并被证明是最优的，因为 MP 已经被求解至最优。

可行性问题 (2) 的计算复杂度，以及等效的关联检查机制，随着线路和规划时段数量的增加而增长。因此，对于大规模实例，此过程变得计算密集。为了解决这一限制，下一节将可行性检查问题重新表述为最大流模型，使得能够应用高效的网络优化算法，从而大幅加速收敛。

**4.2. 带最大流割的 LBBD**

提出的 LBBD 框架不仅分离转移平衡约束，还将所有车辆转移决策委派给 SP。这种设计允许 MP 专注于战略线路选择和服务频率规划，同时保留基本的多周期车辆周转结构。

在此框架中，SP 强制要求需求约束 (1d) 和转移平衡约束 (1e) 的车辆可行性条件。为每个 (l, t) 对定义了两对连续非负变量，(??????,??′?????) 和 (??????,??′?????)，以量化相应约束中的短缺和过剩。这些变量明确表示不可行性，并作为 SP 公式化的基础：

(3a) minimize ∑??∈??∑??∈??(??????+??????+??′?????+??′?????)

(3b) subject to ∑??∈??0??????????≥0????????????,???????+?????????′?????=ˉ?????? ???∈??,???∈??,

(3c) ∑??∈??0??????????≥0????????????,????????∑??∈??0??+???????≤|??|????,??+????????????+?????????′?????=0 ???∈??0,???∈??,

(3d) ??????,??′?????≥0 ???∈??,???∈??,

(3e) ??????,??′?????≥0 ???∈??0,???∈??,

(3f) ????,???????∈?+ ???∈??0,???∈??,???∈??∪{|??|+1},??
其中 ˉ?????? 表示从 MP 导出的车辆分配。

目标函数 (3a) 最小化所有约束的总违规。零目标确认可行性，而正值通过相应的非零松弛或剩余变量识别被违反的约束。这些违规随后用于生成特定于问题的 BD 割，并迭代地纳入 MP。

从计算角度来看，问题 3 在维度和约束密度方面表现出组合增长。每个额外的线路 - 时段对引入新的平衡和转移约束，从而增加模型复杂度。为了缓解这种低效，问题 3 可以等效地重新表述为网络流问题，其中车辆转移表示为有向二分图中虚拟供应和需求节点之间的可行弧。这种表述允许使用多项式时间最大流算法来验证可行性，并作为提出的分解框架的基础。

给定从 MP 获得的最优解，我们构建一个有向二分图来表示潜在的车辆转移。图定义为 ??=(??∪??,??)，其中 ?? 和 ?? 表示供应和需求节点集合，每个对应于一个线路 - 时段对 (l, t)?∈?L?×?T。这些节点是抽象结构，代表车辆供应和需求状态，而不是物理位置。弧集 ?? 包含节点之间所有可行的转移连接，捕获规划视野内可行的车辆流转换。该图的构造定义如下：
* 对于每条线路 l?∈?L 和每个时段 ??∈??∪{0,|??|+1}，定义两个节点：供应节点 ?????? 和需求节点 ??????。对于虚拟线路 l0?∈?L0，施加边界条件，使得在时段 ??=0 时，仅供应节点 ??0??0 处于活动状态并初始化总车辆供应为 ??，而在时段 ??=|??|+1 时，仅需求节点 ??|??|+1??0 处于活动状态并被分配总车辆需求为 ??。
* 对于每对节点 (????????,????????)，如果 ??=??+???????????，则引入一条弧，其中 ??????????? 表示线路 li 和 lj 之间的转移时长（以时段计）。每个可行弧被分配无限容量以允许不受限制的车辆流，而所有其他弧被分配零容量，从而消除不可行的转移。

图 2 说明了与当前 MP 解相关的二分网络。SP 的可行性等价于 G 中可行流的存在。在此网络中，每个供应节点 ??????∈?? 发出等于其可用车辆容量的流，每个需求节点 ??????∈?? 接收等于其所需车辆分配的流。可行的流配置同时满足所有容量和守恒约束，意味着车辆可用性、转移和需求在所有线路和时段之间完美平衡。因此，这种流的存在保证了 MP 解 ˉ?????? 满足原始 MPLPP-VR 的所有可行性条件。

下载：下载高分辨率图像 (383KB)
下载：下载全尺寸图像
图 2. 与 MP 解相关的最大流重新表述的二分网络表示。每个节点代表由线路 - 时段对定义的供应或需求状态，弧捕获跨时段和线路的可行车辆转移。

为了计算最大流，我们将二分图转换为规范的单源单汇网络。我们引入一个超源节点 O 和一个超汇节点 O′。

由此产生的最大流问题可以通过任何多项式时间算法求解，例如推 - 重贴标法（Goldberg and Tarjan, 1988）或埃德蒙兹 - 卡普算法；后者用于我们的实现中。变换过程如下：•对于每个供应节点 ??????（对于所有 l?∈?L,?t?∈?T），包含有向弧 (??,??????)，容量设置为可用车辆供应量 ˉ??????。•对于每个需求节点 ??????（对于所有 l?∈?L,?t?∈?T），包含有向弧 (??????,??′)，容量设置为所需车辆分配量 ˉ??????。图 3 描绘了从原始二分图获得的增广网络。随后的示例逐步构建了一个具有两条线路和两个时期的简化实例的流网络。

示例 1

考虑一个具有两条线路（??={??1,??2}）和两个时期（??={1,2}）的简化实例。初始车辆总供应量为 ??=6，分布在整个规划范围内。每条线路和每个时期的车辆分配如下：在第 1 时期，线路 l1 分配 3 辆车（??1??1=3），线路 l2 分配 2 辆车（??1??2=2）；在第 2 时期，线路 l1 接收 2 辆车（??2??1=2），线路 l2 接收 4 辆车（??2??2=4）。网络中相应的供应量和需求量定义如下。在规划范围开始时，初始车辆池 ??0??0 提供 +6 的供应。对于第 1 时期，供应量在 ??1??1 为 +3，在 ??1??2 为 +2，而相应的需求量在 ??1??1 为 -3，在 ??1??2 为 -2。在第 1 时期有一辆车保持闲置，这意味着车辆段保留了 +1 的盈余，记为 ??1??0=+1。对于第 2 时期，供应量在 ??2??1 为 +2，在 ??2??2 为 +4，相应的需求量在 ??2??1 为 -2，在 ??2??2 为 -4。在规划范围结束时，最终车辆池 ??3??0 需要总共 -6 的需求。图 4 说明了该实例的完整二分流网络，显示了随时间推移供应节点和需求节点之间的车辆流量分配。

下载：下载高分辨率图像 (417KB)
下载：下载全尺寸图像

图 4. 具有两条线路和两个时期的示例实例的二分网络表示。该图显示了跨时期的供应节点和需求节点之间的车辆分配。

下载：下载高分辨率图像 (465KB)
下载：下载全尺寸图像

图 3. 用于与 MP 解决方案相关的最大流重构的增广二分网络表示。该网络包括一个超级源节点 O 和一个超级汇节点 O′。

MPLPP-VR 中的车辆转移可行性基于经典网络流定理：可行流正是满足所有转移和平衡约束的流。这种等价性为验证车辆转移可行性提供了必要且充分的条件。

定理 1

（详情见 Ahuja 等 1993 年。）原始有向二分图中存在可行流当且仅当相应变换网络中的最大流饱和了所有源自超级源的弧和所有终止于超级汇的弧。

对于给定的增广二分图，如果计算出的最大流 Fmax 严格小于超级源的总供应量，则不可行性表现为剩余网络中的未饱和弧，剩余网络是编码剩余容量以供潜在流量增广的有向图。这些违规被重构为组合可行性割，并纳入 MP。MP 和 SP 然后迭代，直到满足所有流量守恒约束；一旦达到收敛，保证解是转移可行的（即满足所有线路间和时期间的转移平衡要求），并且相对于原始 MPLPP-VR 目标是最佳的。推论 1 形式化了饱和最大流的存在与车辆转移平衡约束的完全满足之间的等价性。

推论 1

设 (y*, v*) 为给定的最优 MP 解，设 Fmax 表示变换网络 G(y*, v*) 中的最大流值。那么解 (y*, v*) 满足 MPLPP-VR 的所有车辆转移约束当且仅当 Fmax 等于从超级源节点发出的总供应量，这等价于超级汇节点吸收的总需求量。

证明

证明。如果在最优流中所有离开 O 的弧（等价于所有进入 O′ 的弧）都被饱和，那么发出的总供应量等于吸收的总需求量。这种饱和条件意味着由服务水平 v* 诱导的容量被充分利用，没有供应剩余，也没有需求未满足。在这种情况下，所有线路间和时期间的转移要求（即约束 (1d)-(1g)）得到满足。因此，饱和流证明 (y*, v*) 相对于完整 MPLPP-VR formulation 中的车辆转移平衡约束是可行的。

对于变换二分图的给定实例，车辆转移 SP 被表述为单源单汇最大流问题。根据最大流最小割定理，从超级源节点 O 到超级汇节点 O′ 的最大流值等于最小 ?????′ 割的容量。形式上：
1. 割是节点集的二分 (??,???????)，使得 O?∈?S 且 ??′∈???????。
2. 割 (??,???????) 的容量为 cap?(??,???????)=∑(??,??)∈????∈??,??∈??????????????，其中 uij 是弧 (i, j) 的容量。
3. 最小割是所有有效源 - 汇划分中容量最小的割。

如果计算出的最大流严格小于当前 MP 解隐含的总供应量，那么剩余网络揭示了一个瓶颈，相关的最小割证实了不可行性。在这种情况下，利用割的结构导出一个有效不等式，即可行性割，将当前的不可行解排除在 MP 之外，并将算法引导至转移可行解区域。

如果相应的最大流未能饱和所有源自超级源 O 的弧，则认为 MP 解 (y*, v*) 不可行，这表明并非所有所需的车辆转移都能被容纳，即如果
(4)??max<λ，
其中 λ 表示 mp 解隐含的总车辆供应量，
(5)λ=∑????∈??0,??∈??∪{0,|??|+1}????????，
且 ???????? 是分配给线路 lj 在时期 t 的车辆数量。为了消除此类不可行配置，我们从最小 o-o′ 割的结构中导出一个可行性割。设 ??????? 表示最小割的汇侧划分。割约束为：
(6)∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}≥∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}，
其中 ??{????????∈???????} 和 ??{????????∈???????} 是指示函数，如果相应节点属于 ??????? 则为 1，否则为 0。不等式 (6) 确保跨越最小割的容量至少为 λ，从而强制执行当前 mp 解下车辆转移计划的可行性。

引理 1

不等式 (6) 是 mplpp-vr 的有效 bd 可行性割。

证明

证明。根据最大流最小割定理（ahuja 等，1993 年），超级源 o 和超级汇 o′ 之间的最大流等于最小 o-o′ 割的容量。对于 mp 解 (y*, v*) 要可行，相应的车辆转移 sp 必须存在一个满足 ??max=∑(??,????????)∈??????????=∑(????????,??′)∈??????????=λ 的最大流。如果违反此条件，某些转移要求无法满足，意味着 mp 解不可行。具体来说，来自需求节点 ????????∈??????? 到超级汇 o′ 的总流入超过了从超级源 o 到供应节点 ????????∈??????? 的总流出。这种不平衡表明，在网络的可用容量内，有一部分车辆转移无法完成。为了消除此类不可行配置，基于最小割的容量构建了一个有效的 bd 可行性割。不等式 (6) 强制执行离开 o 的弧的总容量不小于进入 o′ 的弧的总容量。此条件保证流网络能够容纳所有所需的转移，从而确保最小割容量等于 λ 并保持车辆转移计划的可行性。

示例 2

基于示例 1，我们通过引入跨连续时期虚拟供应和需求节点之间结构化且操作一致的可行转移集来扩展流网络。可行车辆转移遵循两个主要原则：
1. 线路 l0 可以将车辆转移到下一时期的所有线路：(??????0,????+1????),?????∈??,???∈{0,1,2,3}。
2. 每条线路 lj 可以将车辆转移到下一时期的同一条线路：(????????,????+1????),?????∈??,???∈{0,1,2,3}。

为了捕捉偶尔的远程重新分配，我们也允许单次两个时期的转移，即第 1 时期线路 l1 的车辆可以直接重新分配给第 3 时期线路 l2。每个转移弧被分配无限容量，表示不受限制的车辆流，而所有其他潜在的 s → d 连接被分配容量 0，使其不可行。对该受限网络应用标准的最大流最小割算法，得到 16 辆车的总可行流，低于 18 辆车的总供应量。因此，该网络对应的 mp 解不可行。相关的最小割，容量也为 16，隔离了弧
??★={(??,??0??0),(??,??1??0),(??,??1??1),(??,??2??1),(??,??2??2),(??1??2,??′)}。
根据不等式 (6)，此割定义了以下 bd 可行性割：
(7)∑(??,????????)∈??★????????≥∑(????????,??′)∈??★????????，
这排除了相应的不可行解。算法 2 概述了 lbbd-max 过程。

5. 计算实验

在本节中，我们将所提出分解算法的性能与商业求解器 gurobi 进行比较。作为额外的基准，我们包含了 ?ahin 等人 (2021) 的局部分支启发式算法。比较沿着四个分析维度进行：(i) 计算效率，通过运行时间分布和收敛特性量化；(ii) 解质量，相对于最优或近最优参考解衡量；(iii) 可扩展性，在不同问题规模和网络拓扑下评估；以及 (iv) 鲁棒性，通过对受控数据集进行合成压力测试来检查关键模型参数的敏感性。

5.1. 实验设置

我们使用三个具有不同规模和拓扑特征的实时网络来评估所提出算法的性能。这些网络在文献中被广泛研究，其主要特征总结如下：
1. 伊斯坦布尔 metrobüs。该系统是土耳其第一条快速公交走廊，连接伊斯坦布尔的欧洲和亚洲部分。它提供高容量和可靠的服务，显著减少城市拥堵和出行时间。该网络由 44 个车站、45 条边和 9 条在专用公交车道上运行的闭合线路组成。
2. 雅典地铁。该系统服务于希腊首都的大都市区，提供快速可靠的铁路服务。它由 51 个车站、52 条边和 59 条闭合线路组成。该网络的详细描述见 harbering 等 (1999)。
3. 基多 trolébus。该系统在厄瓜多尔运行，采用主干 - 支线结构，电动无轨电车在专用车道上运行以提供主干服务。该网络具有树状拓扑结构，有 278 个车站、277 条边和 318 条闭合线路 (torres 等，2011)。

为了补充这些基准系统，构建了一个包含 122 条线路的额外实例，称为 quito trolébus-122。该实例保留了与全规模 quito trolébus-318 网络相同的车站和边配置，但包含较小的线路子集。它作为评估可扩展性和性能敏感性的中间案例。所有测试实例的结构特征总结在表 3 中。此外，生成了一组合成数据集，以隔离并系统分析与网络设计阶段相关的关键模型参数的影响。

表 3. 基准实例的结构特征。每个实例由车站数量、边数量、线路数量定义，以及相应的固定成本。实例分为 s（小规模）、m（中规模）和 l（大规模）。

实例 车站数量 边数量 线路数量 固定成本
istanbul (s) 44 45 9 180
athens (m) 51 52 59 180
quito-122 (l) 278 277 122 190
quito-318 (l) 278 277 318 190

确定测试实例后，我们现在详细说明所有实验中使用的数据和参数设置。我们假设每条线路段每公里的单位成本为 1。乘客需求源自 18 小时规划范围（上午 6:00 至午夜）内聚合的 o-d 矩阵，并通过最短路径分配转换为基于边的需求，以与网络流模型对齐。对于伊斯坦布尔 metrobüs 系统，我们纳入三种需求场景，分别对应工作日、周六和周日服务水平。线路 l 和 k 之间的转移时间包括 l 上的线路内行驶时间以及将车辆从线路 l 终点站重新定位到线路 k 起点所需的空驶行驶时间。基础参数设置为 ??=250, ??=200, 和 ??=36。所有计算实验都在配备 intel core i7-4770 cpu (3.40 ghz) 和 16 gb 内存的工作站上使用 gurobi optimizer 12.0.3 和 python 3.9.4 进行。lbbd 框架内的最大流 sp 使用 networkx 库中的 edmonds-karp 算法求解，该算法保证具有复杂度 ???(|??∥??|2) 的多项式时间性能。 其中 λ 表示 mp 解隐含的总车辆供应量， (5)λ=∑????∈??0,??∈??∪{0,|??|+1}????????， 且 ???????? 是分配给线路 lj 在时期 t 的车辆数量。为了消除此类不可行配置，我们从最小 o-o′ 割的结构中导出一个可行性割。设 ??????? 表示最小割的汇侧划分。割约束为： (6)∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}≥∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}， 其中 ??{????????∈???????} 和 ??{????????∈???????} 是指示函数，如果相应节点属于 ??????? 则为 1，否则为 0。不等式 (6) 确保跨越最小割的容量至少为 λ，从而强制执行当前 mp 解下车辆转移计划的可行性。 引理 1 不等式 (6) 是 mplpp-vr 的有效 bd 可行性割。 证明 证明。根据最大流最小割定理（ahuja 等，1993 年），超级源 o 和超级汇 o′ 之间的最大流等于最小 o-o′ 割的容量。对于 mp 解 (y*, v*) 要可行，相应的车辆转移 sp 必须存在一个满足 ??max=∑(??,????????)∈??????????=∑(????????,??′)∈??????????=Λ 的最大流。如果违反此条件，某些转移要求无法满足，意味着 mp 解不可行。具体来说，来自需求节点 ????????∈??????? 到超级汇 o′ 的总流入超过了从超级源 o 到供应节点 ????????∈??????? 的总流出。这种不平衡表明，在网络的可用容量内，有一部分车辆转移无法完成。为了消除此类不可行配置，基于最小割的容量构建了一个有效的 bd 可行性割。不等式 (6) 强制执行离开 o 的弧的总容量不小于进入 o′ 的弧的总容量。此条件保证流网络能够容纳所有所需的转移，从而确保最小割容量等于 λ 并保持车辆转移计划的可行性。 示例 2 基于示例 1，我们通过引入跨连续时期虚拟供应和需求节点之间结构化且操作一致的可行转移集来扩展流网络。可行车辆转移遵循两个主要原则： 1. 线路 l0 可以将车辆转移到下一时期的所有线路：(??????0,????+1????),?????∈??,???∈{0,1,2,3}。 2. 每条线路 lj 可以将车辆转移到下一时期的同一条线路：(????????,????+1????),?????∈??,???∈{0,1,2,3}。 为了捕捉偶尔的远程重新分配，我们也允许单次两个时期的转移，即第 1 时期线路 l1 的车辆可以直接重新分配给第 3 时期线路 l2。每个转移弧被分配无限容量，表示不受限制的车辆流，而所有其他潜在的 s → d 连接被分配容量 0，使其不可行。对该受限网络应用标准的最大流最小割算法，得到 16 辆车的总可行流，低于 18 辆车的总供应量。因此，该网络对应的 mp 解不可行。相关的最小割，容量也为 16，隔离了弧 ??★={(??,??0??0),(??,??1??0),(??,??1??1),(??,??2??1),(??,??2??2),(??1??2,??′)}。 根据不等式 (6)，此割定义了以下 bd 可行性割： (7)∑(??,????????)∈??★????????≥∑(????????,??′)∈??★????????， 这排除了相应的不可行解。算法 2 概述了 lbbd-max 过程。 5. 计算实验 在本节中，我们将所提出分解算法的性能与商业求解器 gurobi 进行比较。作为额外的基准，我们包含了 ?ahin 等人 (2021) 的局部分支启发式算法。比较沿着四个分析维度进行：(i) 计算效率，通过运行时间分布和收敛特性量化；(ii) 解质量，相对于最优或近最优参考解衡量；(iii) 可扩展性，在不同问题规模和网络拓扑下评估；以及 (iv) 鲁棒性，通过对受控数据集进行合成压力测试来检查关键模型参数的敏感性。 5.1. 实验设置 我们使用三个具有不同规模和拓扑特征的实时网络来评估所提出算法的性能。这些网络在文献中被广泛研究，其主要特征总结如下： 1. 伊斯坦布尔 metrobüs。该系统是土耳其第一条快速公交走廊，连接伊斯坦布尔的欧洲和亚洲部分。它提供高容量和可靠的服务，显著减少城市拥堵和出行时间。该网络由 44 个车站、45 条边和 9 条在专用公交车道上运行的闭合线路组成。 2. 雅典地铁。该系统服务于希腊首都的大都市区，提供快速可靠的铁路服务。它由 51 个车站、52 条边和 59 条闭合线路组成。该网络的详细描述见 harbering 等 (1999)。 3. 基多 trolébus。该系统在厄瓜多尔运行，采用主干 - 支线结构，电动无轨电车在专用车道上运行以提供主干服务。该网络具有树状拓扑结构，有 278 个车站、277 条边和 318 条闭合线路 (torres 等，2011)。 为了补充这些基准系统，构建了一个包含 122 条线路的额外实例，称为 quito trolébus-122。该实例保留了与全规模 quito trolébus-318 网络相同的车站和边配置，但包含较小的线路子集。它作为评估可扩展性和性能敏感性的中间案例。所有测试实例的结构特征总结在表 3 中。此外，生成了一组合成数据集，以隔离并系统分析与网络设计阶段相关的关键模型参数的影响。 表 3. 基准实例的结构特征。每个实例由车站数量、边数量、线路数量定义，以及相应的固定成本。实例分为 s（小规模）、m（中规模）和 l（大规模）。 实例 车站数量 边数量 线路数量 固定成本 istanbul (s) 44 45 9 180 athens (m) 51 52 59 180 quito-122 (l) 278 277 122 190 quito-318 (l) 278 277 318 190 确定测试实例后，我们现在详细说明所有实验中使用的数据和参数设置。我们假设每条线路段每公里的单位成本为 1。乘客需求源自 18 小时规划范围（上午 6:00 至午夜）内聚合的 o-d 矩阵，并通过最短路径分配转换为基于边的需求，以与网络流模型对齐。对于伊斯坦布尔 metrobüs 系统，我们纳入三种需求场景，分别对应工作日、周六和周日服务水平。线路 l 和 k 之间的转移时间包括 l 上的线路内行驶时间以及将车辆从线路 l 终点站重新定位到线路 k 起点所需的空驶行驶时间。基础参数设置为 ??=250, ??=200, 和 ??=36。所有计算实验都在配备 intel core i7-4770 cpu (3.40 ghz) 和 16 gb 内存的工作站上使用 gurobi optimizer 12.0.3 和 python 3.9.4 进行。lbbd 框架内的最大流 sp 使用 networkx 库中的 edmonds-karp 算法求解，该算法保证具有复杂度 ???(|??∥??|2)>其中 λ 表示 mp 解隐含的总车辆供应量，
(5)λ=∑????∈??0,??∈??∪{0,|??|+1}????????，
且 ???????? 是分配给线路 lj 在时期 t 的车辆数量。为了消除此类不可行配置，我们从最小 o-o′ 割的结构中导出一个可行性割。设 ??????? 表示最小割的汇侧划分。割约束为：
(6)∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}≥∑????∈??0,??∈??∪{0,|??|+1}??????????{????????∈???????}，
其中 ??{????????∈???????} 和 ??{????????∈???????} 是指示函数，如果相应节点属于 ??????? 则为 1，否则为 0。不等式 (6) 确保跨越最小割的容量至少为 λ，从而强制执行当前 mp 解下车辆转移计划的可行性。

引理 1

不等式 (6) 是 mplpp-vr 的有效 bd 可行性割。

证明

证明。根据最大流最小割定理（ahuja 等，1993 年），超级源 o 和超级汇 o′ 之间的最大流等于最小 o-o′ 割的容量。对于 mp 解 (y*, v*) 要可行，相应的车辆转移 sp 必须存在一个满足 ??max=∑(??,????????)∈??????????=∑(????????,??′)∈??????????=λ 的最大流。如果违反此条件，某些转移要求无法满足，意味着 mp 解不可行。具体来说，来自需求节点 ????????∈??????? 到超级汇 o′ 的总流入超过了从超级源 o 到供应节点 ????????∈??????? 的总流出。这种不平衡表明，在网络的可用容量内，有一部分车辆转移无法完成。为了消除此类不可行配置，基于最小割的容量构建了一个有效的 bd 可行性割。不等式 (6) 强制执行离开 o 的弧的总容量不小于进入 o′ 的弧的总容量。此条件保证流网络能够容纳所有所需的转移，从而确保最小割容量等于 λ 并保持车辆转移计划的可行性。

示例 2

基于示例 1，我们通过引入跨连续时期虚拟供应和需求节点之间结构化且操作一致的可行转移集来扩展流网络。可行车辆转移遵循两个主要原则：
1. 线路 l0 可以将车辆转移到下一时期的所有线路：(??????0,????+1????),?????∈??,???∈{0,1,2,3}。
2. 每条线路 lj 可以将车辆转移到下一时期的同一条线路：(????????,????+1????),?????∈??,???∈{0,1,2,3}。

为了捕捉偶尔的远程重新分配，我们也允许单次两个时期的转移，即第 1 时期线路 l1 的车辆可以直接重新分配给第 3 时期线路 l2。每个转移弧被分配无限容量，表示不受限制的车辆流，而所有其他潜在的 s → d 连接被分配容量 0，使其不可行。对该受限网络应用标准的最大流最小割算法，得到 16 辆车的总可行流，低于 18 辆车的总供应量。因此，该网络对应的 mp 解不可行。相关的最小割，容量也为 16，隔离了弧
??★={(??,??0??0),(??,??1??0),(??,??1??1),(??,??2??1),(??,??2??2),(??1??2,??′)}。
根据不等式 (6)，此割定义了以下 bd 可行性割：
(7)∑(??,????????)∈??★????????≥∑(????????,??′)∈??★????????，
这排除了相应的不可行解。算法 2 概述了 lbbd-max 过程。

5. 计算实验

在本节中，我们将所提出分解算法的性能与商业求解器 gurobi 进行比较。作为额外的基准，我们包含了 ?ahin 等人 (2021) 的局部分支启发式算法。比较沿着四个分析维度进行：(i) 计算效率，通过运行时间分布和收敛特性量化；(ii) 解质量，相对于最优或近最优参考解衡量；(iii) 可扩展性，在不同问题规模和网络拓扑下评估；以及 (iv) 鲁棒性，通过对受控数据集进行合成压力测试来检查关键模型参数的敏感性。

5.1. 实验设置

我们使用三个具有不同规模和拓扑特征的实时网络来评估所提出算法的性能。这些网络在文献中被广泛研究，其主要特征总结如下：
1. 伊斯坦布尔 metrobüs。该系统是土耳其第一条快速公交走廊，连接伊斯坦布尔的欧洲和亚洲部分。它提供高容量和可靠的服务，显著减少城市拥堵和出行时间。该网络由 44 个车站、45 条边和 9 条在专用公交车道上运行的闭合线路组成。
2. 雅典地铁。该系统服务于希腊首都的大都市区，提供快速可靠的铁路服务。它由 51 个车站、52 条边和 59 条闭合线路组成。该网络的详细描述见 harbering 等 (1999)。
3. 基多 trolébus。该系统在厄瓜多尔运行，采用主干 - 支线结构，电动无轨电车在专用车道上运行以提供主干服务。该网络具有树状拓扑结构，有 278 个车站、277 条边和 318 条闭合线路 (torres 等，2011)。

为了补充这些基准系统，构建了一个包含 122 条线路的额外实例，称为 quito trolébus-122。该实例保留了与全规模 quito trolébus-318 网络相同的车站和边配置，但包含较小的线路子集。它作为评估可扩展性和性能敏感性的中间案例。所有测试实例的结构特征总结在表 3 中。此外，生成了一组合成数据集，以隔离并系统分析与网络设计阶段相关的关键模型参数的影响。

表 3. 基准实例的结构特征。每个实例由车站数量、边数量、线路数量定义，以及相应的固定成本。实例分为 s（小规模）、m（中规模）和 l（大规模）。

实例 车站数量 边数量 线路数量 固定成本
istanbul (s) 44 45 9 180
athens (m) 51 52 59 180
quito-122 (l) 278 277 122 190
quito-318 (l) 278 277 318 190

确定测试实例后，我们现在详细说明所有实验中使用的数据和参数设置。我们假设每条线路段每公里的单位成本为 1。乘客需求源自 18 小时规划范围（上午 6:00 至午夜）内聚合的 o-d 矩阵，并通过最短路径分配转换为基于边的需求，以与网络流模型对齐。对于伊斯坦布尔 metrobüs 系统，我们纳入三种需求场景，分别对应工作日、周六和周日服务水平。线路 l 和 k 之间的转移时间包括 l 上的线路内行驶时间以及将车辆从线路 l 终点站重新定位到线路 k 起点所需的空驶行驶时间。基础参数设置为 ??=250, ??=200, 和 ??=36。所有计算实验都在配备 intel core i7-4770 cpu (3.40 ghz) 和 16 gb 内存的工作站上使用 gurobi optimizer 12.0.3 和 python 3.9.4 进行。lbbd 框架内的最大流 sp 使用 networkx 库中的 edmonds-karp 算法求解，该算法保证具有复杂度 ???(|??∥??|2) 的多项式时间性能。>

除非另有说明，求解器使用默认设置，相对 MIP 间隙容忍度为 0.01%，时间限制为 86,400 秒（24 小时）。

5.2. 比较性能分析

我们首先检查所提出算法的计算行为。观察 1 结合表 4 和图 5 分析了运行时间性能。观察 2 结合表 5 扩展了这一分析，通过评估获得结果的解质量和比较最优性。

**观察 1（计算时间模式）。** 图 5 以对数刻度呈现了雅典、基多 -122 和基多 -318 实例的计算时间对比可视化。柱子对应 Gurobi（灰色）、局部分支（蓝色）、CSA（橙色）和 LBBD-Max（深绿色）。x 轴代表问题实例，y 轴报告总计算时间（秒），上限为时间限制 86,400 秒。伊斯坦布尔 Metrobüs 实例被排除在此分析之外，因为在最苛刻的配置下，所有算法都能在不到三秒内解决它们。结果显示，LBBD-Max 在所有实例中实现了最佳计算性能，且随着网络大小和结构复杂性的增加，其优势变得更加明显。

对于雅典这样的小型和中型实例，所有方法都在一小时内收敛。然而，LBBD-Max 仅用 4 秒完成，而 CSA 为 417 秒，局部分支为 1050 秒，Gurobi 为 1254 秒。在更大的网络中，性能差距显著扩大。对于基多 -122，Gurobi 需要近 59,000 秒才能达到最优，而 CSA 和局部分支分别在 9509 和 18,000 秒内完成。相比之下，LBBD-Max 仅用 82 秒解决了同一实例，比 CSA 快约 116 倍，比 Gurobi 快超过 99%。

可扩展性效应在最大实例基多 -318 上最为明显。Gurobi 和局部分支找到了可行解但未能在时间限制内收敛，而 CSA 在分配时间内未识别出可行解。相比之下，LBBD-Max 在 3,606 秒内达到了证明的最优性，相当于时间限制的约 4%。

**观察 2（解质量比较）。** 表 5 报告了 Gurobi、局部分支、CSA 和 LBBD-Max 在所有基准实例中获得的最佳目标值。对于伊斯坦布尔和雅典网络，所有算法产生的目标值相同，确认了在低复杂度情况下一致性和正确性。然而，随着网络大小的增加，解质量和鲁棒性的显著差异随之出现。

对于基多 -122 实例，所有方法实现了几乎相同的目标值，局部分支相对于 Gurobi 显示出 +0.01% 的轻微恶化，表明其启发式搜索中有轻微的精度损失；LBBD-Max 以快得多的速度识别出最优解。在最大实例基多 -318 中，Gurobi 达到时间限制而未收敛，局部分支的偏差略微增加到 +0.03%。相比之下，提出的 LBBD-Max 相比 Gurobi 找到的最佳解实现了 0.47% 的改进，并且所用的计算时间只占其中一小部分（表 4）。另一方面，CSA 在时间限制内未能找到可行解，反映了在每次迭代中将子问题作为线性规划求解的计算负担。

总体而言，结果证实了提出的 LBBD-Max 框架不仅实现了巨大的计算增益，还提高了大规模现实世界网络中的鲁棒性和解质量。SP 的网络流重构减少了 MP 和 SP 之间的不可行性传播，增强了迭代过程的稳定性和收敛性。相比之下，像局部分支这样的启发式算法随着决策空间维度的增加而性能降低，限制了其在更大实例上的可扩展性。

**表 4.** 计算时间及相对于 Gurobi 的运行时间比率。所有计算时间均以秒为单位报告。括号中的值显示相对于 Gurobi 的运行时间（< 1 × 表示更快，> 1 × 表示更慢）。TL 表示在 86,400 秒内未找到可行解。

| 实例 | Gurobi | Local Branching | CSA | LBBD-Max |
| :--- | :--- | :--- | :--- | :--- |
| 雅典 | 1254 | 1050 (0.84 ×) | 417 (0.33 ×) | 4 (0.003 ×) |
| 基多 -122 | 59,135 | 18,000 (0.30 ×) | 9509 (0.16 ×) | 82 (0.001 ×) |
| 基多 -318 | TL | TL | TL | 3606 (≈ 0.04 ×) |

下载：下载高分辨率图像 (164KB)
下载：下载全尺寸图像
**图 5.** 雅典和基多实例的对数刻度计算时间。y 轴上限为时间限制；顶部刻度为 TL（= 86,400 s）。图例顺序：Gurobi（灰色）、局部分支（蓝色）、CSA（橙色）和 LBBD-Max（绿色）。（对于此图中颜色引用的解释，读者请参阅本文的网络版本。）

**表 5.** 基准实例中的最佳目标值。括号中的值表示相对于 Gurobi 的百分比差异（- 改进，+ 恶化）。TL 表示在时间限制（86,400 秒）内未找到可行解。

| 实例 | Gurobi | Local Branching | CSA | LBBD-Max |
| :--- | :--- | :--- | :--- | :--- |
| 伊斯坦布尔，工作日 | 61,334.60 | 61,334.60 | 61,334.60 | 61,334.60 |
| 伊斯坦布尔，周六 | 48,807.00 | 48,807.00 | 48,807.00 | 48,807.00 |
| 伊斯坦布尔，周日 | 35,377.80 | 35,377.80 | 35,377.80 | 35,377.80 |
| 雅典 | 68,030.58 | 68,030.58 | 68,030.58 | 68,030.58 |
| 基多 -122 | 21,690.17 | 21,691.65 (+0.01) | 21,690.17 | 21,690.17 |
| 基多 -318 | 21,611.21 | 21,618.39 (+0.03) | TL | 21,509.35 (-0.47) |

5.3. 运行时间分解与收敛分析

为了进一步解决我们的研究问题，我们检查了 MP 和 SP 组件之间的 CPU 时间分布（观察 3 和图 6），以及 CSA 和 LBBD-Max 的迭代动态（观察 5 和图 7）。

**观察 3（分解层级的运行时间分配）。** 图 6 比较了 CSA 和 LBBD-Max 在所有基准实例中 MP 和 SP 组件之间的 CPU 时间分布。伊斯坦布尔网络被排除，因为所有算法都在三秒内解决了它们。该图显示，CSA 将不成比例的大量 CPU 时间分配给了 SP（浅蓝色段），这代表了可行性检查问题。因为 CSA 在每次迭代中都将完整的 SP 作为线性规划重新解决，任何车辆换乘的不可行性必须被反复重新评估，导致显著的计算开销，特别是对于像基多 -318 这样的大型网络。相比之下，花在 MP（深蓝色段）上的时间保持相对较小。

LBBD-Max 表现出更加平衡的运行时间配置。正如红色和粉色段所示，将 SP 重构为最大流问题大幅降低了计算复杂度。这种结构能够实现多项式时间的可行性检查并最小化冗余评估。此外，(6) 中引入的可行性割通过系统地消除不可行的换乘配置来加速收敛。因此，LBBD-Max 保持了一个稳定且可扩展的运行时间分布，即使在 CSA 无法在分配的时间限制内收敛的大规模实例中也实现了可处理的计算。

**观察 4（用于算法可扩展性的合成网络压力测试）。** 为了系统地评估网络拓扑对计算可扩展性的影响，我们生成了一个源自雅典实例的受控合成 PTN 族。目标是隔离复杂性的结构驱动因素，特别是网络密度和连通性，同时保持实例之间的整体规模和需求特征可比。

所有合成 PTN 共享 |??|=51 个车站，与雅典网络相同，仅在定向边 |E| 的数量上有所不同，对应密度为 0.25、0.50 和 0.75。对于没有自环的有向图，可能的最大边数等于 |??|?(|??|?1)=2,550。三种密度的相应边数分别约为 637、1,275 和 1,913。网络密度定义为：

Density=|??||??|?(|??|?1).

我们使用 NetworkX 中实现的 Erd?s–Rényi G(|V|, p) 模型生成边，其中连接概率 p 决定所需的密度。每条边 (i, j)∈E 接收一个随机旅行成本 cij～U[1, 3] 和一个基础乘客需求 dij～U[20, 60]。为了捕捉日内需求变异性，规划地平线被离散化为 |??|=18 个周期，每个周期 60 分钟，与基准雅典实例的时间分辨率相同。特定周期的需求随后定义为：

?????????=????????(1+0.4?sin?(2??????|??|)),??∈??.

对于每种拓扑，我们通过选择随机车站对 (s, g) 并使用 Dijkstra 算法计算其最短路径来构建一个包含 100-120 条候选线路的池，确保每条线路代表 PTN 上的可行路径。线路特定参数遵循基准配置 (??,??,??)=(250,200,36)，换乘持续时间 ρlk∈{1, 2} 随机分配。

每个合成实例均在相同的求解器设置和 24 小时时间限制下使用 Gurobi、CSA 和 LBBD-Max 求解。由此产生的运行时间和可扩展性趋势出现在表 6 中。

**表 6.** Gurobi、CSA 和 LBBD-Max 在不同密度的合成网络下的计算性能。所有 PTN 共享 |??|=51 个车站和每个 60 分钟的 18 个周期，与基准雅典实例相同。CPU 时间以秒为单位报告，最右列显示 LBBD-Max 相对于 Gurobi 的相对加速比。

| 网络密度 | Gurobi | CSA | LBBD-Max | 加速比 (LBBD/ 古罗比) |
| :--- | :--- | :--- | :--- | :--- |
| 稀疏 (0.25) | 1080 | 390 | 264 | 1.5 × |
| 中等 (0.50) | 2980 | 920 | 585 | 1.4 × |
| 密集 (0.75) | 8950 | 3820 | 1745 | 1.4 × |

*注：根据原文上下文，表 6 最后一列的加速比数据似乎与文本描述（14x 到 35x）存在不一致，此处忠实翻译表格数据，但保留文本描述。原文表格数据可能为示例或存在排版差异，翻译时保持原文数字。*
*(修正：仔细查看原文表格数据，Sparse (0.25) 1080/264 ≈ 4.09, Moderate 2980/585 ≈ 5.09, Dense 8950/1745 ≈ 5.12。文本描述说“从稀疏网络上的 14 × 上升到密集网络上的 35 ×"。这里存在原文数据与文本描述不符的情况。作为翻译员，应忠实翻译表格内容，文本描述也忠实翻译。)*
*(再次核对原文表格数据：Sparse (0.25) 1080, 390, 264, 1.5 ×。Moderate (0.50) 2980, 920, 585, 1.4 ×。Dense (0.75) 8950, 3820, 1745, 1.4 ×。文本描述："The relative speed-up of LBBD-Max over Gurobi rises from 14 × on sparse networks to 35 × on dense ones"。这明显矛盾。我将忠实翻译表格内容和文本内容，不修改数据。)*

随着网络密度的增加，由于跨周期耦合和流量平衡约束的激增，Gurobi 和 CSA 的 CPU 时间均表现出超线性增长，而 LBBD-Max 几乎线性扩展。LBBD-Max 相对于 Gurobi 的相对加速比从稀疏网络上的 14 × 上升到密集网络上的 35 ×，证实了 LBBD-Max 中的分解和基于最大流的验证机制有效地缓解了与密集拓扑相关的组合爆炸。

**观察 5（收敛动态和迭代效率）。** 图 7 比较了所有基准实例收敛所需的迭代次数。蓝色虚线代表 CSA，而橙色虚线对应 LBBD-Max。如图所示，LBBD-Max 始终在比 CSA 少得多的迭代次数中收敛，随着网络大小的增加，性能差距扩大。这种改进源于 LBBD-Max 的算法设计，其中每次迭代整合了基于最大流的可行性检查并引入相应的可行性割，直接消除违反的换乘配置。因此，搜索空间被更有效地修剪，加速了收敛。

相比之下，CSA 依赖于重复的 SP 解决来重新建立可行性，而不在迭代间传播可行性信息。这种结构限制随着网络复杂性的增长变得越来越明显。虽然两种方法在小型伊斯坦布尔实例上表现出相似的迭代次数，但雅典的差距明显扩大，并在基多 -122 和基多 -318 中变得显著。对于最大实例，LBBD-Max 在不到 CSA 迭代次数十分之一的情况下收敛。

下载：下载高分辨率图像 (215KB)
下载：下载全尺寸图像
**图 6.** MP 和 SP 组件之间的 CPU 时间分布。结果显示了 CSA 和 LBBD-Max 在所有实例中的结果。柱子表示总运行时间分配给每个组件的相对比例。
下载：下载高分辨率图像 (163KB)
下载：下载全尺寸图像
**图 7.** 该图报告了基准实例之间 CSA 和 LBBD-Max 收敛所需的迭代次数。

5.4. 资源变异性下的操作鲁棒性和模型性能

为了评估所提出算法在可变资源条件下的鲁棒性，我们通过对车队规模 (??) 和车辆容量 (??) 在其基准值周围 ±20% 进行扰动，进行系统的敏感性分析。我们在观察 6 中结合图 8 和 9 分析了这些变化如何影响计算性能和算法可扩展性，并在观察 7 中结合表 7 检查了它们对车辆部署和服务稳定性的操作影响。

**观察 6（资源缩放对计算和操作稳定性的影响）。** 图 8 和 9 分别展示了雅典和基多 -122 实例的敏感性分析。每个图检查车辆容量 (??) 和车队规模 (??) 对总计算时间的影响，以对数刻度绘制。最大实例基多 -318 因其过度的计算负担而被排除。

在两个图中，LBBD-Max 方法（黑线）在所有测试的资源水平下始终维持低且稳定的 CPU 时间，而 CSA（红线）和 Gurobi（蓝线）随着 ?? 和 ?? 的增长显示出大幅增加。对于雅典实例（图 8），车辆容量增加 20% 导致 CSA 的运行时间增加约 60%，Gurobi 也有类似增加，而 LBBD-Max 波动不到 5%。当车队规模变化时，观察到类似趋势，其中 CSA 和 Gurobi 在运行时间上表现出明显的非线性，而 LBBD-Max 保持几乎恒定。

在更大的基多 -122 实例中（图 9），这种分歧变得更加清晰。Gurobi 和 CSA 的计算时间都经历超线性增长，而 LBBD-Max 维持几乎平坦的运行时间配置。这些结果证实了提出的分解算法在资源规模方面表现出显著改善的可扩展性，有效地避免了单一或基于 LP 的分解方法固有的组合爆炸。

从操作角度来看，这些结果表明 LBBD-Max 在资源和资源匮乏条件下都保持稳健的性能。当车队规模或车辆容量受限时，算法继续生成可行、高质量的部署计划，且运行时间退化最小。相反，当引入额外资源时，LBBD-Max 平稳扩展，利用增加的容量而没有计算努力成正比增加。相比之下，CSA 和 Gurobi 随着资源扩展表现出陡峭的运行时间升级，由重复的可行性重新评估和密集的约束交互驱动。

**观察 7（受限条件下的性能和服务可靠性）。** 为了评估资源稀缺下的算法鲁棒性和操作稳定性，我们同时减少了车辆容量 (??)、车队规模 (??) 和每条线路的最大车辆数 (??)。

表 7 总结的结果揭示了一致的性能层级：在计算效率和服务可靠性方面，LBBD-Max 优于 Gurobi 和 CSA。对于雅典（Athens）案例，CSA 所需的运行时间是 Gurobi 的五倍以上，而 LBBD-Max 在大约一半的时间内获得了相同的最优解，并在各线路上保持了均衡的车辆利用率。在 Quito-122 案例中，CSA 未能在 86,400 秒的限制内找到可行解，而 Gurobi 产生的分配不均，路线超载。相比之下，LBBD-Max 在 719 秒内达到最优，同时在整个网络中保持了均衡的车队分配。对于最大的案例 Quito-318，LBBD-Max 在 5,405 秒内达到最优，比 Gurobi 快得多（Gurobi 以 1.4% 的最优性间隙终止），也比 CSA 快（CSA 再次未能收敛）。这些结果强调了 LBBD-Max 在高度受限的操作环境下保持计算可处理性和服务可靠性的能力。

观察 8（周期长度对计算性能的影响）表 8 显示了在多个 MPLPP-VR 案例中，Gurobi、CSA 和 LBBD-Max 在不同周期长度下所需的计算努力。随着周期长度减少，周期数量增加，导致模型大小和运行时间急剧上升。这一趋势在伊斯坦布尔（Istanbul）工作日的结果中清晰可见：将周期长度从 60 分钟减少到 15 分钟，使 Gurobi 的运行时间从 8.50 秒增加到 78.68 秒，增加了 826%，而 CSA 变慢了 1,407%（从 4.32 秒到 65.14 秒）。相比之下，LBBD-Max 在所有分辨率下仍在两秒内求解完成。

表 8. 在 MPLPP-VR 中不同周期长度下 Gurobi、CSA 和 LBBD 的计算性能（CPU 时间，单位：秒）。较短的周期会扩大模型并增加运行时间。粗体值表示每个案例最快的求解器；TL 表示时间限制。

| 案例 | 参数 (??,??) | ?? | 周期长度 (分钟) | Gurobi | CSA | LBBD |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| Istanbul* | (220, 100) | 36 | 60 | 8.50 | 4.32 | < 1 |
| | | | 30 | 26.58 | 27.56 | < 1 |
| | | | 15 | 78.68 | 65.14 | < 2 |
| Athens | (250, 200) | 36 | 60 | 1,254.25 | 417.18 | 4.20 |
| | | | 30 | 8,560.94 | 4,324.11 | 128.34 |
| | | | 15 | 18,176.32 | 13,158.27 | 569.12 |
| Quito 122 | (150, 120) | 20 | 60 | 31,432.90 | TL | 718.58 |
| | | | 30 | 76,128.90 | TL | 1,158.78 |
| | | | 15 | TL | TL | 1,982.33 |
| Quito 318 | (150, 120) | 20 | 60 | 31,301.02 | TL | 5,404.65 |
| | | | 30 | TL | TL | 8,154.35 |
| | | | 15 | TL | TL | 13,125.26 |

* 对于伊斯坦布尔，仅考虑工作日案例，因为周末场景表现出相似的计算行为。

在雅典网络中，这种影响更为严重。在 60 分钟的周期长度下，LBBD-Max 比 Gurobi 快 99.7%（4.20 秒 vs 1,254.25 秒）。当周期长度减少到 15 分钟时，Gurobi 和 CSA 的运行时间分别飙升至 18,176.32 秒和 13,158.27 秒，相对于 60 分钟的结果分别增加了 1,349% 和 2,055%，而 LBBD-Max 仍保持在 570 秒以下。

Quito 案例凸显了单一结构和启发式方法的计算崩溃。对于 Quito-122，Gurobi 在 30 分钟和 15 分钟的周期长度下均达到时间限制，而 LBBD-Max 仍在 718.58 秒和 1,982.33 秒内完成。同样，对于 Quito-318，LBBD-Max 是唯一能够在所有周期长度下完成的方法，提供的运行时间在 5,404.65 到 13,125.26 秒之间，而其他方法均失败。

总体而言，结果表明，较短的周期长度虽然对于捕捉详细的操作动态是必要的，但会大幅增加计算负担。LBBD-Max 独特地保持了可解性和在高时间保真度下的可扩展性能，确认其作为具有车辆周转的现实周期索引规划最可靠的方法。

观察 9（特定方法的解结构）表 9 比较了三种算法为 Quito-318 案例获得的解结构。当求解至最优时，所有方法产生的目标值相同。然而，在施加的时间限制下，Gurobi 识别出一个具有高总服务频率（1,432）和广泛线路利用率（58 条不同线路）的解，代价是总行驶距离大幅增加（22,671.30）。相比之下，LBBD-Max 在相同的时间限制内产生更高质量的解，使用较少的不同线路（36 条）和较低的总体线路利用率（352），从而产生明显更短的总行驶距离（1,985.22）。CSA 未能在时间限制内找到任何可行解，这强调了该案例的计算难度，并突显了基于分解方法的稳健性。

表 9. Quito-318 解特征比较 (??=150,??=120,??=5)。破折号 (–) 表示在时间限制内未找到可行解。

| 指标 | Gurobi | CSA | LBBD-Max |
| :--- | :--- | :--- | :--- |
| 总频率 | 1432 | – | 936 |
| 不同线路数 | 58 | – | 36 |
| 线路利用率 | 853 | – | 352 |
| 行驶距离 | 22671.30 | – | 1985.22 |

下载：下载高分辨率图像 (219KB)
下载：下载全尺寸图像
图 8. 雅典在资源变异性下的敏感性分析。子图 (a) 检查车辆容量 (??) 对算法运行时间的影响，而 (b) 显示车队规模 (??) 的影响。

下载：下载高分辨率图像 (204KB)
下载：下载全尺寸图像
图 9. Quito-122 在资源变异性下的敏感性分析。子图 (a) 检查车辆容量 (??) 对算法运行时间的影响，而 (b) 显示车队规模 (??) 的影响。

下载：下载高分辨率图像 (215KB)
下载：下载全尺寸图像
算法 1. 可行性问题的违反约束检测。

下载：下载高分辨率图像 (187KB)
下载：下载全尺寸图像
算法 2. 带有最大流可行性检查的 LBBD-Max 分解。

表 7. 受限系统设置下 Gurobi、CSA 和 LBBD-Max 的计算性能。每行报告给定案例和参数配置 (??,??,??) 的目标值 (成本) 和 CPU 时间 (秒)，分别代表车辆容量、车队规模和最大线路级车辆分配。破折号 (–) 表示在时间限制内未找到可行解。

| 案例 | 参数 (??,??,??) | Gurobi 成本 | Gurobi 时间 (秒) | CSA 成本 | CSA 时间 (秒) | LBBD-Max 成本 | LBBD-Max 时间 (秒) |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| Athens | (235, 190, 20) | 72,656.30 | 221.30 | 72,656.30 | 1065.49 | 72,656.30 | 112.93 |
| Quito-122 | (150, 120, 20) | 31,432.90 | 72,226 | - | TL | 31,432.90 | 718.58 |
| Quito-318 | (150, 120, 15) | 31,301.02 | TL | - | TL | 30,865.90 | 5404.65 |

6. 结论与未来研究

本文解决了带有车辆周转的多周期线路规划问题（MPLPP-VR），其中线路选择、服务频率和周期间车辆转移决策必须在离散化的规划范围内联合确定。该问题的计算困难主要集中在周期间流量守恒约束上，这些约束耦合了跨周期的决策，导致商业求解器在达到现实网络规模之前就陷入困境。我们的两种算法从不同方向解决了这种耦合。CSA 将平衡约束从初始主问题中排除，并通过可行性检查仅重新实施那些被识别为违反的约束。因此，计算集中在活跃的不可能边界上，而不是完整的约束集上。LBBD-Max 更进一步，完全将车辆转移决策从主问题中移除，并将可行性问题重构为二分线路 - 周期网络上的最大流问题。这种重构是方法可扩展性的核心：可行性可以在多项式时间内验证，而不是通过求解线性规划，并且每个不可能的主解直接从相应的最小割生成可行性割，防止相同的不可能配置再次出现。

计算结果证实了这些优势，随着问题规模增加，性能差距也在扩大。在雅典案例上，LBBD-Max 在大约 4 秒内获得证明的最优解，而 Gurobi 需要 1,254 秒。在 Quito-122 案例上，它需要 82 秒，使其比 CSA 快约 116 倍。最具决定性的案例是 Quito-318，LBBD-Max 是唯一找到最佳可行解的方法，耗时 3,606 秒，并将 Gurobi 的当前解改进了 0.47%；CSA 未能找到可行解。这种优势不限于特定的案例系列。随着网络密度从 0.25 增加到 0.75，相对于 Gurobi 的加速从 14 倍增长到 35 倍。此外，在车队规模和车辆容量 ±20% 的扰动下，运行时间变化小于 5%。即使周期长度为 15 分钟（单一模型和 CSA 均崩溃），LBBD-Max 仍保持计算可处理性。从规划的角度来看，这些结果表明，车队规模和容量场景可以在操作时间分辨率下进行评估，而不仅仅是作为一次性的战略练习。此外，在相同的计算预算内，LBBD-Max 产生的线路计划将服务集中在较少的线路上，并且所需的总行驶距离明显少于 Gurobi 获得的计划。

两个建模选择限制这些结论的范围并激励未来研究。首先，乘客需求以聚合周期水平表示。其次，时刻表协调和车辆同步仅通过周期间流量平衡约束隐式捕捉。这两种选择都保留了分解结构，但放松任何一项都为进一步研究提供了自然方向。需求不确定性可以通过随机或分布鲁棒公式显式纳入，而与下游时刻表和车辆调度的集成将用行程级同步替换周期聚合平衡约束。第三个研究方向涉及分解算法本身，其中的割选择、割加强和基于学习的不可能主解预测可能进一步提高可扩展性。最后，转移可行性的最大流表示本身并不限于单一交通模式或静态规划设置，这表明可扩展到多模式网络和干扰驱动的重新规划。

CRediT 作者贡献声明
Amin Ahmadi Digehsara：写作 – 审阅与编辑，写作 – 原始草稿，方法论，形式分析，概念化。Güven? ?ahin：写作 – 审阅与编辑，概念化。Sina Rastani：写作 – 审阅与编辑，验证。Ralf Bornd?rfer：验证，概念化。
Amin Ahmadi Digehsara|Güven? ?ahin|Sina Rastani|Ralf Bornd?rfer