TSP - branch and bound

Question

Hi. I'm trying to solve the TSP with branch and bound algorithm.

I'm must bulid a matrix with cost but i have one big problem. I have city with coordinates x and y.

The cost of travel is ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + days in city. V is speed.

Days in city depend from day when w come to city. For example when we arrived on Monday(t1) to city 1. we stay 9 days but when we arrived on tuesday we stay in city 4 days.

         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

How can i solve this problem using branch and bound algorithm?

Answer 1

Here you go: http://lcm.csa.iisc.ernet.in/dsa/node187.html - it seems to explain fairly well how this should be approached.