允中 發自 凹非寺量子位 | 公眾號 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的剪枝思路，引入多個昇騰算子實現了帶約束的組合能力?；贜PU算力，SPP的求解相比傳統求解器方法，求解速度提升60+倍。該技術可以快速求解得到最優解，更高性能搜索高質量solution。最終效果該研究團隊在公開數據集（由 Sartori 和 Buriol 于 2020 年提出，基于實際工業場景的數據集）上對所提出的技術進行了全面的實驗驗證。實驗結果顯示，這一方法在多個算例中實現了顯著的性能提升，共刷新了榜單中的57項世界紀錄，在部分算例上相對于基準結果改進幅度達6%。榜單鏈接：https://github.com/cssartori/pdptw-instances/tree/master/solutions—完—投稿請發郵件到：ai@qbitai.com標題注明【投稿】，告訴我們：你是誰，從哪來，投稿內容?附上論文/項目主頁鏈接，以及聯系方式哦我們會（盡量）及時回復你點這里?關注我，記得標星哦～一鍵三連「分享」、「點贊」和「在看」科技前沿進展日日相見 ~