A Column Generation Heuristic for Multi-Depot Vehicles Scheduling with Electric Vehicles

In this thesis we have formulated a method to solve the MultiDepot Vehicle Scheduling Problem with a bus-fleet which is partially electrically fuelled. This method incorporates a Column Generation process and a dedicated heuristic to solve the Pricing Problem. The Truncated Column Generation heuristic provides integer solutions in reasonable time for large instances of the MDVSP. Two additional challenges surface with the introduction of electric vehicles: The limited action radius of the batteries, resulting in a more challenging Pricing Problem. Secondly, electric vehicles are smaller than diesel vehicles in terms of passenger capacity. To incorporate the electric fleet, we have introduced a new set of arcs to the network for which a bus can be recharged. Additionally, we have determined the demand per trip and removed arcs for which a bus as insufficient capacity. The algorithm used to solve the Pricing Problem is similar to any shortest path algorithm. We introduced one additional update-condition to ensure there is always sufficient charge left in battery to continue and return to the depot to recharge. The heuristic is used to solve the vehicle scheduling problem based on historical data for trip demand. We have compared the results of these schedules to the schedules we have solved for each weekday for two test weeks. We conclude that the on average the operational costs using dayspecific schedules are reduced by 9.3%.