DURAN, Monsieur Cristian (2019) Résolution efficace du problème du p-centre PFE - Projet de fin d'études, ENSTA.

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

[img]
Prévisualisation
PDF
594Kb

Résumé

Le problème d’optimisation combinatoire du p-centre consiste à choisir p localisations d'un ensemble de sites dont les distances entre les clients et sites sont connues, afin d'y installer p entrepôts de façon à minimiser la distance maximale d’un client à l’entrepôt le plus proche. Différentes méthodes de résolution exacte et d'approximation ont été proposées. La méthode la plus efficace considère la résolution d'une série de problèmes de couverture par des ensembles associés. L'objectif de ce travail a été d'améliorer la performance d'une méthode qui calcule une borne inférieure au problème du p-centre. La recherche s'est orientée vers une étude polyèdrale sur ces sous-problèmes. Ce rapport présente l'étude théorique réalisée et les résultats obtenus lors de la mise en œuvre des différents algorithmes de génération de coupes. Ce travail de stage de recherche a été réalisé au laboratoire de l'Unité de Mathématiques Appliquées (UMA) de l'École Nationale Supérieure de Techniques Avancées (ENSTA) pour obtenir le diplôme de Master Parisien de Recherche Opérationnelle (MPRO) de l'Université Paris-Saclay.

Type de document:Rapport ou mémoire (PFE - Projet de fin d'études)
Mots-clés libres:programmation mathématique, problème du p-centre, problème de couverture par des ensembles, génération de coupes
Sujets:Mathématiques et leurs applications
Code ID :7948
Déposé par :Cristian DURAN
Déposé le :27 janv. 2020 15:57
Dernière modification:27 janv. 2020 15:57

Modifier les métadonnées de ce document.