Mémoire de maîtrise (2014)
|
Libre accès au plein texte de ce document Conditions d'utilisation: Tous droits réservés Télécharger (625kB) |
Résumé
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.
Abstract
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.
Département: | Département de mathématiques et de génie industriel |
---|---|
Programme: | Génie industriel |
Directeurs ou directrices: |
Guy Desaulniers |
URL de PolyPublie: | https://publications.polymtl.ca/1603/ |
Université/École: | École Polytechnique de Montréal |
Date du dépôt: | 01 avr. 2015 15:36 |
Dernière modification: | 08 avr. 2024 08:49 |
Citer en APA 7: | Leuliet, A. (2014). Nouvelles coupes pour le problème de tournées de véhicule avec demandes stochastiques [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1603/ |
---|---|
Statistiques
Total des téléchargements à partir de PolyPublie
Téléchargements par année
Provenance des téléchargements