Etat de l'art sur les méthodes de tournée de véhicule avec fenêtre de temps

Abstract

Le problème de tournées de véhicules (VRP) avec fenêtres de temps (VRPTW) consiste à faire la livraison de marchandise à un ensemble de clients avec une flotte de véhicules ayant un ou plusieurs points de départ appelés dépôts. Chaque client doit être desservi à l'intérieur d'une période prédéfinie, appelée fenêtre de temps. En pratique, on doit pouvoir respecter un grand nombre de contraintes et de caractéristiques complexes telles que des flottes hétérogènes de véhicules, des restrictions sur les routes, etc., en plus de devoir prendre en compte un grand nombre de clients. Il est donc primordial pour les distributeurs d'avoir accès à des outils performants d'optimisation capables de gérer un grand ensemble de contraintes de façon efficace. Dans cette mémoire, on va donner une description du VRP et ses paramètres puis nous énumérons ses différentes variantes. On se concentrera après sur le VRPTW, où on va citer ses variantes et comparer entre les différentes méthodes exactes et heuristiques pour le résoudre.***

The vehicle routing problem (VRP) with time windows (VRPTW) consists of delivering merchandise to a set of customers with a fleet of vehicles having one or more starting points called depots. Each customer must be served within a predefined period, called a time window. In practice, we must be able to comply with a large number of constraints and complex characteristics such as heterogeneous fleets of vehicles, restrictions on roads, etc., in addition to having to take into account a large number of customers. It is therefore essential for distributors to have access to efficient optimization tools capable of managing a large set of constraints effectively. In this thesis, we will give a description of the VRP and its parameters, and then we will list its different variants. We will focus later on the VRPTW, where we will enumerate its variants and compare between the different exact and heuristic methods to solve it.