• <xmp id="om0om">
  • <table id="om0om"><noscript id="om0om"></noscript></table>
  • 數據科學

    突破性的 NVIDIA cuOpt 算法將路線優化解決方案的速度提高 100 倍

    NVIDIA cuOpt 是一個加速優化引擎,專為解決復雜的路線規劃問題而設計。它能夠高效地處理各種問題,包括但不限于:休息和等待時間、車輛的多個成本和時間矩陣、多目標優化、訂單與車輛的匹配、車輛的起始和結束位置、以及車輛的起始和結束時間等。

    更具體地說,cuOpt 解決了兩個問題的多個變體:時間窗口容量車輛路線規劃問題 (CVRPTW) 和時間窗口拾貨和交付問題 (PDPTW).這些問題的目的是滿足客戶請求,同時盡可能減少車輛數量和按相應順序行駛的總距離。

    cuOpt 在過去三年中設定的最大路由基準測試中打破了 23 項世界紀錄,由 SINTEF 進行。

    本文將探討優化算法的關鍵要素及其定義,以及將 NVIDIA cuOpt 與該領域的領先解決方案進行基準測試的過程,并重點介紹這些比較的重要性。在整篇博文中,我們將術語“請求”用于 CVRPTW 的訂單,以及用于 PDPTW 問題的取貨 – 配送訂單對。

    盡管該領域存在各種限制和問題維度,但本文的范圍僅限于容量和時間窗口限制。容量限制要求執行車輛隨時的商品總量不得超過車輛容量。時間窗口限制強制要求在不早于時間窗口開始時間且不晚于時間窗口結束時間的情況下執行訂單。

    組合優化

    組合優化問題是世界上計算成本最高的問題之一 (NP-hard),搜索空間中的可能狀態數量是因乘問題。由于無法對大型問題使用精確算法,因此使用啟發式算法將解決方案近似于優化點。啟發式算法使用各種計算成本高昂且具有二次或更高計算復雜性的算法來探索搜索空間。

    由于問題的復雜性和本質,我們可以使用大規模并行 GPU 加速這些算法。得益于 GPU 加速,我們可以在合理的時間內獲得接近最佳的解決方案。

    構建進化路線優化算法

    典型的路由求解器包含兩個階段:生成初始解決方案和改進解決方案。本節介紹生成初始解決方案和改進這些解決方案的步驟。

    初始解決方案生成算法

    找到一組滿足所有限制條件的有限機群來生成可行的初始解決方案本身就是一個 NP 難題。我們的團隊已經改進并并行化了 引導式彈射搜索 (GES) 算法,用于向路由發出請求。

    GES 的主要理念很簡單。我們首先嘗試將請求插入路由。如果無法插入該請求,我們會從路由中彈出一個或多個易于插入的請求,并將請求插入到已放松的路由。每個請求的懲罰分數 (p-score) 表示將該請求插入路由的難度。僅當被彈出請求的 p-score 的總和小于所考慮的請求時,算法才會插入請求。

    每次無法將請求插入路由 (即使是彈射) 時,我們都會增加該請求的 p 分數,然后重試。我們會將所有未服務的請求保留在彈射池中,然后算法運行,直到彈射池變為空。換言之,它一直運行,直到所有請求都得到服務。

    此算法的主要缺點是循環 (返回到解決方案中的前一組節點)、在彈射節點數量較多時查找彈射組合的速度較慢,以及僅考慮弱的隨機微擾解決方案。我們已經消除了這些倒退,這使我們能夠生成比當前先進方法更少路線數量的解決方案。

    在探討彈射算法之前,了解可行性檢查和解決方案評估使用時間扭曲方法至關重要。這種方法顯著縮短了計算時間,但也增加了并行化的難度,因為需要遵守搜索任意數量的彈射的字典順序。

    找到要彈出的請求以及在何處插入所考慮的請求是一個計算成本高昂的問題:它相對于彈出請求的數量呈指數級增長,并且需要檢查所有路由中的所有插入位置。我們的實驗表明,少量彈出會導致算法的循環。

    因此,我們提出了一種方法,該方法可在執行廣泛搜索時并行彈出多達 10 個請求 (啟發式) 和 5 個請求。我們通過從每個路由中彈出片段并在線程塊中處理這些臨時路由來并行處理彈出算法。然后,我們嘗試并行將考慮的請求插入所有可能的位置。

    深度搜索算法嘗試對路由中所有請求的彈射進行所有可能的排列。我們為每個請求插入位置使用不同的線程塊,并通過將詞匯表順序拆分為獨立的子排列來并行執行詞匯表搜索。

    GES 算法循環直到我們用完時間限制或請求池為空。在每次迭代中,我們都會對解決方案進行微擾,以改進解決方案狀態并打開解決方案中的差距,以便找到可行的插入。微擾是一種隨機本地搜索,它隨機重新定位并交換路線之間和路線內的節點。

    在找到滿足要求的最佳車輛數量后,我們將切換到負責最小化目標的改進階段。默認情況下,這是總行駛距離,但可以在 cuOpt 中配置其他目標。

    The figure shows an algorithm flowchart that explains the GES procedure in cuOpt. After the start, the arrow goes to “Randomly remove a route” then the algorithm inserts nodes from this randomly removed route. If the limit is not reached or the algorithm reached the sufficient number of routes, it goes back to the step “Randomly remove a route”. Otherwise,the algorithm exists.
    圖 1.顯示 NVIDIA cuOpt 中 GES 算法的流程圖

    進化過程和局部搜索算法

    改進階段適用于多個解決方案,并使用進化策略對其進行改進。生成的解決方案放在一個群體中。為了達到足夠多樣化的初始解決方案,我們在生成過程中使用隨機化。利用 GPU 架構,我們并行生成了許多不同的解決方案。多樣化的群體經歷了一個進化改進過程,將解決方案的最佳屬性保留在新一代中。

    在進化過程的單個步驟中,我們采用兩個隨機解決方案并應用交叉運算符。這將生成一個子代解決方案,該解決方案繼承了父母雙方的良好屬性。可以對解決方案應用不同的交叉運算符,其中一些操作會使子代處于不完整狀態。我們通過彈出重復節點、插入未路由節點或對其執行不可行的本地搜索來修復解決方案。

    例如,基于順序的交叉運算符根據節點在另一父解決方案中的出現順序,對一個父解決方案的一條或多條路由中的節點進行重新排序。生成的子代會保留一個父解決方案的分組屬性和另一個解決方案的排序屬性。然而,這種運算符的結果可能是一個在時間和容量限制方面不可行的完整解決方案。cuOpt 包含多個在解決方案上隨機執行的交叉運算符。

    在這種情況下,分頻后的局部搜索階段在減少或消除不可行性或改善總目標或行駛距離方面發揮著關鍵作用。局部搜索的目標權重由需要優化的重要內容決定。提高不可行性權重有助于將解決方案返回到可行區域,而大多數問題通常都是如此。

    局部搜索為子代解決方案找到一個局部最小值,然后由后者參與進一步的進化步驟。擁有快速的局部搜索至關重要,因為這是決定在時間預算內可以進行多少次改進迭代的主要因素。我們使用快速、近似和大型鄰域搜索算法來找到性能出色的局部最小值。我們沒有像傳統方法那樣執行固定大小的鄰域局部搜索,而是設計了一個“網絡”,可以快速捕獲簡單的改進,并在達到停滯時捕獲非常深入的運算符。

    快速運算符可以快速探索小區域,而近似運算符可以在每次應用時評估不同的移動。這一點尤為重要,因為分頻經常會使部分路線保持不變。大型運算符在移動鏈中移動請求,以路線之間的移動周期表示,正如在 用于查找圖中負子集不相交周期的 GPU 并行算法 中所述。

    循環運算符探索一個非常大的社區,無法使用簡單的運算符進行探索。這僅僅是因為這些約束禁止這些簡單的運算符通過搜索空間中的一些小山。此工作流允許經常使用快速運算符,而更頻繁地使用計算成本較高的深度運算符。

    GPU 并行化是通過將每個假設的路由映射到線程塊來完成的。這允許使用共享內存來存儲與路由相關的數據,這在搜索移動時是暫時的。臨時路由或者是原始路由的副本,或者是彈出一個或多個請求的版本。線程塊中的線程嘗試將所有可能的請求從其他路由插入到臨時路由中的所有位置。

    在查找并記錄所有移動后,我們通過求和每個路線對的插入/彈射成本增量來找到每個路線對的最佳移動。成本增量由目標權重計算,其中也包含不可行懲罰權重。如果多個此類移動在其修改的路線方面相互排除,則我們會執行多個此類移動。

    The figure shows an algorithm flowchart that explains the local search procedure in cuOpt. There are three steps, the first step is Parallel Fast Local Search Engine, the second step is the Parallel Approximate Local Search Engine, and the third step is Parallel Fast Very Large Neighborhood Search Engine. The procedure loops following each step.
    圖 2. NVIDIA cuOpt 中本地搜索程序的流程圖

    cuOpt 基準測試

    我們持續致力于提升 cuOpt 的性能和質量。為了評估質量,我們已針對研究最深入的基準,將求解器與最知名的解決方案進行了比較,包括針對 CVRPTW 的 Gehring&Homberger 以及針對 PDPTW 的 Li&Lim。在實際應用中,求解器能夠以多快的速度找到所需的解決方案,對于企業來說至關重要。

    評估標準和目標

    • 精度的定義是,在目標方面,找到的解決方案與已知的最佳解決方案 (BKS) 之間的百分比差距。問題規范將第一個目標指定為車輛數量,將第二個目標指定為行駛距離。
    • 解決方案測量時間表示達到 BKS 或期望目標結果的特定差距所需的時間。解決方案時間是實際用例中最重要的標準之一。在時間預算內達成高精度解決方案非常重要。組合優化算法需要大量時間。

    圖 3 和圖 4 顯示了求解器在一組大型基準實例上的收行為。

    The chart represents the convergence behavior of cuOpt on a randomly selected thousand task instances of Gehring & Homberger benchmark. The green line represents cuOpt solution quality over time and it has a steep down movement in the first 10 mins, then slowly converges towards the horizontal blue line which represents BKS. The green line approaches the blue line with a very small gap.
    圖 3.cuOpt 對 CVRPTW 問題的收行為

    我們從每個類別 (C1_10_1,C2_10_1,R1_10_1,R2_10_1,RC1_10_1,RC2_10_1) 中選擇了一個實例,以顯示求解器的整體行為,具體取決于 (集群、隨機) 和 (長路徑、短路徑) 實例。我們將每分鐘采樣的聚合求和與聚合 BKS 進行比較。

    開始時的急劇收會隨著時間的推移逐漸接近 BKS 聚合。對于這些實例集,我們能夠匹配 BKS 的車輛總數。cuOpt 求解器可以在 Gehring 和 Homberger 實例的幾乎所有實例中找到 BKS 車輛數量。但是,與改進階段相比,實際性能取決于生成初始解決方案所花費的時間。

    雖然求解器在較大的實例上能夠快速收,但在較小的實例上,求解器的收速度卻快了幾個數量級。在下表中,我們展示了針對各種問題規模達到 BKS 所需的時間,同時實現了與 BKS 相同的車輛數量。

    This chart represents a time to a certain solution quality measure for a different number of tasks on a PDPTW problem. The bar chart shows increasing values for different numbers of tasks. There are three different bars representing the gap to the BKS for 1%, 2%, and 5%. Reaching 1% takes longer in larger instances, but for smaller instances reaching 1%, 2%, and 5% take the same time. For 1,000 tasks, it takes around 300 seconds to reach 1%, 200 seconds to reach 2%, and 120 seconds to reach 5% gap to BKS.
    圖 4.找到適用于 PDPTW 問題的特定解決方案的時間

    cuOpt 創造 23 項世界紀錄

    借助 GPU 加速啟發式算法的新方法和先進的進化策略,cuOpt 打破了 Gehring&Homberger 基準測試中 15 個實例和 Li&Lim 基準測試中 8 個實例的記錄。

    現在, NVIDIA 保留了過去三年 CVRPTW 和 PDPTW 類別的所有記錄。

    在圖 5 中,每個邊緣都表示從一個任務到另一個任務的路徑。綠線表示與之前記錄相同的邊緣。兩個解決方案之間的藍色和紅色邊緣不同。得益于進化策略,cuOpt 解決方案在可能解決方案的搜索空間中處于完全不同的位置,這意味著有許多不同的邊緣。

    This image shows one of the records of cuOpt on a Gehring & Homberger instance R1_10_5. It shows two solutions together in the same picture by drawing edges between the task locations. The green edges are the common edges to the previous record,and the blue and the red edges are different edges between two solutions. It is possible to see more than half of the edges are different from the previous record.
    圖 5.cuOpt 世界紀錄與之前記錄的對比路線可視化。來源:Combopt.org

    Gehring&Homberger 與 BKS 的總體平均差距為 -0.0 息%的距離差距和 0.29%的車輛計數差距。Li&Lim 與 BKS 的總體平均差距為 1.2 息%的距離差距和 0.36%的車輛計數差距。基準測試在單個測試中運行了 200 分鐘 NVIDIA H100 GPU

    結束語

    NVIDIA cuOpt 利用 GPU 加速和 NVIDIA 技術(如 RAPIDS),與基于 CPU 的實現相比,我們在本地搜索操作中實現了 100 倍的加速。相比之下,基于 CPU 的求解器需要數小時才能找到類似的解決方案。

    了解詳情和 開始使用 NVIDIA cuOpt。您還可以通過 NVIDIA API 目錄NVIDIA LaunchPad 了解如何 cuOpt 可以幫助您的組織節省時間和資金。

    加入我們參加 NVIDIA GTC 2024 會議,聆聽 NVIDIA 優化 AI 工程經理 Alex Fender 的演講,以優化 AI 領域的進展。此外,您還可以參加 NVIDIA 深度學習培訓中心(DLI)的培訓,了解如何使用我們的路線優化微服務提高效率并節省成本。

    0

    標簽

    人人超碰97caoporen国产