[發明專利]一種基于軌跡大數據的眾包物流配送路徑規劃方法及系統

有效

• 申請號: 201811390979.2
• 申請日: 2018-11-21
• 公開（公告）號: CN109376952B
• 公開（公告）日: 2022-10-18
• 發明（設計）人: 涂偉;趙天鴻;黃正東;李清泉;朱婷婷;楊超
• 申請（專利權）人: 深圳大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 深圳市君勝知識產權代理事務所(普通合伙) 44268
• 代理人: 王永文;劉文求

1.一種基于軌跡大數據的眾包物流配送路徑規劃方法，其特征在于，所述方法包括：

收集歷史浮動車軌跡數據，根據所述歷史浮動車軌跡數據，找出浮動車的停留信息，并基于浮動車的停留頻數確定出配送中轉站的備選地址，建設配送中轉站；

采用啟發式算法對包裹進行時效路由計算，并基于路徑最短原則確定出包裹從初始點到目標點之間經過配送中轉站的最佳路徑；

獲取城市在線浮動車軌跡數據，計算浮動車軌跡和最佳路徑中某個子路徑中兩個中轉站之間連成的軌跡；

計算所有待匹配的浮動車的軌跡與所有包裹所確定的最佳路徑之間的相似度；

找出相似度滿足預設要求的浮動車，并指派所述浮動車對所述城市包裹進行配送；

所述采用啟發式算法對城市包裹進行時效路由計算，并基于路徑最短原則確定出包裹從初始點到目標點之間經過配送中轉站的最佳路徑的步驟，包括：

根據建設的配送中轉站，利用圖與網絡理論建立城市配送網絡；

通過靜態大規模浮動車軌跡大數據挖掘配送中轉站之間的網絡交通強度；

用所述網絡交通強度對路網長度進行加權，得到配送網絡弧之間的代價值；

用大規模鄰域搜索算法對包裹進行時效路由計算，并基于路徑最短原則確定出包裹從初始點到目標點之間經過配送中轉站的最佳路徑；

所述用大規模鄰域搜索算法對包裹進行時效路由計算的步驟，包括：

輸入配送網絡與參數；

初始解生成算法，經過破壞算子、修復算子、自使用算法以及禁忌搜索算法，最后進行迭代運算；

當迭代結束后，輸出最佳路徑；

當迭代沒有結束時，返回破壞算子算法步驟，重新計算，直至迭代結束；

所述計算所有待匹配的浮動車的軌跡與所有包裹所確定的最佳路徑之間的相似度，找出相似度滿足預設要求的浮動車，并指派所述浮動車對所述城市包裹進行配送，包括：

計算浮動車的軌跡(x_to,y_to,x_td,y_td) 和最佳路徑中某個配送子路徑中兩個配送中轉站之間連成的軌跡(x_i-1,y_i-1,x_i,y_i) 的相似度，計算所述相似度的表達式為

計算所有待匹配的浮動車與所有包裹所確定的最佳路徑之間的相似度；

取每個包裹相似度較高的前M個浮動車相連接，將相似度作為權重建立浮動車與包裹子路徑之間的二分圖；

利用匈牙利匹配算法匹配出相似度滿足預設要求的浮動車，并指派所述浮動車對所述城市包裹進行配送。

2.根據權利要求1所述的基于軌跡大數據的眾包物流配送路徑規劃方法，其特征在于，所述浮動車是指安裝了車載GPS定位裝置并行駛在城市交通軌道上的車輛。

3.根據權利要求1所述的基于軌跡大數據的眾包物流配送路徑規劃方法，其特征在于，所述收集歷史浮動車軌跡數據，根據所述歷史浮動車軌跡數據，找出浮動車的停留信息，并基于浮動車的停留頻數確定出配送中轉站的備選地址，建設配送中轉站的步驟，具體包括：

收集歷史浮動車軌跡數據，并對所述歷史浮動車軌跡數據進行數據清洗以及數據補充；

從所述歷史浮動車軌跡數據中獲取每一輛浮動車的一天中的停留頻數、停留點位置以及停留時長；

獲取停留頻數高于預定數目的停留點位置，并設置為配送中轉站的備選地址。

4.根據權利要求3所述的基于軌跡大數據的眾包物流配送路徑規劃方法，其特征在于，所述數據清洗包括：剔除GPS記錄小于預定值的數據、重復數據以及屬性缺失的數據。

5.根據權利要求3所述的基于軌跡大數據的眾包物流配送路徑規劃方法，其特征在于，所述數據補充包括：對GPS數據連續間斷時間超過預設的時間閾值的間斷數據進行修復補充，補充GPS點的位置是間斷前的位置，補充點的時間t_sup＝t_start+dis/V，t_start為間斷前的時間，dis為間斷兩點之間的距離，v為補充的速度。