基于昇腾算力突破AI求解，最高加速100倍！| 华为GTS&深圳市大数据研究院

允中 发自 凹非寺量子位 | 公众号 QbitAI基于昇腾算力的矩阵运算改进求解器框架，大幅提升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标题注明【投稿】，告诉我们：你是谁，从哪来，投稿内容‍附上论/项目主页链接，以及联系方式哦我们会（尽量）及时回复你点这里👇关注我，记得标星哦～一键三连「分享」、「点赞」和「在看」科技前沿进展日日相见 ~