Dynamic scheduling strategy for bicycle-sharing in cities
-
摘要: 为满足城市共享单车用户的用车需求，提高共享单车的使用效率，结合路况信息提出了一个两阶段的共享单车实时投放与调度框架：在离线建模阶段，基于历史的短程出租车轨迹数据聚类，使用区域提取技术（Regional Extraction Technique，RET）获取不同时段的城市热门用车区域、用车频次与行程结束后的热门停车区域及其停车频次；在线调度阶段，建立共享单车的实时调度优化模型（Real-time OptimizationModel，ROM），根据下一时段的热门用车区域，搜索当前时段内距离其较近的k近邻单车停车区域，并结合实时路况为调度车推荐前k条路况良好的行车线路.出租车轨迹数据集上的实验表明，所提的调度策略相较于传统的自行车调度策略具有较好的有效性.Abstract: To meet the soaring demand of share bike using and improve the service efficiency of bicycle-sharing, this paper proposes a two-stage shared bicycle real-time delivery and scheduling framework based on road condition information. At the offline modeling phase, clustering is implemented on the historical short-distance taxi trajectory data using RET(Regional Extraction Technique) algorithm, to obtain the popular regions of pick-up (or drop-off), and the frequencies of the pick-up (or drop-off) at different time periods. At the online scheduling phase, a dynamic scheduling optimization model (called ROM (Real-time Optimization Model)) for bicycle-sharing is designed to obtain the popular pick-up regions in the next time period. Specifically, searching for the k-nearest neighbor bicycle drop-off regions within the current time period, and combining them with the real-time road conditions to recommend the top-k roads with convenient vehicular access for the bike dispatching car. Experiments on the taxi trajectory dataset show that the proposed method is more effective than the traditional bicycle scheduling strategies.
-
表 1 结点符号含义
Tab. 1 Node symbol definitions
符号 含义 $P_{i}$.id 出租车ID $P_{i}.s$ 出租车载客状态 $P_{i}.t$ 出租车所处时间段 $P_{i}$.lon 经度坐标 $P_{i}$.lat 纬度坐标 $P_{i}.v $ 出租车速度 
下载: 导出CSV
算法1 RET based on DBSCAN 输入: A list of point $D$={$p_{1}, p_{2}{, {\cdots}, p}_{n}$}, MinPts, $ r_{\rm spatio}$ 输出: $C$: Clustering result clusterList $C$ $\leftarrow $ 0, cluster_$i\leftarrow $1; Initialize $D$, TaxiID_i, $D_{s}^{\rm pick}$, $D_{s}^{\rm drop}$, C; 1: for each point $ p_{j}$ in $D$ do 2: if($ p_{i}$.id=TaxiID_i.id)do 3: for each point $ p_{j }$ in TaxiID_i do 4: if ($p_{i}$.time$ < p_{j}$.time)then 5: TaxiID_$i\leftarrow p_{j}=p_{i }\cup p_{j+1}=p_{j }$; 6: else if ($p_{i}$.time$\ge p_{j}$.time)then 7: TaxiID_$i\leftarrow p_{j+1}=p_{i}$; 8: else TaxiID_$i++\leftarrow p_{i }$; /*find short-distance taxi routes, record the drop-off and pick-up point*/ 9: if($p_{m }$and $p_{n }$ is the pick-up and drop-off points of a trip)do 10: if(dist$\vert $$p_{m}, p_{n}$$\vert$$\le $3 km $\vert \vert $T$_{s}$.start$\le p_{n}$.time, $p_{m}$.time$\le T_{s}$.end)then 11: $D_{s}^{\rm pick}\leftarrow p_{n }$; $D_{s}^{\rm drop}\leftarrow p_{m}$; 12: for each point $ p_{e}$ in $D_{s}^{\rm pick}$, $D_{s}^{\rm drop}$do 13: While!$p_{e}$.isVisited=true do; /*find the Neighborhood points for $p_{e }$: Nr$_{\rm spatio}p_{e}$*/ 14: if($\vert $ Nr$_{\rm spatio}p_{e}$$\vert $$\ge $MinPts)then 15: $p_{e}$.cluster_ID=cluster_$i$; 16: for each Neighborhood point $ p_{a}$ in Nr$_{\rm spatio}p_{e}$ do; 17: While!$p_{a}$.isVisited=true do; /*find the Neighborhood points for $p_{a}$ about $r_{\rm spatio}$: Nr$_{\rm spatio}p_{a}$ */ 18: if($\vert $ Nr$_{\rm spatio}p_{a }\vert \ge $MinPts)then 19: Nr$_{\rm spatio}$pi$\leftarrow r_{\rm spatio} p_{i}\cup r_{\rm spatio} p_{a}$ 20: if($p_{a}$.cluster_ID=0)then 21: $p_{a}$.cluster_ID=cluster_$i$; 22: cluster_$i$++; 23: resturn $C$;
下载: 导出CSV
表 2 出租车GPS数据格式
Tab. 2 Format of taxi GPS data
数据符号 数据类型 描述(样例) TaxiID char 出租车标识(18834) Status char 载客状态(1)空载状态(0) Time char 时间(2015-04-01 14:25:27) Longitude float 经度值(121.441 895) Latitude float 纬度值(31.206 928) Speed short 速度(0.0) Angle short 角度(228.0)
下载: 导出CSV
表 3 top-$k$停车区域数据表
Tab. 3 Top-$k$ drop-off region data table
线路长度排名 区域编号 线路长度/km 停车比例/% 1 $g_5$ 0.52 0.70 2 $g_{40}$ 0.66 0.50 3 $g_{10}$ 1.1 1.10 4 $g_{20}$ 1.2 0.90 5 $g_{8}$ 1.3 1.00 6 $g_{7}$ 1.5 0.70 7 $g_{9}$ 1.5 1.50 8 $g_{41}$ 1.6 0.50 9 $g_{11}$ 1.7 0.70 10 $g_{6}$ 1.9 1.30 11 $g_{51}$ 2.1 3.50
下载: 导出CSV
-
[1] CHANG H W, TAI Y C, HSU Y J. Context-aware taxi demand hotspots prediction[J]. International Jounal of Business Intelligence and Data Mining, 2010, 5(1):3-18. doi: 10.1504/IJBIDM.2010.030296 [2] LI X L, PAN G, WU Z H, et al. Prediction of urban human mobility using large-scale taxi traces and its application[J]. Frontiers of Computer Science, 2012, 6(1):111-121. http://d.old.wanfangdata.com.cn/Periodical/zggdxxxswz-jsjkx201201009 [3] LIU H P, JIN C Q, ZHOU A Y. Popular route planing with travel cost estimation[C]//International Conference on Database Systems for Advanced Applications(DASFAA), 2016, 2016: 403-418. [4] CHEN C, CHEN X, WANG Z, et al. Scenicplanner:Planning scenic travel routes leveraging heterogeneous user-generated digital footprints[J]. Frontiers of Computer Science, 2017, 11(1):61-74. doi: 10.1007/s11704-016-5550-2 [5] EOIN O M, DAVID B S. Data analysis and optimization for (citi)bike sharing[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI, 2015: 687-694. [6] DIMITRIOS T, IOANNIS B, VANA K. Lessons learnt from the analysis of a bike sharing system[C]//PETRA'17 Proceedings of the 10th International Conference on PErvasive Technologies Related to Assistive Environments. 2017: 261-264. [7] CHENG F, JANE H, DANIEL R. Moment-based probabilistic prediction of bike availability for bike-sharing systems[C]//International Conference on Quantitative Evaluation of Systems, QEST 2016: Quantitative Evaluation of Systems. 2016: 139-155. [8] CHEN L B, ZHANG D Q, PAN G, et al. Bike sharing station placement leveraging heterogeneous Urban open data[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. ACM, 2015: 571-575. [9] DIVYA S, SOMYA S, PETER I F, et al. Predicting bike usage for New York City.s Bike sharing system[C]//Association for the Advancement of Artificial Intelligence. 2015: 110-114. [10] LIU J M, SUN L L, CHEN W W, et al. Rebalancing bike sharing systems: A multi-source data smart optimization[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016: 1005-1014. [11] FÁBIO C, ANAND S, BRUNO P.B, et al. A heuristic algorithm for a single vehicle static bike sharing rebalancing problem[J]. Computers & Operations Research, 2017, 79:19-33. [12] ALVAREZ-VALDES R, BELENGUER J M, BENAVENT E, et al. Optimizing the level of service quality of a bike-sharing system[J]. Omega, 2015, 62:163-175. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9b015e7c3d8974d18e08b7d023892292 [13] LI Y X, ZHENG Y, ZHANG H C, et al. Traffic prediction in a bike-sharing system[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM SIGSPATIAL, 2015: Article No 33. [14] CHRISTIAN K, GUNTHER R R. Full-load route planning for balancing bike sharing systems by logic-based benders decomposition[J]. Wiley Periodicals, 2017, 69(3):270-289. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5a7bc0394d83c1171935047514e7fb07 [15] DIJSTRA E D. A note on two problem in connexion with graphs[J]. Numerische Mathematik, 1959(1):269-271. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1177/001872676702000107 [16] MAO J L, SONG Q G, JIN C Q, et al. TSCluWin: Trajectory stream clustering over sliding window[C]//DASFAA 2016: Databases Systems for Advanced Applications. 2016: 133-148. [17] JOSHI S, KAUR S. Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem[C]//International Conference on Computing for Sustainable Global Development. 2015: 86-88. [18] ZHAO F G, LI S J, SUN J S, et al. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers and Industrial Engineering(COMPUT IND ENG), 2009, 56(4):1642-1648. doi: 10.1016/j.cie.2008.10.014 -
点击查看大图
图(10) / 表(4)
计量
- 文章访问数: 109
- HTML全文浏览量: 78
- PDF下载量: 0
- 被引次数: 0