il problema del viaggiatore

[blake]

Ciao,
ho trovato in rete un'implementazione dell'algoritmo ungherese che sto
modificando per risolvere il problema del viaggiatore. Per quanto
riguarda le spese di trasporto ho capito come creare la matrice dei
costi perchè per ogni destinazione del tipo Roma-->Milano o
Milano-->Roma posso inserire le spese di trasporto relativamente al
mezzo prescelto, idem per quanto riguarda la matrice dei tempi, ma per
quanto riguarda le spese di vitto e alloggio non ho ben chiaro come
inserirle nella matrice dei costi sommandole alle spese di trasporto.
Mi sapreste dire come dovrebbero essere inserite nella matrice dei costi
usando l'attuale elaborazione del programma che sto facendo e che
trovate di seguito?
grazie


The matrix is:
Roma Milano Torino Vicenza Bologna Padova
1000,00 33,60 14,00 40,90 14,50 11,50
34,70 1000,00 21,70 13,00 20,20 23,40
14,80 21,50 1000,00 29,30 2,00 3,90
41,70 13,10 29,40 1000,00 27,60 30,30
15,00 20,20 2,00 27,50 1000,00 3,90
12,00 22,80 2,00 30,10 4,00 1000,00

The winning assignment (min sum) is:

array(1,6) = 11,50
array(2,4) = 13,00
array(3,5) = 2,00
array(4,2) = 13,10
array(5,3) = 2,00
array(6,1) = 12,00

Nessun ciclo hamiltoniano trovato, ma solo i seguenti cicli:
(1,6,1)-(2,4,2)-(3,5,3)-

The min is: 53,60

Total time required: 0s

_______________________________________________________________

Condizione: x_16 + x_61<=1
Si impone: x_16=0

The matrix is:
1000,00 33,60 14,00 40,90 14,50 1000,00
34,70 1000,00 21,70 13,00 20,20 23,40
14,80 21,50 1000,00 29,30 2,00 3,90
41,70 13,10 29,40 1000,00 27,60 30,30
15,00 20,20 2,00 27,50 1000,00 3,90
12,00 22,80 2,00 30,10 4,00 1000,00

The winning assignment (min sum) is:

array(1,3) = 14,00
array(2,4) = 13,00
array(3,5) = 2,00
array(4,2) = 13,10
array(5,6) = 3,90
array(6,1) = 12,00

Nessun ciclo hamiltoniano trovato, ma solo i seguenti cicli:
(1,3,5,6,1)-(2,4,2)-

The min is: 58,00

Total time required: 0s

_______________________________________________________________

Condizione: x_16 + x_61<=1
Si impone: x_61=0 e x_16=1

The matrix is:
1000,00 1000,00 1000,00 1000,00 1000,00 11,50
34,70 1000,00 21,70 13,00 20,20 23,40
14,80 21,50 1000,00 29,30 2,00 3,90
41,70 13,10 29,40 1000,00 27,60 30,30
15,00 20,20 2,00 27,50 1000,00 3,90
1000,00 22,80 2,00 30,10 4,00 1000,00

The winning assignment (min sum) is:

array(1,6) = 11,50
array(2,4) = 13,00
array(3,5) = 2,00
array(4,2) = 13,10
array(5,1) = 15,00
array(6,3) = 2,00

Nessun ciclo hamiltoniano trovato, ma solo i seguenti cicli:
(1,6,3,5,1)-(2,4,2)-

The min is: 56,60

Total time required: 0s

_______________________________________________________________

[Bruno Campanini]

blake wrote on 09-06-13 :

> Ciao,
> ho trovato in rete un'implementazione dell'algoritmo ungherese che sto
> modificando per risolvere il problema del viaggiatore. Per quanto riguarda le
> spese di trasporto ho capito come creare la matrice dei costi perchè per ogni
> destinazione del tipo Roma-->Milano o Milano-->Roma posso inserire le spese
> di trasporto relativamente al mezzo prescelto, idem per quanto riguarda la
> matrice dei tempi, ma per quanto riguarda le spese di vitto e alloggio non ho
> ben chiaro come inserirle nella matrice dei costi sommandole alle spese di
> trasporto.
> Mi sapreste dire come dovrebbero essere inserite nella matrice dei costi
> usando l'attuale elaborazione del programma che sto facendo e che trovate di
> seguito?

Non capisco.
Il problema del commesso viaggiatore (TSP) è quello della ricerca del
minimo percorso hamiltoniano.
Tu sostituisci al chilometro il costo chilometrico (carburante, bollo,
assicurazione, etc), e fin qui nulla di strano.
Ma per il vitto e alloggio come vorresti fare? in un viaggio di 24 ore
il viaggiatore dorme una volta e mangia tre volte, e in 26 ore cosa fa,
dorme e mangia il 10% in più?

I calcoli che hai riportato sono fatti con Lindo, col Simplesso o che
altro? Se la tua ricerca è a fini teorici va tutto bene ma se ha un
fine pratico e coinvolge meno di una decina di località il Branch &
Bound, il Constraint Generation, il Banch & Cut sono una bella noia.
Sarebbe molto più semplice usare le permutazioni.

Bruno

[blake]

Il 10/06/2013 03:27, Bruno Campanini ha scritto:

> Non capisco.
> Il problema del commesso viaggiatore (TSP) è quello della ricerca del
> minimo percorso hamiltoniano.
> Tu sostituisci al chilometro il costo chilometrico (carburante, bollo,
> assicurazione, etc), e fin qui nulla di strano.

Veramente vorrei implementare il problema del viaggiatore generico,
utilizzando non necessariamente l'auto come mezzo di trasporto ma anche
nave,treno,aereo,moto,pulman , per cui sto facendo un programma dove si
inseriscono le spese di trasporto relative ai vari mezzi e poi non
appena scelto il mezzo di trasporto il costo finisce in automatico nella
matrice dei costi. E' sbagliato questo modo di procedere?

> Ma per il vitto e alloggio come vorresti fare? in un viaggio di 24 ore
> il viaggiatore dorme una volta e mangia tre volte, e in 26 ore cosa fa,
> dorme e mangia il 10% in più?
>

Forse per quanto riguarda le spese di vitto e l'alloggio , queste non
dovrebbero finire nella matrice dei costi, bensì dovrei cercare il
minimo di un elenco di spese di vitto e il minimo di un elenco di spese
di alloggio, che si dovrebbe sommare al costo minimo delle spese di
trasporto ottenuto ripetendo più volte l'algoritmo ungherese alla
matrice dei costi secondo la visita di un albero binario dall'alto in
basso (Branch & Bound).

> I calcoli che hai riportato sono fatti con Lindo, col Simplesso o che
> altro?

Sono fatti con un programma che sto facendo, dopo avere prelevato da
internet un'implementazione dell'algoritmo ungherese .

>Se la tua ricerca è a fini teorici va tutto bene ma se ha un fine
> pratico e coinvolge meno di una decina di località il Branch & Bound, il
> Constraint Generation, il Banch & Cut sono una bella noia.
> Sarebbe molto più semplice usare le permutazioni.
>
> Bruno
>

Col metodo che sto usando (Branch & Bound con algoritmo ungherese), ho
risolto quella matrice dei costi con pochi passaggi. Il problema semmai
è costruire la matrice dei costi e quella dei tempi...
Ciao

[Bruno Campanini]

blake laid this down on his screen :

[...]

> Col metodo che sto usando (Branch & Bound con algoritmo ungherese), ho
> risolto quella matrice dei costi con pochi passaggi. Il problema semmai è
> costruire la matrice dei costi e quella dei tempi...

Col metodo delle permutazioni, soggetto alla limitazione già detta,
risolvi tutto in pochi secondi con un unico passaggio, senza dover
prendere decisioni intermedie, senza approssimazioni e con unica
soluzione: l'ottima.

Comunque buon lavoro.

Bruno

[blake]

Il 10/06/2013 11:12, Bruno Campanini ha scritto:
>
> Col metodo delle permutazioni, soggetto alla limitazione già detta,
> risolvi tutto in pochi secondi con un unico passaggio, senza dover
> prendere decisioni intermedie, senza approssimazioni e con unica
> soluzione: l'ottima.
>
> Comunque buon lavoro.
>
> Bruno
>
>

Effettivamente se ottengo tutte le permutazioni cicliche con luogo di
partenza prefissato e relativo costo, posso prendere il ciclo
hamiltoniano che ha costo minimo.
grazie

[Bruno Campanini]

blake explained :

> Effettivamente se ottengo tutte le permutazioni cicliche con luogo di
> partenza prefissato e relativo costo, posso prendere il ciclo hamiltoniano
> che ha costo minimo.
> grazie

Il ciclo hamiltoniano ottimo è tale da qualsiasi luogo si parta.

3-5-2-4-1-3 --> 35+52+24+41+13 = 41+13+35+52+24 = 13+....

L'ho sviluppato in Excel (VBA): quasi una A4 e mezzo di codice.
Quando l'hai terminato paragoniamo i tempi di esecuzione.

Bruno

[blake]

Il 10/06/2013 15:10, Bruno Campanini ha scritto:
> Il ciclo hamiltoniano ottimo è tale da qualsiasi luogo si parta.
>
> 3-5-2-4-1-3 --> 35+52+24+41+13 = 41+13+35+52+24 = 13+....
>
> L'ho sviluppato in Excel (VBA): quasi una A4 e mezzo di codice.
> Quando l'hai terminato paragoniamo i tempi di esecuzione.
>
> Bruno
>
>

Veramente la soluzione ottima è questa : 1-6-3-5-2-4-1 costo 90,4
ma ce ne sono altre notevolmente minori della tua :
1-3-5-2-4-6-1 costo 91,5
1-3-2-4-5-6-1 costo 92,0

Ciao

[Bruno Campanini]

blake presented the following explanation :

> Veramente la soluzione ottima è questa : 1-6-3-5-2-4-1 costo 90,4
> ma ce ne sono altre notevolmente minori della tua :
> 1-3-5-2-4-6-1 costo 91,5
> 1-3-2-4-5-6-1 costo 92,0

Ma io non mi son riferito ad alcun caso particolare, stavo solo
esemplificando a caso.
Se vuoi un confronto dei risultati fa' un esempio e io ti manderò la
soluzione.
L'esempio però non deve superare le 9 località pena un out of memory
del mio sistema.

Bruno

[blake]

Il 11/06/2013 02:33, Bruno Campanini ha scritto:
> Ma io non mi son riferito ad alcun caso particolare, stavo solo
> esemplificando a caso.

> Se vuoi un confronto dei risultati fa' un esempio e io ti manderￜ la
> soluzione.
> L'esempio perￜ non deve superare le 9 localitￜ pena un out of memory del
> mio sistema.
>
> Bruno
>
>

Per ora ti mando l'esempio di partenza. Se vuoi mandami tu un esempio
con il numero di localitￜ che vuoi ,cosￜ lo provo col programma che sto
facendo.

The matrix is:

1000,00 33,60 14,00 40,90 14,50 11,50
34,70 1000,00 21,70 13,00 20,20 23,40
14,80 21,50 1000,00 29,30 2,00 3,90
41,70 13,10 29,40 1000,00 27,60 30,30
15,00 20,20 2,00 27,50 1000,00 3,90
12,00 22,80 2,00 30,10 4,00 1000,00

Numero di permutazioni con partenza e arrivo in 1 : 120

Sono stati trovati i seguenti cicli hamiltoniani:

(1635241) --> costo=90,40
(1632451) --> costo=90,60
(1635421) --> costo=90,80
(1634251) --> costo=91,10
(1352461) --> costo=91,50
(1624531) --> costo=91,70
(1324561) --> costo=92,00
(1245361) --> costo=92,10
(1342561) --> costo=92,50
(1654231) --> costo=92,60
(1542361) --> costo=92,70
(1652431) --> costo=92,90
(1524361) --> costo=93,00
(1532461) --> costo=93,30
(1642351) --> costo=93,40
(1423561) --> costo=93,60
(1624351) --> costo=93,70
(1653241) --> costo=93,70
(1243561) --> costo=93,90
(1534261) --> costo=94,30
(1653421) --> costo=94,60
(1524631) --> costo=94,80
(1245631) --> costo=94,90
(1542631) --> costo=95,30
(1246351) --> costo=95,90
(1364251) --> costo=96,30
(1362451) --> costo=96,30
(1426351) --> costo=96,40
(1563241) --> costo=96,60
(1365241) --> costo=96,80
(1365421) --> costo=97,20
(1356241) --> costo=97,40
(1563421) --> costo=97,50
(1246531) --> costo=97,70
(1324651) --> costo=97,80
(1356421) --> costo=97,80
(1536241) --> costo=97,90
(1564231) --> costo=98,10
(1426531) --> costo=98,20
(1536421) --> costo=98,30
(1562431) --> costo=98,40
(1423651) --> costo=98,60
(1342651) --> costo=98,80
(1243651) --> costo=98,90
(1632541) --> costo=124,40
(1634521) --> costo=125,30
(1325461) --> costo=125,50
(1645231) --> costo=125,90
(1625431) --> costo=126,20
(1452361) --> costo=126,30
(1345261) --> costo=126,50
(1254361) --> costo=126,60
(1235461) --> costo=127,10
(1623541) --> costo=127,20
(1253461) --> costo=127,40
(1453261) --> costo=127,40
(1625341) --> costo=127,50
(1643251) --> costo=127,70
(1432561) --> costo=127,90
(1523461) --> costo=128,00
(1234561) --> costo=128,10
(1543261) --> costo=128,30
(1254631) --> costo=128,40
(1654321) --> costo=128,60
(1452631) --> costo=128,90
(1463251) --> costo=129,90
(1362541) --> costo=130,10
(1263541) --> costo=130,20
(1364521) --> costo=130,50
(1456321) --> costo=130,60
(1256341) --> costo=130,70
(1263451) --> costo=130,90
(1462531) --> costo=131,00
(1526341) --> costo=131,10
(1354621) --> costo=131,30
(1325641) --> costo=131,40
(1253641) --> costo=131,50
(1326451) --> costo=131,60
(1456231) --> costo=131,70
(1236451) --> costo=131,90
(1256431) --> costo=132,00
(1326541) --> costo=132,10
(1436251) --> costo=132,20
(1345621) --> costo=132,30
(1236541) --> costo=132,40
(1526431) --> costo=132,40
(1346521) --> costo=132,50
(1462351) --> costo=132,70
(1265431) --> costo=132,70
(1543621) --> costo=132,80
(1235641) --> costo=133,00
(1436521) --> costo=133,10
(1532641) --> costo=133,20
(1465321) --> costo=133,40
(1264351) --> costo=133,50
(1534621) --> costo=133,60
(1435621) --> costo=133,70
(1234651) --> costo=133,90
(1562341) --> costo=133,90
(1265341) --> costo=134,00
(1564321) --> costo=134,10
(1432651) --> costo=134,20

Total time required: 0s

[Bruno Campanini]

blake presented the following explanation :

Io calcolo solo 2 hamiltoniani:
quello di percorrenza minima (3524163, 90.40)
quello di percorrenza massima (5143265, 134.20)
tempo di esecuzione = 0.0390625

Coincidono, per forza, coi tuoi risultati.

Bruno