OptaPlanner VRP邊權重需要使用實際的GPS數據，而不是歐幾里得距離

Question

我是optaplanner的新手。我試圖修改vrp示例[CVRP或VRPTW]是否支持多於僅作爲節點之間的邊權重的歐幾里德距離。我正在使用最新版本的optaplanner 6.0.0.CR5。任何關於如何改變節點之間邊緣權重的建議都將非常感謝。

謝謝

Answer 1

有幾種方法可以解決這個問題。所有假設你有一個GPS系統（如谷歌地圖），可以很容易地返回2點A和B之間的距離。

請注意，這是GPS的系統責任，決定從A到B的實際道路（這是不是NP完全問題，GPS系統已經爲其優化）。 OptaPlanner將決定執行A，B，C，D，...（這是NP完成）的順序。

A）計算在臨時的距離（不推薦）

只是到您的GPS系統中的呼叫替換獲得Location.get...Distance(Location)方法。

缺點：通常這種方法被稱爲每秒數千次，並且您的GPS系統不會返回那麼快的答案，會極大地減慢您的平均分數計算。

B）預先計算的距離和在內存

存儲在類Location，添加一個Map<Location, int> dinstanceMap到保持到每個其它Location的距離。填寫Map，然後致電solve()並執行get...Distance()以僅做return distanceMap.get(otherLocation)。

缺點：內存擴展：如果客戶太多，你會得到一個OutOfMemory異常。

解決方法：對於每個Location，只添加該地圖中距離最近的1000個位置。篩選移動選擇器，以便它永遠不會嘗試連接不在彼此的地圖中的2個位置。這可能會影響結果的質量。

C）預先計算的距離，並將其存儲在磁盤上和存儲器

同B）對其進行緩存，但由於距離矩陣太大，將其存儲在磁盤上。如果最近沒有被問到，使用緩存只能從磁盤獲取一個值。