考虑多仓库的共享单车重新配置问题研究

doi:10.12005/orms.2021.0018

运筹与管理 ›› 2021, Vol. 30 ›› Issue (1): 121-129.DOI: 10.12005/orms.2021.0018

考虑多仓库的共享单车重新配置问题研究

孙卓¹, 李一鸣²

1.大连海事大学交通运输工程学院,辽宁大连 116026;
2.大连海事大学航运经济与管理学院,辽宁大连 116026

收稿日期:2019-03-23 出版日期:2021-01-25
作者简介:孙卓(1979-),男,辽宁大连人,教授,博士生导师,研究方向:物流系统优化与仿真;李一鸣(1993-),男,广东深圳人,博士研究生,研究方向:交通运输系统规划与设计。
基金资助:
国家自然科学基金资助项目(61304179,71831002);教育部人文社会科学研究青年基金项目(19YJC630151);大连市科技创新基金项目(2020JJ26GX023);辽宁省自然科学基金(2020-HYLH-32);辽宁省社会科学规划基金项目(L19BGL011)

Solving a Static Bike Repositioning Problem with Multiple Depots

SUN Zhuo¹, LI Yi-ming²

1. Transportation Engineering College, Dalian Maritime University, Dalian116026, China;
2. School of Maritime Economics and Management, Dalian Maritime University, Dalian 116026, China

Received:2019-03-23 Online:2021-01-25

摘要/Abstract

摘要： 共享单车是我国大力提倡的低碳交通出行模式,加快共享单车发展是解决最后一公里、城市拥堵和环境污染等问题的重要途径。由于人们停放共享单车的无规律性,使得共享单车系统中各车桩的单车库存量存在不平衡。如何合理的对车桩中的单车进行重新调配,来满足用户的需求,是相关企业亟待解决的问题。共享单车的调配路线优化是优化车桩库存量的重要手段之一。本文研究多仓库条件下的货车调配路线优化问题,建立了一个混合整数非线性规划模型。不同于传统的路径优化问题的研究大多是以成本或时间为目标,本文采用基于车桩库存量的非线性惩罚函数来表示用户需求,从而使得所研究的问题是一个凸函数优化问题。为了简化本文的问题,将目标函数分段线性化。基于车桩网络的特点,设计了变邻域搜索算法,以及构建初始解的贪婪算法。最后,以某共享单车公司为例,进行算例分析,来说明模型和算法的合理性和有效性。

关键词: 多仓库, 共享单车, 路线优化, 变邻域搜索

Abstract: Shared bike has been developing rapidly in China, encouraging people to cycle and use this low-carbon transport mode to make trips. Accelerating the development of shared bikes is an important way to solve the last mile, urban congestion and environmental pollution problems. With the irregularity of people parking share bikes, the station inventory is unbalanced in the shared bike system. How to optimize the station inventory to meet user demand that must be solved by related companies. The repositioning routing optimization of shared bikes is a key mean to realize the reasonable inventory level at stations. This paper investigates a static bike repositioning problem (SBRP) with multiple depots, and a mixed-integer nonlinear programming model is proposed. Different from the objective function of cost or time used in the path optimization problems, this paper uses the nonlinear penalty objective functions based on station inventory to describe user demand, leading to a convex optimization problem. In order to simplify our problem, we utilize a piecewise linear function to linearize the objective function. Based on characteristics ofstationnetwork,avariableneighborhoodsearchalgorithm(VNS)andagreedyalgorithmforconstructing the initial solutions are designed to solve our problem. Finally, a case study of a shared bike company is presentedtoaccountfortherationalityandeffectivenessofthemodelandalgorithm.

Key words: multiple depots, shared bike, routing optimization, VNS

中图分类号:

F253.4

孙卓, 李一鸣. 考虑多仓库的共享单车重新配置问题研究[J]. 运筹与管理, 2021, 30(1): 121-129.

SUN Zhuo, LI Yi-ming. Solving a Static Bike Repositioning Problem with Multiple Depots[J]. Operations Research and Management Science, 2021, 30(1): 121-129.

参考文献

[1] 王梅.城市公共自行车发展迷思[J].交通与港航,2016,3(2):23-32.
[2] Al-Thalej A, Yassen E T, Al-Khateeb B. Hybrid quantum genetic algorithm for vehicle routing problem with time window[J]. Jour of Adv Research in Dynamical & Control Systems, 2018, 10(13).
[3 ] Hatamlou A. Solving travelling salesman problem using black hole algorithm[J]. Soft Computing, 2018, 22(24): 8167-8175.
[4] Hernández-Pérez H, Salazar-González J J, Santos-Hernández B. Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem[J]. Computers & Operations Research, 2018, 97: 1-17.
[5] Euchi J. Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem[J]. Journal of Modelling in Management, 2017.
[6] Nair R, Miller-Hooks E. Fleet management for vehicle sharing operations[J]. Transportation Science, 2011, 45(4): 524-540.
[7] Contardo C, Morency C, Rousseau L M. Balancing a dynamic public bike-sharing system[M]. Montreal, Canada: Cirrelt, 2012.
[8] Benchimol M, Benchimol P, Chappert B, et al. Balancing the stations of a self service “bike hire” system[J]. RAIRO-Operations Research, 2011, 45(1): 37-61.
[9] Chemla D, Meunier F, Calvo R W. Bike sharing systems: solving the static rebalancing problem[J]. Discrete Optimization, 2013, 10(2): 120-146.
[10] 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.
[11] Erdo ğan G, Laporte G, Calvo R W. The static bicycle relocation problem with demand intervals[J]. European Journal of Operational Research, 2014, 238(2): 451-457.
[12] Li Y, Szeto W Y, Long J, et al. A multiple type bike repositioning problem[J]. Transportation Research Part B: Methodological, 2016, 90: 263-278.
[13] 徐国勋,李妍峰,李军,徐冠宇.多类型公共自行车调运问题[J].运筹与管理,2019,28(1):116-124.
[14] Shui C S, Szeto W Y. Dynamic green bike repositioning problem-A hybrid rolling horizon artificial bee colony algorithm approach[J]. Transportation Research Part D: Transport and Environment, 2018, 60: 119-136.
[15] Liu Y, Szeto W Y, Ho S C. A static free-floating bike repositioning problem with multiple heterogeneous vehicles, multiple depots, and multiple visits[J]. Transportation Research Part C: Emerging Technologies, 2018, 92: 208-242.
[16] Ho S C, Szeto W Y. Solving a static repositioning problem in bike-sharing systems using iterated tabu search[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 69: 180-198.
[17] Raviv T, Tzur M, Forma I A. Static repositioning in a bike-sharing system: models and solution approaches[J]. EURO Journal on Transportation and Logistics, 2013, 2(3): 187-229.
[18] Raviv T, Kolka O. Optimal inventory management of a bike-sharing station[J]. IIE Transactions, 2013, 45(10): 1077-1093.
[19] Meng X, Li J, Dai X, et al. Variable neighborhood search for a colored traveling salesman problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(4): 1018-1026.
[20] Nucamendi-Guillén S, Angel-Bello F, Martínez-Salazar I, et al. The cumulative capacitated vehicle routing problem: new formulations and iterated greedy algorithms[J]. Expert Systems with Applications, 2018, 113: 315-327.

[1]	赵道致, 王迪. 基于降低失效停放区比率的共享单车系统稳定性研究[J]. 运筹与管理, 2021, 30(5): 60-65.
[2]	张建同, 丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题[J]. 运筹与管理, 2019, 28(11): 77-84.
[3]	刘佳, 王书伟. 顺序相依拆卸线平衡多目标优化模型及算法研究[J]. 运筹与管理, 2018, 27(6): 82-90.
[4]	陈久梅, 邱晗光. 两级定位-路径问题模型及变邻域粒子群算法[J]. 运筹与管理, 2014, 23(3): 38-44.

考虑多仓库的共享单车重新配置问题研究

Solving a Static Bike Repositioning Problem with Multiple Depots

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics