Scheduling for mass transit isn’t simple. In fact, scheduling is a NP-Hard problem. As a result, it requires intensive compute resources; adding the simplest realities of mass transit operations, such as depot requirements or breaks, makes it exponentially more complex (to understand the complexity, check this example of what adding depots implies).
As a result, past practices separated mass transit scheduling into two discrete steps that were performed sequentially:
- Vehicles were scheduled (a practice called “blocking” in the US) and only then
- The drivers that will drive those vehicles were scheduled (a process called “runcutting” in the US).
As we were working to develop the Optibus platform, it became evident that this two step process yields less than optimal results, since the blocks are fixed and can’t be modified to better accommodate the needs of the driver schedule. As a result, and in order to achieve superior optimization results, our platform design goal was to optimize vehicles and drivers at the same time.
That’s why one of the features we’re particularly fond of at Optibus is the ability to make the following choice before running an optimization:
- Optimize vehicles
- Optimize drivers; or
- Optimize both (all of the above)
Optimizing “all of the above” delivers the best results, and we wanted to use this blog post to demonstrate how and why.
The problem with sequential vehicle and driver scheduling
First, let’s look at what happens when driver and vehicle scheduling are done separately.
In the past, scheduling work was entirely manual, done with pen and paper, or using spreadsheets. This is still the case in many places around the world, even today.
Vehicle scheduling was a manual process which involved taking a series of trips and attaching them to a “block”. Later on, each block was assigned to a vehicle.
The driver scheduling process involved “cutting” the block into pieces and then ״stitching״ them together to form a driver shift – also known as a “run”. In the past, this was literally done with scissors, cutting the blocks which were drawn on a piece of paper, into pieces – hence the name “run-cutting”.
Years later, the first software platforms used the same technique. To this day, most computer programs for vehicle and driver scheduling, still form “blocks” and then “cut” them into driver duties. But, as I mentioned earlier, this results in less than optimal results. To understand why, let’s look at how the process was done in the past, by first optimizing vehicles and only then drivers. Afterwards we will show what performing simultaneous optimizations of both vehicles and duties can do.
Vehicle Scheduling
Before we go into an example of vehicle only scheduling, let us mention that there is a profound difference between driver and vehicle scheduling, and the underlying reason is that drivers are human and vehicles aren’t: they are inherently different when it comes to work times and downtime.
Vehicles don’t take breaks and can work very long shifts (from sunrise to midnight). They don’t get paid for overtime. As a result, a typical vehicle-only optimization will lump all vehicles together, minimizing breaks and deadhead trips. The goal would be to maximize revenue miles driven by each vehicle. You can see this visually here, in this vehicle scheduling output:
Driver Scheduling
In general, driver scheduling has much higher degrees of complexity compared to vehicle scheduling.
Optimizing for drivers alone requires that you first define rules and preferences (such as state and federal labor rules, union agreements, other driver preferences, overtime, breaks, etc.) There are many possible constraints that you can set on the Optibus platform. Here is a simple example of a break preference that you might set for drivers:
Driver duties produce a result that is visually different than the vehicle schedule above (driver duties here are sorted by the beginning time for each shift):
This is the vehicle and driver schedule after optimizing first for vehicles and then for drivers. As can be seen in the image above, there are many driver shifts (duties) which are short. This is because the vehicle schedule that was generated (and was optimal for vehicles) is not well suited for drivers (drivers need breaks while vehicles don’t). Therefore we get a schedule which is quite costly with a total cost of $108,120 due to the high number of required drivers, with 235 duties, a PVR of 87 and only 60% crew efficiency. Let’s see whether optimizing driver and vehicle schedules at the same time can deliver better results.
Driver and vehicle scheduling at the same time
When driver and vehicle scheduling are done at the same time, vehicle blocks are modified as we run the driver schedule optimization, to better fit the duties.
Here is the vehicle schedule – now it is better adjusted to fit with driver duties:
Here is the driver schedule:
In the case of this simultaneous optimization, costs are lower, at $ 90,755, representing a savings of 16% and a slightly higher PVR of 88. Thus, we’ve proven that the historical method of optimizing vehicles first and drivers afterwards isn’t optimal and provides results that are considerably worse than combining vehicle and driver optimization into one process.
Conclusion
Technology is changing traditional driver and vehicle scheduling processes, and delivering better results, faster. Examining traditions, such as the practice of separating driver, vehicle and relief vehicle schedules, and using computational and algorithmic powers to make them run at once hold the promise of better scheduling optimization outcomes.
