摘要
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.
学科与关键词
- Reinforced Lin-Kernighan-Helsgaun algorithms for the traveling salesman problemsZheng, 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 ProblemsXu, 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 PenaltiesZhang, Ke; Lin, Xi; Li, Meng*IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 24649-24661.被引 15
