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

• URL: http://arxiv.org/abs/2003.10942v1
• Date: Tue, 24 Mar 2020 16:05:25 GMT
• Title: Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control
• Authors: Connor Riley and Pascal Van Hentenryck and Enpeng Yuan
• Abstract summary: 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 with a small number of vehicles while minimizing waiting times under constraints on ride duration. Experiments using historic taxi trips in New York City indicate that this integration decreases average waiting times by about 30% over all test cases.
• Score: 22.894789405660816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Scalable Transit Delay Prediction at City Scale: A Systematic Approach with Multi-Resolution Feature Engineering and Deep Learning [1.065661841579261]
  Most existing delay prediction systems handle only a few routes, depend on hand-crafted features, and offer little guidance on how to design a reusable architecture.<n>We present a city-scale prediction pipeline that combines multi-resolution feature engineering, dimensionality reduction, and deep learning.<n>A global LSTM with cluster-aware features achieves the best trade-off between accuracy and efficiency, outperforming transformer models by 18 52% to 52%.
  arXiv  Detail & Related papers  (2026-01-26T14:30:50Z)
• Scalable Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantee: A Constrained Mean-Field Reinforcement Learning Approach [42.070187224580344]
  We introduce continuous-state mean-field control (MFC) and mean-field reinforcement learning (MFRL) models that employ continuous vehicle repositioning actions.<n>MFC and MFRL offer scalable solutions by modeling each vehicle's behavior through interaction with the vehicle distribution, rather than with individual vehicles.<n>Our approach scales to tens of thousands of vehicles, with training times comparable to the decision time of a single linear programming rebalancing.
  arXiv  Detail & Related papers  (2025-03-31T15:00:11Z)
• OPUS: Occupancy Prediction Using a Sparse Set [64.60854562502523]
  We present a framework to simultaneously predict occupied locations and classes using a set of learnable queries. OPUS incorporates a suite of non-trivial strategies to enhance model performance. Our lightest model achieves superior RayIoU on the Occ3D-nuScenes dataset at near 2x FPS, while our heaviest model surpasses previous best results by 6.1 RayIoU.
  arXiv  Detail & Related papers  (2024-09-14T07:44:22Z)
• GPT-Augmented Reinforcement Learning with Intelligent Control for Vehicle Dispatching [82.19172267487998]
  GARLIC: a framework of GPT-Augmented Reinforcement Learning with Intelligent Control for vehicle dispatching. This paper introduces GARLIC: a framework of GPT-Augmented Reinforcement Learning with Intelligent Control for vehicle dispatching.
  arXiv  Detail & Related papers  (2024-08-19T08:23:38Z)
• DAISY: Data Adaptive Self-Supervised Early Exit for Speech Representation Models [55.608981341747246]
  We introduce Data Adaptive Self-Supervised Early Exit (DAISY), an approach that decides when to exit based on the self-supervised loss. Our analysis on the adaptivity of DAISY shows that the model exits early (using fewer layers) on clean data while exits late (using more layers) on noisy data.
  arXiv  Detail & Related papers  (2024-06-08T12:58:13Z)
• End-to-end Autonomous Driving: Challenges and Frontiers [45.391430626264764]
  We provide a comprehensive analysis of more than 270 papers, covering the motivation, roadmap, methodology, challenges, and future trends in end-to-end autonomous driving. We delve into several critical challenges, including multi-modality, interpretability, causal confusion, robustness, and world models, amongst others. We discuss current advancements in foundation models and visual pre-training, as well as how to incorporate these techniques within the end-to-end driving framework.
  arXiv  Detail & Related papers  (2023-06-29T14:17:24Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  Vehicle Re-Identification is one of the key elements in city-scale vehicle analytics systems. Many state-of-the-art solutions for vehicle re-id mostly focus on improving the accuracy on existing re-id benchmarks and often ignore computational complexity. We propose a simple yet effective hybrid solution empowered by self-supervised training which only uses a single network during inference time.
  arXiv  Detail & Related papers  (2022-05-16T12:14:42Z)
• A Deep-Learning Based Optimization Approach to Address Stop-Skipping Strategy in Urban Rail Transit Lines [0.0]
  We introduce an advanced data-driven optimization approach to determine the optimal stop-skip pattern in urban rail transit lines. We employ a Long Short-Term Memory (LSTM) deep learning model to predict the station-level demand rates for the peak hour. Considering the exponential nature of the problem, we propose an Ant Colony Optimization technique to solve the problem in a desirable amount of time.
  arXiv  Detail & Related papers  (2021-09-17T23:52:19Z)
• Estimating the Robustness of Public Transport Systems Using Machine Learning [62.997667081978825]
  Planning public transport systems is a highly complex process involving many steps. Integrating robustness from a passenger's point of view makes the task even more challenging. In this paper, we explore a new way of such a scenario-based robustness approximation by using methods from machine learning.
  arXiv  Detail & Related papers  (2021-06-10T05:52:56Z)
• A Deep Value-network Based Approach for Multi-Driver Order Dispatching [55.36656442934531]
  We propose a deep reinforcement learning based solution for order dispatching. We conduct large scale online A/B tests on DiDi's ride-dispatching platform. Results show that CVNet consistently outperforms other recently proposed dispatching methods.
  arXiv  Detail & Related papers  (2021-06-08T16:27:04Z)
• Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms [57.21078336887961]
  Large ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day. We propose a unified value-based dynamic learning framework (V1D3) for tackling both tasks.
  arXiv  Detail & Related papers  (2021-05-18T19:22:24Z)
• H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch [9.35511513240868]
  H-TD2 is a model-free, adaptive decision-making algorithm to coordinate a large fleet of automated taxis in a dynamic urban environment. We derive a regret bound and design the trigger condition between the two behaviors to explicitly control the trade-off between computational complexity and the individual taxi policy's bounded sub-optimality. Unlike recent reinforcement learning dispatch methods, this policy estimation is adaptive and robust to out-of-training domain events.
  arXiv  Detail & Related papers  (2021-05-05T15:42:31Z)
• Real-time and Large-scale Fleet Allocation of Autonomous Taxis: A Case Study in New York Manhattan Island [14.501650948647324]
  Traditional models fail to efficiently allocate the available fleet to deal with the imbalance of supply (autonomous taxis) and demand (trips) We employ a Constrained Multi-agent Markov Decision Processes (CMMDP) to model fleet allocation decisions. We also leverage a Column Generation algorithm to guarantee the efficiency and optimality in a large scale.
  arXiv  Detail & Related papers  (2020-09-06T16:00:15Z)
• BusTime: Which is the Right Prediction Model for My Bus Arrival Time? [3.1761486589684975]
  This paper tries to fill this gap by proposing a general and practical evaluation framework for analysing various widely used prediction models. In particular, this framework contains a raw bus GPS data pre-processing method that needs much less number of input data points. We also present preliminary results for city managers by analysing the practical strengths and weaknesses in both training and predicting stages of commonly used prediction models.
  arXiv  Detail & Related papers  (2020-03-20T17:03:36Z)
• Proposing a Model for Predicting Passenger Origin-Destination in Online Taxi-Hailing Systems [0.0]
  We present a model designed to forecast the origin and destination of travels within a specified time window. We employ K-means clustering in a four-dimensional space with a maximum cluster size constraint for origin and destination zones. A comparison of our results with existing models reveals that our proposed model achieves a 5-7% lower mean absolute percentage error (MAPE) for 1-hour time windows and a 14% lower MAPE for 30-minute time windows.
  arXiv  Detail & Related papers  (2019-10-17T20:19:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.