ACM通信

研究突出了

多行程优化作为云服务

作者:Alexandru Cristian, Luke Marshall, Mihai Negrea, Flavius Stoichescu, Peiwei Cao, Ishai Menache
ACM通信，2021年11月，第64卷第11期，121-129页
10.1145 / 3485626
评论

在本文中，我们描述了多行程优化(MIO)——一种新的必应地图(Bing Maps)服务，它可以自动为多个代理构建行程流程，同时优化他们的路线以最小化旅行时间或距离。MIO可用于拥有车队和司机、移动销售队伍或现场人员团队的组织，以最大化劳动力效率。它支持各种限制条件，如服务时间窗口、持续时间、优先级、取货和送货依赖关系以及车辆容量。MIO还考虑了地点之间的交通状况，这导致了多个层面的算法挑战(例如，大规模计算与时间相关的旅行时间距离矩阵和为多个代理调度服务)。

为了支持周转时间只有几秒钟的端到端云服务，我们的算法设计瞄准了准确性和性能之间的最佳点。为此，我们构建了一种基于ALNS元启发式的可扩展方法。我们的实验表明，考虑交通因素显著提高了解决方案的质量:MIO找到了避免迟到的有效路线，而交通不可知的方法导致旅行时间和到达迟到时间的总和增加了15%。此外，我们的方法生成的行程比前沿启发式(LKH)的质量要高得多，对于大型实例，运行时间更快。

回到顶部

1.简介

对于许多企业来说，路线规划和服务调度操作是一个耗时的手工过程。这个手工过程很少找到有效的解决方案，特别是那些必须考虑通信量、服务时间窗口和其他复杂的现实约束的解决方案。此外，规模也成为一个挑战:服务调度计划可能涉及多个车辆，需要在数天的时间内在多个地点之间进行路由。

大规模互联网地图服务的发展，如谷歌和必应地图，为自动解决路线规划问题创造了机会，作为一种云服务。大量关于地理位置、旅行历史等的数据被存储在企业云中，原则上可以用于为多个代理派生定制行程。这种自动化的目标是提高操作效率，通过更快地确定这些行程(在循环中的人员更少)和与手动生成的日程相比具有更好的质量。然而，要实现这一愿景，还必须解决多重挑战。

首先，路线规划需要有效计算不同地点之间的旅行时间矩阵。尽管这个问题对于自由流动的旅行时间(即没有交通流量)已经很清楚了，^13，8要按需生成任何时间点的交通感知旅行时间，需要仔细关注算法和系统的可伸缩性。其次，路线规划本身必须考虑多个特征——时间窗口、优先级、在每个地点花费的时间(例如，服务持续时间或停留时间)、车辆容量、取货和送货顺序，以及地点之间的预测交通。没有所有这些复杂约束的单一代理版本对应的是旅行推销员问题(TSP)，这已经是NP-hard了。运筹学和相关学科在车辆路径问题(VRP)下对TSP进行了大量的扩展研究。^{15，16，18，22}但是，大部分的工作不能很容易地扩展，以考虑位置之间的通信，特别是在大规模的情况下。为了满足客户的需求，我们的服务必须包含流量，并在数秒内为具有数百个路点的实例输出优化的调度。

在本文中，我们描述了多行程优化(MIO)，这是必应地图最近部署的一项公共服务。²MIO的设计解决了上述算法挑战，以及潜在的工程需求(例如，云资源的有效使用)。特别地，我们的解决方案由一个结构化的高级算法管道组成。在最低层，我们通过结合收缩层次结构(CH)计算旅行时间矩阵。¹³结合交通预测，提出了一种高效的时间相关最短路径算法。然后我们使用这些矩阵进行行程优化。我们的行程优化算法是基于一种流行的元启发式自适应大邻域搜索(ALNS)，²¹它通过在多个搜索操作符(即修复和销毁)之间进行明智的选择来实现最佳调度。我们的搜索操作符经过精心设计，以考虑流量和异构代理。整个管道被实现为云服务，可以通过灵活的REST体系结构轻松访问。

我们执行广泛的评估来检查端到端解决方案的质量。特别地，我们首先强调了在路线规划中考虑交通因素的重要性。我们的实验发现，当规划期间忽略交通时，高达40%的计划工作(例如，服务或在路径点停留时间)在重新引入交通时违反了其时间窗口限制。此外，总的旅行时间和到达延误时间比我们的交通感知方法平均高出15%。另一方面，使用保守的旅行时间(即地点之间的最大旅行时间)会导致行程安排多出10%的旅行时间。接下来，我们将MIO与最先进的启发式lin - kernighan - helsgan (LKH)进行比较。¹⁵我们的结果表明，就及时满足的服务而言，MIO以更少的处理时间获得了更高质量的解决方案。在我们公开发布的包括大约1000个地点的实例中，MIO运行速度比LKH快两倍。⁷

尽管有相关的商业产品(例如，参见第5节的概述)，但公司通常会掩盖算法的一些细节和/或使用一些算法组件作为黑箱(例如，旅行时间计算)。据我们所知，本文首次报道了为多个代理生成流量感知行程的端到端云服务的完整算法细节。本文的其余部分组织如下。第2节提供了一些必要的背景知识;第3节概述了我们的算法和云部署的细节。第四部分描述了我们的实验和结果。我们将在第5节中对相关工作进行调查，并在第6节中进行总结。

回到顶部

2.背景与动机

2.1.互联网地图服务

最近互联网地图服务的创新为微软和谷歌等大型云服务提供商创造了许多新的商业机会。例如，在企业对消费者领域，基于位置的服务可以用于更个性化的用户体验和更好的定向广告等。在企业资源规划方面，诸如车队管理(例如皮卡和送货卡车)和劳动力调度(例如调度和路线现场技术人员)等任务可以从建立在准确和最新地理空间数据上的自动化地理信息系统服务中受益。然而，在互联网时代，地图服务的用户有很高的期望。例如，一个“大型”调度任务(例如，数百到数千个路点)预计在几分钟内完成，而较小的任务(几十个路点)预计在几秒钟内完成。从云提供者的角度来看，这些期望转化为端到端响应时间上的服务级别目标(SLOs)。此外，供应商希望在有效利用计算资源的同时，根据预定义的指标(例如，尽量减少旅行时间或燃料消耗)生成高质量的解决方案。

2.2.Multi-itinerary优化

必应地图最近部署了一项企业级规划服务，称为多行程优化(MIO)。²术语“行程”对应于单个代理(例如，卡车或技术人员)，并从较早的用于假期计划的消费者版本中继承下来。MIO将一组路点(即晚/长位置)作为输入，每个路点都有自己的需求;要求可能包括停留时间、时间窗口、优先级、取货地点和货物数量。输入的另一部分是一组代理。每个代理的特征是起始/结束位置、可用时间窗口和车辆容量(当相关时)。在给定输入的情况下，MIO的目标是找到指向给定代理的路径点子集的一个可行分配(即尊重约束)，这使某些系统目标最大化。例如，一个流行的目标是最大化访问的路径点的数量(或优先级)，同时最小化总旅行时间。

2.3.设计的挑战

MIO作为云服务的实现具有多个层次的复杂性。首先也是最重要的是，服务必须根据客户需求进行健壮的扩展。我们的旅行时间计算包括取一组晚/长地点(世界上任何地方)，将它们连接到道路网络，并在考虑交通流量的同时快速计算成对的最短旅行距离。这需要大量的算法和工程工作来支持大量的用户和路径点。最重要的是，将预测交通纳入到路线规划中会使本已np困难的问题更加复杂。人们可能会怀疑是否真的有必要考虑交通流量。图1演示了单个出发地到目的地路线(西雅图市中心到微软园区)的时间依赖的旅行时间。请注意，由于交通的原因，旅行时间在一天中有很大的差异，特别是在高峰期(上午8-9点和下午3-6点)。由于旅行时间的变化如此之大，明确地考虑交通是非常必要的。我们在第4.2节中的实验提供了这种直觉的定量分析，并强调了在忽略流量时潜在的业务分支。

图1。示例路由的时间依赖性流量概要。

回到顶部

3.绪设计

在本节中，我们将详细介绍MIO的设计。3.1节描述了我们如何有效地计算考虑交通的旅行时间矩阵。这些旅行时间矩阵作为路径规划优化的输入(第3.2节)。在3.3节中，我们将重点介绍使MIO成为高效云服务的一些工程选择。

3.1.行程时间计算

给定一组位置，a距离矩阵是通过计算每对位置之间最短路径的长度而构造的二维矩阵。最短路径原则上可以表示不同的度量，如物理距离、旅行时间和成本。按照惯例，当最短路径使自由流动的旅行时间(即没有交通流量)最小化时，我们使用术语距离矩阵。一个流量矩阵增加了一个额外的时间维度，其中最短路径在给定的时间范围内使依赖时间的旅行最小化。

为了高效计算，我们生成交通矩阵的算法使用相关的距离矩阵作为基线，并使用预先计算的预测交通将其扩展到与时间相关的旅行时间。有几种基于集线器标签的快速距离矩阵计算实现⁸或者收缩层次结构。¹³收缩层次结构是路网距离计算的一种有效方法(在数据量、预处理和查询速度方面)。它通过执行预处理步骤大大减少了计算最短路径距离所需的查询时间。预处理步骤生成由“收缩”步骤组成的多层节点层次结构(顶点层次)，该步骤临时删除节点并添加“快捷方式”以保持正确性。图2给出了一个简单的例子。我们面临的挑战是整合这种快速计算旅行时间的方法，同时考虑到交通波动。

图2。一个CH图的例子。²⁴实线代表原来的路网。收缩步骤临时删除节点(突出显示的区域)并添加快捷方式(虚线)。灰色箭头表示哪些边被组合了。

输入和离线处理。我们的系统结合了许多与交通相关的输入来源(例如，GPS跟踪)，以估计每条道路在任何时刻的旅行时间。为了给出准确的每周交通预测(以15分钟为粒度)，我们使用6个月的历史数据，对每条道路的出行时间进行了汇总，并更多地考虑了最近的出行时间。

在用收缩层次结构(CH)对道路图进行预处理之后，基于预测交通数据和其他图形属性(如转弯限制或转弯成本)，我们计算每次离线收缩的旅行时间;看到图3．这个离线过程的结果是，我们有两个输出:

图3。用于流量矩阵服务的离线管道。

1. CH图(即快捷图和顶点层)
2. CH图中包含672个值的每条边的预测交通数据(7天x 24小时x 4个季度小时)

在查询时，CH图被加载到内存中(北美西部约3GB;~85GB对于整个世界)和预测流量数据从SSD使用内存映射文件读取(~100GB对于北美西部;全世界约5TB)。计算给定时间范围内的流量矩阵的查询使用基于双向Dijkstra的时间相关最短路径算法。¹⁹

与时间相关的最短路径。一般来说，依赖时间的最短路径问题至少np困难;但在一定的假设条件下，可以用多项式时间算法高效求解。^9，14，11特别是，我们假设FIFO属性，这本质上意味着较晚的出发有较晚的到达。

对于依赖时间的最短路径问题，有几个可能的目标。例如，如果一个人的出行时间最小，解可能在原点等待，直到车辆减少，而当最小化总出行时间，解可能在任何路口等待，以避免车辆。在我们的设计中，我们最小化了到达时间，避免了等待，是实践中共同的目标。不管变量是什么，与时间相关的最短路径问题的解决方案是一个距离函数，由开始的“调度”时间参数化。我们的算法被专门设计来生成一个(三维的)交通矩阵，也就是说，一个分段常数的时间相关的距离函数(离散成15分钟的间隔)为每对位置。我们基于双向Dijkstra算法来快速计算从单一起点到多个目的地的所有时间相关距离，从而实现基于时间相关的最短路径算法。

算法的详细信息。CH应用于路网，并使用生成的快捷图和顶点层。预测的旅行时间在一周内以15分钟的间隔存储(共672个值)。CH图被加载到RAM中，并通过SSD上的内存映射文件访问流量预测。

的流量矩阵请求N时间范围内的路径点T时间间隔执行N个人———N与时间相关的最短路径查询(每个原点一个，总共为N x N x T旅行时间)。CH图用于加速双向(向前/向后)搜索，因为它只足以探索具有更高顶点级别(即更重要)的节点。

在正向搜索中，从原点开始，通过遵循出跳(边)，按照它们的层次顺序搜索顶点。对于遇到的每个顶点，从原点计算与时间相关的旅行时间，并缓存每个顶点的最短旅行时间(和请求的时间间隔)。为了提高查询速度，正向搜索受从原点开始的跳数(收缩中最大快捷边数的2倍)和旅行距离(从原点到最远目的地的自由流旅行时间的10倍)的限制。

对于每个目的地，执行一个向后的类似dijkstra的搜索，同样只访问CH图中顶点级别较高的节点(通过进入的边)，并使用自由流旅行时间来确定最短路径。一旦通过前向搜索中看到的后向搜索到达一个顶点，就计算从找到的顶点到目的地的后向路线和旅行时间(预测交通)。然后，在每个间隔中得到的每个旅行时间与之前发现的旅行时间(最初设置为一个非常高的值)进行比较——如果任何一个旅行时间小于已经发现的时间，则更新结果数组。在执行了固定的最大轮数而没有找到任何间隔的更小的旅行时间后，向后搜索将停止。

处理完所有目标后，算法返回N x T给定的起始节点和时间范围的最短旅行时间。

我们注意到，使用自由流旅行时间来引导向后搜索可能会导致近似于时间相关的最短路径;然而，这在实践中不太可能发生，因为在发现正向图和向后图之间的第一个交集后，仍在继续寻找更好的解。

的性能。我们在由来自德国的路点组成的1200个实例的查询集上评估了交通矩阵的性能。这些查询根据路径点和矩阵请求大小之间的距离而变化，每个变量有100个查询。每个查询的时间范围分别为96和672个间隔(分别为一天和一整周)，输出如所示表1．平均响应时间由距离、间隔数和请求矩阵的大小(其中)划分冷从SSD读取流量数据时的响应时间温暖的指示当流量数据已经缓存到内存中时的响应时间。

表1。流量矩阵冷/热响应时间。

观察距离对温暖的响应时间;然而，它显著地影响冷。这是因为路由之间共享的顶点更少，导致更多的SSD行程来获取流量数据，并且需要更长的向前探测阶段。另一方面，温暖的响应时间似乎受到间隔数量的影响最大——请求672个间隔显然比两者都请求96个间隔要昂贵得多冷而且温暖的，但温暖的整个星期的响应时间几乎相当于冷。最后，矩阵大小的变化如预期的那样影响性能——所有的实验都是单线程运行的，因此单源矩阵(例如，1 x 10)和多源矩阵(例如，10 x 10)之间存在线性关系;这是最明显的温暖的响应时间(例如，分别为0.03和0.3 s)。

3.2.路线优化

MIO配备了流量矩阵，为各种不同的路由场景和目标找到有效的解决方案。它的核心是安排特工访问一系列地点。每个地点最多访问一次，最多由一个代理访问，除非该地点是一个仓库或支持取/送货物。每个地点的停留时间都是给定的，必须在该地点指定的时间窗口内完成。代理可以提前到达，但必须等到时间窗口后才开始服务。车辆从仓库运送货物或从取货地点移动物品时，其容量可能有限。目前假设项目不能被分割，也不能通过中间位置转移到其他代理或路由。我们默认的目标是根据优先级最大化访问地点的数量，同时最小化代理的总旅行时间。

MIO算法方法。自适应大邻域搜索(ALNS)是一种流行的元启发式算法，已被用于许多优化问题，特别是车辆路径问题。ALNS使用模拟退火框架，在每次迭代时进行局部搜索，根据之前的迭代调整其行为。通过随机选择一对销毁/修复操作(从预定义的集合中)来控制这个本地搜索。然后，从一个可行解开始，破坏“局部搜索”修改该解，使其可能变为不可行的解。修复操作然后在保证可行性的前提下改变解决方案。如果新的解决方案比以前的更好，那么选择这些破坏/修复操作的概率将会增加。这是ALNS的自适应学习组件。我们的实现遵循Pisinger和Ropke中概述的类似方法，²¹此外，我们支持并行处理和多目标(通过自动加权方案)。请参阅算法1，了解该方法的高级概述。当达到最低温度(即我们确信我们探索了足够的搜索空间且解没有改变)或达到由代理和位置函数给出的固定超时时，满足ALNS的终止条件。在这个过程的最后，我们对我们的解决方案应用k-opt交换后优化步骤，最后尝试提高其质量。

高效计算的最重要组成部分是破坏和修复操作符的设计。这些指导了局部搜索，并试图利用组合优化问题的结构。必须考虑一个谨慎的平衡——快速迭代和明智决策之间的权衡。在这里，我们列出了我们的操作符集，并简要描述了它们的意图。

破坏的方法跳转:删除到达下一个地点的成本大于直接从前一个地点出发的访问;高成本:删除最“昂贵”(例如，就旅行距离而言)的地点;REPLACE ITEM:删除一个位置并用另一个合适的位置替换它;邻域:选择一个随机位置，然后删除它邻域中的位置;转移:删除其他代理行程中成本较低的地点。

修复方法EARLY:倾向于插入靠近代理调度开始的随机位置;LATE:倾向于插入靠近代理时间表末尾的随机位置;NN:使用最近邻启发式插入位置;greedy:使用greedy算法插入位置。

算法1:高级ALNS算法

3.3.云部署和工程

MIO作为云服务的设计必须考虑托管成本和资源使用。为了快速访问，必须将大量数据存储在内存中(集线器标签和CH图~200GB)和SSD上(流量数据~5TB)，可能需要许多底层虚拟机(vm)来支持大量请求。一个简单的实现将由一个VM角色组成，该角色承载整个服务，其中VM的数量可以根据请求量进行伸缩。但是，我们可以利用我们的服务的特殊结构来获得一个资源效率更高的体系结构。从操作的角度来看，我们有三个不同的组件来支持本节前面描述的所有算法:

1. 距离矩阵需要大量内存来驻留集线器标签。
2. 流量矩阵存储CH图只需要很少的内存。但是，该组件是CPU密集型的，需要大量的SSD存储用于流量数据。
3. 路线优化不在内存中持久化任何数据;计算本身是CPU密集型的。

因此，MIO系统包括三个不同的VM角色，每个角色对应上述组件(参见图4对于高级体系结构概述)。角色通过二进制HTTP协议进行通信。每个组件可以根据当前的负载情况单独放大或缩小。具体来说，距离矩阵角色驻留在内存优化的vm上¹；因为我们的设计实现了高吞吐量，我们很少需要扩展这个组件。对于流量矩阵，需要为最大负载条件提供SSD存储。此外，我们使用计算优化的虚拟机¹为其计算;这些虚拟机可以快速扩展，降低运营成本。类似地，路由优化角色也驻留在计算优化的vm上，这些vm可以根据需要进行伸缩。显然，单一VM角色的替代实现无法实现这种级别的灵活性和效率—任何扩展都可能导致至少在一个维度上的资源浪费。

图4。系统架构。路径优化既可以以交通矩阵输入，也可以以距离矩阵输入。

为了实现上述功能，每个角色由以下部分组成:

1. 基于自定义性能计数器的动态伸缩虚拟机集;计数器根据特定角色的需要进行调优。
2. 一个Azure负载均衡器，它将请求分发到VM规模集。
3. 一个Azure流量管理器，处理向最近的数据中心分发请求，以及故障转移管理，以防停机。

我们通过简要描述MIO接口来结束本节。有些应用程序需要计算延迟很小的小计划。尽管其他应用程序有更大的问题和更宽松的时间框架，但它们希望在显示优化的进度条的同时在后台运行服务。为了解决这些不同的需求，我们设计了带有同步和异步接口的MIO(即，分别针对前者和后者的应用程序)。同步接口接收优化请求并使用优化的行程进行响应，而异步接口返回回调id并调度要在后台执行的作业。Azure队列用于编排服务端后台作业的执行，生成的行程保存在Azure存储中。当客户机使用回调id轮询作业完成时，MIO检查优化结果是否存在于Azure存储中，如果存在，则将输出发送回应用程序。

回到顶部

4.实验结果

4.1.实验设置

为了评估与最先进的启发式相比，MIO的流量和性能的影响，我们进行了大规模的计算研究。特别是，我们使用公开可用的实例⁷在最近的微软研究项目中定义¹⁷．这些实例被设计用来真实地模拟服务时间不确定的技术人员路由和调度问题。1440个实例使用真实的位置，包括从我们的服务中获得的简化的流量矩阵。它们覆盖了一系列不同的规模，有多个代理，有不同的轮班开始时间。

为了公平地比较我们的算法，我们使用服务持续时间的期望值，并忽略在使用最大旅行时间时不可能访问所有路径点的实例。因此，我们的优化目标是访问所有的路径点，同时最小化旅行时间。如果一个算法不能保证满足时间窗口(例如，代理到达一个路径点)，我们会优先考虑最小化迟到，而不是最小化旅行时间。

我们将流量不可知和流量感知的MIO变体与基于Lin-Kernighan的启发式方法进行比较。这些启发式是专门设计来快速找到对称tsp的高质量解决方案的。在我们的实验中，我们使用LKH v3.0.6，¹⁵对Lin-Kernighan的最新扩展，支持非对称tsp的约束优化。LKH被设计用于优化许多不同的VRP场景，并在难以置信的大规模实例中取得了巨大成功。

我们将LKH配置为具有时间窗口的有能力车辆路径问题(CVRPTW)，它还支持在位置上的停留时间。需求被设定为零。在计算交通的真实成本时，使用成对地点之间的最大旅行时间来避免时间窗惩罚。我们使用了默认的参数，加上了“SPECIAL”，我们发现排除了这个参数，一些实例的计算时间增加了超过1500倍，而解决方案的质量几乎没有差别。

所有的实验都运行在Azure Standard DS14v2虚拟机实例上，该实例有16个核和120GB RAM。虽然MIO可以利用多个核，但我们将所有算法限制在一个线程上，以便进行公平的比较。相同算法的实验在同一个VM实例上并行运行(即，最多16个实验同时运行)，以获得更快的吞吐量。

4.2.实验设计

在我们的实验中，我们希望检验合并流量的意义。为此，我们在标准模式下运行带有交通预测(MIO)的MIO，并将结果与用静态旅行时间替换交通预测的设置进行比较。特别是，我们在两种流量不可知设置下执行MIO:

• 最短时间:地点间最短时间(即无交通)
• MAX:两地之间的最长时间(即一周内的交通高峰)

我们注意到，使用最小行程，如MIN，历来是最常用的方法，因为自由流动的旅行时间可以仅使用距离和强制的速度限制来精确估计，而不需要大量的交通数据(见第3.1.1节)。如前所述，我们将不同的MIO变体与LKH算法进行比较，使用最大位置间旅行(LKH)。

通过我们的实验设计，可以访问所有在各自时间窗口内的路径点;然而，流量不可知的解决方案可能导致调度一个违反其时间窗口的路径点。也就是说，当重新引入实际的旅行时间(捕获预测的交通流量)时，代理将会迟到。当发生这样的违规行为时，我们记录代理的迟到情况，并增加违规次数。更具体地说，MAX和MIO不违反任何时间窗口(即，代理从不迟到)，而MIN和LKH可能。预计MIN会违反时间窗口，因为它不知道极端的交通状况。LKH似乎将时间窗口视为软约束;因此，虽然我们将算法配置为按优先顺序准时到达，但还是会有一些延迟。

4.3.结果

我们的研究结果的摘要载于图5；中提供了按实例大小划分的细分表2而且图6．所有的结果都按照实例中的路点数量进行了规范化，也就是说，它们表示每个路点的平均成本。例如,图5意味着每增加一个路点，MIO需要额外17.1分钟的旅行时间，并需要额外201 ms的运行时间来解决(平均)。这允许对不同大小的实例进行公平的比较。特别是,图6强调使用相同地理区域的大型实例的“规模经济”——每个航路点的旅行成本随着航路点的数量而减少，这是预期的，因为代理需要在地点之间旅行更少。

表2。每个访问路径点的结果比较。

图5。比较算法在每个访问路径点的平均旅行时间和迟到情况。

图6。算法的比较，每个访问的路径点的结果平均。

从结果中可以看出，MAX在每个路径点上需要比MIO多6%以上的行程，其中包含了交通。尽管如此，MAX的平均运行时间是所有算法中最快的。这是由于静态旅行时间的超快缓存命中;也就是说，MAX在查找时间时不需要二进制搜索;此外，使用最大行程会导致可供算法评估的有效路径更少。在实践中，不建议在严格的时间窗口限制下使用最大旅行时间，因为路径点可能永远不会被安排，因为它们“看起来”不可能在时间窗口内到达。相比之下，MIN在不知不觉中因为迟到而耽误了旅行时间。因此，它的旅行时间平均比MIO少1%，但它的旅行和迟到的总和几乎多15%。

最后，我们将我们的结果与LKH进行比较。对于较小的实例，LKH的速度非常快，平均比我们的MIO变体快17倍以上——但这在规模上发生了变化，MIO几乎比LKH快2倍。不幸的是，LKH似乎很难找到高质量的解决方案。由于LKH使用最大旅行时间，我们预计结果与MAX相似;然而，LKH产生的时间表似乎有明显更大的延迟。旅行和迟到的总和比MIO高72%以上，也就是说，几乎是平均水平的2倍。仔细检查我们的配置和公开的LKH代码表明，这种低质量解决方案的特殊问题是LKH算法的系统性问题。虽然我们不能确定他们的方法有什么不正确的地方，但我们没有进行全面的分析，以确定这些问题是Lin-Kernighan方法固有的，还是LKH添加的扩展所固有的。

回到顶部

5.相关工作

大多数关于车辆路径问题(VRP)的文献都假设地点之间的旅行时间作为输入。²³通常，这些问题有固定的位置集(例如，可以缓存距离矩阵)，但通常，优化VRP的工作非常复杂，因此通常会忽略最短路径旅行时间的计算。相比之下，我们不仅关注路线优化，还关注出行时间的高效计算。我们的系统提供完整的端到端服务，支持全球任何地方的路径点，旨在在非常短的时间内提供高质量的解决方案。在我们的服务中，我们实现了必要的位置之间的距离和交通计算，这在算法上是非平凡的。

5.1.相关商业产品

企业提供相关的云服务，如用于现场服务(资源调度优化)的Microsoft Dynamics 365，⁴路由引擎，⁵地图方向，^3.和TomTom路由。⁶这类商业产品通常不披露算法的全部细节，或使用一些算法组件作为黑匣子(例如，旅行时间计算)。据我们所知，本文是第一篇报道端到端云服务的完整算法细节的文章，该服务支持多个代理的流量感知行程。

5.2.与时间相关的最短路径

关于依赖时间的最短路径算法的查询加速技术的概述，我们参考Delling和Wagner。¹⁰Geisberger中描述了一种类似于我们的流量矩阵算法的方法¹²他还使用了收缩层次结构和改进的Dijkstra算法来计算单个原点和多个目的地之间与时间有关的最短旅行。

5.3.车辆路径问题(VRP)

MIO最初是为解决技术人员路由和调度问题(TRSP)而设计的，TRSP是VRP的变体。TRSP在VRP上的主要扩展是每个地点的停留时间，每个代理的停留时间可能不同(即基于技能/经验)。从我们的第一个设计开始，MIO就得到了扩展，包括额外的VRP功能，例如车辆容量、取货和配送、多个仓库等等。ALNS方法最初是由Pisinger和Ropke介绍的²¹作为求解vrp的通用方法，已经在许多论文中被用于求解TRSP。^16，20.

回到顶部

6.结论

在本文中，我们描述了多行程优化(MIO)——一种全球公开的必应地图服务。MIO获取代理和具有各种需求的所需路径点的列表，并为每个代理输出有效的时间表和路由。MIO包含多种算法，例如用于旅行时间计算的最短路径机制和用于路线优化的精心设计的启发式算法。重要的是，我们的算法考虑到了交通预测，对城市地区有重大影响。我们的实验表明，MIO实现了高效的解决方案和快速的性能——它产生了大规模的高质量调度，运行时间比最先进的启发式(LKH)方法更好。我们认为MIO是一种有吸引力的工具，可以用于自动化许多企业和组织的相关物流操作。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.

---

没有找到条目