Anytime optimization approaches for online dial-a-ride problem

This study presents the development of a real-time dispatching system tailored for a ride-sharing service capable of accommodating a large volume of passengers and trips. The primary objective is to address the dynamic Dial-and-Ride Problem that ensures short travel time and service for each customer while minimizing waiting times. Departing from conventional methods that rely on fixed time intervals for batching requests, this research introduces a novel rolling-horizon strategy with adjustable time epochs. This approach combines the advantages of batch optimization with smaller batch sizes, ensuring rapid and effective dispatching. Two primal-based algorithms within a column generation framework are proposed and compared against a traditional column generation approach. A thorough evaluation is conducted using datasets derived from historical taxi trips in New York City, encompassing scenarios with up to 30,000 requests per hour.