Data-Driven Robust Taxi Dispatch under Demand Uncertainties

Fei Miao, Shuo Han, Shan Lin, Qian Wang, John A. Stankovic, Abdeltawab Hendawi, Desheng Zhang, Tian He, George J. Pappas

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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.

Original languageEnglish (US)
Article number8105899
Pages (from-to)175-191
Number of pages17
JournalIEEE Transactions on Control Systems Technology
Volume27
Issue number1
DOIs
StatePublished - Jan 2019

Bibliographical note

Funding Information:
Manuscript received June 13, 2017; accepted September 24, 2017. Date of publication November 13, 2017; date of current version December 12, 2018. Manuscript received in final form October 20, 2017. This work was supported in part by NSF through the project “CPS: Synergy: Collaborative Research: Multiple-Level Predictive Control of Mobile Cyber Physical Systems With Correlated Context” under Project CPS-1239152 and Project CNS-1239224 and in part by TerraSwarm. This paper was presented in part at the 54th IEEE Conference on Decision Control, Osaka, Japan, December 2015 [19]. Recommended by Associate Editor A. Serrani. (Corresponding author: Fei Miao.) F. Miao is with the Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 USA (e-mail: fei.miao@uconn.edu).

Publisher Copyright:
© 1993-2012 IEEE.

Keywords

  • computationally tractable approximation
  • data-driven robust optimization
  • demand uncertainties
  • probabilistic guarantee
  • resource allocation
  • taxi dispatch framework

Fingerprint

Dive into the research topics of 'Data-Driven Robust Taxi Dispatch under Demand Uncertainties'. Together they form a unique fingerprint.

Cite this