The Vehicle Scheduling Problem for Fleets with Alternative-Fuel Vehicles

Alternative‐fuel vehicles are gaining popularity as a mode of transit, and research is being done into how current infrastructure can accommodate them. The problem of vehicle scheduling consists of assigning a fleet of vehicles to service a given set of trips with start and end times. Vehicle scheduling changes when alternative‐fuel vehicles are used since the vehicles can carry only a limited amount of fuel and can refuel only at fixed locations. This paper presents the alternative‐fuel multiple depot vehicle scheduling problem, a modification of the standard multiple depot vehicle scheduling problem where there is a given set of fueling stations and a fuel capacity for the vehicles. The problem is formally defined and formulated as an integer program, and a branch‐and‐price algorithm is proposed to solve the problem. A heuristic solution is also presented, and both are tested on randomly generated data and data on the Valley Metro bus network in the Phoenix, Arizona, metropolitan area.