Data-Driven Robust Taxi Dispatch Under Demand Uncertainties
- 13 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control Systems Technology
- Vol. 27 (1), 175-191
- https://doi.org/10.1109/tcst.2017.2766042
Abstract
In modern taxi networks, large amounts of taxi occupancy status and location data are collected from networked in-vehicle sensors in realtime. They provide knowledge of system models on passenger demand and mobility patterns for efficient taxi dispatch and coordination strategies. Such approaches face new challenges: how to deal with uncertainties of predicted customer demand while fulfilling the system's performance requirements, including minimizing taxis' total idle mileage and maintaining service fairness across the whole city; how to formulate a computationally tractable problem. To address this problem, we develop a data-driven robust taxi dispatch framework to consider spatial-temporally correlated demand uncertainties. The robust vehicle dispatch problem we formulate is concave in the uncertain demand and convex in the decision variables. Uncertainty sets of random demand vectors are constructed from data based on theories in hypothesis testing, and provide a desired probabilistic guarantee level for the performance of robust taxi dispatch solutions. We prove equivalent computationally tractable forms of the robust dispatch problem using the minimax theorem and strong duality. Evaluations on four years of taxi trip data for New York City show that by selecting a probabilistic guarantee level at 75%, the average demand-supply ratio error is reduced by 31.7%, and the average total idle driving distance is reduced by 10.13% or about 20 million miles annually, compared with nonrobust dispatch solutions.Keywords
Other Versions
Funding Information
- National Science Foundation (CPS-1239152, CNS-1239224)
- TerraSwarm
This publication has 25 references indexed in Scilit:
- Taxi dispatch with real-time sensing data in metropolitan areasPublished by Association for Computing Machinery (ACM) ,2015
- Online Cruising Mile Reduction in Large-Scale Taxicab NetworksIEEE Transactions on Parallel and Distributed Systems, 2014
- Robotic load balancing for mobility-on-demand systemsThe International Journal of Robotics Research, 2012
- Evaluation of traffic data obtained via GPS-enabled mobile phones: The Mobile Century field experimentTransportation Research Part C: Emerging Technologies, 2010
- A Traffic Model for Velocity Data AssimilationApplied Mathematics Research eXpress, 2010
- The optimal dispatching of taxis under congestion: A rolling horizon approachJournal of Advanced Transportation, 2006
- Measuring the robustness of a resource allocationIEEE Transactions on Parallel and Distributed Systems, 2004
- Taxi Dispatch System Based on Current Demands and Real-Time Traffic ConditionsTransportation Research Record: Journal of the Transportation Research Board, 2004
- An improved approach for constrained robust model predictive controlAutomatica, 2002
- Robust Convex OptimizationMathematics of Operations Research, 1998