Problemi di Localizzazione, Giuseppe Bruno « Ricerca Operativa II « Ingegneria

Argomenti della lezione

Gli elementi di un problema di localizzazione
I principali modelli
Il modello del Simple Plant Location
Il modello della p-mediana

Gli elementi di un problema di localizzazione

Un problema di localizzazione consiste nella individuazione della posizione da assegnare ad un insieme di strutture (servizi o facilities) in funzione della distribuzione di una domanda, reale o potenziale, relativa alla loro utilizzazione.

Gli elementi di un problema di localizzazione (segue)

Spazio di localizzazione

Tipo di localizzazione

Domanda

Metrica

Decisori

Afferenza domanda

Criteri di localizzazione

Altri vincoli

Gli elementi di un problema di localizzazione

Spazio di localizzazione

Rappresenta lo spazio, reale o figurato, all’interno del quale devono essere localizzati i servizi.

In generale si parla di localizzazione continua o di localizzazione discreta se lo spazio di localizzazione è continuo o discreto.
Un caso particolare di localizzazione discreta è la localizzazione su rete se si utilizza un grafo per rappresentare lo spazio di localizzazione.

Gli elementi di un problema di localizzazione (segue)

Tipo di localizzazione

In funzione del modello di rappresentazione di un problema di localizzazione, i servizi possono essere di diversa estensione. A tal proposito si parla di:

Problemi di localizzazione puntuale
- Quando i servizi sono efficacemente rappresentabili attraverso punti nello spazio di localizzazione.
Progetto di reti
- Quando i servizi hanno una estensione tale da non poter essere rappresentati come punti.

Gli elementi di un problema di localizzazione (segue)

Domanda

Rappresenta la domanda, reale o potenziale, di utilizzazione dei servizi. Può essere considerata concentrata in punti di domanda o distribuita nello spazio di localizzazione, secondo una certa densità.

Gli elementi di un problema di localizzazione (segue)

Metrica

Un aspetto fondamentale che influenza le scelte localizzative è la distanza tra la domanda (concentrata o distribuita) e i servizi (già esistenti o da realizzare). Pertanto è necessario introdurre una metrica per la valutazione delle distanze.

Gli elementi di un problema di localizzazione (segue)

Decisori

I problemi di localizzazione possono essere caratterizzati dalla presenza di uno o più decisori.

Nel caso di più decisori si parla di localizzazione competitiva se i decisori competono tra di loro per il raggiungimento dei propri obiettivi o di localizzazione cooperativa se i decisori collaborano tra di loro e concordano le scelte.

Gli elementi di un problema di localizzazione (segue)

Afferenza domanda

I meccanismi secondo i quali la domanda si distribuisce tra i servizi disponibili possono essere diversi.

Secondo il meccanismo tutto-niente (all or nothing) si ipotizza che la domanda presente in un punto afferisca tutta alla localizzazione più vicina.

Esistono altri modelli (modelli logit, modelli gravitazionali) in base ai quali la domanda si distribuisce in misura direttamente proporzionale a fattori di attrazione (es: qualità dei servizi) e inversamente proporzionale a fattori di impedenza (es:distanza).

Gli elementi di un problema di localizzazione (segue)

Criteri di localizzazione

La funzione obiettivo è in generale rappresentata da una funzione di costo da minimizzare o una valutazione di benefici da massimizzare.

Le voci di costo più frequentemente considerate sono:

Costi di afferenza: rappresentano una funzione della distanza della domanda dai servizi disponibili.

Costi di localizzazione: indicano il costo necessario all’apertura ed al mantenimento dei servizi.

I benefici sono spesso misurati in termini di copertura del servizio che è dato dal numero di utenti che si trova entro una certa distanza dal servizio (raggio di copertura).

Gli elementi di un problema di localizzazione (segue)

Altri vincoli

Nella pratica possono essere presenti diversi vincoli aggiuntivi.

Esempi tipici sono vincoli di:

budget sui costi di localizzazione;
capacità massima dei servizi;
distanza (minima o massima) tra servizi aperti;
topologia della rete (caso di progetto di rete).

I principali modelli

Simple Plant Location
Individuazione del numero e della posizione di servizi con l’obiettivo di minimizzare la somma dei costi di afferenza e di localizzazione.

P-mediana
Individuazione della posizione di un numero prefissato (p) di servizi con l’obiettivo di minimizzare la somma dei soli costi di afferenza.

P-centro
Individuazione della posizione di un numero prefissato (p) di servizi con l’obiettivo di minimizzare il massimo costo di afferenza.

Maximal covering
Individuazione della posizione di un numero prefissato (p) di servizi con l’obiettivo di massimizzare la copertura totale.

Il Simple Plant Location

Il Simple Plant Location (segue)

Il modello del Simple Plant Location appartiene alla classe dei problemi NP-hard.

Una soluzione ammissibile del problema può essere rappresentata attraverso una stringa di valori binari corrispondente al vettore delle variabili y_j (vedi figura).
Il numero di soluzioni ammissibili è quindi pari al numero di totale di possibili stringhe binarie ovvero è pari a 2ⁿ-1 (meno 1 perché la stringa identicamente nulla non è associata ad una soluzione ammissibile).

Per risolvere il problema è possibile ricorrere, oltre ad euristiche costruttive, a metodi di ricerca locale o a metaeuristiche basate su mosse che alterano in qualche maniera i valori della stringa rappresentativa della soluzione corrente.

La p-mediana

Il modello della p-mediana può essere desunto da quello del Simple Plant Location con l’aggiunta delle seguenti ipotesi

numero di servizi da localizzare noto a priori e pari a p;
costi di localizzazione uguali per ciascun servizio pari a r.

Queste due ipotesi consentono di trascurare i costi di localizzazione nella funzione obiettivo essendo essi costanti.

Infatti si ha

$z=\sum_{i\in I, j\in J}c_{i,j}+ r \sum_{j\in J} y_j= \sum_{i\in I, j\in J} + \not{n}\not p$

Inoltre bisogna aggiungere il vincolo sul numero prefissato di servizi da attivare ovvero

$\sum_{j\in J}y_i=p$

La p-mediana (segue)

Il problema della p-mediana è di tipo NP-hard

Una soluzione ammissibile del problema può essere rappresentata attraverso una stringa binaria caratterizzata da p valori unitari corrispondente al vettore delle variabili y_j.

La p-mediana (segue)

Il numero di soluzioni ammissibili è quindi pari al numero di possibili combinazioni di p elementi su n posizioni che è pari a (vedi figura).

Per risolvere il problema è possibile ricorrere, oltre ad euristiche costruttive, a metodi di ricerca locale o a metaeuristiche basate su mosse che alterano i valori della stringa rappresentativa della soluzione corrente mantenendo inalterato il numero di valori unitari.