通過用戶定義點的TSP

Question

我有一些點集，​​並有點的子集，標記爲「靜態」。所以我需要解決TSP問題，它將創建包括靜態位置上的標記點在內的最佳路徑。我該如何解決它？

可能是我的問題可以通過另一種方式解決：點有兩個主要特點 - 彼此之間的距離和時間，推銷員必須在哪裏。是否有一些問題解決了這個物流任務？

UPD我不明白，非靜態點的TSP如何與靜態點的TSP合併？

Answer 1

如果我正確理解你的問題，它只是你的靜態，非靜態位置和距離/時間矩陣定義的另一個旅行推銷員問題。如果您的原產地問題非常大，那麼首先解決原產地問題的TSP（並且僅一次）可能是有意義的。然後考慮到「非靜態」或用戶定義的位置，例如，所產生的解決方案可用於指定新的初始解決方案。只是通過一個簡單的最佳插入。然後，您可以改進此初始解決方案，例如Lin-Kernighan開發和應用的k-opt啓發式方法（http://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic）。
如果您的原產地問題很小，只需解決另一個TSP（考慮您的「靜態」和「非靜態」位置）。

Answer 2

基本上有三種方法來TSP：

1. 蠻力
2. 啓發式
3. 逼近

使用蠻力可以爲節點數量較少的選項。它涉及生成所有(n-1)!排列並只計算它們的長度。根據您的問題，您必須更改的算法是生成可能的往返程序以排除靜態點不在其指定位置的算法。

使用啓發式算法（如模擬退火），可以計算TSP以解決更大的問題，但不能保證完美的往返，只是一個好的往返。這些通常採用現有的解決方案，並從中得出一個隨機的不同解決方案（或多個解決方案）。適應您的問題，如果違反了靜態點位於其指定位置的要求，則只需放棄衍生解決方案。

第三個變體使用的算法爲您提供了多項式時間的往返行程，例如，沿着最小生成樹行走，向一個方向掃過或貪婪地橫穿它們。這些提供了良好的時機，但是對於所得往返的質量進行了權衡。我不清楚如何使這些解決方案適應需要某些特定位置的解決方案。由於它們的簡單性，它們不容易適應這些附加要求。