Driver Duty Scheduling
Set Partitioning — Column Generation
A transit operator must build driver shifts from 8 scheduled vehicle trips, ensuring every trip is covered exactly once while minimizing total labor cost. Poor crew scheduling wastes 10–20% of labor budget in excess overtime and deadheading.
Where This Decision Fits
Transit planning pipeline — the highlighted step is what this page optimizes
The Problem
From transit timetables to set partitioning
A transit agency operates 8 vehicle trips throughout the day, each with a fixed start time, end time, and terminal location. A feasible duty (driver shift) is a sequence of trips that a single driver can perform: consecutive trips must allow at least 30 minutes of turnaround time between the end of one trip and the start of the next, and no duty may exceed 8 hours of total span. The objective is to select a minimum-cost set of duties such that every trip is covered exactly once.
This is the classic Set Partitioning Problem (SPP). Each column represents a feasible duty; each row represents a trip. The binary decision variable xi selects whether duty i is used. The constraint matrix A has aij = 1 if duty i covers trip j.
| Transit Domain | Set Partitioning Model | |
|---|---|---|
| Vehicle trip | Row / element to cover | |
| Driver duty (shift) | Column / subset | |
| Labor cost of duty | Column cost ci | |
| Cover every trip once | Σ aijxi = 1 ∀ j | |
| 30-min turnaround, 8h max | Column feasibility rules |
subject to
Σi aij xi = 1 ∀ j ∈ Trips // each trip covered exactly once
xi ∈ {0, 1} // binary selection of duties
Try It Yourself
Build driver duties from vehicle trips and see the Gantt chart update
Driver Duty Scheduler
8 Trips · 3 Scenarios| # | Trip | Depart | Arrive | From | To |
|---|
Ready. Select a scenario and click “Solve & Visualize”.
| Algorithm | Duties | Total Hrs | Overtime | Cost | Uncovered |
|---|---|---|---|---|---|
| Click Solve & Visualize | |||||
The Algorithms
Three approaches to crew scheduling
Greedy Chaining
O(n²) | Fast baselineSort trips by departure time. For each unassigned trip, attempt to append it to the duty whose last trip ends earliest and still satisfies the 30-minute turnaround and 8-hour maximum span constraints. If no existing duty can accommodate the trip, open a new duty. This mirrors how dispatchers often build rosters manually — simple and fast, but may create more duties than necessary.
Column Generation (Simplified)
Iterative LP | Near-optimalStart with an initial set of single-trip duties (one per trip). Solve the LP relaxation of the set partitioning master problem. Use the dual prices to identify a new duty (column) with negative reduced cost by enumerating feasible trip sequences. Add the improving column and re-solve. Repeat until no improving column exists. Round the fractional LP solution to obtain an integer solution. For small instances like ours, this typically finds the optimum.
Manual Drag
Human-driven | EducationalBuild your own duties by dragging trips into duty rows. The system validates feasibility in real time (turnaround ≥ 30 min, span ≤ 8h) and highlights violations. Click “Evaluate” to see how your manual solution compares against the algorithmic approaches. This mode is designed to build intuition for why set partitioning is hard.
Real-World Complexity
Why crew scheduling goes beyond the basic set partitioning model
Beyond the Basic Model
- Labor regulations — Maximum driving hours, mandatory breaks, minimum rest between shifts, and overtime rules vary by jurisdiction and labor agreement
- Split shifts — Drivers may work a morning block, go off-duty for several hours, then return for an evening block, creating complex feasibility constraints
- Depot constraints — Duties must start and end at specific depots; deadheading (empty travel between depots) adds cost
- Driver qualifications — Not all drivers are qualified for all vehicle types (articulated buses, trams, etc.), reducing feasible duty sets
- Rostering integration — Daily duties must be assembled into weekly or monthly rosters that balance workload and satisfy days-off requirements
- Real-time disruptions — Driver sickness, vehicle breakdowns, and delays require re-optimization of the remaining schedule on the fly
- Scale — Large transit agencies have thousands of trips and millions of feasible duties, making explicit enumeration impossible without column generation
Key References
Foundational works in crew scheduling and set partitioning
- (1989). “A column generation approach to the urban transit crew scheduling problem.” Transportation Science, 23(1), 1–13.
- (1998). “Branch-and-price: Column generation for solving huge integer programs.” Operations Research, 46(3), 316–329.
- (2005). “Operations research in passenger railway transportation.” Statistica Neerlandica, 59(4), 467–497.
Need to optimize crew scheduling?
From driver duty scheduling to fleet planning and real-time dispatch, mathematical modeling can cut labor costs and improve service reliability. Let’s discuss how Operations Research can work for you.