[發明專利]一種數據驅動的可達性概率和區域生成方法

有效

• 申請號: 201711195575.3
• 申請日: 2017-11-24
• 公開（公告）號: CN108022006B
• 公開（公告）日: 2020-07-24
• 發明（設計）人: 巫英才;翁荻;朱鶴鳴
• 申請（專利權）人: 浙江大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 徐敏

1.一種數據驅動的可達性概率和區域生成方法，其特征在于，包括以下步驟：

(1)處理出租車軌跡數據中的采樣點，并將得到的采樣點匹配到道路網絡中，形成連續的軌跡數據；

(2)掃描步驟(1)中處理得到的軌跡數據，生成基于圖結構的軌跡索引；

(3)通過步驟(2)建立的軌跡索引，對于用戶發起的關于選定地點的可達性概率和區域的查詢請求，采用帶剪枝的算法搜索軌跡圖中與查詢請求相關的結點和邊，以計算所選地點周圍的可達性概率；

(4)根據步驟(3)計算的可達性概率，結合預設的概率閾值，通過廣度優先搜索算法搜索所述的可達性概率，在地圖上劃定在指定時間內從所選地點出發可達或可到達所述地點的區域；

步驟(2)中，掃描步驟(1)中處理得到的軌跡數據，生成基于圖結構的軌跡索引的具體步驟如下：

2-1、將一天分割成一個以v分鐘為單位的時間片集合M＝{m₁,m₂,m₃...}，其中每個時間片m_i的長度均為v分鐘，i代表時間片的編號，給定道路網絡的結構圖G＝(V,E)，定義軌跡圖G_T＝(M×E,E_T)，V代表交叉口，E代表道路，E_T代表軌跡圖的邊集；

2-2、對于任意一輛出租車軌跡中的任意一條記錄R_j＝(t_j,t_j+1,r_j)∈T_i，j是出租車軌跡記錄的編號，t_j是起始時間，t_j+1是終止時間，r_j是這輛出租車在這段時間內所在的道路編號；

確定t_j和t_j+1所對應的時間片m_j和m_j+1，若m_j≠m_j+1，則增加一條邊m_j,r_j,m_j+1,r_j至邊集E’_T；

2-3、對于任意一輛出租車軌跡中的任意連續兩條記錄確定t_j+1對應的時間片m_j+1，若r_j≠r_j+1，則增加一條邊m_j+1,r_j,m_j+1,r_j+1至邊集E’_T；

2-4、將步驟2-2和2-3得到E’_T進行壓縮后得到邊集E_T，基于圖結構的索引即為最后生成得到的軌跡圖G_T＝(M×E,E_T)。

2.如權利要求1所述的數據驅動的可達性概率和區域生成方法，其特征在于，步驟2-4中，將步驟2-2和2-3得到E’_T進行壓縮后得到邊集E_T，基于圖結構的索引即為最后生成得到的軌跡圖G_T＝(M×E,E_T)的具體過程如下：

2-4-1、令E_T＝{m_i,r_u；m_j,r_v,b,...}，其中b為二進制位組成的日期集合，長度為所有出租車軌跡覆蓋的天數，m_i表示起始時間片，m_j表示終止時間片，r_u表示起始道路，r_v表示終止道路；

2-4-2、對于邊集E’_T中的每條邊e’＝m_i,r_u；m_j,r_v，e’對應的軌跡被記錄的日期d，若存在一條邊e與e’部分匹配，即e與e’前四個分量相同，則更新e使得b＝b∪d；否則，向E_T插入一條新的邊e＝e’,fzy4ia3。