Il cammino minimo

La ricerca operativa a vantaggio delle PMI: un algoritmo semplice per gestire i costi logistici.

Proseguiamo nel nostro approfondimento dei metodi della ricerca operativa applicata alle imprese.
Oggi vogliamo trattare il tema del calcolo di un cammino minimo.
Banalmente la sola esperienza quotidiana di muoversi da casa al posto di lavoro ci può far comprendere il tipo di problema. In verità le applicazioni sono molteplici: dalla logistica alle infrastrutture di rete (si immagini il problema di cablare con fibra ottica una città, per esempio), dai trasporti pubblici all’organizzazione dei turni e l’assegnazione dei compiti ad un gruppo di lavoratori o ancora la gestione dei server e l’archivio dei dati.
Diverse problematiche di questo genere si possono risolvere ricorrendo alla teoria dei grafi.
Per un approfondimento sui grafi ed il loro utilizzo rimandiamo a wikipedia .
Nel grafo rappresentato in figura, composto da 6 nodi e diversi archi, ogni nodo rappresenta un luogo, una città, per esempio, e gli archi che collegano i singoli nodi, invece, rappresentano i costi di percorrenza; il verso di percorrenza (la freccia su ogni arco) rappresenta la possibilità di raggiungere un nodo in un senso e non nell’altro (opposto alla freccia), se manca l’arco, i nodi non sono collegati. L’opportunità di individuare un tragitto di costo minimo, pensiamo non serva spiegarla, è evidente che per gli ambiti di applicazione appena citati, sapere qual è il percorso minimo da ogni nodo verso tutti gli altri sia evidentemente un vantaggio, in termini di competizione e di gestione dei costi. Minimizzare i costi logistici, per esempio, è un tipico problema aziendale, non solo per le imprese del settore.

Riportiamo, quindi, un esempio di applicazione.
Immaginiamo di voler organizzare le consegne di un corriere espresso, tra diverse location, ognuna rappresentata dal nodo in figura, gli archi che collegano il grafo rappresentano i costi di trasporto per muoversi da una location ad un’altra. La domanda è: “qual è il costo minimo per raggiungere da un qualsiasi nodo tutti gli altri nodi?”. La domanda così posta e riferita al grafo in figura potrebbe sembrare superflua, perché basta sommare i singoli costi per ogni arco, per le diverse alternative e presto avremmo una risposta, peccato che le cose non stiano esattamente in questi termini; basterebbe, infatti, moltiplicare per due volte i nodi e i percorsi alternativi, che il CALCOLO sarebbe certamente più complesso! Come al solito, proproniamo il caso più semplice per spiegare meglio il concetto.
Per risolvere questo problema applichiamo l’algoritmo di Floyd-Warshall, metodo noto in ricerca operativa, che consente di risolvere velocemente tale tipo di problema. Ogni nodo possiamo rappresentare in una matrice e i costi rappresentiamo all’incrocio di ogni intersezione della matrice, di seguito l’esempio:

Inzializzazione dell'algoritmo

Nella matrice sono riportati nella testata superiore e in quella di sinistra i nodi (A,B,C,D,E,F) la matrice si interpreta così: per andare dal nodo A (prima riga) a se stesso, il costo è = 0, com’è ovvio, per andare invece dal nodo A al nodo B il costo è = 5; si noti che sulla diagonale sono tutti zero, ciò perchè non ci si muove da A verso A, come da B verso B ecc. Il termine “inf” sta per infinito, vale a dire che i due nodi non sono direttamente collegati, per esempio : per andare dal nodo C al nodo A il costo è infinito, perché i due nodi non sono direttamente collegati, quindi, per andare da A al nodo C occorrerà seguire un’altra strada! Quale? Siamo alla ricerca di quella più breve. La matrice rappresentata è quella cosiddetta di inizializzazione, ove si possono osservare diversi inf, ciò perché non conosciamo ancora le strade alternative.
L’algoritmo ragiona così; per andare dal nodo B al nodo D, il costo è infinito (manca il collegamento diretto), allora si verifica per ogni altro nodo il costo relativo, per farlo si processa prima il nodo A (passo K = A) e ci si domanda, per andare dal nodo B al nodo D posso passare per A? Quindi dovrò muovermi da B ad A e poi da A a D; come si può osservare dal grafo pur non essendoci collegamento diretto tra i due nodi, passando, invece per A, ricavo un costo pari a 11 che è inferiore al costo infinito, quindi, tale costo sostituisco nella matrice (infatti il costo da B ad A = 6 mentre il costo per andare da A a D = 5, la somma da 11 che è inferiore a infinito, quindi sostuisco nella matrice il costo = 11), e così via per gli altri passi, riscriviamo la matrice per ogni passo, K=A -> k=B -> K=C -> K=D -> K= E -> K=F, per ogni nodo si verificherà se il costo si riduce rispetto a quello del passo precedente e si sostituirà nella matrice. IL risultato è una matrice ultima, al passo k=F che riporta tutti i costi diretti tra tutti i nodi. In definitiva con questo algoritmo siamo in grado di determinare quale percorso di costo minimo dobbiamo percorre per andare da qualunque nodo a qualunque altro nodo. Per esempio, nella matrice K=F per andare dal nodo C al nodo E il costo è = 17.

Di seguito le immagini da consultare

Licenza di distribuzione:

FONTE ARTICOLO

INFORMAZIONI SULLA PUBBLICAZIONE

Freesbee

Responsabile account:
Sabrina Ferrari (Titolare )

Contatti e maggiori informazioni
Vedi altre pubblicazioni di questo utente
RSS di questo utente