旅行商问题是经典的组合优化问题,在交通调度、物流管理、芯片设计等领域都具有重要的现实应用。因此,该问题自从上世纪被提出后就广受研究者的关注,但旅行商问题作为NP难问题,不存在多项式时间的求解算法。传统求解旅行商问题的算法分为精确算法、近似算法和启发式算法。近年来,随着深度学习在计算机视觉、自然语言处理等领域取得成功,研究者尝试利用深度学习技术来求解旅行商等组合优化问题,以期在组合优化领域也取得突破。现实应用场景中的很多旅行商问题实例具有规模大、时效性强的特点,但现有的深度强化学习算法都无法处理大规模问题。为解决这一个实际需求的瓶颈问题,提出了一种新的分层式深度强化学习算法,分为两层进行交替训练来快速求解大规模旅行商问题。上层算法负责生成子问题和合并子问题的解,其中提出了一种使用k-近邻图和广度优先搜索来动态生成子问题的方法。子问题被定义为具有固定端点的开环旅行商问题,这类问题的解是一条开环路径,可以直接合并为一个完整的旅行商问题路径。下层算法负责求解上层算法生成的子问题,使用基于深度强化学习方法训练的自回归求解器。该求解器的主体是一个编码器-解码器结构的深度神经网络模型,能够对节点数据进行编码,并直接输出节点序列构成的路径。另外,采用了数据增强和片段优化技术这两种在求解阶段能够提升算法性能的增强优化策略,能够通过更长的计算时间换取解的质量优化。分层式深度强化学习算法在四个不同规模的随机分布的数据集上进行了实验测试。实验结果表明,该方法能够快速地得到大规模旅行商问题的较优解,解的质量与最优解之间的差距为个位数百分比,并且所需的求解时间相比几个基准算法要低一至两个数量级。另外,分别对分层深度强化学习算法中的一些关键技术进行了消融实验,验证这些技术在算法中的重要性。