Où poser une usine, un entrepôt, une caserne de pompiers — et pourquoi la réponse change selon ce qu'on cherche à minimiser.
Un territoire de 100 km sur 70, vingt-quatre communes, 187 000 habitants. Deux villes principales : Aubevaux à l'ouest (46 000 habitants) et Quincey à l'est (22 000). Un hameau perdu au nord-est, Yvrandes, avec ses deux mille âmes. Toutes les distances sont à vol d'oiseau et l'on roule à 60 km/h, de sorte qu'un kilomètre vaut une minute : les cartes se lisent indifféremment en distance ou en délai.
La question paraît simple — placer au mieux quelques installations — mais elle se scinde en cinq problèmes qui ne donnent pas les mêmes réponses. Minimiser le coût de transport n'est pas minimiser le délai le plus long ; couvrir tout le monde n'est pas couvrir le plus de monde possible ; et l'emplacement que choisit un marché concurrentiel n'est celui d'aucun planificateur.
On n'ouvre qu'un dépôt. Chaque habitant engendre un trafic proportionnel à sa distance au dépôt : le coût total vaut Σ wi·di, somme des populations multipliées par les distances. Où faut-il se placer ? L'intuition dit « au centre » — mais il y a trois centres, et ils ne sont pas au même endroit.
Trois centres, trois problèmes.
Le barycentre — celui qu'on calcule spontanément — minimise la somme des carrés des distances pondérées par les populations: Σ wi·di². Les communes éloignées pèsent donc fortement sur sa position. Il ne minimise pas le transport total : dans le cas étudié, il entraîne 9,90 % de transport supplémentaire par rapport à l’optimum.
Le point de Weber minimise la somme des distances pondérées par les populations Σ wi·di C’est l’emplacement optimal si le coût de transport est proportionnel à la distance et à la population desservie. Il n’existe généralement pas de formule directe pour le calculer. L’algorithme de Weiszfeld l’approche par étapes, en recalculant un barycentre avec des poids wi/di, où di est la distance à l’emplacement obtenu à l’étape précédente.
Avec l'algorithme de Weiszfeld, on utilise une suite de barycentres pondérés par 1/d.
Le centre du plus petit cercle englobant minimise la distance à la commune la plus éloignée : max di. Il minimise donc le délai maximal si les temps de trajet sont proportionnels aux distances. Les populations n’interviennent pas. Sa position est déterminée par deux ou trois communes situées sur le cercle : il est au milieu de deux communes extrêmes seulement lorsque celles-ci définissent un diamètre.
Contrôles de la solution..
Deux vérifications confortent le résultat obtenu par l’algorithme de Weiszfeld :
- Le gradient Σ wi(x−pi)/di est presque nul : sa norme vaut 4,5 × 10⁻¹³. Cela indique que le point calculé satisfait, à la précision numérique près, la condition d’optimalité.
- Une recherche indépendante sur une grille de 801 × 801 points, couvrant tout le territoire étudié, trouve son meilleur emplacement à seulement 42 mètres du point de Weber. Son coût est supérieur de 0,00095 %. Ce très faible écart est compatible avec la précision limitée de la grille, qui ne teste que des emplacements espacés.
Conséquence pratique. Si l’implantation est libre, la distance moyenne pondérée par la population est de 18,1042 km par habitant. Si l’on impose de choisir parmi les sites communaux étudiés, Bellenave est le meilleur choix, avec 18,1122 km par habitant. Le surcoût n’est que de 0,044 %, soit environ 8 mètres supplémentaires par habitant : choisir un site existant pénalise donc très peu la solution dans ce cas.
Le seuil d'accrochage.
Lorsque l’on augmente la population d’Aubevaux, le point de Weber se rapproche de cette commune. À partir d’un certain poids, Aubevaux devient elle-même l’emplacement optimal et le reste si sa population continue d’augmenter, toutes les autres données étant inchangées.
Ce seuil est donné par une condition exacte : ‖Σj≠i wjuj‖ ≤ wi, où wi est la population d’Aubevaux et uj le vecteur unitaire allant de la commune j vers Aubevaux. Autrement dit, le poids d’Aubevaux doit suffire à compenser l’attraction combinée des autres communes.
La théorie prédit un seuil de 77,477076. Une recherche numérique par dichotomie — qui teste si un petit déplacement autour d’Aubevaux peut encore réduire le coût — donne 77,477043, soit un écart d’environ 0,000034. Les deux résultats concordent donc très précisément.
La difficulté numérique vient de la fonction de coût, et non de l’algorithme lui-même : elle n’est pas différentiable à l’emplacement d’une commune. À cet endroit, sa distance au centre est nulle, ce qui rend le poids wi/di de Weiszfeld impossible à calculer.
Sans traitement spécifique, l’algorithme peut s’approcher du point optimal sans jamais l’atteindre exactement.
On ouvre p installations sur les sites disponibles — les communes elles-mêmes — et chacun se rend à la plus proche. Deux objectifs s'affrontent. La p-médiane minimise la distance moyenne pondérée : c'est le point de vue du logisticien, qui paie le transport. Le p-centre minimise la distance maximale : c'est le point de vue du secours, pour qui seul compte le pire délai. Les deux solutions ne se ressemblent pas.
Le prix de l'équité. À trois installations, la p-médiane choisit Aubevaux, Bellenave et Quincey : deux sites collés dans l'agglomération de l'ouest, parce que c'est là qu'est la population. Distance moyenne 6,75 km — mais Yvrandes attend 43,9 minutes. Le p-centre choisit Aubevaux, Persannes et Varambon, s'éloigne des foules pour aller chercher les isolés, et ramène le pire délai à 25,5 minutes, soit 41,9 % de moins, au prix de 16,4 % de distance moyenne en plus. À cinq installations l'arbitrage devient brutal : le pire délai tombe de 34,7 à 17,1 minutes, mais la distance moyenne enfle de 66 %.
Les optima ne s'emboîtent pas. On croirait qu'ouvrir une installation de plus revient à garder les précédentes et à en ajouter une. C'est faux, et le bouton le montre : le meilleur site unique est Bellenave, mais l'optimum à deux installations est Aubevaux + Quincey — aucun site commun. Pour le p-centre, c'est pire encore : l'optimum à trois installations ne partage aucun site avec l'optimum à deux. Un plan d'équipement construit par ajouts successifs est donc structurellement sous-optimal, et il faut tout redessiner à chaque tranche de budget.
Ce que valent les méthodes rapides.
Pour choisir p sites parmi 24 communes, la méthode exhaustive examine toutes les combinaisons possibles. Avec 6 sites, cela représente 134 596 combinaisons, un nombre encore raisonnable ici. Mais choisir 20 sites parmi 100 communes demande d’examiner environ 5,36 × 10²⁰ combinaisons : cette méthode devient impraticable.
Deux méthodes rapides ont été évaluées sur 300 territoires générés aléatoirement, pour minimiser la somme des distances pondérées par les populations :
- La construction gloutonne ajoute, à chaque étape, le site qui réduit le plus le coût, sans remettre en cause les choix précédents. Elle trouve l’optimum dans 21,7 % des cas. Son coût dépasse celui de l’optimum de 10,4 % en moyenne, et jusqu’à 74 %.
- La méthode d’échange de Teitz et Bart améliore une sélection en remplaçant un site retenu par un site écarté. Elle poursuit les échanges tant qu’ils réduisent le coût. Elle atteint l’optimum dans 90,7 % des cas, avec un surcoût moyen de seulement 0,29 %. Elle reste toutefois susceptible de se bloquer sur une solution qu’aucun échange simple ne peut améliorer.
Pour le problème du p-centre, l’objectif change : il faut minimiser la distance de la commune la plus éloignée de son site le plus proche. Sur ces essais, la méthode gloutonne est nettement moins efficace : 5,7 % d’optima, un excès moyen de 28,6 %, et jusqu’à 84 %. Choisir le meilleur ajout immédiat peut donc conduire à une mauvaise configuration d’ensemble, particulièrement pour cet objectif.
Pour un service de secours, la question change de nature. On se fixe un délai d'intervention — quinze minutes, disons — et une commune est soit couverte, soit non. Deux problèmes en découlent.
Couvrir tout le monde avec le moins de casernes possible : c'est le problème du recouvrement d'ensemble.
Couvrir le plus de monde avec un nombre de casernes imposé : c'est le problème de la couverture maximale. Le premier fixe le service et cherche le budget, le second fixe le budget et cherche le service.
L'escalier du service. La courbe du bas donne le nombre minimal de casernes en fonction du délai qu'on s'accorde. Elle descend par marches : 24 casernes pour tenir 4 minutes, 14 pour 10 minutes, 7 pour 15, 5 pour 20, 3 pour 30, et une seule suffit à partir de 44 minutes. Les marches sont l'information utile : entre 16 et 18 minutes rien ne change, puis on gagne d'un coup une caserne entière. Négocier deux minutes de délai supplémentaire ne rapporte rien à certains endroits de la courbe, et beaucoup à d'autres.
Le glouton se trompe, mais pas de beaucoup. Pour tout couvrir, prendre à chaque étape la caserne qui rattrape le plus de communes découvertes donne 7 casernes à 15 minutes — l'optimum. Mais à 20 minutes il en propose 6 quand 5 suffisent, et à 10 minutes 16 au lieu de 14. Le recouvrement d'ensemble est ici résolu exactement par séparation et évaluation : on choisit à chaque nœud la commune découverte la plus difficile à couvrir et on branche sur les casernes qui l'atteignent, ce qui referme l'arbre en quelques dizaines de nœuds.
La couverture maximale et sa garantie. Avec trois casernes à 12 minutes, l'optimum couvre 159 000 habitants (85,03 %) en plaçant Clairbois, Fontenaud et Quincey ; le glouton, qui commence par le meilleur site isolé — Bellenave —, plafonne à 158 000 (84,49 %). Il rate l'optimum parce que le meilleur premier coup n'appartient pas à la meilleure combinaison. Mais l'écart reste borné : la fonction « population couverte » est sous-modulaire (chaque caserne ajoutée rapporte de moins en moins), et le glouton garantit alors au moins 1 − 1/e = 63,21 % de l'optimum. Sur 400 territoires tirés au hasard, le rapport mesuré descend au plus bas à 0,855, vaut 0,995 en moyenne, et le glouton est exactement optimal dans 86,8 % des cas : la garantie théorique n'est jamais approchée, mais elle existe, et c'est elle qui autorise à s'en servir sur les grandes instances.
Jusqu'ici p était donné. Mais chaque installation coûte à construire et à faire tourner, et chaque kilomètre parcouru coûte aussi. Le nombre optimal se trouve au fond d'une courbe en U : le coût fixe monte en ligne droite avec p, le coût de transport descend — mais de plus en plus lentement.
Le transport est facturé 2 € par habitant, par kilomètre et par an.
La deuxième installation est celle qui rapporte le plus. Passer de une à deux divise la distance moyenne par 2,3 — Aubevaux et Quincey captent d'un coup les deux bassins de population. La troisième ne fait plus gagner que 14 %, la quatrième 12 %, et ainsi de suite. C'est pourquoi la courbe en U est très asymétrique : à 600 k€ par installation, l'optimum est de deux installations ; en ouvrir une troisième coûte 4,5 % de plus, mais n'en ouvrir qu'une coûte 78 % de plus. Se tromper par excès est bénin, se tromper par défaut est ruineux.
La loi de la racine carrée. Sur un semis dense de 700 points de demande, on calcule l'optimum continu par l'algorithme de Lloyd — on affecte chacun à l'installation la plus proche, puis on remplace chaque installation par le point de Weber de son groupe, et on recommence. La distance moyenne décroît alors comme p−1/2 : la pente mesurée en échelle logarithmique vaut −0,482 pour la pente théorique −0,500. Vérification directe, sans régression : quadrupler le nombre d'installations doit diviser la distance par deux, et les rapports mesurés sont 0,595 de 2 à 8, 0,546 de 3 à 12, 0,527 de 4 à 16, 0,513 de 5 à 20, 0,512 de 6 à 24 — ils convergent vers 0,5 à mesure que les effets de bord du territoire s'estompent.
Et donc l'optimum varie en f−2/3. Si le transport vaut A·p−a avec a ≈ 1/2, annuler la dérivée de p·f + A·p−a donne p* = (A·a/f)1/(1+a), soit un exposant −1/(1+a) = −0,675, très proche du −2/3 du cas idéal. Diviser par huit le coût d'une installation quadruple leur nombre optimal. La formule se trompe pourtant jusqu'à trois unités sur le nombre exact d'installations — et c'est sans conséquence : le coût qu'elle donne ne dépasse jamais de plus de 0,98 % celui du meilleur entier, tant que l'optimum dépasse quatre installations. Le fond de la vallée est si plat que le nombre exact importe peu ; ce qui importe, c'est l'ordre de grandeur.
Toutes les planches précédentes supposaient une autorité unique cherchant le bien commun. Supprimons-la. Deux entreprises s'installent librement, chacune veut sa part de clientèle, chaque client va au plus proche. Où se posent-elles ? Hotelling a donné la réponse en 1929 sur le cas le plus simple qu'on puisse imaginer : une plage, des baigneurs répartis uniformément, deux marchands de glaces.
Les deux marchands se rejoignent au centre. Chacun, prenant la position de l'autre pour donnée, a intérêt à se placer juste à côté de lui du côté le plus fourni : il rafle alors tout ce qui est derrière. L'autre riposte de la même façon, et les deux remontent la plage en se doublant l'un l'autre jusqu'au milieu. L'équilibre est exactement 0,5 pour les deux, et il est unique : la recherche exhaustive sur les 861 configurations de la grille au quarantième n'en trouve pas d'autre. Le trajet moyen d'un baigneur y vaut 0,250000, alors que l'optimum social — un marchand au quart, l'autre aux trois quarts — donne 0,125000. Le marché double exactement le déplacement moyen : le prix de l'anarchie vaut ici 2,00000000, et il ne dépend d'aucun paramètre.
À trois, il n'y a pas de solution du tout. Portez le curseur à trois concurrents : la dynamique des meilleures réponses ne se stabilise jamais, celui du milieu étant toujours étranglé et n'ayant jamais intérêt à rester. Ce n'est pas un défaut de l'algorithme : la recherche exhaustive sur les 12 341 configurations de la grille au quarantième ne trouve aucun équilibre — contre un seul à deux concurrents, et trois à quatre concurrents, où les marchands se regroupent par paires au quart et aux trois quarts. Le nombre trois est la seule exception connue de ce problème.
Sur le territoire, le résultat est plus dur encore. Deux entreprises libres, chacune cherchant à maximiser la population dont elle est la plus proche, convergent en six coups vers un même site : Bellenave — précisément la 1-médiane, le meilleur emplacement pour une installation unique. Elles se partagent la clientèle à 50/50 et aucune des 48 déviations possibles n'est profitable. Mais deux installations superposées ne valent qu'une seule : la distance moyenne parcourue est de 18,11 km, contre 7,85 km pour l'optimum à deux installations d'un planificateur — 2,31 fois plus. Deux casernes privées ne desservent pas mieux qu'une seule caserne publique bien placée ; c'est toute la justification économique de la planification des équipements collectifs.