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

Abstract

The VRP is one of the most important combinatorial optimization problems in the fields of logistics, transportation, and delivery services. Its objective is to determine a set of optimal routes for serving customers while satisfying various operational constraints, such as vehicle capacity, time windows, and service times. Owing to its computational complexity and highly combinatorial nature, the VRP has evolved into numerous variants designed to model increasingly realistic distribution scenarios. Over the years, a wide range of solution approaches has been developed to effectively address these different formulations. This thesis presents a comprehensive study of the VRP. It first introduces the fundamental concepts, the main variants, and the mathematical formulation of the problem. It then reviews the principal families of solution methods proposed in the literature, including exact, heuristic, and metaheuristic methods, highlighting their underlying principles. In addition, this work presents the fundamental concepts of Artificial Intelligence (AI), Machine Learning (ML), Deep Learning (DL), and Reinforcement Learning (RL). Finally, a literature review is devoted to the mainDL architectures proposed for solving the VRP, with the aim of analyzing recent approaches, their performance, and the remaining challenges in developing increasingly efficient solution methods capable of addressing the constraints of real-world applications***

Le problème de tournées de véhicules constitue l’un des problèmes d’optimisation combinatoire les plus importants dans les domaines de la logistique, du transport et des services de livraison. Son objectif est de déterminer un ensemble de tournées optimales permettant de desservir des clients tout en respectant diverses contraintes, telles que la capacité des véhicules, les fenêtres de temps et les durées de service. En raison de sa complexité et de son caractère fortement combinatoire, ce problème a donné naissance à de nombreuses variantes visant à représenter des situations de distribution de plus en plus réalistes. Au fil des années, de nombreuses approches ont été développées afin de répondre efficacement à ces différentes formulations. Ce mémoire présente une étude approfondie du problème de tournées de véhicules. Il introduit tout d’abord les concepts fondamentaux, les principales variantes ainsi que la formulation mathématique du problème. Il passe ensuite en revue les principales familles de méthodes de résolution proposées dans la littérature, notamment les méthodes exactes, les méthodes heuristiques et les métaheuristiques, en mettant en évidence leurs principes, leurs avantages, leurs limites ainsi que leurs domaines d’application. Par ailleurs, ce travail présente les notions essentielles de l’intelligence artificielle, de l’apprentissage automatique, de l’apprentissage profond et de l’apprentissage par renforcement. Enfin, une revue de la littérature est consacrée aux principales architectures d’apprentissage profond proposées pour la résolution du problème de tournées de véhicules, afin d’analyser les approches les plus récentes, leurs performances et les défis qui demeurent pour le développement de méthodes de résolution toujours plus efficaces et adaptées aux contraintes des applications réelles