Zero Emission Optimiser

Challenge

The transition from diesel to electric buses goes faster and faster. In 2025 there will be no new diesel buses in the Netherlands and in 2030 the entire bus fleet must be emission free. Hence this transition introduces an additional layer of complexity in network planning. Strategic choices regarding charging locations, charging infrastructure, purchasing of buses and timetables are strongly intertwined and have an impact on the planning, the daily operation and the total costs during the concession.

One challenge is the vehicle scheduling of the buses, determining which bus is assigned to which trip. The bus departs from a storage facility in the morning, performs a journey, possibly drives empty of passengers to another starting point or waits on site for the next ride, and so on until the end of the day at the storage facility. In between, a bus can of course always return to the parking facility for temporary parking. With the limited range of electric buses, it might be necessary to charge in between at one of the charging locations in the network.

We were asked by a world-wide operator to recommend a solution to determine the minimal Total Cost of Ownership (TCO), while all journeys are driven with sufficient capacity, and a bus does not come to a standstill due to an empty battery. The TCO consists of the investment costs over the entire concession or depreciation period, and the daily operating costs for loading, personnel and maintenance.

The goal was not a detailed timetable planner, which is provided by currently existing tools such as Hastus. The goal was rather to determine early in the process and is ideal for example the public transport tendering processes, where it is crucial to make really quick calculations of lots of different scenarios.

Our solution

Our method to approach this problem is a mixed-integer linear problem (MILP), a class of OR problems in which we seek a solution with a minimum value for a target (in this case the total cost) given a set of constraints (including each trip one bus, the battery must not fall below its capacity and buses start and end at the same depot). However, simply putting all parameters in and calculating the optimum would require too much computational time. Because of our previous experience in bus route optimization, we knew we had to apply two methods to make the problem manageable.

One technique we used was to split the problem into relevant subproblems (formally: column generation). We optimized each of these partial problems individually (fixing the other parameters), and applied a master optimisation to connect all individual subproblems and find an overall optimal solution.

We also reduced complexity by letting go of some constraints we knew would likely not have much impact on the optimal answer, but would increase computation time significantly. For example, we assumed simultaneous charging of the buses at the loading location would not be a bottleneck. And after finding the optimal schedule and number of buses, we checked whether this assumption indeed held. 

Applying the techniques mentioned above ensured that the algorithm found an optimal solution within realistic times. 

Result

This way it’s possible to quickly decide the course of action and also make really quick adjustments when the input changes. Our solution has been used in several tenders and has been integrated in the wider strategic planning tool set of this world-wide operator.