Offline Vehicle Routing Problem with Online Bookings
Published:
📌 Key Contributions
Introduced a novel problem formulation Offline Vehicle Routing Problem with Online Bookings that tackles combine challenges of handling large number requests like Offline VRP and real-time decision-making like Dynamic VRP.
The problem is inspired by operational needs in paratransit services, where riders book trips a day in advance but expect confirmed narrow pickup time intervals during the booking call. The model captures this hybrid setting by integrating online decisions with offline optimization.
Developed a deep reinforcement learning (RL) approach that learns an optimal policy to assign tight pickup windows under uncertainty.
Augmented the RL policy with an anytime VRP solver that runs between trip bookings, continuously improving partial route plans.
Our extensive experiments using real-world data demonstrate up to 20-40% cost reduction compared to baseline methods with naive window assignment.
Highlevel overview of Solution Approach
📝 Publication
This research has been published in: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)
“Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit” [IJCAI22]
💻 Code & Data
The source code and anonymized dataset used in this work are publicly available: [Code & Data]