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 prob开发者_如何转开发lem using branch and bound algorithm?
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
This PDF document gives a more detailed explanation of the Branch and Bound implementation for the Traveling Salesperson Problem:
Part 1: A solution with nodes containing partial tours with constraints http://www.jot.fm/issues/issue_2003_03/column7.pdf
Part 2 PDF can also be found. http://www.jot.fm/issues/issue_2003_05/column7/
Step by step explanation of branch and bound method:
- video: https://www.youtube.com/watch?v=RR7GXoWiUw4
- book: https://archive.org/details/algorithmfortrav00litt (link to download in pdf)
- implementation (C++): https://github.com/karepker/little-tsp
I hope my answer will be useful for somebody.
精彩评论