Research On Static Rebalancing Problem Of Bicycle Sharing System

With the rapid development of the social economy,the number of cars has increased rapidly,which has caused a series of urban problems such as traffic congestion and air pollution.The shared bicycle is an effective way to solve these problems and brings convenience for citizens' short trips,which is in accordance with the national green environmental protection policy.However,the imbalance in the number of bikes will reduce the utilization rate of the bikesharing system to some extent.It is required that the operators should rebalance the number of shared bikes at each site according to the historical usage.In this thesis,the bicycle rebalancing problem is studied,and the main work is as follows:The single vehicle and multi visit static bicycle rebalancing problem,which is NP hardness,is studied.Cruz et al.proposed the ILS algorithm to solve the problem in 2017 and obtained good results.However,the structure of the algorithm is complex.It takes lots of time to execute the repair operator.Moreover,due to the high possibility of getting a bad solution after repairing,the optimization results may be affected.To solve this problem,a method P-SMSBR based on parthenogenetic algorithm is proposed,which adopts a more concise optimization process.In this method,decimal code is used to present a vehicle route,seven mutation operators are introduced to participate in the evolution,and elite strategy is used to enhance the search ability of the algorithm.A large number of simulation data and real urban data were used to test and compare the optimization performance of the ILS and the P-SMSBR algorithms.Experimental results show that the P-SMSBR algorithm can obtain a shorter vehicle path scheme in a shorter time than the ILS algorithm,and the advantages of the P-SMSBR algorithm are more significant with the increase of the number of stations.In order to further enhance the hill-climbing ability of the P-SMSBR algorithm,a heuristic algorithm CPS,solving the single vehicle and multi visit static bicycle rebalancing problem,was proposed by combining the simulated annealing algorithm with parthenogenetic algorithm.The simulated annealing algorithm's temperature is used to control the evolution iteration.It starts from a certain initial temperature,and finds the global optimal solution by using the characteristic of probabilistic jump with the decrease of the temperature.The same experimental test data sets were used to compare the optimization performance of algorithms ILS,P-SMSBR and CPS.Experimental results show that the CPS algorithm can obtain a shorter scheduling path than the ILS and P-SMSBR algorithms with the increase of the number of stations.An application software for scheduling the shortest vehicle route was designed based on algorithms P-SMSBR and CPS.The software was developed using Java language.The main functions include such four modules as deployment design,recording operations,brief introduction and about the product.The module of deployment design is the core part of the software,which integrates the shortest path design scheme of algorithms P-SMSBR and CPS.The module of recording operations is used to save the results of the corresponding design scheme.The brief introduction module mainly introduces the precautions of using the software.The “about” module introduces the information of the development team and their contact way,so as to provide technical support later.In conclusion,the static rebalancing problem of bike-sharing system is studied,and two effective algorithms P-SMSBR and CPS are proposed to solve the single vehicle and multi visit static subproblem.A relevant application software is designed.All of these work will further promote the optimization and development of bike-sharing system.