Bus Driver Scheduling Problem

Last updated: ...

Problem Definition

The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem arising in public transportation planning. It has three main goals:

1. Coverage: Define daily driver shifts that cover all predetermined bus tours and meet the transportation system's demand.
2. Feasibility: Respect all requirements from collective agreements and legal regulations, ensuring driver safety through adequate rest and break times.
3. Cost minimization: Reduce operational costs while also minimizing driver dissatisfaction (e.g., avoiding excessively long unpaid breaks).

The instances used here model regulations from the European Regulation (EC) No 561/2006 on driving times and the Austrian Collective Agreement for employees in private omnibus providers, making the problem particularly constrained and challenging.

Problem Input

The input consists of:

• Positions and Distance Matrix: A set of positions (bus stops) \(P\) and a time distance matrix \(D = (d_{ij})\) where \(d_{ij}\) is the time for a driver to travel from position \(i\) to \(j\) when not driving a bus (passive ride time).
• Start/End Work Times: For each position \(p\), the time required to start or end a shift at that location.
• Bus Legs: A set \(L\) of bus legs, where each leg \(\ell\) is a 5-tuple: \[\ell = (\text{tour}_\ell, \text{startPos}_\ell, \text{endPos}_\ell, \text{start}_\ell, \text{end}_\ell)\] representing a trip of a vehicle between two stops. All times are in minutes from midnight.

Solution

A solution \(S\) is a set partition of the bus legs \(L\) into shifts: \(S = \{s_1, s_2, \ldots, s_n\}\). Each shift \(s_i\) represents a subset of bus legs assigned to a single driver for one day. A solution is feasible if drivers have enough time to travel between consecutive legs and all regulatory constraints are satisfied.

Objective Function

The objective is to minimize the total cost across all shifts:

where for each shift \(s\):

• \(W'_s = \max\{W_s, 390\}\): Working time with a minimum of 6.5 hours (390 min) guaranteed pay
• \(T_s\): Total time (span from shift start to end)
• \(\text{ride}_s\): Sum of passive ride times between consecutive legs
• \(\text{change}_s\): Number of tour changes (switching between different buses)
• \(\text{split}_s\): Number of shift splits (unpaid breaks longer than 3 hours)

Key Constraints

Driving Break Options

Before accumulating 4 hours of driving, drivers must complete one of these break patterns:

• One break of at least 30 minutes, or
• Two breaks of at least 20 minutes each, or
• Three breaks of at least 15 minutes each

Rest Break Requirements

Based on working time \(W_s\):

• \(W_s < 300\) min (5h): No rest break required
• \(300 \leq W_s \leq 540\) min: At least one 30-minute break
• \(W_s > 540\) min (9h): At least one 45-minute break

Terminology

Position

A bus stop or location where drivers can start/end work or change between buses. Positions are connected by a distance matrix representing passive travel times.

Tour (Bus Tour)

A sequence of legs assigned to a single vehicle (bus) for one day. Each tour has a unique ID. Legs within a tour do not overlap in time.

Leg (Bus Leg)

The atomic unit of work: a trip of a vehicle between two positions at specific times. Defined as a 5-tuple \((\text{tour}, \text{startPos}, \text{endPos}, \text{start}, \text{end})\). Legs cannot be split between drivers.

Shift

A subset of bus legs assigned to one driver for one day. The work scheduled for a single driver. The solution to BDSP is a set of shifts that partition all legs.

Passive Ride

Time spent by a driver traveling between positions without actively driving a bus. Occurs when consecutive legs in a shift start/end at different positions.

Shift Split

An unpaid break longer than 3 hours (180 minutes) between consecutive legs. Splits reset the driving time counter. A shift may contain at most 2 splits.

Driving Time \(D_s\)

The sum of leg durations in a shift: \(D_s = \sum_{\ell \in s} (\text{end}_\ell - \text{start}_\ell)\). Maximum: 9 hours.

Total Time \(T_s\)

The span from shift start (including start work time) to shift end (including end work time). Maximum: 14 hours.

Working Time \(W_s\)

Total time minus shift splits and unpaid rest breaks: \(W_s = T_s - \text{splitTime}_s - \min\{\text{unpaid}_s, \text{upmax}_s\}\). Maximum: 10 hours.

BP (Branch-and-Price)

An exact optimization algorithm combining branch-and-bound with column generation. Provides optimal solutions for small-medium instances and valid lower bounds.

LNS (Large Neighborhood Search)

A metaheuristic that iteratively destroys and repairs parts of a solution. Finds high-quality solutions for large instances but does not guarantee optimality.

Lower Bound

A proven minimum value for the optimal solution cost, computed via linear programming relaxation in Branch-and-Price.

Gap

The relative difference between the best known solution and the lower bound: \[\text{Gap} = \frac{\text{Best Solution} - \text{Lower Bound}}{\text{Lower Bound}} \times 100\%\] A gap of 0% indicates a proven optimal solution.

Instance Collection

Download

The original real-world instances cannot be publicly shared due to agreements with bus companies. Instead, an instance generator was developed to create realistic instances following similar distributions.

Instance Naming Convention

Instances follow the pattern: realistic_[SIZE]_[ID]

• SIZE: Approximate number of tours (10, 20, 30, ..., 250)
• ID: Unique instance identifier (1-65)

Example: realistic_50_23 is instance #23, containing approximately 50 tours.

Instance Structure

Each instance defines bus legs as 5-tuples following the formal specification:

Example from the formal specification (two bus tours with 6 legs):

tour  startPos  endPos  start  end
  1        0       1    360   395
  1        1       2    410   455
  1        2       1    460   502
  1        1       0    508   540
  2        0       3    360   400
  2        3       0    415   500

The first vehicle (tour 1) starts at 06:00 at position 0, travels between positions 1 and 2 with waiting times in between, then returns to position 0.

Best Known Solutions

Computational Setup

Instance Collection (65 instances)

Generated instances following distributions from actual Austrian bus networks. Sizes range from 8 tours (73 legs) to 250 tours (2339 legs). Lower bounds are computed using Branch-and-Price (BP) where available.

Rows highlighted in green with 0.00% gap represent proven optimal solutions. Click on any instance name to view detailed algorithm comparison results.

Reporting New Best Solutions

If you find improved solutions, please contact tommaso.mannelli@tuwien.ac.at to have them included in this table.

You can also validate your solution online using the web-based validator before submitting.

References

1. Kletzander, L., & Musliu, N. (2020). Solving large real-life bus driver scheduling problems with complex break constraints. ICAPS 2020. DOI
2. Kletzander, L., Mazzoli, T. M., & Musliu, N. (2022). Metaheuristic algorithms for the bus driver scheduling problem with complex break constraints. GECCO 2022. DOI
3. Mazzoli, T. M., Kletzander, L., Van Hentenryck, P., & Musliu, N. (2024). Investigating Large Neighbourhood Search for Bus Driver Scheduling. ICAPS 2024. DOI
4. Mannelli Mazzoli, T., Kletzander, L., Musliu, N., & Smith-Miles, K. (2024). Instance Space Analysis for the Bus Driver Scheduling Problem. PATAT 2024. PDF
5. Kletzander, L., Mannelli Mazzoli, T., Musliu, N., & Van Hentenryck, P. (2025). Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints. Journal of Artificial Intelligence Research (JAIR).