Le problème de tournées de véhicules avec cueillettes, livraisons, fenêtres de temps et contraintes de manutention

Les problèmes de tournées de véhicules avec cueillettes et livraisons consistent à trouver des tournées réalisables minimisant le nombre de véhicules utilisés et la distante totale parcourue, et permettant de compléter toutes les requêtes. Une requête est définie par un point de cueillette et un point de livraison, et une quantité de marchandise à transporter du point de cueillette au point de livraison. Ce faisant, une tournée est dite réalisable si la charge du véhicule ne dépasse pas sa capacité et si, pour chaque requête, on visite le point de cueillette avant le point de livraison avec le même véhicule. Dans la dernière décennie, la communauté de recherche opérationnelle s'est attaquée à des problèmes de plus en plus complexes qui tiennent compte de contraintes opérationnelles difficiles à traiter. Cette thèse s'insère dans cette tendance. Cette thèse propose des modèles et des algorithmes pour résoudre deux variantes du problème de tournées de véhicules avec cueillettes et livraisons : le problème de tournées de véhicules avec cueillettes, livraisons, fenêtres de temps et contrainte de chargement dernier entré premier sorti (last-in-first-out – LIFO) (pickup and delivery problem with time Windows and LIFO loading – PDPTWL) et le problème de tournées de véhicules avec fenêtres de temps et plusieurs piles (pickup and delivery problem with time windows and multiple stacks – PDPTWMS). Dans le PDPTWL, la contrainte de chargement dernier entré premier sorti stipule qu'aucune manutention non nécessaire n'est faite lors de la livraison d'un item : un item peut seulement être livré s'il est situé sur le dessus de la pile. Dans le PDPTWMS, chaque véhicule contient plusieurs piles qui sont gérées selon une politique de chargement dernier entré premier sorti. Afin de résoudre le PDPTWL, trois algorithmes de génération de colonnes avec plans coupants et un algorithme heuristique sont proposés. Le premier algorithme de génération de colonnes incorpore la contrainte de chargement dans le problème maître, alors que le second l'incorpore dans le sous-problème. Pour ce faire, un algorithme d'étiquetage et un critère de dominance spécialisés sont proposés. Le troisième algorithme de génération de colonnes est une combinaison des deux premiers algorithmes. Des inégalités valides connues sont adaptées pour le PDPTWL. Des instances ayant jusqu'à 75 requêtes sont résolues par ces trois algorithmes exacts en une heure de temps de calcul. L'algorithme heuristique, quant à lui, permet de traiter plus rapidement des instances de plus grande taille. D'abord, un ensemble de solutions initiales est construit avec un algorithme glouton. Puis, pour chaque solution, un algorithme de recherche locale est utilisé afin de diminuer en priorité le nombre de véhicules et ensuite la distance totale parcourue. Puis, deux stratégies sont utilisées pour créer des solutions enfants. La première choisit aléatoirement des tournées de l'ensemble de solutions alors que la deuxième utilise un opérateur de croisement. Pour les deux stratégies, un algorithme de recherche locale est ensuite utilisé. Finalement, les enfants sont ajoutés à l'ensemble de solutions et les meilleurs survivants sont conservés. L'ensemble de solutions est géré afin de garder uniquement les solutions variées de meilleure qualité par rapport au coût total. Des instances ayant jusqu'à 300 requêtes sont résolues par cette heuristique en deux heures de temps de calcul. Afin de résoudre le PDPTWMS, deux algorithmes de génération de colonnes avec plans coupants sont proposés. Le premier algorithme de génération de colonnes incorpore la contrainte de chargement avec plusieurs piles dans le sous-problème. Pour ce faire, un algorithme d'étiquetage et un critère de dominance spécialisés sont proposés. Le deuxième algorithme incorpore partiellement la contrainte de chargement avec plusieurs piles dans le sous-problème et ajoute, au besoin, des contraintes au problème maître lorsque la solution trouvée ne respecte pas la contrainte de chargement avec plusieurs piles. Des instances avec une, deux et trois piles et ayant jusqu'à 75 requêtes sont résolues par ces deux algorithmes exacts en deux heures de temps de calcul.