NVIDIA cuOpt 是一個用于解決復雜路徑問題的加速優(yōu)化引擎。它能高效解決不同方面的問題，如休息時間、等待時間、多個車輛成本和時間矩陣、多個目標、訂單-車輛匹配、車輛起始和結束位置、車輛起始和結束時間等。

更具體地說，cuOpt 所解決的諸多問題可以歸為兩大類：帶時間窗的擁擠車輛路徑問題（CVRPTW）和帶時間窗的取送貨問題（PDPTW）。這些問題的目標是在滿足客戶要求的同時，最大程度地減少車輛數(shù)量和總行程。

經(jīng) SINTEF 驗證，過去三年中，cuOpt 在最大規(guī)模的路徑基準測試中打破了 23 項世界紀錄。

本文將探討優(yōu)化算法的關鍵要素和定義，以及在基準測試中比較 NVIDIA cuOpt 與該領域領先解決方案的過程，著重說明進行這些比較的重要意義。在本文中，我們使用“請求”一詞表示 CVRPTW 訂單以及 PDPTW 問題中的取貨-交貨訂單對。

盡管該領域存在各種約束和問題維度，但本文的討論范圍僅限于容量和時間窗約束。容量約束要求車輛上的商品總量在任何時候都不能超過車輛容量。時間窗約束則要求服務訂單的時間不能早于時間窗的開始時間，也不能晚于時間窗的結束時間。

組合優(yōu)化

組合優(yōu)化問題是世界上計算成本最高的問題之一（NP-hard），搜索空間中可能狀態(tài)的數(shù)量是階乘的。由于不可能使用精確算法來解決大型問題，因此需要使用啟發(fā)式算法來接近最優(yōu)解決方案。啟發(fā)式算法使用各種算法探索搜索空間，這些算法具有二次方或更高次方的計算復雜度。

高度的復雜性和問題的性質使得使用大規(guī)模并行 GPU 加速這些算法成為可能。借助 GPU 加速，可以在合理的時間內獲得接近最優(yōu)的解決方案。

構建進化路徑優(yōu)化算法

典型的路徑求解器包括兩個階段：生成初始解決方案和改進解決方案。本章將介紹生成初始解決方案和改進解決方案的步驟。

初始解決方案生成算法

利用有限的車隊生成一個可行的初始解決方案并滿足所有約束條件，本身就是一個 NP-hard 問題。我們的團隊對引導彈射搜索（GES）算法進行了改進和并行化，以便將請求放置到路徑上。

GES 的主要想法很簡單。我們首先嘗試將請求插入路徑。如果插入該請求不可行，我們就從路徑中彈出一個或多個易于插入的請求，然后將該請求插入到放寬的路徑中。每個請求的懲罰分數(shù)（p-score）表示將該請求插入路徑的難度。只有當被彈出請求的 p 分數(shù)之和小于所考慮的請求時，算法才會插入該請求。

無法將某個請求插入路徑時，我們就會遞增該請求的 p-score，然后再試一次。我們會將所有未提供服務的請求保留在彈出池中，算法會一直運行到彈出池清空為止。換句話說，它會一直運行到所有請求都被服務為止。

這種算法的主要缺點是循環(huán)（返回到解決方案中的前一組節(jié)點）。當彈射節(jié)點數(shù)量較多時，找到彈射組合的速度較慢。另一個缺點是只考慮弱的、隨機擾動的解決方案。我們已經(jīng)消除了這些缺陷，能夠生成路徑數(shù)量遠低于當前最先進方法的解決方案。

在深入探討彈射算法之前，了解可行性檢查和解決方案評估是在恒定時間內通過時間扭曲法進行的，這點十分重要。雖然這種方法大大縮短了計算時間，但由于需要遵守任意數(shù)量彈射搜索的詞典順序，因此也增加了并行化的難度。

查找哪些請求需要彈出，以及在何處可行地插入所考慮的請求是一個計算成本很高的問題：它與彈出請求的數(shù)量成指數(shù)關系，并且需要檢查所有路徑中的所有插入位置。我們的實驗表明，少量的彈出請求就會引發(fā)算法循環(huán)。

因此，我們提出了一種可以并行彈出多達 10 個請求（啟發(fā)式）和 5 個請求（當進行廣泛搜索時）的方法。我們將彈出算法并行化，從每個路徑中彈出一個片段，并在一個線程塊中處理這些臨時路徑。然后，嘗試在所有可能的位置并行插入所考慮的請求。

深度搜索算法會嘗試彈出路徑中所有請求的所有可能排列。我們將不同的線程塊用于每個請求插入位置，并通過將詞序拆分為獨立的子排列來并行執(zhí)行詞序搜索。

GES 算法循環(huán)運行，直到耗盡時間或請求池為空。在每次迭代中，我們都會對解決方案進行擾動以改進解決方案的狀態(tài)，并打開解決方案中的缺口，從而找到可行的插入方案。擾動是一種在路徑之間和路徑內部隨機遷移和交換節(jié)點的隨機局部搜索。

在找到滿足要求的最佳車輛數(shù)量后，我們轉入改進階段，該階段負責使目標最小化。默認情況下的目標是總行駛距離，但也可以在 cuOpt 中配置其他目標。

圖 1. NVIDIA cuOpt 中的 GES 算法流程圖

進化過程和局部搜索算法

改進階段使用進化策略對多個解決方案進行改進，生成的解決方案被置于一個群體中。為了獲得足夠多樣化的初始解決方案，我們在生成過程中使用了隨機化技術。利用 GPU 架構，我們可以并行生成許多不同的解決方案。多樣化群體會經(jīng)歷一個進化改進過程，而解決方案的最佳特性會保留在更新的幾代中。

在進化過程的一個步驟中，我們采用兩個隨機解決方案并應用交叉算子，這樣就會產(chǎn)生一個子代解決方案，它繼承了兩個親代的優(yōu)良特性?？梢詫鉀Q方案應用不同的交叉算子，其中一些算子會使子代處于不完整狀態(tài)。我們可以通過刪除重復節(jié)點、插入未選擇路徑的節(jié)點或對其進行不可行性局部搜索來修復解決方案。

例如，基于順序的交叉算子會根據(jù)節(jié)點在另一個父代解決方案中出現(xiàn)的順序，重新排列一個父代解決方案的一條或多條路徑中的節(jié)點。由此產(chǎn)生的子代保留了一個父代解決方案的分組屬性和另一個方案的排序屬性。這個特殊算子的結果是一個完整的解決方案，但就時間和容量限制而言，該解決方案很可能是不可行的。cuOpt 包含多個交叉算子，它們在解決方案上隨機執(zhí)行。

在這種情況下，交叉后的局部搜索階段在減少或消除不可行性，或提高總目標或行程距離方面起著至關重要的作用。局部搜索的目標權重取決于優(yōu)化的重要程度，較高的不可行性權重有助于將解決方案返回可行區(qū)域，這通常是大多數(shù)問題的情況。

局部搜索為子代解決方案找到局部最小值，然后子代解決方案參與進一步的進化步驟?？焖倬植克阉髦陵P重要，因為它是在時間預算內完成多少次改進迭代的主要因素。我們使用快速、近似和大型鄰域搜索算法來找到性能良好的局部最小值。我們沒有像傳統(tǒng)方法那樣執(zhí)行固定大小的鄰域局部搜索，而是設計了一個“網(wǎng)”來快速捕捉容易改進的地方，并在達到停滯時捕捉極深度算子。

快速算子能快速探索小鄰域，而近似算子每次應用時都能評估不同的移動，這一點尤為重要，因為交叉經(jīng)常會使某些路徑保持不變。正如在圖中尋找負子集相交循環(huán)的 GPU 并行算法中所解釋的，大型鄰域算子以路徑間的移動循環(huán)表示的移動鏈來移動請求。

循環(huán)算子可以探索一個非常大的鄰域，而簡單算子則無法探索該鄰域，這只是因為限制條件禁止這些簡單算子通過搜索空間中的某些山。通過這種工作流，我們可以經(jīng)常使用快速算子，而較少使用計算成本較高的深度算子。

GPU 并行化是通過將每條假設路徑映射到一個線程塊來實現(xiàn)的。這樣就可以使用共享內存來存儲與路徑相關的數(shù)據(jù)，這些數(shù)據(jù)在搜索移動時是臨時的。臨時路徑要么是原始路徑的副本，要么是一個或多個請求被彈出的路徑。線程塊中的線程會嘗試將其他路徑中所有可能的請求插入臨時路徑的所有位置。

在找到并記錄所有移動后，我們通過將每個路徑對的插入/彈出成本變量相加，找出每個路徑對的最佳移動。成本變量使用目標權重計算得出，其中還包含不可行性懲罰權重。如果多個移動對所修改的路徑而言是互斥的，我們就會執(zhí)行多個這樣的移動。

圖 2. NVIDIA cuOpt 中的局部搜索程序流程圖

對 cuOpt 進行基準測試

我們不斷提高 cuOpt 的性能和質量。為了衡量 cuOpt 的質量，我們在研究得最多的基準測試（包括 Gehring & Homberger CVRPTW 基準測試和 Li & Lim PDPTW 基準測試）上將求解器與最著名的解決方案進行了比較。在實踐中，求解器能多快得出所需的解決方案對企業(yè)非常重要。

評估標準和目標

準確度被定義為找到的解決方案與已知最佳解決方案（BKS）在目標方面的差距百分比。根據(jù)問題說明，第一個目標是車輛數(shù)，第二個目標是行駛距離。

求解時間是指達到與最佳已知解決方案或預期目標結果之間的某一差距所需的時間。求解時間是實際用例中最重要的標準之一，在預算時間內獲得高準確度的解決方案非常重要，組合優(yōu)化算法需要花費大量時間。

圖 3 和圖 4 顯示了求解器在大型基準測試實例子集上的收斂行為。

圖 3. cuOpt 在 CVRPTW 問題上的收斂行為

我們從每個類別（C1_10_1、C2_10_1、R1_10_1、R2_10_1、RC1_10_1、RC2_10_1）中選取了一個實例，以展示求解器的整體行為取決于（聚類、隨機）和（長路徑、短路徑）實例。我們將每分鐘采樣的總和與總 BKS 進行比較。

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

求解器在較大的實例中收斂速度很快，而在較小的實例中，收斂速度更是要快上幾個數(shù)量級。在下表中，我們展示了在達到與 BKS 相同的車輛數(shù)的同時，在不同規(guī)模的問題上達到 BKS 所需的時間。

圖 4. PDPTW 問題求解時間

cuOpt 創(chuàng)造 23 項世界紀錄

憑借使用 GPU 加速啟發(fā)式算法和最先進的策略這一新方法，cuOpt 打破了 Gehring & Homberger 基準測試中 15 個實例和 Li & Lim 基準測試中 8 個實例的紀錄。

目前，NVIDIA 保持著過去三年 CVRPTW 和 PDPTW 類別的所有紀錄。

在圖 5 中，每條邊代表從一個任務到另一個任務的路徑。綠線代表與前一記錄相同的邊緣，藍色和紅色邊代表兩個解決方案之間的差異。由于采用了進化策略，cuOpt 解決方案在可能解的搜索空間中處于完全不同的位置，這意味著存在許多不同的邊緣。

圖 5. cuOpt 世界紀錄與前紀錄的路徑可視化圖對比

來源：Combopt.org

Gehring & Homberger 與 BKS 的總體平均差距為 -0.07% 距離差距和 0.29% 車輛數(shù)差距。Li & Lim 與 BKS 的總體平均差距為 1.22% 距離差距和 0.36% 車輛數(shù)量差距?；鶞蕼y試在單顆 NVIDIA GPU 上運行了 200 分鐘。

總結

NVIDIA cuOpt 利用 GPU 加速和 RAPIDS 等 NVIDIA 技術，在數(shù)秒內即可獲得高質量的解決方案。我們的局部搜索運行速度較基于 CPU 的方法提高了 100 倍，基于 CPU 的求解器需要數(shù)小時才能獲得類似的解決方案。

審核編輯：劉清