Anytime optimization approaches for real-time ride-sharing systems

Ridesharing is an on-demand transportation service that offers cost-effective and convenient options for a wide range of users. The emergence of commercial ride-sourcing companies has highlighted the need for advanced optimization techniques to handle vast numbers of ride requests efficiently in real-time. This paper introduces an anytime optimization approach for the online Dial-a-Ride Problem in the context of a large-scale real-time ride-sharing system. Unlike traditional algorithms that utilize fixed time epochs for batching requests, our proposed method employs a rolling-horizon strategy with flexible time epochs, combining the strengths of optimization batch methods and smaller batch sizes to provide a fast and efficient solution. Two primal-based algorithms within a column generation framework is introduced and evaluated against a traditional column generation method. The evaluation has been conducted on instances derived from historic taxi trips in New York City involving up to 30,000 requests per hour.