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.
翻译:车辆路由问题(VRPs)可分为两大类:离线的VRPs,其中考虑要满足的一组旅行请求,和在线的VRPs,其中乘客通常会通过电话预订第二天的行程。根据与公共过境机构的讨论,我们发现一个没有通过现有配方解决的现实世界问题:提前(例如前一天的3小时)用灵活搭车窗口预订旅行(例如,提前3小时),在订票时确认紧凑的购物窗口(例如,30分钟)。这种服务模式在准透明服务环境中经常需要,乘客通常会通过电话预订次日旅行。为了解决离线问题和在线问题之间的这一差距,我们采用了一种新颖的配方,即在线订票的离线车辆路由问题。这个问题在计算上非常困难,因为它面临着考虑大量请求的复杂性 -- -- 类似于离线的VRPS,但在运行过程中必须严格遵守严格的限制 -- -- 类似于在线的VRPs。为了解决这个问题,我们建议一种创新的计算方法,即从现在的代理机运算算法与我们现在学习的结果。