算法：航行计划

Question

我需要计划一次航行，将具有指定起点和指定目的地的海中的n个位置连接到以下约束。
航程必须触及所有位置。
如果有从A到B的预订，那么必须在B之前触摸a
每个位置的时间花费有所不同（取决于对该位置的预订）
每个位置都有一个工作窗口。如果船只在工作窗口之前到达，它必须等待。
注：“最小生成树”算法可能不会像在每个端口所需的时间取决于以前的路线上（由于工作窗口）
是否有可用于此的任何算法？

Answer 1

Ant colony optimization似乎是最知名的解决这个。请注意，这是一个NP problem，实际上甚至是NP完全问题。这意味着验证解决方案是否“正确”很“容易”，但找到它却“很难”。找到“最佳”解决方案的唯一途径是尝试所有可能的解决方案，比较结果并采取最佳解决方案。当然，如果你想在合理的时间范围内解决这个问题，这是不可接受的。

蚁群算法会找到一个很好的解决方案，接近最佳。我说得很接近，因为AFAIK并不能保证总能找到最好的。可能有更好的解决方案然而，通常没有必要真正找到可能的最佳解决方案，只需“非常好”的解决方案就可以实现，ACO就是您正在寻找的。它可以在合理的时间间隔内找到解决方案，并且解决方案肯定会有好处。

在你的情况，你需要稍作修改。通常它只会尝试找到最短的路线，只考虑路径。在你的情况下，它必须考虑你的工作窗口，预订和花费在一个位置上的时间。但这些只是“蚂蚁如何旅行”的修改，基本算法保持不变，仍然可以工作。

Answer 2

见Traveling salesman problem

Answer 3

这是一个旅行商问题的修改增加了工作窗口的限制......这意味着解决这个问题将更难找到比标准旅行商问题。

我已经是体面的工作给予近似解的几种方法。

1. Genetic Algorithms
2. Tabu Search
3. Randomized Algorithm（例如，随机漫步）

我不知道是否适用于您的问题，从我的头顶，我说这不，但dynamic programming偶尔可用于棘手的问题。

Answer 4

在这个问题上有很多工作。它通过不同的名称

1. 旅行推销员（车辆路线）问题与时间窗口和优先约束。
2. 接送问题。

有很多关于这个问题的研究，其中很多都在运筹学研究Journals。这个问题一般来说是NP-Hard，所以对问题的一般准确解决方案与您描述的问题不符，但可能会有针对您的具体问题的好的，准确的或近似的解决方案。最好的算法将是你的数据的函数。

• 你的数据集有多大。如果“n”相对较小（30-100），则可能会有与math programming的确切解决方案。
• 时间窗口和优先约束有多紧密。如果在任何时间窗口访问的可能位置数量很小，那么可以使用动态编程等解决方案。
• 如果找不到特殊情况，那么您可能希望将启发式构造算法与本地搜索后处理器相结合。一个简单的方法是所谓的GRASP启发，在那里你
• 利用现有建设启发式，
• 随机化是使多个运行将会给你多种解决方案，
• 运行随机版本多次
• 起飞这是最好的解决方案。