最高加速100倍，基于升腾算率突破AI求解！

05-17 06:37

基于升腾算力的矩阵运算改进求解器框架，大大提高了求解器框架 Local Optimum 跳出能力。

深圳大数据研究所和华为 GTS 基于矩阵运算的运筹优化实验室联合提出 Memetic&LNS 求解技术。

结果刷新了 Sartori&Burial PDPTW 榜单中的57 项世界纪录，与标准结果相比，有些算例的改进幅度达到了。 6%，是继英伟达 cuOPT 刷新 Li&Lim 23 项目标准记录后，基于 NPU/GPU 算率 AI 另一个解决方案的技术突破。

其中，基于升腾的加速，最快可加速 100 倍，在大幅度提高搜索范围的同时，保证性能不受影响。

矩阵化改善传统的求解框架

带有时间窗口的提货和配送问题（PDPTW）这就是路径优化的问题（VRP）其重要组合，是一种非常经典的强组合优化难题，广泛应用于供应链、物流、网络规划调度等领域。

在这个问题中，每个请求都指定了要运输的货物的大小和两个位置:装载点和卸载点。这类问题的主要目标是最大限度地降低总成本，包括车辆的固定成本和行驶成本，同时确保满足所有客户的需求。

PDPTW 复杂性主要来源于极大的求解时间和空间窗口约束。 & 采用配送匹配约束 & 容量限制等约束交织在一起，这种问题很难用精确的算法来解决大问题，现在学习 / 在行业内，一种经典标杆是 Memetic&LNS 结合求解技术，其算法框架如下：

Memetic&LNS 很多组合优化难题都能得到很好的平均效果，那么怎样才能有效地跳出来？ Local Optimum 这仍然是这种算法的一大局限性。搜索过程的初始阶段可能会达到一个相对较好的解决方案。后续的搜索过程停滞不前，无法进一步改进，收敛到局部最佳。

研究团队设计并实现了一个突破性的技术框架，以解决这个难题。

第一，调整传统的求解结构，在路径产生时采取更广泛的搜索策略，提高跳出率。 Local Optimum 概率；

其次，引入 SPP 提升每一代子模型 solution 质量。同时，路径评价与 SPP 在升降加速的基础上，求解也进行了矩阵化转换，最快可加速 100 倍，在大幅度提高搜索范围的同时，保证性能不受影响，大大提高了跳出。 Local Optimum 的能力。

矩阵可行性和目标函数评定，NPU 加快路径探索能力的极大提高

该研究团队提出的最新算法框架专门为高耗时的路径调解评估制定了创新技术。核心思想是将传统的可行性和成本评估转化为矩阵运算，并调用升腾。 NPU 算法，然后实现路径调解的高效评估，如图所示， solution、属性矩阵化，如距离、时间等。

距离评估：

Capacity 违反程度的约束评估

违反时间窗口约束的评估程度

通过上述技术，可以大大加快传统约束可行性、目标评估等高耗时阶段，部分可以达到。 100 倍加速比，大大提高了道路探索能力。

引入 SPP 子模型，NPU 加快搜索优质路径组合，提升每一代 solution 质量

为更好地提升每一代人？ solution 质量方面，本研究团队设计引入了一种高效的面向集合分子模型（Set Partitioning Problem, SPP），搜索路径组合，改善后代 solution 品质，同时传统 SPP 求解过程转化为矩阵运算，使用 NPU 强大的算率达到了显著的加速效果，以下是算法的核心思想，提高每一代迭代效率：