基于广度优先搜索算法（BFS）的立体停车场调度方法研究

潘继姮　刘剑

摘要：随着国民经济的快速发展，人民生活水平的日益提高，城市居民私有车辆的数量也在不断增加，从而引发了“停车难”等一系列社会问题，给城市居民生活带来了不便，一定程度上影响着城市的建设与发展。本文对立体停车场的设计进行了研究与探讨，表明采用广度优先搜索算法在立体停车场的控制调度系统中有效且可行。

关键词：立体停车场 广度优先搜索算法

1 立体停车场的研究意义

随着国民经济的快速发展，我国城市交通的矛盾越来越突出。车辆的不断增多导致了城市交通阻塞现象日益严重，车辆的停放和管理自然也成为了城市生活水平发展的一个关键问题。立体停车系统可以有效地解决这些问题，一定程度缓解目前的压力。

2 立体停车场的形式和特点

目前为止，立体停车场主要有升降横移式、巷道堆垛式、垂直循环式、箱型水平循环式、及圆形水平循环式等几种形式，其中升降横移式立体停车场的建设周期较短，比较节省占地，投资价格较低，可以自动控制，存取车较迅速，并且构造简单，安全可靠，可适用于各种商业及住宅小区。

3 立体停车场的控制调度方法

一个有效可靠的调度算法是立体停车场设计的关键。利用穷搜索法来解决此类问题实际有广度优先搜索算法（BFS）和深度优先搜索算法（DFS） 这两种基本方法。

3.1 广度优先搜索算法（BFS）

在求解问题的过程中，广度优先搜索算法具体是，按照规则，采用首先从初始状态开始，将第一次所有可能的操作都进行完之后，扩展出第一级所有新的状态，再依次分别对所有第一级的新状态进行所有可能操作，扩展出第二级所有新状态，然后以相同步骤继续进行，直到出现目标状态为止。

如图1所示，从S初始状态开始，先将第一次的所有操作都进行完，扩展出1、2结点，再进行下一步操作，扩展出第二级的所有状态，即结点3，4，5，6，7，如果没有达到目标结点，再继续往下进行，直到达到目标结点。

3.2深度优先搜索算法（DFS）

在求解问题的过程中，深度优先搜索算法具体是，按照规则，采用首先从初始状态开始，就近操作，并优先扩展最近产生的新状态，直到找到目标为止，即达到深度限度。如果没有找到目标或者无法再扩展时，就回到另一状态继续扩展。

如图2所示，从S初始状态开始，首先沿着结点1，2，3 一步步往下扩展，当无法产生下一级结点时，再回到上一级结点2，沿着结点4，5继续扩展。如果没有达到目标结点，就再回到结点1，沿着6继续扩展，直到达到目标结点。

图1 广度优先搜索算法 图2 深度优先搜索算法

在广度优先搜索算法中，当新的结点状态与已经产生的某个结点状态相同时，广度优先搜索算法会找出一条长度最短的路径。在深度优先搜索算法中，如果深度限度过大，就会既浪费时间也浪费空间，算法中解的路径长度需要小于或等于深度限度。由此可见，基于广度优先算法的立体停车场系统，可以提供一套切实可行的智能化解决方案。

4 立体停车场的调度算法应用

4.1 多维立体停车场调度算法

图3为一个3×3×3的多维立体停车场模型。

图3 3×3×3 立体车库模型

在处理多维立体停车场调度问题中，采用的是分层处理，即将立体停车场纵向分解为若干个单维的停车场单元。如图3所示的这样一个3×3×3 的立体停车场，我们就可以将它分解为三个 3×3 的立体停车场单元。

如图4所示，假设目标车位处于第三个纵切面的左上角，利用广度优先搜索算法，我们应该总共经历四个步骤使目标车位移动到右下角的进出口处。

图4 第三个纵切面车位移动示意图

接下来，同样利用广度优先搜索算法将第二个纵切面的空车位移动到右下角，如图5所示。利用同样方法再将第一层纵切面的空车位移动到右下角。最后，将目标车位从第三个纵切面移动到第一个纵切面的进出口处，如图6所示。

图5 第二个纵切面车位移动示意图 图6多维立体停车场车位移动

其中，在利用广度优先搜索算法移动车位的过程中，当出现空车位距离进出口比目标车位距离进出口远的情况时，如图7所示，假设B为所要移动到出口的车位，空车位在B的左边，扩展此结点时，空车位不必再向左移动。同理，无论空车位在目标车位的任何方向，如果空车位距离进出口比目标车位距离进出口远，则结点不再向此方向扩展。

另外，当车位开始移動时，空车位总是先移动到目标车位，这个过程中的各个结点没有必要扩展出所有可能的状态。如图8所示，假设E作为目标车位，我们可以规定空车位的移动次序总是先向左，再向上，直到到达目标车位。

图7 空车位示意图 图8 空车位移动示意图

5 结束语

本文利用广度优先搜索算法解决了现实中急需解决的立体停车场的控制调度问题，具有重要的实际意义。