Research On Public Bicycle Routing And Scheduling Optimization

At present, as an emerging public transport system, public bike-sharing system(PBS) has flourished in the world. Public bike-sharing not only can take advantage of short trip because of its convenience and flexibility, but also can effectively extend the scope of services of public transport. However, the difficulty in rental and return bicycle in the actual operation has seriously restricted the function of PBS and influenced the development and promotion of PBS.The difficulty in rental and return bicycle is related to urban functional arrangements, distribution of station and travel law. However, efficient scheduling helps to solve this problem. The vehicle scheduling mainly focuses on the stock between stations and center. Scheduling problem contains scheduling demand forecasting and scheduling route optimization problem. This paper focuses on scheduling route optimization problem, and time constraint, vehicle arrangement, changing demand and other factors should be considered. In this paper, scheduling optimization problem is attributable to multiple traveling salesman problems, and will be classified in order to adapt to different scheduling environment. Specifically, this paper mainly studied the following aspects:(1) According to the classification criteria of vehicle routing problem and combining features of scheduling optimization problem, this paper research four types of problems. The type 1 is single-depot PBS scheduling optimization problem without time window. Considering vehicle capacity constraint and driving distance constraint, this paper establishes model to minimize the routing length. At the same time, the model of single-depot PBS scheduling optimization problem is the basis of other types.(2) The second type refers to single-depot PBS scheduling optimization problem with soft time window. In order to improve satisfaction, time window constraint is used to measure scheduling timeliness. It is required to accept certain penalty when scheduling goes beyond the time window constraints. And then, the paper establishes multi-objective constrained model considering minimizing the routing length and maximizing satisfaction. We can obtain the arrival time of each station through an iterative relationship of time.(3) The third type refers to muti-depot PBS scheduling optimization problem with soft time window. This paper weakens the assumptions in the model, that is to say, returning to the original depot is not necessary. The third type achieves the effect on optimizing the number of vehicle and routing length.(4) This paper studies on dynamic-demand scheduling optimization problem through further weakening the assumptions. The timeline and key points are established to transform the dynamic problem into static problem; therefore, this thesis has established the model of dynamic-demand Scheduling optimization. By making appropriate relaxation of constraints or attaching different characteristics, these four types of problem in this paper are closer and close to the actual scheduling problem. The system of scheduling optimization problems is constructed and can satisfy the requirements of different scheduling environment.Based on improved genetic algorithm, this thesis programs in Matlab. Finally, this paper solves the four types of scheduling optimization problem with the public bike-sharing system of 22 stations in Weifang as the case. The efficiency of the algorithm is verified by analyzing calculated results.