車輛路由/資源調度算法設計

Question

我的第一篇文章 - 希望你可以幫助我設計一個我現在已經考慮了一段時間的算法 - 不知道要採取什麼方法（VRPTW或資源調度或別的什麼完全！？）

爲了說明一個真實的例子，我們在很少的地方（通常小於5）有很多花園垃圾。廢物必須在規定的時間範圍內運輸到其他地點。爲了移動花園垃圾，我們有拖車，必須用汽車拖車。花園廢物只能在特定時間（時間窗口）的廢物倉庫投放。在一些地點，我們可以將拖車卸下，以便人員填滿或清空，但在其他地點，車輛駕駛員必須自己做，而且車輛必須留在那裏。所有的時間都可以被計算（即裝載/卸載時間，運輸時間等）。汽車可以在沒有拖車的地點之間移動，拖車可以被拖曳空，但拖車不能在地點之間移動。

我們的目標是確保垃圾被運而

• 會議減少拖車和汽車的數量在所有使用時間窗口的脫落廢物的所有拖車負載
• 「平衡」的預告片 - 即在一天結束時，我們在每個位置都有一樣多的預告片，與當天開始時的片尾一樣

我想到了將此作爲資源調度算法，但我不確定如何處理預告片的「平衡」。

我考慮的另一種方法是首先考慮汽車。然後，我可以選擇最早的任務並在此之後構建所有可行任務的圖形。如果我然後選擇圖表中最長的路徑來服務拖車負載的最大數量。然後，我可以從任務列表中刪除這些任務並重復執行，直到完成所有任務爲止。然後我需要運行這些拖車裝載清單來計算所需拖車的數量。

任何想法的方法將不勝感激！

Answer 1

我同意Jiri ...您需要一種啓發式算法，可以快速合理地接近可接受的解決方案，然後從此處進行細化。

我以前在公司工作過的交付路由軟件和他們採取的方法是使用遺傳算法來解決非常相似，但規模較大的問題。如果您不熟悉該方法，請撥打look here。從該網站：

1. [開始]生成n個染色體的隨機人口（針對問題適當的解決辦法）
2. [健身]評估每個染色體X的健身F（X）在人羣中

3. [新人口】通過重複下面的步驟創建一個新的羣體，直到新的人口完成

   [選擇]根據他們的健身（更好的健身，更大的機會被選中）從人口的兩個父染色體

   [交叉]以交叉概率交叉父母形成新的後代（兒童）。如果沒有交叉進行，後代是父母的確切副本。

   [突變]突變概率在每個基因座（染色體中的位置）突變新的後代。

   [接受]將新的後代在一個新的人口

4. [更換]使用新產生的羣體對算法的進一步運行
5. [測試]如果滿足結束條件，停止，並返回最佳在目前的人口
6. [循環]轉到解決方案步驟2

訣竅，這是你的編碼將約束「染色體」，並寫了「健身」功能。適應度函數必須輸入潛在解決方案的結果，並且如果它違反了任何約束條件，則將其解決方案的分數吐出或拋出。

正如Jiri所說，這種解決方案的優點在於它提供了一個可行的，雖然可能不是最好的答案，但答案很快，而且讓它運行得越久，解決方案就越好。

Answer 2

我們在這裏談論一個NP完整的算法，當然，除了一些汽車和拖車之外，這不會是一個任務，你可以從所有可能的解決方案中獲得最佳解決方案，然後放棄並去掉再次避免您建議的最長路徑。如果你以這種方式設計算法，很可能有一天你增加了更多的汽車和拖車，它永遠不會完成計算解決方案。

您可能想要使用算法，可以合理快速生成問題的足夠好的解決方案。確保爲解決方案的質量創建度量標準，您可以通過一種很好的方式來估算理想解決方案的度量值，然後設置一些您希望解決方案來自理想解決方案的％採取第一個解決方案，在度量範圍內。如果這個算法計算時間過長並且放棄它，這還有額外的好處，即使它不在預期範圍內，仍然可以使用計算度量值最低的解決方案。

我不確定採取什麼辦法來解決問題本身。我會建議在acm portal上搜索後閱讀幾篇文章。我會假設UPS和Fedex可能有類似的問題，如果你將它們作爲關鍵字添加到谷歌搜索中，你可以得到一些更有用的結果。

Answer 3

我傾向於同意羅伯特。這對我來說聽起來像是他描述的遺傳算法實現這樣的進化優化技術的非常好的候選人。

我在粒子羣優化（PSO）的某些問題上也取得了很好的成功。基本上，您可以將每個基因組想象成一個多維空間中的粒子。粒子的座標是您計算的參數（適應度函數）。每個粒子以隨機速度隨機開始。對於模擬的每一次迭代，用每個粒子的當前行進向量更新每個粒子的位置，然後添加其他向量的分量，例如：到目前爲止最好的粒子的方向，最好的粒子的方向，到本地組的方向最好等..

它似乎相當艱鉅，在第一實施GA或PSO，但我向你保證，這是很容易寫一個小框架，從實際問題領域的抽象算法（GA/PSO）是你正試圖優化。您可以隨時回到維基百科以瞭解算法的詳細信息。一旦我有了一個框架，我通常從一個2參數問題開始（可能簡化你的問題，或者圖像上的X和Y位置），這樣我可以很容易地可視化和調整算法，這樣我就可以良好的蜂羣行爲。然後我將它擴展到更多維度。

我喜歡這種方法，因爲它使我可以輕鬆地針對實際問題陳述（如汽車和拖車）中具有相當複雜和複雜部分的問題進行優化。

此外，爲什麼演化技術是有吸引力的是因爲您可以將一段固定時間用於模擬，並在您決定停止時採取最佳答案。根據我的經驗，在編寫硬編碼啓發式解決方案時，您傾向於花費盡可能多的時間調整GA或PSO的參數（一旦您有實現），但好處是要改變策略尋找解決方案通常僅需要更改參數或者將非常明確的算法與另一個實現交換出來，而不是編寫完全不同的策略來從頭開始嘗試解決啓發式問題。

如果您需要關於爲兩種算法設計通用框架的指導，請給我留言。我必須指出，你也有幾個很好的免費第三方框架。我有時候喜歡自己編碼，因爲我理解算法的每個方面，然後我知道我可以在哪裏調整策略。

Answer 4

一般方法：

既然問題是小，直到你得到一個可行的解決方案，而不是試圖減少汽車和拖車，我建議在此處添加汽車和拖車的方法。

解決：

我已經對燃氣具約束較少的成功和天然氣甚至更少成功與整型變量的約束（例如拖車的位置數）。這可能是約束規劃是一種更好的方法，因爲您只是想爲給定數量的汽車和拖車生成一個可行的解決方案，而不是試圖最小化行駛距離。

觀察：

你的網絡中的最後一個動作可能會重新定位一個空的拖車上解決問題。

祝你好運！

Answer 5

本地搜索是遺傳算法的替代方案。在局部搜索算法（如禁忌搜索和模擬退火算法）中，顯然擊敗了遺傳算法條目（在約80名競爭對手IIRC中，LS的第1到第4位與第1軌中GA的第5位）。另外，看一下這裏的一些庫，比如OptaPlanner（禁忌搜索，模擬退火，延遲接受，開源，java），JGap（遺傳算法，開源，java），OpenTS（Tabu搜索，...