Dynamic balance between demand-and-supply of urban taxis over trajectories

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.