<  Back to the Polytechnique Montréal portal

Nouvelles coupes pour le problème de tournées de véhicule avec demandes stochastiques

Alexandre Leuliet

Masters thesis (2014)

[img]
Preview
Download (625kB)
Cite this document: Leuliet, A. (2014). Nouvelles coupes pour le problème de tournées de véhicule avec demandes stochastiques (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1603/
Show abstract Hide abstract

Abstract

RÉSUMÉ : Dans ce mémoire, on se propose de résoudre le problème de tournées de véhicules avec demandes stochastiques à l’aide de l’algorithme L-shaped en nombres entiers. Des coupes de type LBF (Lower Bounding Functionals) sont générées pour accélérer la résolution. Le problème est semblable aux problèmes de tournées de véhicules classiques mais considère que les demandes des clients sont des variables aléatoires dont la valeur n’est révélée qu’au moment de leur visite. Ces variables suivent une loi Normale, sont indépendantes et identiquement distribuées. Le problème est formulé comme un programme stochastique en deux étapes en nombres entiers. Les variables de décisions de première étape servent à définir des routes a priori qui devront minimiser le coût total espéré de parcours. Chaque fois qu’un véhicule arrive chez un client, si la demande ne peut pas être servie en totalité alors on dit qu’un échec apparaît. Dans une telle situation, les décisions de seconde étape sont prises et consistent à effectuer un aller-retour entre le client courant et le dépôt pour se recharger ou se décharger en marchandise. Ce recours est communément appelé le recours simple. Une étape préliminaire à la résolution consiste à relaxer le modèle en enlevant temporairement les contraintes de capacité et d’élimination de sous-tours ainsi que les contraintes d’intégrité. La fonction de recours est remplacée par une variable réelle positive représentant une borne inférieure sur le coût de recours espéré. L’intégrité des variables est retrouvée grâce à une procédure d’énumération implicite. Les contraintes de capacité et de sous-tours violées sont ajoutées dynamiquement au modèle chaque fois qu’elles sont identifiées. Des coupes d’optimalité sont générées et assurent la convergence de l’algorithme vers la solution optimale. Pour accélérer le processus de résolution par rapport à ce qui existe déjà dans la littérature, on développe deux nouvelles familles de coupes LBF. Les premières sont basées sur l’identification de chaînes dans les solutions intermédiaires rencontrées aux différents nœuds de l’arbre d’énumération. Ces coupes sont ajoutées chaque fois qu’on en identifie une qui est violée par la solution courante. Elles imposent à la borne inférieure sur le coût de recours de prendre une certaine valeur si la solution courante visite les clients des chaînes dans le même ordre. Les deuxièmes sont basées sur des ensembles non structurés de noeuds. Elles sont générées de façon semblable aux coupes LBF précédentes et présentent L’avantage d’être actives sur un plus grand ensemble de solutions entières et fractionnaires. La contrepartie à cela est la faiblesse de la borne associée. Pour identifier les coupes violées, on a développé des algorithmes de séparation heuristiques basés sur un même principe. Celui-ci préconise leur construction en augmentant la taille de l’ensemble des variables concernées de façon itérative jusqu’à ce que la borne de la coupe associée soit suffisante pour constituer une coupe violée. Enfin, on produit des tests numériques sur un ensemble riche d’instances qui prouvent l’efficacité de nos travaux puisque nous résolvons 13 nouvelles instances de la littérature en moins de 10000 secondes. De plus, on réduit les temps de calcul des instances résolues de 30% en moyenne.----------ABSTRACT : In this master’s thesis, we intend to solve the vehicle routing problem with stochastic demands by means of an integer L-shaped algorithm. We use lower bounding functionals (LBF) to speed up the resolution process. The problem is similar to classic vehicle routing problems, except that customer demands are random variables which values are only revealed when they are visited. These variables follow a normal distribution and are independantly and equally distributed. The problem is formulated as an integer two-stages stochastic programming model. The first stage decision variables are used to define a priori routes designed to minimize the total expected recourse cost. Each time a vehicle reaches a client, if his demand can’t be fully served then a failure is said to occur. In such a situation, second-stage decisions are made and consist in returning to the depot to load or unload goods and going back to the current client to resume the planned route. This recourse action is commonly referred to as the simple recourse. A preliminary step to the resolution consists in relaxing the model by temporarily removing To identify violated cuts, we developped heuristic separation procedures based on one principle. Their purpose is to construct cuts by increasing iteratively the size of the involved variables set until the associated lower bound is enough to form a violated cut. Finally, we produce numerical experiments involving a rich set of instances which prove the efficiency of our work as 13 new instances from the literature could be solved to optimality in less than 10000 seconds. Moreover, we reduce the computing times of the solved instances by 30% on average.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Guy Desaulniers, Walter Rei and Ola Jabali
Date Deposited: 01 Apr 2015 15:36
Last Modified: 27 Jun 2019 16:48
PolyPublie URL: https://publications.polymtl.ca/1603/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only