出租車數據的城市道路網路段通行時間估計方法

黃順倫，杜春，宋寶泉，李軍，陳浩

城市道路通行時間的準確估計和預測對于改善城市交通狀況是至關重要的，其目標在于計算準確的道路網通行時間信息, 以便選擇道路網中更好的路線使通行時間最小。若欲準確評估路段通行時間，最核心的就是從道路傳感器中獲取良好的車輛實時信息。然而，在大多數情況下，只能獲得離散的車輛速度和位置信息, 具體的時空軌跡信息難以實時獲取。因此，必須開發適當的方法來估計道路網路段通行時間。

目前，針對城市道路通行時間估計和預測的研究主要包括兩類方法，即基于傳感器數據的預測以及基于城市全球定位系統(global positioning system，GPS)數據的預測方法。

第一類方法的研究主要依賴于各種類型傳感器采集的數據進行預測，主要包括:環形線圈檢測器[1-3]、自動車輛識別[4-5]、攝像機、遠程通信微波傳感器[6]和自動化牌照識別[7]等。通常，這些數據需要相應精度級別的傳感器來獲取。然而由于傳感器的安裝和維護費用高昂，導致基于傳感器獲取數據的道路通行時間預測方法的應用難以普及。

第二類方法是基于GPS數據估計城市地區交通動態需求和道路網動態變化，因其具有極大的應用價值而引起國內外學者的廣泛關注。通過車輛或移動手機中的GPS設備獲取的數據可以成為監測城市交通量的可行來源[8]。隨著從車輛和手機中獲得的GPS數據越來越多，基于這些大規模分散數據估計路段通行時間已變為現實。因為手機數據涉及個人隱私等問題，大量研究主要以車輛GPS數據為主。Zhan等[9]基于軌跡數據估計城市交通流量；Zheng等[10]基于稀疏車輛數據提出了估計城市路段通行時間的ANN模型；Hunter等[11]利用GPS車輛數據統計路段通行時間；Herring等[12]認為出租車相比普通車輛在城市中具有更高滲透率，利用出租車GPS數據可以更好表現道路網情況，因此他們基于500輛出租車的GPS數據，估計和預測了舊金山城市范圍內離散的交通狀況。然而，所有上述方法僅適用于GPS軌跡數據。但是，現實世界中大量出租車GPS數據僅含起點終點(origin-destination，OD)信息，如紐約公布的出租車行駛數據集[13]等。由于全球定位系統起點終點(GPS-OD)數據中，僅包含出租車一次運營過程的起點和終點，而不包含本次運營的路線信息，于是基于GPS-OD數據進行路網通行時間估計，不僅需要擬合路段時間，還需要分析出租車運行路線，給城市道路網路段通行時間估計問題帶來了新的挑戰。Zhan[14-15]等利用紐約出租車GPS-OD數據，估計道路網路段通行時間。但是，他只考慮了道路單車道對車輛行駛的影響，當路段較寬時，車道數可能更多，單車道不能很好地刻畫道路網精細化程度。

為了克服上述的問題，本文基于出租車數據提出了一種城市道路網路段通行時間估計方法，主要貢獻在于:

1）建立了基于出租車GPS-OD數據集的雙車道道路網通行時間估計模型。假設道路網每條路段為雙車道，能夠更準確地描述道路網通行情況，為了避免訓練數據量不足而導致的過擬合問題，建立了雙車道間通行時間多項式關聯關系模型。

2）采用優化非線性最小二乘方法估計路段每小時平均通行時間，從而實現路網通行時間擬合。

3）設計多組實驗，分析雙車道通行時間之間不同多項式關系對道路網路段通行時間估計結果的影響，確定效果最優的多項式關系。通過多組估計不同時段路段通行時間的實驗，驗證了本文所提雙車道預測方法相比于單車道方法能夠更準確地估計道路網路段的通行時間。

1 道路網路段通行時間估計模型

本節將介紹估計道路網路段通行時間模型，該模型的總體框架如圖1所示，主要包括以下4個步驟:1)地圖匹配。GPS數據中的起點和終點映射到道路網中，以減小GPS誤差帶來的影響，將原始數據轉化為可用數據。2)路徑選擇。采用k-最短路徑算法[16]，構建每段行程的路徑集合，并根據MNL(multinominal logit model)[17]模型計算司機選擇不同路徑的可能性，最后篩選合理的路徑集合作為估計路段時間過程的基礎。3)雙車道通行時間模型構建。為精細刻畫道路網通行時間程度，提出雙車道通行時間多項式關聯關系模型。4)路段通行時間估計。將步驟2)中篩選出的多條路徑作為出租車某次行程的可能發生事件以計算每次行程的期望時間，最后將路段通行時間估計問題轉換為行程觀測時間與期望時間均方誤差最小問題。

圖1 模型總體框架Fig. 1 General framework for model

下面將詳細介紹地圖匹配、路徑選擇模型、路段雙車道通行時間間多項式關聯關系模型，道路網路段通行時間估計方法。

1.1 地圖匹配

GPS數據因接收設備老化，信號傳播延遲等原因存在一定定位誤差，需要預先對原始GPS數據進行地圖匹配，其具體作用將起點和終點映射到道路網中，將原始數據轉換為可用數據，便于道路網分析。

圖2說明了數據地圖匹配過程，其中端點(A1，A2，B1，B2)為路徑相交節點，首先將原始起點和終點 (A，B)匹配到最近路段的垂足上 (A′，B′)，匹配后的點的位置用路段兩個端點(A1和A2，B1和B2)和表示。對于位于單向街道的起點和終點，兩個端點在給定路段的方向信息情況下很容易被識別。對于位于雙向街道上的點，這個路段的兩個端點都可用，不同端點組合的也可能是同樣的記錄。

圖2 地圖匹配示例Fig. 2 Illustration of data mapping

1.2 路徑選擇模型

將GPS-OD數據進行地圖匹配后，得到了道路網中每次行程的起點終點數據。由于路徑選擇信息的缺失，在估計城市道路網時間時需要推斷實際的路徑。但在城市的道路網中，對于某一確定的出租車行程，所有路徑的集合是非常大的。考慮到交通網中觀測數目過于龐大，對整個空間進行路徑搜索非常耗時，減少路徑數目是很有必要的。這里，采用k-最短路徑搜索算法生成最初的路徑集合，然后利用數據中記錄的行程距離來排除不合理的路徑。

計算每段行程的可選路徑集合后，由于缺少司機社會和行為特征，不能用傳統的計量經濟學模型來估計司機所選擇的路徑。因為司機做出決策之前不可能知道實際的路徑時間。但是，他們可以通過經驗推測道路網通行時間，因此本文基于MNL模型利用可選路徑集合中的路徑時間和距離表示路徑成本Cm求不同路徑的選擇概率。為降低復雜性，定義路徑選擇模型為

式中：Pm表示某一行程中可選路徑m的選擇概率與道路網路段通行時間t、行程中各個可選路徑的距離d、參數θ有關。Cm表示路徑m的成本與道路網路段通行時間t和路徑距離dm有關，參數θ用于表示司機感知不同時間段道路網通行時間不同時的路徑成本變化，θ大表示感知錯誤小，司機傾向于選擇成本小的路徑，而θ小意味著感知錯誤較大，成本越大的路徑越有可能被選擇。在此模型中，θ和道路網通行時間都是待估參數。

假設每個司機在同一起點終點的行程下，更偏好選擇行程時間和距離更短的路徑，那他們就能夠行駛更多行程數量，獲得更多收益。在建立合理的路徑集合時，設置閾值用于排除違反上述選擇行為假設的路徑。路徑距離在行程觀測距離一定比例內的才會被使用。因為數據中記錄的行程距離不精確(只到160 m)，設置工作日行程距離閾值為15%～25%，周末為20%～25%，消除那些偏離記錄中行程距離太多的不合理路徑。閾值設定取決于一個小時內可用的行程數據量。

根據城市出租車計價規則:開始行程收取基本費用，超過基本乘車距離和時間，按相應比例收取疊加費用。考慮到實際情況下票價計算的復雜，采用行程時間和距離的線性模型表示行程成本，如式(2)所示。

式中：fare 表示行程成本，β0為常數，β1、β2是行程時間和距離的成本系數。根據文獻[14]，β1、β2的估計值為0.275/min和2.516/km。

式中：dm是路徑m的距離，路徑m的通行時間定義為

式中：t0是起點所在路段的通行時間，tD是終點所在路段的通行時間，L是道路網的路段集合，tl是路段l的通行時間，是路徑與路段的關系值，取值為0、1, 1表示路徑m經過路段l，0則相反，是距離比例。

1.3 路段雙車道通行時間之間多項式關聯關系模型

在城市道路網中許多道路分為左側車道、直行車道和右側車道。左側和直行車道在行駛過程中會出現等待紅綠燈的情況，右側車道則可以直接通行。若只考慮單車道情況，將會忽略左側和直行車道上等待紅綠燈的時間。若加入多車道，但不考慮車道間關系，可能導致待估變量數目太多，擬合效果較差，或樣本數不足的情況。假定同一路段上左側車道和直行車道上的車輛通行時間服從相似的分布，并根據路段車道間車流量會相互影響的實際情況，我們認為路段上為雙車道，且存在一定的多項式關系，如式(5)所示。

式中：x是路段上一條車道的通行時間，y表示與x相關的另一條車道的通行時間，多項式γ為待估參數。

1.4 道路網路段通行時間估計

道路網路段通行時間估計是最小化行程觀測時間與期望時間之間的均方差，將出租車實際路徑選擇作為隱含變量，路段通行時間t、雙車道之間的多項式關系參數γ和比例參數θ作為待估參數，觀測i的期望時間可寫成

式中：Yi是觀測i的時間變量，Ri是根據觀測i的OD行程記錄建立的可能路徑集, t是道路網路段通行時間向量，γ是雙車道間多項式關系參數，d是Ri的所有路徑距離，是路徑m的行程時間，是選擇路徑m的可能性，θ是比例參數。

對于一條路徑，其距離是確定的，道路網路段通行時間向量t，雙車道間多項式關系參數γ和比例參數θ是待估參數，那么可以表示為一個與有關的函數：

進一步，行程觀測時間yi與行程期望時間之間的誤差可以定義為

則誤差平方定義為

由此，所估計的道路網路段通行時間為

2 道路網路段通行時間求解

利用Levenberg-Marquardt(LM)[18]方法解決非線性最小二乘問題。該方法是一種廣泛用于求解最小二乘擬合和非線性規劃問題的優化算法。在各種問題上，它優于一般的梯度下降方法和著名的高斯–牛頓(GN)方法[18]。傳統的高斯–牛頓法是計算代價高的線性搜索法。更新的高斯–牛頓法類似于牛頓法，當近似的Hessian矩陣近似奇異時變成了數學問題。如果利用不恰當的初始值，則容易不能收斂到最優。另一方面，Levenberg-Marquardt方法利用信任域策略而不是線性搜索方法，在更新步驟前確定步長。在LM中利用不同的Hessian近似方法也有助于確保每次迭代時矩陣的正定性，具有更好的魯棒性，這意味著在許多情況下，即使初始值遠離最終優值，Levenberg-Marquardt法也能找到一個近似解。在Bonnans和Gilbert[19]中表明Levenberg-Marquardt具有快速局部收斂性能。

本文中，利用LM算法求解的目標函數為行程期望時間：

路段通行時間t，車道間多項式關系參數γ，比例參數θ在第v次迭代更新為

當迭代結束后，式(17)所得t值即為所估計的道路網路段通行時間，γ為雙車道間多項式關系參數，θ為表示司機對道路網感知程度的比例參數。

通過分析可以發現，上述函數非凸，可能有多個局部最優點。在具體求解時，考慮將初始值默認為整個道路網當前時段下的平均速度，能較快較好地收斂到合適的最優的值。

3 實驗結果與分析

我們采用紐約出租車行程數據集，數據由城市出租車豪華轎車委員會(New York City Taxi and Limousine Commission，NYTLC)收集。其特點是每個出租車都安裝了GPS設備采集數據。紐約有北美最大的出租車市場，12 779(2006年)輛黃色紀念章出租車每年大約服務2.4億人次。在曼哈頓，乘坐出租車人數是所有出行人數的25%[20]。數據集包含2010—2015年出租車行程數據，其中包括行程開始和結束(OD數據)的地理位置、行程距離、時間和票價等信息，而缺少出租車的確切軌跡。但是，大量的數據(一天450 000～550 000的記錄數量)可以推斷出租車可能路線，并進一步估計道路網的路段通行時間。

基于Python語言編程實現前面部分討論的模型。硬件配置為i5處理器，3.2 GHz CPU，4 GB內存。在實驗中利用均方根誤差(root mean square error，RMSE)和平均絕對百分比誤差(mean absolute percentage error，MAPE)來評估估計結果：

3.1 測試數據和道路網

實驗中利用紐約出租車兩周(3/2/2015—3/15/2015)的OD行程數據測試所提出的方法。實驗區域位于曼哈頓中央公園東南部一塊1 508 m2的范圍，相關道路網如圖3所示，包含208個節點和386條邊。道路網中有348條道路是單向街道，38條是雙向街道。圖4、5分別展示了在該范圍內工作日(3/2/2015和3/9/2015，周一)和周末(3/7/2015和3/14/2015，周六)的行程頻數。通過統計和觀察圖4、5可以發現，該區域內工作日(周一)一小時內將近1 200條行程數，周六大約1 000條的行程數。且每周同一天行程觀測數近似服從同一分布。

圖3 研究區域測試道路網:曼哈頓市中心Fig. 3 Test network of study region: midtown Manhattan

圖4 研究區域內周一每小時觀測數目直方圖Fig. 4 Histogram for number of hourly observations in the study region on Monday

圖5 研究區域內周六每小時觀測數目直方圖Fig. 5 Histogram for number of hourly observations in the study region on Saturday

若實驗數據以分鐘為單位采樣，行程數和信息量太少不能保證良好的統計意義。若以天為單位采樣，不具有良好的代表性和研究意義。因此實驗以小時為單位采樣，從相應的數據中估計道路網通行時間。

3.2 結果與分析

為了驗證提出的算法性能，在實驗中引入了Zhan[14]提出的單車道道路通行時間估計模型進行比較。設計了兩組實驗，第一組實驗分析單車道與雙車道間不同多項式關系對估計道路網路段通行時間結果的影響，并確定效果最優的多項式關系，第二組為不同時段估計路段通行時間的實驗。

3.2.1 雙車道間通行時間多項式關聯關系模型下的估計誤差實驗

為了驗證2.3節所提雙車道模型的有效性，以3/2/2015—3/15/2015中9:00–10:00為研究時段分別計算不同車道關系下的模型估計誤差，實驗結果如表1所示。通過觀察可以發現，雙車道模型整體上RMSE和MAPE相比Zhan等[14]提出的單車道方法要低:當轉換模型為二階、三階、四階多項式時，一周中有半數以上的時間段雙車道模型誤差低于單車道模型;當轉換模型為五階、六階多項式時，一周中的RMSE和MAPE全都低于單車道模型結果。當雙車道通行時間之間多現實轉換模型取為六階多項式時，周一到周六實驗所得的RMSE和MAPE分別比單車道低 3.45，5.33，0.21，0.13，0.06，0.41 和39.8%，11.7%，1.75%，2.6%，1.5%，5.4%。上述分析證明，高階多項式的雙車道模型能夠更好地刻畫道路網的精細化程度，相比單車道模型能夠更準確地估計道路網通行時間。

表1 不同車道關系下的模型估計誤差Table 1 Model estimation error in different lane conditions

3.2.2 單車道模型與雙車道六階多項式關聯關系模型估計道路網通行時間的實驗

該實驗分為訓練和測試兩個階段，首先基于第3節訓練求出道路網路段通行時間t，雙車道間六階多項式參數γ、θ 3個值，然后在測試階段輸入新的OD行程記錄，并根據式(6)求出該行程記錄的期望時間和誤差。

基于兩周的GPS數據(3/2/2010-3/15/2010)，其中每周同一天數據的80%作為訓練樣本，剩下20%第2周的數據作為測試樣本，估計一天中4個時間段 (9:00—10:00，13:00—14:00，19:00—20:00，21:00—22:00)的道路網路段通行時間。分別采用Zhan[14]單車道模型和本文雙車道為六階多項式關系的模型對道路路段通行時間進行估計，通過觀察表2可見，雙車道模型在更多數據情況下結果都優于單車道模型。

表2 模型估計誤差Table 2 Model estimation error

除了時間段(3月9日周三21:00—22:00)，雙車道模型路段通行時間估計結果的MAPE低于40%，可以觀察到單車道模型和雙車道模型在周三21:00—22:00誤差值最大。可發現周三(3/11/2015)有紐約洋基對戰巴爾的摩金鶯的橄欖球比賽，比賽結束后可能導致大量擁堵以及密集人群流動，該事件可能與誤差結果有較大關系。且雙車道模型遇到異常情況時，效果更加穩健，其結果比單車道模型低94%。

我們用道路網路段通行速度而不是道路網路段通行時間直觀表示估計結果，圖6表示周一、周二9:00—10:00, 路段估計時間直方圖和行程觀測時間與估計時間之間的關系圖，其中X軸表示路段通行速度，Y軸表示該速度的路段數目。子圖中X軸為行程觀測時間，Y軸為模型估計時間。圖7表示周三，周六13:00—14:00的關系。其他時間段的關系與其相似，不多作贅述。

圖6 周一、周二路段估計時間直方圖和行程觀測時間與估計時間之間的關系Fig. 6 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Monday, Tuesday

圖7 周三，周六路段估計時間直方圖和通行觀測時間與估計時間之間的關系Fig. 7 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Wednesday,Saturday

圖8 周五、周日路段估計時間直方圖和通行觀測時間與估計時間之間的關系Fig. 8 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Friday, Sunday

由于路段通行時間是以小時為單位估計的，所以一小時內道路的變化也會導致模型的誤差(Fosgerau和Fukuda[21])。司機之間的選擇偏好(例如，一些司機駕駛速度快，偏好選擇短路徑，一些司機駕駛速度慢，偏好采取相對較長的路徑等)也可能導致誤差。觀察到某些行程在測試的道路網中長達20 min，這使得在路徑選擇中有很多不確定性，從而導致了一些誤差。

4 結束語

本文提出了一種基于出租車GPS-OD數據來估計城市道路網通行時間的新模型。為了更精細地刻畫道路網，該模型基于雙車道估計行程期望時間，為了避免訓練數據量不足而導致的過擬合問題，建立了雙車道間通行時間多項式關聯關系模型，并通過最小化行程期望時間和行程觀測時間之間的誤差來估計道路網通行時間。實驗結果表明本文提出的方法能夠有效地估計道路網每小時通行時間。為充分利用城市出租車數據估計道路網時間提供新的可能性。在下一步工作中，我們將利用GPS數據進一步研究城市交通流量的估計問題。

[1]COIFMAN B, CASSIDY M. Vehicle reidentification and travel time measurement on congested freeways[J]. Transportation research part a: policy and practice, 2002, 36(10):899–917.

[2]ZHANG X, ZHANG B, LIU L, et al. Estimating foliar nitrogen concentration with hyperspectral remote sensing image[C]//Third International Asia-Pacific Environmental Remote Sensing Remote Sensing of the Atmosphere, Ocean,Environment, and Space. Beijing, 2003: 187–193.

[3]WU C C, LEE W M G. Control of vaporous naphthalene by scrubbing with surfactants[J]. Journal of environmental engineering, 2004, 130(3): 276–281.

[4]PARK D, RILETT L. Forecasting multiple-period freeway link travel times using modular neural networks[J]. Transportation research record: journal of the transportation research board, 1998(1617): 163–170.

[5]LI R, ROSE G. Incorporating uncertainty into short-term travel time predictions[J]. Transportation research part c:emerging technologies, 2011, 19(6): 1006–1018.

[6]YEON J, ELEFTERIADOU L, LAWPHONGPANICH S.Travel time estimation on a freeway using discrete time Markov chains[J]. Transportation research part B: methodological, 2008, 42(4): 325–338.

[7]HASAN S, CHOUDHURY C, BEN-AKIVA M, et al. Modeling of travel time variations on urban links in London[J].Transportation research record: journal of the transportation research board, 2011(2260): 1–7.

[8]HERRERA J C, WORK D B, HERRING R, et al. Evaluation of traffic data obtained via GPS-enabled mobile phones: the mobile century field experiment[J]. Transporta-tion research part c: emerging technologies, 2010, 18(4):568–583.

[9]ZHAN X, ZHENG Y, Yi X, et al. Citywide traffic volume estimation using trajectory data[J]. IEEE transactions on knowledge and data engineering, 2017, 29(2): 272–285.

[10]ZHENG F, VAN ZUYLEN H. Urban link travel time estimation based on sparse probe vehicle data[J]. Transportation research part c: emerging technologies, 2013, 31(0):145–157.

[11]HUNTER T, HERRING R, ABBEEL P, et al. Path and travel time inference from GPS probe vehicle data[J]. NIPS analyzing networks and learning with graphs, 2009, 12(1).

[12]HERRING R, HOFLEITNER A, ABBEEL P, et al. Estimating arterial traffic conditions using sparse probe data[C]//13th International IEEE Conference on Intelligent Transportation Systems. Madeira Island, Portugal, 2010:929–936.

[13]Taxi data from new york taxi and limousine commission.[2016-05-14] http://www.nyc.gov/html/tlc/html/home/home.shtml.

[14]ZHAN X, HASAN S, UKKUSURI S V, et al. Urban link travel time estimation using large-scale taxi data with partial information[J]. Transportation research part c: emerging technologies, 2013, 33(0): 37–49.

[15]ZHAN X, UKKUSURI S V, YANG C. A Bayesian mixture model for short-term average link travel time estimation using large-scale limited information trip-based data[J]. Automation in construction, 2016, 72: 237–246.

[16]YEN J Y. Finding the k shortest loopless paths in a network[J]. Management science, 1971, 17(11): 712–716.

[17]DAGANZO C. Multinomial probit: the theory and its application to demand forecasting[M]. Elsevier, 2014.

[18]CHEN Y, OLIVER D S. Levenberg–Marquardt forms of the iterative ensemble smoother for efficient history matching and uncertainty quantification[J]. Computational geosciences, 2013, 17(4): 689–703.

[19]BONNANS J F, GILBERT J C, LEMARéCHAL C, et al.Numerical optimization: theoretical and practical aspects[M]. Springer Science and Business Media, 2013.

[20]KING D A, PETERS J R, DAUS M W. Taxicabs for improved urban mobility: are we missing an opportunity[C]//Transportation Research Board 91st Annual Meeting.Washington DC, USA, 2012 (12-2097).

[21]FOSGERAU M, FUKUDA D. Valuing travel time variability: Characteristics of the travel time distribution on an urban road[J]. Transportation research part c: emerging technologies, 2012, 24(0): 83–101.

[22]孫鋒, 黃玲, 葉盈,等. 混行條件下直線式公交站點停靠車輛數優化[J]. 哈爾濱工程大學學報, 2015, 36(2): 152–155.SUN Feng, HUANG Ling, YE Ying, et al. Optimizing the number of buses stopping at on-line stops under mixed traffic conditions[J]. Journal of Harbin Engineering University, 2015, 36(2): 152–155.

[23]徐程, 曲昭偉, 陶鵬飛,等. 動態交通數據異常值的實時篩選與恢復方法[J]. 哈爾濱工程大學學報, 2016, 37(2):211–217.XU Cheng, QU Zhaowei, TAO Pengfei, et al. Methods of real-time screening and reconstruction for dynamic traffic abnormal data[J]. Journal of Harbin Engineering University, 2016, 37(2): 211–217.