Online Optimization of a Dial-a-Ride Problem with the Integral Primal Simplex

This paper focuses on developing a real-time dispatching system for a ride-sharing service. The primary goal is to address the dynamic dial-a-ride Problem, aiming to minimize waiting times while ensuring service quality by limiting ride duration. We introduce a rolling horizon-based framework, involving the division of the time horizon into small epochs, batching requests within each epoch, and re-optimizing the problem for the batch of requests. Unlike prior studies that restart optimization for each period from scratch, we leverage the strength of integral primal simplex to reuse effectively the previously computed solutions as a warm start, extending current routes with new incoming requests. Moreover, using integral primal methods allows us to provide an algorithm that is tractable in real-time and scales effectively to handle thousands of customers per hour. Experiments using historic taxi trips in New York City, involving up to 30,000 requests per hour, illustrate the efficacy and potential advantages of the method in effectively managing large-scale and dynamic scenarios.