Où le marché est il localisé et où faut il implanter le point de vente de façon à capter une part suffisante de ce marché afin que l’activité envisagée soit performante ?

Les modèles de localisation-allocation regroupent d’une manière générale cinq composants de baset :

• la fonction objectif : c’est une fonction qui intègre la notion de distance séparant les consommateurs aux emplacements potentiels des points d'offre ainsi éventuellement qu’une mesure de leur attractivité. Elle quantifie donc l’accessibilité globale des points d'offre vis-à-vis des clients. les points de demande : ils représentent le niveau de la demande concernant un ensemble de biens sur une zone géographique ( région, ville, quartier..).
• Les points de demande correspondent en général à des cellules de forte densité de population disposant d’un pouvoir d’achat intéressant.
• les emplacements potentiels : ce sont les localisations possibles en termes de disponibilité foncière, coût, accessibilité.
• la matrice d’éloignement ou de temps : cette matrice rend compte de la distance géographique ou temporelle séparant les emplacements potentiels des points de demande. Plus précisément, ces distances peuvent être mesurées en distance kilométrique à vol d’oiseau, en cheminement piétonnier, en temps de conduite...
• la règle d’allocation : cette règle spécifie de quelle manière les emplacements potentiels seront alloués aux points de demande. On peut par exemple considérer dans le cas le plus simple que chaque client fréquentera le point de vente le plus proche de son domicile, la règle d’allocation étant alors la proximité géographique. Il est possible d’envisager des règles plus complexes à savoir par exemple que la fréquentation d’un point de vente dépendra de la saison et se reportera sur un autre emplacement à d’autres moments de l’année.

Ainsi, compte tenu de ces cinq facteurs décrivant entièrement un modèle de localisation-allocation donné, l’espace commercial peut être apprécié sous la forme d’un réseau constitué de nœuds caractérisés par une certaine demande et/ou pouvant accueillir un point d'offre, les segments liant les nœuds de ce réseau représentant les éloignements. A ce réseau doit être néanmoins associé une fonction objectif qui, exprimé le plus souvent sous forme mathématique, spécifie la manière selon laquelle les clients opteront pour tel ou tel emplacement potentiel. Dans le cas où n’existerait qu’un seul point d'offre à localiser, le problème revient à le placer virtuellement tour à tour à l’un ou à l’autre des emplacements potentiels puis à choisir celui pour lequel la fonction objectif est la plus favorable.

Tout se complique si l’on doit localiser plusieurs activités, car le nombre de nœuds étant souvent élevé, il devient pratiquement impossible physiquement, même avec des ordinateurs puissants, de calculer la fonction objectif exhaustivement pour chacune des combinaisons d’emplacements envisageables. Il a donc été développé pour cela des solutions approchées par la mise en œuvre d’heuristiques qui conduisent, non pas à une série de localisations optimales mais tout au moins à un niveau satisfaisant de la fonction objectif. L’un des premiers modèles de localisation-allocation a été développé par Alfred Weber avec comme problématique la réduction du coût total de transport de matières premières à l’usine et de l’usine au marché.

2.1 Le modèle p-médian

La recherche opérationnelle en matière de localisations d'activités a été l'une des préoccupations majeures dans de nombreux domaines d'applications (logistique, transport, grande distribution, services bancaires, assurance). En particulier, en ce qui concerne la localisation de points de vente ou de services ou même d'entrepôts, une problématique essentielle consiste à trouver les localisations pour un nombre p d'activités devant fournir n clients de telle manière que la somme de l'ensemble des « distances » (au sens le plus large du terme), entre chaque activité et les clients, soit minimale.

Ce problème lié à un réseau discrétisé bien identifié est classiquement connu sous le nom de p-médian [17] [18] qui trouve son origine au début du XX^ème siècle dans les réflexions d'Alfred Weber [19] sur la meilleure manière de placer un centre de production par rapport aux sources de matières premières.

En pratique, le problème du p-médian (nommé en abrégé p-MP) est soulevé dans la plupart des réseaux qu'ils soient routiers, aériens ou téléphoniques [20] [21] . Handler et Mirchandani [22] ont dressé la liste très variée des applications potentielles du modèle p-médian comme les décisions de localisation pour les services d'urgence (police, pompiers, urgences médicales), les réseaux informatiques et de communication (localisation des fichiers informatiques sur une série de serveurs identifiés), les applications militaires (centres stratégiques), les activités de service 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 nuage de points).

Mais, les applications dédiées à la distribution ont été mises en œuvre dans les années 1980 avec comme objectif principal d'optimiser le nombre de points de vente et leurs emplacements, connaissant la localisation précise des consommateurs, les coûts de déplacement et éventuellement la demande [23] [24] [25] . Le présent exposé même s'il se concentre sur l'application à la localisation spatiale de services, pourrait très bien être directement transposé aux autres domaines précédemment cités.

Il existe bien entendu de nombreux autres modèles dits de localisation-allocation que le p-médian, plus ou moins bien adaptés selon les cas. On peut citer parmi eux le modèle p-centré [26] qui recherche les p localisations les plus proches des clients: créer p activités, en assignant chaque client à l'une d'entre elles, de telle manière que la distance maximale de n'importe quelle activité à l'ensemble de ses clients soit minimale. Cette problématique, dénommée également minimax, cadre bien avec la localisation d'ambulances ou de stations de pompiers qui doivent être les plus proches possibles de toutes les zones d'intervention envisageables.

Bien que le modèle p-médian ne s'appuie que sur la notion de distance (ou de coût de déplacement) entre clients et sites potentiels d'activité, la compilation des données sur les localisations de ces différents acteurs pour trouver une localisation proche de l'optimal demande beaucoup d'efforts et de temps de calcul ainsi que nous le constaterons plus loin.

2.2 Formulation mathématique du p-MP

La résolution du problème p-médian n'échappe pas à sa nécessaire rationalisation consistant à l'exprimer en langage mathématique : le p-MP sous-entend l'existence d'un réseau constitué de nœuds ou points et de liens, ces derniers étant associés à un coût de déplacement représenté par la distance di,j (distance du point i au point j). L'objectif est ainsi de trouver un emplacement optimal pour p activités au sein des nœuds du réseau en cherchant à minimiser la distance totale entre les p activités et les clients qui leur sont associés (un client est associé à une activité s'il se trouve plus proche de cette dernière que de toutes les autres). Les modèles p-médian pondérés et non-pondérés se différencient par le fait que les premiers tiennent compte de la demande ai au point i avec l'objectif de minimiser la somme totale des distances pondérées par la demande.

D'une manière générale, la formulation mathématique du p-MP s'écrit de la façon suivante [27] :

Minimiser a_i d_ij x_ij                      

représente la fonction objectif,      (1)

avec x_ij = 1,   " i,     assure que tous les clients sont assignés à une activité et une seule, (2)

x_ij ‹= y_j,   " i, j    empêche d'assigner un client à une activité si elle n'est pas ouverte,  (3)

y_j = p,         le nombre total d'activités est p,    (4)

x_ij, y_j Qque soit {0,1},  " i, j       nature binaire des variables x_ij, y_j   (5)

où

Cette formulation suppose que tous les nœuds du réseau ont la qualité de localisation potentielle pour les activités et que les p activités seront placées en des points distincts. Dans le cas non-pondéré, les demandes a_i sont toutes égales à 1. Il est également possible d’introduire dans ce modèle, un coût c_j d’ouverture des activités et dans ce cas, la fonction objectif devient :

Minimiser a_i d_ij x_ij   +  c_j y_j

Ce coût est également susceptible de représenter un niveau de préférence sur le choix géographique des implantations (chaque implantation potentielle recevant une note en fonction de sa qualité à pouvoir recevoir une activité). Mais, ces coûts liés aux nœuds d’implantation doivent en tous les cas être mesuré sur la même échelle que les distances di,j puisque ces deux quantités sont additionnées dans la fonction objectif.

Le problème p-MP appartient à la classe des problèmes connus comme étant NP-complets [28] : ses solutions issues d'algorithmes linéaires deviennent insolubles au fur et à mesure que le nombre des variables (activités et clients) augmente en progression exponentielle. En effet, selon une logique d'analyse combinatoire, le nombre de solutions à examiner est en fonction de n, le nombre de  nœuds, et p, le nombre d'activités à placer :

ce qui signifie par exemple que si l'on devait chercher à placer 15 points de vente au milieu d'un réseau de 100 clients et que l'on dispose d'un ordinateur capable de réaliser un million  d'opérations par seconde, le temps requis pour parvenir à la solution optimale serait de huit millénaires [29] !

Dans le cas où l'on voudrait solutionner tous les problèmes p-médian (p variant de 1 à p activités à placer) si on ne connaît que le nombre maximum p d'activités à placer, le nombre de combinaisons à étudier serait alors de:

Il existe un grand nombre d'heuristiques pour trouver une solution acceptable au problème p-Médian malgré le fait que toutes ces solutions ne convergent que vers des optima locaux et non vers une solution globale et qu'il ne soit pas possible a priori de connaître le niveau d'optimalité de cette solution.

2.3 Les algorithmes de résolution du p-MP

Dans les algorithmes de résolution fondamentaux, on trouve l'algorithme flou, l'algorithme de recherche de voisinage, une heuristique de substitution [30] et ses variantes [31] , cette dernière catégorie étant l'une des plus robustes selon Densham et Rushton [32] .

D'une façon générale, les heuristiques se rangent en deux classes [33] : les algorithmes de construction qui permettent de rechercher des localisations avec un degré d'optimalité faible et les algorithmes d'amélioration destinés à améliorer les résultats fournis par les algorithmes de construction. Alors que l'algorithme flou est du type construction, l'heuristique de substitution et l'algorithme de recherche de voisinage ont une approche d'amélioration

Localisation d'une activité unique dans la problématique du p-MP : le 1-médian

Examinons tout d'abord la recherche de solutions dans le cas le plus simple, la localisation d'une activité unique ou problème 1-médian. Dans le cas où, plus de la moitié de la demande a_i  est localisée en un point, une des solutions optimales consiste à placer l'activité en ce nœud. Et si ce nœud concentre plus de la moitié de la demande, cette localisation est alors la localisation optimale unique [34] .

La résolution du cas le plus général a été donnée par Goldman [35] . Elle consiste à choisir aléatoirement un nœud d'extrémité de branche sur le réseau et si au moins la moitié de la demande n'est pas fixée en ce nœud à le supprimer (ainsi que le lien) et à reporter sa demande sur le nœud suivant. Si l'un des nœuds du réseau concentre plus de la moitié de la demande, alors l'activité est à localiser en ce point et on peut calculer la distance totale pondérée par la demande.

Un exemple concret plus explicite selon Daskin [36] est donné par le réseau suivant qui compte une demande totale de 48 (la demande au point x est représenté par h_x).

Aucun des nœuds ne compte plus de la moitié de la demande. Si l'on considère donc le point A dont la demande égale à 10 est inférieure à 48/2 = 24, on reporte cette demande sur le point B en supprimant le point A, demande qui atteint alors 5 + 10 = 15 :

Figure 5 : Méthode de résolution du 1-médian : étape 1

Figure 6 : Méthode de résolution du 1-médian :étape 2

La demande en B égale à 15 est toujours inférieure à 24 (comme celle de tous les autres points). Supprimons alors le point D où la demande, 12, est la plus faible en la reportant sur le point adjacent C:

Figure 7 : Méthode de résolution du 1-médian : étape 3

Comme les demandes de B, C et D sont toujours inférieures à 24, supprimons E et reportons sa demande sur C. On s'aperçoit alors que la demande de C égale à 33 est supérieure à la demande totale divisée par deux (24), ce qui signifie que C est le point optimal sur lequel doit être placée l'activité:

Figure 8  : Méthode de résolution du 1-médian : étape 4

L'algorithme flou

L'algorithme flou consiste tout simplement à localiser les activités sur le réseau une par une, puis à utiliser une procédure de voisinage ou de substitution pour optimiser les localisations. Dans un premier temps, on choisit donc le meilleur emplacement pour la première activité ce qui est facile si on calcule la fonction objectif pour chaque nœud envisagé en retenant le nœud pour lequel cette fonction objectif est la plus faible. Ensuite, on localise un deuxième point envisageant chaque nœud (sauf celui déjà occupé) et en assignant à la localisation précédente, les nœuds qui lui sont les plus proches comparés au nœud examiné.

Figure 9 : Organigramme de l'algorithme flou

La fonction objectif est calculée de la même manière et on retient toujours comme second emplacement le nœud pour lequel cette fonction possède la valeur minimale.

Ce processus est réitéré autant de fois qu'il y a d'activités à localiser.

Résolution par les multiplicateurs de Lagrange [37]

Une méthode de résolution appartenant aux algorithmes de construction, plus classique mais moins performante, est représentée par les contraintes du p-médian relaxées à l'aide des multiplicateurs de Lagrange. Elle permet de transformer un problème contraint en un problème sans contraintes [38] . Nous la mentionnons pour mémoire. Appliquée à la relation (2) de la formulation générale du problème du p-médian, une relaxation par les multiplicateurs de Lagrange devient:

Minimiser a_i d_ij x_{ij  +} l_i [1 - x_ij ]        (1)

= ( a_i d_{ij +} l_i ) x_ij    +  l_I                                               avec x_ij = 1,   " i,     (2)

x_ij £ y_j,   " i, j,    (3)

y_j = p,         (4)

x_ij, y_j Î {0,1},  " i, j       (5)

Les coefficients l_i considérés comme fixes sont appelés multiplicateurs de Lagrange et la nouvelle fonction objectif à minimiser devient (1).  En appliquant une relation identique à la relation (3) de la formulation générale du p-médian, on démontre que les multiplicateurs de Lagrange peuvent être calculés à partir d'une formule récurrente, avec des multiplicateurs initialisés à une valeur quelconque:

l_iⁿ⁺¹ = max { 0, l_iⁿ - tⁿ (X_ijⁿ - Y_jⁿ)}

avec 

où        tⁿ : le pas de la procédure de Lagrange à la nième itération,

aⁿ : une constante généralement prise égale à 2,

UB : (upper bound) la plus petite limite supérieure de la fonction objectif,

Lⁿ : la fonction objectif de Lagrange (1) ci-dessus,

Y_jⁿ : la valeur optimale de la variable de localisation Y_j à la n^ième itération.

La méthode de résolution du p-médian par les multiplicateurs de Lagrange a été récemment utilisée dans des travaux de recherche en informatique pour déterminer sur quels serveurs en réseau il était préférable d'implanter les informations pour obtenir des traitements de calcul plus rapides au niveau de l'ensemble [39] . Le même algorithme a été utilisé dans le même esprit pour améliorer la configuration des réseaux de communication [40] .

Une méthode de résolution générale et (presque) exacte des problèmes de localisation développée par Homberg, Rönnqvist et Yuan fait appel à l'algorithme par les multiplicateurs de Lagrange en parallèle d'une procédure par séparation et évaluation (Branch and Bound en anglais) dans le cas où chaque nœud de demande est assigné à une activité et une seule [41] .

La procédure par séparation et évaluation est une méthode d'énumération implicite qui repose sur le principe de diviser les solutions en paquets. Plus précisément, on divise l'ensemble des solutions possibles d'un problème de localisation-allocation (ou plus généralement d'optimisation combinatoire) en sous-ensembles de plus en plus petits afin d'isoler dans l'un d’eux une solution optimale.

Le parcours est représentable par un arbre avec comme racine le problème de départ et toutes les combinaisons possibles, les branches représentant les sous-problèmes correspondant à des sous-ensembles de toutes les combinaisons admissibles.

L'exploration de l'arbre se fait vers des niveaux d'optimalité des solutions obtenues croissantes et la partition des ensembles de solutions (destinée à créer des branches) est produite en allouant un ou plusieurs clients d'une activité à une autre si l'on considère la solution explorée en cours.

Cette réallocation des clients se fait généralement par un processus aléatoire. La recherche de Homberg, Rönnqvist et Yuan montre que l'utilisation individuelle de la procédure par séparation et évaluation (grâce à l'algorithme commercial CPLEX) met jusqu'à 5 heures pour résoudre un problème de 30 activités à localiser en prenant en compte la position de 300 clients alors que la méthode associant cet algorithme avec les multiplicateurs de Lagrange ne met qu'une heure pour obtenir des solutions généralement meilleures.

On le voit, les meilleurs algorithmes de résolution même s'ils tournent sur des ordinateurs puissants (un ordinateur Sun Sparc 20/HS151 pour cette recherche) n'arrivent à résoudre dans un temps raisonnable que des problèmes de localisation-allocation de quelques centaines de nœuds. Dans certains cas (1 cas sur 71 cas étudiés), l'algorithme de Homberg, Rönnqvist et Yuan ne réussit cependant pas à trouver une solution optimale et donc ne peut être qualifié de méthode de résolution exacte.

Résolution par la méthode des algorithmes génétiques

Les algorithmes génétiques se fondent sur la théorie générale de l'évolution de Darwin selon laquelle les espèces vivantes progressent en organisation et en complexité par la simple sélection naturelle de leurs caractères génétiques les plus performants lors des phases de reproduction.

Ainsi, ce principe qui optimiserait la configuration génétique des systèmes vivants face à un environnement hostile serait tout aussi bien capable de traiter des problèmes d'optimisation beaucoup plus généraux tels que la résolution des problèmes d'optimisation ou des modèles de localisation-allocation. Les premières applications à ces cas datent des années 70 [42] ^[43] .

De manière analogue pour ces modèles, un individu ou une solution se caractérise par son empreinte génétique ou sa structure de données. Les opérations génétiques de croisement et de mutation modifient les données ou chromosomes de chaque individu ce qui permet en théorie de parcourir tout l'éventail des solutions possibles.

L'algorithme génétique va donc à chaque nouvelle génération créer de nouvelles solutions mais aussi en détruire ainsi que le décrit la théorie de la sélection naturelle [44] . La performance de l'individu ou l'optimalité de la solution se mesure par le niveau de sa fonction objectif.

Dans un premier temps, l'algorithme génétique va générer des solutions de manière aléatoire, puis il va les laisser évoluer jusqu'à obtenir les meilleures solutions possibles.

Pour utiliser avec succès un algorithme génétique, il est nécessaire :

• de réussir à coder les solutions en des ensembles de chromosomes,
• de partir d'une population ou de solutions de base,
• de disposer d'une fonction objectif qui va mesurer le niveau d'optimalité de chaque solution,
• de décider comment sélectionner les chromosomes les plus performants,
• de décrire les opérateurs génétiques ou le mode d'échange des données,
• de spécifier les paramètres de l'algorithme tels que taille de la population initiale, probabilités de croisement et de mutation,
• de donner un critère d'arrêt de l'algorithme.

Le codage d'un modèle p-médian est une succession binaire de 0 et de 1 correspondant à l'absence ou à la présence d'un point de vente dans la liste des nœuds du réseau. Les caractéristiques des solutions de départ et leur nombre (population de départ) peuvent être tirées au hasard ou bien déterminées par une autre heuristique du modèle p-médian. Dans ce dernier cas, l'algorithme génétique constituera une procédure d'amélioration de la solution.

La fonction objectif du p-médian nous conduisait à minimiser la quantité :

L'évaluation la plus simple de la force de l'individu ou optimalité de la solution consiste à prendre l'inverse de la fonction objectif que l'on cherchera à maximiser :

La sélection va déterminer à partir de quels individus on va construire la génération suivante. On utilise assez souvent la roue de Goldberg [45] qui consiste à tirer les solutions sur une roue de loterie sur laquelle les individus sont représentés sur une surface proportionnelle à leur force ou optimalité.

De cette façon, les individus les plus forts auront à l'étape ultérieure de croisement et de mutation, une représentativité plus forte avec un nombre de copies plus importantes au sein de la population.

Le croisement consiste alors à échanger des paquets de données (des suites de 0 et de 1 découpées dans la solution) entre des paires d'individus.

La mutation consiste à basculer dans notre cas un 0 en 1 ou réciproquement un 1 en 0 en de très rares occasions selon une probabilité de mutation fixée à l'avance. Cette procédure permettrait d'explorer toutes les solutions en évitant d'emprisonner la recherche dans un maximum local.

En pratique, les chromosomes sont tirés de façon aléatoire et sont remplacés par un chromosome d'une autre valeur toujours prise aléatoirement. Enfin, le nombre maximal de générations correspond au nombre d'itérations que l'on se fixe pour stopper la procédure.

Tous les paramètres de l'algorithme génétique sont fixés empiriquement. Une population de 20 à 1000 individus qui en général reste stable au fur et à mesure des générations, satisfait généralement la résolution de tous les problèmes. Une taille de population trop faible ne permettra pas d'explorer tous les champs de solutions possibles alors qu'une taille très élevée nuira à la rapidité d'exécution.

Les moyennes des probabilités de croisement oscillent entre 0,65 et 0,9 : une probabilité élevée favorisera l'examen d'un grand nombre de solutions, mais une probabilité de croisement excessive risque d'emprisonner la recherche dans des maxima locaux. Une certaine probabilité de mutation [46] est au contraire nécessaire pour réussir de temps en temps à générer des individus hors-normes qui sont susceptibles de constituer des super-solutions au problème. Ces solutions bien meilleures ne sauraient dans certains cas être générées par des simples transformations de croisement. Il reste que la probabilité de mutation doit rester faible, de 0,001 à 0,2 voire 0,1 à 10 pour ne pas entraver le processus normal de reproduction et d'empêcher l'algorithme de converger vers un optimum [47] .

Outre ces paramètres fixés empiriquement, il n'existe pas à l'heure actuelle de critère de convergence efficace pour stopper le processus dès qu'une solution intéressante est atteinte. Il est donc indispensable de déterminer au départ le nombre d'itérations au bout duquel on arrête l'algorithme [48] .

Les algorithmes génétiques sont généralement particulièrement recommandés dans les problèmes pour lesquels n'existe aucune autre méthode de résolution ou bien pour lesquels les méthodes existantes n'offrent que des solutions approchées comme les modèles de localisation-allocation [49] .

Les algorithmes d'amélioration

- L'algorithme de recherche de voisinage [50]

Dans l'algorithme de voisinage, on considère le voisinage de chaque localisation d'activité, c'est-à-dire l'ensemble des nœuds qui lui sont le plus proche et on calcule dans ce voisinage une localisation améliorée par l'algorithme du 1-médian vu précédemment. L'algorithme de voisinage peut être utilisé comme algorithme de construction si l'on démarre la recherche de localisation avec une configuration aléatoirement choisie.

- L'heuristique de substitution [51]

On procède à l'heuristique de substitution en supprimant tout à tour chacune des p activités déterminées dans la procédure initiale de localisation, ensuite en recherchant le meilleur autre emplacement pour cette activité supprimée par une simple énumération et en calculant la fonction objectif correspondante. La recherche d'une valeur plus faible de la fonction objectif parmi celles calculées en recherchant une nouvelle localisation pour chaque activité déjà déterminée donnera éventuellement une configuration améliorée par rapport à celle obtenue à l'étape précédente.

Les variantes des algorithmes d'amélioration

La variante très proche de l'algorithme précédent, donnée par Goodschild et Noronha [52] , revient à identifier le nœud d'activité et le nœud libre dont la substitution offre la fonction objectif la plus basse. Si la fonction objectif a tendance à diminuer par rapport à la solution trouvée initialement, alors ce nouvel emplacement peut être considéré comme un optimum local.

Une autre variante des algorithmes d'amélioration consiste à travailler au niveau global, puis régional [53] . Considérons l'ensemble des nœuds occupés par une activité S et celui des nœuds non occupés (V-S) avec V l'ensemble de tous les nœuds. Si un nouveau nœud est mis dans l'ensemble S, on appelle cette procédure ADD alors que si on retire un nœud de l'ensemble S, cette procédure est nommée DROP. Dans la première phase globale, on réalisera une séquence de DROP et d'ADD jusqu'à ce que l'on ne trouve plus d'amélioration à la fonction objectif. Dans la phase locale, on décomposera le réseau en p problèmes 1-médian que l'on résoudra par l'algorithme de voisinage explicité précédemment.

Enfin, la procédure "Tabu" mise au point par Rolland, Schilling et Current [54] utilise un temps dit tabou, mesuré en nombre d'itérations, durant lequel il est interdit de pratiquer une procédure DROP sur un nœud incorporé à l'ensemble S par une procédure ADD (le compteur d'itérations est initialisé dès que ce nœud est placé dans l'ensemble S). Cette durée "taboue" fixe, aléatoire ou dynamique durant le fonctionnement de l'algorithme doit être écoulée pour avoir le droit à nouveau de supprimer le nœud de l'ensemble S. Ce programme d'amélioration semble enregistrer de meilleurs résultats que les heuristiques déjà citées.

2.4 Les autres modèles de localisation-allocation

Le modèle p-centré cherche la configuration pour laquelle la distance entre chaque point de vente et le plus éloigné de ses clients soit minimale. Ce modèle est particulièrement indiqué pour placer des services d'urgence, des hôpitaux ou des casernes de pompiers étant donné une population.

Le modèle de couverture maximale [55] vise à assurer que la majorité des clients sont à une distance maximale au moins d'un service donné : si cette condition est bien vérifiée, on dit alors que l'ensemble des clients est couvert : ces modèles sont indiqués pour placer des services généraux du type poste, trésorerie, services de mairie et administrations d'une manière générale. Les algorithmes de résolutions de ces autres modèles de localisation-allocation se calquent sur ceux du p-médian.