自适应的共享单车动态平衡

何涛 张健 徐鹤

摘  要： 自行车共享系统成功的关键之一是重新平衡运营的效率，每个区域的自行车数量必须通过卡车运送以恢复到需求值。不同的时间区间用户的用车需求波动较大，体现出“潮汐现象”的特征动态。为了有效地解决“潮汐现象”，减少区域之间车辆的调配以及满足用户的需求，通过深度学习提取区域分布特征以及强化学习自适应学习环境的结合，提出一种自适应的共享单车动态分布，旨在通过外部环境确定每个区域内不同时间点的不同状态的需求值。仿真结果表明，所提出的算法可以快速平稳、实时满足区域内的单车需求并减少区域之间的单车调配数量。

关键词： 共享单车; 动态平衡; 深度学习; 强化学习; 区域分布; 单车调配

中图分类号： TN915?34; TP301.6                     文献标识码： A                  文章编号： 1004?373X（2019）16?0169?05

0  引  言

由于共享经济的兴起以及日益增长的环境、能源和经济问题，近年来共享交通发展迅猛。在各种形式的共享使用手机中，公共自行车共享系统（Bicycle Sharing Systems）[1?2]越来越受欢迎，数据表明，2015年有超过500个自行车共享计划在至少49个国家运行，共有100万辆自行车。随着数量的增加，共享单车系统通常会出现“供不应求”和“供过于求”的不均衡现象，在一定的时间段内租车量持续高于或者低于还车辆，并且会根据节假日或者天气因素，以一定时间为循环周期重复出现，严重影响了系统的运行效率，“潮汐現象”是共享单车系统的设计和运行中普遍存在的规律。城市边远地带的一些用地功能复合低的区域，用户出行的需求趋势相同，出行时间集中，短时间内对车辆的需求量大而波动频繁是潮汐现象形成的主要原因。

对于“潮汐问题”，目前使用的办法是自行车共享再平衡算法（Bike Sharing Rebalancing Problem）[3]， 采用额外调配的车辆，实现共享自行车的重新分配，以最大限度地降低总成本，通过自行车的高效率，低成本调度，有效提升公共自行车的流转量，减少因为过饱和和过负载造成的阻碍，及时满足供给和需求的相对均衡，保证用户的正常使用。自行车共享再平衡算法采用静态的优化方法，是一类特殊的商品的拾取和交付能力的车辆路由问题，通过设定混合整数线性规划公式，并对公式设置约束条件从而求解车辆的路由问题和运输问题。系统一般会在系统关闭的时候或者是使用量比较低的时候，例如夜间，按照每一个区域的需求量，对单车数目进行重新分配以及配送来实现系统的静态平衡。

由于“潮汐现象”发生在一天中的多个时间段，而周期比较长的静态平衡显然不能有效地解决“潮汐现象”[4]，增加了车辆分布的不均匀和闲置率，降低了单车的有效使用，同样也增加了区域之间的单车的调配难度和时效。对于共享单车在每一个区域的重新分配的需求量会依据客户网络中的客户需求以及节假日、工作日等时间因素为参考进行预测，这样的模型缺乏稳定性，难以按照环境的变化而做出相对应的处理，自适应性相对较差。

2  算  法

2.1  模型架构

本文首先介绍提出的自适应的多时间段共享单车动态平衡框架，依据共享单车的随机性和多状态性，结合深度学习强大的特征提取和强化学习的策略定值能力，把子空间的状态通过预处理传输给算法模型，根据算法模型的概率输出，做出相应的动作以获取最大的累积奖赏值，并根据动作生成新的区域状态，按照设定的时间，不断重复该动作以实现各区域之间的共享单车动态平衡。其整体框架如图2所示。

图2  算法整体框架图

Fig. 2  Overall framework diagram of algorithm

在子空间系统的大量共享单车分布区域中，假设存在n个单车集中分布区域[Pii=1，2，…，n]，每一个区域的共享单车需求数量分别依次对应为[Sii=1，2，…，n]，单车需求数量Si为约束条件-k～+k的范围之间任意整数值，默认共享单车分布区域内的总数满足用户的需求，所以各区域需求的总和为0，即[i=0nSi=0]。

由于强化学习模型在与环境的交互过程中的转移样本和时间序列是高度相关的，但是模型要求训练数据之间是相互独立的，所以在每个更新都使用经验回放机制从经验池D中随机采样mini?batch数量的转移样本作为训练数据来更新网络的权值[11]。在训练的初始阶段，经验池D中并没有足够的转移样本来训练网络，实验中，通过采取随机策略的方式存储足够多的转移样本到经验池D中，以防止在学习的初期由于训练数据太少，而导致学习较差的泛化性和陷入局部最优解的问题。

奖赏函数[12]是所有强化学习算法所必须的，为强化学习提供了目标，本文设计一个奖赏函数来映射每个状态，以表达每一个动作的内在期望。奖赏函数先将当前状态通过检测网络求出检测结果，然后计算偏差，用偏差的变化来表征当前状态的奖赏值。定义奖赏函数[Ra（s，s′）]，[s′]表示状态s执行动作a后的状态。当动作的转移使各区域的需求更加均衡，奖赏值为1;否则，当动作的转移使各需求值更加离散，奖赏会按照偏差做出相应得惩罚。

[R′ai（s，s′）=abs（s′i-0）k，   abs（s′i-0）>θ1，                              abs（s′i-0）<θ]  （8）

[R=i=1NR′ai（s，s′）]    （9）

因为强化深度学习是免模型学习，对于动作的选择在初期是未知的，通过选择多样的动作用于后期的迭代学习，可以使模型按照状态?动作函数自行选择并快速收敛。在动作的选择初期，是一个无策略的学习过程，通过贪心策略可以尝试所有可能的动作。后期动作可以从自身或者他人的记忆中学习经验，动作选择服从概率为[1-ε]贪婪策略[12]，并且服从概率为[ε]的非贪婪策略。

动作空间是在观察到一个状态以后，必须从当前的可选的动作中选择一个动作。为了保持分布的均衡和减小区域之间的调度数量，动作为需求高的区域向需求低的区域的转移单车的数量，区域按照缺少或者多余的数目排序，需求低的区域接收需求高的区域的转移数目。[σ]是转移动作和区域最大需求量k的比例，[σ的取值为{0%，10%，20%，30%，40%}]，相对应需求高的区域动作为a={k·0[%]，k·10[%]，k·20[%]，k·30[%]，k·40[%]}。

2.2  模型的训练过程

1） 存放转移样本的经验池D容量初始化为N，记忆单元D={e1，e2，…，eN}，初始化深度学习网络的参数[θt]，[θt]的值服从以0为中心，方差为1的截断正态分布。

2） 初始化随机生成子空间中各区域的共享单车需求状态S，状态S服从-k～+k的均匀分布，状态S经过数据的预处理后通过算法模型。

3） 从动作集合A中选择动作a，这里采取的是[ε-greddy]策略，以概率[1-ε]选择一个随机的动作a来鼓励探索，否则以1-[ε]的概率选择a=[maxQ]（S，a;[θt]）及对应Q值最大的，观察得到下一个状态S′和通过奖赏函数得到的奖赏值r，把与环境交互得到的轉移样本et=存入到经验池D。

4） 判断经验池D是否已经到达容量N，否则返回步骤2）直到经验池到达容量。

5） 从经验池D中随机采样数量固定的小批量的转移样本进行模型的训练及后期的使用，设置[y=r+γmax QS′，a;θt]近似表示值函数的优化目标也就是最优值函数，并且误差函数为[L=QS，a-r+γmax QS′，a;θt2]，使用式（6）求偏导更新参数[θt]的值。

6） 判断损失函数L是否小于阈值T，否则返回到步骤5）直到损失函数小于阈值T。

7） 判断随机生成状态S是否已经把全部的状态组合遍历结束，否则返回步骤2），直到状态S遍历完成。

3  算法实验及分析

实验环境采用Python 3.5和tensorflow深度学习框架对算法进行仿真研究、分析算法性能和处理数据采用Matlab语言。假设在大量共享单车分布区域中，每一个区域的需求数在-k～+k内随机分布，并且区域的需求数总和为零。经验池的容量N设置为1万个转移样本，mini?batch的规模为32，式（7）中的折扣因子[γ]设置为0.99，行为策略[ε-greddy]的参数[ε]设置为从训练开始到10万区间线性递加的形式。每次的结果取10次仿真实验结果的均值。

分布的区域个数对于模型的训练速速和模型的收敛都有很重要的作用，通过设置不同的个数来比较区域数对于模型的影响。在共享单车分布范围内，分别在区域数为3，4，5，6，7的情况下对模型进行训练和预测。训练的误差值和奖赏值如图3所示。

图3a）中，当区域个数为5时，随着训练步数的增加，误差值不断缩小，奖赏值不断增大;当步数为20万步左右时，误差值趋于稳定，保持不变，说明模型已经固定并且算法是合理的，而奖赏值随着步数增加依然增长。由图3b）可以得知，区域个数为3，4，5，7的折线在区域个数为6的下方，这是由于较多的区域个数可以满足各种动作的选择，可以有效地提升回报值;但是区域个数7的奖赏值在区域个数6的下方，说明个数太大时难以快速满足区域的动态平衡。所以在动作为a={k·0%，k·10%，k·20%，k·30%，k·40%}的情况下，区域个数为6的模型的奖赏值是最大。

在机器学习中，提高算法的稳定性首先想到的是降低学习率。较高的学习率可能会导致过拟合，传统的强化学习中使用较高的学习率会导致学习曲线发散和振荡;使用小的学习率似乎能够解决振荡问题，因为每一步都采用了更小的步长进行更新。在区域个数为6，并且选择的动作为a={k·0%，k·10%，k·20%，k·30%，k·40%}的情况下，式（7）中的学习率[α]分别选择为0.99，0.5，0.099。得到训练的误差值和奖赏值如图4所示。

从图4a）可以看出，奖赏值的大小和学习率[α]成正相关关系，较高的学习率可以提高奖赏值，使单车分布更加均衡;但是通过图4b）可以得出，更小的学习率可以使学习过程快速地趋于平稳，减少学习的训练时间。

通过对比使用自适应的共享单车动态平衡算法和没有使用算法来证明算法的可行性，在一片区域中区域个数为6，学习率[α]为0.99，使用学习好的模型进行模拟，极差值和方差值如表1所示。使用算法和未使用算法的极差对比如图5所示。通过图5可以看出，在使用自适应的共享单车动态平衡算法后，极差值明显下降，说明算法在满足单车动态平衡方面是可行的。

4  结  论

目前共享单车一般采用静态平衡，使得共享单车不能实时满足用户的需求。为了有效地解决共享单车分布的问题，通过深度学习和强化学习的有机结合，提出自适应的共享单车动态平衡算法。本算法的意义在于，在已知环境的背景下，对多区域的不同时间段进行综合考虑，自适应的选择状态所映射的动作，追求长时间下多区域的奖赏最大化，减小区域之间的调配数量并满足每一个区域的需求量。但是，本算法在时间复杂度方面比较高，在学习和模型稳定方面需要较长的时间，在未来的工作中，将寻找更好的状态?动作更新方法，使模型快速平稳。

参考文献

[1] GAVALAS D， KONSTANTOPOULOS C， PANTZIOUS G. Design and management of vehicle sharing systems： a survey of algorithmic approaches [M]// OBAIDAT M S，  NICOPOLITIDIS P. Smart Cities and Homes. San Francisco： Morgan Kaufmann， 2016： 261?289.

[2] LAPORTE G， MEUNIER F， CALVO R. Shared mobility systems [J]. A Quarterly Joumal of Operations Research， 2015， 13（4）： 341?360.

[3] DELL′AMICO M， HADJICOSTANTINOU E， LORI M， et al. The bike sharing rebalancing problem： Mathematical formulations and benchmark instances [J]. Omega， 2014， 45： 7?19.

[4] MA T， LIU C， ERGODAN S. Bicycle sharing and public transit [J]. Transportation research record： journal of the transportation research board， 2015， 2534（1）： 1?9.

[5] DONGHYUN K， CHANYOUNG P， JINOH O， et al. Convolutional matrix factorization for document context?aware recommendation [C]// Proceedings of 10th ACM Conference on Recommender Systems. Boston： RecSys， 2016： 233?240.

[6] 谭国真，王莹多.一种基于深度强化学习的交通信号自适应控制方法：CN201710258926.4[P].2017?04?19.

TAN Guozhen， WANG Yingduo. A traffic signal adaptive control method based on deep reinforcement learning： CN201710258926.4 [P]. 2017?04?19.

[7] DUCHI J， HZAAN E， SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization [J]. Journal of machine learning research， 2011， 12（7）： 2121?2159.

[8] SILVER D， HUANG A， MADDISON， et al. Mastering the game of go with deep neural networks and tree search [J]. Nature， 2016， 529： 484?489.

[9] MNIH V， KAVUKKCUOGLU K， SILVER D， et al. Human?level control through deep reinforcement learning [J]. Nature， 2015， 518： 529.

（上接第173页）

[10] O′NEILL J， PLEYDELLl?BOUVERIE B， DUPRET D， et al. Play it again： reactivation of waking experience and memory [J]. Trends in neurosciences， 2010， 33（5）： 220?229.

[11] SCHAUL T， QUAN J， ANTONOGLOU I， et al. Prioritized experience replay [J]. Computer science， 2015， 11（19）： 1511.

[12] 刘全，翟建伟.一种基于视觉注意力机制的深度循环Q网络模型[J].计算机学报，2017，40（6）：1353?1363.

LIU Quan， ZHAI Jianwei. A deep recurrent Q?network based on visual attention mechanism [J]. Chinese journal of computers， 2017， 40（6）： 1353?1363.