Intersection delay estimation from floating car data via principal curves: a case study on Beijing’s road network

Abstract

It is a pressing task to estimate the real-time travel time on road networks reliably in big cities, even though floating car data has been widely used to reflect the real traffic. Currently floating car data are mainly used to estimate the real-time traffic conditions on road segments, and has done little for turn delay estimation. However, turn delays on road intersections contribute significantly to the overall travel time on road networks in modern cities. In this paper, we present a technical framework to calculate the turn delays on road networks with float car data. First, the original floating car data collected with GPS equipped taxies was cleaned and matched to a street map with a distributed system based on Hadoop and MongoDB. Secondly, the refined trajectory data set was distributed among 96 time intervals (from 0: 00 to 23: 59). All of the intersections where the trajectories passed were connected with the trajectory segments, and constituted an experiment sample, while the intersections on arterial streets were specially selected to form another experiment sample. Thirdly, a principal curve-based algorithm was presented to estimate the turn delays at the given intersections. The algorithm argued is not only statistically fitted the real traffic conditions, but also is insensitive to data sparseness and missing data problems, which currently are almost inevitable with the widely used floating car data collecting technology. We adopted the floating car data collected from March to June in Beijing city in 2011, which contains more than 2.6 million trajectories generated from about 20000 GPS-equipped taxicabs and accounts for about 600GB in data volume. The result shows the principal curve based algorithm we presented takes precedence over traditional methods, such as mean and median based approaches, and holds a higher estimation accuracy (about 10%–15% higher in RMSE), as well as reflecting the changing trend of traffic congestion. With the estimation result for the travel delay at intersections, we analyzed the spatio-temporal distribution of turn delays in three time scenarios (0: 00–0: 15, 8: 15–8: 30 and 12: 00–12: 15). It indicates that during one’s single trip in Beijing, average 60% of the travel time on the road networks is wasted on the intersections, and this situation is even worse in daytime. Although the 400main intersections take only 2.7% of all the intersections, they occupy about 18% travel time.

Keywords

intersection delay / float car data / trajectory / principal curves

References

[1] Ban X J, Herring R, Hao P, Bayen A M (2009). Delay pattern estimation for signalized intersections using sampled travel times. Transport Res Rec, 2130(1): 109–119

[2] Bejan A, Gibbens R, Evans D, Beresford A, Bacon J, Friday A (2010). Statistical modelling and analysis of sparse bus probe data in urban areas. In:13th International IEEE Conference on Intelligent Transportation Systems (ITSC), <month>September</month><day>19–22</day>, Madeira Island, Portugal, 1256–1263

[3] Boyce D E, Kirson A, Schofer J L (1991). Design and implementation of ADVANCE: the Illinois dynamic navigation and route guidance demonstration program. In: IEEE Vehicle Navigation and Information Systems Conference(VNIS’91), <month>October</month><day>20–23</day>, Dearborn, Michigan, United States, 2: 415–426

[4] Cheu R L, Xie C, Lee D (2002). Probe vehicles population and sample size for arterial speed estimation. Comput-Aided Civ Inf, 17(1): 53–60

[5] Chodorow K, Dirolf M (2010). MongoDB: The Definitive Guide. Sebastopol, O’Reilly Media, Inc

[6] Cowan K, Gates G (2002). Floating Vehicle Data system-realisation of a commercial system. In: 11th International Conference on Road Transport Information and Control, <month>March</month><day>19–21</day>, London, the United Kingdom, 87–189

[7] Fabritiis C D, Ragona R, Valenti G (2008). Traffic estimation and prediction based on real time floating car data. In: 11th International IEEE Conference on Intelligent Transportation Systems, <month>October</month><day>12–15</day>, Beijing, China, 197–203

[8] Ghaffarian H, Fathy M, Soryani M (2012). Vehicular ad hoc networks enabled traffic controller for removing traffic lights in isolated intersections based on integer linear programming. Iet Intell Transp Sy, 6(2): 115–123

[9] Gühnemann A, Schäfer R P, Thiessenhusen K U, Wagner P. (2004). Monitoring traffic and emissions by floating car data. Institute of Transport Studies Working Paper, Issue ITS-WP-04–07, Sydney, Australia

[10] Hastie T, Stuetzle W (1989). Principal curves. J Am Stat Assoc, 84(406): 502–516

[11] Heidemann D (1994). Queue length and delay distributions at traffic signals. Transport Res B—Meth, 28(5): 377–389

[12] Hellinga B R, Fu L (2002). Reducing bias in probe-based arterial link travel time estimates. Transport Res C—Emer, 10(4): 257–273

[13] Herrera J, Work D, Herring R, Ban X J, Jacobson Q, Bayen A M (2010). Evaluation of traffic data obtained via GPS-enabled mobile phones: the Mobile Century field experiment. Transport Res C—Emer, 18(4): 568–583

[14] Herring R, Hofleitner A, Abbeel P, Bayen A (2010). Estimating arterial traffic conditions using sparse probe data. In: Proceedings of the 13th International IEEE Conference on Intelligent Transportation Systems, <month>September</month><day>19–22</day>, Madeira Island, Portugal, 929–936

[15] Homburger W S, Hall J W, William R R, Edward C S, Michelle D, Loretta H, John J L, Matthew R, Vernon H W (2007). Fundamentals of traffic engineering. University of California, Berkeley, Institute of Transportation Studies

[16] Hong J, Zhang X, Wei Z, Li L, Yong R (2007). Spatial and temporal analysis of probe vehicle-based sampling for real-time traffic information system. In: Proceedings of the 2007 IEEE Intelligent Vehicles Symposium, <month>June</month><day>13–15</day>, 2007, Istanbul, Turkey, 13–15

[17] Hunter T, Herring R, Abbeel P, Bayen A (2009). Path and travel time inference from GPS probe vehicle data. In: NIPS Analyzing Networks and Learning with Graphs, <month>December</month><day>7–10</day>, British Columbia, Canada

[18] Kothuri S M, Tufte K A, Fayed E, Robert L B (2008). Toward understanding and reducing errors in real-time estimation of travel times. Transport Res Rec, (2049): 21–28

[19] Kwong K, Kavaler R, Rajagopal R, Varaiya P (2009). Arterial travel time estimation based on vehicle re-identification using wireless magnetic sensors. Transport Res C—Emer, 17(6): 586–606

[20] Li R, Rose G (2011). Incorporating uncertainty into short-term travel time predictions. Transport Res C—Emer, 19(6): 1006–1018

[21] Liu H X, Ma W, Wu X, Hu H (2012). Real-time estimation of arterial travel time under congested conditions. Transportmetrica, 8(2): 87–104

[22] Long J, Gao Z, Zhao X, Lian A, Orenstein P (2011). Urban traffic jam simulation based on the cell transmission model. Netw Spat Econ, 11(1): 43–64

[23] Lou Y, Zhang C Y, Zheng Y, Xie X, Wang W, Huang Y (2009). Map-matching for low-sampling-rate GPS trajectories. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington, 352–361

[24] Lu C (2010). A travel time estimation for planning models considering signalized intersections.ITE J, 80(10): 34–39

[25] Nielsen O A, Frederiksen R D, Simonsen N (1998). Using expert system rules to establish data for intersections and turns in road networks. Int Trans Oper Res, 5(6): 569–581

[26] Skabardonis A, Geroliminis N (2005). Real-time estimation of travel times on signalized arterials. In: Hani S M, ed. Transportation and Traffic Theory. Flow, Dynamics and Human Interaction. 16th International Symposium on Transportation and Traffic Theory, July 19-21, College Park Maryland, United States, 387–406

[27] Sun L (2007). An approach for intersection delay estimate based on floating vehicles. Dissertation for Ph.D. Degree<DissertationTip/>. Beijing: Beijing University of Technology (in Chinese)

[28] Wang Z (2004). Using floating cars to measure travel time delay: How accurate is the method? Transport Res Rec, 1870(1): 84–93

[29] White T (2010). Hadoop: The Definitive Guide. Sebastopol: Yahoo Press, O’Reilly Media, Inc

[30] Winter S (2002). Modeling costs of turns in route planning. GeoInformatica, 6(4): 345–361

[31] Xie X, Cheu R L, Lee D H (2001). Calibration-free arterial link speed estimation model using loop data. J Transp Eng, 127(6): 507–514

[32] Xiong J, Liu J, Guan J, Sun J, Liu X, Wen H (2010). The minimum sample size determination of floating car in Beijing expressway. J Transp Syst Eng Inf Technol, 4: 38–43 (in Chinese)

[33] Zhang H C, Lu F, Zhou L, Duan Y Y (2011). Computing turn delay in city road network with GPS collected trajectories. In: Proceedings of the 2011 International Workshop on Trajectory Data Mining and Analysis. <month>September</month><day>17–21</day>, Beijing, China, ACM,45–52

[34] Zhang J P, Wang J (2003). An overview of principal curves. Chinese Journal of Computers, 26(2): 129–146 (in Chinese)

[35] Zheng N B, Lu F, Duan Y Y (2010). Dynamic dual graph model for turn delays on road networks. Journal of Image and Graphics, 15(6): 915–920 (in Chinese)

[36] Zheng Y, Zhou X F (2011). Computing with Spatial Trajectories. New York: Springer-Verlag

Acknowledgements

This research was supported by the National Natural Science Foundation of China (Grant No. 41271408), the National Hi-tech Research and Development Program of China (Grant No. 2012AA12A211) and State Key Laboratory of Resources and Environmental Information System Open Foundation (No. 088RA500KA). And we also thank the anonymous referees for their helpful comments and suggestions.

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg