第6章：随机最短路径问题 - 动态
本章概览
第5章提出了一个最短路径问题，该问题假设我们要么对链路上动态变化的旅行时间一无所知，要么只能观察到与我们的旅行者当前所在交叉口相连的链路上的时间（但对未来的情况一无所知）。
现在设想我们是像Google地图这样的服务，可以获取整个网络的实时信息。此外，这些信息正在实时更新，从而使得Google能够更新推荐给旅行者去往目的地的路径。这一信息引入了模型中的一个重大变化，完全排除了使用我们在第5章中介绍的方法的可能性。
我们用于这个问题的方法适用于任何这样的问题：我们通过使用所谓的对不确定值的”最佳估计”来规划未来，从而求解该问题。这为我们首次使用第四类策略——我们称之为直接前瞻近似——提供了一个应用场景。我们利用这一场景来展示一种实用而强大的方法，用于在动态环境（即在不确定性下）做出决策，我们从一个确定性前瞻模型出发，然后引入参数使其能够在不确定性下随时间推移更好地发挥作用。
叙述
我们将再次探讨随机最短路径问题，但这一次我们将像Google地图（或任何商用导航系统）中那样来处理它。我们都认识到，交通网络往往具有可预测的拥堵模式，同时也存在自然发生的随机变化。例如，一起事故可能造成积压，我们或许可以估计由于该事故旅行延误将如何演变。
与静态最短路径问题的不同之处在于，我们对未来成本的估计是随时间演变的。我们将回到成本是随机的这个问题，但当我们到达节点$i$时，我们看不到节点$i$之外成本的实际实现值。然而，我们将假设我们被提供了整个网络上成本的更新估计。这些估计可以被看作是一种预测；我们将假设，当我们穿越一条弧时所产生的实际成本，平均而言将等于该预测值（即预测是无偏的），但这些预测会随着我们获得关于网络状态的更新而随时间演变。
界定问题
我们对三个界定问题的回答如下：
- 指标： 我们希望最小化预期旅行时间，其中我们也可以包含对晚于目标到达时间到达的惩罚。
- 决策： 对于位于节点$i$的旅行者，我们希望告诉他接下来应穿越到哪个节点$j$。
- 不确定性： 每当旅行者穿越一条通往下游节点的链路时，估计的旅行时间会随机变化。穿越一条链路时的实际时间将与估计值不同。
基本模型
假设当我们必须在时间$t$做出决策时，我们拥有基于当前拥堵水平（通过跟踪我们的智能手机在交通中移动的速度）而得到的旅行成本更新估计。我们将使用$\cbar_{tk\ell}$来表示这些时间，即在时间$t$已知信息的基础上，对时间$t$穿越链路$(k,\ell)$的估计成本。
目前，我们不打算对在给定时间$t$已知信息的情况下，到达某个时间点$t’ > t$的成本进行建模。因此，我们可能在下午3点估计我们将在下午5点到达某条链路，但我们将使用我们在下午3点做出的估计值（正如Google现在所做的那样）。
状态变量
假设位于节点$N_t = i$、处于时间$t$的旅行者被给定了一组预测值$\cbar_{t} = (\cbar_{ttk\ell})_{k, \ell \in \Ncal}$，即在时间$t$已知信息的基础上，对时间$t$穿越链路$(k, \ell)$的成本估计向量。旅行者在时间$t$的状态$S_t$则为
\[S_t = (N_t, \cbar_t).\]请注意，这个状态变量非常庞大；它由网络中每一条链路的链路成本估计向量组成。
决策变量
决策变量与静态随机最短路径问题相同
\[x_{tij} = \begin{cases} 1 & \text{if we traverse link } i \text{ to } j \text{ when we are at } i \text{ at time } t, \\ 0 & \text{otherwise.} \end{cases}\]只要$i$不是目的地，该决策必须遵守我们在状态$N_t = i$中要做某事这一约束条件。我们将此约束写为
\[\begin{align} \sum_j x_{t,i,j} = 1 \quad \text{for } N_t = i \text{ other than the destination.} \label{dynamicshorestpathconstraint} \end{align}\]如果我们已经到达目的地，那么我们什么都不做，而是对等于目的地的$i$写$x_{tij} = 0$，对任何其他节点$j$写。
如上所述，我们令$X^\pi(S_t)$为我们用于确定向量$x_t$的策略，我们假设该向量必须满足约束$\eqref{dynamicshorestpathconstraint}$。
外源信息
对于这个问题，有两种类型的外源信息。第一种类型是观测到的成本：$\chat_{t+1,ij}$，即旅行者在时间$t$做出穿越该链路的决策之后，穿越链路$(i,j)$的实际成本。请注意，我们只有当旅行者确实穿越链路$(i,j)$时才能观测到$\chat_{t+1,ij}$（对于我们没有穿越的链路，我们可以直接插入0，因为我们不会使用这些值）。
第二种新信息类型是对链路成本估计$\cbar_t$的更新。我们将把外源信息建模为估计值的变化：
\[\delta \cbar_{t+1,k\ell} = \begin{cases} \cbar_{t+1,k\ell} - \cbar_{tk\ell} & \text{if } x_{tk\ell}=1, \\ 0 & \text{otherwise.} \end{cases}\] \[\delta \cbar_{t+1} = (\delta \cbar_{t+1,k\ell})_{(k,\ell)\in\Ncal}.\]那么，我们的外源信息变量由下式给出
\[W_{t+1} = (\chat_{t+1}, \delta \cbar_{t+1}).\]转移函数
我们假设$\chat_{t+1}$作为外源信息到达（我们本可以让外源信息为成本的变化，但这样更自然）。
预测值的转移函数按以下方式演变
\[\begin{align} \cbar_{t+1,k\ell} = \cbar_{tk\ell} + \delta \cbar_{t+1,k\ell}. \label{eq:shortestpathdynamictransition1} \end{align}\]最后，我们使用下式更新物理状态$N_t$
\[\begin{align} N_{t+1} = \{j\vert x_{t,N_t,j} = 1\}. \label{eq:shortestpathdynamictransition2} \end{align}\]换句话说，如果我们位于节点$i=N_t$并做出决策$x_{tij}= 1$（这要求我们必须位于节点$i$，否则$x_{tij} = 0$），那么$N_{t+1} = j$。
对$\chat_{t+1}$的更新，即对预测值$\cbar_{t+1}$的方程$\eqref{eq:shortestpathdynamictransition1}$，以及对我们物理状态$R_t$的方程$\eqref{eq:shortestpathdynamictransition2}$，共同构成了我们的转移函数
\[S_{t+1} = S^M(S_t, X^\pi(S_t), W_{t+1}).\]目标函数
现在我们将目标函数写为
\[\begin{align} \min_\pi F^\pi(S_0) = \E \left\{\sum_{t=0}^T \sum_{(i,j)\in\Ncal} \chat_{t+1,i,j}X^\pi(S_t)\vert S_0 \right\}. \label{eq:shortestpathdynamicobjective} \end{align}\]请注意，我们的策略$X^\pi(S_t)$根据我们在时间$t$已知的信息（由$S_t$所捕获）来选择我们接下来要移动到的链路。
不确定性建模
在实践中，成本（及预测值）的动态更新来自真实系统，这意味着它们是数据驱动的。在这种情况下，我们不使用链路成本的数学模型。另一种方法是拥有一个关于随机信息$W^{n+1}$的数学模型。
如果我们希望运行模拟，那么我们就面临对由$\chat_t$所捕获的成本实现值以及预测值序列进行建模的挑战。必须对这个模型给予相当的关注。首先，对$\ctilde_t$估计值的变化——我们用$\delta \ctilde_{t+1}$表示——必须从均值为$0$的分布中抽取。此外，实现值$\chat_{t+1}$必须从均值为$\ctilde_t$的分布中抽取。
我们并不想淡化创建一个现实的随机模型所面临的挑战。链路成本的变化源自不同的因素，包括自然的交通变化、天气、事故，以及驾驶员对网络其他地方拥堵做出反应而导致的流量变化。链路成本的随机变化是非平稳的，并且无论是在时间上还是在链路之间都不是独立的。然而，除了承认这些困难挑战之外，一个更现实的模型超出了我们讨论的范围。
设计策略
一个快速的提示表明我们将不会使用贝尔曼方程（即使是近似地使用），那就是状态变量的规模，它现在包括了网络中每一条链路的旅行成本预测。
相反，我们将基于一种特殊的模型来制定策略，我们称之为前瞻模型。例如，在时间$t$，我们可以创建一个由状态$S_t$、决策$x_t$和外源信息$W_{t+1}$组成的模型，但在我们的基础问题中，状态变量$S_t = (N_t, \cbar_t)$相当复杂。
相反，我们将创建一个更简单的模型，首先创建一组新变量，这些变量通常是基础模型中变量的近似值。我们通过在前瞻模型中的变量上加波浪号，来将这组新变量与基础模型的变量区分开来，并用两个时间索引来对它们进行索引：时间$t$，即做出决策的时刻，以及第二个索引$t’$，即前瞻模型内部的时间。
前瞻模型中状态、决策和外源信息的序列可以写成
\[(\Stilde_{tt}, \xtilde_{tt}, \Wtilde_{t,t+1}, \ldots, \Stilde_{tt'}, \xtilde_{tt'}, \Wtilde_{t,t'+1}, \ldots ).\]我们的成本向量$\cbar_t$则将被替换为向量$\ctilde_{tt’}$。我们现在面临设计一个前瞻策略的挑战，我们可以称之为$\Xtilde_{tt’}(\Stilde_{tt’})$，它在前瞻模型内部确定$\xtilde_{tt’}$。下面我们提出两种策略，二者都可以用简单的最短路径算法求解。
确定性前瞻策略
我们通过假设前瞻模型中的成本$\ctilde_{tt’}$是固定的，并等于当前的估计值来近似该问题，这意味着我们令
\[\ctilde_{tt'k\ell} = \cbar_{tk\ell}.\]这意味着我们不再拥有外源信息变量$\Wtilde_{tt’}$，这为我们提供了一个确定性前瞻模型。
这使我们能够确定性地求解前瞻模型，将成本估计值$\ctilde_{tt’,k\ell}$当作正确的成本而非随机变量来处理。在这种情况下，我们的状态变量再次简单地就是（前瞻模型内）旅行者所在的节点。
我们可以用标准的最短路径算法来求解这个问题，正如我们在第5章中所看到的，这是一个确定性动态规划问题，我们可以用贝尔曼方程来求解，具体做法是首先求出在前瞻模型中时间$t’$位于节点$i$的”值”。我们可以通过将前瞻模型末端时间$t$处的值设为零来计算这些值
\[\Vtilde_{t,t+H}(i) = 0,\ \text{for all } i.\]然后，我们在（前瞻模型中的）时间上向后回溯，对$t’ = t+H-1, t+H-2, \ldots, t$，并对每个节点$i$计算：
\[\begin{align} \Vtilde_{tt'}(i) = \min_{j\in\Ncal^+_i} (\ctilde_{tt',ij} + \Vtilde_{t,t'+1}(j)). \label{eq:shortestpathdetlookahead} \end{align}\]于是我们的前瞻策略由下式给出
\[\begin{align} \Xtilde^\pi_{tt'}(\Stilde_{tt'}=i) = \argmin_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij} + \Vtilde_{t,t'+1}(\Stilde_{t,t'+1}=j)\big). \label{eq:shortestpathbellmandetlookahead} \end{align}\]最后，如果我们位于节点$i$，我们将在基础模型中实施的策略将是
\[X^\pi_t(S_t = i) = \Xtilde^\pi_{tt}(S_t = i).\]这就是我们在使用导航系统时所遵循的策略。基于确定性前瞻模型做出决策，是在不确定性下求解序贯决策问题时使用最广泛的方法之一。
图6.1展示了一个滚动前瞻过程。在时间$t$、$t+1$、$t+2$、$\ldots$，我们使用我们所知的成本估计创建并求解一个前瞻模型。然后我们求解最短路径问题，其结果体现在针对所有节点$j$的决策$\xtilde_{tt’}(j)$中，但随后我们只对我们在时间$t$所处的节点$i$实施决策$\xtilde_{tt}(i)$。
当我们在前瞻模型中将一个动态变化的变量保持不变时，我们将这个变量称为前瞻模型中的潜在变量。”潜在变量”这个术语从技术上讲意味着隐藏变量；在此语境下，它指的是一个（在前瞻模型内）不随时间变化的变量，在这种情况下，我们将其从状态变量中剔除，这意味着它是隐藏的（同样，是在前瞻模型中）。
这是可以在前瞻模型中进行的多种不同类型近似之一。我们所做的最明显的近似是使用一个确定性的未来，这意味着链路成本的估计值在前瞻模型内被保持不变，即使它们在基础模型中是在变化的。
因此，前瞻模型是其自身的模型，具有自身的特性，这也是我们使用带波浪号变量的原因——正是通过这种方式，我们将使用诸如$S_t$和$x_t$这样变量的基础模型，与使用诸如$\Stilde_{tt’}$和$\xtilde_{tt’}$这样变量的前瞻模型区分开来。
接下来，我们将提出一个小的调整，使这种方法在不确定性下能更好地发挥作用。
参数化确定性前瞻策略
处理我们动态最短路径问题中不确定性的一个简单策略是，用成本的$\theta$分位数来替代我们对链路$(k,\ell)$在时间$t$的通行成本的点估计$\ctilde_{tt’k\ell}=\cbar_{tk\ell}$，这意味着我们可以将成本写作$\ctilde_{tt’,k\ell}(\theta) = \cbar_{tij}(\theta)$。举例来说，这种逻辑可以避免经过某个有时会变得非常拥堵的区域，因为在那里成本可能相当高。
这一策略仍然产生一个确定性最短路径问题，其求解难度与我们使用点估计$\cbar_t$时一样简单。我们只需通过使用$\theta$分位数的链路成本来修改上面的方程$\eqref{eq:shortestpathdetlookahead}$–$\eqref{eq:shortestpathbellmandetlookahead}$。然后我们将值函数记为$\Vtilde_{tt’}(i\vert \theta)$，以表明其对参数$\theta$的依赖关系，该参数通过下式计算：
\[\begin{align} \Vtilde_{tt'}(i\vert \theta) = \min_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij}(\theta) + \Vtilde_{t,t'+1}(j\vert \theta)\big). \label{eq:shortestpaththetalookahead} \end{align}\]于是我们的前瞻策略由下式给出：
\[\begin{align} \Xtilde^\pi_{tt'}(\Stilde_{tt'}=i\vert \theta) = \argmin_{j\in\Ncal^+_i} \big(\ctilde_{tt',ij}(\theta) + \Vtilde_{tt'}(\Stilde_{t,t'+1}=j)\big). \label{eq:shortestpathbellmanthetalookahead} \end{align}\]然后我们使用下式来表示基础模型的参数化策略（该策略给出实际实施的决策）：
\[X^\pi_t(S_t = i\vert \theta) = \Xtilde_{tt}(S_t = i\vert \theta).\]这与我们原来的确定性前瞻模型是等价的，只有一个主要例外：我们需要通过优化下式来调节$\theta$：
\[\begin{align} \min_\theta F^\pi(\theta\vert S_0) = \E \left\{\sum_{t=0}^T C(S_t,X^\pi(S_t\vert \theta))\vert S_0\right\}. \label{eq:tuneshortestpathcfa} \end{align}\]其中$S_{t+1} = S^M(S_t,X^\pi(S_t\vert \theta), W_{t+1})$（参见方程$\eqref{eq:shortestpathdynamictransition1}$–$\eqref{eq:shortestpathdynamictransition2}$），使用某种方法来生成$W_1, \ldots, W_T$的随机实现。
$\eqref{eq:tuneshortestpathcfa}$中的优化问题本身是一个具有挑战性的问题，但由于$\theta$是一个介于0和1之间的标量，这使问题得到了简化。用于优化$\eqref{eq:tuneshortestpathcfa}$中目标函数的实用算法通常涉及运行仿真以获得该函数的带噪声观测值。
一个显而易见的问题是，使用不同于$\theta = 0.5$的分位数是否会改善结果。我们的经验是，当存在迟到惩罚时（例如，我们希望在上午9点赴约），这确实会有所改善。
我们学到了什么？
- 我们展示了如何建模一个动态网络问题，其中成本的估计值随时间演变。这一次，系统的状态是出行者的位置以及网络中每条链路的成本估计值。
- 我们引入了近似前瞻模型的概念，本例中为确定性前瞻，它可以作为最短路径问题求解。尽管这是一个最优解，但求解一个近似前瞻模型，即使是最优地求解，也并非最优策略。
- 我们描述了潜变量，这些是在前瞻模型中被保持不变的动态变量（链路上的成本），这也是它们不再出现在状态变量中的原因。
- 我们展示了如何将我们的确定性前瞻改造为参数化确定性前瞻。我们可能不使用每条链路的期望成本，而是使用$\theta$分位数，从而考虑某条链路可能有多糟糕。参数$\theta$必须经过调节，这使得该策略成为一种混合体：它既是参数化的确定性前瞻近似（DLA策略），因而也具有CFA策略的形式，从而形成了一种DLA/CFA混合策略。
习题
复习题
- 为什么我们不能使用[第5章](/sdam/zh/chapter-5/)中的近似动态规划方法来求解我们的动态问题？
- 在前瞻模型中，我们是如何对外源过程$W_t$建模的？
- 用文字描述我们所说的前瞻策略是什么意思。
问题求解题
- 我们将求解确定性前瞻模型作为我们的策略。这可以最优地求解该确定性问题。为什么这不是一个最优策略？
- 我们使用贝尔曼方程将确定性前瞻模型（可能带有修改后的成本$\cbar_{ij}(\theta)$）作为确定性动态规划来求解。为什么我们不能说我们是在用动态规划求解我们的基础模型？
- 设想我们希望尽可能晚地从起点节点出发，但如果到达终点节点迟到会有很高的惩罚。如果我们对成本$\cbar_{tij}(\theta)$的$\theta$分位数进行优化，这一逻辑将如何帮助我们避免迟到？
- 根据习题6得到的启示，你认为使用$\theta$分位数成本对于一个仅仅试图最小化总旅行时间、而不考虑迟到可能性的问题会有什么帮助？
- 请为以下情形提供完整的模型（状态变量、决策变量……）：节点$i$出发链路的成本$\chat_{tij}$在出行者到达节点$i$、并且在她做出选择哪条链路通行的决策之前被揭示。请记住你要最小化沿路径的累计成本。你不需要设计一个具体的策略；请遵循我们的标准做法，引入一个策略$X^\pi(S_t)$而不具体规定该策略。
- 设想我们要求解最短路径问题，我们希望尽可能晚地从起点出发，但必须在上午9点之前到达终点。我们对每迟到一分钟到达终点设定一个惩罚$\eta$。请描述用于求解该问题的基础模型和参数化前瞻策略。基础模型的状态变量是什么？前瞻模型的状态变量又是什么？
编程题
这些习题使用tinyurl.com/sdagithub上的Python模块StochasticShortestPath_Dynamic。
- 我们将使用讲义中所采用的确定性前瞻模型，但不使用每条链路的期望成本，而是使用我们记为$\theta^{cost}$的分位数。例如，如果$\theta^{cost} = 0.8$，那么我们将使用成本的第80百分位数（可以将其理解为对成本可能有多大的一种估计）。设$\cbar_{tij}(\theta^{cost})$为在时间$t$已知信息条件下链路$(i,j)$的$\theta^{cost}$分位数成本。
- 写出前瞻模型，这将是一个使用成本$\cbar_{tij}(\theta^{cost})$的确定性最短路径问题（正如书中所做的那样）。利用该模型正式定义一个前瞻策略$X^{DLA}(S_{tj}\vert \theta^{cost})$。
- 该动态问题的状态变量是什么？请记住，状态变量包括用于做出决策（包括计算成本和约束条件）所需的一切动态变化信息，以及计算从$t$到$t + 1$的转移所需的信息。
- 写出用于评估我们前瞻策略的目标函数。
- 现在我们有了一个由$\theta^{cost}$参数化的策略$X^{DLA}(S_{tj}\vert \theta^{cost})$。使用python模块StochasticShortestPath_Dynamic，对$\theta^{cost} = (0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0)$仿真该策略。将每个版本的策略仿真100次，并取实际总成本（而非$\theta^{cost}$分位数）的平均值。同时考虑"迟到"的风险，即实际总成本大于给定阈值的情况。绘制结果并进行比较。