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

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