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

doi:10.11772/j.issn.1001-9081.2021122109

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (11): 3395-3403.DOI: 10.11772/j.issn.1001-9081.2021122109

所属专题：第九届CCF大数据学术会议(CCF Bigdata 2021)

• 第九届CCF大数据学术会议 • 上一篇下一篇

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP181

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

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.

图/表 9

图1 用户激励下共享单车调度工作示意图

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

表1 符号定义

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$	表示用户激励下的调度策略中的预算限制

表1 符号定义

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$	表示用户激励下的调度策略中的预算限制

图2 用户激励下的共享单车调度策略

Fig. 2 Bike?sharing dispatching strategy with user incentives

图3 工作日与周末的用户需求

Fig. 3 User demands in weekdays and weekends

图4 区域划分及编号

Fig. 4 Regional division and indexing

表2 实验参数

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$

表2 实验参数

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$

图5 LSTM预测的用户需求数据

Fig. 5 LSTM predicted user demand data

图6 不同预算限制下未骑到车的用户数

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

图7 不同共享单车初始供应量情况下未骑到车的用户数

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

参考文献 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]	范黎林, 曹富康, 王琬婷, 杨凯, 宋钊瑜. 基于需求模式自适应匹配的间歇性需求预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2747-2755.
[2]	周毅, 高华, 田永谌. 基于裁剪优化和策略指导的近端策略优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[3]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[4]	李欢欢, 黄添强, 丁雪梅, 罗海峰, 黄丽清. 基于多尺度时空图卷积网络的交通出行需求预测[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2065-2072.
[5]	赵晓焱, 韩威, 张俊娜, 袁培燕. 基于异步深度强化学习的车联网协作卸载策略[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1501-1510.
[6]	唐睿, 庞川林, 张睿智, 刘川, 岳士博. D2D通信增强的蜂窝网络中基于DDPG的资源分配[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1562-1569.
[7]	秦鑫彤, 宋政育, 侯天为, 王飞越, 孙昕, 黎伟. 基于自适应p持续的移动自组网信道接入和资源分配算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 863-868.
[8]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[9]	李源潮, 陶重犇, 王琛. 基于最大熵深度强化学习的双足机器人步态控制方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 445-451.
[10]	余家宸, 杨晔. 基于裁剪近端策略优化算法的软机械臂不规则物体抓取[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3629-3638.
[11]	龙杰, 谢良, 徐海蛟. 集成的深度强化学习投资组合模型[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 300-310.
[12]	郭茂祖, 张雅喆, 赵玲玲. 基于空间语义和个体活动的电动汽车充电站选址方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2819-2827.
[13]	王昱, 任田君, 范子琳. 基于引导Minimax-DDQN的无人机空战机动决策[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2636-2643.
[14]	王子腾, 于亚新, 夏子芳, 乔佳琪. 融合好奇心和策略蒸馏的稀疏奖励探索机制[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2082-2090.
[15]	魏远, 林彦, 郭晟楠, 林友芳, 万怀宇. 融合出发地与目的地时空相关性的城市区域间出租车需求预测[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2100-2106.

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

User incentive based bike‑sharing dispatching strategy

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 32

相关文章 15

编辑推荐

Metrics