École Nationale Supérieure de
Techniques Avancées

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.