A construction-and-repair based method for vehicle scheduling of bus line with branch lines. (April 2023) - Liu, Yahong; Zuo, Xingquan; Ai, Guanqun; Zhao, Xinchao
Abstract: Bus vehicle scheduling is vital to reduce operational cost and ensure service quality for bus companies. Bus Vehicle Scheduling Problem of a bus line with Branch Lines (VSP-BL) is common in practice, but there is no study on this problem. In this paper, we propose a Construction-and-Repair based Method (C&RM) to solve the problem. In addition, existing studies seldom consider bus driver scheduling and rostering factors in vehicle scheduling problem, thus that the solution to the problem is hard for driver scheduling and rostering. To address this dilemma, we take driver scheduling and rostering factors into account in the solution method. C&RM includes two stages: The first stage uses a trip assignment strategy to assign timetabled trips to vehicles to construct a solution. Vehicle scheduling and some driver scheduling constraints are considered in this stage. If the constructive solution dose not satisfy all driver scheduling constraints, the second stage adopts a repair method to improve the solution to satisfy all the vehicle scheduling and driver scheduling constraints. Experimental results show that C&RM outperforms the comparative methods on the number of vehicles and in balancing vehicles' driving tasks; moreover, the solution found by C&RM satisfies all the constraints of driver scheduling and rostering, which facilitates driver scheduling and rostering. Highlights: A Vehicle Scheduling Problem for bus line with Branch Lines (VSP-BL) is studied. The VSP-BL considers practical constraints of driver scheduling and rostering. A construction-and-repair based method (C&RM) is proposed to solve VSP-BL. C&RM is applied to a real-world problem and compared against other methods.