每个核心每秒每秒数十万条路由。Yandex路由体验

几周前，Danya Tararukhin 在哈布雷（Habé）上告诉我们，Yandex.Routing服务的外观如何，以及它如何为公司提供物流服务。通过创建平台，我们解决了一些有趣的问题，其中一个专门针对今天的帖子。我想谈谈路线规划本身及其所需的资源。

在多个点之间找到最佳路线是一个经典的离散优化问题。要解决此问题，您需要知道所有点之间的距离和传播时间。也就是说，要知道距离和时间的矩阵。两年前，长矩阵计算对我们来说是一个非常关键的问题，阻碍了开发。用已知矩阵搜索最优解需要10分钟，但是大型任务（针对数千个订单）的矩阵所有单元格的计算却要花费数小时。

要解决五千个订单的问题，您需要知道所有点之间的距离和行驶时间。这是两个数字矩阵，尺寸为5000x5000。我们计划一整天的快递路线，早上，快递员一次到另一点，晚上到另一点。因此，您需要计算一天中每个小时的时间和距离矩阵。并非一天中的所有时间都是唯一的，但是软木塞的时间（早上和晚上）需要很好地涵盖。因此，我们进行了十三个小时的配置。总共，我们需要两个多维数据集（时间和距离），每个13x5000x5000。根据实际路线图，这是3.25亿条路线，其中有1.65亿条边。在Yandex.Maps小组经过充分优化的算法中，一条路线的计算大约需要10毫秒，总共需要900个小时的计算时间。即使并行化为900个CPU，您也需要等待1个小时。我们无法启动这样的服务，我们需要一个更合适的算法。

为了进一步阅读，了解Dijkstra的算法以找到图中的最短路径很有用。可以想象为从路线的起点发出并绕过整个图形直到达到终点的“波浪”。该算法的运行时间与图表的边缘成比例，即波浪所覆盖的区域：



几乎每个在面试中面试的候选人都猜测到优化此任务的第一步：您可以从两侧开始波浪，并在波浪相遇时结束搜索。半半径的两个波浪的总面积小于一个大。



实际的路线图结构合理，可以使用。当您寻找莫斯科与圣彼得堡之间最短的距离时，在经典的迪克斯特拉（Dijkstra）中，您将被迫围成一圈散布海浪，穿越莫斯科的所有街道和小巷，莫斯科地区的城市和村庄，特维尔和诺夫哥罗德的街道。这是大量的计算，但是您可以预先准备并记住城市之间的最佳路线（也称为快捷方式），而不必在运行时重复它们。然后，要在分层的Dijkstra中找到两点之间的路线，您需要计算到所需快捷方式的最短距离。由于层次结构级别可能不是2而是5-6，因此它们大大减少了搜索时间。

卡路由器团队已经实施了此类优化已有相当一段时间。正是由于他们，他们才有可能在10毫秒内找到两点之间的路线。 :)因此，到目前为止，我们还无法解决问题。

由于点对点搜索模式已经非常优化，因此我们可以优化矩阵中序列的计算。行是从一个点到所有其他点的距离。在寻找到最远点的距离时，我们同时计算了到更近点的距离。因此，计算级数等效于计算到最远点的距离。



我们看一下使用此算法计算序列的时间，并回想起依次计算5000条路线将花费大约5000 * 10 ms = 50 s：


该图显示了对于不同的N（根据实际数据），在大小为1 * N的距离矩阵中一行的计算时间。可以看出，我们感兴趣的大小为1 * 5000的行的计算适合1.3秒。趋势线已添加到图表中，它表​​明计算时间的增长速度比线性增长的N慢得多，N **的数量级0.74

已经不错！使用此算法，我们可以在13 * 5000 * 1.3 s = 84 500 s =几乎24小时内计算出立方体。它很容易并行排列，使用50个CPU时，距离以半小时计算。多维数据集计算算法的复杂度顺序为O（N ** 1.74）：


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

两年半前，我们以这种形式发布了API的第一个版本，该版本解决了物流问题。客户经常抱怨决策时间长，他们很容易理解：您开始要解决的任务，等待1个小时，得到解决方案，并且您知道自己忘记与驾驶员确定轮班时间，您对其进行了更正并重新开始了所有工作。司机开始变得紧张，因为他们冒着进入高峰时间的风险，甚至没有时间按时交付订单。有必要做点什么。我们不想“扔”铁的问题：我们正在为重负荷做准备，它需要大量的铁，并且服务器的购买不会马上发生。

一项对学术文章的研究表明，针对此任务，存在一些具有线性复杂度的算法*！ （在引用的文章中，对Dijkstra加速的各种现代方法进行了广泛的概述，包括矩阵情况。）以线性时间计算矩阵并不适合我的想法。我们的一位开发人员自愿编写了一个原型，这就是发生的事情：是


时候使用“快速矩阵”算法在一个CPU上计算一个大小为N * N的矩阵了。复杂度约为O（N ** 1,1）。高Ns被排除在趋势线之外，因为答案的生成及其在网络上的下载已经对时间产生了更大的影响。

使用单核并且对N的线性依赖关系，每个5000x5000矩阵需要115秒。虚构已经成为现实！该算法的思想结合了上述两个思想：用于序列搜索和层次搜索的Dijkstra。显然，开始计算第二行，在某些时候，我们将再次遍历刚刚经过的图形的同一区域，从而计算上一行。因此，让我们在分层图的节点上记住到所有目标的最短距离。当我们开始计算下一个序列时，到了这样一个节点，我们将立即获得到其他点的几乎所有距离。



一年半前，这使我们能够节省大量的时间，半小时Ë物流大大减少了铁的摄入。以前，对于一个大请求，我们需要50个核心半小时，但现在-13个核心2分钟。每个核心每秒大约有200,000条路由。新算法不仅关闭问题类别，而且扩展了我们对可能性的想法的罕见情况。

---

_{^{*文章“交通网络中的路线规划”，请参见第2.7.2节“分批的最短路径”}}