Anytime optimization approach for dynamic DARP

Operating large-scale ride-sharing services requires solving the dynamic Dial-a-Ride Problem (DARP) in real time, constantly balancing routing efficiency against strict computational latency limits. Traditional batch-based dispatching relies on fixed intervals, which inherently introduce response delays and fail to adapt to varying computational loads. To address this, we introduce a novel anytime re-optimization framework driven by a flexible rolling-horizon strategy, where epoch lengths dynamically adapt to the actual computation time rather than predetermined batching intervals. At the core of this framework is an anytime column generation (A-CG) algorithm designed to prioritize early solution improvement. By systematically reusing information across consecutive planning epochs, the algorithm makes high-frequency re-optimization computationally tractable. The method also includes a simple lightweight vehicle rebalancing strategy to improve coverage in high-demand areas. Computational experiments on large-scale instances derived from New York City taxi data demonstrate that the proposed approach achieves a strong balance between responsiveness and service quality—reducing customer waiting times while maintaining short per-update computation times, even at demand levels of up to 30,000 requests per hour.