ScholarMate
English简体中文繁體中文
客服热线:400-1616-289
登录注册
期刊论文

Solving Dynamic Traveling Salesman Problems With Deep Reinforcement Learning

Zhang, Zizhen; Liu, Hong*; Zhou, MengChu; Wang, Jiahai中山大学
IEEE Transactions on Neural Networks and Learning Systems2023-4DOI: 10.1109/TNNLS.2021.3105905
50被引13阅读
引用收藏
分享

摘要

A traveling salesman problem (TSP) is a well-known NP-complete problem. Traditional TSP presumes that the locations of customers and the traveling time among customers are fixed and constant. In real-life cases, however, the traffic conditions and customer requests may change over time. To find the most economic route, the decisions can be made constantly upon the time-point when the salesman completes his service of each customer. This brings in a dynamic version of the traveling salesman problem (DTSP), which takes into account the information of real-time traffic and customer requests. DTSP can be extended to a dynamic pickup and delivery problem (DPDP). In this article, we ameliorate the attention model to make it possible to perceive environmental changes. A deep reinforcement learning algorithm is proposed to solve DTSP and DPDP instances with a size of up to 40 customers in 100 locations. Experiments show that our method can capture the dynamic changes and produce a highly satisfactory solution within a very short time. Compared with other baseline approaches, more than 5% improvements can be observed in many cases.

学科与关键词

关键词
RoutingTraveling salesman problemsPlanningReal-time systemsDecision makingComputational modelingReinforcement learningAttention modeldeep reinforcement learning (DRL)dynamic traveling salesman problem (DTSP)machine learningpolicy gradient
相关
加载中…
  • Reinforced Lin-Kernighan-Helsgaun algorithms for the traveling salesman problems
    Zheng, Jiongzhi; He, Kun*; Zhou, Jianrong; Jin, Yan; Li, Chu-MinKnowledge-Based Systems, 2023, 260: 110144.被引 18
  • Reinforcement Learning With Multiple Relational Attention for Solving Vehicle Routing Problems
    Xu, Yunqiu; Fang, Meng; Chen, Ling*; Xu, Gangyan*; Du, Yali; Zhang, ChengqiIEEE Transactions on Cybernetics, 2022, 52(10): 11107-11120.被引 47
  • Transformer-Based Reinforcement Learning for Pickup and Delivery Problems With Late Penalties
    Zhang, Ke; Lin, Xi; Li, Meng*IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 24649-24661.被引 15
查看全部 →

发表信息

论文状态
公开发表
期刊
IEEE Transactions on Neural Networks and Learning Systems
发表日期
2023-04
卷期
第 34 卷, 第 4 期
页码
2119-2132
DOI
10.1109/TNNLS.2021.3105905
语言
ENGLISH
成果收录
SCIE
资助标注
National Key Research and Development Program of China [2018AAA0101203]; National Science Foundation of China [71601191, 62072483]; Guangdong Natural Science Funds [2019A1515011169, 2021A1515011301]; Ministry of Science and Higher Education of the Russian Federation as part of World-class Research Center Program: Advanced Digital Technologies [075-15-2020-903]

作者

  • Z

    Zhang, Zizhen (第一作者)

    sun yat sen univ

  • L

    Liu, Hong (通讯)

查看全部 4 位作者收起作者
  • Z

    Zhou, MengChu

    new

  • W

    Wang, Jiahai

    sun yat sen univ

登录解锁更多功能

  • 收藏这篇,随时在“我的 · 收藏”找回
  • 认领你的成果,生成推广素材
  • 关注作者获取最新成果
  • 加入项目组、协同写作
注册 / 登录

产品服务

  • 科研之友
  • 创新城
  • 科创云

服务支持

  • 帮助中心
  • 隐私政策
  • 服务条款

联系方式

在线客服:【】
客服热线:400-1616-289
电子邮箱:support@scholarmate.com

关注或下载科研之友

微信二维码
微信公众号
客户端下载二维码
下载客户端
科研成果科研人员科研机构科研动态爱瑞思软件

©2026 深圳市科研之友网络服务有限公司

公安备案图标粤公网安备 44030502000213
粤ICP备 16046710 号粤B2-20110417