技术简报#

概述#

商业车队行业中最大的挑战之一是路线优化。这在许多行业中都很普遍，在这些行业中，确定最具成本效益的路线可以为餐饮配送带来显著的成本节约，例如，一个单一的连锁餐厅每天可以配送数百万份餐食，或者一家电信公司每年可以派遣数百万个工作任务。在这些大型场景中，低效的路线可能会导致数十亿美元的运营成本，并减少我们的环境碳足迹。计算求解器可以通过找到多个地点之间的最优路线来最大限度地减少这些低效率。如今，基于 CPU 的计算求解器已经可用，但借助 GPU 加速的巨大吞吐量，更具雄心的算法将有助于推动我们的未来。

上述路线优化问题通常被称为旅行商问题 (TSP)。为了缩短开发 GPU 加速 TSP 解决方案的时间，NVIDIA 开发了路线优化 AI 工作流，以简化车辆路径问题 (VRP) 解决方案的开发。

此 NVIDIA AI 工作流包含有关如何部署路线优化的示例性 AI 解决方案的详细信息；其中包括以下项目

起点-目的地成本矩阵创建
数据预处理
NVIDIA cuOpt™ GPU 加速求解器管线
驾驶方向
地图可视化
用于身份验证、日志记录和监控工作流的组件
可作为 Helm Chart 打包的云原生可部署捆绑包

注意

工作流中使用的组件和说明旨在用作集成的示例，并且可能本身并不具备充分的生产就绪性（如所述）。应自定义工作流并将其集成到自己的基础设施中，并将工作流作为参考。

此 AI 工作流涵盖三个不同的 TSP 用例

最后一英里交付 (LMD): 卡车车队从配送中心派遣，向商店交付订单。
取货和交付 (PDP): 卡车车队被派遣，然后通过取货并将其送到不同的地点来完成订单。例如，DoorDash 司机从餐厅取餐并将其送到顾客的家庭住址。
调度优化: 服务提供商被派遣以满足一系列不同的服务请求。这些请求被分配了一定的时间，并且时间可能因请求而异。例如，电信技术人员被分配到客户家中安装路由器，然后到另一个家中安装数据线。

使用上述资产，此 NVIDIA AI 工作流为您提供了一个参考，帮助您以最少的准备工作开始构建自己的 AI 解决方案，并包含企业就绪的实施最佳实践，范围从身份验证、监控、报告和负载均衡，帮助您更快地实现期望的 AI 成果，同时仍然允许您偏离路径。

NVIDIA AI 工作流设计为微服务，这意味着它们可以单独部署在 Kubernetes 上，也可以与其他微服务一起部署，以创建生产就绪的应用程序，以便在您的企业环境中实现无缝扩展。

工作流组件打包在一起成为可部署的解决方案，如下图所示

这些组件用于构建和部署路线优化 cuOpt 微服务，并与下图所示的其他组件集成在一起

有关所用组件的更多信息，请参见路线优化和NVIDIA 云原生服务附加组件包部署指南。

此外，路线优化 AI 工作流描述了如何将 cuOpt Server API 与第三方 API 集成，以进行路线地图绘制和地图可视化。

NVIDIA AI 工作流组件#

NVIDIA 路线优化 AI 工作流通过具象状态传输 (REST) 微服务 API 使用 NVIDIA cuOpt 服务器来生成路线。为此，工作流中包含了一系列示例合成数据集，用于将一组订单分配给配送司机车队。工作流使用三个 csv 文件将司机分配给其相应的订单；订单、仓库和路线。

cuOpt 托管服务#

cuOpt 以前作为 SDK 提供，现在作为云服务提供。客户可以更快地在其路线优化应用程序中采用 cuOpt GPU 加速路线求解器，而无需安装 Python SDK 或自行部署微服务（无论是在本地还是在云端）。由于 cuOpt 托管服务具有内置的身份验证、扩展和其他机制，因此客户可以使用 cuOpt，而无需自行设置。现在，客户可以通过获取凭据和 API 端点来访问客户端。用户可以自行完成数据预处理，将所有数据保存到一个 JSON 文件中，并在一个命令中将此 JSON 文件发送到 cuOpt 求解器。cuOpt 求解器将返回结果，结果可以打印或保存到新的 JSON 文件中以供稍后处理。在获得初始结果后，客户可以使用新数据（例如，已下的新订单或更新的成本矩阵）更新 JSON 文件，并将新的 JSON 文件发送到 cuOpt 以获得重新优化的路线。

示例数据集#

工作流中包含了一系列示例合成数据集，用于将订单分配给配送司机车队。每个用例中使用三个 CSV 文件将司机分配给其相应的订单；订单、仓库和路线。以下段落进一步描述了每个合成数据集，以及它们如何用于每个特定用例。

订单: 订单可以是向客户交付货物、从客户处取货或其他类型的工作。示例包括家具交付、从餐厅取走废油脂或检查访问。在此工作流中，我们关注从配送中心到商店的交付。订单数据集包括商店的数据。这包括商店名称、位置、开始和结束时间（营业时间）、需求（订单重量，单位为磅）和服务时间（卸载包裹所需的时间）。
仓库: 仓库是车辆在其工作日开始时出发并在工作日结束时返回的地点。仓库是车辆装载（用于交付）或卸载（用于取货）的地点。在某些情况下，仓库也可以充当续订地点，车辆可以在此卸载或重新装载并继续执行交付和取货。仓库具有由硬性时间窗口指定的开放和关闭时间。车辆不能在此时限窗口之外到达仓库。在此路线优化工作流中，车辆在早上离开仓库并在一天结束时返回。仓库的信息包括名称、位置以及开始和结束时间（营业时间）。
路线: 路线信息指定车辆和司机的特征，例如车辆容量、工作班次时间和行驶里程，它表示仓库和订单之间的行程。此处需要的功能是车辆名称/ID 号、起始和结束仓库名称、开始和结束时间（车辆/司机班次时间）以及载货能力。

示例 AI 工作流使用这三个 CSV 文件的组合，使用您的数据为您的特定用例找到最具成本效益的路线。例如，在订单 CSV 文件中，指示了包裹重量，而路线 CSV 文件包含具有最大订单重量的送货卡车的路线。路线分配给仓库。

注意

您可能还有其他功能，具体取决于问题，例如订单优先级或车辆休息时间窗口。其他功能的预处理方式与工作流中显示的功能类似。

求解器配置

需要发送到 cuOpt 求解器的最后一部分数据是配置设置。两个主要设置是时间限制和爬山者数量。

时间限制是为找到解决方案分配的最大时间。这取决于用户，用户可以灵活地设置更高的时限以获得更好的结果。爬山者数量是检查解决方案搜索空间的并行代理的数量。

如果用户想要第一个解决方案，那么对于 2000-4000 个爬山者来说，大约 2-3 秒就足够了。

默认情况下，爬山者的数量是通过考虑小型 GPU 的占用率和实验运行时与爬山者数量的权衡（即，在最短时间内获得最佳结果）来选择的。通常，1024 或倍数是一个好的开始。

在某些情况下，例如包裹递送服务，有数千个地点。在这种情况下，路线是在夜间生成的，以便及时生成成本矩阵，并且求解器有足够的时间来获得优化的路线。但是，订单可能会在白天发生变化；可以添加新订单，并且现有订单可能会延迟或丢失。对于如此庞大的问题空间，可以将位置分批提交给 cuOpt。当存在队列时，我们可以给 cuOpt 求解器一个较短的时间限制来重新优化初始路线，从而及时完成更多作业，以便司机可以实时获得这些新路线。

Jupyter Notebook 客户端#

作为工作流的一部分，我们提供了一个 Jupyter Notebook 来执行数据预处理和路线地图绘制步骤。

数据预处理

cuOpt 服务器有一组数据要求，这些要求在预处理阶段处理，包括将数据建模为整数数组并创建成本矩阵。在此路线优化 AI 工作流中，成本矩阵已为您构建，并以 csv 文件的形式提供。成本矩阵表示从一个仓库或订单到另一个仓库或订单的旅行时间。预处理阶段完成后，来自上述三个数据集的数据以及成本矩阵将通过网络发送并导入到 cuOpt 服务器。

请注意，当存在混合车辆车队时，不同的运输类型可能具有不同的旅行时间，可能需要额外的成本矩阵。例如，单个成本矩阵可用于 LMD 用例中的卡车和电动货车，因为这两种车辆类型具有相同的旅行时间。但在 PDP 用例中，当汽车和自行车用于运输交付时，由于这两种车辆类型具有不同的旅行时间，因此需要多个成本矩阵。

下面的成本矩阵示例共有五个位置。成本矩阵将以数据帧的形式如下所示。

上面的成本矩阵表示旅行时间，单位为分钟。与我们的 AI 工作流类似，从位置 0 到位置 1 的旅行时间为 16.546667 分钟。

注意

从一个位置到其自身位置的成本通常为 0，并且从位置 A 到位置 B 的成本不一定等于从位置 B 到位置 A 的成本。

预处理阶段完成后，订单、仓库和路线数据以及成本矩阵将通过 API 调用发送并导入到 cuOpt 服务器。这些调用是使用 Jupyter Notebook 客户端进行的。

路线地图绘制

一旦 cuOpt 求解器返回优化的路线，路线优化 AI 工作流将使用开源路线规划机 (OSRM) API 作为开源路由器，该路由器使用 OpenStreetMap。OSRM 解析 cuOpt 求解器响应，将位置转换为坐标点，然后绘制路线。这些优化的路线本身就包含了每个订单的驾驶方向。

其他组件#

监控

Prometheus 是一个开源监控和警报解决方案。在此工作流中，它存储来自 Triton 的管线性能指标，使系统管理员能够了解系统的健康状况和吞吐量。

虽然指标以纯文本形式提供，但 Grafana 也用于通过仪表板可视化指标。例如，下面显示了一些可用的指标；根据使用情况指标，可以手动或自动扩展 cuOpt Pod。