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

doi:10.3778/j.issn.1002-8331.2212-0047

摘要/Abstract

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

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

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

郭茂祖, 马力, 赵玲玲. 面向共享单车调配的带约束游牧算法研究[J]. 计算机工程与应用, 2024, 60(7): 325-334.

GUO Maozu, MA Li, ZHAO Lingling. Nomad Algorithm with Constraints Research on Bike-Sharing Allocation[J]. Computer Engineering and Applications, 2024, 60(7): 325-334.

参考文献

[1] 程磊. 城市轨道交通车站周边共享单车需求预测及动态调配研究[D]. 北京: 北京交通大学, 2021.
CHENG L. Research on demand prediction and dynamic allocation of shared bikes around urban rail transit stations[D]. Beijing: Beijing Jiaotong University, 2021.
[2] PFROMMER J, WARRINGTON J, SCHILDBACH G, et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(4): 1567-1578.
[3] 石兵, 黄茜子, 宋兆翔, 等. 基于用户激励的共享单车调度策略[J]. 计算机应用, 2022, 42(11): 3395-3403.
SHI B, HUANG X Z, SONG Z X, et al. User incentive bike-sharing dispatching mechanism[J]. Journal of Computer Applications, 2022, 42(11): 3395-3403.
[4] SCHUIJBROEK J, HAMPSHIRE R C, VAN HOEVE W J. Inventory rebalancing and vehicle routing in bike sharing systems[J]. European Journal of Operational Research, 2017, 257(3): 992-1004.
[5] YAN S, LIN J R, CHEN Y C, et al. Rental bike location and allocation under stochastic demands[J]. Computers & Industrial Engineering, 2017, 107: 1-11.
[6] FRICKER C, GAST N. Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity[J]. Euro Journal on Transportation and Logistics, 2016, 5(3): 261-291.
[7] 李博峰. 城市无桩共享单车需求预测及调度问题研究[D]. 西安: 西安建筑科技大学, 2019.
LI B F. Research on demand prediction and repositioning problem of city’s free-floating bike sharing system[D]. Xi’an: Xi’an University of Architecture and Technology, 2019.
[8] 宋飞宇. 考虑需求动态变化的共享单车调度问题研究[D]. 北京: 北京交通大学, 2021.
SONG F Y. Research on scheduling problem of shared bicycle considering dynamic demand[D]. Beijing: Beijing Jiaotong University, 2021.
[9] 徐长兴. 基于Stacking策略的共享单车需求量组合预测与调度路径优化建模研究[D]. 北京: 北京交通大学, 2021.
XU C X. Short-term travel demand forecast of free-floating shared bicycle based on stacking strategy and dispatching route optimization[D]. Beijing: Beijing Jiaotong University, 2021.
[10] WU X, LIN J, YANG Y, et al. A digital decision approach for scheduling process planning of shared bikes under Internet of things environment[J]. Applied Soft Computing, 2023, 133: 109934.
[11] JIAN N, FREUND D, WIBERG H M, et al. Simulation optimization for a large-scale bike-sharing system[C]//2016 Winter Simulation Conference (WSC). Piscataway, NJ: IEEE, 2016: 602-613.
[12] ZHANG J, MENG M, WANG D Z W, et al. Allocation strategies in a dockless bike sharing system: a community structure-based approach[J]. International Journal of Sustainable Transportation, 2022, 16(2): 95-104.
[13] 何紫齐, 肖磊, 李世隆, 等. 共享单车调度模型和方法综述[J]. 中国自行车, 2022(5): 76-79.
HE Z Q, XIAO L, LI S L, et al. Review on the methods and model of bike-sharing scheduling[J]. China Bicycle, 2022(5): 76-79.
[14] KADRI A A, KACEM I, LABADI K. A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems[J]. Computers & Industrial Engineering, 2016, 95: 41-52.
[15] 苏影. 基于数据分析的共享单车动态调配优化研究[D]. 北京: 北京交通大学, 2019.
SU Y. Research on dynamic allocation optimization of bike-sharing based on data analysis[D]. Beijing: Beijing Jiaotong University, 2019.
[16] AKOVA H, HULAGU S, CELIKOGLU H B. Static bike repositioning problem with heterogeneous distribution characteristics in bike sharing systems[J]. Transportation Research Procedia, 2022, 62: 205-212.
[17] CHEN J, LI K, LI K, et al. Dynamic bicycle dispatching of dockless public bicycle-sharing systems using multi-objective reinforcement learning[J]. ACM Transactions on Cyber-Physical Systems (TCPS), 2021, 5(4): 1-24.
[18] VISHKAEIA B M, MAHDAVI I, MAHDAVI-AMIRI N, et al. Balancing public bicycle sharing system using inventory critical levels in queuing network[J]. Computers & Industrial Engineering, 2020, 141: 106277.
[19] 张建同, 何钰林. 考虑维护的共享单车再平衡问题研究[J]. 工业工程与管理, 2022, 27(4): 142-149.
ZHANG J T, HE Y L. Bike rebalancing problem with maintenance consider[J]. Industrial Engineering and Management, 2022, 27(4): 142-149.
[20] WANG Y, LI Q, GUAN X, et al. Collaborative multi-depot pickup and delivery vehicle routing problem with split loads and time windows[J]. Knowledge-Based Systems, 2021, 231: 107412.
[21] GLEDITSCH M D, HAGEN K, ANDERSSON H, et al. A column generation heuristic for the dynamic bicycle rebalancing problem[J]. European Journal of Operational Research, 2022.
[22] LU Y, BENLIC U, WU Q. An effective memetic algorithm for the generalized bike-sharing rebalancing problem[J]. Engineering Applications of Artificial Intelligence, 2020, 95: 103890.
[23] LIN N, FU L, ZHAO L, et al. A novel nomad migration-inspired algorithm for global optimization[J]. Computers and Electrical Engineering, 2022, 100: 107862.
[24] CHEN Z, HU Y, LI J, et al. Optimal deployment of electric bicycle sharing stations: model formulation and solution technique[J]. Networks and Spatial Economics, 2020, 20(1): 99-136.
[25] 汪慎文, 杨锋, 徐亮, 等. 离散差分进化算法求解共享单车调度问题[J]. 郑州大学学报(工学版), 2019, 40(4): 48-53.
WANG S W, YANG F, XU L, et al. Discrete differential evolution algorithm for solving free-floating bike-sharing system scheduling problem[J]. Journal of Zhengzhou University (Engineering Science), 2019, 40(4): 48-53.
[26] NAVARRO M A, OLIVA D, RAMOS-MICHEL A, et al. An analysis on the performance of metaheuristic algorithms for the estimation of parameters in solar cell models[J]. Energy Conversion and Management, 2023, 276: 116523.
[27] VAROL ALTAY E. Hybrid Archimedes optimization algorithm enhanced with mutualism scheme for global optimization problems[J]. Artificial Intelligence Review, 2022: 1-62.