《Computers & Operations Research》：TuneNSearch: A hybrid transfer learning and local search approach for solving vehicle routing problems
編輯推薦：
車輛路徑問題（VRP）的求解是物流優化的核心挑戰。現有方法往往受限于泛化能力弱或計算成本高。本研究提出TuneNSearch框架，將Transformer架構與邊緣感知圖注意力網絡（E-GAT）結合，并集成高效的局部搜索算法。該框架先以多倉庫VRP（MDVRP）進行預訓練，再通過微調適配多種VRP變體。實驗表明，TuneNSearch在CVRPLIB和TSPLIB數據集上，與已知最優解的偏差保持在3%以內，顯著優于現有神經網絡方法，為實際物流系統提供了高效、通用的決策支持。
車輛路徑問題（Vehicle Routing Problem, VRP）是組合優化領域的經典難題，其目標是為車隊設計訪問一系列客戶點的最優路線，以最小化總行駛距離。從城市配送、外賣物流到無人機投遞，VRP的解決方案直接關系到運營成本與效率。然而，VRP家族龐大，包括帶容量約束的VRP（CVRP）、多倉庫VRP（MDVRP）、帶時間窗的VRP（VRPTW）等諸多變體，且問題本身是NP-Hard的，這意味著隨著問題規模增大，精確求解將變得不可行。
傳統上，研究者們依賴元啟發式算法（如遺傳算法、模擬退火）來尋找高質量的解。近年來，基于神經網絡的方法嶄露頭角，它們能夠從數據中學習策略，快速生成解決方案。但這些方法通常存在兩大局限：其一，大多數模型是針對單一VRP變體專門訓練的，缺乏跨不同問題的泛化能力；其二，對于大規模實例，純神經網絡方法的求解質量往往不及成熟的元啟發式算法。此外，現有的多任務或遷移學習方法，其預訓練通常基于較簡單的單倉庫問題（如CVRP），這使得模型難以應對現實世界中更復雜的多倉庫物流場景。
為了解決這些挑戰，來自葡萄牙科英布拉大學的研究團隊在《Computers 》上發表論文，提出了TuneNSearch——一個創新的混合框架。該框架巧妙地將遷移學習與高效的局部搜索相結合，旨在開發一個既能泛化到多種VRP變體，又能與頂尖元啟發式算法性能相媲美的通用求解器。
為了開展這項研究，作者們主要運用了以下幾個關鍵技術方法：首先，在模型架構上，他們采用了基于Transformer的編碼器-解碼器框架，并創新性地集成了邊緣感知圖注意力網絡（Edge-aware Graph Attention Network, E-GAT）。E-GAT能夠將節點間的距離信息直接融入注意力機制，從而更好地捕捉路徑問題中固有的空間關系。其次，在訓練策略上，他們使用了強化學習中的REINFORCE算法，并采用了帶有多重最優策略優化（Policy Optimization with Multiple Optima, POMO）的框架，以利用問題的對稱性提升解的質量。第三，他們設計了一套包含多種算子的高效局部搜索程序，用于對神經網絡初步生成的解進行迭代優化。最后，在驗證階段，研究使用了大規模的公開基準數據集（CVRPLIB, TSPLIB）和隨機生成的實例進行評估，確保了結論的可靠性。
研究結果
1. 模型架構的有效性
研究者將E-GAT編碼器與POMO框架相結合。結果表明，這種組合增強了模型對圖結構的編碼能力，使其在評估從不同起點出發的解決方案軌跡時更為精準。在MDVRP的50節點和100節點實例上，該模型顯著優于之前提出的多倉庫多類型注意力（MD-MTA）方法。
2. 基于MDVRP預訓練的遷移學習優勢
TuneNSearch選擇在更為復雜的MDVRP上進行預訓練，而非傳統的CVRP。實驗發現，以此為基礎模型，經過微調后，其在單倉庫變體（如CVRP）上的表現與專門在CVRP上訓練的模型相當；而在多倉庫變體上，其性能則遠超后者。例如，在100節點的多倉庫問題上，TuneNSearch比在CVRP上預訓練的模型性能高出44%。這證明了從復雜問題中學習到的知識更易于向簡單問題遷移。
3. 局部搜索的顯著提升作用
在神經網絡推斷出初始解后，集成的高效局部搜索算法被用于進一步優化。該算法使用了多種搜索算子。結果顯示，這一步驟以很小的額外計算成本，帶來了顯著的性能提升，使得TuneNSearch在多個數據集上達到了神經網絡方法中的最新領先水平。
4. 廣泛的泛化與卓越的性能
TuneNSearch在CVRPLIB和TSPLIB的多個數據集上進行了測試。平均而言，其求解結果與文獻中已知最優解的偏差不到3%。相比之下，其他神經網絡方法的偏差在6%到25%之間，具體取決于問題的復雜程度。在數千個隨機生成的實例上，對于100節點的各種VRP變體，TuneNSearch的平均相對性能偏差與高性能元啟發式求解器PyVRP相比小于4%，而所需計算時間僅為后者的一小部分。這表明該方法在跨問題規模、跨實例分布和跨任務形式上都展現了強大的泛化能力。
結論與討論
本研究的核心結論是，TuneNSearch成功地將遷移學習與局部搜索相結合，為解決多樣化的車輛路徑問題提供了一個高效、通用的框架。其重要意義體現在三個方面：
首先，在方法學上，它打破了神經網絡模型通常局限于特定問題變體的桎梏。通過從復雜的MDVRP進行預訓練，模型學習到了更豐富的特征表示，從而能夠有效地適應包括單倉庫和多倉庫在內的各種VRP變體。
其次，在性能上，它通過集成局部搜索，彌補了純神經網絡方法在大規模實例上求解質量不足的缺點，使其性能能夠與當前先進的元啟發式算法（如PyVRP的混合遺傳搜索）競爭，同時保持了神經網絡固有的快速推理優勢。
最后，在實踐上，TuneNSearch為物流和供應鏈管理提供了強大的決策支持工具。企業無需為每個不同的路由場景開發和維護多個專用模型，從而可以節省大量的計算資源和人力資源，并能快速應對不斷變化的路由條件或新出現的問題變體，具有顯著的運營優勢和經濟效益。
總之，這項工作為神經組合優化領域提供了一條可行的路徑，即通過結合機器學習與傳統優化技術的優勢，來開發既強大又靈活的求解器，為應對現實世界中復雜的優化挑戰開辟了新的可能性。
