Méthodes hybrides basées sur la génération de colonnes pour des problèmes de tournées de véhicules avec fenêtres de temps

Un problème de tournées de véhicules avec fenêtres de temps 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 thèse, nous présentons une méthode heuristique pour résoudre un ensemble de problèmes de tournées de véhicules de grande taille avec fenêtres de temps de façon efficace. Les problèmes abordés sont riches dans le sens où ils contiennent des caractéristiques non conventionnelles complexes s'apparentant à des problématiques réelles. La méthode proposée est un hybride entre une méthode métaheuristique de recherche à grands voisinages et une méthode exacte de génération de colonnes, la plus performante à ce jour pour résoudre de façon exacte des problèmes de tournées de véhicules assez contraints. La recherche à grands voisinages est une méthode où l'on vient itérativement détruire (phase de destruction) et reconstruire (reconstruction) des parties d'une solution courante afin d'obtenir de meilleures solutions. Les voisinages, définis dans la phase de destruction, sont explorés dans la phase de reconstruction. Dans notre méthode, les voisinages sont explorés par génération de colonnes gérée de façon heuristique. Une méthode de génération de colonnes sert à résoudre la relaxation linéaire d'un programme linéaire. Elle résout itérativement un problème maître, qui est le programme linéaire restreint à un sous-ensemble de variables, et un ou plusieurs sous-problèmes qui servent à rajouter des variables de coût réduit négatif au problème maître. La résolution se termine lorsque les sous-problèmes ne trouvent plus de variables de coût réduit négatif. Cette méthode est imbriquée dans un algorithme de séparation et évaluation pour obtenir des solutions entières. Plusieurs opérateurs sont définis pour sélectionner des éléments qui seront retirés de la solution courante dans la phase de destruction. À chaque itération, un opérateur est choisi aléatoirement en favorisant ceux qui ont permis d'améliorer la solution courante dans les itérations précédentes. La génération de colonnes sert ensuite à explorer le voisinage ainsi défini (reconstruction). Plusieurs aspects de la génération de colonnes sont gérés de façon heuristique afin d'obtenir de bonnes solutions en des temps raisonnables aux dépens de la certitude de trouver une solution optimale. Les sous-problèmes sont résolus par une méthode de recherche tabou et la génération de colonnes est stoppée après une trop faible amélioration de la valeur de la solution courante de la relaxation linéaire au cours des dernières itérations. Afin d'obtenir des solutions entières, un branchement agressif sur la variable ayant la valeur fractionnaire la plus grande est effectué. Sa valeur est fixée à 1 sans possibilité de retour en arrière.