Many-to-Many Route Searching

□

做配送计划的时候，真正的优化算法还没开始跑，就先卡在一件更朴素的事情上：距离矩阵。

一辆车一天跑 50 个配送点，就是 $50 \times 50 = 2500$ 个 OD 对。OD 即 Origin–Destination，一个「起点—终点」对。一个营业所几十辆车，一次重排就是几十万个。车辆路径问题（VRP）的求解器会反复查这张表，所以它必须先被完整地算出来。

这件事听上去只是「把最短路算很多遍」，但在算法工程里，它是一个被单独研究了将近二十年的子问题 从第一篇专门针对路网多对多问题的论文（Knopp 等人，ALENEX 2007）算起，到今天约十九年。Knopp 等人在论文里写道，他们没有找到此前针对路网（或其他稀疏图）的专门结果。 。这篇沿着它的发展脉络走一遍：每一步解决了上一步的什么问题，又留下了什么新问题。

问题

+

这一领域的标准综述：Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D. & Werneck, R. F. (2016). “Route Planning in Transportation Networks.” Algorithm Engineering: Selected Results and Surveys, LNCS 9220, 19–80。预印本见 arxiv.org/abs/1504.05140。下文凡是标注「综述 Table 1」的数字，都来自这篇综述第 23 页的 Table 1：PTV 提供的西欧路网（1800 万节点、4250 万条有向弧），以行驶时间为边权，单核 Intel X5680 3.33 GHz，起终点在全图中均匀随机抽取。

给定有向图 $G = (V, A)$，每条弧有非负长度 $\ell(u,v)$；再给定源集合 $S$ 和目标集合 $T$。多对多最短路要求对所有 $s \in S,\ t \in T$ 算出 $\mathrm{dist}(s,t)$，结果是一张 $|S| \times |T|$ 的表。

它夹在两个更常见的问题之间：$|S| = |T| = 1$ 是点对点查询，$S = T = V$ 是全对最短路。路网上我们关心的是中间地带——$|S|$、$|T|$ 从几十到几万，远小于 $|V|$ 的千万量级 $|V|$ 取综述里西欧路网的 1800 万节点。$|S|$、$|T|$ 的范围参考 Knopp 等人的实验：他们手上来自真实 VRP 业务的九个实例，规模在 173 到 2892 个点之间；论文中的随机实例则做到了 $20{,}000 \times 20{,}000$。 。

最朴素的解法是跑 $|S| \cdot |T|$ 次点对点查询。哪怕每次只要 $1\ \text{ms}$，$1000 \times 1000$ 也要十几分钟 $10^6 \times 1\ \text{ms} = 1000\ \text{s} \approx 17$ 分钟。1 ms 是 Knopp 等人在 2007 年给出的 Highway Hierarchies 单次查询时间，他们据此估算 $10{,}000 \times 10{,}000$ 次查询要「大约一天」。 。而且不难看出其中的浪费：$s_i \to t_j$ 和 $s_i \to t_k$ 出了 $s_i$ 所在的城区之后，很可能走同一条高速；$s_i \to t_j$ 和 $s_l \to t_j$ 快到 $t_j$ 时，也会汇到同一条主干道上。$|S| \cdot |T|$ 次搜索，把同一片路网反复扫了 $|S| \cdot |T|$ 遍。

整条发展脉络，就是在回答这些重复劳动怎么才能只做一次。

第一步：一行一行地算

+

Dijkstra, E. W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik, 1, 269–271。

第一个可以利用的事实来自 Dijkstra 算法本身：它按距离从小到大依次确定每个点，要确定 $t$，就得先确定所有比 $t$ 更近的点。所以点对点和一对全的成本几乎一样——从 $s$ 搜到 $t$ 时，半径 $\mathrm{dist}(s,t)$ 以内的点已经全部算完了。

于是有了最早、也最常用的做法：对每个 $s \in S$ 跑一次 Dijkstra，不在碰到第一个目标时停下，而是一直跑到 $T$ 里所有点都被确定为止。一次搜索填满矩阵的一整行，$|S|$ 次搜索填满整张表。

这把 $|S| \cdot |T|$ 降到了 $|S|$，而且实现极其简单，至今仍有系统直接这样做，比如 pgRouting 的 pgr_dijkstraCostMatrix pgRouting 文档对它的描述是「Calculates a cost matrix using pgr_dijkstra」，不做任何预处理。见 docs.pgrouting.org。 。当 $|S|$ 很小——「一个仓库发往一堆客户」——这个做法就够用了。

但它的每一行都很贵。在西欧路网上，随机一对点的 Dijkstra 平均要扫九百多万个节点，约 2.2 秒 综述 Table 1：Dijkstra（4-heap）平均扫描 9,326,696 个节点，耗时 2,195,080 μs。Knopp 等人 2007 年在 2.6 GHz 的 AMD Opteron 上测的是一次约 10 秒，据此估算 $10{,}000$ 个源点要跑「大约一天」。 。$|S|$ 一大，就回到了「每一行都把整片路网扫一遍」。

更麻烦的是，点对点查询的那些不需要预处理的加速手段，在这里几乎派不上用场 Knopp 等人把目标导向搜索和双向搜索都改造到了多对多场景，实测相比一行一行的 Dijkstra 只快 2 到 3 倍，视输入而定。 ：

• 目标导向的方法（A*、ALT）靠「朝目标的方向」剪枝。可这一次搜索要同时服务 $|T|$ 个散落各处的目标，只能朝着它们当中最保守的那个方向去估计，剪枝效果大打折扣。
• 双向搜索从 $s$ 和 $t$ 两头对搜，在中间相遇。可这里的一次搜索并没有一个确定的「另一头」。

要让每一行变便宜，得换一种思路。

第二步：从中间劈开

+

Sanders, P. & Schultes, D. (2005). “Highway Hierarchies Hasten Exact Shortest Path Queries.” ESA ‘05, LNCS 3669, 568–579。HH 的「高速边」不是按道路等级人为指定的，而是按局部邻域定义的：一条边若出现在某条最短路上、并且离这条路的两端都超出了各自的邻域半径，它就属于上一层。层级由此逐层归纳出来。

2000 年代中期，点对点查询的研究转向了层次化方法，代表是 Sanders 和 Schultes 的 Highway Hierarchies（HH）。它的观察是：离起点和终点足够远之后，最短路只会走高等级道路。于是双向搜索的两侧各自在局部铺开一小片，然后迅速「升」到稀疏的高层网络上，在那里相遇。

对多对多来说，这类方法有一个关键性质，当时并不显眼：

从 $s$ 出发的正向搜索空间，主要由 $s$ 自己决定；从 $t$ 出发的反向搜索空间，主要由 $t$ 自己决定。而且两者都很小。

普通的双向 Dijkstra 要靠两侧的半径来判断何时停，两侧是绑在一起的。层次化方法的两侧则各自按层级规则剪枝，搜索空间基本不依赖对方。既然如此，同一个 $t$ 的反向搜索，就没必要为每个 $s$ 重做一遍。

+

Knopp, S., Sanders, P., Schultes, D., Schulz, F. & Wagner, D. (2007). “Computing Many-to-Many Shortest Paths Using Highway Hierarchies.” ALENEX ‘07, 36–45。PDF 见 ae.iti.kit.edu。更早的版本是 Knopp 的硕士论文：Knopp, S. (2006). Efficient Computation of Many-to-Many Shortest Paths. Diplomarbeit, Universität Karlsruhe。

2007 年，Knopp 等人据此提出了多对多问题的第一个专门算法。论文里把它称作「关键的一步」：每个正向搜索和每个反向搜索都只做一次，把反向搜索空间存下来，供所有正向搜索复用。

用式子来写 $F(s)$、$B(t)$ 这套记号是本文为了串起后文而引入的，不是 Knopp 原文的写法。 ：记 $F(s)$ 为 $s$ 的正向搜索空间，$B(t)$ 为 $t$ 的反向搜索空间，层次化方法保证最短路一定经过两者的某个公共点，于是

$$\mathrm{dist}(s,t) = \min_{v \in F(s) \cap B(t)} \big( d(s,v) + d(v,t) \big)$$

这个式子把每一条最短路从中间劈开了：前半段只和 $s$ 有关，后半段只和 $t$ 有关。剩下的问题只是：怎么高效地把它们拼起来。

Knopp 的答案是桶（bucket）：

阶段 ①  对每个 t ∈ T：
            做一次反向搜索，得到 B(t)
            对其中每个节点 v：把 (t, d(v,t)) 放进 v 的桶 β(v)

阶段 ②  对每个 s ∈ S：
            做一次正向搜索，得到 F(s)
            对其中每个节点 v：
                for (t, d(v,t)) in β(v):
                    D[s][t] ← min(D[s][t], d(s,v) + d(v,t))

成本变成了 $|S| + |T|$ 次搜索，加上一遍桶扫描 Knopp 等人给出的代价模型是 $|S| \cdot \mathrm{Dijkstra}(F + |G'_K|) + |T| \cdot \mathrm{Dijkstra}(F) + O(|S| \cdot |T| \cdot f)$，其中 $F$ 是层级 $K$ 以下的平均搜索空间大小，$G'_K$ 是第 $K$ 层的核心，$f$ 是一次反向搜索在核心里留下的平均桶项数。前两项是搜索，第三项是扫桶。 。原论文在西欧路网上算 $10{,}000 \times 10{,}000$ 的距离表用了 67 秒，比一行一行的 Dijkstra 和 $10^8$ 次 HH 点对点查询都快一千倍以上——后两者各自估算要一天左右 数字出自 Knopp 等人论文第 1 节，硬件为单核 2.6 GHz AMD Opteron，路网为 1800 万节点的西欧商业数据。 。

这个原始版本的两侧其实并不对称。为了不让两侧都去搜庞大的最高层，反向搜索在进入第 $K$ 层核心时就停下，把剩下的路留给正向搜索：正向搜索要把整个第 $K$ 层核心都探索一遍。所以反向（填桶）的一侧便宜，正向的一侧贵，论文因此约定把较大的集合放在填桶的一侧，否则就在反向图上跑同一个算法 原文：「Without loss of generality we will assume $|T| \ge |S|$. Otherwise, it is more efficient to apply the algorithm below to the reverse graph.」 。

论文还指出了一个很有启发性的事实：调整参数 $K$，这个算法会在两个极端之间平滑过渡。$K = 0$ 时它就是一行一行的 Dijkstra；$|S| = |T| = 1$ 时它基本就是普通的 HH 点对点查询 原文：「our algorithm smoothly interpolates between the best algorithms for these extreme cases and promises considerable speedups in the middle where none of these other algorithms works very well.」 。用上面的式子来看，第一步其实是它的一个退化情形：取 $F(s) = V$，$B(t) = \lbrace t \rbrace$，反向那一侧什么都不做，所有工作都压在正向。桶方法的贡献，就是让两侧分摊工作，并且两侧都很小。

第三步：CH，让底座变简单

+

Geisberger, R., Sanders, P., Schultes, D. & Delling, D. (2008). “Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.” WEA ‘08, LNCS 5038, 319–333。期刊版：Geisberger, R., Sanders, P., Schultes, D. & Vetter, C. (2012). “Exact Routing in Large Road Networks Using Contraction Hierarchies.” Transportation Science, 46(3), 388–404。

桶方法本身不挑底座，只要求底座的查询是「两侧独立搜索、在中间相遇」 综述 2.7.2 节：桶方法「was introduced for Highway Hierarchies, but can be used with any other hierarchical speedup technique (such as CH) and even with hub labels」。 。第二年出现的 Contraction Hierarchies（CH） 把这个底座做到了几乎最简。

□ 收缩一个节点：如果它在某对邻居的唯一最短路上，就补一条等长的捷径；否则什么都不用做。判断依据来自一次局部的「见证搜索」。

CH 给所有节点排一个重要性次序，然后从最不重要的开始逐个「收缩」：拿掉节点 $v$ 时，如果 $u \to v \to w$ 是 $u$ 到 $w$ 的唯一最短路，就补一条长度为 $\ell(u,v) + \ell(v,w)$ 的捷径，保证剩下的图里距离不变。全部收缩完之后，把每条边（含捷径）按两端的次序定向，只保留「从低到高」的方向，得到一张上行图。

它带来的性质比 HH 干净得多 理由是：最短路上任何一个「两侧邻居都比它高」的低谷节点，在收缩时都会被一条捷径跨过去。反复替换之后，路径上就只剩一个最高点，它的左边单调上升、右边单调下降。 ：

任意 $s \to t$ 的最短路，都能写成「一段上行 + 一段下行」，中间是路径上次序最高的那个点。

于是 $F(s)$ 就是从 $s$ 在上行图上能走到的所有点，$B(t)$ 就是从 $t$ 沿反向在上行图上能走到的所有点。两者都由预处理唯一确定，两侧完全对称，不再需要 HH 那样的参数 $K$。

在西欧路网上，CH 的预处理约 5 分钟，一次点对点查询（两侧合计）平均只扫 280 个节点，耗时约 $110\ \mu s$ 综述 Table 1：CH 预处理 0:05（时:分），空间 0.4 GiB，平均扫描 280 个节点，查询 110 μs。和上面 Dijkstra 的 930 万个节点相比，差了四个多数量级。 。套上桶方法（通常叫 BCH，Bucket CH），每一侧的搜索都很便宜，表一大，成本的大头就落到了扫桶上：搜索的总量随 $|S| + |T|$ 增长，扫桶的总量却随 $|S| \cdot |T|$ 增长 见前面 Knopp 代价模型里的第三项。论文的实验也印证了这一点：在接近方阵的输入上，正向搜索和扫桶占了主要时间；只有在 $|T|$ 远大于 $|S|$ 时，反向搜索才是大头。 。

围绕扫桶，又有几个工程上的改进：

• stall-on-demand。 CH 的上行搜索会确定一些距离并不是真正最短的点（真正的最短路要先下后上才能到达它们），它们留下的桶项注定没用。搜索时顺手检查一下能否从更高的邻居更便宜地到达，就能把这些点剪掉，桶的总量随之下降 stall-on-demand 最早出自 Schultes, D. & Sanders, P. (2007). “Dynamic Highway-Node Routing.” WEA ‘07, LNCS 4525，后来成为 CH 查询的标准配件。Knopp 等人在 HH 上也做了思路相近的「减少桶项」优化；Buchhold 等人 2021 年的拼车算法在生成桶项时同样用了它。 。
• 桶的存储。 桶是「先全部写完、再反复读」的，所以与其给每个节点挂一个动态数组，不如把所有 $(v, t, d)$ 三元组收集到一个数组里按 $v$ 排序，变成连续内存。这个做法 Knopp 等人在 2007 年就用了，他们报告比最初的动态数组实现快了两倍多 Knopp 等人用的是计数排序，排好之后每个节点只存自己那段桶的起始偏移和长度。OSRM 的 table 服务（many_to_many_ch.cpp）也是先收集、再 std::sort，正向搜索时用 std::equal_range 二分定位桶。 。
• 多个度量一起带。 实际的距离表往往按「加权代价」找最短路，却要输出这条路的时间和里程。比如加了「尽量不走小路」惩罚的代价，就和真实的行驶时间不再成比例，没法从一个推出另一个，所以这几个量必须在桶项里一起沿路累加 OSRM 的桶项 NodeBucket 里同时存了 weight、duration 和 distance 三个字段，weight 用来比较和取最小，后两者只作为输出。 。

到这一步，BCH 成了多对多的事实标准，以 CH 为底座的引擎（比如 OSRM）的矩阵服务就是它。

分岔：目标非常多的时候

BCH 适合 $|S|$ 和 $|T|$ 都不算大的方阵。如果某一侧大到接近全图，扫桶就变成了主要成本，桶本身也会占掉大量内存。这时值得回到第一步的「一行一行地算」，只不过用 CH 把每一行变便宜。

+

Delling, D., Goldberg, A. V., Nowatzyk, A. & Werneck, R. F. (2013). “PHAST: Hardware-Accelerated Shortest Path Trees.” Journal of Parallel and Distributed Computing, 73(7), 940–952（会议版为 IPDPS ‘11）。

PHAST（2011）解决的是一对全。它的想法是：既然每条最短路都是「上行 + 下行」，那就先从 $s$ 做一次上行搜索，然后按次序从高到低把所有节点线性扫一遍，沿下行边把距离往下推。扫到一个点时，所有比它高的点都已经算完，所以它的距离也就确定了。

这个看似笨拙的全图扫描反而很快，因为第二阶段的访问顺序是预先固定的，和 $s$ 无关。节点可以按这个顺序重新排布内存，扫描几乎是纯顺序访问；还可以在同一遍扫描里同时推进多个 source 的距离向量，用 SIMD、多核乃至 GPU 并行。在路网上，PHAST 即使单线程也能比 Dijkstra 快一个数量级以上 综述 2.7.2 节：「In road networks, PHAST can be more than an order of magnitude faster than Dijkstra’s algorithm, even if run sequentially, and can be further accelerated using multiple cores and even GPUs.」 。

+

Delling, D., Goldberg, A. V. & Werneck, R. F. (2011). “Faster Batched Shortest Paths in Road Networks.” ATMOS ‘11, OASIcs 20, 52–63。

RPHAST（同年）把它限制到一对多：既然只关心 $T$ 里的点，就先从 $T$ 出发做反向上行搜索，收集所有可能把距离传给 $T$ 的点，得到一个小得多的子图。之后每来一个 source，都只需要「一次上行搜索 + 一遍小子图扫描」。子图的提取只做一次，所以 RPHAST 特别适合 $T$ 固定、$S$ 反复变化的场景——仓库集合不变、客户点每天不同。

用前面的式子来看，PHAST / RPHAST 走的是另一条路：它们保留了 $B(t) = \lbrace t \rbrace$ 的「行式」结构，但用 CH 的次序把「算出一整行」从一次 Dijkstra 变成了一遍顺序扫描。拼接式和行式这两条线，从这里开始分开发展。

分岔：把搜索空间存下来

另一个方向是继续往拼接式的极致走：既然 $F(s)$ 和 $B(t)$ 都由预处理唯一确定，何不干脆提前算好、存下来？

+

2-hop 标签的原始概念：Cohen, E., Halperin, E., Kaplan, H. & Zwick, U. (2003). “Reachability and Distance Queries via 2-Hop Labels.” SIAM Journal on Computing, 32(5), 1338–1355。

路网上的实现：Abraham, I., Delling, D., Goldberg, A. V. & Werneck, R. F. (2011). “A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks.” SEA ‘11, LNCS 6630, 230–241。

这就是 Hub Labeling（HL）。每个点 $u$ 存一个正向标签 $L_f(u)$ 和一个反向标签 $L_b(u)$，里面是若干 $(h, d)$ 对，要求任意 $s, t$ 的最短路上都有一个 $h$ 同时出现在 $L_f(s)$ 和 $L_b(t)$ 里。Abraham 等人在 2011 年发现，直接拿 CH 的上行搜索空间当标签就满足这个要求，再剪掉其中距离不正确的项，标签就能缩到平均 85 项左右 Abraham 等人（2011）第 3–4 节：直接用 CH 搜索空间作标签，西欧路网平均每个标签 536 项，估计共需 154 GB；用基于 stall-on-demand 的启发式剪枝降到约 133 项；再去掉所有距离不紧的项，并结合理论算法的思路，最终降到不到 85 项。 。

于是点对点查询变成两个有序数组的归并，约 $0.56\ \mu s$，比 CH 又快了两个数量级 综述 Table 1：HL 查询 0.56 μs，CH 110 μs，相差约 200 倍。 。

+

把标签放进关系数据库、用 SQL 完成一对多、kNN 等查询：Abraham, I., Delling, D., Fiat, A., Goldberg, A. V. & Werneck, R. F. (2012). “HLDB: Location-Based Services in Databases.” SIGSPATIAL GIS ‘12。

放到多对多里，结构和 BCH 完全一样：把所有 target 的反向标签按 hub 倒排，得到 $h \mapsto \lbrace (t, d(h,t)) \rbrace$——这就是桶；再对每个 source 遍历它的正向标签，查这张倒排表 综述在介绍桶方法时引用了 RPHAST 那篇论文（Delling, Goldberg & Werneck 2011），说明桶方法同样可以配合 hub labels 使用。 。区别只在于，原本要靠一次上行搜索现算的 $F(s)$ 和 $B(t)$，现在直接从内存里读出来。

代价是空间：西欧路网的标签要 18.8 GiB，压缩版 HLC 也要 1.8 GiB，仍是 CH 的四倍多 综述 Table 1：HL 18.8 GiB，HLC 1.8 GiB（查询 2.55 μs），CH 0.4 GiB。 。这是一个用空间换掉全部搜索的方案。

走出静态图

到这里为止的所有方法都有一个隐含前提：图和边权是固定的，预处理一次，查询无数次。实际应用会从三个方向打破这个前提，多对多的研究也跟着走了出去。

边权随时间变化

+

Geisberger, R. & Sanders, P. (2010). “Engineering Time-Dependent Many-to-Many Shortest Paths Computation.” ATMOS ‘10, OASIcs 14, 74–87。

引入早晚高峰后，通过一条边的时间取决于什么时候进入它。正向搜索没有问题，时钟沿路往前推就行；问题出在反向搜索——要算「从 $v$ 到 $t$ 要多久」，得先知道几点到达 $v$，而这取决于 $s$ 是谁、走了哪条路。

这时表里的每一格就不再是一个数，而是一个函数：出发时刻 ↦ 行驶时间，通常用分段线性函数表示。Geisberger 和 Sanders 在 2010 年基于时间依赖 CH（TCH）给出了第一批高效算法。他们指出，算出整张函数表本身就是 $\Theta(|S| \cdot |T|)$ 的；于是其中一个方案只做 $\Theta(|S| + |T|)$ 的预计算，之后按需回答某个 $(s, t, \text{出发时刻})$，比直接用 TCH 查询快两个数量级 据论文摘要：「The computation of a table is inherently in $\Theta(|S| \cdot |T|)$ … We provide one particular algorithm using only $\Theta(|S|+|T|)$ time and space, being able to answer queries two orders of magnitude faster than the basic TCH implementation.」 。拼接的思路没变，只是拼的对象从数变成了函数，计算量和空间都重得多。

工程上更常见的是退让，大致有三种，各自带着不同的误差：

• 只用正向搜索：放弃拼接，退回第一步的一行一行正向搜索。结果是精确的，但失去了 $|S| + |T|$ 的好处。
• 冻结时钟：固定出发时刻，假设整个行程中路况不变，这样反向搜索又能用了。行程越长，误差越大。
• 分时段：把一天分成若干时段，每段当作静态图各算一张表。跨时段的行程会有误差。

边权随请求变化

+

Dibbelt, J., Strasser, B. & Wagner, D. (2016). “Customizable Contraction Hierarchies.” ACM Journal of Experimental Algorithmics, 21, 1.5:1–1.5:49（会议版为 SEA ‘14）。预印本见 arxiv.org/abs/1402.0402。

CH 的捷径长度绑定在一套具体的边权上。实时路况一变，或者换一种车型（避开收费、卡车限高），整套预处理就失效了。

Customizable CH（CCH） 把预处理拆成两步：节点次序只依赖图的拓扑（用嵌套剖分生成），离线做一次；边权相关的部分叫 customization，在西欧路网上不到一秒就能完成 Dibbelt 等人论文 9.5 节：在 2 × 8 核的机器上并行，「we customize Europe in below one second」，摊销后为 415 ms。作为对照，综述 Table 2 里另一条可定制路线 CRP 的 customization 约 0.37 s（12 核）。 。CCH 保留了「上行 + 下行」的性质，所以桶方法可以原样搭在它上面。

这让多对多可以跟着实时路况走：每隔几分钟按最新路况重新 customize 一次，查询照旧用桶 下文 Buchhold 等人的拼车算法就是这样用的：「by building on customizable contraction hierarchies, we can quickly update these costs according to the current traffic situation every few minutes.」 。但如果每个请求都带一套不同的代价参数，customization 就得按请求来做，这几百毫秒的固定开销会压在每一次查询上。这条路并非走不通——综述提到，CRP 的 customization 借助 GPU 可以压到 36 ms，已经快到能在查询时设定代价函数 综述 3.1 节：「Customization times can be even reduced to 36 ms with GPUs, … This is fast enough for setting the cost function at query time.」 ——但它对硬件和工程的要求都很高。很多需要按请求定制代价的引擎，最终还是选择了不做预处理、靠运行时的启发式剪枝去近似。

$S$ 和 $T$ 本身在变化

+

Buchhold, V., Sanders, P. & Wagner, D. (2021). “Fast, Exact and Scalable Dynamic Ridesharing.” ALENEX ‘21。预印本见 arxiv.org/abs/2011.02601。

最后一个变化来自网约车和拼车调度。这里的「矩阵」不是一次性的：一整支车队的计划路线一直在变，新的乘客请求不断到来，每来一个请求，都要算出它的上下车点和所有车辆的所有途经点之间的距离，从而判断插到哪辆车的哪个位置最划算。

Buchhold、Sanders 和 Wagner 在这里把桶方法推向了一个新形态：桶不再是一次查询的临时数据，而是一个持续维护的索引。 每辆车的每个途经点常驻在桶里；车辆插入一个新停靠点时，就为它生成桶项，完成一个停靠点时，就删掉对应的桶项。新请求到来时，只需要从上车点和下车点各做一次搜索、扫一遍桶。

配合这个形态还有一个很漂亮的剪枝。车辆在相邻两个途经点 $a$、$b$ 之间留有一个时间余量 $\lambda$，任何插进来的新停靠点 $v$ 都必须满足

$$d(a,v) + d(v,b) \le d(a,b) + \lambda$$

满足这个条件的 $v$ 构成以 $a$、$b$ 为焦点的一个「椭圆」，桶项只需要放在这个椭圆里的节点上。论文把它叫作椭圆剪枝（elliptic pruning），作者自己的评价是「surprisingly effective」。

最终的算法 LOUD 是精确的，比当时业界和学术界通用的方案快 30 倍，在柏林规模的交通仿真里把一轮仿真从几天缩短到了几小时 据论文摘要与第 1 节：「Our algorithm finds provably exact solutions, is still 30 times faster than a state-of-the-art algorithm currently used in industry and academia, and scales much better. When used within iterative transport simulations, our algorithm decreases the simulation time for large-scale scenarios with many requests from days to hours.」实验场景之一是 Open Berlin Scenario。 。

回头看

把这条脉络串起来，所有方法都落在同一个式子里：

$$\mathrm{dist}(s,t) = \min_{v \in F(s) \cap B(t)} \big( d(s,v) + d(v,t) \big)$$

区别只在于 $F(s)$ 和 $B(t)$ 怎么得到，以及用什么把它们拼起来。

沿着这张表往下读，能看到两条线索交替推进。

一条是把工作挪到哪里。最初所有工作都压在正向一侧；桶方法让两侧分摊；HL 把两侧都挪进了预处理；动态拼车则把一侧变成了常驻的索引。每一次挪动，都是在用预处理和空间换查询时间。

另一条是前提有多强。越靠后的方法越快，也越依赖「图不变、边权不变、度量唯一」。时间依赖、可定制、动态集合这几支工作，都是在已有的速度和被打破的前提之间重新找平衡。

所以真正用的时候，问题往往不是「哪个算法最快」，而是你的场景能接受多强的前提：边权固定就上 BCH；一侧固定就考虑 RPHAST；度量要按请求定制，又没有条件做快速 customization，就只能回到第一步，老老实实地一行一行算，再靠分块、缓存和近似把成本压下来。