Offline Vehicle Routing Problem with Online Bookings

Published:

Recommended citation: Sivagnanam, A., Kadir, SU., Mukhopadhyay, A., Pugliese, P., Dubey, A., Samaranayake, S., & Laszka, A. (2022, July) Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (pp. 3933-3939)

📌 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 image


📝 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]