Solveur de Localisation d'Installations en Ligne

Pseudocode

Le problème arbitre entre deux coûts qui tirent en sens inverse: ouvrir des sites coûte de l'argent, mais chaque site ouvert raccourcit le trajet vers les clients. La formulation exacte est un programme en nombres entiers; en pratique on emploie une heuristique gloutonne avec amélioration locale.

// Exact (petit): tester chaque sous-ensemble de sites
meilleur = infini
pour chaque sous-ensemble non vide S des sites candidats:
    cout = somme des coutOuverture[f] pour f dans S
    pour chaque client c:
        cout += min sur f dans S de coutService[f][c]
    meilleur = min(meilleur, cout)

// Glouton (grand): ouvrir le site qui economise le plus
S = {}
repeter:
    f* = le site ferme qui reduit le plus le cout total
    si ouvrir f* ne reduit pas le cout: arreter
    S = S + {f*}

// Ensuite: recherche locale par echange, ouverture et fermeture

L'essentiel est que les clients sont toujours affectés au site ouvert le moins cher pour eux, le seul véritable degré de liberté est donc le choix du sous-ensemble à ouvrir. Cela transforme un problème d'apparence continue en un problème combinatoire sur les sous-ensembles, et c'est aussi ce qui le rend NP-difficile: il existe 2 puissance n sous-ensembles et aucun moyen connu de les parcourir en temps polynomial.

Exemple détaillé, étape par étape

Décide quels sites ouvrir avec trois candidats et quatre clients, en comparant tous les sous-ensembles.

Graphe d'exemple: Coûts d'ouverture: F1 vaut 10, F2 vaut 8, F3 vaut 6. Coûts de service par client: F1 dessert C1 et C2 pour 2 et 3 mais C3 et C4 pour 9 chacun; F2 dessert C3 et C4 pour 2 et 3 mais C1 et C2 pour 8 et 7; F3 dessert les quatre pour 5 chacun.

1. Ouvrir seulement F1. Coût d'ouverture 10, plus 2 + 3 + 9 + 9 de service, soit 33 au total. F1 est excellent pour ses deux clients proches et catastrophique pour les deux autres.
2. Ouvrir seulement F2. Ouverture 8, plus 8 + 7 + 2 + 3, soit 28. C'est l'image miroir de F1.
3. Ouvrir F1 et F2. Ouverture 10 + 8 = 18, et chaque client choisit désormais sa meilleure option: 2 + 3 + 2 + 3 = 10 de service, soit 28. Les coûts de service sont imbattables, mais payer deux ouvertures absorbe tout l'avantage.
4. Ouvrir seulement F3. Ouverture 6, plus 5 + 5 + 5 + 5 = 20 de service, soit 26. F3 n'est le meilleur choix pour aucun client en particulier, et l'emporte pourtant.
5. Ouvrir les trois. Ouverture 10 + 8 + 6 = 24, plus 2 + 3 + 2 + 3 = 10, soit 34. Ouvrir davantage de sites dégrade le résultat.

L'optimum consiste à n'ouvrir que F3, pour un coût total de 26. Cela mérite qu'on s'y arrête: F3 n'est le site préféré d'aucun client, et pourtant le sous-ensemble optimal est exactement celui-là. Une heuristique affectant chaque client à son site de service le moins cher ouvrirait F1 et F2 et aboutirait à 28. Seul l'arbitrage entre coût d'ouverture et coût de service compte, et raisonner client par client ne le capture pas.

Complexité et son origine

Temps: NP-difficile; exact O(2^n · n · m) · Espace: O(n · m)

Avec n sites candidats et m clients, l'énumération exacte teste les 2 puissance n sous-ensembles non vides et, pour chacun, affecte les m clients à leur site ouvert le moins cher en O(n) par client, soit O(2 puissance n fois n fois m). Ce n'est praticable que jusqu'à 20 ou 25 sites environ. Le problème est NP-difficile, aucun algorithme exact polynomial n'est donc attendu. La bonne nouvelle est que la variante sans capacité est approximable: il existe des algorithmes à facteur constant autour de 1,5 fondés sur l'arrondi de programmation linéaire et sur la recherche locale, ce qui contraste avec la coloration de graphes où aucune approximation correcte n'est connue. Le glouton qui ouvre à chaque étape le site procurant la plus grande économie offre une garantie logarithmique et se comporte bien en pratique.

Quand utiliser Localisation d'Installation, et quand l'éviter

La variante pertinente dépend de l'existence de limites de capacité et du nombre de clients.

Pièges fréquents

• Affecter les clients avant de décider des ouvertures. L'affectation est triviale une fois l'ensemble ouvert fixé: chaque client rejoint son site ouvert le moins cher. Raisonner à l'envers, en choisissant d'abord le site favori de chaque client, conduit à sur-ouvrir, comme le montre l'exemple où ce raisonnement donne 28 contre un optimum de 26.
• Supposer qu ouvrir plus de sites aide toujours. Ouvrir les trois de l'exemple coûte 34, soit pire que n'ouvrir que F3 à 26. Chaque ouverture ajoute un coût fixe qui doit être amorti par l'économie de service, et ce n'est souvent pas le cas.
• Ignorer la limite de capacité lorsqu elle existe. La variante sans capacité autorise un site à servir tous les clients. Si la réalité impose un plafond de demande, la solution optimale sans capacité peut être purement et simplement irréalisable, et il faut la formulation capacitée.
• Utiliser la distance euclidienne quand le coût réel ne l est pas. Les coûts de service incluent souvent le temps de conduite, les péages, les créneaux horaires ou les tarifs par zone. Les remplacer par la distance à vol d'oiseau change le problème et souvent la réponse.
• Traiter le résultat comme définitif alors que la demande varie. La localisation de sites est une décision de long terme prise sur une prévision de demande. Il vaut la peine de vérifier si le sous-ensemble optimal le reste sous d'autres hypothèses de demande avant de construire quoi que ce soit.

Questions fréquentes

Qu'est-ce que le problème de localisation de sites?

Étant donné un ensemble d'emplacements candidats avec un coût d'ouverture et un ensemble de clients avec un coût de service depuis chaque emplacement, le problème demande quels sites ouvrir pour minimiser la somme du coût d'ouverture et du coût de service. Il modélise l'implantation d'entrepôts, le placement de serveurs, la planification de réseaux de points de vente et le choix de sites de centres de données.

Pourquoi la localisation de sites est-elle difficile?

Parce que l'affectation des clients est triviale une fois décidé quoi ouvrir, tout le problème se ramenant au choix d'un sous-ensemble d'emplacements. Avec n candidats il existe 2 puissance n sous-ensembles et aucun moyen connu de les explorer en temps polynomial. Le problème est NP-difficile, même si la variante sans capacité admet une approximation à facteur constant.

Quelle est la différence entre localisation avec et sans capacité?

Sans capacité, un site ouvert peut servir n'importe quel nombre de clients. Avec capacité, chaque site a une limite de demande, si bien que des clients peuvent être contraints de rejoindre un site plus coûteux parce que le plus proche est déjà saturé. La variante capacitée est sensiblement plus difficile et ses solutions sont structurellement différentes.

Ouvrir plus de sites réduit-il toujours le coût?

Non. Chaque ouverture ajoute un coût fixe, justifié seulement si l'économie de service le dépasse. Dans l'exemple ci-dessus, ouvrir les trois sites coûte 34 alors qu'en ouvrir un seul coûte 26. Cet arbitrage entre coût fixe et coût variable est le cœur du problème.

Quelle est la différence entre localisation de sites et k-moyennes?

K-moyennes partitionne des points en k groupes en minimisant la distance intra-groupe, sans aucun coût d'ouverture et avec k fixé d'avance. La localisation de sites décide combien de sites ouvrir et lesquels, en arbitrant coût d'ouverture contre coût de service. K-moyennes est un problème de regroupement; la localisation est une décision économique.