Abstract: The bike-sharing allocation is an important way to optimize the urban traffic resources rebalancing, but the current optimal-route allocation method is sensitive to the bike system magnitude. Therefore, a time-based and inter-regional bike-sharing allocation method is researched, and the nomad algorithm with constraints (NCA) is proposed to obtain the optimal allocation solution. Firstly, with the bike flow as the constraints and the minimal operation loss as the target, the allocation problem is modeled as a multi-constrained objective optimization problem. Then, NCA is proposed to predict the optimal bike inventory in the stations and the transfer amount among the stations. Compared with the original nomadic algorithm without constraint thinking, NCA improves the local search strategies and the global optimization strategies, and optimizes the tribe generation methodology. Finally, based on the predicted inventory and transfer amount, the interregional allocation scheme in different time periods is obtained. The comparative experimental results on the relevant datasets in Shanghai and New York show that the running time is about 15% of other methods. The demand response rate is 0.15% higher than the branch-and-bound algorithm. The bike quantity and the operating losses are reduced by about 10% compared to the genetic algorithm. It can be seen that the proposed method has higher optimization efficiency and user demand response rate.

Key words: traffic resources rebalancing, bike-sharing allocation, nomad algorithm, multi-constraint objective optimization

摘要： 共享单车调配是优化城市交通资源配置的重要手段，但目前的最优路径调配方法往往对单车系统规模敏感。为此，研究一种分时段、区域间调配的共享单车投放方法，提出了带约束的游牧算法（nomad algorithm with constraints，NCA）求解调配模型的最优解。将单车调配问题建模为以单车流量为约束、以最小化运营损耗为目标的优化问题；提出求解上述模型的NCA算法，预测投放区域单车存量和区域间转移量，相比无约束的原游牧算法，改进了局部搜索和全局寻优策略，优化了部落初定位方法；基于预测的存量和转移量得出分时段区域间单车的调配方案。在上海和纽约相关数据集上的对比实验结果表明，运行时长约为其他方法的15%，租赁需求响应率高于分支定界算法0.15%，单车总数和运营损耗比遗传算法降低了约10%，验证了该方法具有更高的优化效率和用户需求响应率。

关键词: 交通资源配置, 共享单车调配, 游牧算法, 多约束目标优化