Offline Vehicle Routing Problem with Online Bookings

📌 Key Contributions

• Focus on a real-world paratransit operations where riders book trips in advance with time flexibility but expect tight pickup time windows at booking time
• Introduced a novel problem formulation: the Offline Vehicle Routing Problem with Online Bookings, which blends the scalability of Offline VRP with the real-time responsiveness of Dynamic VRP
• Developed a Deep Reinforcement Learning–based policy that learns to assign optimal time windows under demand uncertainty and booking-time constraints
• Integrated an anytime VRP solver to incrementally refine and improve route plans between bookings, enabling better long-term efficiency
• Achieved 20–40% cost reduction over baseline methods with naive window assignments, as demonstrated through extensive experiments on real-world paratransit of Chattanooga

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]