計算在同一時間

Question

我有兩個驅動程序和每個駕駛員都有一套約15個地點，他們需要把車開到單日最快的路線和一些點。計算兩個驅動程序的最短路徑不是問題（使用矩陣路由API）。

的驅動程序可以在他們的路線相同的位置。如果它們一樣，那麼它們都需要同時在那裏。所以我需要製作計算最快路線的軟件，但有時候司機需要同時在同一地點。

我的問題：我怎樣才能使這個軟件，並在那裏我可以使用任何庫？

實施例具有6個位置（軟件需要計算15）：

駕駛員A的位置：

• 51.873215,4.606388（開始）
• 51.7498817,4.3705702
• 51.8395805,4.3535099（與驅動程序B相同）
• 51.8961411,4.4681101
• 52.0041504,4.48627
• 52.061006,4.486609（結束）

位置驅動B的：

• 51.873215,4.606388（開始）
• 51.7914314,4.6571202
• 51.8422203,4.33954
• 51.8670325,4.3453742
• 51.8395805,4.3535099（同駕駛員A）
• 51.7084897,4.6603792（結束）

軟件需要對座標進行排序以獲得最快的路線。但司機必須在這個位置上的同一時間同一地點：51.8395805,4.3535099

預期的輸出驅動器答：https://www.google.nl/maps/dir/51.873215,4.606388/51.8395805,4.3535099/51.7498817,4.3705702/51.8961411,4.4681101/52.0041504,4.48627/52.061006,4.486609/

預期的輸出驅動器B： https://www.google.nl/maps/dir/51.873215,4.606388/51.8395805,4.3535099/51.8422203,4.33954/51.8670325,4.3453742/51.7914314,4.657120251.7084897,4.6603792/

Answer 1

你可以試試jsprit 。

如果您確定兩個驅動程序在指定位置先驗地彼此相遇的時間窗口，則很容易建模（只需查看wiki中的「簡單示例」即可瞭解如何建模和解決此類問題一個問題）。 時間窗口定義如下：

Service.Builder.newInstance("service").setTimeWindow(TimeWindow.newInstance(10,20)) ... 

如果你不想設定時間窗口提前，你需要學習如何設置自己的狀態和約束。它部分記錄在here以及一些例子和郵件列表中。

從一個位置考慮您的最短路線到另一個（從你的矩陣路由API），只需使用core.util。VehicleRoutingTransportCostMatrix（jsprit.examples.CostMatrixExample演示它）並將矩陣分配給您的問題。

Answer 2

它看起來類似於一個vrp問題。您可以將問題分解爲更小的問題，例如考慮駕駛員作爲車廠遇到的位置。然後你可以用這個約束來使用vrp算法。