首頁(yè) 猿問(wèn) 如何在 Google...

如何在 Google OR-Tools 中指定路線的結(jié)束位置？

Python

蝴蝶刀刀 2023-06-13 11:01:59

我有一個(gè)有效的車(chē)輛路徑問(wèn)題解決方案，它是在 Python 中使用 Google 的 OR-Tools 實(shí)現(xiàn)的。我有一個(gè)包含 16 個(gè)位置的時(shí)間矩陣、每個(gè)位置的時(shí)間窗口以及丟棄每個(gè)位置的懲罰。所有值都以秒為單位。我有意只用一輛車(chē)解決這個(gè)問(wèn)題（實(shí)質(zhì)上是解決旅行推銷(xiāo)員問(wèn)題）。只要需要，我允許車(chē)輛在任何地點(diǎn)等待。我已將某些位置的掉落懲罰設(shè)置得非常高，因?yàn)槲也幌胱屗鼈兊袈?。時(shí)間矩陣中表示的每個(gè)位置都會(huì)有一個(gè)時(shí)間窗口，它表示自一天開(kāi)始以來(lái)的時(shí)間（28800 相當(dāng)于上午 8:00，64800 相當(dāng)于下午 6:00，等等）我設(shè)置上限最大值為 64800，因?yàn)槲蚁Ｍ?chē)輛在下午 6:00 之前完成。我已將矩陣中的第一個(gè)位置指定為起始位置?，F(xiàn)在，我希望矩陣中的第二個(gè)位置是結(jié)束位置。下面是我的源代碼 - 它運(yùn)行成功，但確實(shí)使用矩陣中的第二個(gè)位置作為它創(chuàng)建的解決方案的結(jié)束位置。輸出{'Dropped':?[4,?5],?'Schedule':?[[0,?28800,?28800],?[9,?28901,?29249],?[13,?31173,?31521],?[15,?33414,?33762],?[8,?36292,?36640],?[14,?39535,?39883],?[2,?43200,?43200],?[6,?45676,?46195],?[7,?47868,?48387],?[3,?50400,?50400],?[11,?54641,?57541],?[10,?56997,?59897],?[12,?59663,?62563],?[1,?64800,?64800],?[0,?64800,?64800]]}我的理解是需要對(duì) RoutingIndexManager 進(jìn)行主要更改。就像 Google OR-Tools 文檔似乎表明的那樣，我嘗試了以下更改：manager?=?pywrapcp.RoutingIndexManager(len(Matrix),1,0)到manager?=?pywrapcp.RoutingIndexManager(len(Matrix),1,[0],[1])但這會(huì)導(dǎo)致錯(cuò)誤：WARNING:?Logging?before?InitGoogleLogging()?is?written?to?STDERR F0820?15:13:16.748222?62401984?routing.cc:1433]?Check?failed:?kUnassigned?!=?indices[i]?(-1?vs.?-1)? ***?Check?failure?stack?trace:?***我在使用 OR 工具時(shí)是否存在任何明顯的錯(cuò)誤？我很樂(lè)意回答任何問(wèn)題。任何幫助將不勝感激！謝謝你！

查看完整描述

1 回答

海綿寶寶撒

TA貢獻(xiàn)1809條經(jīng)驗(yàn) 獲得超8個(gè)贊

首先，正確更改管理器構(gòu)造函數(shù)代碼。

????#?Create?the?routing?index?manager.[-]?manager?=?pywrapcp.RoutingIndexManager(len(Matrix),?1,?0)
[+]?manager?=?pywrapcp.RoutingIndexManager(len(Matrix),?1,?[0],?[1])

其次，您不能在析取中指定開(kāi)始或結(jié)束節(jié)點(diǎn)：

????#?Allow?to?drop?nodes.[-]?for?node?in?range(1,?len(Matrix)):
[+]?for?node?in?range(2,?len(Matrix)):
??????routing.AddDisjunction([manager.NodeToIndex(node)],?Penalties[node])

第三，您不能在開(kāi)始或結(jié)束節(jié)點(diǎn)上使用NodeToIndex(node_index)，因?yàn)樗⒉豢偸请p射。

????#?Add?time?window?constraints?for?each?location?except?start?and?end?location.
????for?location_idx,?time_window?in?enumerate(Windows):
[-]???if?location_idx?==?0:
[+]???if?location_idx?==?0?or?location_idx?==?1:????????continue
??????index?=?manager.NodeToIndex(location_idx)
??????time_dimension.CumulVar(index).SetRange(time_window[0],?time_window[1])

最后，一定要在結(jié)束位置設(shè)置一個(gè)時(shí)間窗口：

????index?=?routing.Start(0)
????time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
[+]?index?=?routing.End(0)
[+]?time_dimension.CumulVar(index).SetRange(Windows[1][0],Windows[1][1])

反對(duì) 回復(fù) 2023-06-13