IEEE Transactions on Robotics

Optimal On-the-Fly Route Planning With Rich Transportation Requests

作者：Cristian-Ioan Vasile, Jana Tumova, Sertac Karaman, Calin Belta, Daniela Rus · 机构：Lehigh University, Bethlehem, PA, USA; KTH Royal Institute of Technology,Stockholm, Stockholm, Sweden; Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, USA; University of Maryland, College Park, MD, USA; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA

会议/期刊：IEEE Transactions on Robotics · 发布日期：2025 · 页码：4041-4056

路径规划优化

精读笔记

Problem Setting

论文标题：Optimal On-the-Fly Route Planning With Rich Transportation Requests（IEEE Transactions on Robotics / 2025）。

这篇论文处理的是一个比动态车辆路径规划更“语义化”的在线路由问题：单车在道路网络中持续接收请求，每个请求包含 pickup location、scLTL 任务公式、deadline、容量需求和 priority；请求到达时未知未来，planner 只能在当前历史之后找最优 continuation。这里的关键不是“找一条路”，而是同时决定：何时接哪些请求、哪些请求可共享车、当前已接请求的逻辑任务进度如何推进、deadline 冲突时牺牲谁。

真正困难点有两个。第一，request 不是可拆成独立 waypoint 的普通任务，scLTL 公式可能包含顺序、选择、avoid-until、并行 conjunctive eventualities 等结构，不能简单映射成一组 pickup/dropoff pair。第二，deadline 可能不可同时满足，因此可行性不是二元的；系统需要一个 violation semantics 来定义“最优失败”。这也是传统 DVRP / dial-a-ride 和常规 TL synthesis 都容易卡住的地方：前者任务表达力不足，后者往往假设规格可满足或只做单个全局规格的最小修改。

Motivation

已有路线缺的是“复杂任务语义”和“不可满足时的优化决策”同时在线处理。动态 VRP 文献通常把请求当成 A-to-B 或带时间窗的运输对象，容量和动态到达可以处理，但对请求内部依赖结构无能为力；TL-based planning 能自然表达 rich task，但很多工作关心 correct-by-design satisfaction，即规格要么可满足，要么做公式修复，很少把 deadline delay、priority 和在线到达作为一等对象。

作者的核心观察是：rich transportation request 的任务结构可以交给 scLTL 自动机处理，而 deadline violation 不必硬编码进时序逻辑；把 deadline 和 priority 留给路径 cost，就可以在任务语义保持严格的同时处理 infeasible deadlines。这个建模切分很重要：逻辑层只回答“任务何时完成”，优化层回答“晚了多少、谁更重要、该怎么权衡”。

Core Idea

本文真正的核心不是 MILP 本身，而是把在线 rich request routing 重新组织成“当前活跃请求集合上的 least-violating accepting-run search”。每次重规划时，只看已经到达且未完成的 active demands，把道路 WTS 与这些请求的 scLTL 自动机做 product；product state 同时携带车辆位置、每个请求自动机状态、当前车上/进行中的请求集合。这样，一条 accepting run 就对应一段后缀路线：所有 active demands 都最终完成，容量从图结构上被保证，pickup/dropoff 决策也从路径中恢复。

本质区别在于它没有把 complex request 预处理成一串 waypoint 或 pairwise precedence constraint，而是直接保留为 automaton progress state；也没有把 deadline 作为 hard feasibility constraint，而是转成 delay vector 上的优化目标。这引入了一个很强的 inductive bias：任务结构由自动机离散状态精确记忆，优化只在这些状态之间做最短路式选择。因此它比普通 VRP 更 general，又比任意 TL planning 更贴近运输调度中的 priority/deadline tradeoff。

Method

关键机制可以压缩成几件事。

第一，active-set receding-horizon formulation。系统不尝试规划无限请求序列，而是在每个决策时刻对 active demands 求最优 continuation。它解决的是 online arrival 下未来未知的问题；代价是最优性只相对于相同历史和当前已知请求，不是全局 clairvoyant optimum。

第二，product automaton 加 pickup/capacity 状态。普通 WTS × automata product 只能跟踪公式进度；本文额外加入当前 in-progress demand set，使得“请求从 pickup 后才开始评价公式”和“容量不超限”都变成图可达性约束。这是比早期 conference version 更实用的改动，也是把 car sharing 纳入 TL planning 的关键。

第三，向量权重编码 service duration。product transition 的权重不是单个 travel time，而是对每个 active demand 的累计服务时间贡献：未完成的请求继续累积，已完成的请求权重为 0。这样最终 accepting path 的权重和就直接给出每个请求的 duration，再减 deadline 得 delay。

第四，cost functions 定义不同 violation policy。highest-priority-first 强制优先级词典序式支配；bottleneck-delay 关注最大加权延迟；cumulative-delay 关注整体效率。它们不是小改动，而是对应不同调度伦理：特权、平等、效率。

第五，MILP / graph search 求最优 accepting path。一般 cost 被写成 delay 与 violation indicator 的 max-of-linear form，用 MILP 选 source-to-sink path；若 cost 满足 translation monotonicity，则可用 Dijkstra-like graph search。后者的核心是路径前缀优劣在追加相同未来代价后不反转，因此 greedy label-setting 成立。

Key Insight / Why It Works

最重要的 insight 是：把“请求是否完成”与“完成得好不好”解耦。scLTL 自动机保证任务语义，product accepting state 保证所有 active demands 都完成；delay/priority cost 只评价到达 accepting state 的路径质量。这避免了把 deadline relaxation 直接揉进逻辑公式导致的复杂 timed-logic synthesis，也避免了在 VRP 里手工展开复杂 temporal dependencies。

方法有效的根源不是 MILP 魔法，而是 product automaton 给出了一个完备但有限的 latent state space：每个状态完整表示车辆位置、每个任务进度和车内容量占用。因此在这个状态空间上，寻找最优 route 就退化成一个带复杂路径 cost 的图搜索问题。换言之，planning 能力来自显式状态展开，而不是启发式搜索学习到的隐式策略。

最实质的贡献是 product construction 与 violation cost 的接口设计：向量权重让一个 product path 同时携带所有请求的 service duration，这使得多种 delay policy 可以共享同一自动机结构。MILP 是通用解法，但更像把已构造好的图优化问题交给 solver；工程上重要，但理论新意相对有限。

linear-time graph search 部分的价值在于给出一个清晰边界：只有 translation-monotone cost 才能享受 label-setting 式最优性。这个结果也揭示了为什么 bottleneck 和 hard highest-priority 不适合简单 Dijkstra：它们的相对排序可能因未来共同平移而翻转。这里的 theorem 有概念价值，但 practical scope 偏窄；cumulative delay 和 modified priority-weighted delay 才自然满足。

需要直接判断的是：scalability 增益主要来自 road-network abstraction 和 active demands 较少，而不是突破了 automata product 的指数瓶颈。论文中 solver 表现不错，可能主要因为实例结构接近 shortest path/network flow，且请求数不大。若 active demands 上升、公式自动机变大、capacity 产生更多组合，product size 仍会迅速爆炸。

Relation To Prior Work

它最接近三条线的交叉：dynamic VRP / dial-a-ride with time windows，TL-based robotic planning，least-violating planning for unsatisfiable specs。与 DVRP 相比，新增信息是请求内部由 scLTL automata 表示，而不是简单 transport pair；与 TL planning 相比，新增信息是在线到达、pickup 后语义生效、容量共享，以及 deadline violation cost；与 least-violating TL 相比，它不是最大满足子公式或修公式，而是保持每个任务最终完成，只优化完成时间相对 deadline 的违反程度。

看似新的部分里，automata product、MILP shortest-path encoding、big-M indicator、Dijkstra-like search 都不是新思想；它们是已有 formal methods 和 network optimization 的重组。真正实质创新在问题组合方式和状态/权重设计：把 rich transportation request 的进度、pickup/capacity 决策、delay vector 放进同一个 product graph，使得在线重规划有可证明的局部最优性。

它属于“formal methods for robotics 向 operations research routing problem 渗透”的技术谱系，而不是传统 VRP 的大规模启发式路线。它牺牲了大规模 fleet-level scalability，换来请求语义的严格表达和可证明 optimality。

Dataset / Evaluation

评估覆盖了一个真实路网 case study：mid-Manhattan 子图，travel duration 来自真实 taxi 数据并按小时变化；这支持其 road-network deployment plausibility。请求本身则是随机生成的 scLTL templates，包含顺序、选择、avoid-until 等结构，能测试表达力，但不代表真实用户请求分布。没有真车实验，也没有真实在线需求流。

实验基本验证了两个层面的 claim：一是框架能在中等规模道路网络上跑通；二是三种 cost function 的调度行为确实不同。cumulative delay 更平衡且可用 graph search，因此 runtime/cost tradeoff 最好；bottleneck 更公平但求解更贵；highest-priority-first 会强制优先级但可能导致低优先级长时间等待或 mask 已不可按时完成的请求。

但 evaluation 对核心 scalability claim 的支持是有限的。路网规模影响被 abstraction 消掉，因此实验主要说明“当重要地点数量小、active demand 数量小”时可扩展；真正难的是 active demand 增长，论文也显示这是主要驱动。没有和强 DVRP/TW 启发式、CP-SAT、large neighborhood search 或专门 dial-a-ride solver 做系统比较，因此不能说明它在传统 routing performance 上更强，只能说明它能处理更丰富语义。

Limitation

第一，指数上限没有消失。product automaton size 随 active demands 的自动机状态数乘积增长，还叠加 pickup/in-progress set 的容量组合。论文通过 active-set、road abstraction 和 solver 结构吃掉了实际规模，但理论瓶颈仍是核心限制。

第二，最优性是局部在线最优。每次重规划只对已知 active demands 和固定历史最优；未来到达未知，因此不能保证长期全局最优。若请求到达频繁，当前为了完成 active set 的决策可能对未来很差。文中未充分说明是否存在策略性等待或预测机制。

第三，时间模型偏理想。transition weight 可 time-dependent，但重规划只能在状态处发生，边上不可抢占；节点服务时间、乘客上下车时间、停车等待、取消请求、no-show、随机 travel time 都没有进入核心模型。真实 deployment 中这些因素会显著改变 deadline violation。

第四，highest-priority-first cost 有数值和行为风险。用 big-M 与 |D|^p 做严格优先级支配，理论上清楚，但实际可能数值不稳定；并且一旦某高优先级或低优先级请求已经不可按时完成，它在 cost 中可能变成某种 masked/constant-like 项，诱导非直觉等待。作者在实验讨论中观察到这一点，但没有给出机制修正。

第五，road abstraction 的最优性边界需要更谨慎。对静态最短路替换中间无关节点通常合理；但在 time-dependent travel times、avoid-until constraints、或经过某些标签会影响公式时，抽象是否保持语义和代价最优并不总是显然。文中说明较少。

第六，multi-vehicle 不是自然扩展。单车 product 已经指数增长；多车会引入 assignment、coupled capacity、collision/congestion 和共享请求分配，组合复杂度会更高。把本文方法直接扩展到 fleet 级别大概率需要完全不同的 decomposition / auction / column generation 机制。

Takeaway

  • 1. 最值得迁移的思想是“逻辑语义与 violation optimization 分层”：让 automata 只管任务完成语义，让 cost 管 deadline/priority tradeoff。
  • 这比把所有时间约束塞进逻辑更干净。
  • 2. 对 rich request routing，显式维护每个请求的 automaton progress 是强 inductive bias；它牺牲规模，但换来语义正确性和可解释调度。
  • 3. cost function 不是附属选择，而是在定义系统行为伦理。

一句话总结

这篇论文把动态车辆路由、scLTL 任务规划和 least-violating optimization 组合成一个在线 product-automaton 路径搜索框架，真正贡献在于 rich request 语义与 deadline/priority violation 的统一建模，而不是 MILP 求解本身。