基于交互式蚁群算法的停车路径方法

张红艳，谢陈磊，袁翠艳

(安徽建筑大学 智能建筑与建筑节能安徽省重点实验室，安徽 合肥 230022)

0 引言

近年来，我国大型公共建筑的数量和规模开始不断扩大，机动车的数量逐渐增加，停车场数量和规模也随之扩大，部分大型地下停车场的道路状况复杂、障碍物多、运行效率和可靠性降低等问题日渐突出。运用合理的方法引导驾驶员寻找最佳车位可以减少驾驶员在地下停车场内的消耗时间，从而提高停车场的运行效率和可靠性[1]。

作为楼宇自动化系统的重要组成部分，地下停车场管理系统一般采用集中式分层管理架构控制各个管理子系统[2]。集中式分层管理架构在实际应用中会存在一系列问题，如信息冗余、现场配置困难和不能实现跨系统功能等。集中式分层管理架构带来的不同子系统底层信息不能共享、设备之间无法联动、信息冗余和处理突发事件能力弱等问题会给驾驶员寻泊造成麻烦，其中存在极大的不可靠性。为了克服现有的集中式分层系统架构所带来的问题，清华大学构建了新型建筑智能化平台。该平台按照空间划分的原则将建筑划分为互不重合的多个子空间单元，每个子空间单元对应一个智能计算节点(computing process node，以下简称CPN)，各个CPN只处理本空间的相关事务，然后相互进行必要的数据交互。该平台拥有自识别、自组织、自协调和易扩展等优点[3-5]。

国内外对于路径引导算法的研究主要包括Dijkstra算法、遗传算法、A*算法、D*算法和粒子群算法等。其中，Liu Jingyu[6]使用小波神经网络预测最佳停车位置，并使用自适应遗传算法进行路径引导，可以缩短驾驶员的驾驶时间，只是自适应遗传算法容易过早收敛。Thomas[7]和田硕[8]使用遗传算法进行最短路径规划并使用照明标记规划路径，有效地提高了停车场的运行效率，但遗传算法为集中式算法，并不适用于新型建筑智能化平台。Yuan Lingyun[9]使用Dijkstra算法在驾驶员入场处和目标车位之间进行最短路径规划，有效地节省了驾驶员的时间，但该算法的计算量较大、迭代次数较多、收敛时间长，因此并不适用于大型场所中的路径规划。Guruji A.K.[10]使用A*算法对机器人进行规避障碍物的路径规划，缩减了机器人的行进时间，但该算法容易被诱导进畸形搜索中，以至于搜索不到正确的结果。Ruby Singh[11]考虑停车效率和停车位搜索时间两个参数并使用萤火虫算法和前向-反馈神经网络算法进行最短路径规划，减少了驾驶员寻找停车位的时间，但是这两种算法的复杂度较高，在新型建筑智能化平台中难以应用。有的研究人员[12-15]还根据最短路径和最小能耗原则使用蚁群算法对进入停车场的车辆进行路径规划并以灯光来标记路径，节约了时间并且减少了车辆的能源消耗。

面向新型建筑智能化平台，本文设计并实现了交互式蚁群算法。首先，利用带权邻接矩阵的方法建立停车场模型，其主要作用是为交互式蚁群算法提供停车场内基础数据，如车位数、车位状态、有无车辆进出场等；其次，根据以驾驶员舒适度为主的原则选择驾驶员步行路径最短的车位并将其作为目标车位；最后，通过优化的交互式蚁群算法为进入停车场的车辆选择最短路径。

1 相关算法介绍

1.1 基本蚁群算法

基本蚁群算法是以蚂蚁的行走路径组成可行解的集合，蚂蚁在行进过程中会留下信息素以标记所走路径，且在单位时间内短路径上的信息素浓度会高于较长路径上的信息素浓度。其他蚂蚁会根据之前蚂蚁遗留下来的信息素选择信息素浓度较高的路径，随着时间的推移，较短路径上的信息素浓度就会越来越高，而较长路径上的信息素浓度会随着蚂蚁的减少而变得越来越淡。蚂蚁最终会根据信息素浓度逐渐聚拢到较短路径上，从而找到最短路径[16]。

1.2 交互式蚁群算法

交互式蚁群算法是基于新型建筑智能化平台设计并实现的，其主要特点是利用CPN实现信息实时交互，从而达到无中心、扁平化的目的。交互式蚁群算法是在基本蚁群算法上进行的改进，主要思想是：当所有蚁群完成一次搜寻后，各个CPN之间会交互蚂蚁搜寻结果，包括信息素矩阵和最短路径，若某CPN在此次迭代中的搜寻结果不是最优，就会舍弃自身的搜寻结果，通过CPN之间的信息交互获取邻居节点中最优的搜寻结果，并继续进行下一次迭代，直到找到正确的最佳路径。其流程图如图1所示。

图1 交互式蚁群算法流程图

其具体步骤如下所示：

(1)初始化信息。为了更好地模拟现实场景中的路径长度、走向及道路状况，需要将应用场景进行数学建模，并构建相应的禁忌表来标记路径上存在的障碍物等信息。

(2)初始化算法参数。算法参数包括启发式因子、期望式因子、信息素挥发速度以及信息素矩阵等。

(3)根据数学模型、禁忌表和以驾驶员舒适度为主要原则选择最佳目的地。

(4)初始化迭代次数和蚂蚁种群数。

(5)记录起点位置。蚂蚁K会根据转移状态矩阵选择下一步该走哪个点。转移状态矩阵计算公式如下：

(1)

(2)

(6)判断蚂蚁K是否到达了目的地。若到达，则该蚂蚁结束搜寻；若没有到达，则重复步骤(5)。

(7)当所有蚂蚁到达目的地后，需要根据所有蚂蚁的搜寻路径更新全局信息素浓度。计算公式如下：

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

(3)

(4)

(5)

式中：τij(t+n)是指(t+n)时刻路径(i,j)上的信息素浓度，τij(t)是指时刻路径(i,j)上的信息素浓度,Δτijk(t)是指t时刻第k只蚂蚁在路径(i,j)上增加的信息素浓度，Q是指信息素增加强度，Lk是指第k只蚂蚁走过的路径总长度。

(8)当所有蚂蚁都完成一次迭代以后，CPN会交互本次迭代的最佳搜寻结果，包括最短路径和信息素矩阵。

(9)CPN判断最佳搜寻结果是否产生于本节点，如果不是最佳搜寻结果，则丢弃本节点搜寻结果，以获取邻居节点中最佳的搜寻结果。

(10)判断是否满足算法结束的条件，如果没有满足算法结束条件，则进行下一次迭代，即重新从步骤(5)开始执行。如果满足算法结束条件，则结束搜寻并输出最短路径及其长度。

2 试验过程

基于新型建筑智能化平台，在地下停车场内使用交互式蚁群算法进行目标车位搜寻和最佳路径规划的试验流程如图2所示。

图2 试验流程示意图

2.1 构建停车场模型

以某商场为实验背景，通过将停车场中的各个顶点进行坐标化的方法对地下停车场进行建模。该停车场总占地面积超过20000 m2，其中包括2个车辆出入口和4个电梯出口，总车位数达到600个(如图3所示)。

图3 某商场地下一层停车场示意图

图4 地下停车场特征点选择示意图

根据地下停车场的建筑特征，适量地选取地下停车场中特征点，并以坐标轴的形式描述各个特征点的位置信息。特征点的选择如图4所示，其中fk(k=1,2,3,...，t)为车位的编号，ci(i=1,2,3,...，n)为地下停车场中的出入口，dj(j=1,2,3,...，m)为车道中心点即选取的地下停车场中车道中间的点，用于路径引导。特征点的主要作用是对停车场道路进行标记，以便在进行路径规划的时候规避停车场内的障碍物。

2.2 设计启发式函数

在基本的蚁群算法中，启发式函数与状态转移概率成正相关关系，即当启发式函数越大时，蚂蚁从点到点的概率就越大。在基本蚁群算法中启发式函数一般取两点之间距离的倒数，即两点之间距离越小，启发式函数就越大。当交互式蚁群算法应用在地下停车场中时要考虑各点之间是否为直接相连的关系，即各点之间是否存在直接连通的道路，若两点之间不是直接相连，则不能直接以两点间的距离来表示这两点间的启发式函数。因此，本文提出了适用于地下停车场的启发式函数，具体定义式为：

(6)

(7)

(8)

式中：ωij表示点i和点j之间的权值，lij为点i到点j的实际距离，xi，yj为点的X轴与Y轴的坐标值；Mij为不直接相连的i，j两点间的距离的集合，max(Mij)是指i，j两点间的最大距离值。

2.3 设置蚁群算法参数

在蚁群算法中信息素残留因子(1-ρ)、启发式因子α和期望式因子β都会影响算法的效率和准确度，且对于这类参数的选择没有相关的理论依据。为了更加科学地选择这3种参数的数值，本文分别对这3个参数进行了对比试验。对比试验以吴江华润万象城为例，蚂蚁数量为40，最大迭代次数设100，将10次试验得到的平均最短路径和平均迭代次数作为衡量标准。

2.3.1 信息素残留因子ρ

信息素残留因子是表征蚂蚁之间联系强弱的参数，主要影响算法的运行效率和准确度。根据信息素残留因子、启发式因子和期望式因子的取值范围，参考相关文献，将试验参数设置为α=1，β=1，ρ={0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9}，试验结果如图5、图6所示。由图5、6可知，当ρ=0.3时，平均最短路径和平均迭代次数最小，因此将ρ设置为0.3，即1-ρ=0.7。

图5 平均路径长度相对于 图6 平均迭代次数相对于信息素残留度变化曲线 信息素残留度变化曲线

2.3.2 启发式因子α和期望式因子β

启发式因子和期望式因子表示行进过程中积累的信息量和启发式信息对蚂蚁引导的相对重要程度，且两者之间存在相互影响。基于上文对信息素残留因子的实验结果，本实验的参数设置为1-ρ=0.7，(α，β)={(1，1)，(1，2)，(1，3)，(1，4)，(1，5)，(2，1)，(3，1)，(4，1)，(5，1)}，试验结果如表1所示。根据实验结果，本文将启发式因子α的数值设置为1，期望式因子β的数值设置为1，即(α，β)=(1，1)。

表1 启发式因子、期望式因子对平均路径和平均迭代次数的影响

2.4 确定目标车位

确定最佳车位的主要因素包括车辆入场的位置、电梯的位置和车位状态三个部分，具体流程如图7所示。

图7 最佳车位选择流程图

首先，选择空闲状态的车位并根据电梯出口的位置计算出离电梯最近的车位编号；其次，判断最近距离的车位个数是否大于1，如果车位的个数大于1，则计算这些车位到车辆入场位置的距离；最后，选择到车辆入场位置的距离最小的车位为目标车位。

交互式蚁群算法根据地下停车场模型提供的数据进行目标车位的选择。确定好目标车位后，交互式蚁群算法根据车辆起点位置、目标车位的位置以及停车场内的环境分布进行最短路径规划并引导驾驶员到达目标车位。

为了验证交互式蚁群算法的有效性和可靠性，本文在相同的试验环境和参数设置下对交互式蚁群算法、基本蚁群算法和遗传算法进行了多次对比试验。

3 试验结果与分析

3.1 单辆车的最短路径规划试验结果分析

在同一场景和相同参数设置下，采用基本蚁群算法和遗传算法在车辆入场位置和最佳车位之间进行最短路径规划对比试验，试验结果如图8所示。基本蚁群算法首先找到最短路径，故二者相比，基本蚁群算法的收敛速度更快。

图8 基本蚁群算法与遗传算法实验结果对比图

为了验证算法的高效性和准确度，在同种试验条件下分别对两种算法做了50次对比试验，试验结果如表2所示。基本蚁群算法的平均最短路径长度较遗传算法减小5.16 m，迭代次数的方差比遗传算法减小15.66，最短路径规划准确率较遗传算法提高了4%。

表2 基本蚁群算法和遗传算法对比实验结果

在同一场景和相同的参数设置下，采用基本蚁群算法和交互式蚁群算法在车辆入场位置和最佳车位之间进行了最短路径规划，试验结果如图9所示。交互式蚁群算法首先找到最短路径，故二者相比，交互式蚁群算法的收敛速度更快。

图9 基本蚁群算法与交互式蚁群算法试验结果对比图

为了验证算法的高效性和准确度，在同种试验条件下分别对两种算法做了50次对比试验，试验结果如表3所示。交互式蚁群算法搜寻的最短路径的最大值、最小值和平均值均一致，且其最短路径的最大值、最小值和平均值均为最小，其迭代次数的方差比基本蚁群算法减小1.75，其最短路径规划的准确率较蚁群算法提高了8%，说明交互式蚁群算法提高了最短路径规划的准确率和可靠性。通过对比试验结果可知，交互式蚁群算法能够更快地找到正确的最短路径。

表3 基本蚁群算法和交互式蚁群算法对比实验结果

3.2 连续车辆的最短路径规划试验分析

在同一场景和相同的参数设置下，采用交互式蚁群算法、基本蚁群算法和遗传算法对10辆连续进场的车辆进行了20次路径规划对比实验，实验结果如图10所示。交互式蚁群算法的准确率达到了100%，高于基本蚁群算法和遗传算法，且其准确率变化趋势相对平稳。交互式蚁群算法的迭代次数的方差、平均迭代次数和平均路径长度较蚁群算法有了明显的降低。由表4可知，交互式蚁群算法的准确率比基本蚁群算法提高了4.5%，比遗传算法提高了16%，故交互式蚁群算法比基本蚁群算法和遗传算法更加有效。

图10 路径规划准确率变化曲线图

表4 交互式蚁群算法、基本蚁群算法和遗传算法试验结果对比

4 结论

设计交互式蚁群算法对停车场进行最短路径规划以便提高停车场运行效率。首先，对停车场进行数学建模。其次，根据车辆进场位置确定最佳停车位。最后，利用交互式蚁群算法在车辆入场位置和最佳车位之间进行最短路径规划。在单辆车路径规划对比试验和连续车辆路径规划对比试验中，交互式蚁群算法的准确率达到了100%，表明了交互式蚁群算法的可靠性。交互式蚁群算法的迭代次数的方差、平均迭代次数和平均路径长度比基本蚁群算法都有了明显的降低，表明交互式蚁群算法具有较高的可靠性、有效性和可行性。