Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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={v1,..,vn}insieme di n nodi rappresentativo di località, A={(vi,vj): vi,vj∈V} insieme archi che identificano i possibili collegamenti tra località.
A ciascun arco è associato un costo cij 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= minj∈S’ ctj) 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 kS 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 Δ= cik+ ckj- cij (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

Δ= ci*k* + ck*j* - ci*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

Si supponga di avere due circuiti non orientati aventi un nodo d in comune e siano i e j due nodi direttamente collegati a d appartenenti a due circuiti diversi.

È possibile costruire un unico circuito introducendo lo spigolo (i,j) e cancellando gli spigoli (i,d) e (d,j).

Si può definire un risparmio o saving sij=cid+cdj-cij che, se positivo, indica la riduzione di costo ottenibile con la fusione dei due circuiti.


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 sij e si ordinano in senso decrescente. Si esamina nell’ordine la lista degli sij 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)


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion