Problema di localizzazione

Un problema di localizzazione consiste nella ricerca della posizione da assegnare ad un insieme di strutture (facilities o servizi) in funzione della distribuzione della domanda relativa alla loro utilizzazione. In ricerca operativa esistono problemi di localizzazione nel continuo, in cui gli impianti e la domanda possono assumere qualunque posizione in un insieme continuo oppure problemi di localizzazione su reti, in cui gli impianti e la domanda è localizzata sui vertici di una rete. I problemi di localizzazione possono essere classificati nel modo seguente:

• Problemi di copertura (covering): si vogliono situare un insieme di impianti in modo che tutti i clienti siano coperti. Non è noto a priori quanti impianti sarà necessario ubicare. Un tipico esempio è la localizzazione degli estintori in un edificio.
• Problemi di mediana (median): situa p impianti in modo da minimizzare la distanza media tra i punti di domanda e l'impianto più vicino tra i p disposti. Si considera che ogni cliente si recherà nell'impianto a lui più vicino. Un classico esempio di questo tipo di problemi è la localizzazione di centri commerciali o scuole.
• Problemi di centro (center): situa p impianti in modo da minimizzare la massima distanza tra un punto di domanda e un impianto. Tipici esempi sono la localizzazione di punti di primo soccorso e di presidio alle emergenze in generale.

A seconda del numero di impianti da localizzare si usa chiamare i problemi di centro, 2-centro, 3-centro, ..., p-centro e, analogamente, problemi di p-mediana.

Problemi di copertura

Problemi di mediana

In questo tipo di problemi si vuole minimizzare la distanza media tra la domanda e gli impianti. Analogamente agli altri problemi di localizzazione gli elementi dell'insieme clienti (cioè della domanda) possono avere tutti lo stesso peso unitario oppure alcuni possono avere peso maggiore. È questo il caso, per esempio, in cui si considera che la popolazione delle città sia distribuita nel centro cittadino e gli si attribuisce peso pari alla popolazione locale, in questo modo si trasforma un problema in cui la domanda è distribuita sul continuo in uno in cui è distribuita su rete. ${\displaystyle \min \sum _{i}\sum _{j}h_{i}d_{ij}Y_{ij}}$ ${\displaystyle \sum _{j}X_{j}=P}$
${\displaystyle \sum _{j}Y_{ij}=1\forall i}$
${\displaystyle Y_{ij}-X_{j}\leq 0\forall i,j}$
${\displaystyle X_{j}\in \{0,1\}\forall j}$
${\displaystyle X_{i,j}\in \{0,1\}\forall i,j}$
dove i è l'indice per i nodi della domanda, j è l'indice dei nodi dei potenziali siti degli impianti, ${\displaystyle h_{i}}$ è la domanda relativa al nodo i, ${\displaystyle d_{i,j}}$ è la distanza tra il nodo i e il nodo j, P è il numero di impianti che vanno ubicati.

Problemi di centro

In questo tipo di problemi dà maggiore enfasi alla parte di clienti più sfavorita, tipicamente quella più lontana dagli impianti. La localizzazione dell'impianto o degli impianti è tale da minimizzare la distanza massima tra cliente e l'impianto a lui più vicino.