【论文笔记】A Deep Reinforcement Learning Based Real-Time Solution Policy for the TSP

发布于:2025-07-11 ⋅ 阅读:(10) ⋅ 点赞:(0)

《基于 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 问题),设计更灵活的图像表示。


关键问题

  1. 该方法如何实现 TSP 的实时求解?与传统算法相比优势何在?

    答:通过问题分解将 TSP 转化为子问题,利用 DCNN 的前向传播直接输出下一个城市,避免迭代;DRL 训练无需标签,模型训练完成后求解新实例仅需 0.022 秒(50 城市),而 CPLEX 需 16.53 秒,LKH 需 0.33 秒,显著提升实时性。优势在于:① 求解速度快,不受问题规模激增影响;② 泛化能力强,跨城市规模无需重新训练。

  2. 该方法为何能在无标签情况下训练?DRL 的作用是什么?

    答:采用 DRL 中的策略梯度方法,智能体通过与环境(TSP 实例)交互自主学习:① 以路径负距离为奖励,鼓励选择短路径;② 蒙特卡洛采样生成轨迹,通过优势函数(A (τ))优化策略,无需预先知道最优解标签。DRL 的作用是替代监督学习的标签,使模型从自身决策中学习最优策略。

  3. 该方法在大规模 TSP(如 100 城市)中的表现如何?泛化能力的核心原因是什么?

    答:100 城市 TSP 中,平均误差可控制在 10% 以内,无需额外训练。泛化能力源于:① 问题分解降低了映射复杂度,子问题结构一致(均为选择下一个城市);② DCNN 通过图像特征提取学习城市间的空间关系,而非记忆特定实例;③ 过滤机制确保解的可行性,避免无效决策干扰。

个人感悟

其创新点在于将TSP序列问题转换成了视觉问题,这个视觉模块,感觉可以后续写论文水一个创新点。将TSP坐标离散映射到图像上,会丢失一些信息,这个映射处理还需要进一步优化。

强化学习的训练是需要微调的,感觉不是很稳定,尤其是没有一个固定的baseline的时候,policy可能会学歪,有时可以快速收敛,有时难以收敛


网站公告

今日签到

点亮在社区的每一天
去签到