TSP - Branch and bound

Question

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?

Oded Yes but, i look for some help. I don't wont to solve this problem for me. I looke for help, to steer. I don't wont to write this for me. ... — gummmibear, Jan 28 '10 at 11:58

score 4 · Answer 1 · edited Nov 26 '16 at 08:24

4

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

edited Nov 26 '16 at 08:24

John

896
9
19

answered Jan 28 '10 at 12:12

laura

7,280
4
35
43

score 2 · Answer 2 · edited Jul 15 '16 at 06:47

2

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/

edited Jul 15 '16 at 06:47

Sergey Telshevsky

12,077
6
55
78

answered May 07 '13 at 01:14

juejiang

323
4
15

score 1 · Answer 3 · answered May 12 '17 at 15:09

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.

TSP - Branch and bound

3 Answers3

Linked