简介#

NVIDIA cuOpt 是一款 GPU 加速的组合和线性优化引擎，用于解决复杂的路径优化问题，例如车辆路径规划和大型线性规划。典型的问题领域包括 旅行商问题 (TSP)、车辆路径规划问题 (VRP)、取货和交付问题 (PDP)、线性规划 (LP) 和 混合整数线性规划 (MILP)。

注意

线性规划 (LP) 和混合整数线性规划 (MILP) 是早期访问功能，目前仅对部分客户开放。

通过使用加速计算，NVIDIA® cuOpt 通过支持更好、更快的决策来优化运营研究和物流。传统的基于 CPU 的求解器在历史上让生态系统中的许多人感到沮丧，因为 CPU 求解器存在不准确和漫长的等待时间。

NVIDIA cuOpt 提供并行启发式算法的高级使用，并支持这些基本问题的多种变体，例如在车辆容量、交货时间窗口以及车辆驾驶员在工作日的轮班和休息期间添加约束。

_images/cuopt_feature_diag.jpg

作为 NVIDIA AI Enterprise 的一部分，NVIDIA cuOpt 提供了一种安全、高效的方式来快速生成世界一流的路线优化解决方案。使用单个优化的容器，您可以在 5 分钟内在云、数据中心、工作站或 PC 中加速的 NVIDIA GPU 系统上部署 AI 微服务。需要 NVIDIA AI Enterprise 许可证或 NVIDIA 开发者计划会员资格。或者，您可以使用 NVIDIA API 目录中的托管 API 终端节点，新用户可以免费获得前 5000 个 API 请求。许可用户根据其实例使用量付费。

注意

查看此常见问题解答，了解有关 NVIDIA 开发者计划的更多信息。

路径规划（TSP、VRP 和 PDP）#

车辆路径规划问题 (VRP) 和 取货和交付问题 (PDP) 源自旅行商问题 (TSP)，后者是运筹学以及更广泛的计算机科学中研究最多的问题之一。

TSP 提出以下问题

  • 给定一个目的地列表和每对目的地之间距离的矩阵，访问每个目的地恰好一次并返回原始位置的最短可能路线是什么？

例如，TSP 在规划和物流中有多种应用，在货物运输和交付中，一个好的解决方案可以节省大量的旅行时间和燃料成本。VRP 和 PDP 本质上是 TSP 的扩展，具有额外的复杂性。

VRP 将 TSP 推广为求解一组车队的最佳路线，以便向给定的客户群交付货物。PDP 增加了两种不同类型服务的可能性，即取货或交付，而在 VRP 中，所有客户都需要在客户位置执行相同的服务。

cuOpt 路径规划如何解决问题#

cuOpt 首先生成初始解决方案种群，然后迭代改进种群，直到达到时间限制，并从种群中选择最佳解决方案。

启发式算法的必要性#

考虑到暴力枚举所需的时间和计算资源，获得精确的最优解根本不现实。然而，存在经过充分研究的启发式算法，可以在合理的时间内为非常大的问题产生接近最优的解，而 NVIDIA cuOpt 专注于使用这些启发式算法。

线性规划 (LP)#

线性规划是一种关于如何在给定一组线性等式和不等式约束的情况下优化线性目标函数的技术。例如，请观察以下内容。

给定系统约束

2x + 4 y >= 230

3x + 2y < 190

x >= 0

y >= 0,

最大化目标函数

f(x) = 5x + 3y

注意

线性规划 (LP) 和混合整数线性规划 (MILP) 是早期访问功能，目前仅对部分客户开放。

cuOpt LP 如何解决问题：#

cuOpt LP 求解器基于 PDLP，一种新的用于大规模求解 LP 的一阶方法 (FOM)。它实现了一种梯度下降，通过启发式算法增强，并通过利用最新的 NVIDIA GPU 高效地执行大规模并行操作。

混合整数线性规划 (MILP)#

混合整数线性规划是线性规划的一个版本，其中一些变量被约束为整数，而另一些变量可以是非整数。NVIDIA cuOpt 生成启发式解决方案并耗尽用户给定的所有时间限制。

给定系统约束

2x + 4 y >= 230

3x + 2y < 190

x >= 0 且 x 是整数

y >= 0 且 y 是浮点数，

最大化目标函数

f(x) = 5x + 3y

即使问题看起来与之前的类似，但这个问题是完全不同的。

GPU 释放大规模并行计算能力#

凭借其利用数千个并行核心的能力，GPU 是加速大规模可并行化问题的理想计算平台，在这些问题中，数千或数百万个单独的任务需要并行计算。这使得在运行此类问题的启发式算法时能够实现数量级的加速，从而降低运营成本并提高解决方案的准确性。

在本页中