Deep Learning-Based Dynamic Vehicle Routing for Real-Time Optimization under Time and Capacity Constraints

Abstract

The Vehicle Routing Problem (VRP) represents a fundamental challenge in the fields of logistics, transportation, and delivery services. Solving this problem efficiently enables companies to reduce operational costs, optimize fleet utilization, and improve customer satisfaction. However, traditional heuristic and metaheuristic methods, while effective for static instances of the problem, are not well suited to dynamic environments that require real-time adaptation and rapid decision-making. These approaches rely on fixed assumptions and require frequent re-optimization, making them unable to respond effectively to unpredictable operating conditions. This thesis proposes a Deep Reinforcement Learning (DRL) framework for solving the Dynamic Vehicle Routing Problem (DVRP) in real time. Unlike traditional methods, which rely on static assumptions and require frequent re-optimization, the proposed system continuously adapts to changes in the environment and generates routing decisions on the fly, making it well suited to dynamic logistics scenarios. The framework employs a Graph Attention Network (GAT)v2 encoder to capture the spatial and temporal relationships among customer nodes, while the decoder combines a Multi-Head Attention (MHA) mechanism with a dynamically context-aware Long Short-Term Memory (LSTM) to model sequential dependencies and ensure constraint feasibility during route generation. This architecture effectively handles complex constraints, such as time windows and vehicle capacity, while maintaining real-time decision-making capabilities. The experimental results demonstrate that the proposed approach achieves an effective balance between solution quality and computational efficiency. In particular, it significantly reduces inference time compared with OR-Tools and the Variable Neighborhood Search (VNS)/Tabu Search heuristic, making it particularly suitable for applications requiring real-time decision-making. Although OR-Tools achieves lower routing costs, the proposed approach produces higher-quality solutions than VNS/Tabu Search while requiring substantially less computation time. These findings confirm that the proposed framework delivers satisfactory performance for dynamic vehicle routing by effectively balancing solution quality with fast inference***

services de livraison. Résoudre ce problème de manière efficace permet aux entreprises de réduire leurs coûts opérationnels, d’optimiser l’utilisation de leur flotte et d’améliorer la satisfaction client. Cependant, les méthodes heuristiques et métaheuristiques traditionnelles, bien qu’efficaces pour des instances statiques du problème, sont peu adaptées aux environnements dynamiques nécessitant une adaptation en temps réel et une prise de décision rapide. Ces approches reposent sur des hypothèses fixes et nécessitent une ré-optimisation fréquente, ce qui les rend incapables de répondre efficacement à des conditions opérationnelles imprévisibles. Cette thèse propose un cadre basé sur le DRL pour résoudre le DVRP en temps réel. Contrairement aux méthodes traditionnelles, qui reposent sur des hypothèses statiques et nécessitent une ré-optimisation fréquente, le système proposé s’adapte continuellement aux changements de l’environnement et génère des décisions de routage à la volée, ce qui le rend particulièrement adapté aux scénarios logistiques dynamiques. Le cadre proposé s’appuie sur un encodeur GATv2 afin de capturer les relations spatiales et temporelles entre les noeuds clients, tandis que le décodeur combine un mécanisme de MHA avec un LSTM sensible au contexte dynamique pour modéliser les dépendances séquentielles et garantir le respect des contraintes lors de la génération des tournées. Cette architecture permet de gérer efficacement des contraintes complexes, telles que les fenêtres de temps et la capacité des véhicules, tout en conservant des capacités de prise de décision en temps réel. Les résultats expérimentaux montrent que l’approche proposée établit un compromis efficace entre la qualité des solutions et l’efficacité computationnelle. En particulier, elle réduit significativement le temps d’inférence par rapport à OR-Tools ainsi qu’à l’heuristique VNS/Tabu Search, ce qui la rend particulièrement adaptée aux applications nécessitant une prise de décision en temps réel. Bien qu’OR-Tools obtienne des coûts de routage plus faibles, l’approche proposée produit des solutions de meilleure qualité que VNS/Tabu Search tout en nécessitant un temps de calcul nettement inférieur. Ces résultats confirment que le cadre développé offre des performances satisfaisantes pour le routage dynamique de véhicules en conciliant efficacement la qualité des solutions et la rapidité d’inférence.