User incentive based bike‑sharing dispatching strategy

doi:10.11772/j.issn.1001-9081.2021122109

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (11): 3395-3403.DOI: 10.11772/j.issn.1001-9081.2021122109

Special Issue: 第九届CCF大数据学术会议(CCF Bigdata 2021)

• CCF Bigdata 2021 • Previous Articles Next Articles

User incentive based bike‑sharing dispatching strategy

Bing SHI¹, Xizi HUANG¹, Zhaoxiang SONG¹, Jianqiao XU²()

^1.School of Computer Science and Artificial Intelligence，Wuhan University of Technology，Wuhan Hubei 430070，China
^2.Department of Information Security，Naval University of Engineering，Wuhan Hubei 430033，China

Received:2021-12-15 Revised:2022-01-18 Accepted:2022-01-24 Online:2022-11-14 Published:2022-11-10
Contact: Jianqiao XU
About author:SHI Bing， born in 1982， Ph. D.， professor. His research interests include artificial intelligence， multi‑agent systems.
HUANG Xizi， born in 1997， M. S. candidate. Her research interests include artificial intelligence， multi‑agent systems.
SONG Zhaoxiang， born in 1997， M. S. candidate. His research interests include artificial intelligence， multi‑agent systems.
XU Jianqiao， born in 1979， M. S.， lecturer. His research interests include network and information security， artificial intelligence.
Supported by:
Humanity and Social Science Research Foundation of Ministry of Education of China(19YJC790111);Philosophy and Social Science Post?Foundation of Ministry of Education(18JHQ060)

基于用户激励的共享单车调度策略

石兵¹, 黄茜子¹, 宋兆翔¹, 徐建桥²()

^1.武汉理工大学计算机与人工智能学院, 武汉 430070
^2.海军工程大学信息安全系, 武汉 430033

通讯作者: 徐建桥
作者简介:石兵（1982—），男，江苏泰兴人，教授，博士，CCF会员，主要研究方向：人工智能、多智能体系统
黄茜子（1997—），女，湖北咸宁人，硕士研究生，主要研究方向为：人工智能、多智能体系统
宋兆翔（1997—），男，湖北孝感人，硕士研究生，主要研究方向：人工智能、多智能体系统
徐建桥（1979—），男，湖北武汉人，讲师，硕士，主要研究方向：网络与信息安全、人工智能。xujianqiao321@163.com
基金资助:
教育部人文社会科学研究项目(19YJC790111);教育部哲学社会科学研究后期资助项目(18JHQ060)

Abstract

Abstract:

To address the dispatching problem of bike?sharing， considering the budget constraints， user maximum walking distance restrictions， user temporal and spatial demands and dynamic changes in the distribution of shared bicycles， a bike?sharing dispatching strategy with user incentives was proposed to improve the long?term user service rate of the bike?sharing platform. The dispatching strategy consists of a task generation algorithm， a budget allocation algorithm and a task allocation algorithm. In the task generation algorithm， the Long Short?Term Memory （LSTM） network was used to predict the future bike demand of users； in the budget allocation algorithm， the Deep Deterministic Policy Gradient （DDPG） algorithm was used to design a budget allocation strategy； after the budget was allocated to the tasks， the tasks needed to be allocated to the user for execution， so a greedy matching strategy was used for task allocation. Experiments were carried out on the Mobike dataset to compare the proposed strategy with the dispatching strategy with unlimited budget （that is， the platform is not limited by budget and can use any money to encourage users to ride to the target area）， the greedy dispatching strategy， the dispatching strategy with truck hauling， and the situation without dispatching. Experimental results show that the proposed dispatching strategy with user incentive can effectively improve the service rate in the bike?sharing system compared to the greedy dispatching strategy and dispatching strategy with truck hauling.

Key words: bike?sharing dispatching, demand prediction, user incentive, Markov decision, deep reinforcement learning

摘要：

针对共享单车的调度问题，在考虑预算限制、用户最大步行距离限制、用户时空需求以及共享单车分布动态变化的情况下，提出一种用户激励下的共享单车调度策略，以达到提高共享单车平台长期用户服务率的目的。该调度策略包含任务生成算法、预算分配算法和任务分配算法。在任务生成算法中，使用长短期记忆（LSTM）网络预测用户未来的单车需求量；在预算分配算法中，采用深度策略梯度（DDPG）算法来设计预算分配策略；任务分配完预算后，需要将任务分配给用户执行，因此在任务分配算法中使用贪心匹配策略来进行任务分配。基于摩拜单车的数据集进行实验，并把所提策略分别与无预算限制的调度策略（即平台不受预算限制，可以使用任意金钱激励用户将车骑行至目标区域）、贪心的调度策略、卡车拖运下的调度策略以及未进行调度的情况进行对比。实验结果表明，与贪心调度策略和卡车托运下的调度策略相比，用户激励下的共享单车调度策略能有效提高共享单车系统中的用户服务率。

关键词: 共享单车调度, 需求预测, 用户激励, 马尔可夫决策, 深度强化学习

CLC Number:

TP181

Bing SHI, Xizi HUANG, Zhaoxiang SONG, Jianqiao XU. User incentive based bike‑sharing dispatching strategy[J]. Journal of Computer Applications, 2022, 42(11): 3395-3403.

石兵, 黄茜子, 宋兆翔, 徐建桥. 基于用户激励的共享单车调度策略[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3395-3403.

Figures/Tables 9

Fig. 1 Schematic diagram of user incentive for bike?sharing dispatching

Tab. 1 Symbol definition

符号	描述
$R = r 1, r 2, ⋯, r n$	表示将区域划分互为不交叉重叠的 $n$ 个小区域
$T = t 1, t 2, ⋯, t T$	表示将时间分为 $T$ 个时隙
$S U t$	在 $t$ 时间段开始时所有区域的共享单车供应量
$U t = u 1, u 2, …, u n u t$	表示在 $t$ 时间段到来的用户的集合
$r s j$	表示用户 $u j$ 的起点区域
$r a r r j$	表示用户 $u j$ 的目的地区域
$r w a n t j$	表示用户 $u j$ 的调度任务区域
$r a c t j$	表示用户 $u j$ 实际归还共享单车的区域
$d m a x j$	表示用户 $u j$ 的最大步行距离
$B U$	表示用户激励下的调度策略中的预算限制

Tab. 1 Symbol definition

符号	描述
$R = r 1, r 2, ⋯, r n$	表示将区域划分互为不交叉重叠的 $n$ 个小区域
$T = t 1, t 2, ⋯, t T$	表示将时间分为 $T$ 个时隙
$S U t$	在 $t$ 时间段开始时所有区域的共享单车供应量
$U t = u 1, u 2, …, u n u t$	表示在 $t$ 时间段到来的用户的集合
$r s j$	表示用户 $u j$ 的起点区域
$r a r r j$	表示用户 $u j$ 的目的地区域
$r w a n t j$	表示用户 $u j$ 的调度任务区域
$r a c t j$	表示用户 $u j$ 实际归还共享单车的区域
$d m a x j$	表示用户 $u j$ 的最大步行距离
$B U$	表示用户激励下的调度策略中的预算限制

Fig. 2 Bike?sharing dispatching strategy with user incentives

Fig. 3 User demands in weekdays and weekends

Fig. 4 Regional division and indexing

Tab. 2 Experimental parameters

参数	描述
区域划分数量	5×5
用户最大步行距离	均值为单个网格区域长度的正态分布
用户步行成本参数	1
总时间段数 $T$	78
时间间隔	10 min
$N_S T A T E S 2$	301
$N_A C T I O N S 2$	1，其中 $a t ∈ 0,1$

Tab. 2 Experimental parameters

参数	描述
区域划分数量	5×5
用户最大步行距离	均值为单个网格区域长度的正态分布
用户步行成本参数	1
总时间段数 $T$	78
时间间隔	10 min
$N_S T A T E S 2$	301
$N_A C T I O N S 2$	1，其中 $a t ∈ 0,1$

Fig. 5 LSTM predicted user demand data

Fig. 6 Number of users without bike under different budget constraints

Fig. 7 Number of users without bike under different initial supply of shared bikes

References 32

1	DEMAIO P. Bike‑sharing： history， impacts， models of provision， and future［J］. Journal of Public Transportation， 2009， 12（4）： 41-56. 10.5038/2375-0901.12.4.3
2	李琨浩. 基于共享经济视角下城市共享单车发展对策研究［J］. 城市， 2017（3）： 66-69. 10.3969/j.issn.1005-278X.2017.03.012
	LI K H. Research on the development countermeasures of city shared bicycles from the perspective of sharing economy［J］. City， 2017（3）： 66-69. 10.3969/j.issn.1005-278X.2017.03.012
3	王怡苏.“共享经济”在中国的发展现状和模式的研究——以共享单车为例［J］. 当代经济， 2017（17）： 140-141. 10.3969/j.issn.1007-9378.2017.17.061
	WANG Y S. Research on development status and model of “sharing economy” in China ― taking shared bicycle as an example［J］. Contemporary Economics， 2017（17）： 140-141. 10.3969/j.issn.1007-9378.2017.17.061
4	PFROMMER J， WARRINGTON J， SCHILDBACH G， et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems［J］. IEEE Transactions on Intelligent Transportation Systems， 2014， 15（4）： 1567-1578. 10.1109/tits.2014.2303986
5	SHAHEEN S A， GUZMAN S， ZHANG H. Bikesharing in Europe， the Americas， and Asia： past， present， and future［J］. Transportation Research Record， 2010， 2143（1）： 159-167. 10.3141/2143-20
6	吴垚，曾菊儒，彭辉，等. 群智感知激励机制研究综述［J］. 软件学报， 2016， 27（8）： 2025-2047. 10.13328/j.cnki.jos.005049
	WU Y， ZENG J R， PENG H， et al. Survey on incentive mechanisms for crowd sensing［J］. Journal of Software， 2016， 27（8）： 2025-2047. 10.13328/j.cnki.jos.005049
7	童咏昕，袁野，成雨蓉，等. 时空众包数据管理技术研究综述［J］. 软件学报， 2017， 28（1）： 35-58.
	TONG Y X， YUAN Y， CHENG Y R， et al. Survey on spatiotemporal crowdsourced data management techniques［J］. Journal of Software， 2017， 28（1）： 35-58.
8	TONG Y X， SHE J Y， DING B L， et al. Online minimum matching in real‑time spatial data： experiments and analysis［J］. Proceedings of the VLDB Endowment， 2016， 9（12）： 1053-1064. 10.14778/2994509.2994523
9	徐毅，童咏昕，李未. 大规模拼车算法研究进展［J］. 计算机研究与发展， 2020， 57（1）： 32-52. 10.7544/issn1000-1239.2020.20190239
	XU Y， TONG Y X， LI W. Recent progress in large‑scale ridesharing algorithms［J］. Journal of Computer Research and Development， 2020， 57（1）： 32-52. 10.7544/issn1000-1239.2020.20190239
10	AESCHBACH P， ZHANG X J， GEORGHIOU A， et al. Balancing bike sharing systems through customer cooperation ― a case study on London’s Barclays Cycle Hire［C］// Proceeding of the 54th IEEE Conference on Decision and Control. Piscataway： IEEE， 2015： 4722-4727. 10.1109/cdc.2015.7402955
11	FRICKER C， GAST N. Incentives and redistribution in homogeneous bike‑sharing systems with stations of finite capacity［J］. EURO Journal on Transportation and Logistics， 2016， 5（3）： 261-291. 10.1007/s13676-014-0053-5
12	CAGGIANI L， CAMPOREALE R， MARINELLI M， et al. User satisfaction based model for resource allocation in bike‑sharing systems［J］. Transport Policy， 2019， 80： 117-126. 10.1016/j.tranpol.2018.03.003
13	TONG Y X， ZENG Y X， DING B L， et al. Two‑sided online micro‑task assignment in spatial crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（5）： 2295-2309.
14	LI K Y， LI G L， WANG Y， et al. CrowdRL： an end‑to‑end reinforcement learning framework for data labelling［C］// Proceeding of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 289-300. 10.1109/icde51399.2021.00032
15	CHENG H， WED S Y， ZHANG L Y， et al. Engaging drivers in ride hailing via competition： a case study with arena［C］// Proceeding of the 22nd IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2021： 19-28. 10.1109/mdm52706.2021.00016
16	YANG H， QIN X R， KE J T， et al. Optimizing matching time interval and matching radius in on‑demand ride‑sourcing markets［J］. Transportation Research Part B： Methodological， 2020， 131： 84-105. 10.1016/j.trb.2019.11.005
17	ZHAO Y， ZHENG K， CUI Y， et al. Predictive task assignment in spatial crowdsourcing： a data‑driven approach［C］// Proceeding of the IEEE 36th International Conference on Data Engineering. Piscataway： IEEE， 2020： 13-24. 10.1109/icde48307.2020.00009
18	BAN S， HYUN K H. Designing a user participation‑based bike rebalancing service［J］. Sustainability， 2019， 11（8）： No.2396. 10.3390/su11082396
19	LI L F， SHAN M Y. Bidirectional incentive model for bicycle redistribution of a bicycle sharing system during rush hour［J］. Sustainability， 2016， 8（12）： No.1299. 10.3390/su8121299
20	REISS S， BOGENBERGER K. A relocation strategy for Munich’s bike sharing system： combining an operator‑based and a user‑based scheme［J］. Transportation Research Procedia， 2017， 22： 105-114. 10.1016/j.trpro.2017.03.016
21	HUANG J J. CHOU M C， TEO C P. Bike‑repositioning using volunteers： crowd sourcing with choice restriction［C］// Proceeding of the 35th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2021： 11844-11852. 10.1609/aaai.v35i13.17407
22	PAN L， CAI Q P， FANG Z X， et al. A deep reinforcement learning framework for rebalancing dockless bike sharing systems［C］// Proceeding of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 1393-1400. 10.1609/aaai.v33i01.33011393
23	DUAN Y B， WU J. Optimizing rebalance scheme for dock‑less bike sharing systems with adaptive user incentive［C］// Proceeding of the 20th IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2019： 176-181. 10.1109/mdm.2019.00-59
24	SINGLA A， SANTONI M， BARTÓK G， et al. Incentivizing users for balancing bike sharing systems［C］// Proceeding of the 29th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2015： 723-729. 10.1609/aaai.v29i1.9251
25	SUTSKEVER I， VINYALS O， LE Q V. Sequence to sequence learning with neural networks［C］// Proceeding of the 27th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2014： 3104-3112.
26	DONG C J， XIONG Z H， SHAO C F， et al. A spatial‑temporal‑ based state space approach for freeway network traffic flow modelling and prediction［J］. Transportmetrica A： Transport Science， 2015， 11（7）： 547-560. 10.1080/23249935.2015.1030003
27	YAO H X， TANG X F， WEI H， et al. Revisiting spatial‑temporal similarity： a deep learning framework for traffic prediction［C］// Proceeding of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 5668-5675. 10.1609/aaai.v33i01.33015668
28	杜圣东，李天瑞，杨燕，等. 一种基于序列到序列时空注意力学习的交通流预测模型［J］. 计算机研究与发展， 2020， 57（8）： 1715-1728. 10.7544/issn1000-1239.2020.20200169
	DU S D， LI T R， YANG Y， et al. A sequence‑to‑ sequence spatial‑temporal attention learning model for urban traffic flow prediction［J］. Journal of Computer Research and Development， 2020， 57（8）： 1715-1728. 10.7544/issn1000-1239.2020.20200169
29	LILLICRAP T P， HUNT J J， PRITZEL A， et al. Continuous control with deep reinforcement learning［EB/OL］.（2019-07-05）［2021-09-23］..
30	SILVER D， LEVER G， HEESS N， et al. Deterministic policy gradient algorithms［C］// Proceeding of the 31st International Conference on Machine Learning. New York： JMLR.org， 2014： 387-395.
31	余显，李振宇，孙胜，等. 基于深度强化学习的自适应虚拟机整合方法［J］. 计算机研究与发展， 2021， 58（12）： 2783-2797. 10.7544/issn1000-1239.2021.20200366
	YU X， LI Z Y， SUN S， et al. Adaptive virtual machine consolidation method based on deep reinforcement learning［J］. Journal of Computer Research and Development， 2021， 58（12）： 2783-2797. 10.7544/issn1000-1239.2021.20200366
32	卢海峰，顾春华，罗飞，等. 基于深度强化学习的移动边缘计算任务卸载研究［J］. 计算机研究与发展， 2020， 57（7）： 1539-1554. 10.7544/issn1000-1239.2020.20190291
	LU H F， GU C H， LUO F， et al. Research on task offloading based on deep reinforcement learning in mobile edge computing［J］. Journal of Computer Research and Development， 2020， 57（7）： 1539-1554. 10.7544/issn1000-1239.2020.20190291

[1]	Yi ZHOU, Hua GAO, Yongshen TIAN. Proximal policy optimization algorithm based on clipping optimization and policy guidance [J]. Journal of Computer Applications, 2024, 44(8): 2334-2341.
[2]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.
[3]	Tian MA, Runtao XI, Jiahao LYU, Yijie ZENG, Jiayi YANG, Jiehui ZHANG. Mobile robot 3D space path planning method based on deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(7): 2055-2064.
[4]	Xiaoyan ZHAO, Wei HAN, Junna ZHANG, Peiyan YUAN. Collaborative offloading strategy in internet of vehicles based on asynchronous deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(5): 1501-1510.
[5]	Rui TANG, Chuanlin PANG, Ruizhi ZHANG, Chuan LIU, Shibo YUE. DDPG-based resource allocation in D2D communication-empowered cellular network [J]. Journal of Computer Applications, 2024, 44(5): 1562-1569.
[6]	Xintong QIN, Zhengyu SONG, Tianwei HOU, Feiyue WANG, Xin SUN, Wei LI. Channel access and resource allocation algorithm for adaptive p-persistent mobile ad hoc network [J]. Journal of Computer Applications, 2024, 44(3): 863-868.
[7]	Yuanchao LI, Chongben TAO, Chen WANG. Gait control method based on maximum entropy deep reinforcement learning for biped robot [J]. Journal of Computer Applications, 2024, 44(2): 445-451.
[8]	Fuqin DENG, Huifeng GUAN, Chaoen TAN, Lanhui FU, Hongmin WANG, Tinlun LAM, Jianmin ZHANG. Multi-robot reinforcement learning path planning method based on request-response communication mechanism and local attention mechanism [J]. Journal of Computer Applications, 2024, 44(2): 432-438.
[9]	Jiachen YU, Ye YANG. Irregular object grasping by soft robotic arm based on clipped proximal policy optimization algorithm [J]. Journal of Computer Applications, 2024, 44(11): 3629-3638.
[10]	Jie LONG, Liang XIE, Haijiao XU. Integrated deep reinforcement learning portfolio model [J]. Journal of Computer Applications, 2024, 44(1): 300-310.
[11]	Yu WANG, Tianjun REN, Zilin FAN. Air combat maneuver decision-making of unmanned aerial vehicle based on guided Minimax-DDQN [J]. Journal of Computer Applications, 2023, 43(8): 2636-2643.
[12]	Ziteng WANG, Yaxin YU, Zifang XIA, Jiaqi QIAO. Sparse reward exploration mechanism fusing curiosity and policy distillation [J]. Journal of Computer Applications, 2023, 43(7): 2082-2090.
[13]	Yuan WEI, Yan LIN, Shengnan GUO, Youfang LIN, Huaiyu WAN. Prediction of taxi demands between urban regions by fusing origin-destination spatial-temporal correlation [J]. Journal of Computer Applications, 2023, 43(7): 2100-2106.
[14]	Heping FANG, Shuguang LIU, Yongyi RAN, Kunhua ZHONG. Integrated scheduling optimization of multiple data centers based on deep reinforcement learning [J]. Journal of Computer Applications, 2023, 43(6): 1884-1892.
[15]	Xiaolin LI, Yusang JIANG. Task offloading algorithm for UAV-assisted mobile edge computing [J]. Journal of Computer Applications, 2023, 43(6): 1893-1899.

User incentive based bike‑sharing dispatching strategy

基于用户激励的共享单车调度策略

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 32

Related Articles 15

Recommended Articles

Metrics