具有多個起點和一個終點的旅行推銷員

我正在嘗試製作一個Google地圖應用程序，其中涉及從不同位置的車輛路線。例如，假設有三輛車分別位於不同的位置，他們必須覆蓋10個地點併到達一個共同的目的地。我需要找到用3輛車覆蓋所有10點的最佳方式。我知道Google Directions API提供了一個「方便點」功能來解決旅行商問題，但只有一種車輛。我看着車輛路線問題，但無法找到解決問題的算法。如果有人能指出我解決這個問題的正確方向，我將不勝感激。具有多個起點和一個終點的旅行推銷員

來源

2014-01-17 anishk25

每輛車都必須參觀所有10點嗎？或者這些積分是否必須至少有一輛車？ –

只需要覆蓋一次。它可以覆蓋任何車輛 – anishk25

而且我認爲沒有訪問任何城市的汽車可以直接前往目的地是可以的嗎？另外，我們是最小化距離還是時間？如果每個城市都有體重說明駕駛員需要花費多少時間，那麼我們可能會得到非常不同的結果。 –

我相信這可以被定義爲一個網絡流量問題，並通過線性規劃解決。大多數關於線性規劃的書籍解決了這些問題例如，以下是從一本書chapter上優化

在你的情況我會模擬你的出發地點爲源，汽車作爲產品被運輸，城市是節點，單水槽是最終的目的地。路線上的權重是距離。

網絡流量問題的一個特例是「最短路徑樹問題」（上文提到的論文的第8頁），這聽起來像是你確切的問題，只是相反：你從一個公共點開始並移動到其他節點。解決您的問題應該是一樣的。

來源

2014-01-17 22:11:17

'用線性規劃求解'不可能是正確的，因爲TSP是NP-hard，而線性規劃是多項式時間。也許你的意思是這個問題可以被定義爲INTEGER線性規劃，並且通過ILP的標準線性規劃放寬來近似？ – user2566092

@ user2566092這根本不是旅行商問題，它更接近最小生成樹。事實上，我想我可以通過預先計算節點間地圖上的最小路徑來將其減少到最小生成樹問題的特殊情況。 –

@Codie CodeMonkey.Thanks尋求幫助。你是說首先計算圖中每個節點之間的最小路徑，然後使用最小生成樹算法？在我的情況下，我需要使用Google Maps來計算從一個選定節點到所有其他節點的距離，併爲所有節點執行此操作。 – anishk25

您可以將此模型設置爲旅行推銷員問題（一位銷售人員訪問所有城市並返回其出發點）。您必須對該問題進行的修改爲：

從終點到起點的費用爲零。終點應與有汽車一樣多次複製。

TSP的解決方案將提供一個以最低成本連接所有城市的旅程。從一個起點到結束點的其中一個副本的每條路徑（此行程的一部分）是汽車應採取的路線之一。

由於此解決方案可以使用最先進的TSP解算器，因此您可能比使用自己構建的算法獲得更好的結果。

來源

2014-01-30 12:23:19 Vortexfive

具有多個起點和一個終點的旅行推銷員

回答

相關問題