《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (11): 3395-3403.DOI: 10.11772/j.issn.1001-9081.2021122109
• 第九届CCF大数据学术会议 • 上一篇
收稿日期:
2021-12-15
修回日期:
2022-01-18
接受日期:
2022-01-24
发布日期:
2022-11-14
出版日期:
2022-11-10
通讯作者:
徐建桥
作者简介:
石兵(1982—),男,江苏泰兴人,教授,博士,CCF会员,主要研究方向:人工智能、多智能体系统基金资助:
Bing SHI1, Xizi HUANG1, Zhaoxiang SONG1, Jianqiao XU2()
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.Supported by:
摘要:
针对共享单车的调度问题,在考虑预算限制、用户最大步行距离限制、用户时空需求以及共享单车分布动态变化的情况下,提出一种用户激励下的共享单车调度策略,以达到提高共享单车平台长期用户服务率的目的。该调度策略包含任务生成算法、预算分配算法和任务分配算法。在任务生成算法中,使用长短期记忆(LSTM)网络预测用户未来的单车需求量;在预算分配算法中,采用深度策略梯度(DDPG)算法来设计预算分配策略;任务分配完预算后,需要将任务分配给用户执行,因此在任务分配算法中使用贪心匹配策略来进行任务分配。基于摩拜单车的数据集进行实验,并把所提策略分别与无预算限制的调度策略(即平台不受预算限制,可以使用任意金钱激励用户将车骑行至目标区域)、贪心的调度策略、卡车拖运下的调度策略以及未进行调度的情况进行对比。实验结果表明,与贪心调度策略和卡车托运下的调度策略相比,用户激励下的共享单车调度策略能有效提高共享单车系统中的用户服务率。
中图分类号:
石兵, 黄茜子, 宋兆翔, 徐建桥. 基于用户激励的共享单车调度策略[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.
符号 | 描述 |
---|---|
表示将区域划分互为不交叉重叠的 | |
表示将时间分为 | |
在 | |
表示在 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户激励下的调度策略中的预算限制 |
表1 符号定义
Tab. 1 Symbol definition
符号 | 描述 |
---|---|
表示将区域划分互为不交叉重叠的 | |
表示将时间分为 | |
在 | |
表示在 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户 | |
表示用户激励下的调度策略中的预算限制 |
参数 | 描述 |
---|---|
区域划分数量 | 5×5 |
用户最大步行距离 | 均值为单个网格区域长度的正态分布 |
用户步行成本参数 | 1 |
总时间段数 | 78 |
时间间隔 | 10 min |
301 | |
1,其中 |
表2 实验参数
Tab. 2 Experimental parameters
参数 | 描述 |
---|---|
区域划分数量 | 5×5 |
用户最大步行距离 | 均值为单个网格区域长度的正态分布 |
用户步行成本参数 | 1 |
总时间段数 | 78 |
时间间隔 | 10 min |
301 | |
1,其中 |
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]. 《计算机应用》唯一官方网站, 2022, 42(9): 2722-2731. |
[2] | 罗飞, 白梦伟. 基于强化学习的交通情景问题决策优化[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2361-2368. |
[3] | 邓绍斌, 朱军, 周晓锋, 李帅, 刘舒锐. 基于局部策略交互探索的深度确定性策略梯度的工业过程控制方法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1642-1648. |
[4] | 李学明, 吴国豪, 周尚波, 林晓然, 谢洪斌. 基于分数阶网络和强化学习的图像实例分割模型[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 574-583. |
[5] | 臧嵘, 王莉, 史腾飞. 基于注意力消息共享的多智能体强化学习[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3346-3353. |
[6] | 徐郁, 朱韵攸, 刘筱, 邓雨婷, 廖勇. 基于深度强化学习的电力物资配送多目标路径优化[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3252-3258. |
[7] | 尚芳剑, 李信, 翟迪, 陆阳, 张东磊, 钱玉文. 智能电网中两阶段网络切片资源分配技术[J]. 计算机应用, 2021, 41(7): 2033-2038. |
[8] | 周烁, 仇润鹤, 唐旻俊. 基于禁忌搜索和Q-learning的CR-NOMA系统的功率分配算法[J]. 计算机应用, 2021, 41(7): 2026-2032. |
[9] | 王建平, 王刚, 毛晓彬, 马恩琪. 基于深度强化学习的二连杆机械臂运动控制方法[J]. 计算机应用, 2021, 41(6): 1799-1804. |
[10] | 张嘉琪, 张月琴, 陈健. 优化强化学习路径特征分类的脉象识别法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3402-3408. |
[11] | 姚兴虎, 谭晓阳. 基于奖励高速路网络的多智能体强化学习中的全局信用分配算法[J]. 计算机应用, 2021, 41(1): 1-7. |
[12] | 傅魁, 梁少晴, 李冰. 基于改进的深度Q网络结构的商品推荐模型[J]. 计算机应用, 2020, 40(9): 2613-2621. |
[13] | 徐雅斌, 彭宏恩. 基于需求预测的PaaS平台资源分配方法[J]. 计算机应用, 2019, 39(6): 1583-1588. |
[14] | 王甜甜, 于双元, 徐保民. 基于策略梯度算法的工作量证明中挖矿困境研究[J]. 计算机应用, 2019, 39(5): 1336-1342. |
[15] | 夏旻, 宋稳柱, 施必成, 刘佳. 基于加权密集连接卷积网络的深度强化学习方法[J]. 计算机应用, 2018, 38(8): 2141-2147. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||