华东师范大学学报（自然科学版） >

2019 , Vol. 2019 >Issue 6: 88 - 102

DOI: https://doi.org/10.3969/j.issn.1000-5641.2019.06.009

计算机科学

城市共享单车的动态调度策略

  • 谢青成 ,
  • 毛嘉莉 ,
  • 刘婷
展开
  • 1. 西华师范大学 计算机学院, 四川 南充 637000;
    2. 华东师范大学 数据科学与工程学院, 上海 200062
谢青成,男,硕士研究生,研究方向为基于位置的服务.E-mail:1061109117@qq.com.

收稿日期: 2018-09-03

  网络出版日期: 2019-11-26

基金资助

国家自然科学基金（61702423）；四川省教育厅重点基金项目（17ZA0381）；西华师范大学国家培育项目（16C005）；西华师范大学英才科研基金（17YC158）

收起

Dynamic scheduling strategy for bicycle-sharing in cities

  • XIE Qing-cheng ,
  • MAO Jia-li ,
  • LIU Ting
Expand
  • 1. School of Computing, China West Normal University, Nanchong Sichuan 637000, China;
    2. School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received date: 2018-09-03

  Online published: 2019-11-26

Fold

摘要

为满足城市共享单车用户的用车需求，提高共享单车的使用效率，结合路况信息提出了一个两阶段的共享单车实时投放与调度框架：在离线建模阶段，基于历史的短程出租车轨迹数据聚类，使用区域提取技术（Regional Extraction Technique，RET）获取不同时段的城市热门用车区域、用车频次与行程结束后的热门停车区域及其停车频次；在线调度阶段，建立共享单车的实时调度优化模型（Real-time OptimizationModel，ROM），根据下一时段的热门用车区域，搜索当前时段内距离其较近的k近邻单车停车区域，并结合实时路况为调度车推荐前k条路况良好的行车线路.出租车轨迹数据集上的实验表明，所提的调度策略相较于传统的自行车调度策略具有较好的有效性.

关键词： 动态调度; 城市共享单车; 用车区域; 停车区域; 实时路况

本文引用格式

谢青成 , 毛嘉莉 , 刘婷 . 城市共享单车的动态调度策略[J]. 华东师范大学学报（自然科学版）, 2019 , 2019(6) : 88 -102 . DOI: 10.3969/j.issn.1000-5641.2019.06.009

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.

Key words： dynamic scheduling strategy; city shared bike; pick-up region; drop-off region; real-time road conditions

参考文献

[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.
[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.
[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.
[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.
[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.
[15] DIJSTRA E D. A note on two problem in connexion with graphs[J]. Numerische Mathematik, 1959(1):269-271.
[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.
Options
文章导航

/

〈 〉