算法：航行計劃

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啓發，在那裏你
• 利用現有建設啓發式，
• 隨機化是使多個運行將會給你多種解決方案，
• 運行隨機版本多次
• 起飛這是最好的解決方案。