Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, Abhishek Dubey, Samitha Samaranayake, Aron Laszka
31st International Joint Conference on Artificial Intelligence (IJCAI) 2022
Paratransit services for elderly and disabled passengers require high flexibility in response to real-time requests while maintaining operational efficiency. This work is novel because it bridges the gap between offline and online routing problems with practical constraints on pickup windows. The combination of optimization and learning approaches enables the system to adapt to dynamic demand while respecting the transportation agency's operational requirements.
This work addresses the offline vehicle routing problem with online bookings for paratransit services, where pickup windows are selected at the time of booking rather than predetermined. The authors propose a formulation combining an offline vehicle routing model with an online bookings model, and present computational approaches including an anytime algorithm with reinforcement learning and a Markov decision process formulation.
The proposed methods were evaluated using real-world paratransit data from Chattanooga, showing that the anytime algorithm with learning outperforms baseline approaches. The reinforcement learning approach effectively learns policies that balance responsiveness to immediate requests with long-term efficiency considerations. The experimental results demonstrate significant improvements in cost reduction and robustness when environmental conditions change dynamically.
@inproceedings{sivagnanam2022offline,
author = {Sivagnanam, Amutheezan and Kadir, Salah Uddin and Mukhopadhyay, Ayan and Pugliese, Philip and Dubey, Abhishek and Samaranayake, Samitha and Laszka, Aron},
booktitle = {31st International Joint Conference on Artificial Intelligence (IJCAI)},
title = {Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit},
year = {2022},
acceptance = {15},
month = {jul},
abstract = {Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. Based on discussions with public transit agencies, we identify a real-world problem that is not addressed by existing formulations: booking trips with flexible pickup windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is often required in paratransit service settings, where passengers typically book trips for the next day over the phone. To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests—similar to offline VRPs—but must abide by strict constraints on running time—similar to online VRPs. To solve this problem, we propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions. Based on a paratransit dataset obtained from our partner transit agency, we demonstrate that our novel formulation and computational approach lead to significantly better outcomes in this service setting than existing algorithms.},
contribution = {colab},
preprint = {https://arxiv.org/abs/2204.11992},
keywords = {vehicle routing, online optimization, paratransit services, reinforcement learning, demand-responsive transport},
month_numeric = {7}
}