Problème de l'emplacement d'installations

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.

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.