基于路徑拼接模型的路徑行程時間估計方法*

李燁燾， 黃敏， 黃春婷， 張小蘭

1.中山大學(xué)智能工程學(xué)院 / 廣東省智能交通系統(tǒng)重點實驗室，廣東 深圳 518107

2.廣東工貿(mào)職業(yè)技術(shù)學(xué)院，廣東 廣州 510510

交通管理與控制技術(shù)的進步與發(fā)展，交通信息采集設(shè)備的增加，提高了道路交通信息采集與實時處理的能力。例如，以AVI 系統(tǒng)（電警卡口、RFID設(shè)備等）為代表的道路監(jiān)控系統(tǒng)，對路徑行程時間的相關(guān)參數(shù)進行了直接測量（劉曉波等，2019）。行程時間作為智能交通信息系統(tǒng)服務(wù)的重要組成部分，對實現(xiàn)交通流誘導(dǎo)、提高道路服務(wù)質(zhì)量具有重要的意義，在交通政策制定、路徑規(guī)劃等方面具有基礎(chǔ)性的作用。

基于車牌識別數(shù)據(jù)的路徑行程時間估計相關(guān)的研究按照研究尺度的大小可以分為2個方面：基于路段層面與基于路徑層面。基于路段層面的研究思路一般為先對組成路徑的單個路段進行行程時間估計，再由路段行程時間得到路徑行程時間（劉張雷和史忠科，2010；馬聞博，2020；千夢晗，2020）。將路段行程時間的簡單疊加來估計路徑行駛時間方便快捷，但同時也將帶來包括路段行程時間誤差的累積以及經(jīng)過信控交叉口時可能的延誤等。基于路徑層面的研究將路徑作為一個整體，通過把握路徑整體特征避免了路段誤差的累積，實現(xiàn)對路徑行程時間更加精準(zhǔn)的估計。李先通等（2022）對路徑的空間特征展開研究，考慮路段空間依賴、時序依賴以及粗顆粒度中時間飄移問題，利用卷積神經(jīng)網(wǎng)絡(luò)及長短期記憶網(wǎng)絡(luò)對路徑行程時間進行估計；Han et al.（2022）提出多語義模型，考慮了路徑長度、交叉口數(shù)量及不同駕駛員個體對于路徑行程時間的影響；Li et al.（2019）構(gòu)建了深度生成模型，結(jié)合路徑的動靜態(tài)特征給出了路徑行程時間分布。此類方法利用數(shù)據(jù)驅(qū)動的方法，結(jié)合大數(shù)據(jù)技術(shù)、深度學(xué)習(xí)模型對行程時間進行估計，十分依賴于給定路徑上的出行軌跡的數(shù)量是否充足。已有研究（馮軒，2019）給出了稀疏數(shù)據(jù)下路徑行程時間估計的方法，但相關(guān)方面文獻較少，值得進一步探究。

基于路段層面的路徑行程時間估計方法會積累各路段上行程時間估計的誤差，造成路徑行程時間總體偏差較大；在路徑層面整體預(yù)測路徑行程時間，誤差較小，這類方法需要大量長出行軌跡數(shù)據(jù)的作為支撐，但在實際中由于種種原因，待研究長路徑上的出行軌跡數(shù)據(jù)可能不足。針對此現(xiàn)象，本文利用大量卡口檢測數(shù)據(jù)探究路徑可拼接的條件，綜合考慮路段與路徑層面上進行行程時間估計的優(yōu)劣，提出用于構(gòu)建目標(biāo)路徑的路徑拼接方案的選擇方法，利用此方法對城市道路中長路徑行程時間進行估計，以概率分布函數(shù)的形式記錄各路徑的行程時間，再次使用時可直接利用，為后續(xù)研究提供數(shù)據(jù)支撐，具體步驟見圖1。

1 路徑拼接模型

本文提出一種路徑拼接模型，介紹了路徑拼接時要滿足的條件以及確定拼接方案的方法，在交通狀態(tài)相近的前提下將不同的短路徑行程時間拼接得到待研究的長路徑行程時間及其概率。首先根據(jù)研究需求選取待研究的目標(biāo)路徑，再根據(jù)卡口檢測數(shù)據(jù)計算各子路徑所處路網(wǎng)狀態(tài)，提取目標(biāo)路徑所包含的子路徑并計算行程時間，分析子路徑所處的交通狀態(tài)，選取若干滿足路徑拼接條件的子路徑拼接為待研究的目標(biāo)路徑，根據(jù)各子路徑行程時間計算目標(biāo)路徑行程時間。

路徑拼接旨在獲取卡口檢測數(shù)據(jù)中未記錄到足夠車輛出行軌跡的路徑的行程時間，利用卡口檢測數(shù)據(jù)中若干有真實車輛出行軌跡覆蓋的路徑，選取路徑中與目標(biāo)路徑重合的部分，在滿足一定條件的前提下組合成目標(biāo)路徑。圖2（a）為有真實出行軌跡覆蓋的路徑1～3；圖2（b）中所示的目標(biāo)路徑（藍）為無真實出行軌跡覆蓋的路徑。為了得到目標(biāo)路徑的出行數(shù)據(jù)，分別在路徑1～3中選取結(jié)點O 到A、結(jié)點A 到C 以及C 到D 的部分路徑，即可在空間上組合成目標(biāo)路徑。再根據(jù)不同路徑在拼接結(jié)點（結(jié)點A 和C）處交通狀態(tài)是否相近確定該拼接方案是否成立。

圖2 路徑拼接示意圖Fig.2 Path splicing

1.1 路徑拼接條件

1） 物理約束。物理條件保證了拼接路徑在空間上是連續(xù)的，用于拼接的兩段相鄰軌跡Li，Li+1必須有一部分是在空間上重合，即兩條軌跡至少有一個共同的結(jié)點（拼接結(jié)點）。

2） 交通狀態(tài)約束。交通狀態(tài)反映了路網(wǎng)交通流運行情況，可依據(jù)路徑流量與密度判斷交通狀態(tài)通暢與否。路徑的行程時間受交通狀態(tài)影響，假設(shè)同一路徑的路徑路網(wǎng)狀態(tài)相近時，該路徑上的行程時間服從相同的分布。對于相鄰的子路徑Li，Li+1，要求下游子路徑Li+1在其出發(fā)的時刻所對應(yīng)的實時路徑路網(wǎng)狀態(tài)與上游路徑Li到達拼接結(jié)點時路徑Li+1所對應(yīng)的路徑的初始路徑路網(wǎng)狀態(tài)相同。

設(shè)滿足上述物理條件以及交通狀態(tài)條件的拼接路徑L={L1，L2，L3，…，Lm}中各子路徑的行程時間為TLi，則路徑L的總行程時間為各子路徑的行程時間之和。

1.2 拼接方案選擇

選擇行程時間誤差最小的拼接方案可轉(zhuǎn)為求解行程時間的整體方差最小的優(yōu)化問題：

使用遺傳算法（靳文舟等，2020）求解上述問題，將拼接方案編碼為一個0-1 字符串，涉及到n個路段的拼接問題染色體長度為n- 1，每一位用字符0 或1 表示對應(yīng)相鄰路段是否被打斷。如圖3所示，以目標(biāo)路徑為L'={l1，l2，l3，l4}為例，目標(biāo)路徑由4 個路段組成，則其染色體長度為3，對應(yīng)4 個路段形成的3 個路口，染色體“101”表示第1 個和第3 個路口不打斷，第2 個路口打斷，即拼接方案為L'={{l1，l2}，{l3，l4}}.

圖3 路徑拼接方案編碼示意圖Fig.3 Example of chromosome composition

適應(yīng)度代表了染色體存活概率的大小，將適應(yīng)度函數(shù)設(shè)置為Fi= -Var(L，L1，L2，…，Lm)，采用“輪盤賭”選擇方法確定下一代個體，則方案的整體方差越小染色體被選中的概率越大；染色體交叉過程采用二點交叉法，在兩條父代染色體上分別隨機抽取長度相等的兩條染色體片段并交換；變異過程采用點位變異，隨機選擇多個基因依照設(shè)置的概率在子代染色體上進行變異，由于采用了0-1編碼，變異時將基因編碼取反即可。

2 路徑行程時間估計

2.1 交通狀態(tài)劃分

交通流基本圖模型由Greenshields et al.（1935）提出，描述了宏觀交通運行過程中流量、密度和速度之間關(guān)系。宏觀基本圖由Daganzo（2007）提出，相較于傳統(tǒng)交通流基本圖，宏觀基本圖更關(guān)注道路網(wǎng)絡(luò)層面上交通流3 參數(shù)之間的關(guān)系和性質(zhì)。參考傳統(tǒng)基本圖與宏觀基本圖，提出介于二者之間的描述路徑3參數(shù)間關(guān)系的路徑交通流基本圖，用于對路徑所處的交通狀態(tài)進行劃分。參考Edie（1963）提出的交通流參數(shù)的觀測方法，定義路徑L的流量：

根據(jù)Greenshields 模型中交通流速度與密度存在的正比關(guān)系，可以推出流量與密度間存在二次函數(shù)關(guān)系，利用二次函數(shù)擬合路徑流量與路徑密度之間的關(guān)系，圖4中繪制了擬合后的曲線。設(shè)路徑L上流量與密度的關(guān)系為：

圖4 路徑交通流基本圖示意圖Fig.4 Basic diagram of a path

則臨界密度kLm= -( )b2a.根據(jù)路徑L在時刻t的密度劃分其所處的交通狀態(tài)CL(t)，參考Lin（2019）的密度劃分依據(jù)，可將CL(t)劃分為暢通、基本暢通、擁堵、嚴重擁堵4類，具體劃分方法為

2.2 考慮交通狀態(tài)的路徑行程時間分布

路徑行程時間在不同交通狀態(tài)下會呈現(xiàn)不同分布，分別對路徑在不同交通狀態(tài)下的行程時間分布進行擬合，得到路徑L在交通狀態(tài)CL(t)下的路徑行程時間概率密度函數(shù)為f(TL，CL)，則行程時間小于Tx的概率

由于出行者對連續(xù)變化的時間感知度有限，為了便于后續(xù)計算，可以將行程時間分布離散化處理。將行程時間為[)Tx-τ，Tx的概率作為行程時間為Tx的概率，以P(Tx，CL)表示路徑L上路徑行程時間為Tx的概率，即

其中Tx=hτ，h= 1，2，3，…，Tx單位為s.

2.3 路徑行程時間概率

在出發(fā)時間已知的情況下，給定目標(biāo)行程時間，則概率計算步驟：

1）將目標(biāo)路徑分解，選取所有拼接方案中Var 最小的拼接方案，為該方案中各子路徑分配行程時間使得各子路徑的行程時間之和為給定的目標(biāo)行程時間；

2）根據(jù)子路徑的起始時刻所對應(yīng)的交通狀態(tài)及相應(yīng)的概率分布函數(shù)，計算各子路徑對應(yīng)行程時間的概率，將每段子路徑行程時間概率相乘即得到該時間分配方案下路徑行程時間的概率，累加所有時間分配方案的概率，即為目標(biāo)路徑的行程時間為給定值的概率（圖5）。

圖5 路徑行程時間概率計算過程Fig.5 Process of path travel time probability

假設(shè)待研究的拼接方案為

3 案例分析

為了驗證基于路徑拼接的行程時間估計方法可行性及準(zhǔn)確性，選取廣州市工業(yè)大道、南田路、前進路、東曉路及新滘路所圍的區(qū)域內(nèi)，于2021 年8 月29 日卡口過車數(shù)據(jù)進行實例研究。研究區(qū)域內(nèi)共有可觀測路口21 個，可觀測路段32條，見圖6。卡口過車數(shù)據(jù)記錄車輛車牌、所處路段、進入和離開路段的時刻等信息，結(jié)合路網(wǎng)拓撲結(jié)構(gòu)提取車輛出行記錄。剔除車輛出行軌跡中路徑平均速度小于5 km/h 或大于120 km/h 的異常值后，研究區(qū)域內(nèi)單日提取車輛出行20 萬余次，單次出行路徑長度均值約為2 km，單次出行時間均值為664 s。

圖6 研究區(qū)域Fig.6 Study area

選取圖6 中綠色路徑為目標(biāo)路徑，起點A 為南田路與工業(yè)大道交叉口，終點B 為昌崗路與東曉路交叉口，該路徑長約4.5 km，2021 年8 月29日目標(biāo)路徑上共有真實出行軌跡1 232 條，平均路徑行程時間為816.8 s。一天內(nèi)該路徑的行程時間分布如圖7所示。

圖7 真實軌跡行程時間分布Fig.7 Travel time distribution of real trajectory

3.1 宏觀基本圖擬合

以目標(biāo)路徑L的拼接方案為例，依據(jù)式（1）和（2）計算各子路徑Li的流量與密度，并繪制各子路徑的路徑交通流基本圖（圖8）。

圖8 子路徑交通流基本圖Fig.8 Basic diagram of sub-paths

繪制目標(biāo)路徑及其子路徑的路徑交通流基本圖并使用二次函數(shù)進行擬合，選取確定系數(shù)R2以及均方根誤差RMSE 表征擬合優(yōu)度。其中R2∈[0，1]，越接近1 則擬合程度越高；RMSE用于衡量擬合值與真實值之間的偏差；擬合情況見表1。由表1 可知，利用二次函數(shù)擬合的結(jié)果中R2>0.85，RMSE>10，擬合度較好。

表1 路徑交通流基本圖擬合情況（部分）Table 1 Fitting of basic diagram of path

3.2 行程時間分布函數(shù)擬合

按照式（3）將子路徑劃分為“暢通”“基本暢通”“擁堵”和“嚴重擁堵”等4 種交通狀態(tài)，以子路徑L2為例，不同交通狀態(tài)下子路徑行程時間分布情況如圖9所示。

圖9 不同交通狀態(tài)下行程時間分布Fig.9 Travel time distributions under different traffic status

分別利用Gamma、Normal 以及Burr 分布對行程時間分布進行擬合，利用殘差平方和評價分布擬合效果。殘差平方和越小，則擬合效果越好。子路徑在不同交通狀態(tài)下的殘差平方和見表2。由表2 可知，Burr分布在各種交通狀態(tài)下擬合的殘差平方和均為最小，因此采用Burr 分布對所有狀態(tài)下的行程時間分布進行擬合。特別地，若交通狀態(tài)為“嚴重擁堵”時的路徑行程時間數(shù)據(jù)量不足時，則認為該路段不存在此狀態(tài)，在進行路徑拼接時不考慮該狀態(tài)。

表2 子路徑在不同交通狀態(tài)下路徑行程時間分布擬合殘差平方和Table 2 RSS of travel time distribution of sub routes under different traffic status 10-6

3.3 路徑行程時間概率分布

將2021 年8 月29 日8：00 時刻的路徑路網(wǎng)狀態(tài)作為輸入，分別計算目標(biāo)路徑上行程時間為0～2 000 s 的概率，得到目標(biāo)路徑行程時間估計值分布。將其與該路徑上2021 年8 月29 日8：00～9：00時段內(nèi)軌跡的行程時間真實值分布進行對比，結(jié)果見圖10，部分行程時間對應(yīng)的概率密度與累計概率如表3所示。在此時間段內(nèi)，真實出行軌跡的行程時間均值為714 s，本方法所得行程時間估計值均值為693 s，誤差3.04%。

表3 行程時間真實值與估計值對應(yīng)累計概率與概率密度Table 3 Cumulative probability and probability density of different travel times

圖10 目標(biāo)路徑行程時間真實值與估計值對比Fig.10 Comparison of target path travel time distributions

使用JS 散度（Chen & Liu，2021）進一步判斷上述2 種分布的相似性。JS 散度是基于KL 散度提出的一種概率統(tǒng)計方法（Kullback & Leibler，1951），在信息論中廣泛應(yīng)用于定量衡量兩個概率分布間的差異性。離散型分布U，V的KL散度為

JS散度取值在0～1之間，相同分布的JS散度為0，JS 散度越大，兩個分布間的相似性越小。按照式（4）計算可得目標(biāo)路段行程時間分布的估計值與實際值的JS散度為0.05，可以認為本文方法得到的行程時間分布與真實行程時間分布的趨勢一致，同一行程時間所對應(yīng)的概率相近。因此，從行程時間均值與分布兩方面來看，本方法對行程時間估計的結(jié)果可靠，可為后續(xù)相關(guān)研究提供數(shù)據(jù)基礎(chǔ)。

4 總 結(jié)

針對行程時間相關(guān)研究中可能出現(xiàn)的路徑行程時間數(shù)據(jù)量不足的問題，本文提出了基于路徑拼接模型的路徑行程時間估計方法，通過路徑拼接模型確定路徑拼接方案。使用Burr 分布擬合不同路網(wǎng)狀態(tài)下的路徑行程時間分布，結(jié)合路徑拼接方案給出目標(biāo)路徑行程時間及其概率分布。該方法計算得到的行程時間與實際行程時間的均值誤差較小，所得行程時間分布與實際分布相似，對路徑行程時間的估計結(jié)果較為準(zhǔn)確，可為后續(xù)行程時間可靠性、個性化路徑推薦等基于路徑行程時間的研究提供數(shù)據(jù)支撐。