Scheduling Electric Buses with Stochastic Driving Times
Summary
In this thesis we look at the Stochastic Electric Vehicle Scheduling Problem. In this problem we are given a set of trips, and we need to schedule vehicles such that each trip is driven. We apply this problem to electric buses, where we want to minimize the operating cost taking the battery life into account. Here, we want to make our schedules more robust against delays. These delays could be caused by, for example, various traffic conditions, or passenger loads, as these factors have an effect on the driving time. Thus, in order to make our schedules more robust against these delays, we use stochastic driving times instead of deterministic driving times. Not only the driving time itself could be a source of delays, but also the energy consumption. Bus drivers have different driving styles, which affects the energy consumption, and thus the time needed for charging. Thus, we also consider the energy consumption to be stochastic.
To achieve this, we use a combination of simulated annealing and simulation. Here, we use simulation to calculate the cost of a solution. This, however, comes with a performance penalty. Thus, we try different methods of determining how many simulations we need, such that we still make a correct choice about which solution is better. The techniques we consider here are: Optimal Computation Budget Allocation, Indifference Zones, and a method we developed ourselves, which uses t-tests.
We show that the use of some of these methods can increase the runtime performance while performing similar in terms of their final score. Furthermore, with our use of stochastic driving times, we see in increase in the punctuality of the buses, and they also arrive a bit earlier at the start of their trip. However, we also see a slight increase in operating cost, as we need slightly more buses compared to when we use deterministic driving times.