吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (6): 1677-1684.doi: 10.13229/j.cnki.jdxbgxb20170543

• • 上一篇    下一篇

共享单车故障车辆回收模型

常山(),宋瑞(),何世伟,黎浩东,殷玮川   

  1. 北京交通大学 城市交通复杂系统理论与技术教育部重点实验室,北京 100044
  • 收稿日期:2017-05-25 出版日期:2018-11-20 发布日期:2018-12-11
  • 作者简介:常山(1992-),男,博士研究生.研究方向:城市交通规划与管理.
  • 基金资助:
    国家自然科学基金重点项目(U1434207);北京市自然科学基金项目(J160001)

Recycling model of faulty bike sharing

CHANG Shan(),SONG Rui(),HE Shi-wei,LI Hao-dong,YIN Wei-chuan   

  1. MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China
  • Received:2017-05-25 Online:2018-11-20 Published:2018-12-11

摘要:

提出了共享单车故障车辆回收的流程,采用K-means算法对共享单车故障车辆进行聚类,形成聚类服务点,在此基础上构建了以车辆回收工作总成本最小为目标的共享单车故障车辆回收模型,并使用Cplex优化软件求解。以北京市某片区共享单车为例,验证了模型和方法的有效性。结果表明:装载容量的取值对回收任务产生较大影响,本文模型和算法可较好地应用于共享单车故障车辆回收任务中。

关键词: 交通运输系统工程, 共享单车, 故障车辆回收, 公共自行车系统, Cplex

Abstract:

Bike sharing is a new dockless public bicycle system based on the mobile Internet technology. The solution of recycling problem of faulty bikes can reduce the bike sharing company's operating costs. A recycling process model of the faulty bikes is proposed in this work. Firstly, a K-means algorithm is used to cluster faulty bikes to different service points. Then a model of faulty bikes recycling is present in order to minimize the total recycling costs. The optimization software Cplex is used to solve the model. Finally, a case study based on a certain area in Beijing is carried out to validate the proposed model. The results show that the value of loading capacity greatly affects the results of recycling, and that the model and method proposed can be applied effectively to the recycling of faulty bikes.

Key words: engineering of communication and transportation, bike sharing, faulty bikes recycling, public bicycle system, Cplex

中图分类号: 

  • U491

图1

共享单车故障车辆回收网络"

图2

共享单车故障车辆回收流程图"

图3

共享单车热力图"

图4

K-means算法误差平方和的收敛图"

图5

K-means算法得到的聚类中心示意图"

表1

K-means算法得到的聚类结果"

序号 经纬度 共享单车/辆
1 116.312697°E, 39.976673°N 12
2 116.331015°E, 39.973789°N 29
3 116.328320°E, 39.982991°N 7
4 116.319399°E, 39.982194°N 20
5 116.335323°E, 39.983526°N 33
6 116.323458°E, 39.979507°N 21
7 116.325095°E, 39.971676°N 35
8 116.308566°E, 39.975907°N 24
9 116.331941°E, 39.968915°N 16
10 116.326312°E, 39.975648°N 23
11 116.315797°E, 39.986571°N 14
12 116.320677°E, 39.974414°N 10
13 116.334485°E, 39.976352°N 15
14 116.319400°E, 39.971287°N 7
15 116.311083°E, 39.971009°N 34

表2

实例的行程时间矩阵"

{0} 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
{0} 0 3 5 9 5 7 3 4 2 6 4 4 2 4 1 8
1 3 0 9 9 5 9 6 6 2 8 6 8 6 6 5 8
2 5 9 0 8 9 7 6 3 9 3 4 9 4 5 5 15
3 9 9 8 0 9 9 8 9 12 8 8 9 10 6 10 17
4 5 5 9 9 0 6 3 8 8 9 8 2 7 7 6 14
5 7 9 7 9 6 0 7 7 12 7 7 6 8 4 10 15
6 3 6 6 8 3 7 0 4 6 6 3 5 5 4 5 12
7 4 6 3 9 8 7 4 0 9 4 3 8 2 4 3 7
8 2 2 9 12 8 12 6 9 0 8 6 6 4 6 3 5
9 6 8 3 8 9 7 6 4 8 0 6 10 6 5 5 9
10 4 6 4 8 8 7 3 3 6 6 0 8 4 2 5 11
11 4 8 9 9 2 6 5 8 6 10 8 0 6 8 5 10
12 2 6 4 10 7 8 5 2 4 6 4 6 0 4 4 11
13 4 6 5 6 7 4 4 4 6 5 2 8 4 0 5 9
14 1 5 5 10 6 10 5 3 3 5 5 5 4 5 0 8
15 8 8 15 17 14 15 12 7 5 9 11 10 11 9 8 0

表3

Cplex运行最优结果"

车辆序号 回收车满载率/% 车辆到达的具体服务点 线路行程时间/min 总花费时间/min 总成本/元
1 87.5 0-8-15-1-0 18 88 710
2 92.5 0-12-7-2-0 12 86 610
3 97.5 0-10-6-4-11-0 16 94 710
4 97.5 0-13-5-3-9-14-0 31 109 1010
合计 - - 77 377 3040

表4

计算结果对比"

车辆
容量
发车数
/辆
平均满
载率/%
总线路行
程时间/min
总花费时
间/min
总成本
/元
60 6 无可行解
70 5 85.7 81 381 3120
80 4 93.8 77 377 3040
90 4 83.3 77 377 3040
100 3 无可行解
[1] Fishman E, Washington S, Haworth N , et al. Factors influencing bike share membership: an analysis of Melbourne and Brisbane[J]. Transportation Research Part A:Policy and Practice, 2015,71:17-30.
doi: 10.1016/j.tra.2014.10.021
[2] Fishman E . Bikeshare: a review of recent literature[J]. Transport Reviews, 2016,36(1):92-113.
doi: 10.1080/01441647.2015.1033036
[3] Shaheen S A, Guzman S, Zhang H . Bikesharing in Europe, the Americas, and Asia: past, present, and future[J]. Transportation Research Record, 2010(2143):159-167.
[4] Chemla D, Meunier F, Calvo R W . Bike sharing systems: Solving the static rebalancing problem[J]. Discrete Optimization, 2013,10(2):120-146.
doi: 10.1016/j.disopt.2012.11.005
[5] 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.
doi: 10.1016/j.ejor.2016.08.029
[6] Ghosh S, Varakantham P, Adulyasak Y , et al. Dynamic repositioning to reduce lost demand in bike sharing systems[J] Journal of Artificial Intelligence Research, 2017,58:387-430.
doi: 10.1613/jair.5308
[7] 刘臻 . 城市公共自行车运营中的多车场车辆调配优化研究[D]. 北京:北京交通大学交通运输学院, 2014.
Liu Zhen . Study on multiple-depot scheduling optimization in urban public bicycle operation[D]. Beijing:School of Traffic and Transportation, Beijing Jiaotong University, 2014.
[8] 何流, 李旭宏, 陈大伟 , 等. 公共自行车动态调度系统需求预测模型研究[J]. 武汉理工大学学报:交通科学与工程版, 2013,37(2):278-282.
doi: 10.3963/j.issn.2095-3844.2013.02.014
He Liu, Li Xu-hong, Chen Da-wei , et al. Research on the demand forecast model of public bike dynamic scheduling system[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2013,37(2):278-282.
doi: 10.3963/j.issn.2095-3844.2013.02.014
[9] Baldacci R, Christofides N, Mingozzi A . An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[J]. Mathematical Programming, 2008,115(2):351-385.
doi: 10.1007/s10107-007-0178-5
[10] Subramanian A, Penna P H V, Uchoa E , et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem[J]. European Journal of Operational Research, 2012,221(2):285-295.
doi: 10.1016/j.ejor.2012.03.016
[11] Wang S, Liu X. Energy minimization vehicle routing problem with heterogeneous vehicles [C]//International Conference on Service Systems and Service Management, Kunming, China, 2016: 7538462.
[12] 潘述亮, 卢小林, 邹难 . 灵活型接驳公交路径优化及协同调度模型[J]. 吉林大学学报:工学版, 2016,46(6):1827-1835.
Pan Shu-liang, Lu Xiao-lin, Zou Nan . Route planning and coordinated scheduling model for flexible feeder transit service[J]. Journal of Jilin University(Engineering and Technology Edition), 2016,46(6):1827-1835.
[13] Sterzik S, Wang X, Kopfer H . A case study for a location-routing problem[J]. Operations Research Proceedings, 2012,208(2):275-280.
doi: 10.1007/978-3-642-20009-0_44
[14] Farham M S, Süral H, Iyigun C . A column generation approach for the location-routing problem with time windows[J]. Computers & Operations Research, 2018,90:249-263.
[15] 冯超 . K-means聚类算法的研究[D]. 大连:大连理工大学软件学院, 2007.
Feng Chao . Research of K-means clustering algorithm[D]. Dalian:School of Software Technology, Dalian University of Technology, 2007.
[1] 白乔文,曲昭伟,陈永恒,熊帅,陶楚青. 非严格优先权下无左转专用相位直行车辆轨迹模型建立[J]. 吉林大学学报(工学版), 2019, 49(3): 673-679.
[2] 李志慧,钟涛,赵永华,胡永利,李海涛,赵景伟. 面向车辆自主驾驶的行人跟踪算法[J]. 吉林大学学报(工学版), 2019, 49(3): 680-687.
[3] 曹宁博,赵利英,曲昭伟,陈永恒,白乔文,邓晓磊. 考虑双向行人跟随行为的社会力模型[J]. 吉林大学学报(工学版), 2019, 49(3): 688-694.
[4] 罗小芹,王殿海,金盛. 面向混合交通的感应式交通信号控制方法[J]. 吉林大学学报(工学版), 2019, 49(3): 695-704.
[5] 陈磊,王江锋,谷远利,闫学东. 基于思维进化优化的多源交通数据融合算法[J]. 吉林大学学报(工学版), 2019, 49(3): 705-713.
[6] 尹超英,邵春福,王晓全. 考虑停车可用性的建成环境对小汽车通勤出行的影响[J]. 吉林大学学报(工学版), 2019, 49(3): 714-719.
[7] 凃强,程琳,林芬,孙超. 考虑出行者风险态度的最优路径搜索[J]. 吉林大学学报(工学版), 2019, 49(3): 720-726.
[8] 陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[9] 曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[10] 宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[11] 刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[12] 钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[13] 刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[14] 宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.
[15] 栾鑫, 邓卫, 程琳, 陈新元. 特大城市居民出行方式选择行为的混合Logit模型[J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 刘庆民,王龙山,陈向伟,李国发. 滚珠螺母的机器视觉检测[J]. 吉林大学学报(工学版), 2006, 36(04): 534 -538 .
[2] 董立岩,苑森淼,刘光远,李永丽,关伟洲 . 一种基于遗传算法的受限制的分类器学习算法[J]. 吉林大学学报(工学版), 2007, 37(03): 595 -0599 .
[3] 程平,张海涛,高岩,李俊锋,王洪艳 . ANN在聚丙烯酸酯乳液性质预测中的应用
[J]. 吉林大学学报(工学版), 2007, 37(02): 362 -0366 .
[4] 段福庆,周明全,张家才 . 基于均值漂移的非线性尺度空间滤波[J]. 吉林大学学报(工学版), 2007, 37(03): 634 -0639 .
[5] 张大庆;何清华;郝鹏;陈欠根 . 液压挖掘机铲斗轨迹跟踪的鲁棒控制[J]. 吉林大学学报(工学版), 2006, 36(06): 934 -938 .
[6] 梁继才,李义,李忠然,张巍,柳承德 . 汽车保险杠树脂传递模塑工艺充模过程的数值模拟[J]. 吉林大学学报(工学版), 2006, 36(增刊2): 15 -19 .
[7] 李静,吴云平,杨宗昂,郭立书,王军,李幼德,李春峰 . 车辆姿态控制系统悬架阻尼控制策略[J]. 吉林大学学报(工学版), 2006, 36(增刊2): 24 -28 .
[8] 臧文利,郭治 . 基于LMI的随动系统PID控制下的多指标相容性[J]. 吉林大学学报(工学版), 2006, 36(05): 745 -0750 .
[9] 吕建婷,马广富,李传江. 卫星姿态跟踪的模糊滑模控制器设计[J]. 吉林大学学报(工学版), 2007, 37(04): 955 -958 .
[10] 傅立敏,胡兴军 . 虚拟仪器在汽车尾流测量中的应用
[J]. 吉林大学学报(工学版), 2006, 36(05): 644 -0649 .