Transport Research >

2023 , Vol. 9 >Issue 4: 72 - 83

DOI: https://doi.org/10.16503/j.cnki.2095-9931.2023.04.007

Theory & Method

Parking Space Allocation in AGV Parking Lots with Path Length and Conflict Consideration

  • YAO Baozhen ,
  • ZHANG Jin ,
  • SHI Bin ,
  • CUI Heqi ,
  • ZHANG Mingheng
Expand
  • School of Automotive Engineering, Dalian University of Technology, Dalian 116024, China

Received date: 2023-03-30

  Online published: 2023-09-22

Fold

Abstract

In response to the issues of unreasonable parking space allocation and frequent conflicts during multi-AGV collaborative operations in AGV parking lots, a study was conducted on parking space allocation within the parking lot. The topological map method was used to establish a parking lot environment map model based on the layout of the parking lot environment, and a bi-objective optimal pattern function for parking space allocation considering length and conflict was proposed to mitigate conflicts between multiple AGVs on a global level. Given the multi-objective characteristics of the model,The NSGA-Ⅱ algorithm was designed to solve the parking space allocation model. In order to validate the effectiveness of the model and algorithm, a simulation experiment was conducted on parking space allocation, and the proposed model was compared with traditional parking space allocation methods based on the shortest parking path length and random allocation of empty parking spaces. The experimental results show that the NSGA-Ⅱ algorithm is suitable for solving parking space allocation models, and the algorithm can obtain a diverse set of Pareto non inferior solutions under different task quantities and AGV configurations. Compared with traditional methods, the total parking path length index of the proposed model is similar to this minimum parking path length method, while the path conflict probability is reduced by 67.44% and 44.00%, respectively, compared to the minimum parking path length method and random allocation method. In the continuous parking tasks of AGV intelligent parking lots during peak hours, the proposed parking space allocation model and solving algorithm can find the optimal parking space allocation scheme and plan the AGV parking path from a global perspective.

Key words： intelligent parking; automatic guided vehicle (AGV); parking space allocation; multi-objective optimization; path planning

Cite this article

YAO Baozhen , ZHANG Jin , SHI Bin , CUI Heqi , ZHANG Mingheng . Parking Space Allocation in AGV Parking Lots with Path Length and Conflict Consideration[J]. Transport Research, 2023 , 9(4) : 72 -83 . DOI: 10.16503/j.cnki.2095-9931.2023.04.007

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 部分节点拓扑关系数据
节点 140 141 142 143 144 145 146 147 148 149 150
28 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
29 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
30 ∞ ∞ 3.375 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
140 ∞ 2.5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
141 ∞ ∞ 2.5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
142 ∞ ∞ ∞ 2.5 ∞ ∞ ∞ ∞ ∞ ∞ ∞
143 ∞ ∞ ∞ ∞ 2.5 ∞ 11 ∞ ∞ ∞ ∞
144 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
145 ∞ ∞ ∞ ∞ 11 ∞ 2.5 ∞ ∞ ∞ ∞
146 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2.5 ∞ ∞ ∞
147 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2.5 ∞ ∞
148 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2.5 ∞
149 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2.5
150 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
151 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
152 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
153 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
154 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
155 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

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

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

2.1 停车位分配模型

假设有 n台车辆等待进入停车场停放，停车场空车位数为 m且 m ≥ n，停车场内有 k台AGV进行停车作业。建立待停放车辆集合W，如式（1）所示：
W = w 1 ,   w 2 , ⋯ ,   w i           i ∈ [ 1 ,   n ]
建立空闲停车位集合P，如式（2）所示：
P = ( p 1 ,   p 2 , ⋯ ,   p j )           j ∈ [ 1 ,   m ]
建立停车AGV集合A，如式（3）所示：
A = ( a 1 ,   a 2 , ⋯ ,   a q )           q ∈ [ 1 ,   k ]
建立停车位分配方案集合T，如式（4）所示：
T = t i j q
式（1）~式（4）中： w i表示第 i台待停放车辆， i ∈ [ 1 ,   n ]； p j表示第 j个空闲停车位， j ∈ [ 1 ,   m ]； a q表示编号为 q的AGV， q ∈ [ 1 ,   k ]； t i j q表示AGV a q将待停放车辆 w i搬运至分配的空闲停车位 p j。
在停车位分配方案中，设待停放车辆 w i由AGV a q搬运停放至空闲停车位 p j的停车路径为 r i。基于停车区域拓扑电子地图，AGV将待停放车辆由交换等待区搬运至分配停车位的路径规划问题可视为图论问题。根据所建停车场环境地图模型，一条路径可表述为图中的一些节点组合和边组合。因此，车辆 w i的停车路径 r i可表示为式（5）：
r i = V i ,   E i
式（5）中： V i为路径 r i所经过的节点集合； E i为路径 r i所经过的节点所连接成的边集合，路径长度为路径经过的所有节点连接成的边的权值累加。
基于此，建立停车位分配模型，如式（6）所示：
m i n   F ( T ) = ( f 1 ( T ) ,     f 2 ( T ) )
其中：
f 1 ( T ) = ∑ i = 1 n L ( r i )
f 2 ( T ) = ∑ i = 1 n C ( r i ) n - 1
L r i = ∑ e ∈ E i ω e
C ( r i ) = ∑ o = i - k + 1 i - 1   ∑ e ∈ ( E i ⋂ E o ) ω e ∑ o = i - k + 1 i L ( r i )
式（6）~式（10）中： F ( T )为停车位分配模型的目标函数，包括路径长度函数 f 1 ( T )和冲突概率函数 f 2 ( T )； T为停车位分配方案集合； L ( r i )为AGV a q 将待停放车辆 w i停放至空闲停车位 p j的路径长度； ω e为邻接矩阵中所储存的边权值； C ( r i )为AGV a q将待停放车辆停放至空闲停车位 p j的路径与场内同时存在的其他路径的冲突概率，其计算参考了Zheng等[1]在2022年提出的停车路径冲突概率计算方法； E o为停车场中已在执行的任务路径所经过的边的集合； E i为当前规划路径所经过的边的集合；其余变量含义同前。
A*算法作为一种图论理论中的智能寻路算法，其在AGV路径规划及拓扑环境地图中已有大量成熟的应用案例。因此，为了提高停车位分配效率和准确性，本文采用A*算法来解决停车路径搜寻和停车路径长度计算问题。

2.2 算法求解

考虑停车路径长度和停车路径冲突的停车位分配问题是一种组合优化问题，需在有限的停车场道路资源和停车效率之间做出最佳决策，以最大程度地缩短停车路径长度并减小停车路径冲突概率。由于搜索空间较大且优化目标间存在冲突，此类问题较难采用精确算法对真实的应用案例进行求解，因此需设计与问题结构相匹配的启发式算法进行求解。考虑到所提出的停车位分配问题为一个离散优化问题且具有实时性，尤其在停车场高峰期具有频繁的停车任务需求，因此采用收敛速度快、适用性广的非支配排序遗传算法Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ, 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 NSGA-Ⅱ算法求解4台AGV、100辆待停车辆背景下的停车位分配方案
待停车辆 最优停车路径 停车路径长度/m 停车路径冲突概率
1 1-109-144-143-142-141-140-139-138-137-116-8 28.75 0.00
2 2-110-109-144-145-180-179-178-54 29.75 0.04
3 3-111-142-30 10.12 0.00
4 4-112-141-140-139-138-137-136-135-134-133-132-131-130-129-128-127-19 45.12 0.22
5 5-113-140-139-138-151-150-149-148-147-31 36.12 0.07
6 6-114-139-138-151-174-187-186-185-212-76 45.25 0.05
7 1-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-225-83 72.12 0.00
8 2-110-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-243-242-241-240-239-9 83.75 0.01
9 3-111-142-141-140-139-138-151-174-187-210-223-246-245-244-243-242-241-240-239-238-94 79.88 0.04
10 4-112-141-140-139-138-151-150-149-148-32 36.12 0.06
⋮ ⋮ ⋮ ⋮
97 1-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-243-242-241-240-239-238-231-87 87.12 0.02
98 2-110-109-144-143-142-141-29 19.00 0.05
99 3-111-142-141-140-139-138-137-136-135-134-133-132-131-122-121-13 42.38 0.14
100 4-112-141-140-139-138-151-174-187-210-223-246-245-244-243-242-241-240-239-238-237-93 79.88 0.17
总值5 005.88 均值0.11
根据表2，待停车辆依次进入交换等待区节点，其中1号待停车辆由1号AGV从交换等待区节点1搬运至停车位节点8，其停车路径 r 1为1-109-144-143-142-141-140-139-138-137-116-8，可表示为：
r 1 = { V 1 ,   E 1 }
V 1 = { 1 ,   109 ,   144 ,   143 ,   142 ,   141 ,   140 ,   139 ,   138 ,   137 ,   116 ,   8 }
E 1 = { ( 1 ,   109 ) ,   ( 109 ,   144 ) ,   ( 144 ,   143 ) ,   ( 143 ,   142 ) , ( 142 ,   141 ) ,   ( 140 ,   139 ) ,   ( 139 ,   138 ) ,   ( 138 ,   137 ) ,   ( 137 ,   116 ) , ( 116 ,   8 ) }
根据邻接矩阵信息，停车路径 r 1长度为28.75 m。
2号待停车辆由2号AGV从交换等待区节点2搬运至停车位节点54，其停车路径 r 2可表示为：
r 2 = { V 2 ,   E 2 }
V 2 = { 2 ,   110 ,   109 ,   144 ,   145 ,   180 ,   179 ,   178 ,   54 } ）
E 2 = { ( 2 ,   110 ) ,   ( 110 ,   109 ) ,   ( 109 ,   144 ) ,   ( 144 ,   145 ) ,   ( 145 ,   180 ) ,   ( 180 ,   179 ) ,   ( 179 ,   178 ) ,   ( 178 ,   54 ) }
根据邻接矩阵信息，停车路径 r 2长度为29.75 m。
路径 r 1与 r 2存在重叠边（109,144），根据环境地图邻接矩阵，其边权值为2.25，即路径 r 2与 r 1的停车路径冲突长度为2.25 m，根据式（7），对应的停车路径冲突概率为0.04。以此类推，路径 r 3与已有停车任务路径没有重叠的路径边，冲突概率为0，与路径 r 4的冲突概率为0.22。在连续停放100台待停车辆的运行背景下，停车路径总距离为5 005.88 m，平均路径冲突概率为0.11。
在停车区域配备4台AGV、停放100辆待停车辆的任务背景下，算法收敛过程如图6（a）所示，总停车路径函数 f 1 ( T )和停车路径冲突概率函数 f 2 ( T )收敛到最优解的算法迭代次数均在120次左右。在停车区域配备4台AGV、停放50辆待停车辆的任务背景下，算法收敛过程如图6（b）所示，算法求解连续停放100辆车和50辆车两种任务背景下，总耗时均在15 s内，验证了算法在求解维度较高的停车位分配方案时，仍具有较高的实时性。
图6 NSGA-Ⅱ算法迭代效果图

3.2 对比分析

为验证所提出的停车位分配模型及其求解算法的有效性，将其与相关文献[12⇓-14]中采用的基于最短停车路径长度的停车位分配方法和基于空车位随机分配的停车位分配方法进行对比实验。
3组实验均在停车区域配备4台AGV，即 A = ( a 1 ,   a 2 ,   a 3 ,   a 4 )，待停放车辆数量设置为100辆，即 W = ( w 1 ,   w 2 ,   ⋯ ,   w 100 )。AGV按待停放车辆编号顺序依次执行停车任务，由交换等待区车位搬运待停放车辆行驶至分配的停车位后停放车辆，不考虑AGV空载返回交换等待区车位的过程。对每种停车位分配方法，在上述相同的任务背景下各进行10次仿真实验。3种停车位分配方案对比实验结果如表3所示。
表3 3种停车位分配方法对比实验结果
实验
编号		 考虑路径冲突的停车位分配方法 基于最短停车路径的停车位分配方法 空车位随机分配的停车位分配方法
停车路径长度/m 停车路径冲突概率 停车路径长度/m 停车路径冲突概率 停车路径长度/m 停车路径冲突概率
1 5 496.75 0.10 5 490.50 0.38 5 498.75 0.24
2 5 523.50 0.15 5 493.75 0.47 5 500.25 0.27
3 5 498.55 0.12 5 497.25 0.42 5 498.75 0.20
4 5 492.25 0.18 5 505.25 0.40 5 492.00 0.30
5 5 504.55 0.11 5 493.50 0.48 5 507.25 0.29
6 5 501.25 0.16 5 490.75 0.43 5 512.00 0.25
7 5 492.55 0.13 5 492.50 0.39 5 497.50 0.19
8 5 513.25 0.15 5 490.50 0.45 5 501.75 0.23
9 5 493.50 0.18 5 491.00 0.41 5 492.25 0.28
10 5 499.25 0.20 5 502.75 0.46 5 497.50 0.24
平均值 5 501.54 0.14 5 494.78 0.43 5 499.80 0.25
从表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智能停车场应用数据，研究中未考虑不同车辆停放时间对停车位分配方案的影响。未来研究中将进一步完善模型和算法，考虑更多实际因素，以满足不同应用需求。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
ZHENG X, ZHENG R, NING S. Parking space allocation model of intelligent parking lot under peak demand[C]// Proceedings of the 2022 IEEE 25th International Conference on Computer Supported Cooperative Work in Design. Hangzhou: IEEE, 2022: 543-547.

[2]
张金梦. 智能停车场短时泊车位预测的研究[D]. 重庆: 重庆大学, 2017.

[3]
李全勇, 李波, 张瑞, 等. 基于改进Dijkstra算法的AGV路径规划研究[J]. 机械工程与自动化, 2021(1):23-25.

[4]
刘二辉, 姚锡凡. 基于改进遗传算法的自动导引小车路径规划及其实现平台[J]. 计算机集成制造系统, 2017, 23(3):465-472.

[5]
王家君. 基于泊车AGV的停车场调度策略的研究[D]. 青岛: 山东科技大学, 2020.

[6]
XU W, WANG Q, YU M, et al. Path planning for multi-AGV systems based on two-stage scheduling[J]. International Journal of Performability Engineering, 2017, 13(8): 1347.

[7]
BAI Y, DING X, HU D, et al. Research on dynamic path planning of multi-AGVs based on reinforcement learning[J]. Applied Sciences, 2022, 12(16): 8166.

[8]
UMAR U A, ARIFFIN M K A, ISMAIL N, et al. Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment[J]. The International Journal of Advanced Manufacturing Technology, 2015, 81(9-12): 2123-2141.

[9]
SUN X, ZHAO Y, SHEN S, et al. Scheduling multiple AGVs with dynamic time-windows for smart indoor parking lot[C]// 2018 IEEE 22nd International Conference on Computer Supported Cooperative Work in Design (CSCWD). Nanjing: IEEE, 2018: 864-868.

[10]
TRAN THI KIM O, TRAN N H, PHAM C, et al. Parking assignment: Minimizing parking expenses and balancing parking demand among multiple parking lots[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(3): 1320-1331.

[11]
GENG Y, CASSANDRAS C G. New "smart parking" system based on resource allocation and reservations[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(3): 1129-1139.

[12]
张铁楠, 肖玮, 张磊, 等. 基于多目标点A*算法的停车场车位路径引导系统设计[J]. 计算机与现代化, 2020, 298(6):40-45.

[13]
邢丽娟, 李建国. 立体车库车位分配仿真与分析[J]. 铁路计算机应用, 2011, 20(10):32-34.

[14]
LI Y, LI N, TSENG H E, et al. A game theoretic app-roach for parking spot search with limited parking lot information[C]// 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). Rhodes: IEEE, 2020: 1-6.

[15]
郝树运. AGV智能停车库路径规划与布局优化研究[D]. 北京: 北京交通大学, 2019.

Options
Outlines

/

〈 〉