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

交通运输研究第9卷 第4期2023收稿日期：2023-03-30基金项目：国家自然科学基金项目（52272413）作者简介：姚宝珍（1976），女，安徽枞阳人，博士，教授，博士生导师，研究方向为智能交通。E-mail:考虑路径长度与冲突的AGV停车场停车位分配方法姚宝珍，张晋，时彬，崔贺琪，张明恒（大连理工大学 汽车工程学院，辽宁 大连 116024）摘要：为解决自动引导小车（Automated Guided Vehicles,AGV）智能停车场中的停车位分配不合理、多AGV协同作业过程中频繁冲突的问题，针对停车位分配问题进行了研究。根据停车场环境布局，采用拓扑图法建立停车场环境地图模型，并提出一种考虑长度与冲突的停车位分配双目标优化模型，从全局层面减少多台AGV之间的冲突。鉴于模型的多目标特征，设计非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm-,NSGA-）对停车位分配模型进行求解。为验证模型与算法的有效性，进行停车位分配仿真实验，并将所提出的模型与传统的基于最短停车路径长度的停车位分配方法及空停车位随机分配方法进行对比。实验结果表明，NSGA-算法适用于求解停车位分配模型，在不同任务数量和不同AGV配置数量下，算法均能得到多样的Pareto非劣解集；与传统方法相比，所建模型的总停车路径长度指标与基于最短停车路径长度的停车位分配方法相近，路径冲突概率则比基于最短停车路径长度的停车位分配方法和随机分配方法分别降低67.44%和44.00%；在AGV智能停车场高峰期的连续停车任务中，所提出的停车位分配模型和求解算法可寻找到最优停车位分配方案并从全局角度规划AGV的停车路径。关键词：智能停车；自动引导小车；停车位分配；多目标优化；路径规划中图分类号：U491.7文献标识码：A文章编号：2095-9931（2023）04-0083-12Parking Space Allocation in AGV Parking Lots with Path Length andConflict ConsiderationYAO Baozhen,ZHANG Jin,SHI Bin,CUI Heqi,ZHANG Mingheng(School of Automotive Engineering,Dalian University of Technology,Dalian 116024,China)Abstract:In response to the issues of unreasonable parking space allocation and frequent conflicts duringmulti-AGV collaborative operations in AGV parking lots,a study was conducted on parking space alloca-tion within the parking lot.The topological map method was used to establish a parking lot environment交通运输研究TRANSPORT RESEARCH第9卷 第4期Vol.9No.4姚宝珍，张晋，时彬，等.考虑路径长度与冲突的AGV停车场停车位分配方法J.交通运输研究，2023，9（4）：72-83.YAO B,ZHANG J,SHI B,et al.Parking space allocation in AGV parking lots with path length and conflict considerationJ.Transport Research,2023,9(4):72-83.DOI：10.16503/ki.2095-9931.2023.04.00772TRANSPORT RESEARCHVol.9 No.4姚宝珍，等：考虑路径长度与冲突的AGV停车场停车位分配方法map model based on the layout of the parking lot environment,and a bi-objective optimal pattern func-tion for parking space allocation considering length and conflict was proposed to mitigate conflicts be-tween multiple AGVs on a global level.Given the multi-objective characteristics of the model,The NS-GA-algorithm was designed to solve the parking space allocation model.In order to validate theeffectiveness of the model and algorithm,a simulation experiment was conducted on parking spaceallocation,and the proposed model was compared with traditional parking space allocation methodsbased on the shortest parking path length and random allocation of empty parking spaces.The experi-mental 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 quanti-ties and AGV configurations.Compared with traditional methods,the total parking path length indexof the proposed model is similar to this minimum parking path length method,while the path conflictprobability is reduced by 67.44%and 44.00%,respectively,compared to the minimum parking pathlength method and random allocation method.In the continuous parking tasks of AGV intelligentparking lots during peak hours,the proposed parking space allocation model and solving algorithm canfind the optimal parking space allocation scheme and plan the AGV parking path from a global per-spective.Key words:intelligent parking;automatic guided vehicle(AGV);parking space allocation;multi-objective optimization;path planning0引言近年来，我国汽车保有量持续增长，而城市停车位数量增长缓慢，停车难问题日益突出。同时，已有停车设施使用效率低，停车信息不通畅，驾驶者寻找车位过程中的无效巡游导致停车拥堵和大量的尾气排放1-2。为解决城市停车难题，基于自动引导小车（AutomatedGuidedVehicles,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 行驶距离、行驶路径的干扰及冲突，进而为待停车辆73交通运输研究第9卷 第4期2023分配合适的停车位置，可以有效地减少AGV之间的干扰，从而改善停车场内的交通状况，因此关于停车位分配方法的研究逐渐受到重视。关于停车位分配问题的既有研究，大多针对为人类驾驶的车辆分配最佳停车位10-11，如肖玮设计了一种基于多目标点 A*算法的停车场车位路径引导系统，综合考虑用户需求和停车路径长度为待停车辆分配最优停车位12。还有一些研究则从空间利用率、存取效率的角度出发，重点解决立体车库场景下的停车位分配问题，如邢丽娟等采用随机车位分配策略和就近车位分配策略，针对车辆入库和出库、车位利用率、堆垛机运行距离等建立仿真模型13；Li等提出一种基于博弈论的停车位搜索方法，可在比启发式谨慎策略更短的行驶距离内找到可用的停车位14。然而，现有针对停车位分配问题的研究与AGV智能停车场的环境背景区别较大，若直接应用于 AGV 智能停车场环境中，可能导致AGV工作区域过于集中，造成频繁的拥堵和冲突，但其中一些多目标优化的思路和算法仍具启发意义。总体上，现有关于AGV在智能停车场领域应用的研究成果主要针对局部视角中已经产生冲突的规划调度问题，而在全局层面的停车位分配问题研究中忽略了AGV智能停车场环境的特殊性。因此，本文在充分考虑AGV智能停车场环境特征的基础上，将提出一种考虑路径长度与冲突的AGV智能停车场停车位分配模型，将停车路径冲突概率和停车路径长度纳入模型目标函数，以期在全局层面为待停放车辆分配合理的停车位，在AGV执行停车任务前降低多台AGV路径之间产生冲突的概率，同时在局部层面，最小化停车任务的路径长度，进而提升AGV智能停车场运营效率。此外，设计NSGA-算法对所提出的模型进行求解，最后通过仿真实验对模型和算法的有效性进行验证。1停车场环境描述及地图建模1.1AGV智能停车场描述本研究主要针对由现有停车设施改建的AGV智能停车场，车辆到达停放或取车离开停车场的过程采用AGV进行自动化搬运。考虑到取车问题是一个端到端的最短路径规划问题，路径起点及终点均已确定，因此本研究的重点为存取车高峰期的连续停车问题。停车场有多个出入口且在出入口设有交换等待区，驾驶人将待停放车辆停放在交换等待区后离开车辆。停车场控制系统将查询当前停车场状态，为待停放车辆分配一个空闲停车位，随后指派1台空闲AGV将待停放车辆搬运至系统分配的停车位。整个停车过程可分为以下几个步骤。1）车辆驶入停车场。驾驶员将车辆驶入停车场入口，并停放在指定的临时交换等待区域。2）车辆请求停车。当待停车辆到达停车场入口时，向停车场控制系统发送请求停车信号。3）分配停车位。控制系统接收到请求信号后，会根据当前停车场内空余车位的情况，为待停车辆分配1个合适的停车位，通常采用随机分配、最近可用等算法。4）分配任务至AGV。任务系统为当前停车任务分配1台空闲AGV，AGV从交换等待区载运待停车辆。5）导航至停车位。控制系统将停车位的位置信息及规划路径信息发送给AGV，然后AGV根据路径信息自主将待停放车辆搬运至分配的停车位。6）完成停车。AGV到达停车位后，使用机械臂将车辆抬起并移动到停车位后放下车辆，完成停车任务。7）更新AGV停车场状态。停车系统更新车辆停放位置、停车状态及空闲停车位信息，等待接收下一个停车任务。通常，大型停车场包含数百个停车位，并根据布局分为几个区域。为了增加研究结果的可扩展性，假设停车场不同区域的布局结构及车位数量相似。在实际应用中，停车场内一般有多个出入口，不同区域间的车辆交互较少，受郝树运15提出的 AGV停车场布局启发，本文以某 AGV停车场单个停车区为基础展开研究，如图 1所示。74TRANSPORT RESEARCHVol.9 No.4该停车区包含 102个停车位、6个交换等待区车位。停车位尺寸设计为5.5m 2.5m，满足 AGV旋转半径的车道宽度为5.5。交换等待区停车位在实际应用中需考虑人员上下车操作空间，因此应比普通停车位尺寸大，但为便于研究，建模过程中假设交换等待区停车位尺寸设计与普通停车位相同。为简化问题并突出关键环节，对停车环境做如下约束：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所示，其中节点16为交换等待区节点，节点7108为停车位节点，节点109252为路径节点。为使所建停车场电子环境地图直观且便于理解，建模过程中忽略了停车场实际环境中的立柱区域及其他设备空间。节点间的实际距离以权值的形式表示并记录在拓扑地图的邻接矩阵中。部分邻接矩阵信息如表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间无可通行路径。图1AGV智能停车场环境布局姚宝珍，等：考虑路径长度与冲突的AGV停车场停车位分配方法75交通运输研究第9卷 第4期2023表1部分节点拓扑关系数据2829301401411421431441451461471481491501512.53.3752.52.52.511112.52.52.52.52.5节点140141142143144 145 146 147 148 149 150152153154155表1（续）节点140141142143144 145 146 147 148 149 1502停车位分配模型构建及算法求解本研究针对AGV智能停车场，从停车位分配的角度出发，为待停放车辆分配最优停车位，并对停车AGV进行路径规划。最优停车位是指能降低停车高峰期间，停车场内多台AGV同时停放车辆时产生路径冲突的概率，并使AGV所行驶的总距离尽可能短，以提升AGV停车场的停车效率。为此，需构建一个考虑停车路径长度和路径冲突概率的停车位分配模型。2.1停车位分配模型假设有n台车辆等待进入停车场停放，停车图2停车区域拓扑地图建立76TRANSPORT RESEARCHVol.9 No.4场空车位数为m且m n，停车场内有k台 AGV进行停车作业。建立待停放车辆集合 W，如式（1）所示：W=()w1,w2,wii 1,n（1）建立空闲停车位集合P，如式（2）所示：P=(p1,p2,pj)j 1,m（2）建立停车AGV集合A，如式（3）所示：A=(a1,a2,aq)q 1,k（3）建 立 停 车 位 分 配 方 案 集 合 T，如 式（4）所示：T=tqij（4）式（1）式（4）中：wi表示第i台待停放车辆，i 1,n；pj表示第j个空闲停车位，j 1,m；aq表示编号为q的 AGV，q 1,k；tqij表示 AGVaq将待停放车辆wi搬运至分配的空闲停车位pj。在停车位分配方案中，设待停放车辆wi由AGVaq搬运停放至空闲停车位pj的停车路径为ri。基于停车区域拓扑电子地图，AGV将待停放车辆由交换等待区搬运至分配停车位的路径规划问题可视为图论问题。根据所建停车场环境地图模型，一条路径可表述为图中的一些节点组合和边组 合。因 此，车 辆wi的 停 车 路 径ri可 表 示为式（5）：ri=Vi,Ei（5）式（5）中：Vi为路径ri所经过的节点集合；Ei为路径ri所经过的节点所连接成的边集合，路径长度为路径经过的所有节点连接成的边的权值累加。基于此，建立停车位分配模型，如式（6）所示：min F(T)=(f1(T),f2(T)（6）其中：f1(T)=i=1nL(ri)（7）f2(T)=i=1nC(ri)n-1（8）L()ri=e Eie（9）C(ri)=o=i-k+1i-1e (Ei Eo)eo=i-k+1iL(ri)（10）式（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-是一种流行的多目标优化算法，由遗传算法改进而来，其采用快速非支配排序、拥挤距离算法和基因型多样性保留等技术，可有效解姚宝珍，等：考虑路径长度与冲突的AGV停车场停车位分配方法77交通运输研究第9卷 第4期2023决多目标优化问题，准确得到多目标优化问题的Pareto 非劣解集。NSGA-算法流程如图3所示。针对所提出的停车位分配优化模型，对染色体进行实数编码，每条染色体包含2n（n为待停放车辆数）个基因。染色体编码结构如图4所示。染色体中的每个元素都是1个基因，这些基因组成了染色体，用于描述一个完整的停车位分配方案。在算法迭代过程中，通过对染色体进行交叉和变异操作，可以生成新的停车位分配方案。根据图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数量条件下初始化种群，Gen=0开始非支配排序选择、交叉、变异生成一代子群进化代数 Gen+1选择、交叉、变异父代子代合并非支配排序计算个体拥挤度精英策略选择优胜个体入新的父代种群判断是否Genmax Gen输出Pareto非劣解集结束否是图3NSGA-算法流程图停车位节点编号等待区节点编号图4染色体编码结构示例78TRANSPORT RESEARCHVol.9 No.4的停车位分配模型求解结果如图 5所示，其中，图5（a）、（b）为4台AGV协同作业下，分别连续停放100辆及50辆待停车辆的求解结果；图5（c）、（d）为3台AGV协同作业的求解结果；图5（e）、（f）为2台AGV协同作业的求解结果。在不同的停车分配任务下，NSGA-算法均求得了多样化的帕累托非劣解集。考虑到非劣解集中，总停车距离值差异较小，对AGV停车场运行效率的影响相对较小，因此，选取非劣解集中路径冲突概率最小的解作为停车位分配模型的最优解。帕累托非劣解被支配解帕累托非劣解被支配解帕累托非劣解被支配解帕累托非劣解被支配解帕累托非劣解被支配解帕累托非劣解被支配解0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18停车路径冲突概率0.080.100.120.140.160.18停车路径冲突概率（a）4台AGV、100辆待停车辆0.080.100.120.140.16停车路径冲突概率0.080.100.120.14停车路径冲突概率0.050.06 0.060.07 0.07 0.070.080.04 0.05 0.06 0.07 0.08 0.09 0.10 0.11停车路径冲突概率停车路径冲突概率5 1805 1605 1405 1205 1005 0805 0605 0405 020停车路径长度/m2 4002 3002 2002 1002 000停车路径长度/m5 2505 2005 1505 1005 0502 4002 3002 2002 100停车路径长度/m停车路径长度/m5 2005 1755 1505 1255 1005 0755 0505 0255 000停车路径长度/m2 5002 4002 3002 2002 100停车路径长度/m图5不同待停车辆和AGV数量下算法求解结果（b）4台AGV、50辆待停车辆（c）3台AGV、100辆待停车辆（d）3台AGV、50辆待停车辆（e）2台AGV、100辆待停车辆（f）2台AGV、50辆待停车辆由于不同背景下多个解集包含的解数量较多，现以4台AGV协同作业、停放100辆待停车辆为例进行分析，其最优停车位分配方案和停车路径如表2所示。根据表2，待停车辆依次进入交换等待区节点，其中1号待停车辆由1号AGV从交换等待区节点1搬运至停车位节点8，其停车路径r1为1-109-144-143-142-141-140-139-138-137-116-8，可表示为：r1=V1,E1V1=1,109,144,143,142,141,140,139,138,137,116,8姚宝珍，等：考虑路径长度与冲突的AGV停车场停车位分配方法79交通运输研究第9卷 第4期2023E1=(1,109),(109,144),(144,143),(143,142),(142,141),(140,139),(139,138),(138,137),(137,116),(116,8)根据邻接矩阵信息，停车路径r1长度为28.75 m。2号待停车辆由2号AGV从交换等待区节点2搬运至停车位节点54，其停车路径r2可表示为：r2=V2,E2V2=2,110,109,144,145,180,179,178,54）E2=(2,110),(110,109),(109,144),(144,145),(145,180),(180,179),(179,178),(178,54)根据邻接矩阵信息，停车路径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内，验证了算法在求解维度较高的停车位分配方案时，仍具有较高的实时性。待停车辆12345678910979899100最优停车路径1-109-144-143-142-141-140-139-138-137-116-82-110-109-144-145-180-179-178-543-111-142-304-112-141-140-139-138-137-136-135-134-133-132-131-130-129-128-127-195-113-140-139-138-151-150-149-148-147-316-114-139-138-151-174-187-186-185-212-761-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-225-832-110-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-243-242-241-240-239-93-111-142-141-140-139-138-151-174-187-210-223-246-245-244-243-242-241-240-239-238-944-112-141-140-139-138-151-150-149-148-321-109-144-145-180-181-216-217-252-251-250-249-248-247-246-245-244-243-242-241-240-239-238-231-872-110-109-144-143-142-141-293-111-142-141-140-139-138-137-136-135-134-133-132-131-122-121-134-112-141-140-139-138-151-174-187-210-223-246-245-244-243-242-241-240-239-238-237-93停车路径长度/m28.7529.7510.1245.1236.1245.2572.1283.7579.8836.1287.1219.0042.3879.88总值5 005.88停车路径冲突概率0.000.040.000.220.070.050.000.010.040.060.020.050.140.17均值0.11表2NSGA-算法求解4台AGV、100辆待停车辆背景下的停车位分配方案80TRANSPORT RESEARCHVol.9 No.43.2对比分析为验证所提出的停车位分配模型及其求解算法的有效性，将其与相关文献12-14中采用的基于最短停车路径长度的停车位分配方法和基于空车位随机分配的停车位分配方法进行对比实验。3组实验均在停车区域配备4台AGV，即A=(a1,a2,a3,a4)，待停放车辆数量设置为100辆，即W=(w1,w2,w100)。AGV 按待停放车辆编号顺序依次执行停车任务，由交换等待区车位搬运待停放车辆行驶至分配的停车位后停放车辆，不考虑AGV空载返回交换等待区车位的过程。对每种停车位分配方法，在上述相同的任务背景下各进行10次仿真实验。3种停车位分配方案对比实验结果如表3所示。从表3中的对比实验结果可以看出，本文所提出的考虑路径冲突的停车位分配方法在两个指标上均获得较优的表现。与基于最短停车路径的停车位分配方法相比，考虑路径冲突的停车位分配方法在10次实验中的平均停车路径长度仅高出停车拥堵概率总停车距离迭代次数/次0255075100125150175200（a）4台AGV、停放100辆待停车辆5 0705 0605 0505 0405 0305 0200.160.150.140.130.120.11停车路径长度/m停车路径冲突概率停车拥堵概率总停车距离2 3502 3002 2502 2002 1502 1002 0500.150.140.130.120.110.100.09停车路径长度/m停车路径冲突概率迭代次数/次0255075100125150175200（b）4台AGV、停放50辆待停车辆图6NSGA-算法迭代效果图实验编号12345678910平均值考虑路径冲突的停车位分配方法停车路径长度/m5 496.755 523.505 498.555 492.255 504.555 501.255 492.555 513.255 493.505 499.255 501.54停车路径冲突概率0.100.150.120.180.110.160.130.150.180.200.14基于最短停车路径的停车位分配方法停车路径长度/m5 490.505 493.755 497.255 505.255 493.505 490.755 492.505 490.505 491.005 502.755 494.78停车路径冲突概率0.380.470.420.400.480.430.390.450.410.460.43空车位随机分配的停车位分配方法停车路径长度/m5 498.755 500.255 498.755 492.005 507.255 512.005 497.505 501.755 492.255 497.505 499.80停车路径冲突概率0.240.270.200.300.290.250.190.230.280.240.25表33种停车位分配方法对比实验结果6.76 m（在实际停车场环境中，这样的停车路径长度差异几乎可以忽略），对应的平均停车路径冲突概率仅为0.14，而最短停车路径方法的停车路径冲突概率则高达0.43。这是因为考虑路径冲突的停车位分配方法模型包含了式（7）所示停车路径长度目标函数，停车位分配过程中在降低停车路径冲突概率的同时，兼顾了连续停车任务的总停车路径长度。此外，最短停车路径方法仅姚宝珍，等：考虑路径长度与冲突的AGV停车场停车位分配方法81交通运输研究第9卷 第4期2023考虑单个停车任务的AGV行驶路径长度，在为待停放车辆分配停车位的过程中缺乏全局协作，导致AGV的任务路径重叠严重，AGV之间的冲突和拥堵频繁产生；而考虑路径冲突的停车位分配方法在停车位分配过程中，受式（8）所示子目标函数的优化，在连续进行停车位分配的过程中，能选择路径冲突概率更小的停车位，平均路径冲突概率相比最短停车路径方法降低了67.44%，在不影响AGV行驶路径长度的同时，能有效减少多AGV执行停车任务过程中的冲突和拥堵。随机分配的停车位分配方法由于停车位分配过程中的随机性，为待停放车辆分配的停车位不会同最短路径方法一样过度集中，停车路径冲突概率比最短停车路径方法低。但考虑路径冲突的停车位分配方法相比而言仍具有明显优势，在10次实验中，考虑路径冲突的停车位分配方法的停车路径冲突概率相比于随机分配方法降低了44.00%，这可能是由于随机分配方法缺乏算法对停车位分配方案进行优化，停车位分配过程中可能产生一些不合理的集中，仍存在较严重的AGV行驶路径重叠。综上分析，本文所提考虑路径冲突的停车位分配方法，在求解考虑到停车路径长度和停车路径冲突概率的双目标优化模型后，获得的停车位分配方案达到了理想的优化效果，可在连续停车任务中，为待停放车辆分配路径冲突概率低且AGV行驶距离较短的停车位，提升AGV智能停车场的运行效率。4结束语本文针对AGV智能停车场中考虑停车路径长度及停车路径冲突的停车位分配问题进行研究，采用拓扑图法建立了停车场环境地图模型，提出了一种双目标优化模型，旨在最小化停车路径长度