Problème de l'emplacement d'installations

Le problème d'emplacement d'installations (anglais : facilities location problem) est un problème de recherche opérationnelle et de géométrie algorithmique. Il consiste à répondre à la question :

Quel est le meilleur emplacement pour une installation, ou pour un ensemble d'installations.

Origine du problème

Le terme « installation » peut désigner un atelier, une usine, un service public (service postal, hôpital, Caserne de pompiers...), un commerce, un entrepôt (stock)… Le terme « meilleur » signifie en général « qui a le plus court trajet » (d'un client vers un service, d'une usine vers une autre, d'un stock vers un commerce, d'un véhicule de secours vers le lieu du sinistre), « qui assure le service attendu avec le plus petit nombre d'installations », « qui coûte le moins cher » ou bien « qui éloigne le danger » (usine ou stock de type Seveso par rapport à des agglomérations, commerce concurrent avec risque de saturation du marché local). La méthode s'applique également au partitionnement de données.

Problème mathématiques

Ce problème se traite en mathématiques par des méthodes d'optimisation : la qualité de la solution retenue, c'est-à-dire son adéquation au critère choisi, est mesuré par une fonction réelle, ƒ_o, appelée « fonction-objectif » ou « fonction-coût ». Le problème consiste donc à trouver la solution ayant, selon la manière dont est posé le problème, la plus faible valeur de la fonction-objectif (par exemple la distance la plus courte, la durée d'intervention la plus courte, le plus petit nombre d'installations) ou au contraire la plus haute valeur (par exemple la distance la plus grande). Par convention, on cherche la valeur la plus faible[1].

Dans certains cas, les sites possibles sont identifiés. Le problème consiste à déterminer quelle installation mettre à quel site. C'est un problème d'optimisation combinatoire NP-difficile.

Notes et références

1. Dans le cas où l'on s'intéresse au maximum d'une fonction ƒ_o, cela revient à chercher le minimum de son opposé -ƒ_o.

Voir aussi

Articles connexes

• Théorie de la localisation
• Problème de Weber
• Problème du cercle minimum
• Problème du plus grand cercle vide