Abstract: Bike Sharing system needs to solve the rebalancing of supply and demand of each shared station,which is a complex NP-hard problem.Aiming at the characteristics of Bike Sharing system,a station blocking strategy based on supply and demand relationship was proposed,and a double-layer tabu search algorithm based on supply and demand block strategy was designed to solve the problem.In the supply and demand block strategy,through the pairing between the supersaturated station and the insufficient station,a self-sufficient station set was formed.The double-layer tabu search was performed based on all the block station set and the station set itself respectively.Through a nested mutation operator,the information exchange between the two layers of search was enhanced,which could improve the search capabilities of the algorithm as well as the diversity.The proposed algorithm solved the international benchmark problem of Bike Sharing Rebalancing.The experimental results showed that the proposed algorithm could obtain the optimal solution within 150 stations in less than 100 seconds,which reduced the turnover by more than 80% while reducing the number of vehicles required for operation to less than 5.Compared with similar algorithms,it showed significant advantages in the solution of objective function and CPU consumption.

Key words: bike sharing rebalancing problem, supply and demand relationship, tabu search, mutation operator

摘要： 共享单车系统需解决各个共享站点的供需平衡,这是一个复杂的NP-hard问题。针对共享单车系统的特点,提出一种基于供需关系的站点分块策略,并结合所提模型设计了相应的双层禁忌搜索算法进行求解。供需关系分块策略通过不足站点和过饱和站点之间的配对形成能自给自足的站点集;双层禁忌搜索算法分别基于分块站点集和站点集内部进行双层禁忌搜索,并通过一个嵌套变异算子,增强两层搜索间的信息交流,在提高算法搜索能力的同时增添解的多样性。应用提出算法求解共享单车再平衡国际基准实例,实验结果显示提出算法能在100s内获得150站点以内的较优解,降低作业周转库存80%以上,同时减少作业所需货车数至5辆以内。与同类算法对比,在目标函数求解结果和算法求解时间上均表现出显著优越性。

关键词: 共享单车再平衡问题, 供需关系, 禁忌搜索, 变异算子