[發明專利]一種用于確定可達區域的方法和裝置

有效

• 申請號: 201810565693.7
• 申請日: 2018-06-04
• 公開（公告）號: CN109029476B
• 公開（公告）日: 2020-06-23
• 發明（設計）人: 李瑞遠;鮑捷;阮思捷;鄭宇
• 申請（專利權）人: 京東數字科技控股有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 戚傳江;陸錦華

1.一種用于確定可達區域的方法，其特征在于，包括：

采集路段數據和軌跡數據，其中，所述路段數據包括所述路段的起點位置和終點位置，所述軌跡數據包括所述軌跡所途經的路段和用于所途經的路段的時間；

接收查詢點、最大軌跡拼接次數以及預算時間；

響應于所述查詢點、所述最大軌跡拼接次數以及所述預算時間，基于所述路段數據和所述軌跡數據，確定從所述查詢點出發，在所述預算時間以內的可達區域，其中，在所述可達區域內執行的軌跡拼接次數不大于所述最大軌跡拼接次數。

2.根據權利要求1所述的方法，其特征在于，使用四元數組(tr_i,e_j,t_ij,k)標記從所述查詢點起通過軌跡tr_i、途經路段e_j，花費時間t_ij的可達區域，其中，所述軌跡tr_i途經路段e_j，k為從所述查詢點起通過所述軌跡tr _i至所述路段e_j的終點所花費的軌跡拼接次數，還包括：

初始四元數組創建步驟：基于所述查詢點創建初始四元數組(tr_null,e_null,0,0)，其中，所述tr_null表示初始無軌跡途經所述查詢點，所述e_null表示初始無路段途經所述查詢點，所述查詢點為所述e_null的終點；

軌跡拼接步驟：根據所述軌跡數據確定途經前一次創建的四元數組中的路段的終點、與前一次創建的四元數組中的軌跡不同的軌跡tr_i，確定所述軌跡tr_i途經所述終點之后繼續途經的路段e_j，根據所述軌跡tr_i、所述路段e_j、從所述查詢點起通過先前創建的四元數組中的軌跡和所述軌跡tr_i至所述路段e_j的終點所花費的時間和軌跡拼接次數創建四元數組(tr_i,e_j,t_ij,k)，其中，從所述查詢點起至所述路段e_j的終點所花費的時間t_ij為途經先前創建的四元數組中的路段和所述路段e_j的時間之和，所述軌跡拼接次數k為執行所述軌跡拼接步驟的次數，丟棄所述t_ij大于所述預算時間的四元數組；

可達區域確定步驟：重復執行所述軌跡拼接步驟，直至所述軌跡拼接次數大于所述最大軌跡拼接次數，將所述四元數組中的路段的集合識別為所述可達區域。

3.根據權利要求2所述的方法，其特征在于，還包括：在所述軌跡拼接步驟中，如果在先前創建的四元數組中存在一四元數組(tr_i’,e_j’,t_i’j’,k’)，使得與在所述軌跡拼接步驟中創建的四元數組(tr_i,e_j,t_ij,k)相比，tr _i’＝tr_i，e_j’＝e_j，t_i’j’≤t_ij，k’≤k，則丟棄所述四元數組(tr_i,e_j,t_ij,k)。

4.根據權利要求2或3所述的方法，其特征在于，在所述軌跡拼接步驟中，從所述查詢點起至所述路段e_j的終點所花費的時間t_ij為途經先前創建的四元數組中的路段和所述路段e_j的時間之和，再加上軌跡拼接所花費的時間。