Improved Dynamic Time Warping Algorithm for Bus Route Trajectory Curve Fitting
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 147, Issue 8
Abstract
Applying the electronic route map is a cornerstone for improving the management and operational efficiency of transportation systems. However, the practice of electronic route map designed specifically for the transit system is relatively scarce, because buses are still running and navigating in a complex environment. One major reason is that the online electronic map often fails to match the real-world bus network due to delayed updating of database. To address this issue, this paper proposes a method to fit the bus route trajectory curve based on global positioning system (GPS) data. A complete data processing methodology is established, including GPS trajectory similarity comparison, similar trajectories merging, and simplification of merged bus route trajectories. This paper innovatively proposes a merging algorithm named dynamic time warping–median-based fusion (DTW-MF), which aims to minimize the bias caused by outliers in GPS fusion. Additionally, the Douglas-Peucker algorithm is used for trajectory simplification, which smoothens the bus route trajectories and makes it easier to understand. A case study is conducted in a real-world bus system with 93 bus routes in Hangzhou, China. The results show that the proposed DTW-MF method outperforms the other two commonly used methods, namely DTW barycenter averaging (DBA) and prioritized shape averaging (PSA) algorithms, both in merging performance and computational efficiency.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
This study is supported by the National Key Research and Development Program of China (No. 2018YFB1600900), the General Projects of the National Natural Science Foundation of China (No. 71771050), and the Natural Science Foundation of Jiangsu Province in China (BK20180402).
References
Ahmed, M., S. Karagiorgou, D. Pfoser, and C. Wenk. 2015. “A comparison and evaluation of map construction algorithms using vehicle tracking data.” GeoInformatica 19 (3): 601–632. https://doi.org/10.1007/s10707-014-0222-6.
Ai, C., and Y. Tsai. 2015. “Automatic horizontal curve identification and measurement method using GPS data.” J. Transp. Eng. 141 (2): 04014078. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000740.
Alnaymat, G., S. Chawla, and J. Taheri. 2009. “Sparse DTW: A novel approach to speed up dynamic time warping.” In Vol. 101 of Proc., 8th Australasian Data Mining Conf., 117–127. New York: Association for Computing Machinery.
Amiripour, S. M. M., A. Ceder, and A. S. Mohaymany. 2014. “Hybrid method for bus network design with high seasonal demand variation.” J. Transp. Eng. 140 (6): 04014015. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000669.
Assent, I., M. Wichterich, R. Krieger, H. Kremer, and T. Seidl. 2009. “Anticipatory DTW for efficient similarity search in time series databases.” Proc. VLDB Endowment 2 (1): 826–837. https://doi.org/10.14778/1687627.1687721.
Biagioni, J., and J. Eriksson. 2012. “Inferring road maps from global positioning system traces: Survey and comparative evaluation.” Transp. Res. Rec. 2291 (1): 61–71. https://doi.org/10.3141/2291-08.
Bruntrup, R., S. Edelkamp, S. Jabbar, and B. Scholz. 2005. “Incremental map generation with GPS traces.” In Proc., 2005 IEEE Intelligent Transportation Systems. New York: IEEE.
Dubuisson, M. P., and A. K. Jain. 2002. “A modified Hausdorff distance for object matching.” In Vol. 1 of Proc., of 12th Int. Conf. on Pattern Recognition. New York: IEEE.
Fathi, A., and J. Krumm. 2010. “Detecting road intersections from GPS traces.” In Proc., Int. Conf. on Geographic Information Science. Berlin: Springer.
Fei, L., and J. He. 2009. “A three-dimensional Douglas–Peucker algorithm and its application to automated generalization of DEMs.” Int. J. Geog. Inf. Sci. 23 (6): 703–718. https://doi.org/10.1080/13658810701703001.
Guo, T., K. Iwamura, and M. Koga. 2007. “Towards high accuracy road maps generation from massive GPS traces data.” In Proc., IEEE Int. Geoscience and Remote Sensing Symp., 667–670. New York: IEEE.
Hu, J., A. Razdan, J. C. Femiani, M. Cui, and P. Wonka. 2007. “Road network extraction and intersection detection from aerial images by tracking road footprints.” IEEE Trans. Geosci. Remote Sens. 45 (12): 4144–4157. https://doi.org/10.1109/TGRS.2007.906107.
Huang, D., X. Chen, Z. Liu, C. Lyu, S. Wang, and X. Chen. 2020a. “A static bike repositioning model in a hub-and-spoke network framework.” Transp. Res. Part E Logist. Transp. Rev. 141 (Sep): 102031. https://doi.org/10.1016/j.tre.2020.102031.
Huang, D., J. Xing, Z. Liu, and Q. An. 2020b. “A multi-stage stochastic optimization approach to the stop-skipping and bus lane reservation schemes.” Transportmetrica A: Transport Sci. 17 (4): 1–33.
Huang, Y., W. Fan, and L. Liu. 2018. “Road network updating and track fusion using trajectory data.” Surv. Mapp. Bull. 497 (8): 119–123.
Kong, Q., W. Shi, and Y. Liu. 2012. “Method of automatic generation of vector road network map based on GPS trajectory.” J. China Univ. Sci. Technol. 42 (8): 623–627.
Li, X., J. Tang, X. Hu, and W. Wang. 2020. “Assessing intercity multimodal choice behavior in a touristy city: A factor analysis.” J. Transport Geogr. 86 (Jun): 102776. https://doi.org/10.1016/j.jtrangeo.2020.102776.
Liu, Z., Y. Liu, C. Lyu, and J. Ye. 2020. “Building personalized transportation model for online taxi-hailing demand prediction.” IEEE Trans. Cybern. 1–9. https://doi.org/10.1109/TCYB.2020.3000929.
Mazloumi, E., R. Currie, and R. Rose. 2010. “Using GPS data to gain insight into public transport travel time variability.” J. Transp. Eng. 136 (7): 623–631. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000126.
McGranaghan, M., D. Mark, and M. D. Gould. 1987. “Automated provision of navigation assistance to drivers.” Am. Cartographer 14 (2): 121–138. https://doi.org/10.1559/152304087783875219.
Niennattrakul, V., and C. A. Ratanamahatana. 2009. “Shape averaging under time warping.” In Vol. 2 of Proc., 6th Int. Conf. on Electrical Engineering, Computer, Telecommunications and Information Technology, 626–629. New York: IEEE.
Peng, G. H., X. H. Cai, B. F. Cao, and C. Q. Liu. 2011. “Non-lane-based lattice hydrodynamic model of traffic flow considering the lateral effects of the lane width.” Phys. Lett. A 375 (30): 2823–2827. https://doi.org/10.1016/j.physleta.2011.06.021.
Petitjean, F., A. Ketterlin, and P. Gançarski. 2011. “A global averaging method for dynamic time warping, with applications to clustering.” Pattern Recognit. 44 (3): 678–693. https://doi.org/10.1016/j.patcog.2010.09.013.
Saalfeld, A. 1999. “Topologically consistent line simplification with the Douglas-Peucker algorithm.” Cartography Geographic Inf. Sci. 26 (1): 7–18. https://doi.org/10.1559/152304099782424901.
Shi, W., S. Shen, and Y. Liu. 2009. “Automatic generation of road network map from massive GPS vehicle trajectories.” In Proc., Int. IEEE Conf. on Intelligent Transportation Systems, 1–6. New York: IEEE.
Tang, L., X. Yang, Z. Kan, and Q. Li. 2015. “Lane-level road information mining from vehicle GPS trajectories based on naïve Bayesian classification.” Int. J. Geo-Inf. 4 (4): 2660–2680. https://doi.org/10.3390/ijgi4042660.
Turkay, S., and H. Akcay. 2016. “Road roughness evaluation by curve-fitting and subspace-identification methods.” J. Transp. Eng. 142 (11): 04016050. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000877.
Uno, N., F. Kurauchi, H. Tamura, and Y. Iida. 2009. “Using bus probe data for analysis of travel time variability.” J. Intell. Transp. Syst. 13 (1): 2–15. https://doi.org/10.1080/15472450802644439.
Wang, Z. H., X. Hu, and J. Shan. 2015. “A rasterization-based hierarchical approach for urban road centerline extraction from crowdsourcing GPS floating car data.” Bull. Surv. Mapp. 60 (8): 22–24.
Zhang, M. 2018. “Exploration of promoting the integration of urban and rural passenger transport.” Manage. Transp. Enterprises 33 (2): 29–31.
Zheng, J., and C. Liu. 2017. “DTW-TA trajectory anonymity algorithm based on DTW distance metric function.” Comput. Appl. Res. 34 (8): 2459–2463.
Zhong, H., H. Jin, J. Shen, and M. Xu. 2017. “Algorithm of bus route trajectory based on GIS road network.” Comput. Syst. Appl. 11 (26): 182–186.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 147 • Issue 8 • August 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Jun 11, 2020
Accepted: Feb 19, 2021
Published online: Jun 10, 2021
Published in print: Aug 1, 2021
Discussion open until: Nov 10, 2021
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.