基于昇腾算力的矩阵运算更动求解器框架，大幅晋升 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
标题注明【投稿】，告诉咱们：
你是谁，从哪来，投稿内容
附上论文 / 名堂主页伙同，以及关系方法哦
咱们会（尽量）实时回话你
点这里� � 关爱我，难忘标星哦～
一键三连「共享」、「点赞」和「在看」
科技前沿施展日日相逢 ~