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.