It’s nice when steps are clearly laid out – complete step 1, move on to step 2, finish with step 3, and you’re done. Historically, this is how the transit planning process has gone. First you make the routes and set the timetable, then you assign vehicles to those routes (vehicle scheduling or blocking), and lastly, you assign drivers to those vehicles (crew scheduling or run-cutting) and create weekly rosters. Because the standard mode of planning has, until now, been largely manual, tackling more than one of these steps at once was too complicated to execute. This is because scheduling optimization is an NP-Hard problem – every time you add another route or increase a frequency, the problem becomes exponentially more complicated.
The Division of Labor between PTAs and PTOs
This sequential procession of planning and scheduling is especially evident in the relationship between public transit agencies (PTAs) and private transit operators (PTOs). In most cases, the PTA plans routes and assigns vehicles to these routes (occasionally, this process is contracted out to PTOs). They then give these blocks to a PTO, who assigns drivers to vehicles. The responsibilities are separated and the planning process flows one way:
Why PTAs and PTOs Should Collaborate on Scheduling
You could say that the difference between a PTO and a PTA is that one does the blocks and one does the runcuts, but is this a good outcome?
What if a PTO finds that a small tweak in the blocks could result in a large improvement in the quality of run-cuts? For example, drivers can only get on or off a vehicle at certain terminals, but an optimal vehicle schedule doesn’t necessarily take these considerations into account. So, while a set of vehicle blocks may be optimal for vehicles, the resulting crew schedule can be very inefficient because they must be made in accordance with driver requirements such as rest time or work limitations. And thus, the schedule is worse overall.
These kinds of problems occur often. Because vehicles are optimized first, driver constraints take the back seat, resulting in suboptimal crew schedules. When PTAs and PTOs don’t communicate much, they miss the opportunity for improvement that can be achieved by tweaking the blocks to better accommodate the requirements for crew schedules. For PTOs, this can be frustrating – they can discover potential block changes that are mutually beneficial, but have no way to realize them.
Maybe, by blurring the lines a bit between these responsibilities and adding some collaboration between the PTA and the PTO, we could prioritize both efficient vehicle use and the quality of driver schedules:
By introducing a feedback loop between the PTO and PTA, both parties can explore blocking changes to improve the system as a whole. Of course, it’s not always possible to change vehicle blocks to create a better crew schedule, as PTAs have their own limitations (like capital expenses). But, by making the process dynamic, we have the choice to adapt to crew scheduling preferences and create an optimized system that is better for both vehicles and drivers.
Simultaneous Optimization Makes Sense
The benefits of simultaneous optimization can also be seen algorithmically. We can look at scheduling optimization like choosing a path through a tree, where we want to minimize the total sum (i.e. cost) of our path.
A sequential framework in which vehicles are optimized, and then drivers optimized subject to those vehicle constraints would result in a path like this:
As you can see, we were able to choose the least cost at each step, but failed to find the path that would optimize the entire system. This is because a sequential framework acts like a greedy algorithm – at each step, we make our decision without regard to future consequences. The PTA chooses the most efficient blocks, but isn’t aware that the decision results in a more costly crew schedule later on, requiring more drivers to fulfill the service or resulting in split shifts and other sub optimal results. (It’s true that sometimes blocks do contain some initial adjustments for driver breaks, but this doesn’t always create an optimal solution).
In contrast, a collaborative system, in which duties and vehicles are optimized simultaneously would find the optimal path:
Here, feedback between the PTA and PTO allows them to choose the path that minimizes the total cost because they are able to analyze all possible outcomes.
But, there’s a tradeoff – it’s much easier to find the “best” solution in the sequential framework than it is to find the optimal solution in the simultaneous one. In the sequential framework, we only had to analyze two options. In the simultaneous framework, we had to analyze four. This is manageable now, but imagine a more realistic scenario, where there are 1 million blocking options and 1 million possible run-cuts and therefore 1 trillion possible block/run-cut combinations – it would be impossible to find the optimal path by hand.
This issue can also be seen when a PTA plans for certain frequencies/headways on routes, but sends a fixed timetable (and blocks) to the PTO. If those requirements are shared with the PTO, sometimes a small shift in the timetable can create large potential savings and require less vehicles to operate.
Advanced Algorithms for Simultaneous Optimization
Luckily, recent technological developments free schedulers from the constraints of manual computation, allowing them to address vehicle scheduling and crew scheduling simultaneously. Now, we can find the optimal solution using the simultaneous framework in much less time than we could find the “best” solution using the sequential one.
Because of this, we need a complete overhaul in how we think about transit planning. Rather than seeing it as a sequence of steps with individual optimization opportunities, we can see planning as one system, whose parts (and parties) all interact, that can be optimized end-to-end. Given a set of operational constraints, we could find the best routes, timetables, frequencies and the optimal assignment of vehicles and drivers to support that system. This absolves the need to perform steps sequentially or contract them out – we could just do it all at once. This would enable dynamic transit systems that can quickly and accurately adjust to demand, going from simultaneous optimization of vehicle and drivers to optimizing routes and timetables. That’s the future of transit planning.
