Accelerated column generation: application in online dial-a-ride problem

This paper focuses on developing a solution approach for a large-scale ridesharing system that is simultaneously scalable in real-time and capable of making high-quality decisions over long horizons. We propose an accelerated column-generation method embedded in a rolling-horizon framework, rather than relying on insertion-based heuristics, which lack guarantees on solution quality. To make this framework scalable in real-time, we introduce a set of acceleration strategies that not only reduce computational overhead but also guide the search toward solution structures that preserve flexibility for future decisions. Additionally, to further enhance long-term performance, we evaluate various user-centric objectives to quantify their impact on the flexibility trade-off, identifying which indicators provide better short-term decisions without adverse long-term effects. Extensive empirical experiments on historical taxi trip data from New York City demonstrate the robustness of this approach, which is capable of handling up to 30,000 requests per hour while outperforming state-of-the-art benchmarks in terms of average passenger waiting time.