TSP - Branch and bound
Ich versuche den TSP mit Branch and Bound Algorithmus zu lösen.
Ich muss eine kostenpflichtige Matrix erstellen, habe aber folgendes Problem: Ich habe eine Stadt mit den Koordinaten x und y.
Die Reisekosten betragenceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + Tage in der Stadt verbracht. V ist Geschwindigkeit.
Die Tage in der Stadt hängen vom Tag ab, an dem wir in die Stadt kommen. Wenn wir zum Beispiel am Montag (t1) in Stadt 1 ankommen, bleiben wir 9 Tage, aber wenn wir am Dienstag ankommen, bleiben wir 4 Tage in der Stadt.
x y t1 . t7
city 1. 79 -36 9 4 8 5 5 7 8
city 2. 8 67 6 9 2 1 9 9 1
city 3. 29 57 7 5 10 8 10 9 4
Wie kann ich dieses Problem mit dem Branch-and-Bound-Algorithmus lösen?