有多個車輛的多個車輛的路由算法

我正在尋找/創建一個路由算法，可以用來管理多個貨車執行交付以及每個這些貨車的負載。有多個車輛的多個車輛的路由算法

這裏是我要找的..

有沒有人見過這樣的事情，如果是這樣，任何想法，到什麼算法可以用來做到這一點，或者它是如何完成的一個例子？我見過一些大學論文，但他們很老（現在可能相當低效），不處理包管理 - 他們只是假設所有的麪包車和包都是相同的大小。

任何想法，將不勝感激！

富

2011-01-19 RichW

歸結爲一個優化問題 - 在合理的時間內完成一個相當困難的工作，特別是對於您的數據量。這樣做的商業產品，特別是在你所談論的規模上，花費了1000美元的10美分。這是有原因的！ – winwaed 2011-01-19 14:24:45

是的，我可以想象，我認爲優化只能走得太遠......找出最終的最佳路線是不可行的。不幸的是，我正在研究具有此功能的商業解決方案，因此我們沒有機會購買現有軟件！ – RichW 2011-01-19 14:42:50

pgRouting有一個新的功能，實現了遺傳算法的打電話問換乘問題：http://www.pgrouting.org/docs/1.x/darp.html

它的PostgreSQL/PostGIS的的擴展，就可以構建這樣的應用程序。它還具有最短路徑搜索等功能。

2011-01-21 02:53:31 dkastl

這個具體的任何算法將是專有的，你可能需要買東西。然而，這聽起來像一個可以用遺傳算法實現的問題。下面是一些研究，我發現：

僅僅因爲一個算法是舊的，並不意味着它的效率不高。

2011-01-19 14:28:04

是的我已經嘗試過遺傳算法來開發這樣的東西。我沒有走得很遠。我的GA可能寫得不好，但我認爲這是不切實際的。模擬退火將是另一種可能的方法。 – winwaed 2011-01-19 14:34:18

優秀的資源，尤其是第二個。我會盡快購買，並通過它，希望它會給我一些想法。我希望修改並不難，我在數學上毫無用處！ – RichW 2011-01-19 14:43:47

我的印象是，這種問題經常出現在Operations Research中，標準方法是使用混合整數規劃求解器。這裏的an example使用MIP編碼貨物運輸調度問題

顯然15年的MIP最近的研究使現代求解器30,000倍比原來的更快。

如果您想從頭開始做一個解決方案，您可以從確定您的目標和約束條件開始，然後使用整數規劃中的一些想法，如近似分支定界搜索。

2011-01-19 18:02:46

回答