Dynamic Bike Reposition: A Spatio-Temporal Reinforcement Learning Approach
ABSTRACT
共享单车系统在很多城市都开始使用了，尽管拥挤和空的站点都会导致客户的流失。当前，运营者试图在系统运行中不断地在站点间调度车辆。然而，如何在一个长时间的范围内有效地调度自行车使得乘客的流失最少还没有得到解决。我们提出了一个基于时空强化学习方法的自行车调度模型解决这个问题。首先，一个互相依赖且内部平衡的聚类算法用来对站点聚类。类簇有两点属性，每个类簇类内平衡而且类间独立。因为在很大的系统中有很多三轮车调整自行车，聚类对于减少问题的复杂度来说很重要。其次，我们给每个类簇分配了多辆三轮车，对类内自行车进行调度。我们设计了一个时空强化学习模型对每个类簇进行策略的学习，目标是在长时间范围内降低用户的流失。为了学习每个模型，我们设计了一个深度神经网络来估计它的最优长期价值函数，最优策略可以从这个函数中轻松地推导出来。除了将模型定义成多智能体的方式，我们还通过两个时空剪枝规则减少了训练的复杂度。其三，我们基于两个预测其设计了一个系统模拟器来预测训练和评估调度模型。在Citi Bike的真实数据集上的实验验证了我们的模型的有效性。
1 INTRODUCTION
共享单车系统给公民提供了便利的出行方式。用户可以在一个随机的站点租或返还自行车，通过刷卡，生成一条单车使用记录。然而，因为在一个城市内的单车使用是非常不平衡的，系统中经常出现没有车的空站点以及缺少可用停车位的拥挤站点，导致乘客的流失。当前，系统运营者使用 dynamic bike reposition 来处理这个问题，也就是，在系统运行中使用三轮车不断的在站点间调整车辆。然而，如何在长时间范围内调整车辆使得顾客流失最少还是一个问题。实时监测并不是一个好的方案，因为在观测到不平衡后对车辆重新分配太晚了。仅仅基于单车使用预测来调度只会导致一个贪心且短视的策略，在长时间来看不会是最优的。我们总结了解决这个问题的三个挑战。
A bike-sharing system is complex and dynamic. 系统中经常有几十辆三轮车在几百个站点间调度车辆。在这么一个大的系统内协同调度很复杂，更不用说系统是在运行中保持动态的情况了。难以预测系统的动态性有三点原因：1) 图1. A 展示出了一个月每个小时的租车需求。可以看到，每天的租用模式变化得很剧烈，受多个复杂的因素影响，比如天气、事件以及站点间的相关性。2) 很多移动看起来是随机的。图1. B的第一张图表示出了历史通勤，也就是2016年4月到10月每个工作日的早上这段期间，平均至少发生一次的移动，只占了18%。我们用图1. C的例子解释了这种现象：从A到B，站点间的移动有12种可能，用户一般会根据哪个站点有可用的车辆或车位，选择随机的一条路线，使12条路线中的一条变成可能的频繁移动路线。3) 影响车辆使用的外部因素非常不平衡，比如，晴天时长要比雨天时长多很多。因此，在每个条件下训练一个学习器不能保证在次要条件下的准确性。
A single bike reposition has long-term effect. 一个简单的调度是好是坏不是那么简单就能判断的。我们将用图2的两个例子详细描述一下，红圈表示没有可用车位的站点，绿圈表示一个空的站点；带有一个数字和一个时间标记的实线箭头表示在那个时段会有多少辆车从起点租用并返还到目的地；虚线箭头表示了一个三轮车的调度是如何进行的；$t_0 < t_1 < t_2$。首先，一个简单的调度会影响系统内的车辆使用很长的一段时间。如图2. A) 所示，如果一个三轮车到了空站点 $s_1$，在 $t_0$ 时段放了5辆车，在 $s_1$ 的可用车辆就变成了$5$，在 $t_1$ 时段 $s_1$ 可以服务 $5$ 位即将到来的租车者；这5个租车者骑车到 $s_2$ 在 $t_1 < t_2$ 还车，4位到来的租车者在 $t_2$ 时段 $s_2$ 车站想租车的也可以使用那些还回来的车。因此，一个调度可以服务的额外用户的数量很难估计。其次，当前的调度会影响以下情况。如图2. B) 所示，如果一个三轮车到站点 $s_1$ 在 $t_0$ 时段带走了 9 辆自行车，那里的可用车位就变成了 9，因此9个用户就可以在 $t_1$ 时段把他们的自行车还到 $s_1$。然而，因为 $s_1$ 离 $s_3$ 太远，在完成picking up之后，这辆三轮车不能在 $t_2$ 时段之前将5辆自行车运送到空站点 $s_3$，来服务5位即将到来的租客。
Uncertainties in partical reposition. 在实际的调度过程中有很多不确定因素。尽管我们可以预测系统的动态，我们不能保证预测与实际完全一样，因为模型会有错误以及随机噪声。此外，完成一次调度的时间也是不同的，比如，从 $s_1$ 运送车辆到 $s_2$ 今天可能需要10分钟，明天可能就要15分钟，尽管方法可能一样。这可能是由于变化的外部因素导致，比如，恶劣的天气状况以及交通的拥挤程度，或是随机噪声。因为动态调度是在系统运行的时候工作的，时间很重要，这也可以从上面两个例子看出来。这些不确定因素，还有长期影响，使得优化模型非常复杂，甚至是无法工作。
我们提出了一个基于时空强化学习的动态调度模型来解决这三个挑战。我们的贡献可以归纳为4点：
- 我们提出了一个两步聚类算法，称为 Inter-Independent Inner-Balance算法，简称 IIIB。这个算法首先在系统中迭代地将独立的站点聚类生成小的功能区域，保证每个区域更稳定的租车需求以及车辆移动模式。其次，这个算法根据区域间的移动，将这些区域聚类成组，保证每个类簇是类内平衡且类间独立的。将整个系统分为各个类簇，极大地减少了问题的复杂程度。
- 我们基于两个预测器生成了一个系统模拟器。一个是O-Model，通过一个基于相似度的KNN模型预测每个区域的租车需求，考虑复杂的影响因素，解决了不平衡样本的问题。另一个模型是I-Model，通过一个基于车辆移动的推断方法，预测每个区域的还车需求。
- 我们提出了一个时空强化学习模型，STRL，为每个类簇学习一个最优的类内调度策略。STRL的状态通过捕获系统动态性以及实时的不确定性仔细地设计出来。因为状态以及行动空间很大，我们设计了一个深度神经网络为每个STRL估计最优的长期价值函数，通过这个可以推断出它的最优调度策略。除了将模型定义成多智能体的方式，我们还通过两个时空剪枝规则减少了训练的复杂度。
- 我们在Citi Biki 2016年4月到10月的数据集上证明了我们的模型比baselines更有效。
2 OVERVIEW
这部分定义了符号以及相关术语
2.1 Preliminary
Definition 1 Transition. 一个移动 $f_{ij} = (s_i, s_j, \tau_i, \tau_j)$ 是一辆自行车的使用记录，描述了一辆自行车从地点 $S_i$ 在时刻 $\tau_i$ 被租用以及在地点 $s_j$ 时刻 $\tau_j$ 返还。
Definition 2 Demand. 时段 $t$ 的地点 $s_i$ 的租用需求 $o_{i,t}$ 是想在 $s_i$ 时段 $t$ 内租用自行车的顾客的个数，包括成功以及失败的。时段 $t$ 内地点 $s_i$ 的返还需求 $r_{i,t}$的定义类似。
Definition 3 Episode. 一个时段 $E$ 是一天的一个长时段，在这个时段中，我们想最小化总的客户流失。我们在3.1.2中详细地定义了我们问题中的 Episodes，保证了一些约束，而不是随机选取的。
2.2 Framework
如图3所示，我们的模型包括了一个离线学习过程以及一个在线调度过程。这个学习过程有三个部分，分别是IIIB聚类算法，系统模拟器生成过程以及每个类簇的STRL模型。
IIIB Clustering Algorithm. 为了解决第一个问题，也就是一个系统很大且很复杂，我们提出了一个两步IIIB聚类算法。首先对那些相近且有相似移动模式的站点聚类，在系统中生成小的功能区域。然后基于他们区域间的迁移规律，将区域聚类成组。给每个类簇分配多辆三轮车完成类簇内区域间的调度，而不是类间的自行车调度。
Simulator Generation. 为了训练和评估调度模型，我们基于两个预测器生成了一个系统模拟器，也就是分别预测每个区域的租车需求和还车需求的O-Model和I-Model。对于一个指定的时段，比如周六早上7点到7点半，我们先根据历史的天气统计结果生成一个可能的天气状况，比如晴天，然后O-Model预测每个区域周六早上7点到7点半晴天的租车需求。基于这些预测，每个区域的租车需求由泊松过程模拟。每次一辆自行车被租用，I-Model就会估计它的目的地区域以及到达时间，并且追踪它。每个区域的还车事件通过连续地检查自行车是否到达那里来生成。
STRL Model. 我们提出了一个STRL模型，对每个类簇学习一个最优的类内调度方案。我们这个基于强化学习的模型是多智能体形式。每次一个三轮车完成它最后的调度，它会不等待其他调度的完成，紧接着开始一个由方案生成的新的调度。新的调度基于当前状态生成，这个调度会很仔细地定义，来捕获系统动态性和实时的不确定性。一个状态包含多个因素，如，每个区域当前自行车和车库的可用性；实时预测的租车和还车需求；三轮车的状态，包含它自身的以及其他的；当前的时间，等等。我们设计了一个深度神经网络为每个STRL估计最优的长期价值函数，通过这个我们能推导出最优的调度策略。网络在系统模拟器迭代地训练出来，在图3中用灰色高亮了出来。
Online Reposition. 在学习过程之后，我们在每个类簇上会获得一个神经网络。在在线过程中，当一个三轮车需要一个新的调度时，我们先确定它在哪个类簇中，通过O模型和I模型生成它的当前状态。然后，对应的网络给当前状态中每个可能的调度估计最优的长期价值。选择最大价值的调度并返回。
3 METHODOLOGY
3.1 IIIB Clustering Algorithm
3.1.1 Region Generation
如图1. C)所示的例子，站点间的随机迁移使得车站间的单车调度不是那么有意义，因为我们只需要保证在 $s_1$ 或 $s_2$ 或 $s_3$ 有可用的自行车，在 $s_4$ 或 $s_5$ 或 $s_6$ 或 $s_7$ 有可用的车位。考虑每个站点的车辆和车位的可用性，从 $A$ 到 $B$ 的用户可以选择在哪里租车并且还车。受到这个现象的启发，我们对这个区域周围的几个车站聚类，对目标区域周围的车站进行聚类，生成两个小的区域，也就是 $s_1$，$s_2$ 和 $s_3$ 形成了一个区域，$s_4$，$s_5$，$s_6$ 和 $s_7$ 形成了另一个区域。然后，我们只需要保证每个区域车辆和车位的可用性即可。我们认为一个区域的租车需求比一个单独的车站更稳定，更规律；而且，两个区域间的迁移比两个站点间的迁移更频繁。
为了正式地阐述这个想法，我们基于两个约束在一个系统中生成了一些区域。1) 一个区域的站点应该和其他的站点相近，保证这个区域内顾客的方便。2) 一个区域内的站点应该有相似的OD区域，使得区域间的迁移更专一且更频繁。生成这些的区域的方法是一个迭代的方法，称为二部聚类算法[2]，这个算法会基于车站的位置和迁移模式进行聚类。
基于获得的这些区域，我们分析了 Citi Bike 中历史的车辆使用数据，证实了上述的两个优势。如图1. A)底部所示，一个区域的租车需求更稳定，更规律，因此更容易地精确预测。随机迁移的问题也可用得到解决。图1. B)右图展示了2016年4月到10月工作日的早上区域间的通勤，占了56%。可以看到，得到的区域间迁移模式更简单，使得还车需求预测更简单且更精确。这里获得的区域可用看作是城市中小的功能区，比如居民区周围的车站很可能组成一个区域，而在工作区周围的可能形成另一个。我们对这些区域聚类成组，而不是在整个系统中的这些屈居间直接调度，而且因为两个原因，我们只在类簇内开展调度。1) 聚类可用进一步减少问题的复杂度。2) 司机一般只对城市内的一个区域比较熟悉。
3.1.2 IIIB Clustering Insight
获得到的类簇应该有两个性质，每个类簇的内部平衡以及类簇间的相互依赖。
Inner-Balance.
