Master's thesis (2014)
|
Open Access to the full text of this document Terms of Use: All rights reserved Download (625kB) |
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.
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.
Department: | Department of Mathematics and Industrial Engineering |
---|---|
Program: | Génie industriel |
Academic/Research Directors: |
Guy Desaulniers |
PolyPublie URL: | https://publications.polymtl.ca/1603/ |
Institution: | École Polytechnique de Montréal |
Date Deposited: | 01 Apr 2015 15:36 |
Last Modified: | 08 Nov 2022 12:39 |
Cite in APA 7: | Leuliet, A. (2014). Nouvelles coupes pour le problème de tournées de véhicule avec demandes stochastiques [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1603/ |
---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads