基于蚁群算法的智能停车场引导系统①

张晶晶, 薛 伟

(江南大学 物联网工程学院, 无锡 214122)

1 引言

现在许多大型停车场依旧是传统的人工管理停车场方式, 而人工管理停车场存在很多问题. 停车场内剩余车位信息“不透明”, 没有被占用的车位位置不明确,车主停车时无法及时找到空余停车位, 这就造成停车场利用率低下[1]. 除此之外, 驾驶员在停车场内迂回地寻找车位一方面容易造成停车场内车辆拥堵, 另一方面大量汽车在寻找车位时排放的汽车尾气容易造成空气污染[2]. 本文针对这一问题, 设计了智能停车场. 智能停车场内的每个车位上空放置超声波车位传感器采集车位信息, 并通过ZigBee无线网络传输信息[3]. 停车场内的管理系统[4]采用Microsoft Visual Studio平台设计,主要完成车位信息的处理和存储. 停车场内岔路口处有方向显示屏, 显示左、前、右方向信息, 指引泊车者行进方向, 将车停至最佳停车位置. 这个智能停车诱导系统就能避免泊车者在停车场盲目寻找车位, 减少了汽车在寻找车位时在道路上迂回浪费的时间, 缓解道路空间, 节约资源, 同时也减轻工作人员的负担, 降低人工成本, 提高停车场的利用率.

2 系统总体设计

本文提出了一种基于蚁群算法的智能停车诱导系统, 该系统采用的技术方案包括超声波车位检测,ZigBee无线传输协议, VS平台软件开发. 该智能停车场系统包括上位机综合管理, 空车位检测, 车辆引导等功能. 总体结构框图如图1所示.

图1 系统总体框架图

2.1 ZigBee无线模块与超声波车位探测

超声波车位传感是基于ZigBee终端模块设计的,采用HC-SR04超声波测距模块检测距离, 放置在距离车位上空3.5 m处的位置. 模块的发射器发送8个40 kHz的方波自动检测, 如果发现有障碍物则接收器接受返回的信号. 汽车高度范围在1.3–2.2 m之间, 所以如果检测到1.3–2.2 m处有障碍物代表车位有车红灯亮, 否则绿灯亮.

ZigBee无线模块包括终端、路由器、协调器都是采用TI公司生产的以CC2530芯片为核心, CC2530芯片[5]支持IEEE802.15.4标准、ZigBee标准、ZigBee RF4CE标准的无线传感器网络协议, 具有优秀的接收器灵敏度和健壮抗干扰性, 支持低功耗的无线通信.

无线传输网络采用Z-Stack协议栈, Z-Stack包含了网状拓扑的几乎全部功能的协议栈, 开发者可以很容易地开发出具体的应用程序. 在本系统选择了树状网络拓扑结构, 首先协调器节点负责建立一个网络和整合数据信息, 终端节点负责加入网络和通过无线传输的方式将接收的超声波车位检测信息上传至父节点,经过路由器节点上传至协调器. 如图2包括终端(即基于ZigBee模块的超声波车位传感器)、路由器、协调器.

图2 ZigBee模块

2.2 改进蚁群算法与管理员平台

2.2.1 改进蚁群算法

如图3所示的简易停车场平面结构图, 根据图显示的停车场平面图建立停车场抽象模型. 为建立停车场车位模型将图中的有两条及以上行车方向的交叉路口, 以及各个停车位作为节点. 将各个可相通的交叉路口之间的路段和各个停车位到与之相通的交叉路口的路段作为边.

图3 停车场平面结构图

如图4所示的停车场抽象模型, 边权构成网状结构图转化为带权有向图G=(V, E), 其中V是包含所有节点的集合, E表示所有包含边(弧段)的集合. 图中Ri(1≤i≤6)是停车场的各个岔路口节点, 其中R1作为

停车场的入口节点, R3作为停车场的出口节点, 图中的P29, P32等代表的是剩余空车位节点. 蚁群算法计算从停车场入口R1到各个空余停车位的距离, 然后进行比较得出最短路径, 获得最优停车位以及到达该停车位的路线, 所以建立边权的权值就是各个部分的实际距离. 边权的构建包含两个方面, 一个是各个交叉路口之间的边权(即交叉路口之间的距离), 采用符号W＜Ri, Rj＞(1≤i,j≤6)表示; 另一个是交叉路口到具体停车位的边权采用符号W＜Ri, Pk＞(1≤i≤6)(k=1, 2, 3,…)表示.

图4 带权有向图

基本蚁群算法是一种源于大自然生物世界的新的仿生进化算法, 模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法[6]. 蚂蚁在寻找食物的行进过程中在其走过的路径上释放信息素,随着时间的推移, 路径上的信息素会挥发, 后来的蚂蚁会根据信息素的强度来决定选择该路径的概率. 根据真实蚁群在搜索食物时解决最短路径的问题的方式,可以构建人工蚁群解决本文的最短路径问题.

基本蚁群算法应用在停车场的应用中会出现一些问题, 例如死锁, 停滞, 甚至无解(即无法到达指定终点无法得出结果)的情况. 针对上述问题并且为了更好地应用于停车场的情况, 对传统蚁群算法进行改进, 主要包括三个方面: MAX-MIN Ant System[7](最大-最小蚂蚁系统), 局部信息素更新[8]和撤退方法. 这样既能搜索更大的解空间, 又能使系统陷入局部最优后跳出停滞状态. 而为了增加蚂蚁的全局搜索性, 并且能够有机会选择更多的路径方向, 在选择下一步的转移规则中增加轮盘赌算法.

(1) MAX-MIN Ant System

最大最小蚂蚁系统为了充分利用当前循环中的最优解, 在每次循环之后, 得到的最优解的蚂蚁走过的路径进行信息素更新. 除此之后, 将每条路径上的信息素的值域范围限制在[τmin,τmax]区间内, 这就避免过多蚂蚁行进相同路径而使得路径上的信息素远远高于其他边, 而导致再次吸引更多的蚂蚁在同路径上行进.

(2) 局部信息素更新

最大最小蚂蚁系统中, 只更新每次循环中最优解路径上的信息素, 而为了更好地搜索到最优解, 本文在系统中增加局部更新规则, 如式(1)所示:

其中,τ0表示是各个路径的信息素的初始值, 那么全局最优蚂蚁的信息素的更新规则如式(2)所示:

其中,Lbest表示最优路径的长度.

(3) 撤退方法

蚁群算法在停车场结构图的应用中易出现无解的情况, 例如一个路径的终点是R3, 而蚂蚁在行动中走的路线是R1→R2→R5→R4, 蚁群算法在运行中要求一个节点只能走一次, 那么如果出现上述的路线, 蚂蚁将无法走到终点R3. 为了解决这个问题提出了撤退方法, 如果过程中出现上述类似问题, 将蚂蚁的走向退回到R5节点, 并且将R5→R4路段上的信息素更新为零,利用轮盘赌算法再次为蚂蚁重新选择下一节点, 避免蚂蚁重复上述路段, 直至有路线能够到达终点.

2.2.2 算法执行步骤及实验结果

Step1. 建立停车场平面图模型, 利用贪婪算法规划出一条从初始点到终点的初始路径, 然后计算出τ0.

Step2. 蚁群参数初始化, 设置参数m,α,β,ρ,Q的值, 令循环次数Nc=0和τ=τmax, 设置最大迭代次数G,将m只蚂蚁置于初始节点.

Step3. 蚁群算法开始搜索, 当前蚂蚁节点i，按照如下公式和轮盘赌算法计算下一节点j:

Step4. 判断下一节点j是否确定, 如果无法取得j则选择撤退方法, 再返回到Step4并且路径上信息素更新为0. 如果下一节点j确定, 蚂蚁要对刚走过的路径＜i,j＞上的信息素按照式(1)进行局部信息素更新,并将该节点放入路径表中.

Step5. 判断蚂蚁是否达到终点, 若达到终点则转到Step6, 否则转到Step3.

Step6. 统计当前m只蚂蚁搜索到的最优路径, 选出最短路径, 并将此路线上的信息素通过式(2)局部更新和式(3)进行全局最优蚂蚁的信息素更新.

Step7. 若满足结束条件, 即循环次数Nc≥G, 则程序结束并输出最优结果, 否则清空禁忌表并转至Step3.

根据建立的停车场模型, 搜索最优停车位, 编程环境 VS2013. 设置m=50,ρ=0.5,α=1,β=2,G=300. 根据上述步骤得出实验步骤, 结果如表1所示.

表1 停车场仿真实验结果

实验结果表明, 最佳车位是P46, 路线(S)R1→R2→P46.

2.2.3 管理员平台

管理员平台作为主控机一般采用PC机, 放置在中央控制室, 该上位机主要用来进行人机交互, 并在无线局域网内向显示屏发送方向命令. 我们采用Visual Studio2013在Windows平台上对上位机人机交互界面进行设计, 使用.Net框架下的TCP传输协议建立TCP通信, 设置IP地址以及端口号方便与显示屏建立连接.

具体实现功能, 接收、处理和存储下位机上传的车位信息, 将车位信息内容展示在上位机平台上, 如图5的上位机管理员界面, 红色(图中深色着色)代表此车位已被占用, 绿色(图中浅色着色) 代表车位状态是空闲. 上位机内部统计车位节点信息, 通过改进蚁群算法计算出最优停车路线并保存在数据库中, 为方向引导屏提供信息支持, 以及显示剩余车位信息.

图5 管理员界面

2.3 方向引导屏

采用Visual Studio2013在Windows平台设置的显示屏悬挂在停车场内岔路口上方, 显示屏输入IP地址与端口号以及所在岔路口的节点名称在局域网内与服务器建立通信, 接收从管理员服务器的信息, 指引驾驶员行驶到达最优的停车位置.

如图6所示, 图6的引导屏位于停车场入口的R1位置, 假定停车场先后进入两辆停车场, 获得两辆车的车牌号分别为苏B01010和苏B02020, 由蚁群算法得出的最优的停车位是P29, 所以为第一位驾驶员指向前行驶方向, 指引第一位驾驶员将车停至P29车位.在假定第一停车位已经被占用的情况下, 为第二辆车辆分配最佳车位P35, 到达P35停车位经过的拐角路径是R1→R2, 所以在R1入口处为苏B02020车辆指引向左行驶方向, 将苏B02020车辆指引至R2节点处,再由R2节点处的引导屏指引车辆停至P35车位.

图6 方向引导屏

3 结论

针对停车场内停车难问题, 在停车位上方安装超声波告诉泊车者车位信息; 提出用蚁群算法解决场内最优解问题, 针对停车场的模型对蚁群算法进行优化改进, 使改进后的蚁群算法能更好应用在停车场; 上位机通过改进的蚁群算法计算出距离停车场入口最近的空闲停车位, 并得出具体路线, 通过TCP/IP通信方式向方向指引屏传输信息诱导驾驶员行驶至最佳停车位.本系统的设计能够避免驾驶员在停车场内盲目寻找停车位, 实现了对车位智能诱导功能, 有效地提高停车场的运行效率.