重庆理工大学学报2023，Vol.37Issue(23) ：260-266.DOI:10.3969/j.issn.1674-8425(z).2023.12.030

基于深度强化学习的方法求解带时间窗的旅行商问题

Solving the traveling salesman problem with time window based on deep reinforcement learning

江明 刘志威
重庆理工大学学报2023，Vol.37Issue(23) ：260-266.DOI:10.3969/j.issn.1674-8425(z).2023.12.030
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据

基于深度强化学习的方法求解带时间窗的旅行商问题

Solving the traveling salesman problem with time window based on deep reinforcement learning

江明 1刘志威2
扫码查看

作者信息

  • 1. 福建理工大学 互联网经贸学院,福州 350118
  • 2. 福建理工大学 交通运输学院,福州 350118
  • 折叠

摘要

带时间窗的旅行商问题(traveling salesman problem with time window,TSPTW)是旅行商问题的一个变种,在物资配送等方面有大量的应用.传统方法的求解时间较长且泛化性较差,为提高TSPTW的求解效率,将求解过程建模为马尔科夫决策过程,定义了状态、动作、奖励,提出了一种基于深度强化学习的Transformer加指针网络的组合模型,通过多头注意力对输入的特征进行编码,采用指针网络求出解的概率分布,所提深度学习网络通过强化学习算法进行训练.实验结果表明:所提方法对比传统的启发式求解算法,可以得到更高质量的解,相较于求解器和启发式算法,有超过数10倍的提升效果,且易于将模型拓展到不同规模的问题上.

关键词

带时间窗的旅行商/深度强化学习/组合优化/注意力机制

Key words

traveling salesman with time window/deep reinforcement learning/combined optimization/attention mechanism

引用本文复制引用

基金项目

国家社会科学基金(22BGL007)

福建省社会科学基金(FJ2020B038)

福建省习近平新时代中国特色社会主义思想研究中心项目(GY-S21118)

出版年

2023
重庆理工大学学报
重庆理工大学

重庆理工大学学报

CSTPCD北大核心
影响因子：0.567
ISSN：1674-8425
参考文献量1
段落导航相关论文