A taxi detour trajectory detection model based on iBAT and DTW algorithm

Jian Wan; Peiyun Yang; Wenbo Zhang; Yaxing Cheng; Runlin Cai; Zhiyuan Liu; Jian Wan; Peiyun Yang; Wenbo Zhang; Yaxing Cheng; Runlin Cai; Zhiyuan Liu

doi:10.3934/era.2022229

Electronic Research Archive

2022, Volume 30, Issue 12: 4507-4529. doi: 10.3934/era.2022229

Previous Article Next Article

Theory article Special Issues

A taxi detour trajectory detection model based on iBAT and DTW algorithm

1.
School of Transportation, Southeast University, China
2.
Research and Development Center on ITS Technology and Equipment, China Design Group, China
3.
China Urban Planning and Design Institute Shanghai Branch, China

Received: 19 July 2022 Revised: 10 September 2022 Accepted: 20 September 2022 Published: 17 October 2022

Taxi detour is a chronic problem in urban transport systems, which largely undermines passengers' riding experience and the city's image while unnecessarily worsening traffic congestion. Tourists unfamiliar with city roads often encounter detour problems. Therefore, it is important for regulatory authorities to develop a tool for detour behavior detection in order to discover or identify detours. This study proposes a detour trajectory detection model framework based on the trajectory data of taxis that can identify taxi driving detour fraud at the microscopic level and analyze the characteristics of detouring trajectories from the perspective of microscopic motion traits. The deviation from normal driving trajectories provides a framework for the automatic detection of detour trajectories for the off-site supervision platform of the taxis. Considering drawbacks of the isolation-Based Anomalous Trajectory (iBAT) algorithm, this paper made further improvements in trajectory anomaly detection. In this study, three methods including the iBAT, iBAT + Dynamic Time Warping (DTW), and iBAT + DTW algorithms considering the driving distance and time are compared using the relevant experimental data. The case studies verify that the proposed method outperforms the other methods. Verified by the experiments based on the trajectory data coming from Nanjing, the false positive rate of this framework is only 1.64%.
- taxi trajectory data,
- iBAT,
- DTW,
- anomaly detection
Citation: Jian Wan, Peiyun Yang, Wenbo Zhang, Yaxing Cheng, Runlin Cai, Zhiyuan Liu. A taxi detour trajectory detection model based on iBAT and DTW algorithm[J]. Electronic Research Archive, 2022, 30(12): 4507-4529. doi: 10.3934/era.2022229

Related Papers:

Abstract

Taxi detour is a chronic problem in urban transport systems, which largely undermines passengers' riding experience and the city's image while unnecessarily worsening traffic congestion. Tourists unfamiliar with city roads often encounter detour problems. Therefore, it is important for regulatory authorities to develop a tool for detour behavior detection in order to discover or identify detours. This study proposes a detour trajectory detection model framework based on the trajectory data of taxis that can identify taxi driving detour fraud at the microscopic level and analyze the characteristics of detouring trajectories from the perspective of microscopic motion traits. The deviation from normal driving trajectories provides a framework for the automatic detection of detour trajectories for the off-site supervision platform of the taxis. Considering drawbacks of the isolation-Based Anomalous Trajectory (iBAT) algorithm, this paper made further improvements in trajectory anomaly detection. In this study, three methods including the iBAT, iBAT + Dynamic Time Warping (DTW), and iBAT + DTW algorithms considering the driving distance and time are compared using the relevant experimental data. The case studies verify that the proposed method outperforms the other methods. Verified by the experiments based on the trajectory data coming from Nanjing, the false positive rate of this framework is only 1.64%.

References

[1]	Q. Cheng, Z. Liu, Y. Lin, X. S. Zhou, An s-shaped three-parameter (S3) traffic stream model with consistent car following relationship, Transp. Res. Part B Methodol., 153 (2021), 246-271. https://doi.org/10.1016/j.trb.2021.09.004 doi: 10.1016/j.trb.2021.09.004
[2]	H. Wang, Transportation-enabled urban services: A brief discussion, Mutimodal Transp., 1 (2022), 100007. https://doi.org/10.1016/j.multra.2022.100007 doi: 10.1016/j.multra.2022.100007
[3]	M. Ester, H. P. Kriegel, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in Kdd, AAAI, 96 (1996), 226-231.
[4]	Q. Cheng, Z. Liu, J. Guo, X. Wu, R. Pendyala, B. Belezamo, et al., Estimating key traffic state parameters through parsimonious spatial queue models, Transp. Res. Part C Emerging Technol., 137 (2022), 103596. https://doi.org/10.1016/j.trc.2022.103596 doi: 10.1016/j.trc.2022.103596
[5]	Z. Liu, Y. Wang, Q. Cheng, H. Yang, Analysis of the information entropy on traffic flows, IEEE Trans. Intell. Transp. Syst., 2022 (2022), 1-12. https://doi.org/10.1109/TITS.2022.3155933 doi: 10.1109/TITS.2022.3155933
[6]	D. Huang, J. Xing, Z. Liu, Q. An, A multi-stage stochastic optimization approach to the stop-skipping and bus lane reservation schemes, Transportmetrica A Transp. Sci., 17 (2021), 1272-1304. https://doi.org/10.1080/23249935.2020.1858206 doi: 10.1080/23249935.2020.1858206
[7]	F. Giannotti, M. Nanni, F. Pinelli, D. Pedreschi, Trajectory pattern mining, in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Jose, USA, (2007), 330-339. https://doi.org/10.1145/1281192.1281230
[8]	I. Syarif, A. Prugel-Bennett, G. Wills, Data mining approaches for network intrusion detection: from dimensionality reduction to misuse and anomaly detection, J. Inf. Technol. Rev., 3 (2012), 70-83.
[9]	Y. Yue, H. D. Wang, B. Hu, Q. Li, Y. G. Li, A. G. Yeh, Exploratory calibration of a spatial interaction model using taxi GPS trajectories, Comput. Environ. Urban Syst., 36 (2012), 140-153. https://doi.org/10.1016/j.compenvurbsys.2011.09.002 doi: 10.1016/j.compenvurbsys.2011.09.002
[10]	Q. Cheng, Y. Chen, Z. Liu, A bi-level programming model for the optimal lane reservation problem, Expert Syst. Appl., 189 (2022), 116147. https://doi.org/10.1016/j.eswa.2021.116147 doi: 10.1016/j.eswa.2021.116147
[11]	G. Münz, S. Li, G. Carle, Traffic anomaly detection using k-means clustering, in GI/ITG Workshop MMBnet, 7 (2007), 9.
[12]	I. N. Junejo, O. Javed, M. Shah, Multi feature path modeling for video surveillance, in Proceedings of the 17th International Conference on Pattern Recognition, IEEE, Cambridge, UK, 2 (2004), 716-719. https://doi.org/10.1109/ICPR.2004.1334359
[13]	Q. Meng, P. Liu, Z. Liu, Integrating multimodal transportation research, J. Multimodal Transport., 1 (2022), 100001. https://doi.org/10.1016/j.multra.2022.100001 doi: 10.1016/j.multra.2022.100001
[14]	Y. Zheng, Trajectory data mining: an overview, ACM Trans. Intell. Syst. Technol. (TIST), 6 (2015), 1-41. https://doi.org/10.1145/2743025 doi: 10.1145/2743025
[15]	Z. Feng, Y. Zhu, A survey on trajectory data mining: techniques and applications, IEEE Access, 4 (2016), 2056-2067. https://doi.org/10.1109/ACCESS.2016.2553681 doi: 10.1109/ACCESS.2016.2553681
[16]	N. Paragios, R. Deriche, Geodesic active regions: a new framework to deal with frame partition problems in computer vision, J. Visual Commun. Image Represent., 13 (2002), 249-268. https://doi.org/10.1006/jvci.2001.0475 doi: 10.1006/jvci.2001.0475
[17]	C. Stauffer, W. E. Grimson, Adaptive background mixture models for real-time tracking, in 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No PR00149), IEEE, Collins, USA, 2 (1999), 246-252. https://doi.org/10.1109/CVPR.1999.784637
[18]	S. Coşar, G. Donatiello, V. Bogorny, C. Garate, L. O. Alvares, F. Bremond, Toward abnormal trajectory and event detection in video surveillance, IEEE Trans. Circuits Syst. Video Technol., 27 (2016), 683-695. https://doi.org/10.1109/TCSVT.2016.2589859 doi: 10.1109/TCSVT.2016.2589859
[19]	J. Huo, X. Fu, Z. Liu, Q. Zhang, Short-term estimation and prediction of pedestrian density in urban hot spots based on mobile phone data, IEEE Trans. Intell. Transp. Syst., 23 (2022), 10827-10838. https://doi.org/10.1109/TITS.2021.3096274 doi: 10.1109/TITS.2021.3096274
[20]	D. Huang, Y. Wang, S. Jia, Z. Liu, A Lagrangian relaxation approach for the electric bus charging scheduling optimisation problem, Transportmetrica A Transp. Sci., 2022 (2022), 1-24. https://doi.org/10.1080/23249935.2021.2023690 doi: 10.1080/23249935.2021.2023690
[21]	J. Simon, Remote supply revisited: the jeep problem with costly transfer points, Multimodal Transp., 1 (2022), 100019. https://doi.org/10.1016/j.multra.2022.100019 doi: 10.1016/j.multra.2022.100019
[22]	J. Qiu, K. Huang, J. Hawkins, The taxi sharing practices: matching, routing and pricing methods, Multimodal Transp., 1 (2022), 100003. https://doi.org/10.1016/j.multra.2022.100003 doi: 10.1016/j.multra.2022.100003
[23]	A. T. Palma, V. Bogorny, B. Kuijpers, L. O. Alvares, A clustering-based approach for discovering interesting places in trajectories, in Proceedings of the 2008 ACM Symposium on Applied Computing, ACM, Fortaleza, Brazil, (2008), 863-868. https://doi.org/10.1145/1363686.1363886
[24]	L. Grady, E. L. Schwartz, Isoperimetric graph partitioning for image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 28 (2006), 469-475. https://doi.org/10.1109/TPAMI.2006.57 doi: 10.1109/TPAMI.2006.57
[25]	L. Zhao, G. Shi, J. Yang, An adaptive hierarchical clustering method for ship trajectory data based on DBSCAN algorithm, in 2017 IEEE 2nd International Conference on Big Data Analysis (ICBDA), IEEE, Beijing, China, (2017), 329-336. https://doi.org/10.1109/ICBDA.2017.8078834
[26]	Y. Xi, D. Huang, Y. Yuan, Z. Liu, K. Anish, N. Zheng, Improved dynamic time warping algorithm for bus route trajectory curve fitting, J. Transp. Eng., 147 (2021), 04021044. https://doi.org/10.1061/JTEPBS.0000544 doi: 10.1061/JTEPBS.0000544
[27]	R. F. Ibrahim, A recommendation system based on clustering and classification for optimal trajectory analysis, PhD thesis, Carleton University, 2019. https://doi.org/10.22215/etd/2019-13400
[28]	M. Khashei, M. Bijari, A novel hybridization of artificial neural networks and ARIMA models for time series forecasting, Appl. Soft Comput., 11 (2011), 2664-2675. https://doi.org/10.1016/j.asoc.2010.10.015 doi: 10.1016/j.asoc.2010.10.015
[29]	Y. Yuan, W. Zhang, X. Yang, Y. Liu, Z. Liu, W. Wang, Traffic state classification and prediction based on trajectory data, J. Intell. Transp. Syst., 2021 (2021), 1-15. https://doi.org/10.1080/15472450.2021.1955210 doi: 10.1080/15472450.2021.1955210
[30]	V. Hodge, J. Austin, A survey of outlier detection methodologies, Artif. Intell. Rev., 22 (2004), 85-126. https://doi.org/10.1023/B:AIRE.0000045502.10941.a9 doi: 10.1023/B:AIRE.0000045502.10941.a9
[31]	S. Y. Huang, Y. N. Huang, Network traffic anomaly detection based on growing hierarchical SOM, in 2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), IEEE, Budapest, Hungary, (2013), 1-2. https://doi.org/10.1109/DSN.2013.6575338
[32]	A. S. da Silva, J. A. Wickboldt, L. Z. Granville, A. Schaeffer-Filho, ATLANTIC: A framework for anomaly traffic detection, classification, and mitigation in SDN, in NOMS 2016-2016 IEEE/IFIP Network Operations and Management Symposium, IEEE, Istanbul, Turkey, (2016), 27-35. https://doi.org/10.1109/NOMS.2016.7502793
[33]	K. K. Santhosh, D. P. Dogra, P. P. Roy, Anomaly detection in road traffic using visual surveillance: A survey, ACM Comput. Surv. (CSUR), 53 (2020), 1-26. https://doi.org/10.1145/3417989 doi: 10.1145/3417989
[34]	S. Chawla, Y. Zheng, J. Hu, Inferring the root cause in road traffic anomalies, in 2012 IEEE 12th International Conference on Data Mining, IEEE, Brussels, Belgium, (2012), 141-150. https://doi.org/10.1109/ICDM.2012.104
[35]	P. R. Lei, A framework for anomaly detection in maritime trajectory behavior, Knowl. Inf. Syst., 47 (2016), 189-214. https://doi.org/10.1007/s10115-015-0845-4 doi: 10.1007/s10115-015-0845-4
[36]	J. Wang, I. C. Paschalidis, Statistical traffic anomaly detection in time-varying communication networks, IEEE Trans. Control Network Syst., 2 (2014), 100-111. https://doi.org/10.1109/TCNS.2014.2378631 doi: 10.1109/TCNS.2014.2378631
[37]	E. M. Knorr, R. T. Ng, V. Tucakov, Distance-based outliers: Algorithms and applications, VLDB J., 8 (2000), 237-253. https://doi.org/10.1007/s007780050006 doi: 10.1007/s007780050006
[38]	E. M. Knorr, R.T. Ng, Finding intensional knowledge of distance-based outliers, in Vldb, 99 (1999), 211-222.
[39]	J. G. Lee, J. Han, X. Li, Trajectory outlier detection: A partition-and-detect framework, in 2008 IEEE 24th International Conference on Data Engineering, IEEE, Cancun, Mexico, (2008), 140-149. https://doi.org/10.1109/ICDE.2008.4497422
[40]	S. A. Ahmed, D. P. Dogra, S. Kar, P. P. Roy, Surveillance scene representation and trajectory abnormality detection using aggregation of multiple concepts, Expert Syst. Appl., 101 (2018), 43-55. https://doi.org/10.1016/j.eswa.2018.02.013 doi: 10.1016/j.eswa.2018.02.013
[41]	Y. Ge, H. Xiong, Z. Zhou, H. Ozdemir, J. Yu, K. C. Lee, Top-eye: top-k evolving trajectory outlier detection, in Proceedings of the 19th ACM International Conference on Information and Knowledge Management, ACM, Toronto, Canada, (2010), 1733-1736. https://doi.org/10.1145/1871437.1871716
[42]	W. Qin, J. Tang, C. Lu, S. Lao, A trajectory abnormal detection method based on segmentation and clustering, in Journal of Physics: Conference Series, 2010 (2021), 012188. https://doi.org/10.1088/1742-6596/2010/1/012188
[43]	X. Zhao, Y. Rao, J. Cai, W. Ma, Abnormal trajectory detection based on a sparse subgraph, IEEE Access, 8 (2020), 29987-30000. https://doi.org/10.1109/ACCESS.2020.2972299 doi: 10.1109/ACCESS.2020.2972299
[44]	Z. Ding, M. Fei, An anomaly detection approach based on isolation forest algorithm for streaming data using sliding window, IFAC Proc. Vol., 46 (2013), 12-17. https://doi.org/10.3182/20130902-3-CN-3020.00044 doi: 10.3182/20130902-3-CN-3020.00044
[45]	D. Xu, Y. Wang, Y. Meng, Z. Zhang, An improved data anomaly detection method based on isolation forest, in 2017 10th International Symposium on Computational Intelligence and Design (ISCID), IEEE, Hangzhou, China, 2 (2017), 287-291. https://doi.org/10.1109/ISCID.2017.202
[46]	Z. Cheng, C. Zou, J. Dong, Outlier detection using isolation forest and local outlier factor, in Proceedings of the Conference on Research in Adaptive and Convergent Systems, ACM, Chongqing, China, (2019), 161-168. https://doi.org/10.1145/3338840.3355641

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)