Solving Dynamic Traveling Salesman Problems With Deep Reinforcement Learning
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Deep Reinforcement Learning with Gradient Eligibility Traces
DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty
Explainable AI for Radar Resource Management: Modified LIME in Deep Reinforcement Learning
Multi-Objective Reinforcement Learning for Cognitive Radar Resource Management
Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization
MOORL: A Framework for Integrating Offline-Online Reinforcement Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.