| Fault shared bicycle recovery vehicle route optimization is of great significance.Fault shared bikes exist in shared bike parking stations or scattered on the edge of the urban road network,and the recovery is uncertain and larger than the maximum load of a single vehicle,so it is difficult to meet the demand under a single recovery.In this paper,the problem of PVRP recovery of fault shared bikes with uncertain demand is studied.With the goal of minimizing the total driving distance of recovered vehicles,considering the different situations of fault shared bikes at stations and on the side of the road network,a model is established and solved,which provides a theoretical basis for the recovery of fault shared bikes.The main innovative achievements of this paper are as follows.The establishment and solution of the PVRP(Periodic vehicle routing problem)model of fault shared bicycle recovery on the point where the demand is uncertain.Considering the uncertainty of the recovery quantity at the shared bicycle station,with the goal of minimizing the total driving distance of the vehicle,the fault shared bicycle recovery PVRP model of the single vehicle recovery center is established.The robust optimization method is used to deal with the uncertainty of the recovery quantity in the model,and the approximate algorithm GA is designed to solve the driving path of the fault shared bicycle recovery vehicle.It is proved that the time complexity of the algorithm GA is O(n2).Further analysis shows that the maximum approximation ratio of the algorithm is 2λ/(β+1).When the difference of recovery demand between sites is smaller and the number of service sites is more,the approximation ratio of the algorithm is smaller,and the minimum is λ(1+1/n)/(β+1).Finally,an example of fault shared bicycle recovery in the local area of Xi’an Yanta District is taken to analyze the influence of the uncertainty of site recovery demand on the value of objective function and the approximate ratio of the algorithm.The approximate ratio of the algorithm is stable at about 3.5,which shows that the actual application effect of the algorithm GA is better.The establishment and solution of PVRP model of fault shared bicycle recovery on the edge of the urban road network where the demand is uncertain.Considering the uncertain demand of fault shared bicycles on the side,with the goal of minimizing the total driving distance of recovery vehicles,a fault shared bicycle recovery PVRP model of multi-vehicle recovery center is established,and the K-means algorithm based on the maximum handling distance limit is proposed to cluster the scattered fault shared bikes on the edge of the road network to form clustering collection points.Considering the change of the recovery demand on the clustering collection points,the robust optimization method is used to deal with the uncertain recovery quantity,and the approximate algorithm GA*is designed to solve the driving path of the fault-shared bicycle recovery vehicle.It is proved that the time complexity of algorithm GA*is O(n2).Further analysis shows that the maximum approximation ratio of the algorithm is 2λ/(Kγ+1).When the number of vehicles in the recovery center is larger and the number of clustering collection points is less,the algorithm approximation ratio is smaller and the minimum is 2λ/(K+1).Finally,an example of fault shared bicycle recovery in the local area of Weiyang District of Xi’an is taken to analyze the influence of the uncertainty of recovery demand of fault shared bicycle clustering collection point after clustering on the value of objective function and the approximate ratio of the algorithm.The approximation ratio of the algorithm is stable at about 4.5,which shows that the actual application effect of the algorithm GA*is better. |
