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.

Abstract

This master's thesis presents an exact branch-cut-and-price algorithm for the vehicle Routing problem with stochastic demands. We formulate the problem as a two stage integer stochastic program with fixed recourse and adopt a formulation based on the associated space-capacity graph. We explain how this model can be transformed into a set partitioning master problem and an associated shortest path problem with resource constraint subproblem using Dantzig-Wolfe decomposition. We use a column generation algorithm based on state of the art techniques. During the resolution of the subproblem, we do not limit ourselves to the generation of routes without 2-cycles. We also experiment with $ng$-routes as well as elementary routes. In order to implement these concepts and eliminate larger cycles, we introduce additional binary resource variables each indicating wether a client can be visited by an extension of the current route. We use a bidirectional label setting algorithm that exploits the acyclicity of the underlying graph and only needs to consider each vertex exactly once. To limit the number of labels that can be generated at any iteration of that algorithm, we introduce an improved dominance rule that exploits the structure of the space-capacity graph. We also promote elimination of dominated labels by using the concept of unreachable vertices. In addition, we utilize a tabu search heuristic to speed up the identification of feasible negative reduced cost routes. To improve the lower bound found at each iteration of the column generation procedure, we introduce valid inequalities in the master problem. We specifically consider capacity cuts and Subset-Row Inequalities. We identify violated cuts dynamically at each node of the Branch-and-Bound tree by using a heuristic procedure. If the separation algorithm fails to identify violated cuts, we proceed to normal branching based on inter-tasks. The dominance rule and structure of the subproblem are modified to take these new inequalities into account. Finally, we present numerical results that prove the competitiveness of our algorithm. Indeed, we manage to solve to optimality 20 new instances taken from the literature in less than 20 minutes and we considerably improve the computational time for those already closed. Only 2 out of the 40 instances of our test set remain unsolved.