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

石兵，黄茜子，宋兆翔，徐建桥

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

石兵1，黄茜子1，宋兆翔1，徐建桥2*

（1.武汉理工大学 计算机与人工智能学院，武汉 430070； 2.海军工程大学 信息安全系，武汉 430033）（∗通信作者电子邮箱 xujianqiao321@163.com）

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

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

0 引言

共享单车系统（Bike‑Sharing System）作为共享经济中交通出行领域的一个典型例子，在世界各地发展迅速。共享单车已广泛应用于国内外各主要城市的短途通行，有效解决了“最后一公里”的问题，给国内外都带来了很大的经济效益［1-3］。

由于用户在时间以及空间上的需求不对称，导致共享单车平台在运行一段时间后，共享单车的分布不能很好地满足用户的需求：有些区域的共享单车大量积压，甚至影响路面交通；而有些区域的共享单车数量却很少，导致用户的需求无法得到满足。然而，增加共享单车的数量并不能有效解决上述问题，这不仅会导致许多共享单车空闲，造成资源浪费，还会导致道路堵塞，对环境带来更大的影响。因此如何有效地对共享单车进行调度来提高共享单车平台的长期用户服务率是平台需要解决的关键性问题。共享单车调度问题主要面临着两个挑战：首先，共享单车平台对于共享单车的调度具有一定的预算限制，需要合理地分配预算资源来使平台的长期用户服务率最大化；其次，用户的时空需求也在不断地发生变化，各个区域的共享单车供应量也会随着用户的骑行而不断发生变化。因此需要在预算限制下，对共享单车进行调度以满足不断变化的用户需求，提高平台的长期用户服务率。

传统的共享单车调度方法是由平台的工作人员通过卡车进行拖运调度［4］。然而，在实际情况下，共享单车通常无规律地分布在不同区域，这给卡车托运带来不便。共享单车的调度区域之间的距离通常不远，满足一般的步行距离［5］，所以平台可以通过一定的金钱激励，鼓励骑行的用户在满足自身目的地的前提下适当绕行将单车归还到目标区域，再步行回目的地。本文将对此问题进行研究，设计用户激励下的共享单车调度策略，从而最大化平台的长期用户服务率。

具体地说，本文将在预算限制、用户步行距离限制和用户需求变化情况下，设计激励用户参与的共享单车调度策略，最大化平台的长期用户服务率。本文主要工作如下：

1）在对共享单车的调度问题进行数学描述后，设计了高效的激励用户参与的共享单车调度策略，该策略包含任务生成算法、预算分配算法和任务分配算法。首先通过基于长短期记忆（Long Short‑Term Memory，LSTM）的任务生成算法预测用户在每个时间段各个区域的单车需求量；再通过预算分配算法为每个时间段的调度任务分配预算，该过程是一个序贯决策过程，可以建模为马尔可夫决策过程（Markov Decision Process， MDP），在每个时间段为每个任务分配预算的动作空间是连续的，因此使用适合解决高维连续动作空间的深度确定性策略梯度（Deep Deterministic Policy Gradient， DDPG）算法来分配预算；最后通过基于贪心策略的任务分配算法合理地将任务分配给用户。

2）在摩拜单车数据集上对本文的调度策略进行实验评估，发现任务生成算法对用户未来的单车需求量预测与真实值较为吻合。在不同预算和不同初始单车供应量的条件下，将本文调度策略与贪心调度算法、无预算限制的调度算法、卡车拖运的调度算法进行了两组对比实验，结果表明本文提出的用户激励下的单车调度策略能取得除无预算限制外最好的表现，对共享单车的调度问题有现实的指导意义。

1 相关工作

在用户激励下的共享单车调度策略中，给予用户一定的金钱奖励以激励用户去执行调度任务，这本质上是一种众包管理技术。对于这种时空众包问题，学术上也取得了一些成果。吴垚等［6］讲解了群智感知激励机制相关的工作；童咏昕等［7］对时空众包在数据管理中的应用问题进行了综述，同时他们还在文献［8］中发现贪心算法在时空众包类任务中可以取得较好的效果；徐毅等［9］研究了共享出行中的路线规划问题，同样适用于本文的单车调度问题。

时空众包问题中关于共享单车调度问题的研究也取得了一些成果。Aeschbach等［10］比较早地提出了在没有工人操作卡车或共享单车拖车的情况下，让用户参与到共享单车的调度中，提出了四种不同的控制策略，并通过在一个基于伦敦巴克莱共享单车租赁的真实系统模型上的广泛模拟评估了其有效性。Fricker等［11］提出了同质共享单车的随机模型，研究了用户选择的随机性对满站或空站共享单车数量的影响。他们在研究中表明，简单的激励措施，如建议用户将共享单车返还到两个站点中负荷最小的站点，可以指数性地改善基于卡车调度的方法。Caggiani等［12］将零车时间和满站时间作为关键性能指标，用来反映站内车辆短缺的持续时间和停车位无法使用的持续时间，并依次提出了一个优化模型，使共享单车系统能够在有限的预算下最大限度地提高平台的长期用户服务率。Tong等［13］考虑到时空众包问题中任务和工作者都是动态的，提出了一种强化学习的方法解决时空众包中的任务分配问题。Li等［14］考虑到众包任务与工人的差异性，提出了一种基于强化学习的数据标签框架，使用强化学习方法对任务分配和任务选择进行建模，提高了众包任务的收益。Cheng等［15］在时空众包问题中考虑众包工作者竞争之间的公平性，提出了一种基于预测的匹配方案，解决了众包竞争中的易胜问题。Yang等［16］在拼车出行场景下，提出了一种强化学习方法解决司机与乘客的匹配半径优化问题。Zhao等［17］提出了一个两阶段的数据驱动框架，通过预测未来的时空众包任务并进行匹配，从而提高匹配的任务数量。

在关于用户参与下共享单车调度的具体问题研究中，Ban等［18］提出了一套仿真系统，以测试用户参与下的共享单车调度策略中不同用户参数对用户服务率的影响，如激励给用户的价钱、用户的参与率和额外最大步行距离等。Li等［19］为缓解骑行高峰期的供需矛盾，通过对逆峰骑行者进行奖励以及对平台和政府进行双向激励的方式建立了相关分析模型。Reiss等［20］通过分析慕尼黑共享单车的定位数据，考虑同时使用基于价格折扣的用户调度策略与人工调度策略，以在调度过程中减少碳排放量和平台运营成本。Huang等［21］提出了一种借助已在共享单车平台注册的志愿者来对共享单车进行调度的方法，并且利用稀疏网络来指导志愿者的调度运动。Pan等［22］为用户起始区域的周围区域定价，给予一定的金钱激励用户去其他区域骑共享单车，并提出了一种新的深度强化学习框架来激励用户重新平衡这些系统。他们虽然考虑了整个系统的长期收益，但只考虑了用户在取车时的调度策略，并没有考虑到用户还车时的调度策略以及用户最大步行距离的限制。Duan等［23］扩展了Pan等［22］的深度强化学习框架来促进用户激励，并以自适应的方式来将起始地和目的地激励措施结合。他们虽然考虑到了用户在还车时的调度策略，但只是将共享单车归还到相邻的区域，并没有考虑到用户最大步行距离的限制。

针对现有工作存在的一些局限，本文主要研究在一定预算限制、用户最大步行距离限制、用户时空需求动态变化以及共享单车分布动态变化的情况下，为用户生成调度任务并对调度任务进行预算分配，最后将调度任务合理地分配给用户以实现对共享单车的调度，从而提高平台的长期用户服务率。

2 基本设定

本章介绍了用户激励下的共享单车调度问题，并给出了该问题的相关设定和相关符号的定义。

2.1　问题场景

激励用户参与的共享单车调度问题主要是指共享单车平台将调度任务众包给用户，给予用户一定的金钱激励，激励用户将共享单车归还到合适的区域，从而达到对共享单车进行调度的目的，工作示意图如图1所示。其中：虚线表示用户不执行调度任务的路线；实线表示用户执行调度任务的路线，通过给予用户一定金钱激励用户将单车归还到调度任务所在区域，完成任务后用户再步行到自身目的地。

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

2.2　符号定义

本文主要数学符号如表1所示。

表1　符号定义

2.3　共享单车平台设定

2.4　用户设定

2.5　问题描述

对于调度任务的众包，在用户的时空需求不断发生变化时，各个区域中共享单车的数量只受用户骑行的影响，则有：

调度策略的目标是最大化平台的长期用户服务率，即最小化未骑到车的用户数，表示为：

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

在用户激励下的共享单车调度策略中，共享单车平台通过合理地预测共享单车的用户需求量从而为用户生成调度任务，然后在有限的预算下合理地为每个任务分配预算，最后将调度任务分配给用户。因此用户激励下的共享单车调度策略主要分为三个部分：任务生成算法、预算分配算法以及任务分配算法，如图3所示。

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

3.1　任务生成算法

任务生成算法基于用户历史使用数据对各个区域的用户需求进行预测，再与各个区域现有的单车数量比较分析，进而求得缺车需求，即生成调度任务。

算法1 基于LSTM的任务生成算法。

else：

3.2　预算分配算法

3.2.1马尔可夫决策过程

3.2.2基于DDPG的预算分配算法

DDPG算法［29］是谷歌DeepMind团队提出的一种以确定性策略梯度（Deterministic Policy Gradient，DPG）算法［30］为基础的深度确定性策略梯度算法，可以很好地解决高维状态空间以及连续的动作空间的问题。现有研究中也有许多研究使用DDPG算法解决实际问题［31-32］，并且能取得比较好的效果，因此本文基于DDPG算法来实现用户激励下的共享单车调度策略中的预算分配算法。

对于策略和价值网络的权重参数更新如下：

算法2 基于DDPG的预算分配算法。

if ：

输出每个时间段的预算分配策略.

3.3　任务分配算法

在单个时间段内，当调度任务生成并对其分配预算后，需要将调度任务分配给当前时间段可执行的用户。任务分配算法需要在一定的预算限制和用户的最大步行距离限制下，使用户与调度任务尽可能多地匹配。

传统的二部图匹配中难以附加预算限制的约束条件，所以在匹配过程中可能为了保证完备匹配的结果选择更远的调度任务从而造成成本增加，导致在预算限制下，本可以执行调度任务的用户因完备匹配的结果而无法执行调度任务，所以二部图匹配并不适用于有预算限制的任务分配算法。而贪心匹配策略能保证在预算限制下的局部最优的匹配，即在预算限制下，使执行调度任务的用户数最大化。因为基于贪心匹配策略的任务分配算法中，依据贪心策略找到最小预算的用户‒任务匹配对，直至预算耗尽。因此，本文的任务分配算法适合基于贪心匹配策略来执行调度任务的分配，基于贪心匹配策略的任务分配算法的伪码如算法3所示。

算法3 基于贪心匹配策略的任务分配算法。

4 实验与结果分析

4.1　实验设定

本文实验数据采用摩拜单车数据集（数据集来源为https：//www.heywhale.com/mw/dataset/5eb6787e366f4d002d77c331/file）。每个数据包含以下信息：订单ID、单车ID、用户ID、用户骑行起始时间、结束时间和用户起始位置、结束位置（由经度和纬度指定）等。数据集包含一个月的用户使用数据，工作日和周末的用户需求曲线呈现不同的特征。根据图3可知，工作日的用户需求数据在一天内会呈现双峰，具有一定的规律性，同时在时间上不平衡的用户需求与本文的研究背景相似，而周末的用户需求对于上述规律的呈现并不明显，所以实验中仅使用工作日AM 7：00到PM 8：00的用户使用数据。

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

图4　区域划分及编号

表2　实验参数

4.2　对比算法

本文将用户激励下的共享单车调度策略与无预算限制下的调度、贪心策略调度、卡车拖运下的共享单车调度策略以及未进行调度的情况对比。

1）无预算限制下的调度策略：无预算限制下的调度策略是指在预算分配算法中平台不受预算限制，可以使用任意金钱对调度任务进行预算分配，任务生成算法以及任务分配算法与本文的方法保持一致。由于拥有无限预算激励用户完成调度任务，此算法性能是最好的。

2）贪心策略调度：Tong等［8］在研究中表明贪心策略对时空众包问题能够取得很好的效果，因此本文使用贪心策略调度与本文用户激励下的共享单车调度策略进行对比。贪心策略调度是指将本文用户激励下的共享单车调度策略中的预算分配算法改为基于贪心策略的预算分配，任务生成算法以及任务分配算法与本文的方法保持一致。

3）卡车拖运下的共享单车调度策略：对于卡车调度共享单车，平台在每个时间段决策卡车前往哪个区域进行调度以及在该区域装载或卸载的共享单车数量，来提高平台的长期用户服务率。该过程同样是一个序贯决策过程，因此可以建模为MDP，并且卡车拖运的调度策略只涉及对卡车的调度算法，不用生成与分配调度任务。与用户激励下的调度策略不同，卡车的调度算法并不需要将缺车需求众包给用户，只需要合理的调度卡车，以提高单车长期利用率。

4）未进行调度：即平台不执行任何调度操作。

4.3　实验结果分析

图5为根据某区域内用户的历史需求信息预测该区域内的未来用户需求信息的训练结果，虚线左侧为训练数据，右侧为预测数据。由图5可知，基于LSTM模型可以很好地拟合一个区域内共享单车用户需求的周期性变化，得到接近真实用户需求的预测结果，为后续的用户执行调度任务提供较为准确的用户需求数据支撑。

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

接着从不同的预算限制和不同的单车初始供应量两个方面进行对比实验。图6显示了当各个区域的初始共享单车供应量设定为5，时间周期设置为78个时间段时，在不同预算下，未骑到车的用户数变化情况。随着预算不断增加，共享单车平台未骑到车的用户数会随之减少，这是因为当预算增加时，可激励更多的用户去执行调度任务。从图6中可以看到，用户激励下的共享单车调度策略始终能取得最好的性能。当预算较少时，用户激励下的共享单车调度策略、卡车拖运下的共享单车调度策略以及贪心预算分配的共享单车调度策略相较于其他预算取得的效果较为接近，这是因为预算较少时，没有足够的预算去合理分配给各个时间段，而当预算增加时，用户激励下的共享单车调度策略能够合理的将预算分配给各个时间段，使平台的长期用户服务率更高。总而言之，本文用户激励下的共享单车调度策略在不同的预算限制下，相较于其他调度策略都能取得最好的效果。

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

图7显示了当共享单车平台的预算限制设定为1 000，时间周期设置为78时，在不同单车初始供应量下，未骑到车的用户数变化情况。从图7可以看出，所有调度策略的未骑到车的用户数都会随区域内共享单车的初始供应量的增加而减少。这是因为当区域内共享单车的供应量增加时，平台的缺车需求便会降低，未骑到车的用户数也会减少。同时，由图7可知，除了无预算限制的调度策略之外，本文用户激励下的共享单车调度策略在提高平台的用户服务数方面都能取得最好的效果。而对于无预算限制的调度策略，即使在没有预算限制限制的情况下，未骑到车的用户数仍然不能降为0，这表明不是所有的调度任务都会被用户执行，这是因为调度任务的个数可能会大于可执行调度任务的用户数，且用户有最大步行距离的限制，即使给用户很多的金钱激励，用户也不愿去执行调度任务。

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

5 结语

本文研究了用户激励下的共享单车调度策略，在有限预算以及最大步行距离的限制下制定合理的调度策略以最大化平台长期的用户服务率。本文将用户激励下的共享单车调度策略分为三个步骤完成，即任务生成算法、预算分配算法和任务分配算法。对于任务生成算法，基于LSTM模型对用户未来需求进行预测，预测结果接近真实用户对需求，为后续的调度策略算法提供了较为准确的数据支撑；对于预算分配算法，由于其问题特性可以将其建模为马尔可夫决策过程，因此基于深度强化学习算法DDPG来解决；对于任务分配算法，由于预算的限制使得二部图匹配的性能比贪心策略差，因此基于贪心匹配策略来执行调度任务的分配。使用摩拜单车的真实数据集分别在不同预算和不同初始单车供应量的条件下进行对比实验。实验结果表明，本文用户激励下的共享单车调度策略的性能均仅次于无预算限制的调度策略。这说明本文用户激励下的共享单车调度策略具有现实意义，特别是在共享单车使用量峰值较大的地区，能够有效提高平台长期的用户服务率。

本文研究中假设用户需要真实报告自身信息，在实际情况中，用户可能会谎报自己的目的地、成本等信息以获得更多的收益，因此后续将进一步设计防策略的共享单车调度机制，防止用户的策略性行为，以保证用户能够真实地向平台上报相关信息。

[1] DEMAIO P. Bike‑sharing： history， impacts， models of provision， and future［J］. Journal of Public Transportation， 2009， 12（4）： 41-56.

[2] 李琨浩. 基于共享经济视角下城市共享单车发展对策研究［J］. 城市， 2017（3）： 66-69.（LI K H. Research on the development countermeasures of city shared bicycles from the perspective of sharing economy［J］. City， 2017（3）： 66-69.）

[3] 王怡苏.“共享经济”在中国的发展现状和模式的研究——以共享单车为例［J］. 当代经济， 2017（17）： 140-141.（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.）

[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.

[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.

[6] 吴垚，曾菊儒，彭辉，等. 群智感知激励机制研究综述［J］. 软件学报， 2016， 27（8）： 2025-2047.（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.）

[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.

[9] 徐毅，童咏昕，李未. 大规模拼车算法研究进展［J］. 计算机研究与发展， 2020， 57（1）： 32-52.（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] 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.

[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.

[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.

[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.

[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.

[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.

[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.

[18] BAN S， HYUN K H. Designing a user participation‑based bike rebalancing service［J］. Sustainability， 2019， 11（8）： No.2396.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[28] 杜圣东，李天瑞，杨燕，等. 一种基于序列到序列时空注意力学习的交通流预测模型［J］. 计算机研究与发展， 2020， 57（8）： 1715-1728.（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.）

[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］.https：//arxiv.org/pdf/1509.02971.pdf.

[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.（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.）

[32] 卢海峰，顾春华，罗飞，等. 基于深度强化学习的移动边缘计算任务卸载研究［J］. 计算机研究与发展， 2020， 57（7）： 1539-1554.（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.）

User incentive based bike‑sharing dispatching strategy

SHI Bing1， HUANG Xizi1， SONG Zhaoxiang1， XU Jianqiao2*

（1，，430070，；2，，430033，）

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.

bike‑sharing dispatching; demand prediction; user incentive; Markov decision; deep reinforcement learning

This work is partially 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）.

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.

TP181

A

1001-9081（2022）11-3395-09

10.11772/j.issn.1001-9081.2021122109

2021⁃12⁃15；

2022⁃01⁃18；

2022⁃01⁃24。

教育部人文社会科学研究项目（19YJC790111）；教育部哲学社会科学研究后期资助项目（18JHQ060）。

石兵（1982—），男，江苏泰兴人，教授，博士，CCF会员，主要研究方向：人工智能、多智能体系统；黄茜子（1997—），女，湖北咸宁人，硕士研究生，主要研究方向为：人工智能、多智能体系统；宋兆翔（1997—），男，湖北孝感人，硕士研究生，主要研究方向：人工智能、多智能体系统；徐建桥（1979—），男，湖北武汉人，讲师，硕士，主要研究方向：网络与信息安全、人工智能。