Étude de la séparation des inégalités valides pour le problème de tournées de véhicules avec plusieurs dépôts

Groiez, Mounira (2007). « Étude de la séparation des inégalités valides pour le problème de tournées de véhicules avec plusieurs dépôts » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (12MB)

Résumé

Le problème de tournées de véhicules avec plusieurs dépôts et des dates fixes pour les trajets (nommé MDVSP) est un des problèmes les plus importants en optimisation combinatoire; le MDVSP est un problème NP-complet. Dans le présent mémoire nous présentons un algorithme de type « Branch-and-Cut » pour la résolution du MDVSP. Notre algorithme combine la méthode de séparation et évaluation progressive et une procédure de séparation des inégalités valides, qui consiste à détecter certains trous impairs et à les lifter. Nous présentons aussi les résultats des tests effectués et l'analyse des comparaisons entre notre algorithme et les méthodes utilisées par le logiciel CPLEX. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Le problème de tournées de véhicules avec plusieurs dépôts, séparation des inégalités valides, trous impairs, algorithme de « Branch-and-Cut » pour la résolution du MDVSP

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Marcotte, Odile
Mots-clés ou Sujets:	Inégalité (Mathématiques), Problème NP-complet, Optimisation combinatoire, Résolution de problème
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Service des bibliothèques
Date de dépôt:	27 oct. 2015 13:34
Dernière modification:	27 oct. 2015 13:34
Adresse URL :	http://archipel.uqam.ca/id/eprint/7362

Modifier les métadonnées (propriétaire du document)

Statistiques