Modèle de localisation optimale La p-médiane

Modèle de localisation optimale La p-médiane

La p-médiane consiste à choisir la configuration géographique des unités d’offre de manière à minimiser la somme des distances parcourues sous une série de contraintes énoncées par l’utilisateur[25]. Le modèle assure la couverture efficace du milieu. Dans bien des cas de services, l’hypothèse du plus court chemin est tout à fait soutenable. La p-médiane présente l’avantage d’être facilement adaptée aux spécificités du problème posé par l’utilisateur et d’être résolue par des méthodes efficaces, rapides et souples (Hanjoul et Peeters[21], 1985 ; Hansen, e.a.[22], 1987). Ce modèle permet non seulement de s’attacher à la forme des aires et aux localisations optimales, mais également de suggérer le nombre idéal de services et de simuler des solutions sous diverses contraintes et hypothèses.

Formulation mathématique 

Le problème consiste donc à choisir la configuration géographique des unités d’offre ; de manière à minimiser la somme pondérée des distances parcourues par les utilisateurs[7]. • i et j : indices des points de demande Recherche opérationnelle: Localisation optimale en télécommunication DIONE c Master2 UCAD 2012 Modèle de localisation optimale La p-médiane Formulation mathématique : 8 • ai : Demande affectée au point i • dij : la distance du noeud i au noeud j • p : nombre d’activités à localiser.

Cette formulation suppose que tous les sites de demande ont la qualité potentielle d’être localisés et que les p sites seront localisés en des points distincts. Le problème p-médian est réputé appartenir à la classe des problèmes connus comme NP-difficiles[26] : ses solutions issues d’algorithmes linéaires deviennent insolubles au fur et à mesure que le nombre des variables( sites potentiels d’offre et demande) augmente avec une progression exponentielle de la taille du problème. En effet, selon une logique d’analyse combinatoire, le nombre de solutions à examiner est en fonction de n, le nombre de sites de demande, et p, le nombre d’équipements susceptibles d’être localisés est : C p n = n! p!(n − p)! ce qui signifie par exemple que si l’on devait simplement chercher à localiser 15 sites au milieu d’un nombre total de 100 sites et que l’on dispose d’un ordianteur capable de réaliser un million d’opérateurs par seconde, le temps requis pour parvenir à la solution optimale serait de huit millénaires[?].

Algorithme de résolution 

Algorithme Génétique Les algorithmes génétiques font partis de la famille des algorithmes dits  » stochastique itératif « . Entre 1960 et 1970, John Holland[23] sur la base des travaux précédents, développa les principes fondamentaux de ces derniers dans le cadre de l’optimisation mathématique.

L’ouvrage de Goldberg[16] paru en 1989 qui décrit l’utilisation des algorithmes génétiques dans le cadre de résolution de problèmes concrets a permis une meilleure connaissance de ces derniers par la communauté scientifique et le début d’un intêret accru pour ces techniques d’optimisation. Une des particularités séduisantes de ce type d’algorithme réside dans l’absence d’hypothèse particulière sur la régularité de la fonction  » objectif  » de l’optimisation. Aucune hypothèse sur la continuité, la dérivabilité de cette fonction n’est requise ce qui rend très large le domaine d’application de tel algorithme. Cette méthode permet de traiter des problèmes très complexes et ne se réduit pas à la simple recherche d’optima d’une fonction. 

Base et fonctionnement de l’algorithme génétique

Les algorithmes génétiques sont des procédures itératives qui s’inspirent des mécanismes de sélection naturelle et des phénomènes génétiques. Ce type d’algorithme utilise un vocabulaire similaire à celui de la génétique. Ainsi pour un problème d’optimisation donné, on parlera d’individu dans une population pour représenter un point de l’espace d’état ; ce dernier étant composé d’un chromosome généralement voir de plusieurs dans certains cas ; les chromosomes étant eux-mêmes constitués de gènes représentant les données et les informations de l’individu. L’algorithme génère de façon itérative de nouvelles populations d’individus sur lesquelles on applique des principes de sélection, de croisement, de mutation telle qu’on peut en voir en génétique. L’idée directrice est d’assimiler l’application de l’algorithme au processus d’évolution naturelle en milieu hostile.