Khtatfa, Sahbi (2014). « Algorithme de séparation locale pour le problème de tournées de véhicules avec demandes stochastiques » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique de gestion.
Fichier(s) associé(s) à ce document :
|
PDF
Télécharger (4MB) |
|---|
Résumé
Le problème de tournées de véhicules avec demandes stochastiques (PTVDS) consiste à trouver des routes optimales à assigner aux véhicules et permettant de répondre à des demandes inconnues des clients dispersés géographiquement. En effectuant une route, la présence de l'incertitude au niveau des demandes des clients engendre des problèmes de rupture de stock pour les véhicules. Lorsqu'une telle situation survient, une action corrective doit-être appliquée (i.e., le véhicule fait un retour au dépôt pour recharger la capacité avant de reprendre la route). De telles actions entraînent des coûts supplémentaires et l'introduction de ces coûts dans les modèles d'optimisation (PTVDS) rendent ceux-ci beaucoup plus complexes à résoudre que les problèmes déterministes. L'objectif principal de cette recherche est de produire une heuristique efficace pour résoudre le PTVDS pour des instances de grandes tailles. L'heuristique proposée permettra de trouver des routes à coût minimum et de satisfaire toutes les contraintes exigées par le modèle. Pour résoudre ce problème, nous utiliserons la méthode de séparation locale. Cette méthode se base sur une formulation mathématique combinatoire, dont le principe est de décomposer le problème initial en sous-problèmes par l'ajout de contraintes de séparation locale. Chaque sous-problème est par la suite résolu à l'aide d'un solveur spécialisé. Pour le cas du PTVDS, nous utiliserons comme solveur l'algorithme Integer L-Shaped proposé par (Jabali et al., 2012). L'analyse numérique que nous avons mené illustre empiriquement que l'heuristique est en mesure d'obtenir des solutions de qualité équivalente à l'approche exacte (i.e.; des solutions optimales ou quasi-optimales) en réduisant considérablement les temps de calculs. Ainsi, notre algorithme peut résoudre plus facilement les instances qui sont difficilement résolvables par l'algorithme Integer L-Shaped. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : problème des tournées de véhicules avec demandes stochastiques, heuristique, séparation locale, algorithme Integer L-Shaped
| Type: | Mémoire accepté |
|---|---|
| Informations complémentaires: | Le mémoire a été numérisé tel que transmis par l'auteur. |
| Directeur de thèse: | Rei, Walter |
| Mots-clés ou Sujets: | Algorithme stochastique, Coût de transport, Heuristique, Livraison à domicile, Logistique, Optimisation, Problème de transport (Programmation mathématique), Transport des marchandises |
| Unité d'appartenance: | Faculté des sciences > Département d'informatique École des sciences de la gestion > Département de management |
| Déposé par: | Service des bibliothèques |
| Date de dépôt: | 24 nov. 2014 13:56 |
| Dernière modification: | 24 nov. 2014 13:56 |
| Adresse URL : | http://archipel.uqam.ca/id/eprint/6342 |
| Modifier les métadonnées (propriétaire du document) |
Statistiques |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
