基于混合整数线性规划的不可用共享单车回收维修研究
|
摘要
随着共享经济的出现与发展,共享单车系统开始应运而生。扫码骑行,无需寻找固定桩位,极大程度上方便了居民的短距离出行,解决了"最后一公里"的出行问题。随着新鲜事物的出现必然会带来一些问题,在一些站点内会出现多辆不可用的单车,不仅占用了一定的空间,还会影响用户使用的满意度,同时,运营商的利益也会受损。因此,需要对站点的不可用共享单车进行回收再利用。文章就静态条件下的不可用共享单车回收维修问题,通过一定容量的货车来回收这些不可用单车,使得回收的总运输成本最低。在文章中使用混合整数线性规划模型(MILP),并运用分支切割(B&C)算法解决此问题。最后,对上海市五角场商业圈周边调查的数据进行分析并得出结论。
With the emergence and development of the sharing economy, the shared bicycle system began to emerge. Scanning code riding, without the need to find a fixed pile position, which greatly facilitates the short-distance travel of residents and solves the"last mile"travel problem. With the emergence of new things, it will inevitably bring some problems. In some sites, there will be many unusable bicycles,which will not only occupy a certain space, but also affect the satisfaction of users. At the same time, the interests of operators will also damage. Therefore, it is necessary to recycle and reuse the unavailable shared bicycles of the site. This paper discusses the problem of unusable shared bicycle recycling maintenance under static conditions. The recovery of these unusable bicycles by a certain capacity of the truck makes the total transportation cost of recycling the lowest. A mixed integer linear programming model(MILP) is used in the paper and a branch-and-cut(B&C) algorithm is used to solve these problems. Finally, the data of the survey around the Wujiaochang in Shanghai were analyzed and conclusions were drawn.
With the emergence and development of the sharing economy, the shared bicycle system began to emerge. Scanning code riding, without the need to find a fixed pile position, which greatly facilitates the short-distance travel of residents and solves the"last mile"travel problem. With the emergence of new things, it will inevitably bring some problems. In some sites, there will be many unusable bicycles,which will not only occupy a certain space, but also affect the satisfaction of users. At the same time, the interests of operators will also damage. Therefore, it is necessary to recycle and reuse the unavailable shared bicycles of the site. This paper discusses the problem of unusable shared bicycle recycling maintenance under static conditions. The recovery of these unusable bicycles by a certain capacity of the truck makes the total transportation cost of recycling the lowest. A mixed integer linear programming model(MILP) is used in the paper and a branch-and-cut(B&C) algorithm is used to solve these problems. Finally, the data of the survey around the Wujiaochang in Shanghai were analyzed and conclusions were drawn.
引文
[1] Raviv T, Tzur M, Forma IA. Static repositioning in a bike-sharing system:models and solution approaches[J]. EURO Journal of Transportation and Logistics, 2013(2):187-229.
[2] Contardo C, Morency C, Rousseau L-M. Balancing a dynamic public bike-sharing system[C]//Technical Report CIRRELT-2012-09, CIRRELT, 2012.
[3] Mauro Dell'Amico, Eleni Hadjicostantinou, Manuel Iori, et al. The bike sharing rebalancing problem:Mathematical formulations and benchmark instances[J]. Omega, 2014,45:7-19.
[4]孙小玲,李瑞.整数规划[M].北京:科学出版社,2010.
[5]常山,宋瑞,何世伟,等.共享单车故障车辆回收模型[J].吉林大学学报(工学版),2018,48(6):1677-1684.
[6]王涵霄,董明,张大力.考虑维修的共享单车调度优化研究[J].工业工程与管理,2018(2):135.
[7]钟石泉,马寿峰.车辆路径问题的改进分支切割法[J].系统工程理论与实践,2009,29(10):152-158.
[8]刘臻.城市公共自行车运营中的多车场车辆调配优化研究[D].北京:北京交通大学(硕士学位论文),2014.
[9]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006(11):31-33.
[10] Wang S, Liu X. Energy minimization vehicle routing problem with heterogeneous vehicles[C]//International Conference on Service Systems and Service Management. IEEE, 2016:1-5.
[11]潘茜茜,干宏程.考虑碳排放的冷链物流配送路径优化研究[J].数学的实践与认识,2016(1):62-68.
[12]何流,李旭宏,陈大伟.公共自行车动态调度系统需求预测模型研究[J].武汉理工大学学报(交通科学与工程版),2013,37(2):278-282.
[13]施光燕,董加礼.最优化方法[M].北京:高等教育出版社,1999.
[2] Contardo C, Morency C, Rousseau L-M. Balancing a dynamic public bike-sharing system[C]//Technical Report CIRRELT-2012-09, CIRRELT, 2012.
[3] Mauro Dell'Amico, Eleni Hadjicostantinou, Manuel Iori, et al. The bike sharing rebalancing problem:Mathematical formulations and benchmark instances[J]. Omega, 2014,45:7-19.
[4]孙小玲,李瑞.整数规划[M].北京:科学出版社,2010.
[5]常山,宋瑞,何世伟,等.共享单车故障车辆回收模型[J].吉林大学学报(工学版),2018,48(6):1677-1684.
[6]王涵霄,董明,张大力.考虑维修的共享单车调度优化研究[J].工业工程与管理,2018(2):135.
[7]钟石泉,马寿峰.车辆路径问题的改进分支切割法[J].系统工程理论与实践,2009,29(10):152-158.
[8]刘臻.城市公共自行车运营中的多车场车辆调配优化研究[D].北京:北京交通大学(硕士学位论文),2014.
[9]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006(11):31-33.
[10] Wang S, Liu X. Energy minimization vehicle routing problem with heterogeneous vehicles[C]//International Conference on Service Systems and Service Management. IEEE, 2016:1-5.
[11]潘茜茜,干宏程.考虑碳排放的冷链物流配送路径优化研究[J].数学的实践与认识,2016(1):62-68.
[12]何流,李旭宏,陈大伟.公共自行车动态调度系统需求预测模型研究[J].武汉理工大学学报(交通科学与工程版),2013,37(2):278-282.
[13]施光燕,董加礼.最优化方法[M].北京:高等教育出版社,1999.