⚡ electrical engineering

Where Should Robotaxis Operate? Strategic Network Design for Autonomous Mobility-on-Demand

本文提出了自动驾驶按需出行网络设计问题（AMoD-NDP）的数学模型与基于列生成的可扩展求解算法，利用纽约曼哈顿真实数据验证了该方法在联合优化运营子网络与车队规模、量化基础设施投资与车队效率权衡以及支持战略规划方面的有效性。

原作者： Xinling Li, Gioele Zardini

发布于 2026-02-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Xinling Li, Gioele Zardini

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章主要探讨了一个非常有趣且实际的问题：如果未来城市里全是无人驾驶出租车（Robotaxi），它们应该在哪里跑？又该派多少辆车？

想象一下，你是一家无人驾驶出租车公司的 CEO，手里有一笔钱（用来改造道路设施）和一群车（车队）。你的目标是用最少的钱和车，接最多的乘客，同时保证乘客安全、快速到达。

这篇文章就是教你怎么制定这个“战略地图”。

1. 核心难题：不是所有路都适合跑“机器人”

以前的出租车（比如 Uber）是司机自己开车，他们想走哪条路就走哪条路，系统很难控制。但无人驾驶出租车不一样，它们是由一个中央大脑统一指挥的。

这就带来了一个新挑战：

基础设施限制：现在的马路并不是所有地方都适合无人驾驶。有些路太窄、信号太乱，或者没有安装必要的传感器。
决策困境：公司不能把车派到所有路上去，因为那样成本太高且不安全。公司必须决定：“到底哪几条路值得花钱去改造（比如装传感器、画专用道），让车只在这些路上跑？”

这就好比你要在一张巨大的城市地图上，用有限的“油漆”（预算）画出几条**“黄金赛道”**。车只能在这些赛道上跑，其他路虽然存在，但车不能去。

2. 这篇文章做了什么？（三个关键步骤）

作者提出了一套数学方法，帮 CEO 做这个决定。我们可以把它想象成玩一个**“超级城市规划游戏”**：

第一步：画地图（网络设计）

公司不能盲目地给所有路都装上传感器。算法会计算：

如果只开通这条路，能接到多少乘客？
如果开通那条路，需要花多少钱？
关键点：它不是单独看某条路，而是看**“路 + 车”的组合**。就像你开餐厅，不能只决定“开在哪”，还得决定“请多少厨师”。路修好了，车不够也是白搭；车多了，路没修好也跑不起来。

第二步：找最优路线（路径规划）

一旦确定了哪些路能跑，算法就要帮乘客规划路线。

不仅仅是“最近”：以前导航只找“距离最短”的路。但无人驾驶要考虑**“风险”**。比如，有些路虽然近，但需要频繁左转（容易撞车），算法就会自动避开。
比喻：就像你送外卖，如果为了省 5 分钟要穿过一个全是红绿灯和乱窜行人的复杂路口，你宁愿多走 2 分钟走大路。这篇文章的算法就是帮车队做这种“安全与效率”的权衡。

第三步：应对“意外”（鲁棒性）

现实世界是变化的。今天早高峰堵车，明天可能下暴雨，或者突然有人取消订单。

作者设计的方法很**“皮实”**（鲁棒）。它假设未来可能会有波动，所以设计出来的“黄金赛道”即使在需求忽高忽低的情况下，依然能保持高效，不会轻易崩溃。
比喻：就像你设计一个防洪堤，不仅要防平时的水位，还要考虑万一发大水，堤坝会不会塌。

3. 他们是怎么算出来的？（聪明的算法）

城市里的路成千上万条，可能的路线组合比宇宙中的星星还多。如果让电脑把所有路都试一遍，算到宇宙毁灭也算不完。

作者发明了一种**“列生成”（Column Generation）**的聪明算法：

比喻：想象你要找去北京的最快路线。
- 笨办法：把地球上所有可能的路都列出来，一个个试。
- 聪明办法：先只试几条看起来不错的路。算完发现，好像还有条路能更快？好，把这条新路线加进来再算。如果加进来的路都不能让结果更好了，那就停止。
这种方法让电脑不需要处理所有路，只需要处理**“真正有用”**的那几条，速度极快，连纽约曼哈顿这么大的城市都能算得出来。

4. 他们在纽约曼哈顿做了什么实验？

作者用了纽约曼哈顿的真实数据（出租车行程、地图）来测试这套方法。结果发现：

路不用全修：不需要把整个曼哈顿都变成无人驾驶专用路。只需要覆盖**20%-30%**的关键主干道，就能满足大部分需求。这就像给城市血管做“搭桥手术”，只通关键血管，而不是把全身血管都换一遍。
路很稳定：虽然每天乘客上下车的地方不一样，但算出来的“黄金赛道”几乎每天都是一样的。这意味着公司可以制定长期的基础设施计划，不用每天重新规划。
钱和车的平衡：
- 如果车太少，修再多路也没用（车不够跑）。
- 如果路没修好，派再多车也跑不起来（路不通）。
- 只有**“路”和“车”一起规划**，才能赚到最多的钱。
安全限制的影响：如果强制要求“禁止左转”（为了安全），虽然车跑得慢了一点，赚的钱少了一点，但事故风险大大降低。这给政府和公司提供了一个**“安全 vs. 利润”**的调节旋钮。

总结

这篇文章的核心思想就是：无人驾驶出租车不仅仅是“车”的问题，更是“路”和“车”怎么配合的问题。

它提供了一套工具，帮助政府和公司像下棋一样，提前算好哪条路值得投资、派多少车、怎么跑最安全又最赚钱。这不再是科幻电影，而是未来城市交通规划的真实蓝图。

1. 研究背景与问题定义 (Problem Definition)

背景：
随着城市化进程加快，交通拥堵和排放问题日益严重。现有的按需出行（MoD，如 Uber/Lyft）主要依赖人类司机，存在空驶率高、调度分散等问题。自动驾驶按需出行（AMoD）通过集中控制车队，有望提高效率和可靠性。然而，现有的 AMoD 研究大多假设车辆可以在固定的道路网络上运行，忽略了自动驾驶车辆（AV）需要特定的基础设施（如高精度地图、传感器覆盖）才能安全运行这一事实。

核心问题：
AMoD-NDP (Autonomous Mobility-on-Demand Network Design Problem)：
运营商需要联合决策以下两个战略问题：

子网络选择：在庞大的基础道路网络中，选择哪些路段进行“仪器化”（instrumented，即配备自动驾驶所需的基础设施）以构建运营子网络。
车队与路径规划：在选定的子网络上，如何分配车队资源并规划乘客路径，以最大化利润（或系统效用）。

约束条件：

基础设施预算：仪器化路段的成本限制。
车队时间预算：受限于车队规模，总车辆运行时间有限。
路径级服务质量（QoS）与风险约束：例如，限制单程旅行时间、限制高风险操作（如左转）等。
流量守恒与容量限制。

2. 方法论 (Methodology)

2.1 数学建模

基础模型：将问题建模为一个混合整数线性规划（MILP）。
路径级公式化 (Path-based Formulation)：
- 传统的链路级（Link-based）模型难以表达路径级的约束（如总左转次数、总旅行时间）。
- 作者提出了基于路径的公式，决策变量包括：是否仪器化某条边（ $x_e$ ）以及每条 OD 对（起终点）在特定路径上的流量（ $f_p$ ）。
- 目标函数：最大化总利润（收入减去运营成本）。
- 优势：能够显式地处理路径级的 QoS 和风险约束。
- 挑战：潜在路径数量呈指数级增长，直接求解不可行。

2.2 列生成算法 (Column Generation, CG)

为了解决路径数量爆炸的问题，作者设计了一种基于列生成的分解算法：

主问题 (Master Problem)：
- 在受限的路径集合上求解线性规划（LP）松弛问题。
- 优化受限集合内的路径流量和边仪器化决策。
定价问题 (Pricing Problem)：
- 目标是寻找具有正“缩减成本”（Reduced Cost）的新路径，以改进主问题目标。
- 该问题被转化为一个带资源约束的最短路径问题 (Elementary Shortest Path with Resource Constraints, SPRC)。
- 资源约束：包括旅行时间上限（ $T(p) \le M_{od}$ ）以及路径级风险约束（如左转次数）。
- 求解器：设计了一种定制的标签修正算法 (Label-Correcting Algorithm)。
  - 预处理：利用 Dijkstra 算法剪枝，移除不可能满足时间预算的节点和边。
  - 支配规则：定义标签的支配关系（成本更低、时间更短、访问节点集更优），剪枝非最优路径。
  - 精确性：保证找到精确的最优路径。
整数解恢复：
- 在 CG 收敛得到最优 LP 解后，将仪器化变量 $x$ 重新强制为整数（0 或 1），在生成的路径集合上求解最终的 MILP。
- 最优性间隙证明：算法提供了明确的整数解最优性间隙（Optimality Gap）证书。

2.3 鲁棒性扩展 (Robust Extension)

考虑了旅行时间和OD 需求的盒式不确定性 (Box Uncertainty)。
旅行时间不确定性：通过将边旅行时间替换为“名义值 + 最大偏差”（ $\bar{T} + \rho$ ），将鲁棒约束转化为确定性约束，保持了定价问题的 SPRC 结构。
需求不确定性：通过将需求上限收紧（ $\bar{\alpha} - \rho$ ）来处理。
结论：鲁棒版本保持了与确定性版本相同的算法结构，仅需调整参数。

3. 主要贡献 (Key Contributions)

问题形式化：首次正式定义了 AMoD-NDP 问题，将基础设施投资决策（网络设计）与车队运营决策（路径规划）在单一层级模型中联合优化，区别于传统的双层道路网络设计（上层设计、下层用户均衡）。
可扩展算法：提出了一种基于路径的混合整数规划公式，并开发了可扩展的列生成算法。该算法利用定制的标签修正求解器处理带资源约束的最短路径问题，能够处理城市级规模的网络。
理论保证：算法不仅提供 LP 松弛的最优解，还通过最终 MILP 求解提供整数解的显式最优性间隙证明。
鲁棒性框架：证明了该框架在旅行时间和需求存在盒式不确定性时，仍能保持分解结构，无需重构算法核心。
实证分析：利用纽约曼哈顿的真实数据（TLC 出租车数据和 OpenStreetMap 路网）进行了大规模验证。

4. 实验结果与发现 (Results & Findings)

基于纽约曼哈顿 2024 年 5 月的真实数据（约 4300 个节点，7000 条边，日均 20 万行程）：

计算效率：算法在 25 分钟内即可求解城市级实例，最终整数解与 LP 松弛的最优性间隙小于 $10^{-6}$ 。
子网络结构：
- 最优运营子网络是稀疏的，仅包含基础路网中约 25%-30% 的边（主要集中在服务需求的核心走廊）。
- 时间稳定性：在 31 天的独立需求模拟中，超过 90% 的选中边在 25 天以上的方案中出现，表明设计对短期需求波动具有高度鲁棒性。
预算敏感性分析：
- 发现了三种运行体制：
  1. 车队受限：基础设施充足但车少，增加基建无效。
  2. 基建受限：车多但路没铺好，增加车队无效。
  3. 容量受限：两者都充足，受限于物理路网容量。
- 结论：必须联合优化车队规模和基础设施投资，单一维度的投入会导致边际收益递减。
风险约束影响（左转限制）：
- 引入限制左转次数的路径级约束作为风险代理。
- 结果：严格的左转限制会显著降低服务覆盖率和利润；随着限制放宽，性能迅速提升并趋于稳定。这为运营商提供了在“安全性”与“盈利能力”之间权衡的量化工具。

5. 意义与价值 (Significance)

对运营商：提供了一个决策支持工具，用于确定在哪些区域部署自动驾驶基础设施（ROI 分析），以及如何根据基础设施水平调整车队规模。
对政策制定者：
- 量化了基础设施投资与系统性能之间的权衡。
- 评估了监管政策（如限制左转、限制车队规模）对 AMoD 服务可行性和利润的影响。
- 证明了在密集的城市网格中，通过精心设计的稀疏子网络即可实现接近最优的服务水平，有助于降低基础设施部署成本。
学术价值：填补了 AMoD 领域从“固定网络上的运营控制”向“联合网络设计与运营控制”的空白，并展示了列生成算法在解决大规模路径级约束交通网络设计问题中的有效性。

总结

该论文提出了一种战略性的 AMoD 网络设计框架，通过联合优化基础设施选择和车队路径规划，解决了自动驾驶出行服务落地中的关键规划问题。其提出的算法不仅具有理论上的最优性保证，且在真实城市数据上展现了极高的可扩展性和实用性，为未来自动驾驶出租车的大规模部署提供了重要的理论依据和工具支持。