基于昇腾算力的矩阵运算纠正求解器框架开yun体育网，大幅升迁 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

—  完  —

投稿请发邮件到：

ai@qbitai.com

标题注明【投稿】，告诉咱们：

你是谁，从哪来，投稿内容‍

附上论文 / 名目主页蚁合，以及关系方法哦

咱们会（尽量）实时恢复你

点这里� � 善良我，铭刻标星哦～

一键三连「共享」、「点赞」和「在看」

科技前沿施展日日再会 ~