Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control

Connor Riley; Pascal van Hentenryck; Enpeng Yuan

IJCAI 2020poster0 citations

Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control

Connor Riley, Pascal van Hentenryck, Enpeng Yuan

Abstract

This paper considers the dispatching of large-scale real-time ride-sharing systems to address congestion issues faced by many cities. The goal is to serve all customers (service guarantees) with a small number of vehicles while minimizing waiting times under constraints on ride duration. This paper proposes an end-to-end approach that tightly integrates a state-of-the-art dispatching algorithm, a machine-learning model to predict zone-to-zone demand over time, and a model predictive control optimization to relocate idle vehicles. Experiments using historic taxi trips in New York City indicate that this integration decreases average waiting times by about 30% over all test cases and reaches close to 55% on the largest instances for high-demand zones.

Constraints and SAT: Constraint OptimizationMachine Learning Applications: OtherPlanning and Scheduling: Planning and SchedulingUncertainty in AI: Sequential Decision Making

BibTeX

@inproceedings{ijcai2020p609,
  title     = {Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control},
  author    = {Riley, Connor and van Hentenryck, Pascal and Yuan, Enpeng},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {4417--4423},
  year      = {2020},
  month     = {7},
  note      = {Special track on AI for CompSust and Human well-being},
  doi       = {10.24963/ijcai.2020/609},
  url       = {https://doi.org/10.24963/ijcai.2020/609},
}