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

• CCF Bigdata 2021 • Previous 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]	Fei LUO, Mengwei BAI. Decision optimization of traffic scenario problem based on reinforcement learning [J]. Journal of Computer Applications, 2022, 42(8): 2361-2368.
[2]	Shaobin DENG, Jun ZHU, Xiaofeng ZHOU, Shuai LI, Shurui LIU. Industrial process control method based on local policy interaction exploration-based deep deterministic policy gradient [J]. Journal of Computer Applications, 2022, 42(5): 1642-1648.
[3]	Xueming LI, Guohao WU, Shangbo ZHOU, Xiaoran LIN, Hongbin XIE. Image instance segmentation model based on fractional-order network and reinforcement learning [J]. Journal of Computer Applications, 2022, 42(2): 574-583.
[4]	Rong ZANG, Li WANG, Tengfei SHI. Multi‑agent reinforcement learning based on attentional message sharing [J]. Journal of Computer Applications, 2022, 42(11): 3346-3353.
[5]	Yu XU, Yunyou ZHU, Xiao LIU, Yuting DENG, Yong LIAO. Multi-objective routing optimization of electric power material distribution based on deep reinforcement learning [J]. Journal of Computer Applications, 2022, 42(10): 3252-3258.
[6]	SHANG Fangjian, LI Xin, Di ZHAI, LU Yang, ZHANG Donglei, QIAN Yuwen. Two-phase resource allocation technology for network slices in smart grid [J]. Journal of Computer Applications, 2021, 41(7): 2033-2038.
[7]	ZHOU Shuo, QIU Runhe, TANG Minjun. Power allocation algorithm for CR-NOMA system based on tabu search and Q-learning [J]. Journal of Computer Applications, 2021, 41(7): 2026-2032.
[8]	WANG Jianping, WANG Gang, MAO Xiaobin, MA Enqi. Motion control method of two-link manipulator based on deep reinforcement learning [J]. Journal of Computer Applications, 2021, 41(6): 1799-1804.
[9]	Jiaqi ZHANG, Yueqin ZHANG, Jian CHEN. Pulse condition recognition method based on optimized reinforcement learning path feature classification [J]. Journal of Computer Applications, 2021, 41(11): 3402-3408.
[10]	YAO Xinghu, TAN Xiaoyang. Reward highway network based global credit assignment algorithm in multi-agent reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 1-7.
[11]	FU Kui, LIANG Shaoqing, LI Bing. Commodity recommendation model based on improved deep Q network structure [J]. Journal of Computer Applications, 2020, 40(9): 2613-2621.
[12]	WANG Tiantian, YU Shuangyuan, XU Baomin. Research on proof of work mining dilemma based on policy gradient algorithm [J]. Journal of Computer Applications, 2019, 39(5): 1336-1342.
[13]	XIA Min, SONG Wenzhu, SHI Bicheng, LIU Jia. Deep reinforcement learning method based on weighted densely connected convolutional network [J]. Journal of Computer Applications, 2018, 38(8): 2141-2147.
[14]	XIE Jiyang, YAN Dong, XIE Yao, MA Zhanyu. Analysis of key factors in heat demand prediction based on NARX neural network [J]. Journal of Computer Applications, 2018, 38(11): 3180-3187.
[15]	WANG Qi, QIN Jin. Automatic hierarchical approach of MAXQ based on action space partition [J]. Journal of Computer Applications, 2017, 37(5): 1357-1362.

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