《基于 DRL 和 DCNN 的實時 TSP 求解策略》
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 24, NO. 6, JUNE 2023
一段話總結
本文提出了一種基于深度強化學習（DRL） 和深度卷積神經網絡（DCNN） 的實時旅行商問題（TSP）求解策略。通過問題分解將 TSP 轉化為一系列子問題，采用圖像表示將城市坐標轉化為圖像輸入，利用 DCNN 的特征提取能力擬合子問題映射，并設計過濾機制確保解的可行性。基于 DRL 的訓練方法無需標簽，通過并行采樣加速訓練，實驗表明該方法在 50 城市 TSP 中平均誤差僅 3.97%，求解時間 0.022 秒，顯著快于傳統算法（如 CPLEX、LKH），且在不同城市規模和真實基準（TSPLIB）中表現出良好的泛化能力。
詳細總結
1. 研究背景與動機
-
TSP 的實時需求：物流、導航等領域對 TSP 實時求解需求增加，但傳統算法（如窮舉、遺傳算法）因迭代過程難以滿足實時性。
-
現有方法局限：
-
確定性算法（如 CPLEX）能求最優解，但存在 “組合爆炸”，大規模問題效率極低；
-
啟發式算法（如 LKH、GA）依賴迭代，參數變化時需重新計算；
-
監督學習的深度學習方法（如 PtrNet）需大量最優解標簽，標簽生成成本高。
-
-
研究目標：提出基于 DRL 和 DCNN 的方法，實現 TSP 的實時求解，無需標簽且泛化能力強。
2. 核心方法
2.1 TSP 分解與圖像表示
- 問題分解：將 TSP 拆分為一系列子問題，每個子問題只需從剩余城市中選擇下一個訪問城市，遞歸求解：
其中，fk(i,Uk)f_k(i, U_k)fk?(i,Uk?) 表示從當前城市 iii 訪問剩余 kkk 個城市后返回起點的最短距離。
-
圖像表示：
-
城市坐標歸一化后映射到 40×40 圖像，像素標記為：背景（0）、當前城市（-1）、剩余城市（1）、起點（2）；
-
子問題轉化為圖像分類任務，DCNN 輸出下一個城市的像素概率。
*
-
2.2 DCNN 架構與過濾機制
-
DCNN 結構：基于 VGG16 改進，輸入 40×40 圖像，經 5 次卷積 - 池化操作提取特征，最終通過 SoftMax 輸出 1600 維（40×40）概率分布，對應每個像素被選為下一個城市的概率。
-
過濾機制：排除無效像素（背景、已訪問城市），起點僅在最后一步可選，確保解滿足 TSP 約束（每個城市僅訪問一次，最終返回起點）。
2.3 DRL 訓練方法
- 無需標簽的訓練：通過策略梯度優化 DCNN 參數，智能體（ salesman ）與環境（TSP 實例）交互，以路徑負距離為獎勵：
r(s, a) = -d_{ij}
-
并行采樣：多線程同時處理不同 TSP 實例，加速采樣過程（8 線程比 1 線程快 3.5 倍）。
-
訓練過程可視化：分為 5 個階段（隨機開始→初始策略→全局搜索→局部搜索→微調），可直觀觀察策略形成。
3. 實驗結果與分析
3.1 性能對比（50 城市 TSP）
| 算法 | 平均誤差 | 平均求解時間 | 優勢場景 |
|---|---|---|---|
| CPLEX | 0% | 16.53s | 小規模問題最優解 |
| LKH | 0.39% | 0.33s | 中規模問題高效近似 |
| GA | 29.55% | 7.77s | 實現簡單但精度低 |
| DCNN（本文） | 3.97% | 0.022s | 實時性要求高的場景 |
3.2 泛化能力測試
-
不同城市規模：無需額外訓練，10-100 城市誤差隨規模緩慢增長（100 城市誤差約 6.33%）。
-
遷移學習提升：基于 50 城市模型微調，60-80 城市誤差進一步降低（80 城市誤差從 5.98% 優化至更低）。
3.3 真實基準驗證
- 在 TSPLIB（真實城市坐標數據集）上測試，結果與理論趨勢一致，表明方法適用于實際場景。
4. 結論與未來方向
-
優勢：實時性強（求解時間 < 0.05s）、泛化能力好（跨規模適用）、無需標簽；
-
局限：受圖像尺寸限制，超大規模問題需優化；
-
未來方向：擴展至 TSP 變體（帶時間窗、多 salesman 問題），設計更靈活的圖像表示。
關鍵問題
-
該方法如何實現 TSP 的實時求解？與傳統算法相比優勢何在？
答：通過問題分解將 TSP 轉化為子問題，利用 DCNN 的前向傳播直接輸出下一個城市，避免迭代；DRL 訓練無需標簽，模型訓練完成后求解新實例僅需 0.022 秒（50 城市），而 CPLEX 需 16.53 秒，LKH 需 0.33 秒，顯著提升實時性。優勢在于：① 求解速度快，不受問題規模激增影響；② 泛化能力強，跨城市規模無需重新訓練。
-
該方法為何能在無標簽情況下訓練？DRL 的作用是什么？
答：采用 DRL 中的策略梯度方法，智能體通過與環境（TSP 實例）交互自主學習：① 以路徑負距離為獎勵，鼓勵選擇短路徑；② 蒙特卡洛采樣生成軌跡，通過優勢函數（A (τ)）優化策略，無需預先知道最優解標簽。DRL 的作用是替代監督學習的標簽，使模型從自身決策中學習最優策略。
-
該方法在大規模 TSP（如 100 城市）中的表現如何？泛化能力的核心原因是什么？
答：100 城市 TSP 中，平均誤差可控制在 10% 以內，無需額外訓練。泛化能力源于：① 問題分解降低了映射復雜度，子問題結構一致（均為選擇下一個城市）；② DCNN 通過圖像特征提取學習城市間的空間關系，而非記憶特定實例；③ 過濾機制確保解的可行性，避免無效決策干擾。
個人感悟
其創新點在于將TSP序列問題轉換成了視覺問題，這個視覺模塊，感覺可以后續寫論文水一個創新點。將TSP坐標離散映射到圖像上，會丟失一些信息，這個映射處理還需要進一步優化。
強化學習的訓練是需要微調的，感覺不是很穩定，尤其是沒有一個固定的baseline的時候，policy可能會學歪，有時可以快速收斂，有時難以收斂
