AGV智能停车库车位规划算法研究

李飞飞

（上海海事大学信息工程学院，上海 201306）

0 引言

当前，越来越多的人将汽车作为代步工具，随之而来的是停车场车位严重不足、存取车效率低等问题，严重影响了人们自驾出行的体验感。基于此种社会背景下，对于如何缓解泊车压力已成为提高社会生活舒适性的关键问题。因此基于自动导引运输车（AGV）的自动化停车场应运而生。AGV智能停车具有空间利用率高、存取车过程更加安全等优点。近年来，产生了多种基于多AGV进行路径规划以提高存取车效率的方法。文献[1-3]采用时间窗以及优先级策略或者Dijka⁃tra算法去规划泊车系统的最佳行驶路径，结果表明，所提出的路径规划方法有效解决了目前多AGV路径规划柔性差、易出现死锁碰撞冲突等问题。文献[4-6]采用一种基于遗传算法的路径搜索方法，此方法提高了全局的搜索能力。以上文献所提及的方法都是在原有停车场车位分布不变的情况下，旨在通过规划路径去提高存取车的效率。

本文尝试通过去规划停车场的最佳物理车位的分布位置，以期从源头上缩短存取车路径等问题。

1 问题描述及数学抽象

本文是在一个空白停车场背景下去探索车位物理分布的方法，由于AGV的行车道路比普通停车场窄，一般宽度和车位宽度一致即可，故可将空白停车场的初始状态全都规划为大小一致的长方形并且所有的长方形除去出入口之外都为待规划车位。此时，空白停车场的初始状态如图1所示：

图1 空白停车场初始车位状态

其中，五边形填充的为停车场的出入口，长方形填充的为所有待选车位。

本文需要通过寻找车位位置的算法从所有待选车位中选出最大的可使用的车位数量，被选中的待选车位点设置为一个车位，未被选中的待选车位点设置为道路，同时需确保每一个车位点都能够成功到达出入口。

将图1中的矩形待选车位和六边形出入口都抽象形成一个点，那么便可以将停车场地图信息抽象成网格图的形式，可将网格图表示成矩阵如下所示：

其中，矩阵中的元素代表图1中矩形停车场所抽象成的待规划车位以及停车场的出入口。若待规划车位未被选定为车位，则代表道路信息。利用车位寻找算法去确定所有待规划车位点中哪些为车位、哪些为道路。

2 基于Dijkstra算法的部分最优车位规划算法的实现

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是从一个顶点到其余各顶点的最路径算法，解决的是有向图中最短路径问题。Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

本文中基于Dijkstra的部分最优车位规划算法的内容如下：

（1）将停车场地图信息抽象为图2中所示的矩阵形式。

（2）从所有待规划车位点（00,01,02…0n;10,11,12…1n；…；m0,m1,m2…mn）中（去除出口、入口）随机选择 t（t＜＜m*n）个没有任何偏好的车位点作为初始车位组合，记为 G=（a1,a2,a3,…,at）,并确保 t个车位点都能避开阻碍到达出入口。

（3）在初始车位组合的基础上筛选下一个最优车位点，过程如下：

将去除初始车位点及出入口点后的每一个待规划车位点逐一添加入车位初始组合中，每添加一个点进入初始车位点后计算初始车位组合中所有点到达出口及入口的距离和，按照从小到大的顺序排列，记为（at+1,at+2,at+3,at+4,…,amn-2）,将距离和最小的加入车位组合中，即将at+1加入G中，验证车位组合G中的点是否都能避开阻碍到达出入口，若组合中的所有点都能成功到达出入口，则为可用点，加入到车位组合G中并将此点从地图信息中删除掉继续寻找下一个车位点，依次循环直到所有点都为不可用点则找到了所有的车位组合G。寻找下一个车位点的公式如下：

其中，anext_q表示寻找到的下一个车位点，si表示点到出入口的距离之和，q表示寻找到的第j个车位点，t表示随机选出的没有任何偏好的初始车位点的个数。

最终寻找到的可有效规划的车位总数公式G'如下：

3 基于部分最优车位寻找算法的寻找流程

（1）设置初始车位点组合参数；

（2）通过算法模型求得基于初始参数的车位组合G；

（3）依据算法模型中的初始车位点参数去执行算法模型求得最大车位的数量及位置分布。

4 实验仿真及结果分析

本文通过有效的实验仿真来验证基于Dijkstra的部分最优车位规划算法能够根据初始车位点组合完成自动寻找最佳停车位位置的功能。本实验的硬件环境是Win7系统的Dell台式电脑，采用Python2.7软件进行仿真编程实验。本实验采用一种可动态调整矩阵大小的停车场地图信息方案，根据停车场的具体信息去设定矩阵的参数值。

本文选取停车场地图信息的矩阵参数为8×8，设定矩阵中的点（0,0）位停车场的入口，设定矩阵中的点（0,7）为停车场的出口,其余点为待规划的车位点，实验中将随机初始车位点设定为6进行实验，选取其中五组实验数据记录在表1中，如下所示：

表1 当初始车位为6时，最终的车位数量

表1中的数据显示，当随机的初始车位点的数量为6时，所寻找出的最终车位数量呈现出稳定于某一个数值范围。

取表1中的序列号1为例，当初始车位组合参数坐标为[（6,1）,（4,0）,（7,6）,（0,4）,（1,0）,（6,3）]，寻找到的最终车位坐标为[（6,1）,（4,0）,（7,6）,（0,4）,（1,0）,（6,3）,（1,7）,（2,5）,（2,4）,（2,3）,（2,2）,（0,5）,（0,3）,（0,2）,（3,5）,（2,7）,（2,0）,（4,5）,（3,7）,（3,0）,（5,5）,（4,7）,（4,2）,（5,7）,（5,3）,（5,0）,（4,3）,（7,5）,（7,4）,（6,7）,（7,2）,（5,4）,（4,4）]，将坐标呈现于图上如图2所示：

图2 初始车位组合参数为6时所寻找到的车位分布

将普通停车场的车位分布方式中一种方案图表示为如图3所示：

图3 一种普通停车场车位分布图

图2和图3分别展示了一次实验中所有车位点的分布位置，其中使用矩阵块填充的代表车位的位置，五边形填充的代表停车场的出口和入口。由图2的车位分布图可得知：本文中采用此算法所得到的总的车位数量为33，由图3的车位分布图可知，这种普通停车场容纳的车位数量为30，通过对比发现，本文中的车位规划方案略具有优势，同时，从图2中可知，本文中所用方案得到的车位道路可选择性更多灵活性更高，并且，图3中的停车场车位方案排布依据路径最短算法得出，在总路径长度上具有短的优势。

5 结语

为了改善传统停车场车位灵活性以及效率低的问题，提出一种基于Dijkstra的部分最优车位规划算法，车位的分布更具合理性，效率更高，本文提出的方法为智能新型停车场提供了新的思路，为未来泊车系统提供了新的探索。

在仿真实验中发现，初始车位组合中的初始车位点坐标不同时，所寻找到的最终车位分布坐标有很大的不同，但初始车位点的最佳坐标并没有给出标准，希望以后的探索能够改善此不足。

[1]施剑烽,杨勇生.基于改进的Dijkstra算法AGV路径规划研究[J].科技视界，2016（20）:111-112.

[2]陈志刚,卢山.时间窗约束下基于概率模型的AGV路径研究[J].物流工程与管理，2017，39（10）:65-67+32.

[3]凌剑.复杂环境下AGVS调度系统设计[D].东南大学,2016.

[4]苑光明,翟云飞,丁承君,张鹏.基于改进遗传算法的AGV路径规划[J].北京联合大学学报，2018，32（01）:65-69.

[5]王松涛.基于优化的遗传算子改进蚁群算法AGV路径规划[J].自动化应用，2017（03）:47-49.

[6]井治财,史恩秀.基于免疫遗传算法的AGV路径规划方法研究[J].科技与企业，2016（5）:224-225.DOI:10.3969/j.issn.1004-9207.2016.05.196.