algorithm - TSP - 分支定界

Question

我正在尝试使用分支定界算法解决 TSP。

我必须建立一个包含成本的矩阵，但我遇到了这个问题:我有坐标为 x 和 y 的城市。

旅行的费用是 ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + 在城市中度过的天数。V 是速度。

在城市中度过的天数取决于 w 来到城市的那一天。例如，如果我们在星期一 (t1) 到达城市 1，我们会停留 9 天，但如果我们在星期二到达，那么我们会在城市停留 4 天。

         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

如何使用分支定界算法解决这个问题？

Answer 1

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

Archive.org link