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

基于深度强化学习的动态共享单车重置问题研究 张建同 何钰林摘 要：共享单车在为城市出行带来便利的同时，也面临着资源分布不平衡问题针对单车分布动态变化环境下的共享单车重置问题，提出基于强化学习的实时调度策略结构构建了面向强化学习的共享单车重置问题模型，利用深度确定性策略梯度算法（DDPG）進行求解，以获得实时调度策略基于实际单车分布数据，构建了调度过程中的环境交互模拟器最后，利用强化学习在模拟器中进行大规模数据实验，结果表明算法得到的调度策略能提高系统表现，并且效果好于已有方法关键词：共享单车重置问题;深度强化学习;摩拜单车：F 57文献标志码：A：1005-9679（2021）02-0081-06Abstract：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）σ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值表，内存资源可能没法满足一个可行的解决。