当用户前往共享单车站点租车而站点无自行车或用户还车而无空桩时,将发生未满足租车或还车服务,造成经营方收益损失.为了优化服务,以包含停运期和营运期、在停运期进行自行车静态调度的共享单车系统为研究对象,调度成本和未满足服务损失成本为目标函数,调度卡车启用、旅行路线及站点间车辆调度为决策变量,营运期站点在站自行车数量为状态变量,综合分析调度策略与站点间租还车需求相互作用引发状态变量变化的动态演化过程,分析调度活动的内在逻辑,构建非线性静态调度优化模型,提出一种线性化方法,将其转化为线性规划模型.然后,根据问题特性设计了一种可求解大规模问题的人工蜂群-贪婪算法.最后,应用数值算例对问题性质和算法性能进行分析,结果显示单位租还车损失成本和调度能力对调度优化效果有重要影响,人工蜂群-贪婪算法在求解大规模问题时具有一定优势.研究成果可为共享单车调度提供决策支持.
Abstract
When users go to the station for bicycle rental or return, if there are no bicycles or parking spaces at the station, it will make the user's rental or return needs unable to be met, resulting in losses to the company. Facing this challenge, this study develops a nonlinear static repositioning optimization model for BSS, which considers two periods, namely operation and shutdown periods. The bike repositioning occurs during shutdown period. In the model, the objective functions include the repositioning costs and unmet service cost, the decision variables are truck activation, travel routes, and vehicle repositioning between stations, and the state variable includes the number of bikes at each station during the operation period. Analyses are conducted on the dynamic evolution process of the state variable, which is caused by repositioning strategy and the interaction of rental and return demands between stations. The internal logic of the repositioning is also analyzed, and a linearization method is employed to linearize the model. Then, an artificial bee colony-greedy algorithm is designed to solve large-scale problems based on the problem characteristics. Finally, numerical examples are used to analyze the problem properties and algorithm's performance. The results show that the unit unmet service cost and repositioning capacity have significant impacts on repositioning optimization. The advantages of the artificial bee colony-greedy algorithm in solving large-scale problems have been verified. This research can provide decision support for the repositioning of BSS.
关键词
共享单车 /
租还车需求 /
静态调度 /
线性化 /
人工蜂群-贪婪算法
{{custom_keyword}} /
Key words
bike sharing system /
rental and return demand /
static repositioning /
linearization /
artificial bee colony-greedy algorithm
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Luo H, Zhao F, Chen W Q, et al. Optimizing bike sharing systems from the life cycle greenhouse gas emissions perspective[J]. Transportation Research Part C: Emerging Technologies, 2020, 117: 102705.
[2] Chen J R, Zhou D, Zhao Y, et al. Life cycle carbon dioxide emissions of bike sharing in China: Production, operation, and recycling[J]. Resources, Conservation and Recycling, 2020, 162: 105011.
[3] Chen Y J, Zha Y, Wang D, et al. Optimal pricing strategy of a bike-sharing firm in the presence of customers with convenience perceptions[J]. Journal of Cleaner Production, 2020, 253: 119905.
[4] Wu C L, Kim I. Analyzing the structural properties of bike-sharing networks: Evidence from the United States, Canada, and China[J]. Transportation Research Part A: Policy and Practice, 2020, 140: 52-71.
[5] Datner S, Raviv T, Tzur M, et al. Setting inventory levels in a bike sharing network[J]. Transportation Science, 2019, 53(1): 62-76.
[6] Legros B. Dynamic repositioning strategy in a bike-sharing system: How to prioritize and how to rebalance a bike station[J]. European Journal of Operational Research, 2019, 272(2): 740-753.
[7] 王鹏飞,王景鹏,刘鹏,等.共享停车系统的泊位供给与运营成本优化研究[J].系统工程理论与实践, 2023, 43(9): 2685-2700.Wang P F, Wang J P, Liu P, et al. Research on the optimization of parking supply and operation cost for shared parking system[J]. Systems Engineering — Theory & Practice, 2023, 43(9): 2685-2700.
[8] 张瑞友,王朝鸣,王德成.考虑充电调度的共享电动汽车调运模型与优化[J]. 系统工程理论与实践, 2021, 41(2): 370-377.Zhang R Y, Wang C M, Wang D C. Modeling and optimization of transportation problem for shared electric-cars with recharging scheduling[J]. Systems Engineering — Theory & Practice, 2021, 41(2): 370-377.
[9] Raviv T, Kolka O. Optimal inventory management of a bike-sharing station[J]. IIE Transactions, 2013, 45(10): 1077-1093.
[10] Zhang D, Yu C H, Desai J, et al. A time-space network flow approach to dynamic repositioning in bicycle sharing systems[J]. Transportation Research Part B: Methodological, 2017, 103: 188-207.
[11] Schuijbroek J, Hampshire R C, Hoeve W J V. Inventory rebalancing and vehicle routing in bike sharing systems[J]. European Journal of Operational Research, 2017, 257(3): 992-1004.
[12] Alvarez-Valdes R, Belenguer J M, Benavent E, et al. Optimizing the level of service quality of a bike-sharing system[J]. Omega, 2016, 62: 163-175.
[13] Erdoğan G, Laporte G, Wolfler Calvo R. The static bicycle relocation problem with demand intervals[J]. European Journal of Operational Research, 2014, 238(2): 451-457.
[14] Dell'Amico M, Iori M, Novellani S, et al. The bike sharing rebalancing problem with stochastic demands[J]. Transportation Research Part B: Methodological, 2018, 118: 362-380.
[15] Maggioni F, Cagnolari M, Bertazzi L, et al. Stochastic optimization models for a bike-sharing problem with transshipment[J]. European Journal of Operational Research, 2019, 276(1): 272-283.
[16] 徐国勋,李妍峰,向婷,等.考虑损坏自行车回收的共享单车调度问题[J].系统工程, 2019, 37(2): 91-99.Xu G X, Li Y F, Xiang T, et al. A bike repositioning problem with broken bikes[J]. System Engineering, 2019, 37(2): 91-99.
[17] 徐国勋,张伟亮,李妍峰.共享单车调配路线优化问题研究[J].工业工程与管理, 2019, 24(1): 80-86.Xu G X, Zhang W L, Li Y F, Research on optimization of shared bicycle repositioning routing problem[J]. Industrial Engineering and Management, 2019, 24(1): 80-86.
[18] 徐国勋,李妍峰,金大祥,等. "红包车"机制下的共享单车调度问题[J].系统工程理论与实践, 2020, 40(2): 426-436.Xu G, Li Y F, Jin D X, et al. A user-based method for the static bike repositioning problem[J]. Systems Engineering — Theory & Practice, 2020, 40(2): 426-436.
[19] 吕畅,张超勇,张道德,等.基于双层禁忌搜索算法的共享单车再平衡问题[J].计算机集成制造系统, 2020, 26(12): 3216-3228.Lü C, Zhang C Y, Zhang D D, et al. Bike-sharing rebalancing problem based on double-layer tabu search algorithm[J]. Computer Integrated Manufacturing Systems, 2020, 26(12): 3216-3228.
[20] Ren Y P, Meng L L, Zhao F, et al. An improved general variable neighborhood search for a static bike-sharing rebalancing problem considering the depot inventory[J]. Expert Systems with Applications, 2020, 160: 113752.
[21] 徐悦甡,周奕杉,黄健斌,等.面向共享单车服务调度的流程规划算法[J].计算机集成制造系统, 2022, 28(10): 3284-3294.Xu Y S, Zhou Y S, Huang J B, et al. Process planning for scheduling task in bike-sharing service[J]. Computer Integrated Manufacturing Systems, 2022, 28(10): 3284-3294.
[22] Dell'Amico M, Hadjicostantinou E, Iori M, et al. The bike sharing rebalancing problem: Mathematical formulations and benchmark instances[J]. Omega, 2014, 45: 7-19
[23] Erdoğan G, Battarra M, Wolflercalvo R. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems[J]. European Journal of Operational Research, 2015, 245(3): 667-679.
[24] 白雪,周支立,钱桂生,等.考虑维修车辆的公共自行车系统再平衡问题[J].系统工程理论与实践, 2018, 38(9): 2326-2334.Bai X, Zhou Z L, Qian G S, et al. Bike rebalancing problem considering broken bike collection[J]. Systems Engineering — Theory & Practice, 2018, 38(9): 2326-2334.
[25] 贾永基, 吴琴. 基于电子围栏的无桩式共享单车重平衡问题研究[J]. 工业工程与管理, 2020, 25(1): 79-86.Jia Y J, Wu Q, Study on free-floating bike sharing rebalancing problem based on electric fence[J]. Industrial Engineering and Management, 2020, 25(1): 79-86.
[26] 刘新宇,陈群.考虑动态多时段借还车需求的城市自行车租赁系统规划模型[J].系统管理学报, 2020, 29(1): 83-91.Liu X Y, Chen Q. Planning model for urban bicycle rental systems considering dynamic multi-period borrowing and returning demands[J]. Journal of Systems & Management, 2020, 29(1): 83-91.
[27] Haider Z, Nikolaev A, Kang J E, et al. Inventory rebalancing through pricing in public bike sharing systems[J]. European Journal of Operational Research, 2018, 270(1): 103-117.
[28] 刘新宇,陈群.综合考量借还车需求与调度成本的公共自行车调度优化模型[J].中国公路学报, 2019, 32(7): 146-157.Liu X Y, Chen Q. An optimization model for bike repositioning in bike-sharing systems considering both demands for borrowing or returning bikes and costs of repositioning operations[J]. China Journal Highway Transport, 2019, 32(7): 146-157.
[29] Regue R, Recker W. Proactive vehicle routing with inferred demand to solve the bike sharing rebalancing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 72: 192-209.
[30] Szeto W Y, Wu Y Z, Ho S C. An artificial bee colony algorithm for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2011, 215(1): 126-135.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
北京市教育委员会科研计划(KM202110037003);教育部人文社会科学研究规划基金(23YJA860004); 河南省高等学校哲学社会科学基础研究重大项目(2024-JCZD-27); 国家自然科学基金(72101033)
{{custom_fund}}
PDF(449 KB)
