Research On The Repositioning Problem In Bike Sharing Systems Based On Exact Algorithm

Bike sharing systems solve the "last mile" travel problem in cities,not only in line with the concept of green travel,but also improve the urban public transportation system,becoming the third largest urban public travel mode in my country after public transportation and taxis.As the competition model of the bike sharing industry gradually changes from scale expansion to refined operation,and the development is more standardized,an efficient repositioning system has become the key for bike sharing companies to gain an advantage in market competition.The shared bicycle repositioning system can help companies formulate a reasonable scheduling plan,which is beneficial to improve the operation efficiency of the entire bike sharing system,reduce operating costs,and improve consumer satisfaction.Therefore,in order to further improve the operation level and efficiency of bike sharing systems,how to effectively improve the solution efficiency of the repositioning problem in bike sharing systems has a significant impact on the development of the bike sharing industry.This paper studies the repositioning problem in bike sharing systems and its extension problem,and comprehensively uses theories and methods such as the vehicle routing theory,the shortest path theory,the exact algorithm,and analyzes the repositioning problem in bike sharing systems from the perspectives of problem description,model construction,algorithm design,and sub-problem solving.The repositioning issue is discussed more comprehensively and in depth.The main research work of this paper is as follows.(1)This paper explores the repositioning problem in bike sharing systems with inseparable demand,and designs a method to solve the the repositioning problem in bike sharing systems with inseparable demand by the variable neighborhood simulated annealing algorithm and branch-and-price algorithm.Construct an arc-flow model with single dispatch center,multiple demand points and several dispatch vehicles of the same model as the background.Using Danzig-Wolfe decomposition method to refactor the model into set covering main problem and elementary shortest path problem with resource constraints.Based on the loss-saving algorithm to generate the initial solution of the problem,the variable neighborhood simulated annealing algorithm is used to further optimize the initial solution of the problem.For the pricing sub-problem,a labelsetting algorithm and a corresponding heuristic label-setting algorithm are proposed to solve it.The effectiveness and feasibility of the proposed method are verified by simulation experiments.(2)The repositioning problem in bike sharing systems with split demand is explored,and the label-setting algorithm,the optimal sequence algorithm for picking up and delivering bicycles,and the branch strategy are designed to solve the repositioning problem in bike sharing systems with split demand.Combined with the actual scenario of bike repositioning systems,it relaxes the constraint that "a demand point can only be visited once by one dispatcher",which an arc-flow model is constructed with single dispatch center,multiple demand points and several dispatch vehicles.According to the characteristics of the pricing sub-problem,it is decomposed into a resource-constrained elementary shortest path problem and a multi-stage knapsack problem.A heuristic label-setting algorithm is designed to solvethe repositioning problem in bike sharing systems with split demand.Simulation experiments show that the proposed algorithm is superior to other comparative algorithms in terms of solution scale and solution time.(3)On the basis of the first two problem backgrounds,the complexity of the research problem is expanded.The tabu search algorithm,the effective inequality separation algorithm and the branch-and-price-and-cut algorithm are designed to solve the repositioning problem in bike sharing systems with multi-dispatch centers,multitype dispatch vehicles,and split demand.Constructing an arc-flow model for the problem and designing a branch-and-price-and-cut algorithm to solve it.In order to improve the convergence speed of the algorithm,three kinds of valid inequalities are introduced to improve the lower bounds of the problem.360 examples are used to verify the effectiveness of the proposed method.Simulation experiments show that the proposed tabu search algorithm can speed up the solution speed of the column generation algorithm.This paper studies the repositioning problem in bike sharing systems with integral demand and split demand,followed by expansion of the complexity of the problem,t the repositioning problem in bike sharing systems with multi-dispatch centers,multitype dispatch vehicles,and split demand.This paper build models and designs exact algorithms for the above three problems respectively.Finally,the above three models and algorithms considering different repositioning conditions are applied to the actual case of Changning District,Shanghai,to solve the optimal repositioning scheme under different repositioning conditions,and obtain relevant management enlightenments.