algorithm - 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?

Answer 1

给你： http: //lcm.csa.iisc.ernet.in/dsa/node187.html - 它似乎很好地解释了应该如何处理。

Archive.org 链接

Answer 2

此 PDF 文档更详细地解释了旅行销售员问题的分支定界实现：

第 1 部分：节点包含带有约束的部分游览的解决方案http://www.jot.fm/issues/issue_2003_03/column7.pdf

也可以找到第 2 部分 PDF。http://www.jot.fm/issues/issue_2003_05/column7/

Answer 3

分步定界法的逐步解释：

• 视频：https ://www.youtube.com/watch?v=RR7GXoWiUw4
• 书：https ://archive.org/details/algorithmfortrav00litt （链接下载pdf）
• 实现（C++）：https ://github.com/karepker/little-tsp

我希望我的回答对某人有用。