2002-2024 Tutti i diritti riservati

Ricerca Operativa

Problema del commesso viaggiatore

Soluzioni di Hamilton

(Torino, May 10 2002 12:00AM) DEFINIZIONE DEL PROBLEMA

Si supponga di dover rifornire di viveri 6 postazioni A B C D E F. Il percorso che porta da una postazione ad un’altra è contraddistinto con un numero che indica la distanza “ponderata”, ponderata perché legata non solo alla distanza fisica vera e propria, ma anche alle difficoltà che il percorso tra i due punti può riservare. Alla fine occorre tornare sulla postazione di partenza.

Facciamo un esempio, con una tabella (MATRICE) e con un grafico (GRAFO) che può aiutarci a chiarire meglio il problema:

Ovviamente, per andare da A a A occorre una distanza pari a 0 che indichiamo con -.

Supponiamo, per semplicità, che il percorso alla rovescia abbia la stessa distanza, non consideriamo ostacoli, sensi unici che possano ostacolare tale supposizione.

A B C D E F

A - 7 11 3 4 10

B 7 - 5 6 24 11

C 11 5 - 6 12 2

D 3 6 6 - 7 4

E 4 24 12 7 - 12

F 10 11 2 4 12 -



Cioè: Per andare da A a B occorre una distanza pari a 7

Per andare da A a C occorre una distanza pari a 11

Per andare da A a D occorre una distanza pari a 3

Per andare da A a E occorre una distanza pari a 4

Per andare da A a F occorre una distanza pari a 10

.... e via via per gli altri percorsi.



Il problema consiste nel rifornire di viveri tutte le sei postazioni col minimo percorso “COSTO MINIMO”.

Questo è un classico problema di Ricerca Operativa, materia sviluppata dai matematici e dagli informatici, e trova applicazione anche in altri campi, ovvero in tutti quei casi dove si ricerca il PERCORSO MINIMO. Alla fine, il percorso trovato costituisce un CIRCUITO.

Una possibile soluzione, consiste nel fare il percorso seguendo il circuito A-B-C-D-E-F-A, che utilizzando i dati della matrice ci porta ad un costo totale pari a 47.

AB + BC +CD +DE +EF +FA = 7+5+6+7+12+10 = 47. (Circuito 1)

Probabilmente, questo è il percorso più facile, ma forse non è il più economico.

Di possibili soluzioni ce ne sono almeno 60. Tale numero è dato da (N-1) ! /2.

Questo è un problema di difficile risoluzione per la Ricerca Operativa, perché aumenta considerevolmente all’aumentare delle postazioni (NODI).

Risolvendo lo stesso problema con un algoritmo di ricerca operativa, legato ai circuiti di HAMILTON (che non passano mai 2 volte per lo stesso nodo) si ottiene che il circuito più economico è quello che porta a A-E-D-F-C-B-A, per un costo totale di 29.

AE + ED + DF + FC + CB + BA = 4+7+4+2+5+7 = 29. (Circuito 2).

Circuito 2

OSSERVAZIONE:

Non sempre fare il giro delle postazioni senza ripassare dallo stesso nodo è la soluzione più conveniente.

E’ possibile dimostrare che ci sono percorsi, che ci fanno passare più di una volta dallo stesso nodo e che hanno lo stesso costo se non addirittura più economici. In particolare, per questo caso il circuito A-E-A-D-F-C-B-A ha lo stesso costo di 29.

AE + EA + AD + DF + FC + CB + BA = 4+4+3+4+2+5+7 = 29. (Circuito 3)

Circuito 3

CONSIDERAZIONI:

Ipotizziamo di avere un’altra MATRICE dei percorsi: A B C D E F

A - 7 30 3 4 30

B 7 - 5 30 30 30

C 30 5 - 30 30 2

D 3 30 30 - 30 4

E 4 30 30 30 - 30

F 30 30 2 4 30 -



In questo caso, un circuito generico di HAMILTON, che non passa mai 2 volte per lo stesso punto non è il più conveniente. Facilmente si calcola che il circuito 2 ha un costo pari a 52.

AE + ED + DF + FC + CB + BA = 4+30+4+2+5+7 = 52

ed ogni altro circuito di HAMILTON ha un costo pari se non superiore. Mentre un circuito NON di HAMILTON come il circuito 3 ha un costo pari a 29.

AE + EA + AD + DF + FC + CB + BA = 4+4+3+4+2+5+7 = 29

che senza alcun dubbio è il più conveniente.

Non sempre i circuiti di HAMILTON sono i più convenienti per risolvere questo tipo di problemi legati al COMMESSO VIAGGIATORE ed ai percorsi minimi.