# Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit

**Authors:** Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, Abhishek Dubey, Samitha Samaranayake, Aron Laszka  
**arXiv:** [2204.11992](https://arxiv.org/abs/2204.11992)  
**Date:** 2022-04-25  
**Summary page:** https://www.summarizepaper.com/en/paper/2204.11992v2/

## Key points

- Vehicle routing problems (VRPs) categorized into offline VRPs and online VRPs
- Need for flexible pickup windows in advance and tight pickup windows at booking time in paratransit service settings
- Introduction of offline vehicle routing problem with online bookings to address the gap between offline and online problems
- Computational challenges in handling large request sets while adhering to strict constraints on running time
- Proposed unique computational approach combining anytime algorithm with learning-based policy for real-time decisions
- Empirical analysis using Chattanooga, TN public transit agency dataset demonstrating efficacy of novel formulation and computational approach
- Outperformance of existing algorithms in addressing intricacies of paratransit service settings

## Summary

In the realm of vehicle routing problems (VRPs), there are two primary categories: offline VRPs and online VRPs. Offline VRPs involve pre-determined trip requests while online VRPs deal with real-time request arrivals. However, existing formulations fail to adequately address a specific real-world issue identified through consultations with public transit agencies: the need for booking trips with flexible pickup windows in advance and confirming tight pickup windows at the time of booking. This type of service model is crucial in paratransit service settings where passengers typically schedule trips over the phone for the following day. To bridge the gap between offline and online problems, a novel formulation known as the offline vehicle routing problem with online bookings has been introduced. This problem poses significant computational challenges as it must handle large sets of requests akin to offline VRPs while adhering to strict constraints on running time similar to online VRPs. To tackle this complex problem effectively, a unique computational approach has been proposed that combines an anytime algorithm with a learning-based policy for making real-time decisions. Drawing upon a dataset from the public transit agency of Chattanooga, TN, the efficacy of this novel formulation and computational approach has been demonstrated through empirical analysis. The results showcase that this innovative solution outperforms existing algorithms significantly in addressing the intricacies of paratransit service settings. The study conducted by authors Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, Abhishek Dubey, Samitha Samaranayake, and Aron Laszka sheds light on how advancements in problem formulation and computational strategies can lead to enhanced outcomes in optimizing vehicle routing processes within challenging operational environments like paratransit services.