Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests
This work is significant for public transit agencies operating on-demand services, as it tackles the practical challenge of balancing prompt request confirmation with guaranteed service and continual route optimization, an incremental improvement over existing methods.
The paper addresses the dynamic vehicle routing problem for on-demand transit services, focusing on the need for prompt confirmation of advance requests while ensuring all accepted requests are served. Their proposed approach, which integrates quick insertion search with an anytime algorithm and a reinforcement learning-trained non-myopic objective function, significantly increases the number of requests served compared to existing methods on a real-world microtransit dataset.
Transit agencies that operate on-demand transportation services have to respond to trip requests from passengers in real time, which involves solving dynamic vehicle routing problems with pick-up and drop-off constraints. Based on discussions with public transit agencies, we observe a real-world problem that is not addressed by prior work: when trips are booked in advance (e.g., trip requests arrive a few hours in advance of their requested pick-up times), the agency needs to promptly confirm whether a request can be accepted or not, and ensure that accepted requests are served as promised. State-of-the-art computational approaches either provide prompt confirmation but lack the ability to continually optimize and improve routes for accepted requests, or they provide continual optimization but cannot guarantee serving all accepted requests. To address this gap, we introduce a novel problem formulation of dynamic vehicle routing with prompt confirmation and continual optimization. We propose a novel computational approach for this vehicle routing problem, which integrates a quick insertion search for prompt confirmation with an anytime algorithm for continual optimization. To maximize the number requests served, we train a non-myopic objective function using reinforcement learning, which guides both the insertion and the anytime algorithms towards optimal, non-myopic solutions. We evaluate our computational approach on a real-world microtransit dataset from a public transit agency in the U.S., demonstrating that our proposed approach provides prompt confirmation while significantly increasing the number of requests served compared to existing approaches.