Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
LE PROBLEME DU P-MEDIAN
Afin d’avoir une multitude de visions pour notre problématique, nous avons consulté la thèse de Jérôme Baray [BARAY, 2012], professeur à l’Université Paris-Est Créteil. Cette thèse est fondée sur un exemple d’étude dont le problème de base est de localiser un nombre p d’activités devant fournir n clients de façon à ce que la somme des distances séparant chaque activité aux clients les plus proches soit minimale. Cela entraîne, de façon systémique, une optimisation du nombre de points de vente et leurs emplacements en connaissant la localisation des consommateurs, les coûts de déplacements et la demande.
Dans sa thèse, J. Baray distingue deux catégories de clientèle. La première domiciliée dans une zone proche du point de vente, nommée zone de chalandise, et attirée par un point de vente jouant le rôle d’un pôle, représentant une attraction polaire. La deuxième ayant un caractère plus aléatoire, est induite par le flux de clientèle passant à proximité du point de vente interceptée par ce dernier, représentant une attraction passagère.
A l’issue de cette thèse, J. Baray présente différents moyens de résolution pour l’optimisation multiobjectif en se basant sur le principe de l’attraction polaire. L’une de ces méthodes, présentée sous le nom de p-médian (p-MP) « qui représente une variante de la classe des problèmes de localisation dans le domaine de l’optimisation combinatoire » [GAY, 2011], développée au début du XXème siècle par Alfred Weber [WEBER, 1909]qui était un économiste, sociologue, pédagogue et professeur d’université. Ce modèle peut être appliqué à une multitude de problèmes comme la localisation des services d’urgence (police, pompiers, urgences médicales), les réseaux de communication et informatique (localisation des fichiers informatiques sur une série de serveurs identifiés), les applications militaires (centres militaires stratégiques), les activités des services public ou privé (les magasins, centres commerciaux, postes), les activités de transport (arrêts de transport en commun, entrepôts), l’intelligence artificielle et les modèles statistiques (partition de nuages de points), ainsi que d’autres centres d’applications [HANDLER et al, 1979].
Le problème p-MP appartient à la classe des problèmes NP-complets, à savoir que l’algorithme devient insoluble quand le nombre de variables (activités et clients) augmente avec une progression exponentielle de la taille du problème.
La résolution du p-médian repose sur l’hypothèse qu’il existe déjà un réseau constitué de noeuds ou de points et de liens entre un point i et un point j, qui engendra un coût de déplacement représenté par la distance dіj.
ALGORITHME HEURISTIQUE ET METAHEURISTIQUE
A ce jour, les problèmes d’optimisation combinatoire, qui sont des problèmes NP-difficiles, ne possèdent pas d’algorithme apte à trouver la solution optimale en un temps raisonnable. De ce fait, les chercheurs ont réussi à développer différentes méthodes de résolution qui sont divisés en deux grandes classes : les méthodes exactes (complètes) et les méthodes approchés (incomplètes). Les méthodes dites approchées permettent de trouver une solution admissible qui n’est pas forcement optimale dans un temps raisonnable. Ce type de résolution peut être appliqué à n’importe quelle classe de problèmes. Ces dernières peuvent être divisées en deux classes : heuristiques et métaheuristiques.
Une heuristique est une technique de résolution adaptée à un problème précis, autrement dit, c’est une règle basée sur l’expérience qui permet d’avoir rapidement une solution presque optimale de haute qualité [NINGCHUAN, 2015, p.230] d’un problème, sans promettre une solution optimale. Nous pouvons citer à titre d’exemple l’heuristique MOMS (Maximum Occurrences in Clauses of Minimum Size) qui permet de sélectionner la variable ayant le plus d’occurrences dans les clauses les plus courtes. L’heuristique JW (Jeroslow-Wang) est un autre exemple d’heuristique, basé sur la longueur des clauses et qui permet d’avoir le poids des autres apparaissant dans les clauses les plus petites.
Le terme « méta-heuristique » signifie « trouver dans un niveau supérieur ». De ce fait, les méta-heuristiques ont été créées dans le but de trouver des solutions, pas toujours optimales, mais en tout cas très proches de l’optimum. Ce type de méthodes approchées possède huit propriétés fondamentales :
– Elles sont des stratégies qui permettent de guider la recherche d’une solution optimale.
– Le but de leurs utilisations est d’explorer l’espace de recherche efficacement afin de déterminer des solutions (presque) optimales.
– Les techniques qui constituent des algorithmes de type méta-heuristique vont de la simple procédure de recherche locale à des processus d’apprentissage complexes.
– Les métaheuristiques sont en général non-déterministes et ne donnent aucune garantie d’optimalité.
– Les méta-heuristiques peuvent contenir des mécanismes qui permettent d’éviter d’être bloqué dans des régions de l’espace de recherche.
– Les concepts de base des méta-heuristiques peuvent être décrit de manière abstraite, sans faire appel à un problème spécifique.
– Les méta-heuristiques peuvent faire appel à des heuristiques qui tiennent compte de la spécificité du problème de niveau supérieur.
– Les méta-heuristiques peuvent faire usage de l’expérience accumulée durant la recherche de l’optimum, pour mieux guider la suite du processus de recherche.
UNE PROBLEMATIQUE LIEE A L’AFFECTATION OPTIMALE DU NSA AUX CARE
l’art avait pour but de rassembler les informations nécessaires à la définition de notre problème et des différents moyens existant quant à la résolution de celui-ci. Comme indiqué précédemment, beaucoup de chercheurs se sont intéressés au sujet d’optimisation multiobjectif et ont présenté une multitude de méthodes et solutions associées, mais on s’est concentré sur le problème du p-médian qui touche directement notre sujet. Dans notre cas, le problème se traduit par la formule mathématique suivante composée de deux fonctions objectifs : Fonction objectif 1 : ΣΣ(???∗??????????∗???)?? min Fonction objectif 2 : Σ??? max tels que : Σ(???∗???)≤??? ???∈{0,1}, 1≤?≤? ?? 1≤?≤? La première fonction objectif sert à minimiser la distance parcourue entre un bâtiment et son CARE d’attribution, et la seconde sert à maximiser la capacité des CARE. Le problème du p-médian est en parti utilisé par le module Emplacement-Allocation de ArcGIS qui est un Système d’Information Géographique (SIG), soit un système de gestion, d’organisation, d’analyse, de communication et de diffusion d’informations géographiques. La prochaine partie de ce projet est une explication de ce module utile à la résolution de notre problème. Afin de travailler sur ce logiciel, différentes couches sont nécessaires dont : – les bâtiments de la ville (avec le nombre de personnes à évacuer), – les CARE de Nice (avec leur capacité d’accueil), – et le réseau routier de Nice.
PRESENTATION DE LA FONCTION
Le module emplacement-allocation permet d’identifier des emplacements de telles manières que les ressources répondent à un ensemble d’emplacements de demandes. Ainsi, il est possible de minimiser les ressources nécessaires, d’optimiser la part de marché ou la fréquentation ou bien encore de tenter de réduire les coûts pour répondre à une demande. L’outil de résolution de ce module choisit les meilleur(e)s emplacements ou allocations parmi un ensemble d’emplacements en entrée. Les ressources en entrée produisent des biens ou des services et les points de demandes consomment ces biens et services. L’objectif de ce module est de localiser les ressources qui permettent de répondre le plus efficacement à la demande. L’outil de résolution de problème permet d’analyser différents moyens d’allocation des ressources aux points de demande. La solution est le scénario qui permet d’allouer la plus grande demande aux ressources disponible tout en minimisant l’impédance8 totale. La solution comprend les ressources, les points de demande qui leurs sont associées et les lignes reliant les points de demande à leurs ressources. Le module d’emplacement-allocation peut être configuré pour résoudre des types de problèmes dit “courants”, tels que : • une commune souhaite trouver les meilleurs emplacements pour des casernes de pompier de telle manière à ce que chaque habitation soit à moins de 10min d’une caserne. • en cas de séisme, une commune souhaite identifier les meilleurs emplacements afin de déployer des centres d’accueil de capacité limité, pour prendre en charge la population. • une enseigne de la grande distribution souhaite voir quels emplacements potentiels de points de vente elle doit développer afin d’attirer 15% du marché de la région. • une gendarmerie souhaite positionner des équipes en fonction des incidents de la journée passée.
ALGORITHMES DE RESOLUTION
Le solveur d’emplacement-allocation » de Network Analyst résout les problèmes à l’aide de l’heuristique (cf. 2.3. Algorithme heuristique et métaheuristique).
Premièrement, le solveur commence par créer une matrice de coût origine destination (matrice OD) du plus court chemin entre toutes les ressources et les points de demande le long du réseau. Ensuite, une version modifiée de la matrice OD est créée à l’aide d’un processus appelé « modification de Hillsman ». Cette modification permet à cette même heuristique de résoudre divers types de problèmes différents. Dès lors, le solveur d’emplacement-allocation, génère un ensemble de solutions semi-aléatoires et applique une heuristique de « substitution de sommet » (Teitz et Bart) pour perfectionner ces solutions afin de créer un sous-ensemble de bonnes solutions. Puis, une métaheuristique effectue des combinaisons de ce sous-ensemble de bonnes solutions pour créer de meilleures solutions. Finalement, lorsqu’aucune amélioration supplémentaire n’est possible, la métaheuristique retourne la meilleure solution trouvée.
« La combinaison d’une matrice modifiée, de solutions initiales semi-aléatoires, d’une heuristique de substitution de sommets et d’une métaheuristique d’affinage permet d’obtenir rapidement des résultats proches de l’optimum. » Arcgis Desktop – ESRI.
MODELISATION DU MODELE MULTI-OBJECTIF ET APPLICATION SUR LE QUARTIER DU « CENTRE » A NICE
Le module emplacement allocation sous ArcGIS présenté précédemment, propose 7 types de problèmes différents afin de traiter des types de questions spécifiques. Les 4 premiers types de problèmes seront développés par la suite car ils se rapprochent le plus de notre étude, les autres traitant plutôt des problèmes de concurrence entre les ressources. Ci-dessous la liste des différents problèmes pouvant être résolut avec le module “Emplacement-Allocation” :
• Minimiser l’impédance
• Optimiser la couverture
• Optimiser la couverture de capacité
• Minimiser les ressources
• Optimiser la fréquentation • Optimiser la part de marché
• Part de marché cible Afin de mieux comprendre la fonction de chaque type de problème, une approche sur un territoire réduit a été choisi. Dès lors, le territoire est défini comme étant un regroupement de 25 IRIS9 sur notre territoire d’étude formant le cœur de ville. Ce contour regroupe deux quartiers : Jean-Médecin et la Vieille Ville, pour un souci de praticité nous appellerons ce groupement : « Le Centre ». Voici notre instance d’étude.
|
Table des matières
INTRODUCTION
PARTIE 1. PRESENTATION DU PFE
1.1 CONTEXTUALISATION
1.2 ZOOM SUR NOTRE TERRITOIRE D’ETUDE
1.3 PROBLEMATIQUE
PARTIE 2. ETAT DE L’ART
2.1 LE PROBLEME DU P-MEDIAN
2.2 PROBLEME DU BIN PACKING
2.3 ALGORITHME HEURISTIQUE ET METAHEURISTIQUE
2.4 UNE PROBLEMATIQUE LIEE A L’AFFECTATION OPTIMALE DU NSA AUX CARE
PARTIE 3. METHODE ET RESULTATS
3.1.1 Présentation de la fonction
3.1.2 Algorithmes de résolution
3.2 MODELISATION DU MODELE MULTI-OBJECTIF ET APPLICATION SUR LE QUARTIER DU « CENTRE » A NICE
3.2.1 Minimiser l’impédance
3.2.2 Optimiser la couverture
3.2.3 Optimiser la couverture de capacité
3.2.4 Minimiser le nombre de ressources
PARTIE 4. EXPERIMENTATIONS
4.1 CORRECTIONS DU RESEAU EXISTANT
4.2 SCENARIO 1 : REEVALUATION DE LA CAPACITE DES CARE
4.2.1 Affectation des bâtiments au CARE le plus proche
4.2.2 Capacités théoriques et surcharge
4.3 SCENARIO 2 : CREATION DE NOUVEAUX CARE
PARTIE 5. COMMUNICATION A LA POPULATION
5.1 CONTEXTUALISATION
5.2 DES DICRIM PEU INTERACTIFS
5.3 LIER GESTION DU RISQUE ET NOUVELLES TECHNOLOGIES
CONCLUSION
ANNEXES
TABLE DES ILLUSTRATIONS
REFERENCES
Télécharger le rapport complet
