Problema del Commesso viaggiatore

Branch and Bound per il problema del TSP Asimmetrico

Sia dato un grafo orientato, il problema del commesso viaggiatore (TSP) consiste nel determinare un Ciclo Hamiltoniano di costo minimo.

Ciclo Hamiltoniano

Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l’ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza.

Link to original

Quindi, assegnati dei costi agli archi, si vuole determinare il ciclo che tocchi ogni nodo di G una e una sola volta e che abbia costo minimo

Formulazione Matematica TSP

Per applicare il Metodo del Branch and Bound al TSP dobbiamo capire, anche qui:

• Come ottenere l’upper bound
• Come fare branching
• Come ottenere un lower bound

Troviamo un lower bound, eliminando i vincoli sui sottocicli.

Così otteniamo il Problema dell’assegnamento.

L’assegnamento si opera sul grafo bipartito completo che si ottiene duplicando i nodi di G.

Se l’assegnamento dà un ciclo hamiltoniano, abbiamo la soluzione del TSP.

Altrimenti, vuol dire che ci sono dei sottocicli Li possiamo usare per il branching. La dimensione del branching sarà pari alla cardinalità minima dei sottocicli.

Dalla soluzione dell’assegnamento, prendiamo il sottociclo di cadinalità minima e generiamo tanti problemi quanti sono gli archi di tale sottociclo.

Regola Generale TSP

Dato il sottociclo

Si generano i vincoli di branching imponendo per il primo figlio , per il secondo figlio , e così via fino al figlio k-esimo, per il quale tutti i precedenti saranno 1 e per se stesso 0.

Imporre che vuol dire richiedere che nella matrice dei costi

Upper Bound

Si determina con l’algoritmo del nodo più vicino.

Si parte dal primo nodo e si cerca il nodo successivo connesso con costo minimo.

Esaminati tutti i nodi si trova un ciclo hamiltoniano.