Public Transit Math

Math Climate Day 2024 | Matthew Greenberg | University of Calgary

“Public transportation gets people where they’re going while emitting far fewer climate-warming greenhouse gases than private cars. The reason is simple efficiency: while cars usually carry just one or two people at a time, a bus can carry 50 or more, and a train in a large city may carry thousands.� �Since transportation creates more than a fifth of the world’s greenhouse gas emissions, shifting people from cars to public transit can do a lot to lower our impact on the climate. But people will only choose public transportation when it is their most convenient option for getting around.”

Calgary transit in 2023:

• 90 million rides
• 3000 employees including 2000 operators
• 1000 buses and 200 light rail vehicles
• 6000 stops on 150 routes
• Operating budget $280 million (municipal)
• Capital budget $440 million (provincial and federal)

Public transit is complex and expensive!

Math: Strike the optimal balance

• Service planning and network design (data-driven modeling)�coverage, ridership, service goals, frequencies�
• Timetabling and vehicle scheduling (optimization)�meet-ups, fueling/charging, depots�
• Crew scheduling (optimization)�labor rules

Service

Cost

Scheduling terminology

• Vehicle block: a bus trip beginning and ending at its depot
• Relief point: a point along a vehicle block where a driver change can occur; vehicle blocks may share relief points
• Task: an “atomic” portion of a vehicle block between two consecutive relief points; must be covered by a single driver
• Workpiece: a sequence of consecutive tasks performed by a single driver along a single vehicle block
• Duty: a plausible sequence of workpieces, alternating with breaks, to be performed by a single driver

6

Timetabling and vehicle scheduling

7

Crew scheduling

8

Valid duties and labor rules

• Valid duties must conform to labor rules, typically encoded in a collective agreement between the drivers’ union and the transit company. These agreements may regulate, e.g.:
• min/max length of a workpiece
• min/max length of a break
• max number of workpieces in a duty
• min/max worked time in a duty
• max spread of a duty (time elapsed from clock-in to clock-out)

​

The Crew Scheduling Problem

Enumeration?

• If we could enumerate all valid duties, then we could just pass the CSP to a solver like CPLEX or Gurobi.
• Unfortunately, the number of valid duties is enormous even for moderately sized transit networks. The enumeration is intractable.
• Instead, we pursue an approach in which we generate new valid duties as we need them.

The Master and Restricted Master Problems

Column (duty) generation

Solving the subproblem

Reduced costs and shortest paths

Resource-constrained shortest paths

Encode labor rules as resource maps

Solving the Master Problem

Integrality

That’s all for today!

• Want to know more? Go work for GIRO! They’re always hiring.
• Thanks!
• Questions?