Research On Multi-Objective Bike-Sharing Rebalancing Problem

The bike-sharing system(BSS),as a sustainable way to solve the “first and last mile” problem of mass transit systems,is increasingly popular among users due to its convenient usage,low rental price,and green environmental protection.In the BSS,the “tidal phenomenon” caused by commuting and the one-way nature of bicycles will cause an imbalance between the bicycles’ supply and demand.Thus,the inability to meet the demand will decrease user’s satisfaction,meanwhile,the utilization rate of bicycles is also greatly reduced,which is not conducive to the development of bicycle companies and the rapid operation of the existing transportation system.Therefore,bikesharing rebalance has become an important solution to complete the matching of supply and demand,and the reasonable completion of which is also an urgent problem for urban BSS.Based on these,this article studies the bike-sharing rebalancing problem.The main content and results are as follows:Firstly,we redefine the balance state of the stations and extend it from the point to the interval.Based on this,we deal with the bike-sharing rebalancing problem with balance intervals(BRP-BIs).Then,we formulate the BRP-BI as a bi-objective mixed-integer programming model with the aim of determining both the minimum cost route for a single capacitated vehicle and the maximum average rebalance utility,an index for the balanced degree of station.Then,a multi-start multiobjective particle swarm optimization(MS-MOPSO)algorithm is proposed to solve the model such that the Pareto optimal solutions can be derived.The proposed algorithm is extended with crossover operator and variable neighborhood search to enhance its exploratory capability.Compared with the HNSGA-Ⅱ and MOPSO,the computational experiment results demonstrate that our MS-MOPSO can obtain Pareto optimal solutions with higher quality.Secondly,on the basis of the research with single-vehicle,this article is extended to multivehicle transportation research,which also bases on the balance interval.A multi-objective mixed integer programming model is constructed to minimize the total cost of rebalancing operations and maximize the average rebalancing utility,solving by the hybrid multi-objective particle swarm optimization(HMOPSO)algorithm,which introduces k-means clustering algorithm in the initial solution generation,which clusters unbalanced stations and assigns the results to different vehicles.At the same time,CPLEX is called to find the shortest path for each vehicle,which is used as the path information of one of the particles.To verify the algorithm’s performance,examples of different scales are analyzed and compared with HNSGA-Ⅱ,whose initial solutions are generated randomly.The results show that the HMOPSO algorithm performs better.Finally,considering the uncertainty of demand in real life,this paper also studies the rebalancing problem under random demand.The randomness is transformed into each scenario with probability.With the goal of minimizing the distance of driving route and maximizing the expected utility obtained by completing the rebalancing operations of all scenarios,a two-stage stochastic planning model is constructed,solving by the hybrid variable neighborhood search algorithm which adopting the Latin Hypercube of sampling to generate scenarios(LHS-VNS).At the end,some numerical examples are given to demonstrate the effectiveness of the algorithm.