Neural Combinatorial Optimization with Reinforcement Learning : Solving theVehicle Routing Problem with Time Windows

2021-09-29 · Abdelhakim Abdellaoui, Issmail El Hallaoui, Loubna Benabbou

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. In this context, the current paper aims to present a complete framework for solving the vehicle routing problem with time windows (VRPTW) relying on neural networks and reinforcement learning. Our approach is mainly based on an attention model (AM) that predicts the near-optimal distribution over different problem instances. To optimize its parameters, this model is trained in a reinforcement learning(RL) environment using a stochastic policy gradient and through a real-time evaluation of the reward, quantity to meet the problem business and logical constraints. Using synthetic data, the proposed model outperforms some existing baselines. This performance comparison was on the basis of the solution quality (total tour length) and the computation time (inference time) for small and medium-sized samples.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Combinatorial Optimizationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows

2023-04-03 · Léo Baty, Kai Jungel, Patrick S. Klein, Axel Parmentier 외

With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same day deliveries. Existing multi-stage st…

Combinatorial Optimization Stochastic Optimization

Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems

2023-10-15 · Kuan Xu, Li Shen, Lindong Liu

Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. It has extensive applications in common combinatorial optimization, such as vehicle routing and scheduling probl…

Combinatorial Optimization Scheduling

Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms

2025-04-08 · Ido Greenberg, Piotr Sielski, Hugo Linsenmaier, Rajesh Gandham 외

Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in combinatorial optimization. Solving VRP in real-time at large scale has become critical in n…

Combinatorial Optimization reinforcement-learning Reinforcement Learning

Solving the vehicle routing problem with deep reinforcement learning

2022-07-30 · Simone Foa, Corrado Coppola, Giorgio Grani, Laura Palagi

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 combinat…

Combinatorial Optimization Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+1

Learning Vehicle Routing Problems using Policy Optimisation

2020-12-24 · Nasrin Sultana, Jeffrey Chan, A. K. Qin, Tabinda Sarwar

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 Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)