[發明專利]車輛行駛路徑規劃方法、裝置、電子設備和可讀存儲介質

在審

• 申請號: 201910378703.0
• 申請日: 2019-05-08
• 公開（公告）號: CN111912420A
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 陳浪;孔媛;步允千
• 申請（專利權）人: 北京京東振世信息技術有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06Q10/04;G06Q50/30
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 鄭紅娟;宋志強

1.一種車輛行駛路徑規劃方法，其特征在于，包括：

根據起點和站點集使用啟發式規劃算法生成車輛行駛路徑；所述站點集包括車輛行駛過程中需要經過的全部站點，所述全部站點包含于生成的車輛行駛路徑中，其中車輛行駛路徑中的每條子路徑由起點出發且經過至少一個所述站點；

在所述車輛行駛路徑中的子路徑數量小于預先給定的車輛數量時，針對每條子路徑，基于該子路徑上的每個站點計算路徑拆分前和拆分后的拆分成本，確定拆分成本最低的站點；

在所述拆分成本最低的站點處，對所屬的子路徑進行拆分，直至所述車輛行駛路徑中的子路徑數量等于預先給定的車輛數量，將得到的一組車輛行駛路徑作為路徑規劃結果。

2.根據權利要求1所述的方法，其特征在于，所述基于該子路徑上的每個站點計算路徑拆分前和拆分后的拆分成本的步驟，為：

刪除該子路徑中該站點之后的路徑，并計算該站點之后的路徑被刪除時減少的第一成本；

根據該站點之后的路徑被刪除時釋放的每個空閑站點，使用啟發式規劃算法生成新的子路徑，并計算生成所述新的子路徑增加的第二成本；

根據所述第一成本和所述第二成本，得到路徑拆分前和拆分后的所述拆分成本。

3.根據權利要求1所述的方法，其特征在于，在所述根據起點和站點集使用啟發式規劃算法生成車輛行駛路徑之后，在判斷所述車輛行駛路徑中的子路徑數量是否等于預先給定的車輛數量之前，所述方法，還包括：

隨機釋放車輛行駛路徑中的至少一個站點，為釋放得到的所述至少一個站點，使用啟發式規劃算法生成新的子路徑；

在所述車輛行駛路徑中的子路徑數量等于預先給定的車輛數量之后，所述方法還包括：

返回執行隨機釋放車輛行駛路徑中的至少一個站點的步驟，直至執行次數等于預設的次數閾值；其中，每次執行得到一組車輛行駛路徑，得到的每組車輛行駛路徑中的子路徑數量等于預先給定的車輛數量；

針對每組車輛行駛路徑，計算該組車輛行駛路徑的成本；根據計算出的每組車輛行駛路徑的成本從中確定一組作為路徑規劃結果。

4.根據權利要求2所述的方法，其特征在于，所述生成新的子路徑的步驟，為：

從每個所述空閑站點中，為未被分配路徑的車輛分別分配一個必經站點參數，將所述必經站點參數輸入啟發式規劃算法中執行，生成新的子路徑；所述新的子路徑中分別包含所述必經站點。

5.根據權利要求4所述的方法，其特征在于，在所述根據起點和站點集使用啟發式規劃算法生成車輛行駛路徑之后，在判斷所述車輛行駛路徑中的子路徑數量是否等于預先給定的車輛數量之前，所述方法，還包括：

隨機釋放車輛行駛路徑中的至少一個站點，同時保證每個車輛至少保留一個站點；為釋放得到的所述至少一個站點，使用啟發式規劃算法生成新的子路徑；

在所述車輛行駛路徑中的子路徑數量等于預先給定的車輛數量之后，所述方法還包括：

返回執行隨機釋放車輛行駛路徑中的至少一個站點的步驟，直至執行次數等于預設的次數閾值；其中，每次執行得到一組車輛行駛路徑，得到的每組車輛行駛路徑中的子路徑數量等于預先給定的車輛數量；

針對每組車輛行駛路徑，計算該組車輛行駛路徑的成本；根據計算出的每組車輛行駛路徑的成本從中確定一組作為路徑規劃結果。

6.根據權利要求2所述的方法，其特征在于，所述生成新的子路徑的步驟，為：

根據該站點之后的路徑被刪除時釋放的未被運載的空閑需求量，為未被分配路徑的車輛分別設定車載容量參數，使未被分配路徑的車輛的車載容量參數的總和與所述空閑需求量之間的容量差值，小于每個未被分配路徑的車輛的車載容量參數；

將所述車載容量參數輸入啟發式規劃算法中執行，生成新的子路徑。

7.根據權利要求2所述的方法，其特征在于，所述生成新的子路徑的步驟，為：

為每個未被分配路徑的車輛分別設置費用成本參數；

將每個所述費用成本參數輸入啟發式規劃算法中執行，生成新的子路徑。