基于深度强化学习的动态共享单车重置问题研究

张建同 何钰林

摘 要：共享单车在为城市出行带来便利的同时，也面临着资源分布不平衡问题。针对单车分布动态变化环境下的共享单车重置问题，提出基于强化学习的实时调度策略结构。构建了面向强化学习的共享单车重置问题模型，利用深度确定性策略梯度算法（DDPG）進行求解，以获得实时调度策略。基于实际单车分布数据，构建了调度过程中的环境交互模拟器。最后，利用强化学习在模拟器中进行大规模数据实验，结果表明算法得到的调度策略能提高系统表现，并且效果好于已有方法。

关键词：共享单车重置问题;深度强化学习;摩拜单车

中图分类号：F 57

文献标志码：A

文章编号：1005-9679（2021）02-0081-06

Abstract：While bikes sharing bring convenience to urban travel， they also face the problem of unbalanced distribution of shared bike resources. A real-time scheduling strategy structure based on reinforcement learning was proposed to solve the repositioning problem of shared bikes under dynamic change of bicycle distribution. In this paper， a model of the bike repositioning problem for reinforcement learning is built， which is solved by deep deterministic strategy gradient （DDPG） to obtain real-time scheduling strategy. Based on the actual distribution data of shared bikes， an environmental interaction simulator is constructed for the scheduling process. A large-scale data experiment using reinforcement learning is carried out in the simulator. The experiment results show that the reposi tioning strategy obtained by the algorithm can significantly improve the performance of the system， and the algorithm performance is better than other existing methods.

Key words：bike repositioning problem; deep reinforcement learning; Mobike

共享单车作为一种便捷、环保的出行方式，近年来在国内大部分城市都已经普及，有效地解决了城市公共交通的“最后一公里”问题。但庞大的共享单车系统在运营管理上也面临诸多问题，其中一个主要问题就是共享单车在时空上分布不平衡，导致有些地方单车短缺，无法满足用户需求，而同时在某些地方单车数量过多，不仅浪费资源，同时给城市管理带来了许多麻烦。

针对共享单车分布不平衡现象，许多学者围绕共享单车重置问题（Bike Repositioning Problem，BRP）展开了研究。从调度主体的角度，共享单车重置问题可以分为基于用户的重置问题（User-Based BRP）和基于运营商的重置问题（Operator-Based BRP）。基于用户的重置通过引导用户用车和还车行为实现系统单车再平衡，一般通过动态定价或者对于在指定站点用车与还车行为给予奖励的方式实现。基于运营商的重置一般是由运营商派遣调度卡车，在单车较多的站点取车，往单车较少的站点放车，实现单车数量再平衡。

基于运营商的重置问题可以分为静态重置问题（Static-BRP，SBRP）和动态重置问题（Dynamic-BRP，DBRP）。SBRP会忽略单车数量和需求的变化，适合夜间调度。对于共享单车重置问题研究更多针对的是传统的有桩单车系统。Chemla等首次建立有桩共享单车的静态完全再平衡模型，允许车辆对站点多次访问，并将站点作为临时存储点，结合分支定界与禁忌搜索算法进行求解。Bulhes等建立了多车型且允许重复访问站点的混合整数规划模型，并应用分支剪界算法框架，提出基于迭代局部搜索的启发式算法进行求解。随着近年来无桩式自由浮动共享单车的发展普及，学者也开始关注相关的再平衡问题。Pal等对有停车位的FFBS的SBRP进行研究，将停在停车位外的单车回收重置于停车位。

静态重置问题研究的是夜间调度，将单车分布视为静态不变的，而单车不平衡现象更多会出现在日间用户频繁使用单车进行转移的情况下。动态重置问题会考虑单车数量和需求的时变特征，更符合目前实际重置需求。对于有桩单车的动态重置问题，Shui等采用滚动周期法将动态重置问题分解为多个阶段静态重置问题进行分阶段求解。Zhang等用再平衡车辆的到达时间将整个动态再平衡过程分解为两个子时段，预测每个子时段内的用户不满意度，与车辆路径结合产生非线性时空网络流量模型进行求解。徐国勋等同样将动态调度时间划分为多个静态时间段，同时考虑多类型共享单车的重置问题。Caggiani等针对无桩式自由浮动共享单车的动态重置进行研究，通过定时执行静态调度策略，实现动态调度。

通过划分时间段进行动态重置的方法能实现各个时间段的重置效果最优，但学者并没有针对如何更好划分时间段进行研究;另一方面，各个时间段的重置效果最优不代表从长期角度也能达到调度效果最优，这是因为一个时间段内的重置即从单車较多的节点取车往单车较少的节点放车，而被取车的节点在未来时间段可能出现缺车，而当前取车操作会加剧未来的缺车程度，从而加剧未来的系统不平衡度与增加调度成本。本文从相对较长的调度周期入手，研究在调度周期内的连续决策而非分阶段决策，应用强化学习（Reinforcement learning， RL）的方法对重置问题进行求解，实现实时动态决策。

1 共享单车重置问题

共享单车重置问题研究的是如何从单车较多的节点取车，往单车较少的节点放车，以实现共享单车资源再平衡，同时实现重置成本最低。

在无桩的自由浮动共享单车系统中，虽然没有固定的停放站点，但用户会自发地将共享单车停放在某些聚集度高的区域，如地铁站出入口等，同时附近的用户也会自发地到这些地点使用单车。本文将这些地点作为重置的节点，以这些节点覆盖的周围区域为范围计算节点的单车数量，调度车会在这些调度节点集中回收与投放单车。设系统中有n个节点1，2，…，n，节点i在时间t的共享单车数量记为numi（t）。当节点单车数量较少时，用户会因为寻找单车的时间成本较高而放弃使用单车，使得用户满意度下降;而当节点单车数量较多时，便会引起道路堵塞、乱停乱放等问题，不利于城市管理，所以应将节点单车数量控制在一定范围内。设节点i在时间t的理想共享单车数量范围为[σdi（t），σui（t）]。当节点单车数量numi（t）<σdi（t）时，节点单车数量不足，需要投放单车，缺少单车数量为qdi（t）=σdi（t）-numi（t）;当节点单车数量numi（t）>σui（t）时，节点单车数量过多，需要回收单车，多余的单车数量为qpi（t）=numi（t）-σui（t）。

在动态重置问题中，由于用户的使用，共享单车分布时刻在动态变化中，调度车需要根据共享单车的实时分布情况进行连续决策，在强化学习中以马尔科夫决策过程（MDP）来形式化描述这种连续决策过程，即在每次决策时，只考虑当前的状态，不考虑先前状态。强化学习通过智能体与环境进行交互来实现连续决策。在共享单车重置问题中，智能体可以作为调度车的抽象理解，本文研究在单调度车条件下的动态调度，使用单智能体强化学习进行求解。

强化学习中马尔科夫决策过程可由五元组{S，A，R，P，γ}表示，其中S表示环境的状态空间，A表示动作空间，R表示智能体执行动作后环境状态改变得到的相应奖励值，P表示状态转移概率矩阵，γ表示未来奖励值在当期的折扣率。智能体基于环境状态，根据相应策略执行相应的动作并作用于环境，环境的状态将会发生改变转移到下一状态，同时智能体获得相应行为的奖励，智能体以最大化累计奖励为目标不断学习，从而学得最优策略。根据状态转移概率是否已知，强化学习可以分为基于模型的强化学习与不基于模型的强化学习，在共享单车重置问题中状态转移概率无法提前获得，所以本文使用不基于模型的方法。其他元素定义如下：

（1） 状态空间

在各个时间均具有一个全局状态st∈S，状态信息包含各个节点共享单车数量，调度车当前所在节点及调度车装载单车数量：

其中，pl为一个n维向量，表示调度车所在节点及装载共享单车的数量，当调度车在节点i且当前装载单车数量为l时，向量pl的第i-1维表示为l，其他维元素为0。

（2） 动作空间

每次决策考虑调度车在未来一个小时会执行的动作，包括调度车下一个访问的节点，访问节点的时间，以及实际调度的数量：

其中，p表示调度车下一个访问的节点，使用独热编码表示。τ表示访问下一个节点距离现在的时间长度，时间粒度为分钟，τ的取值范围为[0，60]。在实际调度中要考虑调度车行驶时间，所以到达下一个节点的时间为t′=t+max（τ，d（i，j）/v），其中i和j分别表示当前所在节点与下一个访问节点，d（i，j）表示两个节点间的距离，v表示调度车平均行驶速度。q表示调度车在下一个节点调度单车的数量，q>0表示从节点取车，q<0表示往节点投车，在实施调度操作时需要考虑调度车装载量、剩余容量、节点拥有单车数量，所以实际调度数量为：

其中，C为调度车容量，L为调度车装载的共享单车数量。

（3） 奖励

智能体在当前系统状态执行动作后使得系统状态发生变化，产生奖励，以引导智能体选择更优动作。在本文中，设定重置目标为在调度周期内，系统缺少的单车数量与多余的数量最小化，同时调度成本最小化。设智能体在时间t基于系统状态st执行动作at，调度车从节点i在时间t′到达节点j进行调度，而取/放每辆单车时间都设为l，调度车在时间t″=t′+q′×l完成取/放车操作。由于只有j受到调度操作的影响，所以奖励计算为

式（4）中包含三项，分别计算在时间t″调度完成后，在t″之后的时间[t″，Te]（Te为调度周期终止时间）在节点j的累计多余单车数量的减少量、累计缺少单车数量的减少量、调度车行驶距离，w1、w2、w3分别代表三项的权重。

基于以上强化学习的共享单车重置问题定义，该问题可以被认为是一辆调度车智能体在动态变化的共享单车系统中，获得环境状态信息后，执行调度动作与环境交互，环境收到动作影响并返回对智能体的奖励和下一个状态信息，从而构成一个完整的强化学习迭代过程。

2 基于深度强化学习的共享单车重置

强化学习可分为基于价值（value-based）的方法和基于策略（policy-based）的方法，还有将基于价值与基于策略相结合的方法。基于价值的方法根据动作价值来选择执行的动作，动作价值函数公式为

这里T表示时间步，在时间步T的环境状态sT下，执行动作aT后时间步转移到T+1，系统状态变成sT+1。根据Bellman方程可以转化为递推公式：

在迭代过程中，智能体根据价值函数利用ε-贪婪的方法选择动作。价值函数更新方法有蒙特卡洛法与时序差分法，其中时序差分法价值函数更新公式为

其中，α为步长因子。基于价值的强化学习需要利用Q值表记录每个状态下每个动作的价值，当状态较多时，将需要维持一个非常大的Q值表，内存资源可能没法满足。一个可行的解决方法是近似地计算Q值，而放弃维护完整的Q值表。利用深度学习的方法，使用神经网络近似计算价值的方法，即深度强化学习。深度强化学习需要维护一个经验回放集合，保存智能体在探索过程中的经验{sT，aT，rT，sT+1}，作为神经网络训练集。基于价值的强化学习算法有Q学习（Q-Learning），深度Q网络（DQN）等。

基于价值的方法有其局限性：只适用于离散动作，无法处理如时间、数量等连续动作，且对于受限状态下的问题处理能力不足，无法解决随机策略问题。基于策略的方法能更有效地解决上述问题。基于策略的方法同样使用深度学习的方法近似计算策略函数π（s，a），即在状态s选择动作a的概率，在迭代过程中通过基于蒙特卡罗法的策略梯度的方法优化近似策略函数，但该方法需要完全的序列樣本才能做算法迭代，同时需要使用奖励的期望值来计算状态价值，会导致行为有较多的变异性，参数更新的方向可能不是策略梯度的最优方向。将基于价值与基于策略的方法相结合，可以充分发挥两者的优点，避免其缺点。将基于价值与基于策略的方法相结合的算法有Actor-Critic、A3C、DDPG等。

本文利用DDPG（Deep Deterministic Policy Gradient）求解共享单车重置问题。DDPG基于确定性策略，即相同的策略，在同一个状态下，采取的动作不是基于概率分布的，而是唯一确定的，则策略变成π（s）=a。DDPG包含4个神经网络：

1. Actor当前网络：网络参数为θ，负责根据当前状态s选择当前动作a，与环境交互生成新状态s′，得到奖励r。

2. Actor目标网络：网络参数为θ′，负责根据新状态s′选择新动作a′，参数θ′定期从θ复制。

3. Critic当前网络：网络参数为ω，负责计算在当前状态s执行动作a产生的价值Q（s，a，ω）。

4. Critic目标网络：网络参数为ω′，负责计算在新状态s′执行新动作a′产生的价值Q（s′，a′，ω′），参数ω′定期从ω复制。

应用于共享单车重置问题的DDPG算法流程如下：

输入：Actor当前网络，Actor目标网络，Critic当前网络，Critic目标网络，参数分别为θ，θ′，ω，ω′;衰减因子γ;软更新系数μ;批量梯度下降样本数m;目标网络参数更新频率η;对动作产生扰动概率p0;重置计算周期[Ts，Te];最大迭代次数T。

输出：Actor当前网络参数θ;Critic当前网络参数ω。

1） 随机初始化θ，ω，θ=θ′，ω=ω′，当前迭代轮次i=1;

2） 初始化状态s为初始状态;

3） 向Actor当前网络输入状态s，得到动作a={p，τ，q};

4） 产生随机数，如果小于概率p0，对动作进行随机扰动，得到新动作a′={p′，τ′，q′};

5） 执行动作a，得到新状态s′，奖励r;

6） 如果状态s′的时间t′

7） 将经验{s，a，r，s′，done}存入检验回放集合D;

8） 令s=s′;

12） 如果η|i，则更新Critic目标网络和Actor目标网络参数：

13） 如果s′是终止状态，当前轮次迭代结束，否则转到步骤3）;

14） 如果i=T，则结束迭代，否则令i=i+1，转到步骤2）。

算法中，4个网络均选用全连接BP神经网络进行计算。为了避免算法过早收敛、陷入局部最优，在迭代过程中对动作进行随机扰动，增加学习覆盖率。设定扰动概率p0，在每轮迭代中产生随机数，如果小于概率p0，则随机选择一个原来目标节点p的邻域节点p′作为新目标节点，对τ，q分别加一个随机数，得到τ′，q′，同时τ′，q′应分布控制在其定义范围之内，从而得到新动作a′={p′，τ′，q′}。调度的效果以三个指标进行衡量：所有节点在调度周期内累积短缺共享单车数量减少比例RL、累积多余共享单车数量减少比例RO、总调度路径长度RC，其中RL与RO计算如下：

3 实验结果与分析

3.1 数据概述与环境模拟器构造

本研究使用的数据来源于爬虫爬取的上海某区域摩拜单车分布数据，爬虫每10分钟爬取一次，记录研究区域内停放的共享单车的编号、停放的经纬度位置以及爬虫爬取时间。基于共享单车分布数据，利用基于密度聚类的方法发现6个高密度点作为调度节点，利用Voronoi图划分节点覆盖区域，以覆盖区域内单车数量表述节点单车数量。由于共享单车数量以天为单位周期性变化，选取一天作为调度周期，各节点共享单车数量在一天内的变化如图1所示，其中包含3个日间数量增加节点与3个日间数量减少节点。由于数据每10分钟收集一次，所以将调度周期离散化为时间点，时间点的间隔为10分钟，长度为一天的调度周期共包含144个时间点，记为t1，t2，L，t144。

基于调度周期各时间点的各节点单车数量，构建调度过程中共享单车数量变化模拟器。在调度过程中，调度车在节点进行取车或者放车操作，在此之后的时间该节点的共享单车数量都会发生改变，这种改变既包含当前调度行为的改变，又包含用户使用量的变化。在数据中共享单车的数量变化由用户实际使用归还单车行为引起，但数据并不能反映实际用户需求，特别是在单车数量较少时，用户可能无法在可接受的时间内获得共享单车，而选择其他交通方式。当调度车往节点投放共享单车时，节点的用户使用数量可能会增加，节点单车数量越少增加越明显;当调度车从节点回收共享单车时，节点的用户使用量可能会减少，节点单车数量越少减少越明显。设在时间ti，i∈{1，L，144}，在节点j回收/投放单车数量q，节点j在ti的单车数量变为num′j（ti）=numi（tj）-q，而在此后的时间，单车数量变为

3.2 调度结果分析

设置调度车默认容量C=50，平均行驶速度为500m/min。设置DDPG中衰减因子γ=0.9，软更新系数μ=0.01，批量梯度下降样本数m=64，目标网络参数更新频率η=100，对动作产生扰动概率p0=0.4×0.9i，其中i为迭代次数，最大迭代次数T=2000。基于模拟器利用强化学习进行调度，调度时间为4：00-20：00，得到的调度方案为（3， 4：00， 15）→（1， 8：00， 30）→（6， 9：00， -28）→（3， 9：50， -17），三元组三个元素分别表示调度节点编号、调度时间与调度单车数量。调度结果如图2与表1中DDPG所示。实验结果显示调度完成后所有节点在调度周期内累积短缺共享单车数量减少了14%，累积多余共享单车数量减少了29%，总调度路径长度为6.3km。可以得到结论，使用强化学习方法能得到有效的实时动态调度方案，使得共享单车系统运营效率得到提高。

为了验证强化学习算法解决动态共享单车重置问题的优势，将算法与传统划分为多阶段静态重置问题的方法对比，每个阶段的静态重置问题视为单商品取送货问题，每个阶段以阶段起始时间的共享单车分布情况计算节点调度需求。对比以1小时与2小时为固定长度划分时间段的方法，两种方法得到的调度结果如表1中MSSBRP_1与MSSBRP_2所示。从实验结果可以看出，DDPG的强化學习方法相对于划分为多阶段静态重置问题的方法在减少累积短缺共享单车数量、减少累积多余共享单车数量与调度路径长度三个指标上表现更好。

4 结论

共享单车数量具有时变性的特点，动态的单车调度策略更能满足实际的共享单车重置要求。本文提出利用强化学习方法解决实时动态的共享单车重置问题，并创造性地提出适用于强化学习的共享单车重置问题建模方法。基于爬虫爬取的共享单车现实使用情况数据，构造了调度过程中系统环境变化模拟器，并利用强化学习方法进行模拟调度。结果显示，调度完成后，系统累计缺少单车数量减少14%，累计多余单车数量减少29%。同时对比传统将动态问题划分为多阶段静态问题的方法，强化学习方法无论在调度效果还是在调度成本方面，都有更好的表现。在未来的研究中可以对模型进行扩展，考虑多车辆调度、允许在节点暂存单车、故障单车回收等情况。

参考文献：

[1] CAGGIANI L， CAMPOREALE R， OTTOMANELLI M， et al. A modeling framework for the dynamic management of free-floating bike-sharing systems[J]. Transportation Research， 2018， 87：159-182.

[2] CHEMLA D， MEUNIER F， CALVO R W. Bike sharing systems：solving the static rebalancing problem[J]. Discrete Optim，2013， 10：120–146.

[3] PFROMMER J， WARRINGTON J， SCHIDBACH 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.

[4] FRICKER C， GAST N. Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity[J]. EURO Journal on Transportation and Logistics， 2014.

[5] BULHES T， SUBRAMANIAN A， ERDOGAN G， et al. The static bike relocation problem with multiple vehicles and visits[J]. European Journal of Operational Research， 2018， 264（2）：508-523.

[6] PAL A， ZHANG Y. Free-floating bike sharing：solving real-life large-scale static rebalancing problems[J]. Transportation Research Part C-Emerging Technologies， 2017， 80：92-116.

[7] SHUI C S， SZETO W Y. Dynamic green bike repositioning problem：a hybrid rolling horizon artificial bee colony algorithm approach[J]. Transportation Research， 2018， 60：119-136.

[8] ZHANG D， YU C H， DESAI J， et al. A time-space network flow approach to dynamic repositioning in bicycle sharing systems[J]. Transportation Research Part D：Methodological， 2017， 103：188-207.

[9] 徐国勋， 张伟亮， 李妍峰. 共享单车调配路线优化问题研究[J]. 工业工程与管理， 2019， 1（11）：45-57.

[10] LILLICRAP， TIMOTHY H， JONATHAN P， et al. Continuous control with deep reinforcement learning[J]. Computing Research Repository， 2015.

[11] HERNNDEZ-PREZ H， SALAZAR-GONZLEZ J J. The One-Commodity Pickup-and-Delivery Travelling Salesman Problem[C]. Lecture Notes in Computer Science， 2003.