A Deep Reinforcement Learning Framework for Rebalancing Dockless Bike Sharing Systems

摘要

自行车共享为旅行提供了一种环保的方式，并在世界各地蓬勃发展。然而，由于用户出行模式的高度相似性，自行车不平衡问题不断发生，尤其是对于无停靠自行车共享系统，对服务质量和公司收入造成重大影响。因此，如何有效地解决这种不平衡已经成为自行车共享运营商的一项关键任务。在本文中，我们提出了一个新的深度强化学习框架来激励用户重新平衡这样的系统。我们将问题建模为一个马尔可夫决策过程，并考虑了空间和时间特征。我们开发了一种新的深度强化学习算法，称为分层强化定价(Hierarchical Reinforcement Pricing)(HRP)，它建立在深度确定性策略梯度算法的基础上。与通常忽略空间信息并严重依赖精确预测的现有方法不同，HRP使用带有嵌入式本地化模块的分治结构(divide-and-conquer structure) 来捕获空间和时间依赖性。我们进行了广泛的实验来评估HRP，基于中国主要的无码头自行车共享公司Mobike数据集。结果表明，HRP的性能接近24时隙前瞻优化，在服务水平和自行车分配方面都优于最先进的方法。当应用于看不见的区域时，它也能很好地传输.

1. Introduction

[待修改】
自行车共享，尤其是无码头自行车共享，正在全世界蓬勃发展。例如，中国自行车共享巨头Mobike已经在国内外部署了700多万辆自行车。自行车共享作为一种环保方式，通过在用户之间共享公共自行车，为人们提供了一种方便的通勤方式，并解决了“最后一英里”的问题(沙欣、古兹曼和张2010)。与传统的对接自行车共享系统(BSS)不同，例如Hubway，自行车只能出租和归还在固定的停靠站，用户可以在任何有效的地方访问和停放共享自行车。这减轻了用户的担心，当他们想使用自行车时，他们会找到空的码头，或者当他们想归还自行车时，他们会进入完全被占用的车站。

然而，由于大多数用户的出行模式相似，BSS的租赁模式导致自行车不平衡，尤其是在高峰时段。例如，人们大多在早上高峰时间从家里骑车去上班。这导致住宅区的自行车非常少，这反过来抑制了潜在的未来需求，而地铁站和商业区由于共享自行车的压倒性数量而瘫痪。由于用户停车位置不受限制，这个问题对于无停靠基站来说被进一步夸大了。这种不平衡不仅会给用户和服务提供商带来严重问题，也会给城市带来严重问题。因此，对于自行车共享提供商来说，高效地重新平衡自行车至关重要，以便更好地为用户服务，并避免堵塞城市人行道和造成自行车混乱。

自行车再平衡面临几个挑战。首先，这是一个资源受限的问题，因为服务提供商通常会为重新平衡系统提出有限的预算。天真地花费预算来增加自行车的供应不会解决问题，也不符合成本效益。此外，由于监管，允许的自行车数量通常是有上限的。其次，由于自行车和用户数量庞大，这个问题在计算上很棘手。第三，用户需求通常是高度动态的，并且在时间和空间上都在变化。第四，如果用户也参与自行车再平衡，再平衡策略需要有效利用预算，激励用户提供帮助，而不需要知道用户的私人成本。

最近有大量关于自行车再平衡的结果，主要集中在两种方法上，即基于车辆的方法（O’Mahony 和 Shmoys2015；Liu 等人 2016；Ghosh、Trick 和 Varakantham 2016；Li， Zheng 和 Yang 2018；Ghosh 和 Varakantham 2017）以及基于用户的方法（Singla 等人，2015 年；Chemlaet al. 2013 年；Fricker 和 Gast 2016 年）。基于车辆的方法利用多辆卡车/自行车拖车在不同区域通过装载或卸载自行车来实现重新定位。但其重新平衡效果在很大程度上取决于需求预测的准确性。此外，由于难以实时调整重新定位计划以满足波动的需求，因此可能不灵活。此外，由于卡车的维护和行驶成本以及劳动力成本，基于卡车的方法会迅速耗尽有限的预算。相比之下，基于用户的方法提供了一种更经济、更灵活的方式来重新平衡系统，通过为用户提供金钱奖励和替代的自行车上车或下车地点。通过这种方式，用户更有动力在邻近地区取车或还车，而不是在自行车或码头短缺的地区。然而，现有的基于用户的方法往往没有在激励政策中考虑空间信息，包括自行车分布和用户分布。此外，用户相关信息，例如步行到另一个位置的费用，也经常是未知的。

在本文中，我们提出了一个深度强化学习框架来激励用户重新平衡无备审的BSS，如图1所示。具体来说，我们将问题视为自行车共享服务运营商和环境之间的相互作用，并将问题表述为马尔可夫决策过程(MDP)。在这个MDP，一个州由供给、需求、到达和其他相关信息组成，每个行动对应于每个地区的一套货币激励措施，以激励用户步行到附近的地方并在那里使用自行车。直接的回报是满足用户请求的数量。我们的目标是最大化长期服务水平，即满足的请求总数，这是自行车共享服务提供商最感兴趣的(林和杨2011)。我们的方法属于多智能体系统中激励策略的主题(薛等，2016；唐2017；蔡等2018)。

为了解决这个问题，我们开发了一种新的深度强化学习算法，称为分层强化定价算法。HRP算法建立在深度确定性策略梯度(DDPG)算法的基础上(Lillicrap等人，2015)，使用一般的分层强化学习框架(Dietterich，2000)。我们的想法是将整个感兴趣区域的Q值分解成多个较小区域的子Q值。分解能够有效地搜索策略，因为它解决了由于高维输入空间和时间依赖性而导致的复杂性问题。此外，辣根过氧化物酶算法还考虑了空间相关性，并包含一个局部化模块，以纠正子状态和子动作之间的分解和相关性所引入的Q值函数估计偏差。这样做减少了输入空间，减少了训练损失。与现有算法相比，该算法提高了收敛速度，取得了更好的性能。
本文的主要贡献如下:

• 我们提出了一个新的时空自行车再平衡框架，并将问题建模为一个马尔可夫决策过程(MDP)，目标是最大化服务水平
• 我们提出了分层强化定价(HRP)算法，该算法决定每次如何向不同的用户付费，以激励他们帮助重新平衡系统
• 我们使用摩拜单车的数据集进行了广泛的实验。 结果表明，HRP 大大优于最先进的方法。 我们还通过与我们提出的离线最优算法进行比较来验证 HRP 的最优性。 我们进一步证明了 HRP 在不同领域的泛化能力。

2. Related Work

Rebalancing approaches随着BSS的最新发展，研究人员开始研究利用大数据的运营问题(刘等，2017；Y ang等人，2016年；陈等2016；李等，2015)，其中再平衡是最重要的焦点之一。再平衡方法可以分为三类。第一类采用基于卡车的方法，使用多辆卡车。对于对接的基站系统，这些方法可以静态(刘等人，2016年)或动态(戈什，特里克和瓦拉坎瑟姆，2016年)重新定位自行车。第二类侧重于自行车拖车的使用(O’Mahony和Shmoys，2015年；Ghosh和Varakantham 2017李，郑，杨2018)。第三类侧重于基于用户的再平衡方法(Singla等人，2015年；Chemla等人，2013年；Fricker和Gast 2016)。
==Reinforcement learning. ==深度确定性策略梯度算法(DDPG)(Lilli rap等人，2015)建立在确定性策略梯度算法(Silver等人，2014)的基础上，使用深度神经网络来逼近动作值函数，以提高收敛性。然而，传统的强化学习方法不能扩展到高维输入空间的问题。分层强化学习(Dayan和Hinton 1993)将一个大问题分解成几个由子代理学习的较小的子问题，适用于大规模问题。每个子代理只专注于学习其子DP的子Q值。因此，次级代理可以忽略与其当前决策无关的部分状态(Andre和Russell 2002V an Seijen等人(2017年)，以实现更快的学习。

3. Problem Definition

在本节中，我们介绍并形式化了基于用户的自行车再平衡问题，即通过向用户提供货币激励来激励他们帮助重新平衡系统。

考虑一个在空间上分成n个区域的区域，即{r1，r2，…，rn}。我们将一天离散成长度相等的T个时隙，用 T = { 1 ， 2 ， . . . ， T } \mathcal{T} = \{1，2，...，T\} T={1，2，...，T}。让Si(t)表示时隙timeslot t ∈ T t ∈ \mathcal{T} t∈T开始时的区域 r i r_i ri​中的供应，即可用自行车的数量。我们也把 S ( t ) = ( S i ( t ) , ∀ i ) S(t) = (Si(t),∀i) S(t)=(Si(t),∀i)表示为供给向量。时隙t期间区域 r i r_i ri​骑行的总用户需求和自行车到达分别用 D i ( t ) 和 A i ( t ) Di(t)和Ai(t) Di(t)和Ai(t)表示。我们同样将 D ( t ) = ( D i ( t ) , ∀ i ) 和 A ( t ) = ( A i ( t ) , ∀ i ) D(t) = (Di(t),∀i)和A(t) = (Ai(t),∀i) D(t)=(Di(t),∀i)和A(t)=(Ai(t),∀i)分别表示为需求向量和到达向量。让 d i j ( t ) d_{ij}(t) dij​(t)表示在时隙t期间打算从区域 r i r_i ri​到区域 r j r_j rj​的用户数量。

Pricing algorithm. 在每个时隙t，对于在他的当前区域 r i r_i ri​中找不到可用自行车的用户，定价算法 A \mathcal{A} A建议他在 r i r_i ri​的相邻区域中选择自行车，用 N ( r i ) N(r_i) N(ri​)表示。同时， A \mathcal{A} A还向用户提供价格激励 p i j ( t ) p_{ij}(t) pij​(t)(按照用户到达的顺序)，激励他步行到邻近区域 r j ∈ N ( r i ) r_j∈ N(ri) rj​∈N(ri)去取自行车 b h j b_{hj} bhj​，其中 b h j b_{hj} bhj​表示在 r j r_j rj​的第 h h h辆自行车。 A \mathcal{A} A有一个总的再平衡预算 b b b .当预算完全耗尽时， A \mathcal{A} A不能再进一步拨备。

User model对于区域ri中的每个用户 u k u_k uk​，如果当前区域中有可用的自行车，他会选择最近的一辆。否则，如果他从里走到邻近地区去取自行车，就要付步行费。我们用 c k ( i ， j ， x ) c_k(i，j，x) ck​(i，j，x)表示成本，其中x是从他的位置到自行车的步行距离。我们假设它具有以下形式:
c k ( i , j , x ) = { 0 i 等 于 j α x 2 r j 是 r i 的 邻 居 区 域 + ∞ e l s e   (1) c_k(i,j,x)=\begin{cases}0 & i 等于 j\\\alpha x^2 &r_j是r_i的邻居区域\\+\infty & else \ \end{cases}\tag{1} ck​(i,j,x)=⎩⎪⎨⎪⎧​0αx2+∞​i等于jrj​是ri​的邻居区域else ​(1)

这种特殊形式的 c k ( i ， j ， x ) c_k(i，j，x) ck​(i，j，x)是由在(Singla等人，2015年)进行的一项调查推动的，该调查显示用户成本具有凸形结构。请注意，该成本对每个用户都是私有的，并且服务提供商不知道成本函数。对于在当前区域 r i r_i ri​找不到可用自行车的用户，如果他收到一个报价 ( p i j ( t ) ， b h j ) (p_{ij}(t)，b_{hj}) (pij​(t)，bhj​)并接受它，他将获得一个效用 p i j ( t ) − C k ( i ， j ， x ) p_{ij}(t)-C_k(i，j，x) pij​(t)−Ck​(i，j，x)。因此，用户将选择并挑选他可以获得最大效用的自行车 b h j b_{hj} bhj​，并收取价格激励 p i j ( t ) p_{ij}(t) pij​(t)。如果没有报价导致非负效用，用户将不会接受它们中的任何一个，导致未满足的请求。
Bike dynamics让 x i j l ( t ) x_{ijl}(t) xijl​(t)表示在时隙 t t t区域 r i r_i ri​的用户乘用 r j r_j rj​区域的自行车骑行到 r l r_l rl​区域。每个区域 r i r_i ri​的供应动态可以表示为:

S i ( t + 1 ) = S i ( t ) − ∑ ) j = 1 n ∑ l = 1 n x j i l ( t ) + ∑ m = 1 n ∑ j = 1 n x m j i ( t ) (2) S_i(t+1)=S_i(t)-\sum){j=1}^n\sum_{l=1}^nx_{jil}(t)+\sum_{m=1}^n\sum_{j=1}^nx_{mji}(t)\tag{2} Si​(t+1)=Si​(t)−∑)j=1nl=1∑n​xjil​(t)+m=1∑n​j=1∑n​xmji​(t)(2)
等式(2)中的第二项和第三项表示区域 r i r_i ri​中出发和到达的自行车数量。请注意，自行车在不同地区之间有一个旅行时间(travel time)。
objective我们的目标是开发一个最优定价算法 A \mathcal{A} A，激励拥堵区域的用户到邻近区域取车，从而在平衡预算 B B B的前提下，最大化服务水平，即满足的请求总数。

4. Hierarchical Reinforcement Pricing Algorithm

在这一部分，我们提出了我们的分层强化定价(HRP)算法，激励用户有效地重新平衡系统。

4.1 MDP Formulation

我们的问题是一个在线学习问题，其中一个agent与environment交互。因此，它可以被建模为一个马尔可夫决策过程(MDP)，由5个变量 ( S ， A ， P ， R ， R ， γ ) (S，A，P，R，R，γ) (S，A，P，R，R，γ)定义，其中 S 和 A S和A S和A表示状态和动作的集合， P r P_r Pr​表示转移矩阵， R R R表示即时奖励， γ γ γ表示折扣因子。在我们的问题中，在每个时间步长t,