基於距離和約會時間的預約位置路線

Question

我想開發一種算法，在人員需要從他/她的辦公室開始訪問的不同地點的位置和約會時間中進行。在完成所有預約訪問後，此人必須回到辦公室。我想規劃路線爲他/她，涵蓋這樣的方式，所有的約會：

• 他/她的旅行的最小距離
• 考慮到該帳戶的預約時間路線建設。也就是說，在決定接下來應該訪問哪個位置時，預​​約時間應優先於兩個位置之間的距離。

我的問題是開放式的。我知道，如果我只是想考慮構建路線的距離，這直接適用於旅行推銷員問題。但是，我也想把預約時間考慮在內。我對圖很陌生，我想知道這個問題是否適合我不知道的其他算法。如果沒有，我正在尋找修改TSP算法以考慮這兩個參數的建議。

在考慮這個問題的時候，我考慮過如何實現Dijkstra尋找路線。我知道這與TSP完全不同。但是，您認爲我可以結合兩個參數（距離和約會時間）來比較我的優先隊列ADT中的兩個節點是否爲Dijkstra。

可能這兩個問題需要不同的問題，但我覺得這是一個常見問題。我在尋找有關解決這些圖形問題的建議，其中有兩個因素需要考慮。我如何獲取兩個參數並將它們合併爲一個，以便我可以比較兩個節點？

Answer 1

假設你需要按時約會而不是早期，那麼你可以從一個完全連通的圖開始，然後根據約會時間消除節點之間的邊緣，如果它們相距太遠。

例如，如果節點A的時間爲10:00，節點B的時間爲11:00，且它們之間的最短距離超過1小時，則可以修剪此邊緣。

這也包括修整邊緣（A，B）如果節點A節點B後的約會時間

這一點，你只需要找到最短哈密頓圈之後 - 這是TSP。

編輯：直接回答你的問題：沒有必要考慮TSP部分問題的預約時間。只需設置圖（如上所述），然後運行TSP算法。