Online optimization of a dial-a-ride problem with the integral primal simplex

Ridesharing is an innovative on-demand transport service which provide convenient and cost-effective travel options for diverse population segments. This service has the potential to mitigate congestion and pollution by increasing vehicle occupancy and reducing car utilization, thereby contributing to a more sustainable transportation system. The rise of commercial ride-sourcing companies offering this service at a large-scale underscores the necessity for advanced optimization techniques capable of efficiently managing a substantial number of ride demands in real time. However, state-of-the-art optimization methods are rarely used in practice due to their complex implementation, consequently restricting their potential benefits. This paper focuses on the development of a real-time dispatching system for a ride-sharing service, employing primal methods that scale effectively to handle thousands of customers per hour. The primary goal is to address the dynamic Dial-and-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, we leverage the strength of integral primal simplex to reuse previously computed solutions as a warm start, extending current routes with new incoming requests. Computational experiments, conducted on instances derived from historical 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.