《基于 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可能会学歪，有时可以快速收敛，有时难以收敛
