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.