不确定需求下故障共享单车回收周期性车辆路径问题研究

doi:10.12341/jssms21208

系统科学与数学 ›› 2022, Vol. 42 ›› Issue (2): 337-354.DOI: 10.12341/jssms21208

不确定需求下故障共享单车回收周期性车辆路径问题研究

徐阳^1,2,3, 周亚南^1,2,3, 黎建强⁴, 苏兵^1,2,3, 张欣^1,2,3

1. 西安工业大学经济管理学院, 西安 710021;
2. 陕西省兵工科技创新发展软科学研究基地, 西安 710021;
3. 陕西高校军民融合科技创新研究中心, 西安 710021;
4. 广东工业大学经济与贸易学院, 广州 510006

收稿日期:2021-04-26 修回日期:2021-08-15 出版日期:2022-02-25 发布日期:2022-03-21
基金资助:
国家社会科学基金项目（20XGL023），陕西省教育科学“十三五”规划课题（SGH20Y1097）.

PDF ( 51 ) 引用

徐阳, 周亚南, 黎建强, 苏兵, 张欣. 不确定需求下故障共享单车回收周期性车辆路径问题研究[J]. 系统科学与数学, 2022, 42(2): 337-354.

XU Yang, ZHOU Yanan, LAI Kin Keung, SU Bing, ZHANG Xin. Period Vehicle Routing Problem for Fault-Shared Bicycle Recycling with Uncertain Demand[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(2): 337-354.

Period Vehicle Routing Problem for Fault-Shared Bicycle Recycling with Uncertain Demand

XU Yang^1,2,3, ZHOU Yanan^1,2,3, LAI Kin Keung⁴, SU Bing^1,2,3, ZHANG Xin^1,2,3

1. School of Economics and Management, Xi'an Technological University, Xi'an 710021;
2. Soft Science Base for Ordnance Industry Innovation Dvelopment in Shaanxi Province, Xi'an 710021;
3. Civil-Military Integration Science and Technology Innovation Research Center of Shaanxi's Colleges and Universities, Xi'an 710021;
4. School of Economics and Commerce, Guangdong University of Technology, Guangzhou 510006

Received:2021-04-26 Revised:2021-08-15 Online:2022-02-25 Published:2022-03-21

为了及时有效地回收城市道路网络中的故障共享单车，对分散于路网边上的故障单车进行聚类形成收集点，考虑聚类收集点上回收需求呈现的不确定性特征，建立以行驶总距离最小为目标的回收周期性车辆路径选择模型.采用基约束鲁棒优化方法，利用有界区间对不确定的回收量进行描述，引入扰动系数和控制系数调节模型的鲁棒性和适应性.针对模型设计近似算法求解，证明近似算法的时间复杂性，分析算法近似比的上下界，用实例验证算法的近似比，结果表明算法性能较好.最后，通过分析回收量发生波动时，即扰动系数和控制系数对目标函数和算法近似比的影响，进一步验证了算法和模型的有效性.

关键词： 需求不确定, 周期性车辆路径, 鲁棒优化, K-means算法, 近似算法

In order to timely and effectively recover the fault shared vehicles in the urban road network, the fault shared vehicles scattered on the edge of the road network are clustered to form collection points. Considering the uncertain characteristics of the recovery demand on the cluster collection points, a recovery periodic vehicle route selection model aiming at minimizing the total distance is established. The basis constrained robust optimization method is adopted, the uncertain recovery is described by bounded interval, and the disturbance coefficient and control coefficient are introduced to adjust the robustness and adaptability of the model. An approximate algorithm is designed to solve the model, the time complexity of the approximate algorithm is proved, the upper and lower bounds of the approximate ratio of the algorithm are analyzed, and an example is used to verify the approximate ratio of the algorithm. The results show that the algorithm has good performance. Finally, the effectiveness of the algorithm and model is further verified by analyzing the influence of disturbance coefficient and control coefficient on the approximation ratio of the objective function and the algorithm.

Key words: Demand uncertainty, period vehicle routing problem, robust optimization, clustering algorithm, approximate algorithm

MR(2010)主题分类:

90B06

分享此文:

[1] Shi L, Zhang Y, Rui W, et al. Study on the bike-sharing inventory rebalancing and vehicle routing for bike-sharing system. Transportation Research Procedia, 2019, 39(7):624-633.
[2] Brinkmann J, Ulmer M W, Mattfeld D C. Dynamic look ahead policies for stochastic dynamic inventory routing in bike sharing systems. Computers & Operations Research, 2019, 106(6):260-279.
[3] Manna C. On-line dynamic station redeployments in bike-sharing systems. AI^*IA 2016 Advances in Artificial Intelligence, 2016, (11):13-25.
[4] 刘明, 徐锡芬, 宁静, 等.基于订单数据分析的共享单车重置调度优化研究.中国管理科学, 2020, (12):1-12. (Liu M, Xu X F, Ning J, et al. Research on rescheduling optimization of shared bicycles based on order data analysis. China Management Science, 2020, (12):1-12.)
[5] Caggiani L, Aleksandra C, Michele O. An equality-based model for bike-sharing stations location in bicycle-public transport multimodal mobility. Transportation Research Part A:Policy and Practice, 2020, 140(1):251-265.
[6] Sohrabi S, Ermagun A. Dynamic bike sharing traffic prediction using spatiotemporal pattern detection. Transportation Research Part D:Transport and Environment, 2021, 90(1):102647.
[7] Qin T X, Liu T, Wu H X, et al. RESGCN:Residual graph convolutional network based free dock prediction in bike sharing system. 202021st IEEE International Conference on Mobile Data Management (MDM), IEEE, 2020, (6):210-217.
[8] Wang X P, Zhao M M, He H H. Reverse logistic network optimization research for sharing bikes. Procedia Computer Science, 2018, 126(8):1693-1703.
[9] 孙一榕, 郑国华.故障共享单车回收站选址库存问题模型及算法. 工业工程与管理, 2020, (4):1-13. (Sun Y R, Zheng G H. Model and algorithm of fault sharing bicycle recovery station location inventory problem. Industrial Engineering and Management, 2020, (4):1-13.)
[10] Kaspi M, Raviv T, Tzur M. Bike sharing systems:User dissatisfaction in the presence of unusable bicycles. AIIE Transactions, 2017, (2):144-158.
[11] 许美贤, 郑琰.城市故障共享单车回收路径优化-以摩拜单车为例. 科学技术与程, 2021, 21(13):10-19. (Xu M X, Zheng Y. Optimization of recovery path of urban fault sharing bikes-taking mobike as an example. Science and Technology and Process, 2021, 21(13):10-19.)
[12] 常山, 宋瑞, 何世伟, 等.共享单车故障车辆回收模型. 吉林大学学报, 2018, (6):1677-1684. (Chang S, Song R, He S W, et al. Shared bicycle failure vehicle recovery model. Journal of Jilin University, 2018, (6):1677-1684.)
[13] Salhi S, Rand G K. Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research, 1993, 66(3):313-330.
[14] 杨俊闯, 赵超. K-Means聚类算法研究综述.计算机工程与应用, 2019, 55(23):9. (Yang J C, Zhao C. A survey of K-Means clustering algorithms. Computer Engineering and Applications, 2019, 55(23):9.)

[1]	郑敏超，孟志青. 两阶段波动价格销售下的最优订购策略研究[J]. 系统科学与数学, 2020, 40(11): 1918-1934.
[2]	张玉忠，苗翠霞. 机器有使用限制的混合恶化排序问题的复杂性[J]. 系统科学与数学, 2015, 35(6): 685-694.
[3]	马建华，房勇，陈晓兰. 区间参数线性规划的稳定决策模型[J]. 系统科学与数学, 2013, 33(12): 1404-1414.
[4]	姜春艳，李改弟. 软容量约束的动态设施选址问题的近似算法[J]. 系统科学与数学, 2012, 32(4): 476-484.
[5]	陈荣军，唐国春. 同类机下的供应链排序及转包策略*[J]. 系统科学与数学, 2012, 32(1): 53-61.
[6]	陈荣军;唐国春. 平行机的供应链排序[J]. 系统科学与数学, 2010, 30(2): 274-282.
[7]	张玲;王晶;黄钧. 不确定需求下应急资源配置的鲁棒优化方法[J]. 系统科学与数学, 2010, 30(10): 1283-1292.
[8]	陈旭瑾;胡捷;胡晓东. 带区间数据的最小风险斯坦纳树问题[J]. 系统科学与数学, 2008, 28(11): 1310-1322.
[9]	帅天平. 几种特殊结构全光网中多播路由的波长分配算法[J]. 系统科学与数学, 2007, 27(6): 837-846.
[10]	谈之奕;何勇. 带机器准备时间的平行机在线与半在线排序[J]. 系统科学与数学, 2002, 22(4): 414-421.

阅读次数

全文

摘要