24

鉴于城市列表和每个城市之间的飞行成本，我试图找到访问所有这些城市的最便宜的行程。我目前正在使用MATLAB 解决方案来寻找最便宜的路线，但我现在想修改算法以允许以下内容：

  1. 重复节点- 应该允许重复节点，因为通过枢纽城市旅行通常会导致更便宜的路线
  2. 动态边权重- 往返航班的成本与两个等效的单程航班不同（通常更低）

目前，我忽略了航班日期的问题，并假设可以从任何城市旅行到任何其他城市。

有谁知道如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第 2 点，并在根据行程是否包含往返航班来评估目标函数时简单地调整边缘权重，但也许其他人有更好的主意。

（注意：我使用的是 MATLAB，但我并不是专门寻找编码解决方案，更多的是关于可以使用哪些算法的高级想法。）

编辑 - 在考虑了更多之后，允许“重复节点”似乎过于宽松的约束。我们可以进一步约束这个问题，使得虽然节点可以被重复访问，但每个有向边最多只能被访问一次。忽略任何包含同一方向同一航班的行程不止一次似乎是合理的。

4

6 回答 6

5

我自己没有测试过；但是，我已经读到实施模拟退火来解决 TSP（或其变体）可以产生出色的结果。这里的关键点是模拟退火非常容易实现并且需要最少的调整，而近似算法可能需要更长的时间来实现并且可能更容易出错。Skiena 还有一个专门针对特定 TSP 求解器的页面。

于 2011-03-14T16:46:30.960 回答
0

如果将问题限制在往返（即售货员只能购买往返票），则可以用无向图表示，问题归结为找到最小生成树，这可以有效地完成。

在一般情况下，我不知道使用高效算法的聪明方法；GA 或类似的可能是一个不错的选择。

于 2011-05-03T15:40:09.457 回答
0

你想要一个接近最优的解决方案，还是你想要一个最优的解决方案？

对于最佳解决方案，仍然有很好的蛮力。由于要求 1 涉及重复节点，您必须确保搜索广度优先，而不是部门优先。否则，您可能会陷入无限循环。您可以慢慢丢弃所有超过当前最小值的路由，直到所有路由都用尽并找到最小路由。

于 2011-07-20T22:43:23.647 回答
0

解决 TSP 是一个 NP-hard 问题，因为它的子周期消除约束，如果你删除它们中的任何一个（对于你的中心城市），你只会让问题变得更容易。

但请注意：TSP 与关联问题的相似之处在于您可能会获得无效的行程，例如：

城市：纽约、波士顿、达拉斯、多伦多

小路：

波士顿 - 纽约 纽约 - 波士顿

达拉斯 - 多伦多 多伦多 - 达拉斯

这显然是错误的，因为我们没有遍历所有城市。

子循环消除约束正是为此目的。包括一个“中心城市”听起来你需要增加权重，并在通量问题和 tsp 问题之间进行混合。听起来很难，但第一次尝试可能是：消除与您的中心城市相关的子周期限制（并留下所有其他限制）。然后，您可以将为中心城市获得的子周期链接在一起。

祝你好运

于 2011-03-29T11:20:41.213 回答
0

如果您希望算法产生的解决方案的成本在最优值的 3/2 以内，那么您需要 Christofides 算法。ACO 和 GA 没有保证费用。

于 2011-03-12T06:42:44.783 回答
0

Firstly, what is approximate number of cities in your problem set? (Up to 100? More than 100?) I have a fair bit of experience with GA (not ACO), and like epitaph says, it has a bit of gambling aspect. For some input, it might stop at a brutally inefficient solution. So, what I have done in the past is to use GA as the first option, compare the answer to some lower bound, and if that seems to be "way off", then run a second (usually a less efficient) algorithm.

Of course, I used plenty of terms that were not standard, so let us make sure that we agree what they would be in this context:

  1. lower bound - of course, in this case, MST would be a lower bound.
  2. "Way Off" - If triangle inequality holds, then an upper bound is UB = 2 * MST. A good "way off" in this context would be 2 * UB.
  3. Second algorithm - In this case, both a linear programming based approach and Christofides would be good choices.
于 2011-03-27T04:12:45.143 回答