Urban taxi serves as an irreplaceable tool in public transportation systems. The balancing of demand-and-supply can be of significant social benefit, for which the equilibrium method for urban taxis, especially with dynamic trip demands, is not well studied yet. In this paper, we formally define the equilibrium problem and propose a coarse-grained dynamic balancing algorithm. It efficiently evaluates the trip demand distribution pattern and schedules supplies to more unbalanced regions. We first propose a density-based blocking algorithm to detect regions that are with more travel demands. A trip demand merging strategy is then proposed, which checks the correlation of trip demands to merge the trips into ones. To reduce the computation load, a lazy trip correlation strategy is devised to speed up the merging process. By calculating the defined balance factor, a scheduling algorithm is proposed to realize the trip merge and supply translocation based balancing approach. We evaluated our approach using a month of global positioning system (GPS) trajectories generated by 13,000 taxis of Shanghai. By learning the spatiotemporal distribution of historical taxi demand-and-supplies, we simulated an inflated trip demand platform. Tested on this platform with extensive experiments, the proposed approach demonstrates its effectiveness and scalability.
Citation: Mingyang Liu, Junhao Han, Yushan Mei, Yuguang Li. Dynamic balance between demand-and-supply of urban taxis over trajectories[J]. Mathematical Biosciences and Engineering, 2022, 19(1): 1041-1057. doi: 10.3934/mbe.2022048
Urban taxi serves as an irreplaceable tool in public transportation systems. The balancing of demand-and-supply can be of significant social benefit, for which the equilibrium method for urban taxis, especially with dynamic trip demands, is not well studied yet. In this paper, we formally define the equilibrium problem and propose a coarse-grained dynamic balancing algorithm. It efficiently evaluates the trip demand distribution pattern and schedules supplies to more unbalanced regions. We first propose a density-based blocking algorithm to detect regions that are with more travel demands. A trip demand merging strategy is then proposed, which checks the correlation of trip demands to merge the trips into ones. To reduce the computation load, a lazy trip correlation strategy is devised to speed up the merging process. By calculating the defined balance factor, a scheduling algorithm is proposed to realize the trip merge and supply translocation based balancing approach. We evaluated our approach using a month of global positioning system (GPS) trajectories generated by 13,000 taxis of Shanghai. By learning the spatiotemporal distribution of historical taxi demand-and-supplies, we simulated an inflated trip demand platform. Tested on this platform with extensive experiments, the proposed approach demonstrates its effectiveness and scalability.
| [1] | D. Liu, S. F. Cheng, Y. Yang, Density peaks clustering approach for discovering demand hot spots in city-scale taxi fleet dataset, in 2015 IEEE 18th IEEE International Conference on Intelligent Transportation Systems, IEEE, (2015), 1831–1836. doi: 10.1109/ITSC.2015.297. |
| [2] |
S. Ma, Y. Zheng, O. Wolfson, Real-time city-scale taxi ridesharing, IEEE Trans. Knowl. Data Eng., 27 (2015), 1782–1795. doi: 10.1109/TKDE.2014.2334313. doi: 10.1109/TKDE.2014.2334313
|
| [3] | J. Yuan, Y. Zheng, X. Xie, G. Sun, Driving with knowledge from the physical world, in Proceedings of the 17th SIGKDD Conference on Knowledge Discovery and Data Mining, KDD, (2011), 316–324. doi: 10.1145/2020408.2020462. |
| [4] |
X. Liu, L. Gong, Y. Gong, Y. Liu, Revealing travel patterns and city structure with taxi trip data, J. Transp. Geogr., 43 (2013), 78–90. doi: 10.1016/j.jtrangeo.2015.01.016. doi: 10.1016/j.jtrangeo.2015.01.016
|
| [5] | C. Yang, E. J. Gonzales, Modeling taxi demand and supply in New York city using large-scale taxi GPS data, in Seeing Cities Through Big Data, Springer, (2017), 405–425. doi: 10.1007/978-3-319-40902-3_22. |
| [6] |
C. Yang, E. J. Gonzales, Modeling taxi trip demand by time of day in New York city, Transp. Res. Rec. J. Transp. Res. Board, 2429 (2014), 110–120. doi: 10.3141/2429-12. doi: 10.3141/2429-12
|
| [7] |
C. Kang, K. Qin, Understanding operation behaviors of taxicabs in cities by matrix factorization, Comput. Environ. Urban Syst., 60 (2016), 79–88. doi: 10.1016/j.compenvurbsys.2016.08.002 doi: 10.1016/j.compenvurbsys.2016.08.002
|
| [8] | Y. Huang, J. W. Powell, Detecting regions of disequilibrium in taxi services under uncertainty, in 20th International Conference on Advances in Geographic Information Systems, (2012), 139–148. doi: 10.1145/2424321.2424340. |
| [9] | Q. Zhou, J. Zhang, J. Li, S. Wang, Discovering regional taxicab demand based on distribution modeling from trajectory data, in 2014 IEEE 17th International Conference on Computational Science and Engineering, IEEE, (2014), 1605–1610. doi: 10.1109/CSE.2014.296. |
| [10] | D. Shao, W. Wu, S. Xiang, Y. Lu, Estimating taxi demand-supply level using taxi trajectory data stream, in 2015 IEEE International Conference on Data Mining Workshop, IEEE, (2015), 407–413. doi: 10.1109/ICDMW.2015.250. |
| [11] |
H. Yang, S. C. Wong, A network model of urban taxi services, Transp. Res. Part B Methodol., 32 (1998), 235–246. doi: 10.1016/S0191-2615(97)00042-8. doi: 10.1016/S0191-2615(97)00042-8
|
| [12] |
H. Yang, S. C. Wong, K. I. Wong, Demand-supply equilibrium of taxi services in a network under competition and regulation, Transp. Res. Part B Methodol., 36 (2002), 799–819. doi: 10.1016/S0191-2615(01)00031-5. doi: 10.1016/S0191-2615(01)00031-5
|
| [13] |
H. Yang, T. Yang, Equilibrium properties of taxi markets with search frictions, Transp. Res. Part B Methodol., 45 (2011), 696–713. doi: 10.1016/j.trb.2011.01.002. doi: 10.1016/j.trb.2011.01.002
|
| [14] |
F. He, Z. J. Shen, Modeling taxi services with smartphone-based e-hailing applications, Transp. Res. Part C Emerging Technol., 58 (2015), 93–106. doi: 10.1016/j.trc.2015.06.023. doi: 10.1016/j.trc.2015.06.023
|
| [15] | F. C. Choo, M. C. Chan, A. L. Ananda, L. S. Peh, A distributed taxi advisory system, in 2012 12th International Conference on ITS Telecommunications, IEEE, (2012), 199–204. doi: 10.1109/ITST.2012.6425165. |
| [16] | S. Ma, Y. Zheng, O. Wolfson, T-share: a large-scale dynamic taxi ridesharing service, in 2013 IEEE 29th IEEE International Conference on Data Engineering, IEEE, (2013), 410–421. doi: 10.1109/ICDE.2013.6544843. |
| [17] |
L. Rayle, D. Dai, N. Chan, R. Cervero, S. Shaheen, Just a better taxi? A survey-based comparison of taxis, transit, and ridesourcing services in San Francisco, Transp. Policy, 45 (2016), 168–178. doi: 10.1016/j.tranpol.2015.10.004. doi: 10.1016/j.tranpol.2015.10.004
|
| [18] |
J. Yuan, Y. Zheng, X. Xie, G. Sun, T-Drive: enhancing driving directions with taxi drivers' intelligence, IEEE Trans. Knowl. Data Eng., 25 (2013), 220–232. doi: 10.1109/TKDE.2011.200. doi: 10.1109/TKDE.2011.200
|
| [19] | J. Yuan, Y. Zheng, L. Zhang, X. Xie, G. Sun, Where to find my next passenger, in ACM Conference on Ubiquitous Computing, (2011), 109–118. doi: 10.1145/2030112.2030128. |
| [20] |
N. J. Yuan, Y. Zheng, L. Zhang, X. Xie, T-finder: a recommender system for finding passengers and vacant taxis, IEEE Trans. Knowl. Data Eng., 25 (2013), 2390–2403. doi: 10.1109/TKDE.2012.153. doi: 10.1109/TKDE.2012.153
|
| [21] | J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, et al., T-drive: driving directions based on taxi trajectories, in ACM Sigspatial International Symposium on Advances in Geographic Information Systems, San Jose, (2010), 99–108. doi: 10.1145/1869790.1869807. |
| [22] |
P. Xia, L. Zhang, F. Li, Learning similarity with cosine similarity ensemble, Inf. Sci., 307 (2013), 39–52. doi: 10.1016/j.ins.2015.02.024. doi: 10.1016/j.ins.2015.02.024
|
Figures(10) / Tables(2)
Mingyang Liu, Junhao Han, Yushan Mei, Yuguang Li. Dynamic balance between demand-and-supply of urban taxis over trajectories[J]. Mathematical Biosciences and Engineering, 2022, 19(1): 1041-1057. doi: 10.3934/mbe.2022048
DownLoad: