Algorithme de séparation locale pour le problème de tournées de véhicules avec demandes stochastiques

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 :
[img]
Prévisualisation
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 et technologie
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

Statistiques

Voir les statistiques sur cinq ans...