Quantum Optimization for Large Scale Real-World Problems: A Public Transport Driver Scheduling Case Study

Public transport driver scheduling is a large-scale combinatorial optimization problem with immediate operational impact. A naïve segment-based Mixed Integer formulation leads to billions of variables and is computationally intractable. In this case study, we present how a real-world driver scheduling problem from urban public transport can be transformed and solved efficiently using a Column Generation approach, while providing a natural entry point for quantum optimization research.

We raise the level of abstraction by pruning infeasible transitions, constructing a feasibility graph, and collapsing atomic segments into feasible duties. The resulting problem is modeled as an assignee set-cover and solved via a hierarchical Column Generation framework. A relaxed master problem is solved classically, while a pricing subproblem iteratively generates new duties. This decomposition allows large planning horizons to be addressed efficiently and forms the backbone of industry-grade scheduling systems, delivering high-quality solutions within minutes and satisfying the majority of driver preferences.

Beyond classical optimization, we show how the pricing subproblem can be expressed as a QUBO, enabling experiments with quantum and hybrid quantum–classical methods. On small instances, quantum-enabled pricing demonstrates feasibility with limited qubit counts, while preserving the overall Column Generation structure. This makes Column Generation a powerful bridge between today’s production-ready solvers and tomorrow’s quantum hardware.

Our key message for decision makers is clear: Column Generation is a proven, scalable method delivering immediate business value today, while simultaneously providing a structured and realistic pathway to integrate quantum optimization as hardware matures.