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

2020/03/24 by Riley, Connor, Van Hentenryck, Pascal, Yuan, Enpeng · 2 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2003.10942

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.

Cited by

• RAST-MoE-RL: A Regime-Aware Spatio-Temporal MoE Framework for Deep Reinforcement Learning in Ride-Hailing
• Spatio-Temporal Demand Prediction for Food Delivery Using Attention-Driven Graph Neural Networks

Related

• Learning Model-Based Vehicle-Relocation Decisions for Real-Time Ride-Sharing: Hybridizing Learning and Optimization
• Learning Model Predictive Controllers for Real-Time Ride-Hailing Vehicle Relocation and Pricing Decisions
• Large Scale Real-time Ridesharing with Service Guarantee on Road Networks
• MOVI: A Model-Free Approach to Dynamic Fleet Management
• Robo-Taxi Fleet Coordination with Accelerated High-Capacity Ridepooling