Optimization-driven Demand Prediction Framework for Suburban Dynamic Demand-Responsive Transport Systems

Louis Zigrand, Roberto Wolfler Calvo, Emiliano Traversi, Pegah AlizadehIJCAI 2023 · DOI

TL;DR

This paper introduces an "optimization-driven" demand prediction framework for dynamic demand-responsive transport (DRT) systems, specifically tailored for sparse suburban areas. By integrating a machine learning-based demand prediction with a Dial-a-Ride Problem solver, they improve the efficiency of DRT services, leading to a 3.5% increase in the average insertion rate of travel requests.

What Problem Does This Paper Address?

Demand-Responsive Transport (DRT) systems offer flexible public transportation, adapting routes to real-time demand. However, current DRT planning often relies on myopic heuristics that don't account for future demand, leading to suboptimal route planning. This is particularly challenging in suburban areas, which suffer from sparse and heterogeneous travel demand, making accurate prediction difficult. The paper aims to bridge this gap by developing a demand prediction framework that explicitly considers the constraints and objectives of the underlying optimization problem (the Dial-a-Ride Problem) to improve DRT service efficiency.

Methods

The core of the paper is the development of an "optimization-driven" demand prediction framework. This involves:

  • Data Aggregation: To combat data sparsity, historical travel requests are aggregated into "Aggregated Travel Requests" based on geographical (AD) and temporal (AT) thresholds. This creates clusters of similar origin-destination-time slots.
  • Demand Prediction Framework: Two machine learning models, a Moving Average (MA) and a Long Short-Term Memory (LSTM) network, are used to predict the occurrence of these aggregated travel requests for the next operational day. The LSTM model is enhanced with temporal features and a custom trainable threshold layer.
  • Integration with Optimization: The predicted travel requests are then fed into a Dynamic Dial-a-Ride Problem (DaRP) solver. This solver uses a combinatorial Benders decomposition approach. The key idea is to use the predicted requests to "saturate" driver routes initially, creating slack for actual incoming requests.
  • Look-ahead Offline Optimization: The proposed method involves optimizing initial driver plannings by considering predicted travel requests. These predicted requests are treated as optional, and their inclusion aims to make the initial routes more flexible. After the initial planning, the system simulates the arrival of actual historical requests and reports the insertion rate.

Datasets

The paper utilizes historical travel request data from a Demand-Responsive Transport service managed by Padam Mobility in suburban areas. This dataset is characterized by its sparsity and heterogeneity, contrasting with larger, denser datasets often found in urban transportation research. The authors do not introduce a new benchmark dataset but rather analyze the specific challenges posed by their real-world suburban DRT data.

Key Insights and Ideas

  • Sparsity is a Major Hurdle: Even with aggregation, the resulting "Aggregated Travel Requests" matrix exhibits significant sparsity (over 98%), highlighting the inherent difficulty in modeling suburban demand.
  • Optimization Constraints Shape Prediction: The parameters for data aggregation (AD and AT) are not chosen solely for prediction accuracy but are constrained by the requirements of the Dial-a-Ride Problem solver, emphasizing the "optimization-driven" aspect.
  • Look-ahead Planning Improves Flexibility: By proactively incorporating predicted travel requests into initial driver plannings, DRT systems can create more flexible routes, allowing for better insertion of actual, real-time requests.
  • LSTM Outperforms MA for Optimization: While MA might detect more requests, the LSTM model provides better probability estimates for the predicted requests, which is crucial for its integration into the optimization objective function.

Key Results

  • The proposed "Look-ahead" approach, when integrated with a DaRP solver, achieved an average insertion rate of 60% for travel requests.
  • This represents a 3.5% relative improvement compared to the traditional "Total Duration of the Rides" optimization approach, which achieved 58%.
  • The theoretical upper bound for the insertion rate, as determined by their solver, is 70%.
  • The paper demonstrates that even with noisy predictions, the top-ranked predicted travel requests are more likely to be accurate, making the approach viable for optimization.

Limitations and Future Work

  • Data Sparsity Remains: Despite aggregation, the sparsity of the demand data remains a significant challenge.
  • Offline Optimization Focus: The current work focuses on offline optimization at the start of the day. The authors acknowledge that the overall numerical quality of predictions might seem low, but the focus is on improving the optimization process.
  • Future Work:
    • Develop a new online insertion policy that leverages the optimization performed at the start of the day.
  • Improve the Demand Prediction Framework itself to provide even more accurate and useful predictions for the solver.

Summary updated

BibTeX
@inproceedings{zigrand2023optimization,
  author = {Louis Zigrand and Roberto Wolfler Calvo and Emiliano Traversi and Pegah Alizadeh},
  title = {{Optimization-driven Demand Prediction Framework for Suburban Dynamic Demand-Responsive Transport Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/703},
}

Loading related content...

Figure