[發明專利]一種基于軌跡重構技術的流量修復方法

有效

• 申請號: 202111385121.9
• 申請日: 2021-11-22
• 公開（公告）號: CN114333292B
• 公開（公告）日: 2022-11-18
• 發明（設計）人: 丁婉婷;王雪雪;還斌;韓志躍;陳凱佳;黃佳寅;胡凱倫;談佳睿;徐克寧;劉正杰;劉曉謙
• 申請（專利權）人: 上海電科智能系統股份有限公司
• 主分類號: G08G1/01
• 分類號: G08G1/01
• 代理公司: 上海璀匯知識產權代理事務所(普通合伙) 31367
• 代理人: 王文穎

1.一種基于軌跡重構技術的流量修復方法，其特征在于，包括以下步驟：

步驟S-1：對過車記錄進行預處理，以對檢測生成的明顯的錯誤車輛信息進行處理；

步驟S-2：路段有效行程時間集合，具體包括以下步驟：

步驟S-2-1：路段行程時間集生成

將經過步驟S-1處理的過車記錄排序后，依次讀取過車記錄，同一車牌前后兩次不是同一卡口，則該車牌對應的車輛k前后檢測時間記錄之差為：

其中，TIME_SPAN表示車輛k上下游行程時間；t_k表示車輛k的路段行程時間；表示車輛k經過下游進口道的時間；表示車輛k經過上游進口道的時間；

則兩卡口對之間的旅行時間為：

TRAIL_TIME＝TIME_SPAN，when 0＜TIME_SPAN＜tt_u

tt_u＝2.77*d

其中，TRAIL_TIME表示路段行程時間集合；tt_u表示設置的最大旅行時間閾值；d表示路段距離；

步驟S-2-2：路段行程時間異常值過濾，得到最終路段有效行程時間集合EFFECTIVE_TRAIL_TIME：

步驟S-3：出行鏈分離，具體包括以下步驟：

步驟S-3-1：行程時間上下限計算

記車輛一天出行鏈TRAVEL_DAY中相鄰節點node_i、node_j的經過時間分別為passtime_i、passtime_j，j＞i，則：

Δt_ij＝passtime_j-passtime_i

其中，Δt_ij表示相鄰節點node_i、node_j的檢測時間差；

若路網有向圖中存在有向弧dot_i，dot_j，則D(node_i，node_j)＝1，即node_i→node_j直接可達，則node_i→node_j的距離d_ij為路網有向圖中有向弧dot_i，dot_j的路段長度；

否則，D(node_i，node_j)＝0，即node_i→node_j不直接可達，則距離d_ij用node_i→node_j最短路徑的路段長度和表示，其中，node_i→node_j最短路徑通過最短路算法獲得；

行程時間上限

其中，t_u表示路段統計時間窗內有效行程時間的最大值；

其中，t_l表示路段統計時間窗內有效行程時間的最小值，單位：s。

步驟S-3-2：行程速度上下限計算

相鄰節點node_i→node_j的行程速度上、下限值分別為其中，ξ為調整系數；表示相鄰節點node_i→node_j統計時間窗內有效行程時間的最小值；表示相鄰節點node_i→node_j統計時間窗內有效行程時間的最大值；

步驟S-3-3：出行鏈分離，具體包括以下步驟：

步驟S-3-3-1：當node_i＝node_j時，若Δt_ij＞Δt_θ，則出行鏈分離，否則不進行出行鏈分離，其中，Δt_θ為檢測時間差，根據實際數據分析暫取540s；

當node_i！＝node_j時，進入步驟S-3-3-2；

步驟S-3-3-2：若則標記為異常軌跡，否則進入步驟S-3-3-3，其中，v_ij表示相鄰節點node_i→node_j的行程速度；

步驟S-3-3-3：若D(node_i，node_j)＝1且則不進行出行鏈分離；若D(node_i，node_j)＝1且則出行鏈分離；否則，進入步驟S-3-3-4；

步驟S-3-3-4：若D(node_i，node_j)＝0且則不進行出行鏈分離；若D(node_i，node_j)＝0且則出行鏈分離。

利用清洗后的過車記錄數據，提取每個車牌license_i經出行鏈分離后的上一條出行，按時間先后順序依次經過的路口號、進口道號和經過時間，依次得到每輛車一天的多條出行鏈TRAVEL_DAY；

TRAVEL_DAY＝(node₁→node₂→…node_i…→node_n)

其中，node_i表示出行鏈TRAVEL_DAY中的第i個節點；

步驟S-4：路徑修復

缺失路徑表示為被檢測到的相鄰兩個節點node_i→node_j之間的部分，若node_j-1＝node_i且D(node_i，node_j)＝1，則漏檢節點數h＝0，無漏檢，此時無需修復；在其他情況下，進行路徑修復，具體包括以下步驟：

步驟S-4-1：若node_i+1＝node_j-1且D(node_i，node_j)＝0，則漏檢節點數h＝1，此時采用路網拓撲關系修復；。

步驟S-4-2：若node_i+1！＝node_j-1且D(node_i，node_j)＝0，則漏檢節點數h≥2，此時采用由起點i到終點j所經過的最短路徑集合S所經過的節點數進行判斷，若最短路修復后節點數除首尾節點外h＝2，采用Dijkstra最短路徑進行估計修復，利用Dijkstra算法生成起點i到終點j的距離上的最短路徑；

步驟S-4-3：粒子濾波算法修復

若node_i+1！＝node_j-1且D(node_i，node_j)＝0，則漏檢節點數h≥2，此時采用由起點i到終點j所經過的最短路徑集合S所經過的節點數進行判斷，若最短路修復后節點數除首尾節點外h＞2，采用粒子濾波算法進行估計修復，具體包括以下步驟：

步驟S-4-3-1：粒子濾波之可行解生成

基于最短路徑算法，求相對最短路徑的偏移路徑，由與起點相鄰路口開始偏移，直至找到滿足備選路徑數量需求的偏移路徑集，該偏移路徑集即為可行解，具體包括以下步驟：

步驟S-4-3-1-1：輸入起點o、終點d、要求的最短路徑個數K；初始化集合和集合A和集合B分別用于存放起點o到終點d的K條最短路徑和候選路徑；

步驟S-4-3-1-2：根據步驟S-4-2，求出起點o到終點d的最短路徑，并放入集合A；

步驟S-4-3-1-3：將集合A中最后一條路徑p_k上除終點d外的每個頂點分別看作偏離點，若不存在偏離點，則進入步驟S-4-3-1-4，否則，對每個偏離點V_i做如下計算：

根據步驟S-4-2，求偏離點V_i到終點d的最短路徑V_i，d；為防止起點到終點的整體路徑有環，從偏離點V_i到終點d的最短路徑V_i，d中不能包含起點o到偏離點V_i的最短路徑o，V_i上的任何節點；為避免與已經在集合A中的路徑重復，從偏離點V_i發出的邊不能與集合A中各路徑從偏離點V_i發出的邊相同；

若存在最短路徑V_i，d，則將路徑o，V_i+V_i，d放入集合B；

步驟S-4-3-1-4：若將集合B中路段長度ROUTE_LENGTH和最小的路徑放入集合A；若路段長度和最小的路徑有多條，則選擇其中頂點數最少的路徑作為放入集合A的最小的路徑，并將該最小的路徑對應的路段長度ROUTE_LENGTH放入集合B；

步驟S-4-3-1-5：判斷集合B是否等于否不是，則重復步驟S-4-3-1-3及步驟S-4-3-1-4，直至

步驟S-4-3-3：粒子濾波路徑選擇影響因素分析，包括以下5個方面：

1)候選路徑軌跡可測性權重

候選路徑的軌跡可測性是指考慮候選路徑上節點檢測器布設的情況，假設車輛經過，但是車輛被漏檢是小概率事件，根據檢測器的布設率和漏檢率推斷車輛經過該條候選路徑的概率：

其中，表示基于候選路徑i在不同數量檢測器覆蓋和檢測率的情況下被選擇的概率，用以更新上次觀測的權重；ε為檢測器的漏檢率；α為候選路徑i上檢測器覆蓋的數量；

2)候選路徑的軌跡偏好程度

給定一OD對OD_ij，即node_i→node_j，通過歷史軌跡數據計算不同的車輛行駛路徑選擇該路徑的偏好程度，路徑的偏好程度定義為不同軌跡流量在該OD對的所有軌跡流量和中的占比：

其中，表示第i條候選路徑在路徑選擇時偏好的概率，xⁱ表示OD對OD_ij之間初始路徑集的第i條候選路徑；表示時刻t_k的候選路徑的集合，即為步驟S-4-3-2計算得到的偏移路徑集，x_k中的元素稱為候選軌跡粒子，I表示候選軌跡粒子的總數量；volume_i表示統計時間間隔下第i條候選路的流量；

3)候選路徑路徑旅行時間一致性

路徑旅行時間一致性的定義為不同候選路徑的旅行時間與車輛相鄰兩次卡口檢測時間差一致的程度：

其中，表示第i條候選路徑與相鄰兩次檢測時間一致性的程度；表示在兩個節點node_i、node_j之間第i條候選路徑的平均的旅行時間；traveltime′(node_i，node_j)、traveltime～表示在兩個節點node_i、node_j的真實旅行時間；

4)候選路徑路徑距離權重

對OD對OD_ij之間的第i條候選路徑xⁱ，通過路段基礎配置表可獲得其路徑長度之和length_k，則路徑距離的權重定義為：

其中，為第i條候選路徑的路徑距離在做路徑選擇時的概率大小；max(length_i)為第i條候選路徑xⁱ中最大的路徑距離，min(length_i)為第i條候選路徑xⁱ中最小的路徑距離。

5)候選路徑高等級道路比例權重

高等級道路因素權重的定義為候選路徑tra_k中高等級道路的長度與所有候選路徑高等級道路長度之和的比值：

其中，為考慮候選路徑高等級道路給出的各路徑的選擇概率；arterial_i為第i條候選路徑xⁱ中高等及道路的長度；

步驟S-4-3-4：粒子濾波權重更新與路徑選擇

對于一個特定的車輛l，在進行其路徑修復時：表示時刻t_k的候選路徑的集合，即為步驟S-4-3-2計算得到的偏移路徑集，x_k中的元素稱為候選軌跡粒子，I表示候選軌跡粒子的總數量；表示時刻t_k的觀測狀態向量，J表示觀測狀態向量的總數量，則粒子濾波的過程描述為：

x_k＝f_k(x_k-1，v_k-1)

z_k＝h_k(x_k，n_k)

其中，f_k為狀態轉移函數；h_k為系統測量函數；v_k-1為系統狀態轉移時的過程噪聲；n_k為系統測量噪聲；v_k-1和n_k假設為獨立分布的；

粒子濾波進行路徑選擇的過程為在給定候選路徑的觀測后估計其后驗概率分布；向量Z^k＝{z₁，z₂，...，z_k}為在時間t_k時的觀測，基于貝葉斯濾波的框架，當給定觀測Z^k后，候選軌跡粒子x_k的后驗概率分布函數p(x_k|Z^k)可通過下述預測和更新兩步驟進行計算：

步驟S-4-3-4-1：預測

p(x_k|Z^k-1)＝∫p(x_k|x_k-1)p(x_k-1|Z^k-1)dx_k-1

其中，在時刻t_k-1的p(x_k-1|Z^k-1)通過狀態轉移函數計算得到，p(x_k|Z^k-1)基于p(x_k-1|Z^k-1)進行遞歸計算，其中，p(x_k|x_k-1)通過x_k的轉移函數進行計算；

步驟S-4-3-4-2：更新：

其中，p(z_k|x_k)為給定觀測z_k后當候選的軌跡是候選軌跡粒子x_k時的似然函數，p(x_k|Z^k-1)是時刻t_k-1給定觀測時候選軌跡粒子x_k的概率分布函數；

當提取到缺失路徑的首尾段的節點時，通過Dijkstra最短路算法和K則最短路算法生成K個初始路徑作為初始粒子在每一個時刻t_k每一個粒子會有一個粒子權重每一時刻，當觀測z_k出現后，進行重要性采樣更新每個粒子的權重，權重更新的公式為：

其中，為候選軌跡粒子i在時刻t_k的權重；為候選軌跡粒子i在時刻t_k-1的先驗權重；為時刻t_k的候選軌跡粒子，對于一個特定的候選路徑，在任意一個時刻保持不變；為不同觀測下的似然，通過相鄰卡口對的觀測輸入，通過相鄰卡口對的觀測輸入，基于步驟S-4-3-3得到的按照重要性排序的5個因素依次進行的概率更新，從而獲得粒子權重；

獲得粒子權重后，進行粒子權重歸一化：

表示歸一化后的粒子權重

在進行下一步預測前，進行重采樣，避免粒子退化；

通過以上步驟進行計算后，得到粒子權重最大的軌跡作為修復的軌跡：

步驟S-4-4：漏檢時間插值修復

路徑漏檢位置修復完成后，進一步修復其每個中間交叉口經過時間，以支持路段流量等指標的計算；

中間交叉口經過時間通過每個路段的長度和路徑起終開始時間進行線性插值進行計算：

其中，t_q為中間第q個點的修復時間；t₀為缺失路徑首點的檢測時間；t_n+1為缺失路徑尾點的檢測時間；l_p，p+1為中間第p點到第p+1點之間路段的長度；q表示第q個需進行時間修復的節點；n表示需進行時間修復的節點數；

步驟S-4-5：路徑綜合置信度計算

節點總數為num_total，將檢測成功的節點a在輸出路徑中的數量記為num_a，每個節點的置信度設置為100％，將通過拓撲修復的節點b在輸出路徑中的數量記為num_b，每個節點的置信度設置為95％，將最短路修復的節點c在輸出路徑中的數量記為num_c，每個節點的置信度設置為90％，將通過粒子濾波算法修復的節點d在輸出路徑中的數量記為num_d，每個節點的置信度為通過粒子濾波最終輸出選擇路徑的歸一化權重則輸出的第i條路徑xⁱ的綜合置信度為：

其中，num_total＝num_a+num_b+num_c+num_d為該條路徑的總節點數量。

步驟S-5：流量生成，具體包括以下步驟：

步驟S-5-1：軌跡流量生成

基于以上步驟可修復完成路網計算范圍內任一起點到終點的路徑及節點序列M(node₁→node₂→…node_i…→node_n)。將每個節點所有軌跡疊加，即可生成斷面轉向流量，當前斷面所有的斷面轉向流量之和即為基于軌跡的斷面流量V_trijk，則有：

其中，V_tr表示基于軌跡修復的軌跡疊加流量，下標i為節點，下標j為斷面，下標k為轉向；M_h表示第h條軌跡，總數為f；

步驟S-5-2：調整流量生成

a_ijk＝V_trijk/V_ijk

其中，a_ijk表示軌跡修復疊加流量與實際觀測值的偏斜系數；V_ijk表示實際觀測流量；

其中，confidence_pjk表示目標節點的進口道轉向軌跡流量平均置信度；confidence_pjkx表示目標節點進口道轉向的各軌跡置信度，下標x表示路徑，由步驟S-4-5獲得；

利用具有檢測數據的節點，進行軌跡流量微觀修復，采用以下公式：

β_p1、β_pn表示目標節點相對于頭節點、尾節點的置信度差異系數，下標p表示目標節點，下標1表示頭節點，下標n表示尾節點；

若β_p1≥β_pn，即目標節點與頭節點的置信度差異性較小，更傾向于選擇頭節點檢測數據進行修復，則有：

V_tzpjk＝V_trijp/a_1jk

其中，V_tz表示調整流量；a_1jk表示相鄰具有檢測設備的頭節點的偏斜系數；V_trijp表示目標節點的軌跡疊加流量；

若β_p1＜β_pn，即目標節點與尾節點的置信度差異性較小，更傾向于選擇尾節點檢測數據進行修復，則有：

V_tzpjk＝V_trijp/a_njk

其中，a_njk表示相鄰具有檢測設備的尾節點的偏斜系數。