Anytime optimization approach for dynamic dial-a-ride problem

This study introduces an anytime optimization approach for the online Dial-a-Ride Problem within large-scale, real-time ride-sharing systems. Unlike traditional algorithms that rely on fixed-time epochs to batch requests, our method employs a rolling-horizon strategy with flexible time epochs. This hybrid approach effectively combines the strengths of optimization batch methods and smaller batch sizes, delivering fast and efficient solutions. We propose a column generation-based framework enhanced with accelerated techniques for solving pricing subproblems. This enables rapid re-optimization and the creation of high-quality dispatching plans under dynamic conditions. By dynamically adjusting time epochs based on actual computation times, the system maintains high responsiveness while minimizing passenger waiting times. Extensive experiments conducted on large-scale New York City taxi data demonstrate that our method significantly enhances service quality compared to existing techniques. It proves highly effective in handling thousands of trip requests per hour, making it well-suited for large-scale and dynamic ride-sharing environments.