考虑维护的共享单车再平衡问题研究

Bike Rebalancing Problem with Maintenance Consider

共享单车的运营管理面临单车的供需不匹配和单车故障的问题。针对这两方面问题,对共享单车再平衡进行研究,同时在再平衡过程中进行故障单车的维护。提出了两阶段方法:先由巡检人员检修轻度故障单车和回收严重故障单车到调度节点,再由调度车在调度节点间调配单车和回收严重故障单车。提出多阈值的密度聚类算法以找出单车停放热点区域作为调度节点,利用泰森多边形的方法划分巡检区域,提出启发式算法和精确算法相结合的分支定价算法求解调度模型。数值实验结果表明提出的算法有较好性能。灵敏度分析结果表明,巡检区域密度阈值和调度车容量的不同对巡检调度的成本和效率产生影响。

The operation and management of bike-sharing system are faced with the problem of mismatch between the supply and demand of bikes as well as the problem of faulty bikes. In order to solve these two problems,this paper studied the rebalancing of shared bikes,and carried out the maintenance of faulty bikes in the process of rebalancing. A 2-stage method was put forward. First,the faulty bikes were repaired or repossessed to the rebalancing nodes by the inspectors,and then the vehicles rebalance bikes between rebalancing nodes,and in this process,the faulty bikes at the rebalancing nodes were also repossessed by the vehicle. Inspectors would carry out in-place repair for the bikes with slight faults,and the seriously defective bikes would be repossessed to the rebalancing node. Besides,a multi-threshold density-based clustering algorithm was proposed to find out the hot spots of bike parking as the rebalancing nodes,Tyson polygon method was used to divide the inspection area,and a branch pricing algorithm combining heuristic algorithm and precise algorithm was proposed to solve the rebalancing model. Finally, the result of numerical experiment proved the good performance of the proposed algorithm and showed that the different regional density threshold and the different capacities of vehicles would affect the cost and efficiency of inspecting and rebalancing.