TSP - Branch and bound

algorithm, branch-and-bound, traveling-salesman

Solution

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

Archive.org link

Problem

I'm trying to solve the TSP with Branch and bound algorithm. I must build a matrix with costs but I have this problem: I have city with coordinates x and y. The cost of traveling is `ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v)` + days spent in the city. V is speed. Days spent in the city depends from day when w comes to the city. For example if we arrived on Monday(t1) to city 1, we stay for 9 days but if we arrived on Tuesday, then we stay in the city for 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?

Original source