Giuseppe Bruno » 21.Algoritmi euristici per il TSP

Argomenti della lezione

• Definizioni generali
• Algoritmi euristici per il TSP
• Algoritmo Nearest neighbour
• Algoritmi di inserimento
• Algoritmo di saving

Definizioni generali

Rappresentazione su grafo

Si consideri un grafo G=(V,A) con

V={v₁,..,v_n}insieme di n nodi rappresentativo di località, A={(v_i,v_j): v_i,v_j∈V} insieme archi che identificano i possibili collegamenti tra località.
A ciascun arco è associato un costo c_ij che può indicare la lunghezza del collegamento, il tempo o il costo per coprirlo.
Si parla di problemi a

• copertura dei nodi (node covering) se i servizi si intendono localizzati in corrispondenza dei nodi;
• copertura di archi (arc covering) se i servizi si immagino distribuiti sugli archi

Obiettivo: individuare un insieme di itinerari che visitino i nodi o gli archi presso i quali sono presenti i servizi.

Definizioni generali (segue)

Definizioni generali (segue)

Complessità del problema

Il TSP appartiene alla classe dei problemi NP-hard per i quali, cioè, non esiste un algoritmo in grado di risolvere il problema in tempo polinomiale.
Una soluzione ammissibile è rappresentata da una permutazione

A-C-F-B-D-E-G-H

Il numero delle soluzioni è n!

Per risolvere il problema in applicazioni reali bisogna ricorrere a tecniche euristiche.

Algoritmi euristici per il TSP

Si possono distinguere:

• Algoritmi costruttivi
  • Algoritmo nearest neighbour
  • Algoritmi di inserimento
  • Algoritmo di saving (Clarke and Wright);
• Algoritmi migliorativi;
• Metaeuristiche.

Algoritmi euristici per il TSP

Metodi o algoritmi costruttivi

Metodi orientati alla individuazione (costruzione) di una soluzione ammissibile di un problema di ottimizzazione.

Passi fondamentali di un algoritmo costruttivo:

1. Inizializzazione
Si sceglie un elemento di partenza per la costruzione della soluzione parziale S.

2. Selezione nuovo elemento da aggiungere alla soluzione
Si individua il criterio di selezione di un nuovo elemento da aggiungere alla soluzione parziale S.

3. Criterio di arresto
Se S è completa e, quindi, ammissibile la procedura si interrompe altrimenti si ritorna al passo 2.

Algoritmo nearest neighbor (vicino più vicino)

Si sceglie un nodo iniziale. La soluzione parziale è rappresentata da un percorso. All’iterazione generica si congiunge l’ultimo nodo inserito nel percorso al nodo ad esso più vicino, fino al completamento del circuito

1. Inizializzazione
Si sceglie un qualsiasi nodo d e si pone t=d, S={d}, S’=V-{d} e z(S)=0.

2. Aggiunta di un nuovo elemento alla soluzione parziale
Si individua il nodo k più vicino all’ultimo nodo t inserito nel circuito (k: c*_tk= min_j∈S’ c_tj) e si collega k a t. Si pone S=S∪{k}, S’=S’-{k} e z(S)= z(S)+c*_tk.

3. Criterio di arresto
Se S’=Ø si connette k al primo nodo d in modo da chiudere il circuito e si arresta l’algoritmo. Altrimenti si pone t=k e si ritorna al passo 2.

Algoritmo nearest neighbor (vicino più vicino)

Algoritmo nearest neighbor (vicino più vicino)

Algoritmo nearest neighbor (vicino più vicino)

Algoritmi di inserimento

Alla fine della generica iterazione k si ha a disposizione un sottocircuito passante per k nodi.

All’iterazione k+1, si sceglie un nodo tra quelli non ancora appartenenti al circuito (fase di selezione) e lo si inserisce in una particolare posizione del circuito (fase di inserimento o di espansione del circuito).

Il circuito iniziale (d-k-d) si può definire scegliendo un nodo a caso d e collegandolo con il nodo k ad esso più vicino o più lontano.

È possibile distinguere tra algoritmi

• Nearest insertion
• Cheapest insertion
• Random insertion

Algoritmi di inserimento – nearest insertion

L’algoritmo di inserimento del nodo più vicino (nearest insertion) realizza la fase di selezione scegliendo il nodo k∉S più vicino ad uno dei nodi di S.

Nella fase di inserimento si individua lo spigolo (i,j) che minimizza l’incremento di costo del circuito ossia la somma Δ= c_ik+ c_kj- c_ij (extramileage).

Considerando il meccanismo di selezione e di inserimento, la procedura risulta significativa soltanto nel caso simmetrico.

Algoritmi di inserimento – nearest insertion (segue)

Algoritmi di inserimento – nearest insertion (segue)

Algoritmi di inserimento – nearest insertion (segue)

Algoritmi di inserimento – nearest insertion (segue)

Algoritmi di inserimento – cheapest insertion

L’algoritmo di inserimento del nodo più conveniente (cheapest insertion) unisce la fase di selezione e di inserimento scegliendo direttamente la terna i*, j*, k* che minimizza l’extramileage

Δ= c_i*k* + c_k*j* - c_i*j*.

In pratica, dato un circuito parziale formato da p archi, per ogni arco (i,j) bisogna valutare l’extramileage relativo al possibile inserimento, tra i e j, degli n-p nodi non appartenenti al circuito e scegliere il minimo.

L’algoritmo può essere utilizzato anche nel caso asimmetrico.

Algoritmi di inserimento – cheapest insertion (segue)

Algoritmi di inserimento – cheapest insertion (segue)

Algoritmi di inserimento – cheapest insertion (segue)

Algoritmo di saving (segue)

Scelto un nodo d a piacere, si costruisce una prima soluzione “a stella” in cui ciascun nodo i è collegato a d attraverso una coppia di spigoli o archi (d,i), (i,d).

Per ogni coppia di nodi i,j si calcolano i savings s_ij e si ordinano in senso decrescente. Si esamina nell’ordine la lista degli s_ij e si collegano i nodi i e j unificando i circuiti di appartenenza, a condizione che i e j siano estremi di circuiti diversi.

L’operazione viene applicata iterativamente fin quando non si ottiene un unico circuito.

Poiché la soluzione finale dipende dal nodo di riferimento d, si può eseguire l’algoritmo n volte a partire da ciascun nodo.

Algoritmo di saving (segue)

Algoritmo di saving (segue)

Algoritmo di saving (segue)

Algoritmo di saving (segue)

Algoritmo di saving (segue)

Algoritmo di saving (segue)

Algoritmo di saving (segue)