\renewcommand{\fig}[3]{ \begin{figure}[!htb] \centering \includegraphics[width=#2\textwidth]{#1.png} \caption{#3} \label{#1-zh} \end{figure} } \zihao{-4}\songti \noindent 作者：Parag J. Siddique, Kevin R. Gue, John S. Usher\\ \noindent 出处：Transportation Research Part C: Emerging Technologies, Volume 127, June 2021, 103112 \vspace{2ex} \begin{center} \zihao{4}\textbf{基于谜题的停车} \end{center} \noindent\textbf{摘要：} 在普通停车场中，大部分空间并非用于停车，而是用于车辆在停车位之间行驶的车道。车道不能被阻塞，一个简单的原因是：被阻塞的车可能需要在挡住它的车之前离开。自动停车和自动驾驶车辆的智能通信能力为克服这一限制提供了机会，因此可以实现更高的汽车存储容量。我们展示了如何通过集中控制器将干扰的车辆移开，从而最大化停车场中的汽车数量。我们提供了单入口小型停车场的最优结果，并为更大停车场提供了启发式方法。停车容量的提升可达80\%。 \section{基于谜题的停车场} 自主乘用车辆的前景为改善城市交通提供了许多有趣的机会。在停车方面，远程控制汽车的潜力允许汽车停放得更近，因为不需要打开车门让乘客下车。停车密度的提升潜力估计为20\%。另一个想法是，自动驾驶车辆不需要停在繁忙的城市区域。相反，可以在廉价的郊区创建远程停车区域。另一个被广泛接受的观点是，自动驾驶车辆将消除私人车辆所有权。自动出租车将带来共享出行，从而大幅减少停车需求。 在这一背景下，博世与梅赛德斯和福特合作，设计了一座为自动驾驶车辆设计的自动泊车场。到达停车场时，乘客在一个送车点离开车辆。停车场配备了智能传感系统，引导车辆找到停车位。每当乘客需要车时，可以通过智能手机应用程序检索车辆，车辆将到达取车点。值得注意的是，不需要人工控制汽车，也无需建设额外的市政基础设施。 在这样的自动化停车场中，通过消除行车道，可以实现更高的停车密度。在普通停车场中，行车道不能被封锁的一个简单原因是：被封锁的车可能需要在挡住它的车之前离开。然而，自动泊车场为克服这个问题，实现更高停车密度提供了机会。因此，我们已经拥有实现更高密度所需的技术，一切需要高效的设施设计和规划。 \fig{f1}{0.8}{其他作者提出的高密度停车设计。 (a) Ferreira等人 (2014) 提出了一种通过在平行车道上相互阻挡的设计来停放汽车。他们在设施的入口和出口都分配了缓冲区域，以便车辆可以进行必要的移动进行重新定位。 (b) Timpner等人在被阻挡的车道之间放置了垂直过道，以减少干扰车辆的数量。阻挡的车辆重新定位到过道上，为即将离开的车辆清出道路。 (c) Banzhaf等人通过添加一个车辆阻挡的过道来修改现有的停车场。 (d) 在Nourinejad等人的设计中，过道的宽度随着车道的深度而变化，以帮助容纳重新定位的车辆。} 一些作者设想了一些停车方案，以提高停放汽车的密度，或等效地提高停车场的容量。Ferreira等人首次提出了自主车辆的高密度停车方案。在他们的设计中，汽车通过在平行车道上相互阻挡来停放，类似于材料处理系统中使用的深车道存储系统（图\ref{f1-zh}a）。他们假设有一个自主停车控制器，负责控制停车场内的车辆移动。这一组研究人员已将这项工作扩展到考虑各种操作参数，如每辆车的停车空间、操纵次数、行驶距离和检索时间。他们的设计将停车容量提高了50\%。 为了减少干扰车辆的数量，Timpner等人修改了Ferreira等人的设计，减小了车道深度，并允许车辆从车道的任一端离开。作者估计密度提高了33\%。Banzhaf等人建议通过在现有过道内允许垂直的阻挡车道来修改现有布局。他们报告密度增加了25\%。Nourinejad等人描述了一个类似的系统，其中过道的宽度随着车道的深度变化，以帮助容纳重新定位的车辆。作者制定了一个混合整数非线性规划来最小化预期的车辆重新定位次数。然而，所有这些研究人员都计划针对更适合郊区地区的大型停车场。 从文献中我们了解到，自主车辆不会在停车场闲置。在放下乘客后，它将用于运送另一名乘客。然而，由于供需之间存在差距，当没有行程时会有一些空闲时间，因此车辆必须停在某个地方。如果这些车辆去郊区停车，它们将无法响应客户的呼叫。因此，自主车辆不会选择去城外停车，而是会在城市中心周围巡游以打发时间，从而导致城市拥堵。因此，我们无法完全消除城市停车。相反，我们可以寻找使停车更容易访问和更便宜的方法。为此，我们可以为城市区域提供小型而密集的停车场。这些停车场可以与零售业中的微型履行中心相类比。微型履行中心是靠近客户的小型仓库，专为按需电子商务履行而设计。每当自主车辆处于空闲状态时，它可以停在这些小型停车场。由于这些停车场将位于城市区域，因此每当车辆接收到行程请求时，它可以迅速服务请求。作为增值服务：在这些停车场中还可以引入车辆充电、清洁或类似的服务。 在本文中，我们研究了自主车辆停车场的高密度布局设计。我们的工作在两个重要方面与现有文献有所不同： \begin{enumerate} \item 我们为小型停车场开发最优设计，这是人们可能在城市环境中找到的。 \item 所有现有的研究都是基于一个布局，然后研究在该布局下的最优参数和性能。我们提出并回答了更基本的问题，即在不假设任何特定布局或结构的情况下，停车场可以停放多少辆车。正如我们将展示的，这种放宽导致了具有最大密度的设计，而不采用传统的“排和过道”停车结构。 \end{enumerate} \fig{f2}{0.5}{Rush Hour难题。游戏的目标是通过移动其他车辆让红车直接移动到对面的出口。} \fig{f3}{0.9}{(a) 一个$4 \times 4$停车场的示例，其中有两辆车，一辆水平停放在单元格(43, 44)，另一辆垂直停放在单元格(23, 34)，而单元格(11, 21)是输入/输出点。(b) 停车场内的三个有效移动。每个移动根据所行单元格的数量分配一个权重。} 我们处理的问题类似于Rush Hour难题（图\ref{f2-zh}），这在理论计算机科学领域有相当多的文献。Flake和Baum表明，具有$n \times n$网格的Rush Hour的广义版本是PSPACE-complete。Tromp和Cilibrasi以及Hearn和Demaine表明，仅包含汽车（没有$3 \times 1$的卡车）的Rush Hour也是PSPACE-complete。我们的问题在很多方面都与Rush Hour不同：游戏只允许车辆前后移动，而真实汽车可以转弯；而Rush Hour的目标是移走一个特定的车辆，而真实的停车场必须允许任何请求的车辆到达或离开。在物料处理文献中，也已经讨论了没有定义过道的高密度存储，其中使用可以沿着四个基本方向移动的输送模块存储和检索单元负载或容器。然而，在我们的停车场问题中，汽车独自移动，不需要任何输送模块的帮助，而且汽车可以朝不同的方向行驶。 \section{建模基于谜题的停车场} 我们将停车场视为一个矩形网格。汽车可以水平或垂直停放。我们假设汽车在网格中占据两个单元格，这意味着汽车的大小为$1 \times 2$。停车场的左下角有一个入口/出口点。我们称这个点为输入-输出（I/O）点。在图\ref{f3-zh}a中，两辆车停在一个$4 \times 4$停车场中，一辆停在单元格（43, 44），另一辆停在单元格（24, 34）。单元格（11, 21）表示I/O点。 \fig{f4}{1}{生成$4 \times 4$停车场状态空间图的过程。 (a) 单车图。大红色节点是根节点—这个图中的第一个节点。绿色节点是开放节点。开放节点总是允许新车进入停车场。根节点和一个开放节点都已注释。 (b) $4 \times 4$网格中的2车图。红色节点是初始节点，包括I/O单元格。一个初始节点已注释。 (c) 连接单车图和2车图。单车图中的开放节点连接到2车图中的初始节点，用蓝色突出显示。这些连接器称为桥接边缘。先前注释的节点的位置也显示出来。} 车辆在停车场内可以进行三种类型的移动：直行、直角和平行，这些操作可以前进或后退完成（图\ref{f3-zh}b）。假设车辆花费一个单位的时间在一个单元格上行驶，可以为每个移动分配一个权重以量化行驶时间。例如，车辆进行直行时移动一个单元格，因此将此移动分配一个权重为一。类似地，车辆进行直角和平行移动时移动四个单元格，因此将这些移动分配一个权重为四。我们假设停车场中有一个中央控制器代理，可以与车辆通信以执行所有移动。 读者可能会注意到这里我们并没有指定单元格的尺寸。单元格的大小是根据车辆的尺寸和运动学来决定的。相反，我们希望将单元格的设计留给专业人士。 \subsection{停车场能容纳多少辆车？} 我们使用状态空间图$G = (V, E)$对停车场中的车辆进行建模，其中$V$是表示停车场配置的顶点集合，$E$是表示配置之间可行转换的边缘集合。在本文中，顶点也可以用术语“节点”来表示。配置被定义为停车场的尺寸，停放的车辆数量以及它们的位置。术语“状态”也被用作配置的替代术语。我们想知道：停车场能停放多少辆车？为了开始解决这个问题，我们解决一个小例子，即$4 \times 4$停车场。 在一个$4 \times 4$停车场中，有十六个单元格，每辆车占用两个单元格。因此，我们最多可以放置八辆车。我们首先为$4 \times 4$网格生成状态空间图。在不考虑可操纵性的情况下，一个单独的车辆可以放置在24个不同的位置，每个位置都代表图中的一个潜在节点。然后，我们对所有潜在节点执行两两搜索，确定它们是否可以通过可行的操纵连接。我们将结果称为单车图（图\ref{f4-zh}a）。接下来，我们以每种可能的方式放置两辆车，以创建2车图。然后我们消除了具有重叠车辆的配置。例如，配置[(11, 21), (21, 22)]是不可行的，因为单元格21被两辆车使用，这在物理上是不可能的。我们还消除了占据整行或整列的配置，因为它们是不可行的（除了[(11, 21), (31, 41)]）。最后，我们使用它们各自的移动连接节点，构建了完整的2车图（图\ref{f4-zh}c）。同样，我们可以继续构建多达八辆车的图。 我们发现一个有趣的特征来连接这八个图。在一个空的停车场中，当第一辆车到达时，它最初停放在I/O单元格上。这是单车图的起始节点。这辆车可以移动到停车场内的不同位置。一旦车辆离开I/O单元格，停车场就可以接收第二辆车。当第二辆车到达时，它将自己停放在I/O单元格上。这是2车图的起始点。之后，车辆可以重新定位到停车场内的其他位置。类似地，当这两辆车都停在I/O单元格之外的任何位置时，停车场就可以接收第三辆车，我们可以一直进行此过程直到8辆车。因此，我们观察到每个$k$车图（$k = 1, 2, \dots, 8$）都从I/O单元格开始。因此，我们将包括占用的I/O单元格的停车场配置定义为初始节点。2车图的初始节点在图\ref{f4-zh}b中以红色突出显示。请注意，每个$k$车图都有多个初始节点，除了1车图。为了将此节点与其他初始节点区分开，我们将其定义为根节点（见图\ref{f4-zh}a中的大红色节点）。我们还观察到为了容纳新车辆进入停车场，我们必须确保没有车辆停在I/O单元格上。这样的配置——I/O单元格未被占用——始终允许新车辆进入停车场。我们将这些配置定义为开放节点（见图\ref{f4-zh}a中的绿色节点）。如果I/O单元格中的任何一个被占用，新车辆将无法进入停车场，这些节点称为非开放节点。在图\ref{f4-zh}a中有五个非开放节点（灰色节点）：(11, 21)、(11, 12)、(21, 22)、(21, 31)和(31, 41)。尽管(31, 41)不会立即阻塞停车场，但它只允许第二辆车停在(11, 21)上，之后不能再有车辆进入停车场。 \fig{f5}{0.7}{$4 \times 4$停车场的状态空间图。此图具有5,913个顶点和14,635条边。为了可视化目的，已注释其中一些顶点。} 当第二辆车到达I/O点时，它成为2车图的初始节点。因此，1车图的开放节点和2车图的初始节点通过一种进入车辆的操纵连接在一起。同样，2车图的开放节点和3车图的初始节点也是如此。我们称这些连接器为桥接边缘。1车和2车图的桥接边缘在图\ref{f4-zh}c中用蓝色突出显示。我们一般化，k车图的开放节点和$(k + 1)$-车图的初始节点使用桥接边缘连接。有了桥接边缘，我们就有了一个代表整个状态空间的图（请参见图\ref{f5-zh}，显示了$4 \times 4$停车场的状态空间）。 \fig{f6}{1}{基于谜题的检索测试。(a) 一个带有3辆车的$4 \times 4$停车场。(b) 我们在左侧的布局上执行基于谜题的检索测试，并发现通过重新定位停车场内的其他车辆，可以检索出所有三辆车。} 该状态空间图具有5,913个顶点和14,635条边。在此图中，有72个连接组件，即彼此可达的顶点集。来自一个连接组件的顶点与来自其他连接组件的顶点之间不进行通信。 然而，连接组件内的所有顶点都可以相互到达。为了更好地可视化图，我们已注释了一些节点。例如，图\ref{f5-zh}a是一个只有一辆车的停车场，图\ref{f5-zh}d是一个有四辆车的停车场，依此类推。为了确定有多少辆车可以驶入停车场，我们从寻找1车图的顶点开始。1车图始于第一辆车进入停车场的时刻，即根节点。如果我们探索根节点的连接组件，我们可以达到高达7车图的顶点。其余的连接组件不是从根节点开始的。因此，不可能通过驾驶车辆达到这些配置。例如，图\ref{f5-zh}i、图\ref{f5-zh}j、图\ref{f5-zh}k和图\ref{f5-zh}l中的顶点不能从根节点到达。因此，在$4 \times 4$停车场中最多可以停放7辆车。图\ref{f5-zh}g显示了一个有7辆车的停车场。总之，尽管$4 \times 4$停车场有容纳8辆车的能力，但我们只能驾驶7辆车进入。查找我们可以驾驶进入$m \times n$停车场的最大车辆数的步骤如下： \begin{itemize} \item 计算可以放置在停车场中的最大车辆数，$k_{max} = \lfloor\frac{m\times n}{2}\rfloor$。 \item 为具有$k$辆车的停车场生成状态空间图，其中$k = 1, 2, \dots, k_{max}$。 \item 对于每个图，识别初始节点和开放节点。 \item 将$k$车图的开放节点与$(k +1)$车图的初始节点连接起来。这将产生一个具有一组连接组件的图。 \item 找到带有根节点的连接组件。该组件由1车图到$k_{le}$车图的顶点组成，其中$k_{le}\le k_{max}$。 \item 返回$k_{le}$的值，即可以驾驶进入停车场的最大车辆数。 \end{itemize} 我们已经了解到，在$4 \times 4$停车场中，我们最多可以停放7辆车。我们只能以后进先出的顺序检索这7辆车。然而，我们并不总是希望为了让另一辆车离开而离开停车场。因此，我们想知道：在停车场中最多可以停放多少辆车，以便其中的任何一辆车在其他车辆保留的情况下离开？为了回答这个问题，我们选择一个有$k$辆车的停车场，其中$k = 1,2,\dots,7$，并测试是否有可能让任何一辆车离开。由于这个测试类似于Rush Hour拼图，我们称之为基于谜题的检索测试。例如，在图\ref{f6-zh}中，我们对一个有3辆车的停车场进行了基于谜题的检索测试。我们观察到在所有三种情况下，目标车辆达到了I/O点，而其余车辆不需要离开停车场，而是重新定位以使目标车辆离开。然后，我们对整个状态空间进行基于谜题的检索测试，以找到可以停放在$4 \times 4$停车场中的车辆数。然而，为了最小化我们的搜索工作量，我们从具有7辆车的停车场配置开始这个测试。我们发现这样停放7辆车是不可能的。然后我们探索具有6辆车的配置，测试再次失败。最后，对于具有5辆车的配置，我们发现所有车辆都可以离开。我们不需要对具有少于5辆车的配置继续进行这个测试，因为肯定会有一些配置通过这个测试。因此，我们发现在$4 \times 4$停车场中，最多可以停放5辆车，以便其中的任何一辆车在其他车辆保留的情况下离开。 在传统设置中，我们希望停放的方式是任何一辆车都可以离开，而不需要重新定位其他车辆。因此，我们想知道：在停车场中最多可以停放多少辆车，以便没有车辆被阻挡？为了回答这个问题，我们选择一个有$k$辆车的停车场，其中$k = 1,2,\dots,5$，并测试是否有可能让任何一辆车离开停车场，而不需要重新定位其他车辆。我们将这个测试称为未阻挡检索测试。然后，通过进行蛮力操作，我们发现在$4 \times 4$停车场中，最多可以停放4辆车，以便没有车辆相互阻挡。 \fig{f7}{1}{三种停车场设计。} \fig{f8}{1}{$A^*$搜索的单车启发式。为了从左侧停车场中检索深色车辆，右侧停车场被用作启发式，只在与深色车辆相同的位置放置一辆车。（有关本图例中颜色的解释，请参阅本文的网络版本。）} 观察状态空间图，我们发现存在三种停车场设计。第一种类型是停车场，最多停放车辆，车辆完全相互阻挡，车辆只能按照后进先出的顺序离开。我们将这种设计称为有限出口（图\ref{f7-zh}a）。这种停车场通常在不同的活动中发现，如音乐会或球赛。然后是第二种类型，车辆也相互阻挡，但任何车辆都可以通过移动其他车辆离开，就像Rush Hour拼图一样。我们将这种设计称为完全出口（图\ref{f7-zh}b）。最后，第三种是传统停车场（图\ref{f7-zh}c），在这种停车场中，没有车辆相互阻挡。我们发现了这些设计，因为我们在提出研究问题时没有预设任何特定的布局或结构。 \subsection{检索车辆需要多长时间？} 每辆车的检索时间是这些设计的性能指标之一。我们使用相同的状态空间图来计算检索时间。我们在状态空间图上应用$A^*$搜索算法来计算停车场中每辆车的最佳检索。 $A^*$是一种启发式搜索算法，通过扩展根据最小路径成本选择的最有前途的节点来探索图。路径成本评估为$f(s) = g(s) + h(s)$，其中$g(s)$是从初始状态到当前状态s的成本，$h(s)$是从当前状态s到目标状态的最便宜路径的估计成本。Hart等人还表明，如果启发函数$h(s)$是可接受的和一致的，则$A^*$算法保证产生最优结果。一个可接受的启发式$h(s)$是这样构建的，以便它生成到达目标状态的实际成本$h(s^*)$的下界：$h(s)\le h(s^*)$。一致的启发式是这样的，对于每个状态s和s的每个后继状态$s'$，从s到目标的估计成本$h(s)$不大于到$s'$的步骤成本$c(s, s')$加上从$s'$到目标的估计成本$h(s')$，可以表达为$h(s)\le c(s, s') + h(s')$。一致的启发式必然是可接受的，而反之则未必成立。我们已经简要介绍了$A^*$搜索的文献，更多信息请参阅Hart等人，Pearl，Russell和Norvig。 在我们的$A^*$算法实现中，输入包括：起始节点、目标车辆和启发式函数。起始节点是初始状态，由停车场的大小、停放的车辆数量和它们的位置表示。目标车辆是我们要检索的车辆。作为启发式函数，我们使用单车检索时间。例如，在图\ref{f8-zh}中，为了估算从左侧停车场检索深色车辆的成本，我们在右侧停车场的与目标车辆相同的位置放置一辆车，并计算检索时间。深色车辆的检索成本为27（图\ref{f8-zh}a），启发成本为5（图\ref{f8-zh}b）。由于这是我们问题的简化版本，它始终是一致的，因此我们可以得到最优结果。我们将这个启发式函数称为单车启发式。 我们的检索算法通过使用两个列表来探索状态空间：i) frontier（前沿）和ii) explored（已探索）。前沿列表是一个按照$f(s)$值对所有待访问节点进行排名的优先级队列，而已探索列表则存储所有已访问的节点。在开始时，前沿列表只包含初始节点，当选择访问目标节点时搜索停止。目标节点是目标车辆位于I/O点的配置。我们还创建了一个称为父-子的第三个列表，用于跟踪节点之间的关系——每当我们的搜索达到目标节点时，此列表用于构建从初始节点到目标节点的路径。应用$A^*$搜索，我们已经计算出从图\ref{f9-zh}中的有限出口、完全出口和传统停车场检索车辆所需的最佳移动次数。请注意，在有限出口停车场中，车辆的检索遵循后进先出的顺序，我们首先检索第7辆车，然后是第6辆车，依此类推（见图\ref{f7-zh}a），然后计算累积检索时间，如图\ref{f9-zh}a所示。 \fig{f9}{1}{车辆检索时间。} 在这里，我们计算检索时间，假设车辆在一个单元格内行驶需要一个时间单位。然而，读者可能对在真实停车场中的检索时间感兴趣。在这方面，我们在这里展示一个例子。一般而言，一个停车位的尺寸是$9' \times 18'$。由于我们考虑的是一个$1 \times 2$的停车位，我们可以将一个单元格的尺寸视为$9' \times 9'$。根据Schwesinger等人的说法，停车场中自动驾驶车辆的速度限制为$10 km/h (≈ 9ft/s)$。因此，一个单元格的行驶时间为1秒。在完全出口的停车场（图\ref{f9-zh}b）中，为了取回车辆02，所有车辆共行驶27个单元格。因此，车辆02的检索时间为27秒。