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 the public transit agency of Chattanooga, TN, we demonstrate that
our novel formulation and computational approach lead to significantly better
outcomes in this setting than existing algorithms.

本文研究了一种基于离线车辆路径规划的在线客运服务问题，该问题考虑了灵活的接送时间窗口和实时订车，并提出了一种结合任意算法和基于学习的策略，比现有算法在实现更好的结果的求解方法。