今天小编分享的科学经验：基于昇腾算力突破AI求解，最高加速100倍！，欢迎阅读。
基于昇腾算力的矩阵运算改进求解器框架，大幅提升 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 的强大算力实现了显著的加速效果，提升每一代迭代效率，下面是算法的核心思路：
为了矩阵化上述的组合操作，该团队将该问题的属性建立成一个 0、1 矩阵，其中 0 表示节点不在该路径上，1 表示点在该路径上，如下图所示，
此过程中还参考分支定界算法中基于 bound 的剪枝思路，引入多个昇腾算子实现了带约束的组合能力。
基于 NPU 算力，SPP 的求解相比传统求解器方法，求解速度提升 60+ 倍。该技术可以快速求解得到最优解，更高性能搜索高质量 solution。
最终效果
该研究团队在公开数据集（由 Sartori 和 Buriol 于 2020 年提出，基于实际工业场景的数据集）上对所提出的技术进行了全面的实验验证。实验结果显示，这一方法在多个算例中实现了显著的性能提升，共刷新了榜单中的 57 项世界纪录，在部分算例上相对于基准结果改进幅度达 6%。
榜单链接： https://github.com/cssartori/pdptw-instances/tree/master/solutions
— 完 —
投稿请发邮件到：
标题注明【投稿】，告诉我们：
你是谁，从哪来，投稿内容
附上论文 / 项目主页链接，以及联系方式哦
我们会（尽量）及时回复你
点这里关注我，记得标星哦～
一键三连「分享」、「点赞」和「在看」
科技前沿进展日日相见 ~
>
