Solving the vehicle routing problem with deep reinforcement learning
Recently, the applications of the methodologies of Reinforcement Learning (RL) to NP-Hard Combinatorial optimization problems have become a popular topic. This is essentially due to the nature of the traditional combinatorial algorithms, often based on a trial-and-error process. RL aims at automating this process. At this regard, this paper focuses on the application of RL for the Vehicle Routing Problem (VRP), a famous combinatorial problem that belongs to the class of NP-Hard problems. In this work, first, the problem is modeled as a Markov Decision Process (MDP) and then the PPO method (which belongs to the Actor-Critic class of Reinforcement learning methods) is applied. In a second phase, the neural architecture behind the Actor and Critic has been established, choosing to adopt a neural architecture based on the Convolutional neural networks, both for the Actor and the Critic. This choice resulted in effectively addressing problems of different sizes. Experiments performed on a wide range of instances show that the algorithm has good generalization capabilities and can reach good solutions in a short time. Comparisons between the algorithm proposed and the state-of-the-art solver OR-TOOLS show that the latter still outperforms the Reinforcement learning algorithm. However, there are future research perspectives, that aim to upgrade the current performance of the algorithm proposed.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Learning Vehicle Routing Problems using Policy Optimisation
Deep reinforcement learning (DRL) has been used to learn effective heuristics for solving complex combinatorial optimisation problem via policy networks and have demonstrated promising performance. Existing works have fo…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem
Heavy goods vehicles are vital backbones of the supply chain delivery system but also contribute significantly to carbon emissions with only 60% loading efficiency in the United Kingdom. Collaborative vehicle routing has…
reinforcement-learningReinforcement LearningReinforcement Learning for Solving Stochastic Vehicle Routing Problem
This study addresses a gap in the utilization of Reinforcement Learning (RL) and Machine Learning (ML) techniques in solving the Stochastic Vehicle Routing Problem (SVRP) that involves the challenging task of optimizing …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Neural Combinatorial Optimization with Reinforcement Learning : Solving theVehicle Routing Problem with Time Windows
In contrast to the classical techniques for solving combinatorial optimization problems, recent advancements in reinforcement learning yield the potential to independently learn heuristics without any human interventions…
Combinatorial Optimizationreinforcement-learningReinforcement LearningReinforcement Learning (RL)Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem
The Fleet Size and Mix Vehicle Routing Problem (FSMVRP) is a prominent variant of the Vehicle Routing Problem (VRP), extensively studied in operations research and computational science. FSMVRP requires simultaneous deci…
Computational EfficiencyReinforcement LearningGraph Embedding