Research On Optimal Scheduling Of Vehicle Sharing System

Vehicle sharing system has got fast development in recent years. Owing to its wonderful feature, energy conservation and environment protection, low-carbon green and flexibility, it has vigorously promoted by the government and the society. The use of sharing vehicles (bicycles, cars, electro car) has becoming an important supplement for the choices of urban traffic.The third generation urban public bicycle system, which was originated from Europe,was more and more popular among the public because of the consistently improvement and evolution. An efficient public bike system is not only rely on the reasonable planning, the layout of rent points and a reasonable number of settings at the lease point parking pile, but also closely related with public bicycle manual distribution. Rational manual distribution can realize the inventory balance of whole bicycle sharing system, satisfying the customer and attracting more potential clients to make the whole system equilibrium and benign development. So, the exploration and optimization of public bicycle redistribution strategy has a great research value and practical significance.Firstly, this paper based on the characteristics of static public bicycle vehicle scheduling, and take the vehicle routine problem with simultaneous pickup and delivery (VRPSPD) as the prototype to research public bicycle redistribution problem during night. It regards the realization of system equilibrium as the ultimate goal, and the objective function is established with the minimum transport costs. Secondly, in view of typical public bicycle system unbalanced nature of spatial and temporal distribution during peak periods, this paper put forward a kind of emergency pre-scheduling strategy. Conduct the pre-scheduling for each node in a certain period of time before the peak period, and priority access key nodes. For this strategy an optimization model based on the vehicle routing problem with profit were established.Aiming at the problems mentioned above, a branch-and-price algorithm is used to solve them in this paper. Branch and price algorithm is a generalized branch and bound algorithm which embedded column generation technology in every branch and bound node. The column generation algorithm can decompose a large scale variable linear programming problem into a master problem which is equivalent to the original question and a series of pricing sub-problems that usually have efficient solution algorithms. Through the rapid solution of the pricing sub-problem, the cyclic iteration is carried out between the master problem and sub-problem and finally get the solution of the original problem.In the process of using branch and price algorithm to solve the two models mentioned above, this paper first transform the established mixed integer programming model into a set partitioning model. And then set partitioning model as the master problem of the column generation algorithm. The scheduling optimization problem studied in this paper, its pricing sub-problems performance as a resource constraint elementary shortest path problem (RCESPP).This paper adopts a bidirectional dynamic programming algorithm to solve this problem. Due to the characteristics of public bicycle scheduling, single variety commodity and combined use of pickup delivery, this paper take pickup quantity and delivery volume as the key resource constraints in solving the static scheduling model. When solving the emergency scheduling (peak pre-distribution) model, because of the required timeliness of this model, the exercise time will be added into the key resources. Through the use of the key resource in domination rule and state length limitation technology, this algorithm effectively controls the undominated state scales, and validly improve the speed. Through the vast of experiments, the validity of the branch and price algorithm in small and medium scale numerical example has been verified.