考虑路径长度与冲突的AGV停车场停车位分配方法

姚宝珍，张 晋，时 彬，崔贺琪，张明恒

（大连理工大学汽车工程学院，辽宁 大连 116024）

0 引言

近年来，我国汽车保有量持续增长，而城市停车位数量增长缓慢，停车难问题日益突出。同时，已有停车设施使用效率低，停车信息不通畅，驾驶者寻找车位过程中的无效巡游导致停车拥堵和大量的尾气排放[1-2]。为解决城市停车难题，基于自动引导小车（Automated Guided Vehicles,AGV）的智能停车场应运而生。AGV 因其可实现无人化泊车、便于集中管理停车位信息等优势在智能停车领域具有巨大的应用潜力，通过AGV 实现全自动无人泊车管理成为近年来停车领域的研究热点。

AGV 路径规划作为AGV 系统的重要组成部分，直接关乎AGV系统效率优化、AGV运行安全保障、AGV 能耗降低等[3]，因此得到了广泛研究。目前，国内外关于AGV 路径规划问题的研究侧重于多AGV 路径规划及调度，如刘二辉提出一种改进的花授粉算法求解多AGV 任务调度问题[4]；王家君提出一种基于紧急程度的任务分配算法，用于解决智能停车场内泊车AGV 冲突问题[5]；Xu等提出一种两阶段的AGV 路径规划方法，先使用遗传算法对AGV 进行静态最优路径规划，再采取在线调度的策略以避免多AGV 的冲突碰撞[6]；Bai等将强化学习算法与改进的遗传算法相结合，并将调度策略集成到全局静态路径规划中，可根据动态环境的变化不断调整多AGV 的调度策略，避免AGV 之间产生冲突[7]；Umar 等采用遗传算法对多AGV 进行路径规划，并通过一定的约束目标设立优先级来解决任务执行过程中的冲突问题[8]；Sun 等采用时间窗算法，使每个AGV 可根据时间窗口动态调整路径，从而实现AGV 的无冲突路径规划[9]。上述研究大多从改进路径规划算法和协同调度方法入手，大多数针对智能物流及智能制造等AGV 工作环境，从局部视角对已形成的冲突进行消解，但对AGV 间冲突的产生缺乏解决能力。对于道路狭窄、布局紧凑的停车场环境，上述研究中基于路径规划的方法优化空间非常有限，并不能有效避免冲突的产生。当下仍缺乏从全局层面减少AGV冲突产生的有效方法。

在AGV 智能停车场中，综合考虑AGV 行驶距离、行驶路径的干扰及冲突，进而为待停车辆分配合适的停车位置，可以有效地减少AGV 之间的干扰，从而改善停车场内的交通状况，因此关于停车位分配方法的研究逐渐受到重视。关于停车位分配问题的既有研究，大多针对为人类驾驶的车辆分配最佳停车位[10-11]，如肖玮设计了一种基于多目标点A*算法的停车场车位路径引导系统，综合考虑用户需求和停车路径长度为待停车辆分配最优停车位[12]。还有一些研究则从空间利用率、存取效率的角度出发，重点解决立体车库场景下的停车位分配问题，如邢丽娟等采用随机车位分配策略和就近车位分配策略，针对车辆入库和出库、车位利用率、堆垛机运行距离等建立仿真模型[13]；Li 等提出一种基于博弈论的停车位搜索方法，可在比启发式谨慎策略更短的行驶距离内找到可用的停车位[14]。然而，现有针对停车位分配问题的研究与AGV 智能停车场的环境背景区别较大，若直接应用于AGV 智能停车场环境中，可能导致AGV 工作区域过于集中，造成频繁的拥堵和冲突，但其中一些多目标优化的思路和算法仍具启发意义。

总体上，现有关于AGV 在智能停车场领域应用的研究成果主要针对局部视角中已经产生冲突的规划调度问题，而在全局层面的停车位分配问题研究中忽略了AGV 智能停车场环境的特殊性。因此，本文在充分考虑AGV智能停车场环境特征的基础上，将提出一种考虑路径长度与冲突的AGV智能停车场停车位分配模型，将停车路径冲突概率和停车路径长度纳入模型目标函数，以期在全局层面为待停放车辆分配合理的停车位，在AGV 执行停车任务前降低多台AGV 路径之间产生冲突的概率，同时在局部层面，最小化停车任务的路径长度，进而提升AGV 智能停车场运营效率。此外，设计NSGA-Ⅱ算法对所提出的模型进行求解，最后通过仿真实验对模型和算法的有效性进行验证。

1 停车场环境描述及地图建模

1.1 AGV智能停车场描述

本研究主要针对由现有停车设施改建的AGV智能停车场，车辆到达停放或取车离开停车场的过程采用AGV 进行自动化搬运。考虑到取车问题是一个端到端的最短路径规划问题，路径起点及终点均已确定，因此本研究的重点为存取车高峰期的连续停车问题。停车场有多个出入口且在出入口设有交换等待区，驾驶人将待停放车辆停放在交换等待区后离开车辆。停车场控制系统将查询当前停车场状态，为待停放车辆分配一个空闲停车位，随后指派1 台空闲AGV 将待停放车辆搬运至系统分配的停车位。整个停车过程可分为以下几个步骤。

1）车辆驶入停车场。驾驶员将车辆驶入停车场入口，并停放在指定的临时交换等待区域。

2）车辆请求停车。当待停车辆到达停车场入口时，向停车场控制系统发送请求停车信号。

3）分配停车位。控制系统接收到请求信号后，会根据当前停车场内空余车位的情况，为待停车辆分配1 个合适的停车位，通常采用随机分配、最近可用等算法。

4）分配任务至AGV。任务系统为当前停车任务分配1 台空闲AGV，AGV 从交换等待区载运待停车辆。

5）导航至停车位。控制系统将停车位的位置信息及规划路径信息发送给AGV，然后AGV根据路径信息自主将待停放车辆搬运至分配的停车位。

6）完成停车。AGV 到达停车位后，使用机械臂将车辆抬起并移动到停车位后放下车辆，完成停车任务。

7）更新AGV 停车场状态。停车系统更新车辆停放位置、停车状态及空闲停车位信息，等待接收下一个停车任务。

通常，大型停车场包含数百个停车位，并根据布局分为几个区域。为了增加研究结果的可扩展性，假设停车场不同区域的布局结构及车位数量相似。在实际应用中，停车场内一般有多个出入口，不同区域间的车辆交互较少，受郝树运[15]提出的AGV 停车场布局启发，本文以某AGV 停车场单个停车区为基础展开研究，如图1 所示。该停车区包含102 个停车位、6 个交换等待区车位。停车位尺寸设计为5.5 m × 2.5 m，满足AGV旋转半径的车道宽度为5.5 m。交换等待区停车位在实际应用中需考虑人员上下车操作空间，因此应比普通停车位尺寸大，但为便于研究，建模过程中假设交换等待区停车位尺寸设计与普通停车位相同。

图1 AGV智能停车场环境布局

为简化问题并突出关键环节，对停车环境做如下约束：

1）车辆通过同一交换口进出停车场；

2）AGV从入口位置开始执行停车任务；

3）停车场内部车道为双向单车道，宽度满足AGV的最大转弯半径；

4）AGV 被视为具有安全半径的粒子且以恒定速度行驶，每次转弯时间相同；

5）AGV 只有在进入停车位时允许跨越路径行驶；

6）交叉口允许AGV 从4 个方向进入且可以直行、左转、右转，同一节点同一时刻仅允许1台AGV进入。

1.2 停车场环境地图建模

AGV 作业系统中，环境地图建模方法至关重要，对作业环境准确建模可使AGV 系统精准地识别障碍物和危险区域，进而使路径规划更高效。此外，合理的环境地图建模可使AGV 系统更具适应性，以应对不同的任务类型。环境地图建模方法主要有3 种，分别为栅格法、拓扑法和可视图法。其中，基于拓扑法构建的电子地图主要强调空间的连通性，通过绘制节点之间的边来表示AGV 可通行的区域，这种建模方法可有效预防AGV 与静态障碍物的碰撞。与栅格法和可视图法相比，在同等规模的环境条件下，基于拓扑法构建的电子地图节点数较少，资源占有率较低，有利于提高算法寻优效率。考虑到本研究是从全局的角度进行车位分配和路径规划，不考虑环境中动态障碍物的影响，故选择拓扑地图法用于智能停车场的环境建模。

在拓扑地图建模中，地图结构被抽象成一个图，由连接顶点和顶点间的边构成，用数学方法可以表示为G（V,E），其中G表示图，V是图G中的顶点集合，E是图G中的边集合。根据工作线路的单向和双向行驶要求，连线分为有向和无向。拓扑法在进行计算时，需要针对现有拓扑图，根据连线的方向属性建立相应的邻接矩阵，即把每个点的连接关系通过矩阵具体化。采用拓扑图法建立的停车区域电子有向地图如图2所示，其中节点1～6 为交换等待区节点，节点7～108 为停车位节点，节点109～252为路径节点。

图2 停车区域拓扑地图建立

为使所建停车场电子环境地图直观且便于理解，建模过程中忽略了停车场实际环境中的立柱区域及其他设备空间。节点间的实际距离以权值的形式表示并记录在拓扑地图的邻接矩阵中。部分邻接矩阵信息如表1 所示。其中，与停车位节点相对应的路径节点连接而成的路径边，如（140,141）和（141,142）的权值均为2.5，表示AGV 搬运待停放车辆从节点142 行驶至节点141或从节点141 行驶至节点140 需要行驶2.5 m。路径节点与停车位节点连接成的边如（30,142），其权值为3.375，表示AGV 搬运待停放车辆从路径节点142 行驶至停车位节点30，需要行驶3.375 m。此外，图中的长路径边如（145,144），其边权值为11，表示AGV 从节点144 行驶至节点145需要行驶11 m。表1中∞表示不可通行，例如边（140,142）的权值为∞，表示节点142 与节点140间无可通行路径。

表1 部分节点拓扑关系数据

2 停车位分配模型构建及算法求解

本研究针对AGV 智能停车场，从停车位分配的角度出发，为待停放车辆分配最优停车位，并对停车AGV 进行路径规划。最优停车位是指能降低停车高峰期间，停车场内多台AGV 同时停放车辆时产生路径冲突的概率，并使AGV 所行驶的总距离尽可能短，以提升AGV 停车场的停车效率。为此，需构建一个考虑停车路径长度和路径冲突概率的停车位分配模型。

2.1 停车位分配模型

假设有n台车辆等待进入停车场停放，停车场空车位数为m且m≥n，停车场内有k台AGV进行停车作业。建立待停放车辆集合W，如式（1）所示：

建立空闲停车位集合P，如式（2）所示：

建立停车AGV集合A，如式（3）所示：

建立停车位分配方案集合T，如式（4）所示：

式（1）～式（4）中：wi表示第i台待停放车辆，i∈[1,n]；pj表示第j个空闲停车位，j∈[1,m]；aq表示编号为q的AGV，q∈[1,k]；表示AGVaq将待停放车辆wi搬运至分配的空闲停车位pj。

在停车位分配方案中，设待停放车辆wi由AGVaq搬运停放至空闲停车位pj的停车路径为ri。基于停车区域拓扑电子地图，AGV 将待停放车辆由交换等待区搬运至分配停车位的路径规划问题可视为图论问题。根据所建停车场环境地图模型，一条路径可表述为图中的一些节点组合和边组合。因此，车辆wi的停车路径ri可表示为式（5）：

式（5）中：Vi为路径ri所经过的节点集合；Ei为路径ri所经过的节点所连接成的边集合，路径长度为路径经过的所有节点连接成的边的权值累加。

基于此，建立停车位分配模型，如式（6）所示：

式（6）～式（10）中：F(T)为停车位分配模型的目标函数，包括路径长度函数f1(T)和冲突概率函数f2(T)；T为停车位分配方案集合；L(ri)为AGVaq将待停放车辆wi停放至空闲停车位pj的路径长度；ωe为邻接矩阵中所储存的边权值；C(ri)为AGVaq将待停放车辆停放至空闲停车位pj的路径与场内同时存在的其他路径的冲突概率，其计算参考了Zheng 等[1]在2022 年提出的停车路径冲突概率计算方法；Eo为停车场中已在执行的任务路径所经过的边的集合；Ei为当前规划路径所经过的边的集合；其余变量含义同前。

A*算法作为一种图论理论中的智能寻路算法，其在AGV 路径规划及拓扑环境地图中已有大量成熟的应用案例。因此，为了提高停车位分配效率和准确性，本文采用A*算法来解决停车路径搜寻和停车路径长度计算问题。

2.2 算法求解

考虑停车路径长度和停车路径冲突的停车位分配问题是一种组合优化问题，需在有限的停车场道路资源和停车效率之间做出最佳决策，以最大程度地缩短停车路径长度并减小停车路径冲突概率。由于搜索空间较大且优化目标间存在冲突，此类问题较难采用精确算法对真实的应用案例进行求解，因此需设计与问题结构相匹配的启发式算法进行求解。考虑到所提出的停车位分配问题为一个离散优化问题且具有实时性，尤其在停车场高峰期具有频繁的停车任务需求，因此采用收敛速度快、适用性广的非支配排序遗传算法Ⅱ（Non-dominatedSortingGeneticAlgorithm Ⅱ,NSGA-Ⅱ）对所建停车位分配模型进行求解。

NSGA-Ⅱ是一种流行的多目标优化算法，由遗传算法改进而来，其采用快速非支配排序、拥挤距离算法和基因型多样性保留等技术，可有效解决多目标优化问题，准确得到多目标优化问题的Pareto 非劣解集。NSGA-Ⅱ算法流程如图3所示。

图3 NSGA-Ⅱ算法流程图

针对所提出的停车位分配优化模型，对染色体进行实数编码，每条染色体包含2n（n为待停放车辆数）个基因。染色体编码结构如图4所示。染色体中的每个元素都是1 个基因，这些基因组成了染色体，用于描述一个完整的停车位分配方案。在算法迭代过程中，通过对染色体进行交叉和变异操作，可以生成新的停车位分配方案。

图4 染色体编码结构示例

根据图3 所示NSGA-Ⅱ算法流程，按以下步骤对不同任务背景下的停车位分配模型进行求解。

步骤1：初始化初代种群（停车位分配方案）P0，并将进化代数设置为Gen=0。

步骤2：计算种群中的个体适应度值（目标函数值），其中利用A*算法求解交换等待区节点到停车位节点的路径节点和路径距离。

步骤3：对所有个体进行非支配排序，并分为多个等级，其中第一等级为Pareto 前沿解集中的个体。

步骤4：计算每个等级的个体拥挤度，用于区分该等级内个体之间的密集度。

步骤5：在所有等级的个体中，选择最优个体作为精英进入下一代种群。

步骤6：对选择出来的个体进行变异和交叉，生成新的子代个体。

步骤7：将新的子代个体与父代个体合并，形成新的种群P1，Gen=Gen+1，重复步骤2～步骤6，直至达到最大迭代次数。

3 实验仿真与结果分析

基于所建停车区域拓扑环境地图，设计一个仿真实验，验证在不同待停车辆数和不同AGV 数的条件下，停车位分配模型的性能。此外，对本文所提停车位分配模型与常用随机分配方法及基于最短距离分配的方法进行对比实验。实验程序采用Python语言编写，在内存为24.0 GB、频率为2.90 GHz的Inter Core i5-9400F CPU系统上运行。

3.1 实例仿真

为适应实际停车场环境中硬件设置差异和不同城市停车高峰到达率差异，分别设置50、100两个等级的待停车辆数量以及2、3、4 共3 个等级的AGV 数量配置，以验证算法在不同AGV 停车场环境下的适应性和稳定性。

实验中，将NSGA-Ⅱ算法的种群数设置为100，最大迭代次数为200，交叉率为0.6，变异率为0.05。不同待停车辆数量和AGV 数量条件下的停车位分配模型求解结果如图5 所示，其中，图5（a）、（b）为4 台AGV 协同作业下，分别连续停放100 辆及50 辆待停车辆的求解结果；图5（c）、（d）为3 台AGV 协同作业的求解结果；图5（e）、（f）为2台AGV 协同作业的求解结果。在不同的停车分配任务下，NSGA-Ⅱ算法均求得了多样化的帕累托非劣解集。考虑到非劣解集中，总停车距离值差异较小，对AGV 停车场运行效率的影响相对较小，因此，选取非劣解集中路径冲突概率最小的解作为停车位分配模型的最优解。

图5 不同待停车辆和AGV数量下算法求解结果

由于不同背景下多个解集包含的解数量较多，现以4 台AGV 协同作业、停放100 辆待停车辆为例进行分析，其最优停车位分配方案和停车路径如表2所示。

根据表2，待停车辆依次进入交换等待区节点，其中1号待停车辆由1号AGV从交换等待区节点1搬运至停车位节点8，其停车路径r1为1-109-144-143-142-141-140-139-138-137-116-8，可表示为：

根据邻接矩阵信息，停车路径r1长度为28.75 m。

2号待停车辆由2号AGV 从交换等待区节点2搬运至停车位节点54，其停车路径r2可表示为：

根据邻接矩阵信息，停车路径r2长度为29.75 m。

路径r1与r2存在重叠边（109,144），根据环境地图邻接矩阵，其边权值为2.25，即路径r2与r1的停车路径冲突长度为2.25 m，根据式（7），对应的停车路径冲突概率为0.04。以此类推，路径r3与已有停车任务路径没有重叠的路径边，冲突概率为0，与路径r4的冲突概率为0.22。在连续停放100 台待停车辆的运行背景下，停车路径总距离为5 005.88 m，平均路径冲突概率为0.11。

在停车区域配备4 台AGV、停放100 辆待停车辆的任务背景下，算法收敛过程如图6（a）所示，总停车路径函数f1(T)和停车路径冲突概率函数f2(T)收敛到最优解的算法迭代次数均在120 次左右。在停车区域配备4 台AGV、停放50 辆待停车辆的任务背景下，算法收敛过程如图6（b）所示，算法求解连续停放100 辆车和50 辆车两种任务背景下，总耗时均在15 s内，验证了算法在求解维度较高的停车位分配方案时，仍具有较高的实时性。

图6 NSGA-Ⅱ算法迭代效果图

3.2 对比分析

为验证所提出的停车位分配模型及其求解算法的有效性，将其与相关文献[12-14]中采用的基于最短停车路径长度的停车位分配方法和基于空车位随机分配的停车位分配方法进行对比实验。

3 组实验均在停车区域配备4 台AGV，即A=(a1,a2,a3,a4)，待停放车辆数量设置为100 辆，即W=(w1,w2,…,w100)。AGV 按待停放车辆编号顺序依次执行停车任务，由交换等待区车位搬运待停放车辆行驶至分配的停车位后停放车辆，不考虑AGV 空载返回交换等待区车位的过程。对每种停车位分配方法，在上述相同的任务背景下各进行10 次仿真实验。3 种停车位分配方案对比实验结果如表3所示。

表3 3种停车位分配方法对比实验结果

从表3 中的对比实验结果可以看出，本文所提出的考虑路径冲突的停车位分配方法在两个指标上均获得较优的表现。与基于最短停车路径的停车位分配方法相比，考虑路径冲突的停车位分配方法在10次实验中的平均停车路径长度仅高出6.76 m（在实际停车场环境中，这样的停车路径长度差异几乎可以忽略），对应的平均停车路径冲突概率仅为0.14，而最短停车路径方法的停车路径冲突概率则高达0.43。这是因为考虑路径冲突的停车位分配方法模型包含了式（7）所示停车路径长度目标函数，停车位分配过程中在降低停车路径冲突概率的同时，兼顾了连续停车任务的总停车路径长度。此外，最短停车路径方法仅考虑单个停车任务的AGV 行驶路径长度，在为待停放车辆分配停车位的过程中缺乏全局协作，导致AGV的任务路径重叠严重，AGV之间的冲突和拥堵频繁产生；而考虑路径冲突的停车位分配方法在停车位分配过程中，受式（8）所示子目标函数的优化，在连续进行停车位分配的过程中，能选择路径冲突概率更小的停车位，平均路径冲突概率相比最短停车路径方法降低了67.44%，在不影响AGV 行驶路径长度的同时，能有效减少多AGV执行停车任务过程中的冲突和拥堵。

随机分配的停车位分配方法由于停车位分配过程中的随机性，为待停放车辆分配的停车位不会同最短路径方法一样过度集中，停车路径冲突概率比最短停车路径方法低。但考虑路径冲突的停车位分配方法相比而言仍具有明显优势，在10次实验中，考虑路径冲突的停车位分配方法的停车路径冲突概率相比于随机分配方法降低了44.00%，这可能是由于随机分配方法缺乏算法对停车位分配方案进行优化，停车位分配过程中可能产生一些不合理的集中，仍存在较严重的AGV行驶路径重叠。

综上分析，本文所提考虑路径冲突的停车位分配方法，在求解考虑到停车路径长度和停车路径冲突概率的双目标优化模型后，获得的停车位分配方案达到了理想的优化效果，可在连续停车任务中，为待停放车辆分配路径冲突概率低且AGV行驶距离较短的停车位，提升AGV智能停车场的运行效率。

4 结束语

本文针对AGV 智能停车场中考虑停车路径长度及停车路径冲突的停车位分配问题进行研究，采用拓扑图法建立了停车场环境地图模型，提出了一种双目标优化模型，旨在最小化停车路径长度并降低路径冲突概率。为求解停车位分配模型，设计了NSGA-Ⅱ算法对该模型进行求解，并在所建立的停车场环境地图模型中进行了仿真实验。

实验结果表明，所提出的双目标优化模型和算法在不同AGV 数量和停车需求下都能得到多样化的Pareto 非劣解集，且用时较短，满足实时性需求。与传统方法相比，所提方法在减少停车路径长度和路径冲突概率方面表现更优。特别是，路径冲突概率相对于传统方法分别降低了67.44%和44.00%。

研究表明，考虑停车路径冲突的停车位分配模型和NSGA-Ⅱ算法是可行且有效的，且算法用时较短，满足实际应用环境中的实时性需求，可为不同停车需求和AGV 配置条件下提供更优的停车位分配方案。但由于缺乏实际AGV 智能停车场应用数据，研究中未考虑不同车辆停放时间对停车位分配方案的影响。未来研究中将进一步完善模型和算法，考虑更多实际因素，以满足不同应用需求。