[發明專利]基于動態規劃的出行組客方法、裝置、設備及存儲介質

有效

• 申請號: 202010433434.6
• 申請日: 2020-05-21
• 公開（公告）號: CN111738550B
• 公開（公告）日: 2023-07-25
• 發明（設計）人: 肖楓
• 申請（專利權）人: 深圳賽安特技術服務有限公司
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q10/047
• 代理公司: 北京市京大律師事務所 11321
• 代理人: 姚維

1.一種基于動態規劃的出行組客方法，其特征在于，包括：

獲取多個出行需求訂單，所述出行需求訂單用于為用戶提供出行車輛，所述出行需求訂單包括出發地、出發站點、目的地、目的站點和乘車時刻；

對所述多個出行需求訂單按照預置規則進行處理，得到目標出行需求訂單集合和每個目標出行需求訂單對應的目標訂單號，所述目標出行需求訂單集合的乘車時刻在第一預置時段范圍內；

所述對所述多個出行需求訂單按照預置規則進行處理，得到目標出行需求訂單集合和每個目標出行需求訂單對應的目標訂單號，所述目標出行需求訂單集合的乘車時刻在第一預置時段范圍內，包括：

對多個出行需求訂單進行解析，得到每個用戶的乘車時刻，每個用戶對應一個出行需求訂單；

按照預置時間間隔將所述多個出行需求訂單進行劃分，生成多個初始出行需求訂單集合，每個初始出行需求訂單集合的乘車時間范圍不同；

根據出發站點和目的站點對所述多個初始出行需求訂單集合進行篩選，生成多個過渡出行需求訂單集合，每個過渡出行需求訂單集合中出發站點在同一個城市，目的站點也在同一個城市；

在所述多個過渡出行需求訂單集合中選擇第一預置時段對應的目標出行需求訂單集合，并確定目所述標出行需求訂單集合中每個出行需求訂單對應的目標訂單號；

獲取所述第一預置時段范圍內的車輛信息，所述車輛信息包括每個待分配車輛的座位總數、每個待分配車輛的剩余座位數以及待分配車輛的車輛總數；

遍歷所述目標出行需求訂單集合中每個目標訂單號和所述車輛信息，確定所有站點的上車人數和下車人數，得到訂單人數組合；

調用動態規劃算法遍歷所述訂單人數組合，確定所有的訂單分配組合，所述訂單分配組合包括多個預分配的目標訂單號；

根據所述所有的訂單分配組合和迪杰斯特拉算法確定多個待匹配站點組合，所述待匹配站點組合中可組合的站點之間距離之和最短；

所述根據所述所有的訂單分配組合和迪杰斯特拉算法確定多個待匹配站點組合，所述待匹配站點組合中可組合的站點之間距離之和最短，包括：

初始化一個數組route、頂點集合T和頂點集合U，所述數組用于保存源點s到各個頂點的最短距離，所述頂點集合T用于保存已經找到的最短路徑的頂點；

將源點s的路徑權重設置為0；

若對于所述源點s存在能直接到達的邊(s,e)，則把數組route[e]設為d(s,e),同時把所有其他不能到達源點s的頂點的路徑長度設為無窮大route[∞]；

在數組route中選擇最小路徑值，所述最小路徑值為源點s到所述最小路徑值對應的最近頂點的最短路徑，并且把所述最近頂點加入到預置表格；

判斷新加入的最近頂點是否可以到達其他頂點，并且判斷通過該新加入的最近頂點到達其他點的路徑長度是否比源點s直接到達其他點的路徑長度短；

如果同時滿足，則更新滿足條件的頂點在route中的權重；

繼續在頂點集合U中找到最小值，直至預置表格中包含了路線中所有的頂點，生成待匹配站點組合，所述待匹配站點組合中可組合的站點之間距離之和最短；

把所述多個待匹配站點組合進行排序，得到站點間路程不超過閾值的目標站點組合。

2.根據權利要求1所述的基于動態規劃的出行組客方法，其特征在于，所述調用動態規劃算法遍歷所述訂單人數組合，確定所有的訂單分配組合，所述訂單分配組合包括多個預分配的目標訂單號，包括：

遍歷所述訂單人數組合，將滿足上車點數量要求和車輛滿載率要求設為一個子問題，得到多個子問題；

調用動態規劃算法按順序求解多個子問題，得到多個訂單分配組合，所述訂單分配組合包括多個預分配的目標訂單號。

3.根據權利要求2所述的基于動態規劃的出行組客方法，其特征在于，所述遍歷所述訂單人數組合，將滿足上車點數量要求和車輛滿載率要求設為一個子問題，得到多個子問題，包括：

遍歷所述訂單人數組合，篩選出訂單人數組合中滿足上車點數量要求的多個候選訂單組合，所述上車點數量要求為出發地和目的地都不超過三個；

基于所述多個候選訂單組合設置車輛滿載率要求為子問題，得到多個子問題，其中，所述車輛滿載率要求為每個車輛的車輛滿載率大于或等于對應的最小滿載率。