基于昇騰算力的矩陣運算更動求解器框架，大幅晉升 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
標題注明【投稿】，告訴咱們：
你是誰，從哪來，投稿內容?
附上論文 / 名堂主頁伙同，以及關系方法哦
咱們會（盡量）實時回話你
點這里? ? 關愛我，難忘標星哦～
一鍵三連「共享」、「點贊」和「在看」
科技前沿施展日日相逢 ~ ?