Research Of Vehicle Scheduling Based On Stochastic Travelling Times

In the public transit, the vehicle (including bus, tram, BRT, light rail, metro and train etc.) scheduling problem (VSP) refers to the allocation of the given trips in a timetable to a fleet of vehicles, aiming to minimize the fleet size and operating cost. The trips in the timetable represents the scheduled service to be provided to the public:the headways are determined based on the passengers'demand, while the durations (scheduled trip times) of the trips are determined by the travel time of buses on the service route. In the traditional VSP, the scheduled trip times are assumed to be fixed. However, due to the complex circumstances in the real-world operation, the bus running times on the trips are stochastic, and therefore, the pre-compiled schedules are to some extend hard to be adhered to in real-world operation. Improving the on-time performance of the schedule, while using reasonable cost, is helpful to the bus companies to regular their service. More essentially, with higher on-time performance, the reliability of bus service, as well as the level of service can be improved, which can increase the attractiveness of bus service in the perspective of passengers.In the traditional VSP with fixed trip times, the scheduled trip times (STs) are essential parameters which greatly affect the schedule cost and the on-time performance. The setting of STs is non-trivial work which often frustrates the schedulers. Moreover, the schedule cost and on-time performance are hard to be balanced. Therefore, this paper combines the methods of analyzing the Automatic Vehicle Location (AVL) data in the bus service reliability area with the vehicle scheduling, aiming to compile vehicle schedules with more balanced on-time performance and cost. The research in this paper includes three subjects:(1) With the purpose of improve the process of bus planning and operation in China, we propose a process of vehicle scheduling based on AVL data. In the process, a method for processing the raw AVL data is designed. Methods for partitioning time periods and optimizing the ST parameters are devised, which can support the traditional VSP method. Based on the real-world instances of Haikou Bus Route 4 and Shiyan Bus Route 4, the proposed methods are verified.(2) Research on the vehicle scheduling based on variable trip times. Firstly, the fixedST in each trip given in the timetable is replaced by a variable trip time range, which can be set based on the AVL data. Meanwhile, an expected trip time is set according to the level of on-time performance designated in advance by schedulers or in the service policy. Then the model of VSP based on variable trip time is built, the objective of which is to minimize the total cost (including the fixed cost of vehicles and the operating cost) as well as to achieve the expected on-time performance. Experimental results based on real-world AVL data show that the proposed vehicle scheduling method based on variable trip times can improve the on-time performance of resulting schedules without increasing the fleet size. Besides, the parameters in the newly proposed model are easier to set compared with that in the traditional VSP models since their influence on the fleet size is less sensitive.(3) Research on VSP with stochastic trip times. The duration of each trip is treated as a stochastic variable, which follows a given probability distribution, which can be abstracted from the AVL data. With the stochastic trip times, an adapted network flow for the VSP is proposed. The compatible probability is defined to determine the existence of any trip-link arc, and the cost of each arc is redefined as well. Furthermore, the infeasibility of each arc is penalized to improve the on-time performance. Finally, a probabilistic model for VSP based on stochastic trip times is built, and further extended by considering the delay propagation. Based on real-world instance, the proposed models are verified, the experimental results show that the probabilistic models of VSP based on stochastic trip times can increase the on-time performance of resulting schedule significantly, while without increasing the fleet size. Featuring the delay propagation, the on-time performance of resulting schedule can be further improved. Meanwhile, the fleet size will remain the same and the operating cost will be slightly compromised. Besides, the trip time distributions adopted by the VSP model based on stochastic trip times can be abstracted from the AVL data, therefore the work of setting of scheduled parameters can further reduced, which would relieve the schedulers'pressure in the real-world practices.