允中 发自 凹非寺
量子位 | 公众号 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
标题注明【投稿】，告诉我们：
你是谁，从哪来，投稿内容
附上论文/项目主页链接，以及联系方式哦
我们会（尽量）及时回复你
点这里👇关注我，记得标星哦～
