Dual Policy Reinforcement Learning for Real-time Rebalancing in Bike-sharing Systems

共享单车系统实时再平衡的双策略强化学习

同作者文章：《A Reinforcement Learning Approach for Dynamic Rebalancing in Bike-Sharing Systems》

摘要

自行车共享系统在缓解交通拥堵和促进更健康的生活方式方面发挥着重要作用。然而，确保其可靠性和用户接受度需要有效的策略来重新平衡自行车。本研究介绍了一种新颖的方法来解决车队中车辆的实时重新平衡问题。
该方法采用双重政策强化学习算法，将库存决策和路由决策分开，与以前同时做出这两个决定的方法相比，提高了真实性和效率。
我们首先在连续时间框架内将库存和路径规划子问题表述为多智能体马尔可夫决策过程（multi-agent Markov Decision Process）。随后，我们提出了一种基于DQN的双重策略框架(DQN-based dual policy framework)来联合估计价值函数，以最小化需求损失(jointly estimate the value functions, minimizing the lost demand)。为了便于学习，在第一到达先服务规则下运行的全面模拟器中进行了实验，该规则使计算跨不同需求场景的即时奖励成为可能。
我们在各种数据集上进行了广泛的实验，这些数据集由历史实际数据生成，并受到时间和天气因素的影响。
我们的提议算法在以前的基线方法上展示了显著的性能改进。它为运营商提供了宝贵的实践见解，并进一步探索了将强化学习纳入现实世界动态规划问题中的可能性，为更智能、更健壮的城市交通解决方案铺平了道路。

一、引言

自行车共享系统（ Bike-Sharing Systems，BSS）的发展在缓解城市交通拥堵和减少二氧化碳排放方面发挥了重要作用[16]。然而，用户行为的随机性和高峰时段需求通常导致站点不平衡，需要高效的重新平衡策略来最小化需求损失。

我们的目标就是通过调度车辆，在一天之内，实时地将单车从过剩的站点转移到短缺的站点,从而大大减少那些因为找不到车或者没地方停车而无法满足的用户需求，也就是所谓的丢失需求。

动态自行车重新定位问题（The Dynamic Bike Repositioning Problem,DBRP）解决了网络中站点之间实时重新分配自行车以满足白天波动需求的问题[18]。通常，运营商会使用一组车辆来重新分配站点之间的自行车，以尽量减少未满足的需求。这一任务涉及库存决策（需要收集或投放多少辆自行车）和路线决策（接下来访问哪个站点）。图1的左侧部分展示了简单的BSS示例，包括四个站点和两辆车队。**马尔可夫决策过程（MDPs）**最近被用于解决DBRP问题，在之前的研究中[例如，3；13；19]已经证明了它们可以捕捉到BSS决策的序列性质。

相比之下，基于时序离散化的混合整数规划（Mixed Integer Programming,MIP）模型在[5；11]中被广泛使用，但必须在离散化精度和计算效率之间取得微妙的平衡。强化学习（RL）技术为解决DBRP中的MDP模型提供了希望。它们直接从与环境的交互中学习最优策略，而无需显式建模其动态，但由于高维动作空间，目前适用性通常仅限于单辆重置和小站网络RL的缺点。此外，现有的MDP模型同时在车辆到达站点时做出库存和路线决策。当库存决策完成时，系统状态已经改变，这可能导致在车辆到达时对路线决策进行优化。由于系统动态演变发生在库存重新平衡操作期间，因此解耦库存decoupling inventory和路由决策routing decisions至关重要。

💡 同时决策的影响
举例：在t=1的时候，做出选择站点A并根据当前的情况做出调整10辆车的决策。等在t=10的时候，车辆到达站点A时候，发现调整10辆车不是最优的。这就是需要对库存决策进行再调整。

✋ what is decoupling inventory?
“Decoupling inventory”是指在生产或供应链流程中，将不同阶段的库存进行分离，以创建缓冲区，从而减少因某一环节的中断（如原材料短缺、设备故障或生产速度不一致）而对整个流程造成的影响。这种库存策略的核心目标是通过设置“安全库存”或“缓冲库存”来确保生产流程的连续性

本研究提出了一种用 于DBRP 的 时空RL算法，该算法在连续时间框架下处理多车辆情况下的BSS问题，并解决了当前MIP车辆协调方法中离散化时间的局限性。我们引入了一个双重策略来解耦库存和路由子问题。这使我们能够更真实地捕捉环境动态并最小化需求损失。如图1所示，两个Deep Q网络（DQNs）被联合训练以近似Q值函数，用于库存和路由子问题。这种方法确保了在库存重新平衡期间系统变化是细粒度的，而不是像以前的RL模型那样同时进行库存和路由决策。为了促进学习过程，我们使用了一个实时BSS模拟器来评估基于BSS环境的各种用户需求场景下的即时奖励。我们进行了广泛的实验，包括与MIP模型和具有单一策略或同时进行库存和路由决策的RL模型的比较，以及消融研究(ablation studies)。我们提出的双重政策RL算法（ Dual Policy RL algorithm,DPRL）显著优于所有基准，证明了DPRL在实时重新平衡应用中的有效性。由于其他相关问题，如提货和配送以及拼车，与DBRP共享许多共同特征，涉及库存和路由决策，我们的方法也将作为指导和示例，用于BSS以外的供应链和运输优化任务。

💡 DPRL的核心思想
将原本耦合的库存决策和路径决策解耦开来。这意味着，当一辆车到达一个站点时，它首先根据当前的系统状态，比如各站点的单车数量、用户需求预测等，决定取或放多少单车。这个库存操作完成后，系统状态已经更新，然后车辆再基于最新的状态信息，决定下一步去哪个站点。这种分步决策的方式，能够更真实地反映系统动态变化，避免了同时决策可能导致的路径选择滞后于系统状态变化的问题，从而提高了决策的效率和响应速度。

✋ what is ablation study?
Ablation Study（消融实验）是一种通过移除或修改模型、算法或系统中的某些组件，以评估其对整体性能影响的研究方法。其核心思想是通过“控制变量法”来分析各部分对整体性能的贡献

• 并非“删除所有组件” ：消融实验并非完全移除所有组件，而是有选择地移除部分组件以观察其影响。
• 需结合其他方法：消融实验通常与其他方法（如交叉验证、基准测试）结合使用，以确保结果的全面性

本文其余部分组织如下。第2部分回顾了相关文献。第3部分将DBRP建模为多智能体马尔可夫决策过程（MMDP），而第4部分介绍了我们的双重策略RL方法，用于实时再平衡解决方案。第5部分提供了数值实验和分析，以及一个消融研究。最后，第6部分总结了这项工作并概述了未来的研究方向。

二、相关工作

现有的大多数工作模型使用 MIP 模型[5；14；11等]来模拟 DBRP。为了保持可操作性，MIP模型需要简化问题，离散化规划期限，并假设每个车辆在一段时间内的站点访问次数是恒定的。不幸的是，这些限制并不现实，可能会阻碍BSS对车辆协调和重新平衡的充分优化。

作为一种顺序决策工具，MDP作为BSS中的一种有意义的替代方法，已经越来越多地应用于DBRP。尽管有潜力，DBRP中MDP的采用仍然处于起步阶段，并受到其计算复杂性的阻碍。[文献3]和[文献4]率先提出了基于MDP的方法，分别引入了单个和多个车辆的动态前向策略。[文献7]开发了一种决策支持工具，旨在最小化未满足的用户需求，采用了一步政策改进方法，而[文献13]提出了一种用于单个车辆重新平衡的策略近似算法。MDP在DBRP中的应用不断拓展,对计算复杂性和车辆同步的研究显得尤为重要。

---

文献3： Dynamic lookahead policies for stochastic-dynamic inventory routing in bike sharing systems (共享单车系统中随机动态库存路径的动态前瞻策略)
文献4：The multi-vehicle stochastic-dynamic inventory routing problem for bike sharing systems(自行车共享系统的多车辆随机动态库存路径问题)
文献7：Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station(共享单车系统中的动态重新定位策略；如何确定自行车站的优先级以及如何重新平衡自行车站)
文献13：Dynamic intra-cell repositioning in free-floating bike-sharing systems using approximate dynamic programming(使用近似动态规划的自由浮动自行车共享系统中的动态单元内重新定位，)

---

RL训练代理通过与环境互动并学习最优策略来做出连续决策，从而解决MDP模型。在复杂优化任务中的成功促使了其在BSS中的应用，其中的复杂性类似于游戏、金融和组合优化[21；15；1；2；12]。

动态重新平衡涉及两个关键决策：车辆应访问的下一个站点（路由决策），以及车辆到达时要取走或放下自行车的数量（库存决策）。

• [8] 提出了一个聚类算法来对站点进行分组，并引入了一个RL模型来学习每个集群内的重新平衡策略。
• [22] 提出了一种基于转移学习的分布式RL解决方案，仅关注单个政策（库存决策）。这种方法为每个站点分配一个单独的代理，负责探索其相应站点的最佳重新平衡策略。
• [23] 提出了一个基于RL的重新平衡模型，使用离散时间下的DQN模拟器，忽略了租赁、归还和重新平衡操作的序列。
• [10] 提出了一种用于多车辆DBRP的RL方法，其中库存和路由决策同时进行。
• [13] 和 [20] 研究了单辆DBRP，而 [8] 考虑了在少于 30 个站点的小型集群中重新平衡的多车辆DBRP。

---

文献22：A distributed reinforcement learning solution with knowledge transfer capability for a bike rebalancing problem（一种用于自行车再平衡问题的具有知识转移能力的分布式强化学习解决方案）
文献10：A reinforcement learning approach for dynamic rebalancing in bike-sharing system(共享单车系统动态再平衡的强化学习方法)
文献13：Dynamic intra-cell repositioning in free-floating bike-sharing systems using approximate dynamic programming(使用近似动态规划的自由浮动自行车共享系统中的动态单元内重新定位)
文献20：Rebalancing dockedbicycle sharing system with approximate dynamic programming and reinforcement learning(用近似动态规划和强化学习重新平衡停靠共享单车系统)

---

现有文献要么仅关注库存决策，要么同时进行库存和路线决策。前者忽略了动态再平衡中路线决策的重要性，而后者则忽视了系统状态变化在库存再平衡操作中的影响，导致次优的路线决策。此外，在进行同步库存和路线决策时，需要仔细考虑该框架。这些决策可以是基于车辆到达（对于到达站点的库存决策）或基于车辆离开（对下一个站点的库存和路线决策）。

为了解决这些限制，我们提出了一种新颖的双重政策RL方法，该方法将库存和路线决策解耦。具体来说，在到达一个站点后，库存策略决定要取走或放下多少自行车。一旦库存操作完成，路由策略将决定下一个要访问的站点。这种分离提高了系统对动态变化的真实性和响应性，为实时重新平衡问题提供了更细致和有效的解决方案。

3 Problem Formulation

3.1 The Dynamic Bike Repositioning Problem (DBRP)

我们考虑一个具有|N|个站点和V辆车的车队进行自行车重新平衡的BSS。每个站点$n\in N$有一个容量$C_n$的车库，每辆车$v\in V$有一个容量${\hat{C}}_v$。系统初始状态由每个站点$n\in N$处的自行车库存$d_0^n$以及每个车辆$v\in V$的库存$p_0^v$和位置$z_0^v$站点i和j之间的距离和行驶时间分别为$D_{i,j}$和$R_{i,j}$
装载或卸载一辆自行车所需的时间用$\beta$分钟表示。当租赁或归还请求无法满足时，将发生需求损失。自行车不可用或可用桩位不足是主要原因。主要目标是在整个站点网络中优化车辆重新平衡策略，最小化需求损失。问题参数的完整列表总结在表1中。

3.2 Multi-agent Markov Decision Process (MMDP) Formulation

我们以一个MMDP的形式来表述DBRP，其特征在于元组(S, A, W, R, γ)，其中S是系统状态集，A是代理的动作集，W表示状态转移概率，R是累积折扣总奖励，γ是强调短期奖励而非长期奖励的折扣因子。代理通过一系列步骤操作，每个动作都导致一个新的状态和相关奖励。相关的注释总结在表2中。

State Space.

在每一步k ∈ K，状态$S_k\in S$封装了系统的综合状态，包括时间、车站和车辆信息。 我们用$S_k=(t_k,d_k,H_k)$，其中$t_k$是当前时间，$d_k=(d_k^n,\forall n\in N)$表示每个车站的库存。 车辆状态表示为$H_k=(b_k^v,g_k^v,p_k^v,m_k^v,o_k^v,i_k^v，\forall v\in V)$，

其中$b_k^v$表示车辆v所处的当前站点或刚刚离开的站点，
$g_k^v$ 表示车辆v正在前往的当前站点或下一个站点。注意，当车辆v执行库存操作时，$b_k^v$和$g_k^v$可以是相同的车站。
$o_k^v$表示当前库存的车辆v，
而$m_k^v$是车辆v完成当前库存操作后或到达下一个车站时的预计时间。
剩余重新平衡操作的数量（即，下货或上货）由$o_k^v$指示。
引入二进制指示器$i_k^v$来促进库存和路由决策的解耦：当车辆v到达一个站点并做出库存决策时，$i_k^v=0$；如果车辆v完成库存操作并继续做出路由决策，则$i_k^v=1$。

车站状态（站点1的库存，……，站点n的库存，……）
车辆状态(当前站点或者刚离开的站点， 当前站点或者下一个站点，车辆的库存，预估完成操作的时间，装卸数量，指示器)

Action Space

在每一步$k\in K$，选择一个行动$a_k\in A$，表示库存决策或路线决策。对于库存决策，设$l_k^v$表示该行动，对于路线决策，设$z_k^v$表示该行动。为了简化库存决策，我们考虑三个预定义的补给水平 µ i ∈ [ 0 , 1 ] ， ∀ i ∈ { 1 , 2 , 3 } µ_i ∈ [0, 1]，∀i ∈ \{1, 2, 3\} µi​∈[0,1]，∀i∈{1,2,3}，代表站点容量的比例。车辆的库存调整目标是达到以下水平之一：${\mu }_1{C}_{g_k^v}、{\mu }_2{C}_{g_k^v}$ 或 ${\mu }_3{C}_{g_k^v}$。可行的库存决策取决于车辆的能力${\hat{C}}_v$、当前车辆库存$p_k^v$以及站点库存$d_k^{g_k^v}$。因此，步骤k时车辆v的$l_k^v$（库存决策）定义如下：

• ${\mu }_i{C}_{g_k^v}$ :预定义的比例*下一站站点$g_k^b$的总容量= 预定的站点库存容量(即预定的目标库存值)
• ${\mu }_i{C}_{g_k^v}<d_k^{g_k^v}?$:做比较。若预定义的库存值< 在第k步时站点的自行车容量值。拾取操作
  • 则min{（车辆v的容量-车辆v的库存）=(车辆v的剩余空间)，（下一个站点$g_k^v$的当前库存值-预定义的库存值 ）=(拾取的车辆数目)}
• ${\mu }_i{C}_{g_k^v}>d_k^{g_k^v}?$:做比较。若预定义的库存值> 在第k步时站点的自行车容量值。卸载操作
  • max{ (-车辆v的库存) ， (下一站点$g_k^v$的当前库存值-预定义的库存值)=(卸载的车辆数目)}

在第一个案例中，Equation (1) 中的 $l_k^v>0$ 表示车辆需要从站点取回 $l_k^v$ 辆bikes。
在第二个案例中，$l_k^v<0$，表示车辆需要将$|l_k^v|$个自行车停放在站点。
在第三个案例中，没有进行重新平衡操作。
路由决策由$z_k^v$给出，指示车辆v ∈ V将访问的下一个站点。一个约束被应用以确保没有两个车辆同时指向同一个站点。

DBRP在这里被表述为使得只有当特定车辆到达或离开某个站点时才进行操作，从而允许在较小的动作空间中实现独立的行动，考虑到其他车辆的状态。这确保了决策是实时的，并且能够持续适应系统中的全局状态变化。

Rewards and Returns.

采用细粒度的模拟器来捕捉即时奖励$r_{k+1}$，这是在两个状态之间发生的所有站点需求损失的负值。
累积折扣回报$R_k=\mathbb{E}[{\sum }_{j=0}^{K-k-1}{\gamma }^j{r}_{k+j+1}]$反映了从一系列行动中长期聚合的奖励。折扣因子γ ∈ [0, 1]逐渐减少未来奖励的价值，随着步骤j的增加。规划解决方案通过策略$\pi \in \Pi$编码，其中$\Pi$表示所有可能策略的集合。策略$\pi (a_k|S_k)$作为指导在给定状态s下采取行动的概率的策略。总体目标是识别最大化总预期奖励的时间最优策略$\pi \ast$

4 Dual Policy Reinforcement Learning

本节介绍了我们的DPRL框架，该框架将库存和路由决策解耦，以实现实时重新平衡。这种分离使得对系统动态的调整更加精确和响应迅速，显著减少了需求损失并提高了用户满意度。我们首先介绍为所提双重政策框架量身定制的MMDP，然后是DPRL的学习管道。

4.1 Tailored MMDP for Dual Policy

图2说明了我们连续时间双策略框架内的状态和行动。存在两种不同的状态类型：库存状态和路由状态，它们共享第3.2节中描述的相同组件。一个步骤对应于车辆到达或离开站点完成重新平衡操作后的时间点。
例如，当车辆$v_i$到达站点$g_k^{v_i}$时，会发生库存状态$S_k$，而所有其他车辆要么在他们的站点进行重新平衡，要么移动到下一个站点。此时，生成一个行动$l_k^{v_i}$，决定$v_i$在步骤k处装载或卸载的自行车数量。然后系统转移到下一个状态$S_{k+1}$，这可能代表$v_j$（如图2所示）的一个路由状态，或者对其他车辆来说是一个路线状态。在车辆$v_i$完成库存平衡操作后，在离开站点进行路由规划之前，会做出路由决策。

在我们的双重政策框架中，即时奖励计算为连续两个相同类型状态之间的时段内发生的租赁和归还需求的负值。
这里，库存奖励$r^I(S_k，a_k)$示例显示了持续时间$[t_k，t_{k+1}]$内的情况。相邻两个库存状态是k与k+1
如果状态$S_{k-1}$是路由状态，则相应的路由奖励表示为$r^R(S_{k-1}，a_{k-1})$，用于区间$[t_{k-1}，t_{k+2}]$。相邻两个路由是k-1和k+2

在以前的RL框架[8；23；10等]中，车辆$v_i$的库存和调度决策是在状态$S_k$时同时做出的。然而，当车辆$v_i$在$t_{k+2}$完成库存操作时，在$t_k$所做的调度决策可能不再是最优的，因为系统变化，特别是用户需求，发生在区间$(t_k，t_{k+2})$期间。我们的双重政策框架通过将库存和调度决策解耦来解决这一问题，考虑了系统 以更现实和粒度的方式进行更改。因此，我们的方法侧重于车辆到达站点时的库存决策，并在当前库存操作完成后推迟路由决策。这使我们能够在决定下一个要访问的站点之前考虑最新的系统状态。类似地，在离开站点时做出路由决策，并将库存决策推迟到到达下一个站点时。这一双重政策框架确保决策是基于实时全球系统状态的，从而提高了再平衡战略的整体效率和响应能力。

💡思考1：每一步的时间长是否是均匀的？且多车辆如何去确定步骤的长短呢。
答：在实际操作中，每个步骤的时间确实不是固定的。 多车辆协调：（1）论文使用4辆容量40的车辆（2）通过MMDP模型中的车辆状态向量(bₖᵛ,gₖᵛ等)实时跟踪各车位置和任务（3）决策时会避免多车同时前往同一站点.
步骤的时长计算：$t_{k+1}=t_k+max(\beta \times |l_k^v|(装卸时间),R_{b_k^v,g_k^v}(移动时间))+需求事件触发延迟$

💡思考2：双重策略，这里有库存装卸策略和路由选择策略。在图2中主义到，装卸策略是有即时奖励的，而路由选择似乎没有奖励的。那么如何判断路由动作的好坏呢？
答：延迟奖励机制：
（1）路由决策的奖励会体现在下一个库存决策点
（2）选择好的路线会使得车辆到达时：a.目标站点需求缺口更大（提高装卸操作的价值）b. 减少途中其他站点的需求损失

价值函数传导：
（1）路由策略的Q网络通过TD误差学习：$Q(s_k^R,a_k^R)\leftarrow r_{k+2}+\gamma maxQ(s_{k+2},a^{\prime })$ （其中sₖᴿ是路由状态，rₖ₊₂是后续库存奖励）
协同优化指标
（1）是否将满载车辆引向缺车站点
（2） 是否将空车引向积压站点
（3）移动时间是否最小化

💡 思考3：时间线 $t_{k-1}(路由)\to t_k(库存)\to t_{k+1}(库存)\to t_{k+2}(路由)$, 为什么在$t_{k-1}$的即时奖励要持续在[k-1,k+2]之间呢？
答：路由奖励$r^R(S_{k-1}，a_{k-1})$ 覆盖的是从路由决策时刻 到完成后续装卸后的新路由决策时刻 的完整周期。这样设计是因为：
（a) 单个路由动作的效果需要等到车辆完成装卸并到达新站点才能完整评估
（b) 包含了移动时间和装卸时间内的所有需求损失

举例 ：时间线：t₀(路由) → t₁(库存) → t₂(路由) → t₃(库存) → t₄(路由)
在t₀做的路由决策，其效果持续到：

• t₀-t₁：移动时段
• t₁-t₂：装卸时段
• t₂时刻：到达新路由决策点
  因此t₀路由的奖励计算必须包含这三个阶段的需求损失

4.2 DPRL Pipeline

他提出了 DPRL 框架来解决实时重新平衡问题，并在图3中进行了说明。在离线学习阶段，模拟器根据代理采取的行动和各种需求场景下的需求计算库存和路由奖励并更新系统状态。奖励、系统状态、状态类型和动作共同用于训练双重策略，以实现库存和路由策略的优化。一旦离线学习完成，就将经过优化的双重策略应用于在线重新平衡阶段，确保高效地分配自行车以满足需求波动。这一阶段涉及在测试的各种需求场景集上部署策略,以评估其性能。

BSS Simulator

为了确保对奖励函数的逼真近似和准确更新系统状态，使用了事件驱动的模拟器作为交互环境，在该环境中，事件（重新平衡操作、租赁和归还）按照先到先服务的原则执行。如果起始站点至少有一个可用的自行车，则完成租赁。然后为此次成功的租赁安排一个到达时间在目的地站点的返回时间。如果起始站点为空，则标记为丢失需求的租赁。同样，如果目的地站点有空闲的停泊点，则完成返回。否则，自行车将被重定向到最近的有空闲停泊点的站点，并标记为丢失需求。值得注意的是，只有当相应的租赁成功时，才会发生丢失返回的情况。重新平衡操作与客户行程同时进行，并取决于车辆到达站点的时间。这些操作按事件发生的顺序依次执行。

Dual DQN.

为了动态再平衡，我们使用两个DQN来共同训练库存决策网络和路由决策网络。

DQN是一种离策略的时差（TD）强化学习技术，估计价值函数并预测给定状态下特定行动的预期回报，从而指导代理朝向更有利的结果。鉴于库存和路由决策在动态再平衡中的共享特性，我们利用类似的神经网络架构，仅在输出层上有所不同。输入层与第3.2节中定义的状态观察的维度相匹配。随后，两个全连接密集层后面是修正线性单元（ReLU）激活函数。输出层针对每个网络的动作空间进行调整，使网络能够基于给定状态生成所有可能动作的Q值。具体来说，库存网络的动作空间包括三个填充水平，而路由网络的动作空间则包含车站数量（见第3.2节）。

💡 思考1：库存网络的动作空间包括了3个填充水平，那么也就是要确定每个站点的调整后的自行车数量是吗？
答：是的。输入：当前车辆库存，站点容量，当前站点 的自行车数量。 输出：实际装卸数量(正为取车，负为存车)
举例说明学习目标：在特定状态(如早高峰的办公区站点）自动选择最优填充水平，例如：

• 住宅区早晨优先选择μ₃（多存车）
• 商业区傍晚优先选择μ₁（多取车）

💡 思考2： 路由网络的动作空间则为包含车站的数量。那么假设有100个车站，那么其动作空间为100？这个动作空间也是不小的啊。文中没有其他操作去限制一下当前站点所面临的下一个动作空间的集合吗？

1. 显式约束（硬限制）

• 避免重复分配：通过状态变量 $H_k$ 中的$b_k^v$ （当前车辆位置）和$g_k^v$ （目标位置）确保：
  z k v ∉ { g k v ′ ∣ ∀ v ′ ∈ V } z_k^v \notin \{g_{k}^{v'} | \forall v'\in V\} zkv​∈/{gkv′​∣∀v′∈V} 即禁止多车同时前往同一站点

• 可达性约束：在时间窗口$[t_k,t_{k+2}]$ 内，仅考虑车辆可物理到达的站点： A k v = { j ∣ R b k v , j ≤ τ m a x } \mathcal{A}_k^v = \{ j | R_{b_k^v,j} \leq \tau_{max} \} Akv​={j∣Rbkv​,j​≤τmax​} (${\tau }_{max}$为最大允许移动时间）

2. 隐式约束（学习引导）

• 启发式初始化：训练初期采用混合启发式规则（公式3-4）$u(n)=\alpha \underset{\text{距离优先}}{\underbrace{(1/D_{x,n}{)}^m}}+(1-\alpha )\underset{\text{库存匹配}}{\underbrace{[g(n){]}^m}}$ 其中$g(n)$计算站点-车辆库存匹配度，通过参数m控制探索强度：
  • $m=0\to$均匀随机搜索
  • $m\to \infty \to$贪婪策略
• 课程学习：在训练过程中动态调整$\alpha$和m，从强约束逐步放松

3. 动作空间压缩技术

• 近邻采样：实际实现时只对距离最近的K个站点（如K20）计算Q值
• 分层决策：(1)先用聚类将站点分为M个区域（如M=10）(2)先选区域再选具体站点

4. 实验中的实际处理在论文的60站点实验中：
   原始动作空间：60
   实际有效动作：
   平均移动时间约束下：约15-25个可达站点
   经过库存匹配筛选后：通常剩余3-8个候选站点

Heuristic Initialization.

在训练过程中，我们采用启发式规则作为初始路由策略来加速双重DQN训练过程。离开车站时，启发式路由会将一个相对满的车站分配给一个相对空闲的车辆，反之亦然，并同时考虑车站之间的距离。我们用$u(n)$表示当车辆i从其当前车站x在第k步出发时选择车站n的概率。该分布定义为：

在这些方程中，${\rho }_1(n)$ 表示车站 n 与出发站 x 之间的归一化和指数化的逆距离。这确保了更靠近的车站有更高的概率，符合对附近旅行的直观偏好。此外，${\rho }_2(n)$ 指的是车站 n 相对于车辆 i 的相对库存水平。如方程（4）所述，函数g(n)计算了相对于其总容量的可用停靠点/自行车比例，这与可能在站点n下落或取走自行车的车辆库存水平的比例相一致。 如果车辆i相对满，则相对空闲的站点将具有较高的概率ρ2(n)，使它们更有可能被选择，反之亦然。权重α调整这两个因素的影响，使我们能够关注重新平衡问题的不同方面。值得注意的是，当m→0时，分布趋向于具有均匀概率的随机路由，而m=∞则实现根据这些度量最有利的选择的贪婪策略。

5 Computational Experiments

5.1 Dataset

尽管现实世界中的旅行数据是可用的,但是我们选择合成实例,因为有若干考虑因素。现实世界的数据缺乏关于未观测到的需求的信息,包含不一致或噪声,并且遗漏了运营商重新平衡操作,使得站点库存不可靠。为了解决这些问题，我们使用基于不同天气条件和时间特征的旅行数据实例，使RL模型能够学习一个重新平衡政策，以应对不同的需求场景。我们考虑两个地面真实数据集,GT1和GT2,每个都有60个站点网络和不同的站点分布。在GT1中，九个车站位于单个城市中心内，而GT2则有十二个车站分布在两个城市中心。城市中心的车站有40个码头，而非城市中心的车站有20个码头。使用这两个数据集对于算法验证很重要，因为它反映了现实中的城市通勤模式。对于每个数据集，我们生成了150天的详细行程信息（起始站、出发时间、目的地站和到达时间）。在每个数据集的前100天用于训练，而剩余的50天作为测试集。四个车辆，每辆车有40个自行车容量，可以重新平衡站点。

5.2 Benchmarks

我们评估我们的DPRL算法与各种MIP和RL模型。

• 静态再平衡（Static Rebalancing, SR）：该模型使用[11]中的MIP方法来优化开始时的初始库存。测试日模拟从这些优化后的初始库存开始的用户需求，当天无需进一步再平衡。这种静态解决方案还为其他模型确定了初始库存输入。
• 动态再平衡（Dynamic Rebalancing,DR）：该方法采用[11]中的多时段动态再平衡MIP模型，时间周期为30分钟（DR30）和60分钟（DR60）。它根据训练集的平均租赁和归还情况生成再平衡策略，指示每个时间段内每辆自行车应在哪个站点进行再平衡。所获得的再平衡策略也在测试集中进行了评估
• 带有启发式路由的RL库存（RL Inventory with Heuristic Routing,RIHR）：在这种方法中，MMDP模型专门用于在车辆到达站点时学习库存策略。离开时的路由决策由一个选择下一个站点的启发式算法管理，如第4.2节中m=∞的情况所详细说明。
• 基于启发式库存的RL路由（RL Routing with Heuristic Inventory,RRHI）：仅在车辆出发时训练MMDP模型以确定下一个要访问的站点。目标水平，即确保最佳服务的理想库存水平，作为启发式库存规则。到达一个站点后，车辆会努力重新平衡该站点的库存到这个目标水平。我们利用[9]中计算的目标水平，该水平是根据考虑天气和时间因素的需求预测得出的。
• 同时库存和路由决策的RL（RL with Simultaneous Inventory and Routing decisions,RSIR）：该模型从[10]中整合了车辆到达站点时的库存和路由决策。

上述所有RL模型在训练后均在测试集上进行评估。MIP模型使用IBM ILOG CPLEX v20.1.0.0在2.70 GHz IntelXeon Gold 6258R机器上解决，这些机器有8个核心，直到优化间隙降至0.01%或在24小时后终止。RL模型在单个GPU Tesla V100-PCIE-32GB上进行训练。有关超参数设置的更多详细信息，请参阅附录A.1。

5.3 Results

我们认为从早上7点到上午11点的4小时计划期涵盖了他们的高峰需求时段。这一时期也对应于RL模型中的一个场景。我们通过在测试集上比较我们提出的DPRL模型与各种基准模型来评估其在处理新和复杂需求场景时的实际效用和鲁棒性。

图4展示了我们的算法和基准测试在GT1和GT2上的平均周期性丢失需求及其标准差。我们检查了两个设置的RL模型，这些设置通过ϵ值来区分，表示选择随机动作的概率。当ϵ=0时，基于训练网络中最高的Q值确定动作的选择是确定性的。
为了评估RL模型的鲁棒性，我们将ϵ设为0.05以引入一定程度的动作选择随机性。这探索可以揭示在训练期间可能被忽略的更有效的策略，并通过偶尔偏离确定性策略来帮助防止过拟合。由于MIP模型没有ϵ，它们的表现仅显示为ϵ=0时的情况。

在这些实验中观察到，SR模型始终表现出最高的损失需求，GT1为112.82，而GT2为82.1，这突显了其无法适应全天动态变化。相比之下，动态再平衡策略，如DR30和DR60，在整个白天通过整合用户需求信息显著提高了性能。然而，与某些RL模型相比，它们仍然表现不佳。

在这些RL模型中，RSIR在集成库存和路线决策方面表现得与RIHR和RRHI相当。尽管如此，RSIR由于其同时决策方法的限制，在车辆库存操作期间未能充分考虑系统变化。我们的DPRL模型在最小化需求损失方面表现出更高的适应性和有效性，对于GT1实现了最低23.1的需求损失值，对于GT2实现了最低10.0的需求损失值。具体来说，与DR30相比，DPRL减少了GT1 48.4%和GT2 72.8%的需求损失，与RSIR相比，分别减少了GT1 34.2%和GT2 66.1%的需求损失。通过解耦库存和路由决策，DPRL突出了更现实、更细粒度框架的有效性，用于DBRP。有关详细信息，附录A提供了不同m和α值的RIHR结果。在所有情况下，这些方法的表现都比DPRL差。

为了全面理解学习过程，图5展示了三个高性能RL模型的训练周期回报。每一步代表一个周期，对应于我们的规划时间范围。周期回报量化了每个周期内获得的累积奖励，更高的值表示更成功的重新平衡策略。

图5显示了所有RL模型中递归回报的总体上升趋势，表明随着训练的进行，累积奖励有所提高。值得注意的是，DPRL模型在递归回报方面表现出更一致且更陡峭的增长，优于其他两个模型。这表明DPRL在规划周期内发展出了一种更有效的重新平衡策略。关于TD损失和Q值的更多细节见附录A。

5.4 Ablation Analysis

在本节中，我们进行消融研究以检查不同训练初始化的影响。关于网络架构和启发式路由的额外消融研究分别详细列于附录A.3和附录A.4。
以下结果基于GT1数据集。我们在方程(3)和(4)中的参数m来初始化训练过程。表3展示了测试集的评估结果。注意m = ∞表示贪婪启发式路由规则，其中最满的车辆被分配到最空的车站，反之亦然。

当m=0时，启发式路由的初始化导致随机选择站点，得到最低损失需求为19.66，其中ϵ=0.00。这种均匀选择可能防止过度拟合到特定站点特征，从而产生一个高效的重新平衡解决方案。然而，其缺乏鲁棒性是显而易见的，因为当引入随机性（ϵ=0.05）时，损失需求显著增加。对于m=1，启发式路由平衡了距离和库存水平，导致分别在ϵ=0.00和ϵ=0.05的情况下，损失需求分别为23.08和25.89。这种平衡的方法提供了灵活性和鲁棒性，使其在重新平衡时相对高效。对于m=2，对距离和库存水平的严格敏感性导致了更高的33.86损失需求，这表明过度优先考虑这些因素可能会导致过拟合并降低动态环境中的有效性。最后，当m=∞时，严格的路由规则解决了极端不平衡问题，但缺乏更微妙的重新平衡场景所需的细致方法。

6 Conclusions

本研究介绍了一种新颖的方法，用于解决BSS中的实时再平衡问题，该方法使用了双重政策RL框架。通过将库存和路由决策解耦，我们的方法提供了比以前同时进行这些决策而没有详细考虑系统变化的先前方法更高的真实性和效率。我们把库存和路由子问题建模为一个在连续时间框架内的MMDP。为了便于学习，我们在先到先服务规则下开发了一个全面的模拟器，能够计算即时奖励和状态更新，并且适用于各种需求场景。

我们对不同的数据集进行了广泛实验和消融研究，证明了我们的双策略框架相比几个基准具有更好的性能。总体而言，所提出的框架显著减少了需求损失，为BSS运营商提供了宝贵的见解，并为现实世界中的动态规划问题提供了更智能、更灵活的解决方案。

与我们的工作相关的研究视角是众多的。第一个研究方向涉及将我们的模型扩展到更大的BSS网络，并考虑电子单车共享系统的特殊性（由于充电决定）。额外的模型扩展还可以包括实时交通信息和更复杂的用户行为模型。最后，本工作中获得的方法学见解在适用性方面非常广泛，可以进一步应用于其他可能的移动需求[见，例如6]中的平衡问题。