OptaPlanner自行車信使/ TSPPD

尊敬的OptaPlanner專家！OptaPlanner自行車信使/ TSPPD

我想使用OptaPlanner（或類似的開源Java框架）來優化自行車信使服務的路線。假設5個使者不得不拿起30個信封從一定的淵源，並提供他們一定的目的地：

  X(FROM) Y(FROM) X(TO) Y(TO) 
envelope 1 13745 55419 13883 55756 
envelope 2 8406 53246 13937 55854 
envelope 3 15738 57396 35996 79499 
envelope 4 12045 60418 19349 57118 
envelope 5 13750 56416 35733 78403 
envelope 6 13190 57068 11860 59749 
envelope 7 15021 55768 14098 57379 
envelope 8 11513 58543 11501 59683 
envelope 9 12013 64155 14120 59301 
envelope 10 15006 57578 35511 78426 
envelope 11 11450 58819 11916 58338 
envelope 12 13728 56304 35524 79013 
envelope 13 15104 60923 17937 57066 
envelope 14 11373 58388 13983 53804 
envelope 15 18575 55186 18718 54381 
envelope 16 11639 50071 17363 58375 
envelope 17 11273 53410 10860 60441 
envelope 18 13766 59041 13963 57769 
envelope 19 16138 55801 16183 56024 
envelope 20 13728 56146 14301 61694 
envelope 21 12848 57059 13586 59734 
envelope 22 13645 56488 13955 55859 
envelope 23 12896 56838 13937 55908 
envelope 24 13341 58150 35709 78924 
envelope 25 13483 57303 13614 57820 
envelope 26 12741 63478 15230 59838 
envelope 27 14676 51691 16501 48361 
envelope 28 13748 54933 14120 56110 
envelope 29 17875 59565 20453 61903 
envelope 30 9772 56424 6404 55601

我的五個信使通過城市分佈（所以我沒有一個單一的倉庫），他們沒有回到他們開始的地方：

  X  Y 
messenger A 13750 57578 
messenger B 15104 53410 
messenger C 13728 55801 
messenger D 12741 63478 
messenger E 14676 18575

我會用下面的硬約束：

每一個信使可以進行長達十五信封
信封旅行應小於三次直接路由的方式（所以運輸並不需要太長時間）

而這些軟約束：

優化信使有路以循環

我想我必須調整車輛路線的例子，但由於我是一個新手，我不知道從哪裏開始。如何確保在信使試圖傳遞信封之前收到信封？如果你能幫我在這裏...

謝謝！

來源

2013-09-29 user2828726

採取VRP（車輛路徑）示例和調整它像這樣：

重命名類Vehicle到Messenger
改變類Messenger的depot屬性startingLocation
刪除「車輛回到倉庫「限制（除非信使需要返回到他們的起始位置）。
類Customer重命名爲EnveloppeExchange類型PICKUP或DELIVERY
注意：如果一個拾取和遞送EnveloppeExchange具有相同的位置，使用2個獨立的EnveloppeExchange實例。
在EnveloppeExchange中添加一個叫做messengerContents的影子變量，它列舉了到達那個EnveloppeExchange的信使集。編寫一個VariableListener（請參閱文檔），使影子變量保持最新。
添加該messengerContents在輸送EnveloppeExchange必須包含所需ENVELOPPE
約束添加的約束，該messengerContents在任何EnveloppeExchange必須不更大然後15
添加的約束，任何信封X，總和EnveloppeExchange的messengerContents包含該信封X的距離不得超過直接路由的3倍。

最好使用6.0.0.CR4（今天發佈）。

來源

2013-09-30 05:47:19

嘿傑弗裏，感謝您的快速答案。我成功地重命名爲'Messenger'和startingLocation，然後刪除了「車輛返回到車廠」的限制。我現在要添加PICKUP和DELIVERY類型。你將如何導入這些類型？您首先導入ID和位置列表，然後導入ID和需求，然後導入ID是起始位置還是倉庫。你會添加另一個列表，指定它是PICKUP還是DELIVERY？如果是這樣，你怎麼知道什麼信封屬於PICKUP和什麼DELIVERY位置？ – user2828726

我不是OptaPlanner的專家。但是我想提取你在括號中提到的內容（或類似的開源框架）。但是，如果OptaPlanner已經爲您提供了合理的解決方案，那麼您可能會忽略這一點。如果不是，或者你只是想比較結果，這可能對你很有意思。

首先，你所描述的問題聽起來很簡單，但卻是一個更具挑戰性的問題。它基本上是一個帶有代收和發貨，多個倉庫，開放路線和時間窗口/限制的可容納VRP。您可能無法找到許多針對此類問題的開源解決方案。

我創建了一個名爲jsprit的項目。 jsprit可以解決你的問題。它與OptaPlanner既不相似，也不是框架。它非常關注車輛路徑問題，並且是一個Java工具箱（即一組庫）。我實現了你的問題。 Here你可以找到註釋的代碼。

我稍微改變了一個約束條件（「信封行進的方式應該少於直接路線的三倍，因此交貨時間不會太長」）。如果你想確保交付速度相對較快，我相信你最好相對於「最好」的使者制定這個約束。因此，我用（「信封行進的方式應該小於使用信使的直接路線的三倍，即直接路線上最快的信使」）。看看結果（你可以繪製它並得到一個簡短的報告），並與其他約束或算法配置一起玩，以適應你的需求。如果您有任何疑問，請不要猶豫與我聯繫。

jsprit是絕對的術語，與OptaPlanner相比，這是一個非常年輕的項目，最終你發現錯誤或約束定義並不是那麼舒服。但好處是，通過報告錯誤，批評和建議替代解決方案等，您可以幫助改進它。

來源

2013-12-05 23:01:39

OptaPlanner自行車信使/ TSPPD

回答

相關問題