Un algorithme de génération de colonnes pour le problème de tournées de véhicule avec demandes stochastiques

Ce mémoire présente un algorithme exact de génération de colonnes avec plans coupants pour le problème de tournées de véhicules avec demandes stochastiques. Nous posons le problème comme un programme stochastique en deux étapes en nombres entiers et adoptons une formulation se basant sur le graphe espace-état associé. Nous utilisons ensuite la décomposition de Dantzig-Wolfe pour produire un problème maître de partitionnement d'ensemble et un sous-problème de plus court chemin avec contraintes de ressources. Nous proposons de résoudre ce modèle à l'aide d'un algorithme exploitant des techniques à la fine pointe de l'état de l'art. Lors de la résolution du sous-problème, nous ne nous limitons pas uniquement aux routes sans 2-cycles; nous effectuons également des expériences avec les $ng$-routes ainsi qu'avec les chemins élémentaires. Pour implémenter ces concepts et éliminer de plus grands cycles, nous ajoutons des ressources de visite binaires indiquant si un client peut encore être visité dans une prolongation de la route élémentaire courante. Afin de résoudre le sous-problème, nous utilisons un algorithme d'étiquetage bidirectionnel tirant parti de l'acyclicité du graphe espace-état et qui considère uniquement une fois chaque nœud. Dans le but de limiter le nombre d'étiquettes générées à chaque itération de cette procédure, nous introduisons une règle de dominance améliorée qui exploite la structure du graphe sous-jacent. Nous utilisons également le concept de clients non atteignables pour favoriser l'élimination d'étiquettes inutiles. Par ailleurs, nous implantons une méthode de recherche taboue qui accélère l'obtention de chemins réalisables de coût réduit négatif. Pour augmenter la borne inférieure trouvée à chaque itération de l'algorithme de génération de colonnes, nous ajoutons deux types d'inégalités valides au problème maître: des contraintes de capacité et des contraintes de sous-ensemble de lignes. Nous modifions la structure du sous-problème afin de prendre en compte ces coupes que nous générons dynamiquement à chaque nœud de branchement de façon heuristique. Si l'algorithme de séparation ne parvient pas à trouver d'inégalités valides suffisamment violées par la solution fractionnaire actuelle, alors nous procédons à un branchement basé sur les inter-tâches. Finalement, nous présentons des résultats numériques qui démontrent la compétitivité de notre algorithme. Notre méthode permet effectivement de résoudre 20 nouvelles instances tirées de la littérature en moins de 20 minutes en plus d'accélérer considérablement la résolution des instances déjà résolues. Seulement 2 des 40 instances de notre ensemble de tests demeurent irrésolues.