具有重复节点和动态权重的旅行推销员

Question

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

目前,我忽略了航班日期的问题,并假设可以从任何城市前往任何其他城市.

有没有人有任何想法如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第2点,并根据行程中是否包含返程/往返航班来评估目标函数时简单地调整边权重,但也许其他人有更好的理念.

(注意:我使用的是MATLAB,但我不是专门寻找编码解决方案,更多的是关于可以使用哪种算法的高级想法.)

编辑 - 在考虑了这个之后,允许"重复节点"似乎过于松散了约束.我们可以进一步约束问题,以便尽管可以重复访问节点,但每个有向边只能访问一次.忽略任何不止一次包含同一航班的行程似乎是合理的.

Answer 1

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

Answer 2

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