面向共享单车调配的带约束游牧算法研究  

Nomad Algorithm with Constraints Research on Bike-Sharing Allocation

作　　者：郭茂祖 马力 赵玲玲[3] GUO Maozu;MA Li;ZHAO Lingling(School of Electrical and Information Engineering,Beijing University of Civil Engineering and Architecture,Beijing 100044,China;Beijing Key Laboratory of Intelligent Processing for Building Big Data,Beijing University of Civil Engineering and Architecture,Beijing 100044,China;Faculty of Computing,Harbin Institute of Technology,Harbin 150001,China)

机构地区：[1]北京建筑大学电气与信息工程学院,北京100044 [2]北京建筑大学建筑大数据智能处理方法研究北京市重点实验室,北京100044 [3]哈尔滨工业大学计算学部,哈尔滨150001

出　　处：《计算机工程与应用》2024年第7期325-334,共10页Computer Engineering and Applications

基　　金：国家自然科学基金(61871020);北京市属高校高水平创新团队建设计划项目(IDHT20190506)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]