<  Retour au portail Polytechnique Montréal

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

Alexandre Leuliet

Mémoire de maîtrise (2014)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (625kB)
Afficher le résumé
Cacher le résumé

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, Walter Rei et Ola Jabali
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 nov. 2022 12:39
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

Actions réservées au personnel

Afficher document Afficher document