Research On Multiple Depot Vehicle Scheduling Problem Of Urban Bus System Based On The Time-space Network

With the acceleration of urbanization, urban traffic problems, are becoming increasingly serious. As a result, urban bus system has played an important role in solving traffic congestion for its low construction cost and flexibility. By applying multiple depot vehicle scheduling mode, urban bus system enterprise can dispatch vehicles and crew on different bus lines so as to improve the vehicle efficiency and eventually achieve the optimal allocation of resources. Considering the actual situation of urban bus system in our country, the multiple depot vehicle scheduling problem of urban bus system based on a time-space network is studied.Firstly, the concept of multiple depot vehicle scheduling problem of urban bus system is elaborated and its complexity is also analyzed. The relationship between multiple depot vehicle scheduling problem and single depot vehicle scheduling problem is analyzed.Secondly, the network used to depict the multiple depot vehicle scheduling problem of urban bus system is studied and the structure, simplifying method and the corresponding mathematical model of connection-based network and time-space network are demonstrated. The construction steps of a time-space network model are given. Meanwhile, the task-depicting method, connection-depicting method and network scale of the two different models are compared.Thirdly, after analyzing the multiple depot vehicle scheduling problem of urban bus system, the set partitioning model which has taken the departure-duration constraint of buses into consideration is built up based on a time-space network. To solve the model, a branch-and-price-based large neighborhood search algorithm is also designed.Finally, the set partitioning model and the algorithm are verified by an case. Thé result shows that the branch-and-price-based large neighborhood search algorithm is feasible and effective.