Menu
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?
682
The branch-and-bound algorithm for the traveling salesman problem uses a branch-and-bound tree, like the branch-and-bound algorithms for the knapsack problem and for solving integer programs. The node at the top of the tree is called the root. All edges (arrows) in the tree point downward.
The time complexity of the program is O(n^2) as explained above for the row and column reduction functions.
A lower bound can be found by removing a vertex, then finding a minimum spanning tree: Use Prim's or Kruskal's algorithm to find the length of the minimum spanning tree. Add to this the lengths of the two shortest edges connected to the missing vertex.
TSP can be modelled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once.
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
122
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/
23
Step by step explanation of branch and bound method:
I hope my answer will be useful for somebody.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
