«上一篇
 文章快速检索 高级检索

 智能系统学报  2017, Vol. 12 Issue (6): 790-798  DOI: 10.11992/tis.201706071 0

### 引用本文

HUANG Shunlun, DU Chun, SONG Baoquan, et al. Urban link travel time estimation using taxi data[J]. CAAI Transactions on Intelligent Systems, 2017, 12(6), 790-798. DOI: 10.11992/tis.201706071.

### 文章历史

Urban link travel time estimation using taxi data
HUANG Shunlun, DU Chun, SONG Baoquan, LI Jun, CHEN Hao
School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China
Abstract: The accurate estimation of urban link travel time plays a significant role in urban traffic monitoring and supervision. Using taxicab GPS trip data, which contains origin and destination locations, travel time, and distances, this paper establishes a model to estimate average short-term urban link travel times. Firstly, the urban road network is divided into many segments based on crossings, and the running route of the driver was analyzed using the k-shortest path search algorithm. Then, for each road segment, a polynomial incidence relation model of the travel time in double lanes is proposed; this increases precision and avoids the overfitting of the travel time of the road network caused by insufficient training data. Finally, by minimizing the mean square error between the expected path travel time and the observed path travel time as the optimization objective, the travel time of the road network is fitted. The results of experiments conducted on New York taxi datasets show that, relative to the traditional single-lane estimation method, the proposed model and method more efficiently estimate the travel time of the road segments in urban road networks.
Key words: travel time estimation    GPS-enabled taxicab    urban road networks    two-lane model

1）建立了基于出租车GPS-OD数据集的双车道道路网通行时间估计模型。假设道路网每条路段为双车道，能够更准确地描述道路网通行情况，为了避免训练数据量不足而导致的过拟合问题，建立了双车道间通行时间多项式关联关系模型。

2）采用优化非线性最小二乘方法估计路段每小时平均通行时间，从而实现路网通行时间拟合。

3）设计多组实验，分析双车道通行时间之间不同多项式关系对道路网路段通行时间估计结果的影响，确定效果最优的多项式关系。通过多组估计不同时段路段通行时间的实验，验证了本文所提双车道预测方法相比于单车道方法能够更准确地估计道路网路段的通行时间。

1 道路网路段通行时间估计模型

 图 1 模型总体框架 Fig.1 General framework for model

1.1 地图匹配

GPS数据因接收设备老化，信号传播延迟等原因存在一定定位误差，需要预先对原始GPS数据进行地图匹配，其具体作用将起点和终点映射到道路网中，将原始数据转换为可用数据，便于道路网分析。

 图 2 地图匹配示例 Fig.2 Illustration of data mapping
1.2 路径选择模型

 ${P_m}({\mathit{\boldsymbol{t}}},d,\theta ) = \frac{{\exp [ - \theta {C_m}({\mathit{\boldsymbol{t}}},{d_m})]}}{{\displaystyle\sum\nolimits_{j \in {R_i}} {\exp [ - \theta {C_j}({\mathit{\boldsymbol{t}}},{d_j})]} }}$ (1)

 ${\rm{fare}} = {\beta _0} + {\beta _1} \cdot {\rm{time}} + {\beta _2} \cdot {\mathop{\rm distance}\nolimits}$ (2)

 ${C_m}({\mathit{\boldsymbol{t}}}{\rm{, }}{d_m}) = {\beta _1} \cdot {g_m}({\mathit{\boldsymbol{t}})} + {\beta _2} \cdot {d_m}$ (3)

 ${g_m}({\mathit{\boldsymbol{t}}}) = {a_1}{t_O} + {a_2}{t_D} + \sum\nolimits_{l \in L} {{t_l}}$ (4)

1.3 路段双车道通行时间之间多项式关联关系模型

 $y = {\displaystyle\sum} _{i = 2}^k{\gamma _i}{x^i} + {\gamma _1}x + {\gamma _0},\, k = 2,3, \cdots$ (5)

1.4 道路网路段通行时间估计

 $E({Y_i}|{R_i}) = \sum\nolimits_{m \in {R_i}} {{g_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}}){P_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},d,\theta )}$ (6)

 $E({Y_i}|{R_i}) = f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )$ (7)

 ${r_i} = {y_i} - f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )$ (8)

 $S({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta ) = \sum\nolimits_{i \in D} {r_i^2 = \sum\nolimits_{i \in D} {{{({y_i} - f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta ))}^2}} }$ (9)

 ${\mathit{\boldsymbol{t}}} = \arg \;\mathop {\min }\limits_{\mathit{\boldsymbol{t}}} S({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )$ (10)
2 道路网路段通行时间求解

 $E({Y_i}|{R_i}) = f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta ) = \sum\nolimits_{m \in {R_i}} {{g_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}})\frac{{{P_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )}}{{{S_{{R_i}}}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )}}}$ (11)

 ${P_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta ) = \exp \theta ( - {\beta _1} \cdot {g_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}}) - {\beta _2} \cdot {d_m})$ (12)

 ${S_{{R_i}}}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta ) = \sum\nolimits_{j \in {R_i}} {\exp \theta ({\beta _1} \cdot {g_m}({\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}}) - {\beta _2} \cdot {d_m})}$ (13)

 ${{\mathit{\boldsymbol{J}}}_{il}} = \frac{{\partial f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )}}{{\partial {t_l}}},l = 1,2,\cdots,N$ (14)
 ${{\mathit{\boldsymbol{J}}}_{ip}} = \frac{{\partial f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )}}{{\partial \gamma }},p = N + 1,\cdots,N + k + 1$ (15)
 ${{\mathit{\boldsymbol{J}}} _{iq}} = \frac{{\partial f({R_i},{\mathit{\boldsymbol{t}}},{\mathit{\boldsymbol{\gamma }}},\theta )}}{{\partial \theta }},q = N + k + 2$ (16)

Jacobian矩阵是一个 ${N_D}*(N + k + 2)$ 的矩阵，其中ND是数据集中行程观测数目，N是道路网中路段数目，k是双车道间多项式关系的阶次。

 $\begin{array}{l}{\mathit{\boldsymbol{t}}} \approx {{\mathit{\boldsymbol{t}}}^{v + 1}} = {{\mathit{\boldsymbol{t}}}^v} + {{\mathit{\boldsymbol{u}}}_{\mathit{\boldsymbol{t}}}}^{(v)}\\{\mathit{\boldsymbol{\gamma }}} \approx {{\mathit{\boldsymbol{\gamma }}}^{v + 1}} = {{\mathit{\boldsymbol{\gamma }}}^v} + {{\mathit{\boldsymbol{u}}}_{\mathit{\boldsymbol{\gamma }}}}^{(v)}\\\theta \approx {\theta ^{v + 1}} = {\theta ^v} + {{\mathit{\boldsymbol{u}}}_\theta }^{(v)}\end{array}$ (17)

 $({{\mathit{\boldsymbol{J}}}^{(v){\rm{T}}}}{{\mathit{\boldsymbol{J}}}^{(v)}} + \lambda {\mathit{\boldsymbol{I}}}){{\mathit{\boldsymbol{u}}}^{(v)}} = {{\mathit{\boldsymbol{J}}}^{(v){\rm{T}}}}{r_i}$ (18)

3 实验结果与分析

 ${\rm{RMSE = }}\sqrt {\frac{1}{n}\displaystyle\sum _{i = 1}^n{{(T_i^{{{{\rm{Pr}}}}} - T_i^{{{{\rm{Ob}}}}})}^2}}$ (19)
 ${\rm{MAPE = }}\frac{1}{n}\displaystyle\sum_{i = 1}^n\left| {\frac{{T_i^{{\rm{Pr}}} - T_i^{{\rm{Ob}}}}}{{T_i^{{\rm{Ob}}}}}} \right| \times 100\%$ (20)

3.1 测试数据和道路网

 图 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 结果与分析

3.2.1 双车道间通行时间多项式关联关系模型下的估计误差实验

3.2.2 单车道模型与双车道六阶多项式关联关系模型估计道路网通行时间的实验

 图 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

4 结束语

 [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. (0) [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. (0) [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. (0) [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. (0) [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. (0) [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. (0) [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. (0) [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]. Transportation research part c: emerging technologies, 2010, 18(4): 568-583. (0) [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. (0) [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. (0) [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). (0) [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. (0) [13] Taxi data from new york taxi and limousine commission. [2016-05-14] http://www.nyc.gov/html/tlc/html/home/home.shtml. (0) [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. (0) [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. (0) [16] YEN J Y. Finding the k shortest loopless paths in a network[J]. Management science, 1971, 17(11): 712-716. (0) [17] DAGANZO C. Multinomial probit: the theory and its application to demand forecasting[M]. Elsevier, 2014. (0) [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. (0) [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. (0) [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). (0) [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. (0) [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. (0) [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. (0)