Abstract: The bicycle sharing system has the advantages of improving urban traffic travel structure and reducing traffic pollution.The relative balance of the number of bicycles at each site is very important for improving the utilization of the sharing system,and the problem of rebalancing bicycle sharing systemis proposed.Since the problem is NP-hard one,Fábio et al.proposed the ILS algorithm for solving the single-vehicle and multiple-visit static bicycle rebalancing case in 2017,and obtained good results.However,the ILS algorithm has very complicated structure,and the repair operator,which consumes a lot of time,has a good chance of generating inferior solution.To solve this problem,in this paper,a partheno-genetic algorithm based method P-SMSBR is presented.Amore concise optimization process is designed,and decimal code is used to represent a vehicle path solution.Seven mutation operators are introduced,and elite strategy is adopted to enhance the search ability of the algorithm.A large number of simulation and real data were adopted to test the performance of the algorithm.The experimental results indicate that the P-SMSBR algorithm proposed in this paper has better optimization effect,which can obtain a shorter vehicle path than that obtained by the ILS algorithm in a shorter time.In addition,the P-SMSBR algorithm shows moresignificant advantages with the increase of the number of sites.It is an effective method for solving the single-vehicle and multiple-visit static bicycle rebalancing problem.

Key words: Bicycle sharing system, Heuristic, NP hard, Partheno-genetic algorithm, Static bike rebalancing problem