基于昇騰算力的矩陣運算改進求解器框架，大幅提升 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
— 完 —
投稿請發郵件到：
标題注明【投稿】，告訴我們：
你是誰，從哪來，投稿内容
附上論文 / 項目主頁鏈接，以及聯系方式哦
我們會（盡量）及時回複你
點這裏關注我，記得标星哦～
一鍵三連「分享」、「點贊」和「在看」
科技前沿進展日日相見 ~
>
