基于升腾计算力的矩阵运算改进了求解器框架

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

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

结果刷新了Sartorii&Burial 在PDPTW列表中57项世界纪录，与基准结果相比，求解器框部分算例的基于计算矩阵架改进幅度为6%，继英伟达cuopt刷新Li&Lim 基于NPU/GPU计算能力AI的升腾另一项技术突破，在23项基准记录后。运算

其中，改进以升腾加速为基础，求解器框最快可加速100倍，基于计算矩阵架在大幅提升搜索范围的升腾同时，保证性能不受影响。运算

矩阵化改进了传统的改进解框架

带时间窗的提货和配送问题（PDPTW）是路径优化的问题（VRP）在供应链、物流、求解器框网络规划调度等领域，重要变体是一种非常经典的强组合优化问题。

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

PDPTW的复杂性主要来自于极大的解决空间和时间窗限制&提货配对约束&容量限制等约束交织在一起，很难用精确的算法解决大问题。在目前的学习/行业中，一种经典标杆是memetic&LNS集成求解技术的算法框架如下：

Memetic&LNS可以在许多组合优化问题上取得良好的平均效果，然后如何有效地跳出Local Optimum仍然是这种算法的主要局限性。在搜索过程的早期阶段，它可能会达到一个相对较好的解决方案。随后的搜索过程停滞不前，无法进一步改进，并收敛到当地最佳。

研究团队设计并实现了一种创新的技术框架，以解决这一问题。

首先，调整传统的求解架构，在生成路径时采取更广泛的搜索策略，提高跳出Local Optimum概率；

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

NPU加速可行性和目标函数评估，大大提高了路径探索能力

研究团队提出的最新算法框架是专门为高耗时路径和解评估设计的创新技术。其核心理念是将传统的可行性和成本评估转化为矩阵运算，并调用升腾NPU算子，从而实现路径和解的高效评估，如下图所示，并将其转化为、矩阵化的属性，如距离和时间。

距离评估：

Capacity约束的违反评估

评估时间窗限制的违反程度

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

引入SPP子模型，NPU加速搜索高质量路径组合，提高每一代Solution的质量

为了更好地提高每一代solution的质量，该研究团队设计了一种高效的面向集合分子模型（Set Partitioning Problem, SPP），搜索路径组合，提高子代Solution的质量，将传统SPP的解决过程转化为矩阵操作，利用NPU强大的计算能力实现显著的加速效果，提高每一代迭代效率，以下是算法的核心理念：

对于上述矩阵组合操作，该团队将该问题的属性建立为0、1矩阵，其中0表示节点不在路径上，1表示点在路径上，如下图所示，

在此过程中，还参考了分支定界算法中基于bound的修剪思路，引入了多个升腾算子，实现了带约束的组合能力。

与传统的求解器方法相比，基于NPU计算能力，SPP的求解速度提高了60 倍。该技术可快速求解，获得最优解，更高性能搜索高质量solution。

最终效果

研究小组公开数据集（由 Sartori 和 Buriol 于 2020 基于实际工业场景的年度数据集)对提出的技术进行了全面的实验验证。实验结果表明，该方法在许多例子中实现了显著的性能改进，共刷新了列表中的57项世界纪录。在一些例子中，与基准结果相比，改进幅度为6%。

榜单链接： https://github.com/cssartori/pdptw-instances/tree/master/solutions