Why EV Public Transit Scheduling is Different
The global drive to decrease fossil fuel dependency and resulting policy measures have pushed transit agencies to replace diesel and natural gas fleets with electric vehicles (EVs). Although the high capital costs of EVs present a significant hurdle for agencies, the successful adoption of EVs is much more complicated than just buying new buses.
As a result of battery range limitations, EVs need to be recharged throughout the day and, at the very least, planners must form a charging strategy compatible with available infrastructure. This introduces new challenges to the planning and scheduling process. Because suboptimal recharging threatens to increase the number of vehicles required to operate a timetable (and therefore increase operational costs), optimizing charging events is essential to create economically-viable electric transit solutions.
Deciding when, where, and for how long to recharge electric vehicles is dependent on several variables:
- Electricity pricing
Because electricity pricing varies throughout the day, much more so than diesel or natural gas, taking advantage of low demand (and thus low cost) times is key to minimizing operational costs. - Available charging infrastructure
The availability of in-depot and opportunity (i.e. en-route) charging varies from agency to agency. As a result, travelling to chargers (by way of a deadhead) and the capacity of such charging infrastructure needs to be taken into account. - Charging needs of the fleet as a whole
Schedulers must consider when other vehicles are charging. Having too many vehicles charging at one time can force agencies to use extra diesel buses to account for those EVs temporarily out of service.
The addition of these new parameters to vehicle scheduling makes using an optimization tool all the more necessary, but many scheduling platforms lack the algorithmic ability to support EVs. Luckily, a new generation of planning and scheduling software tackles these challenges.
Visualizing Algorithmic Complexity
Let’s look at the algorithmic complexity of optimizing charging events.
We can model a transit system as a network of possible connections between compatible trips (whose times don’t overlap, are the same vehicle type, and therefore can be driven by the same vehicle). In reality, transit systems are much more complex, but to give us a basic understanding of algorithmic complexity, we can use this simplified model:
If we zoom in on the connection between two compatible trips, we can see what makes optimizing EV scheduling so difficult.
For traditional vehicles, we only have one option for connecting two compatible trips: a deadhead. So, our goal in optimizing scheduling with traditional buses is to connect all trips with the least number of buses possible, while minimizing deadhead cost. Performing this optimization under the constraint of agency-specific rules and preferences results in blocks and crew schedules with maximized operational efficiency.
More Options Mean a Larger Search Space
The electric vehicle scenario gives us a much more complicated model. This is because we might have more than one option when connecting two trips. In our example, each connection has three options: complete a deadhead to the next route immediately, charge at the closest in-depot charger (with deadheads on both sides of the charging event), or charge at the nearest opportunity charger (possibly with deadheads on both sides of the charging event, depending if the opportunity-charger is en-route). We now want to minimize peak vehicle requirement, deadhead costs, and charging costs (electricity and time) with the addition of two new constraints: each bus must have enough charge to complete its trips and there are a limited number of chargers that can be used at one time. Because these constraints involve the entire system, not just one connection between two trips, advanced algorithms are needed to support them.
In this example, we are only looking at one possible connection between two trips. More practically, for a complete system of trips, there are millions. For a real world scenario of 500 service trips, all possible combinations of these connections, without the recharging possibilities, could result in an algorithmic search space of over 2^65 (about 3.69⋅10^19) possible blocks to choose from. If we add the recharging opportunities required for EV optimization, not only does the search space become much larger, the optimal way to sort through it changes, compounding the problem’s complexity. This is because we now have non-feasible vehicles in our search space (that were previously feasible with traditional scheduling) and, as a result, there is no easy algorithmic way to exhaust the search space. Thus, the search space size begins to affect conventional algorithmic capabilities of solving the problem efficiently.
The successful adoption of EVs into public transit is dependent on our ability to optimize the resources available to us while complying with the new constraints created by charging requirements. Doing this with the help of advanced algorithms can allow us to create public transit that maximizes operational efficiency, while reaping the benefits of carbon independence.
