2個運輸公司的最短交貨時間

Question

我正在處理一個算法問題。我有一個單一中心節點的已知圖算法。目的是通過兩個運輸商將貨物從這個中央節點運送到其他特定的節點。每個運輸商都可以運送最多。當時是一個貨物單位，所以在每次節點訪問之後，他們都會回到下一個中​​央節點。我應該計算儘可能最短的時間來做到這一點。

我的方法是使用dijkstra algorithm爲中心節點找到所有其他節點的最短路徑，考慮節點之間的不同距離。然後，對於運輸商應該去的所有節點（有時甚至超過一次到特定節點），由於來回距離，我的值增加了一倍。我將數值分成兩組，每組的數值儘可能接近，因爲有兩個運輸工具，並打印出較大的一個。

但是，解決方案似乎並不完美。我需要另一件事來構建它。如果第一輛運輸車知道自己已經結束了工作，那麼我們應該儘快說8個單位，他可以在交貨期間爲第二個運輸車準備一個貨物，這樣他就不必爲了中央節點而選擇貨物，而是少一點。那麼他們的總時間將是平等的，但同時考慮更短。不幸的是，這並不總是可能的（例如，只有一個節點交付給一個節點等）。我需要將這個方面添加到我的程序中。

Answer 1

其實你正在研究一個「車輛路徑」問題，我們可以通過一些方法如啓發式或建設性的方法來解決它。

你可以找到一些有用的（我希望）here關於這種方法。