Transit Bus Scheduling with Limited Energy

In this paper, we propose a vehicle-scheduling model for electric transit buses with either battery swapping or fast charging at a battery station, and a vehicle-scheduling model with the maximum route distance constraint for compressed natural gas, diesel, or hybrid-diesel buses. Both of these scheduling models are NP-hard. We develop column-generation-based algorithms to solve the scheduling problems. We conduct extensive case studies based on real-world instances and instances randomly generated in a practical setting. Our computational experiments show that our algorithms demonstrate very good computational performances. We also use real-world transit data to systematically analyze the number of buses needed, the total operational costs, and the vehicle emissions generated when compressed natural gas, diesel, hybrid, or electric buses are used in service.