基于离散时空网络的多自动引导车路径规划问题

徐翔斌，李紫阳

(华东交通大学交通运输与物流学院，南昌 330013)

基于智能机器人的订单拣选系统是一种新型的货到人拣选作业模式，相比于传统的人工和自动存储和检索系统(automated storage and retrieval system，AS/RS)拣货系统，其优势在于能够大幅提升拣选效率和准确性，降低运营成本，同时在提高仓库空间利用率以及降低劳动强度等方面也存在明显优势。自动引导车(automatic guided vehicle，AGV)路径规划是智能仓储系统的重要优化方向之一，其核心在于解决多AGV之间的路径冲突。路径冲突问题是指同一时刻不同AGV的运行路线出现交叉或重叠，从而导致系统拥堵，甚至死锁。因此，研究高效可靠的路径规划算法，通过合理的避碰策略将多AGV协调化处理，对保障机器人工作稳定性，提升智能仓储系统的整体性能起着至关重要的作用。

中外学者开展了大量的研究，一般把AGV路径规划方法划分为局部规划和全局规划两种。其中，局部规划也称为动态规划策略，AGV通过传感器实时采集环境信息，根据系统实时状态确定其运行路径。余娜娜等[1]提出改进的差分进化算法，设计动态差分进化策略构建无冲突路径方案；于赫年等[2]根据系统状态信息对AGV规划未来多步的路径，以此多步前瞻的算法来避免冲突；昝新宇等[3]引入多启发式函数和全局信息素更新策略改进蚁群算法，根据多因素综合指标分配各路径信息素量,引导机器人走向。廉胤东等[4]设计了导航、定位和任务信息的图形编码方法，使AGV快速定位和预判，通过改进A*算法实现路径规划和冲突避让策略；张新艳等[5]提出在改进的A*算法中引入时间因子，结合时间窗及优先级策略实现多AGV动态无碰撞路径规划；张硕等[6]建立动态障碍物矩阵，通过基于地图先验知识的粒子群初始化加快求解速度，以克服多AGV路径规划易陷入局部最优值的缺陷；曾庆成等[7]构建了动态路径规划模块，根据导向路段的配置约束确定网络模型，并按照运输网络的状态信息反馈确定最优路径表；动态路径规划能及时应对冲突，但计算量较大且无法得到全局最优解。全局规划的主要思想是当前网络权值不变，综合考虑环境地图所有信息对AGV进行路径规划，因此也称为静态规划策略。王红君等[8]提出爆炸与迁移相结合的策略提升烟花算法的寻优能力，将最短路径换算成蚁群算法的信息素加强值，以解决静态环境下机器人路径规划问题；杨勇生等[9]基于建立多目标混合整数规划模型，考虑软时间窗和惩罚因子的约束对AGV进行路径规划；曹小华等[10]考虑全局路网状态，基于顶点属性和实时位姿信息建立避碰决策的数学模型，优化粒子运行的速度和方向，缩短等待总时长；葛志远等[11]通过改进计算基本蚁群算法启发因子的方法，提出优胜劣汰机制及全局信息素调整方法以解决路径规划中的死锁问题；静态路径规划能得到全局最优解，具有较强的抗干扰性，却难以高效解决路径冲突。结合上述两种方法的优缺点，有学者提出两阶段控制策略求解AGV路径规划问题。陈尔奎等[12]提出双层路径规划思想，通过改进遗传算法进行全局路径规划，再采用改进的人工势场法进行局部动态避障；泰应鹏等[13]结合A*算法，增加时间窗和实时避障功能，对路径规划方法进行了改进；李鑫等[14]在拓扑栅格地图中考虑时间轴构建时空地图模型，加入子节点扩展规则和节点评估函数规划合理路径。

可见，近年来关于AGV拥堵问题的研究，多数是在离线阶段规划路径，在线阶段调整路径解决冲突，无法准确判断AGV在路网中的实时状态信息，缺乏突发情况的应对能力，也增加了研究的复杂性及问题解决的难度。同时，在描述时间依赖的路网问题以及时空关系时，特别是在描述时间窗约束时，一维的物理模型也具有较大的局限性。时空网络[15]是在空间网络的基础上加入时间要素，将一维的物理空间扩展为二维的时空网络，从而可以更加清晰地揭示时间和空间的相互关系，准确刻画路网中AGV实时状态信息。因此，现将时空网络方法引入AGV拥堵问题的研究中，将连续的时间离散化，根据时空路网的实时状态信息，为AGV规划合理高效的拣货路径方案，从而避免冲突及拥堵问题的发生。由于时空网络可以描述物体在时间和空间上的变化，目前已被广泛用于航班调度、铁路列车调配、动态交通分配、车辆路径等诸多领域。蔡涛[16]构建了基于时空网络的资源占用模型，根据列车运行的资源占用特点为列车赋予价值，以整体价值最大化对列车运行问题做出调整；张哲铭等[17]在时空网络中引入状态维度构建了融入乘务规则的时空状态网络，以解决铁路乘务交路规划问题；姜安培等[18]针对机车调配问题提出了非固定牵引区段的两阶段调配方法，在时空-状态网络模型中引进“影子列车”概念解决具有多机组合拆解的机车调配难题；秦进等[19]建立考虑时变需求的基于时空网络的城际高速铁路列车开行方案优化模型，为城际铁路列车开行方案决策提供科学依据；杨森炎等[20]将时空网络扩展状态维度，刻画车辆剩余载重及电量的时空轨迹，在块坐标下降框架下嵌入前向动态规划算法，多维度优化车辆路径和充电策略。时空网络模型已广泛应用于网络流问题，对于解决具有时间约束的路径规划问题具有较好的效果，而在仓储物流系统中，AGV调度问题与交通网络流问题属同类路径规划问题，故现将时空网络引入到仓储物流搬运系统中展开研究。

在现有研究的基础上，现考虑多AGV路径规划系统中存在的拥堵情况，提出规避拥堵的系统优化策略，将多AGV的拣货路径转化为离散时空网络模型下的拣货路径，构建基于离散时空网络下考虑拥堵的多AGV路径优化模型。设计一种将模拟退火算法和时空网络模型相结合的启发式算法，该算法通过生成AGV时空网络模型下的拣货路径，将得到的当前AGV运行路线作为下一AGV拣货路径生成的约束条件，最终得到拣货过程中所有AGV的拣货路径。通过仿真实验证明模型和算法的有效性，并对比分析仓库布局和订单规模对拣货路径的影响。

1 AGV路径优化模型

1.1 问题描述

在智能仓储系统中，为保证把指定货架运往拣货台，需要在环境中建立位置信息相关联的节点，为AGV指明入库点、拣货点及出库点，场景布局如图1所示，每条巷道以5个拣货点为例，AGV接到指派任务后由入库区依次进入仓库，前往指定位置搬运货架后经由出库区到达拣货台[21]。AGV路径规划的目标就是在水平运输路网中规划出一条无冲突、无拥堵和运输时间最短的行驶路径。但是，由于运输任务的不同，AGV将目标货架从仓库作业区运输至拣货台的路径也不相同。在多AGV共同作业模式下，按照既定路径运行，多AGV可能会同时占用同一节点，产生路径冲突。此外，当任务量较多时，同一路段中可能会出现多个AGV同向行驶的情况，使得AGV 完成任务的时间延长，导致系统拥堵甚至死锁，进而影响仓库的作业效率。

如图2所示，在水平运输系统中多AGV作业路径一般存在以下3种冲突类型。

图2 冲突类型Fig.2 Conflict types

(1)赶超冲突。AGV同时到达同一个巷道节点而产生的交叉冲突。

(2)交叉冲突。AGV同向行驶，无负重状态下AGV速度大于负重状态下AGV速度而产生的赶超冲突。

(3)相向冲突。AGV在同一路段中相向行驶，发生冲突，导致道路死锁。

假定系统中各AGV均匀速行驶，不考虑负重对速度的影响，故可将第一种冲突予以避免，仅研究第二、第三种冲突。

1.2 时空网络建立

时空网络建模需要记录路网中各个节点的状态信息，鉴于此，采用栅格表征节点，并在栅格地图基础上拓扑建模，对每个节点赋予相应的时间信息，将一维的物理网络扩展为高维的时空网络。除了构造典型的时空网络旅行弧及时空网络等待弧以外，考虑到仓储系统的实际情况，还构建了附加的时空网络拣货弧，用以建模AGV拣货服务过程，具体操作如下。

(1)建立时空网络节点集合。对于规划时间内的每一时刻t，创建节点(i,t)到时空点集E，i∈N。

(2)构建时空网络旅行弧。创建时空网络旅行弧[i,j,t,t+TT(i,j,t)]∈AT，其中(i,j)∈L，TT(i,j,t)表示AGV在t时刻从节点i出发到达节点j的运行时间。

(3)构建时空网络等待弧。取一对相同节点i，创建时空网络等待弧(i,i,t,t+1)∈AW。

(4)对AGV运行轨迹增加时空网络拣货弧。创建时空网络拣货弧(p,p′,t,t+1)∈AP，p为任务指派的拣货位节点，p′为与p相一致的虚拟节点。

(5)建立时空网络G=(E,A)。其中A=AT+AP+AW是规划时间T下的时空链接集合，(i,j,t,t′)∈A表示在时空网络下的t时刻从节点i出发，并在t′时刻到达节点j。

采用离散化的时空网络结构，便于保证AGV任务要求与时间约束的一致性，同时，在巷道容量恒定的情况下，增加了任务AGV之间的协调性与连续性。

1.3 优化策略设计

提出规避拥堵的系统优化策略主要由4个子系统构成：时空路径生成(space-time create，STC)系统、可行性控制(feasibility control，FC)系统、路网状态(network state，NS)信息表和路径方案评价(scheme evaluate，SE)系统。如图3所示，基本思想如下：路径规划系统根据上述构建的时空路网，在AGV接到任务指派以后，任务信息传输到路径规划系统并由STC实行路径搜索，NS将当前路网状态信息反馈给FC，FC以此为依据对STC所构建的路径进行判定，若当前路径中存在冲突，则将信息反馈给STC，由STC重新进行路径检索；若当前路径合理，则将该路径方案提供给SE进行存储，SE再将路径方案传送到NS进行路网状态信息更新，也就是说，规划完成的每一个AGV运行轨迹，都将成为后续AGV路径生成的约束，最终的运行方案由SE进行对比，得到最优路径指示。

图3 优化策略Fig.3 Optimizing strategy

其中，对AGV路径中存在冲突及拥堵的判定依据如下：①冲突判定：判定相同时刻AGV路径上是否存在节点或路段重叠；②拥堵判定：判定AGV时空网络路径中是否有较多等待弧存在。

2 模型构建

在传统模式下多AGV路径规划问题中，冲突及拥堵导致的AGV等待时间和路径优化策略并不能在一维的物理网络中得到直观的体现，而所构建的时空网络可以将AGVs的运行时间与其运行轨迹相结合，准确刻画出拥堵产生的等待时间以及作业路径的时效性。通过时空网络对存在拥堵问题的仓库作业路径规划问题展开研究，通过构造时空网络，将连续的时间离散化[18]，对AGV的运行、等待以及拣货赋予具有一定跨度的时间区间，故假定AGV在每一段时空网络弧中运行时间、拣货点拣货时间和节点等待时间均为1 s。图4为AGV部分运行路线，设定当前AGV的指派货位编号为101，AGV从始发节点1进入仓库，由于第7秒节点8被占用，第9秒节点14被占用，此时AGV若沿既定路线1→2→8→14→101→15(拣货位节点省略)行驶，则需占用两个等待弧，完成拣货任务耗时17 s，如图5中①所示。若对原路径进行调整，寻找一条无等待或等待较少的运行方案，使任务AGV沿路线1→7→13→14→101→15运行，则可避免在节点8、14处的等待，完成拣货任务耗时15 s，如图5中②所示。

图4 局部路线示意图Fig.4 Local route diagram

图5 路径调整前后对比Fig.5 Path adjustment before and after comparison

2.1 模型假设

在系统优化策略下，建立考虑拥堵因素的路径规划模型，假设如下。

(1)不考虑AGV启停及转向时间。

(2)每个巷道宽度仅允许一台AGV通过。

(3)AGV等待、拣选以及在相邻节点之间运行花费的时间是确定的。

(4)拣货AGV执行的拣选任务在出发前既已确定，且拣选过程中不发生变动。

2.2 模型参数及变量

模型参数定义如表1所示。

表1 路径规划模型参数定义Table 1 Parameter definition of path planning model

决策变量定义如下。

X(i,j,t,t′)(v)：0～1变量，当且仅当机器人v在t时刻从i出发并在t′时刻到达j时取1，否则为0，即车辆v是否选择时空网络弧(i,j,t,t′)。

Y(i,j)(v)：0～1变量，当且仅当机器人v从i到达j时取1，否则为0，即车辆v是否选择物理路径(i,j)。

2.3 模型构建

根据上述条件，构建的基于离散时空网络的路径规划模型如下。

(1)

s.t.

(2)

(3)

i=j∈n

(4)

(5)

(6)

X(i,j,t,t′)(v)+X(k,i,t,t′)(v′)≤1,∀i∈N,

k=j,t

(7)

∀v∈V,(i,j)∈L

(8)

X(i,j,t,t′)(v)∈{0,1}

(9)

Y(i,j)(v)∈{0,1}

(10)

式(1)为所有AGV完成拣货任务的最短时间；式(2)为AGV陆续进入仓库，即单位时间仅允许一辆AGV从起点o进入仓库；式(3)为流平衡约束，表示AGV从起点o出发，并在完成拣货任务后到达终点d；式(4)为任务执行约束，保证每辆AGV必须完成拣货任务；式(5)为巷道容量约束，表示巷道内同一时刻同一位置仅允许一辆AGV占用；式(6)为节点容量约束，表示同一时刻该节点最多被一个AGV占用，避免多AGV之间发生交叉冲突；式(7)为保证在同一路段内，同一时刻不可出现相向行驶的AGV，保证AGV之间不发生相向冲突；式(8)为物理路径和时空路径的一致性约束，即相邻节点所构成的物理链接只对应存在一条时空网络弧；式(9)为0～1变量，当且仅当车辆v在t时刻从节点i出发，在t′时刻到达节点j时取1；式(10)为0～1变量，当且仅当车辆v从节点i出发到达节点j时取1。

3 算法设计

模拟退火(simulated annealing，SA)算法是基于Monte-Carlo迭代求解策略的一种随机寻优算法，该算法通过赋予搜索过程一种时变性且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优。由于SA具有快速收敛到可行解、震荡收敛到最优解的特点，适用于约束条件复杂、难以精确求解的问题模型，设计了一种将传统SA模式转化为时空网络模式的全局优化算法ST-SA对模型进行求解。算法以SA为主框架，将一维物理网络下的可行路径转化为带有时间节点的二维时空路径来计算当前最优解，并将结果返回到主框架，主框架再对物理路径进行调整，直到生成AGV运行路径的最终方案，算法改进部分如图6所示。

图6 ST-SA部分结构示意图Fig.6 Part of ST-SA structure schematic diagram

3.1 解的编码

解的编码方式如图7所示，横向表示不同优先级的任务AGV，纵向表示运行路径中仓库各节点的访问先后顺序，节点1≤i≤37表示各交叉口节点，其中，i=1和i=37分别表示入库点及出库点；i>37时表示巷道内节点，即拣货位点。例如拣货机器人V=1接到指派任务后，从节点1进入仓库，由路网状态信息表NS得知当其在第3秒运行至节点39时，下一目标节点在第4秒被更高优先级拣货AGV占用，则该AGV需要在当前节点等待1 s后继续运行，前往指定货位完成拣货任务，最终从节点37离开仓库。图7反映了整个拣货周期内所有AGV协同完成任务的连续变化关系。

图7 解的表示方式Fig.7 Representation of partial structure diagram of ST-SA

3.2 初始解生成

初始解的生成方式同样遵循了式(6)和式(7)的约束，如图8所示，按照AGV编码从左到右依次递增而其优先级逐渐降低的规则，在时刻t=13 s时，编号为4和5的机器人分别位于节点8和节点92，并且它们的下一目标节点均为14，此时需要为编号为5的AGV在节点92处构造一条时空网络等待弧，待4号机器人通过节点14后再继续运行。同样，当5号机器人在节点95位置拣货时，那么6号机器人需要在当前位置等待，待下一目标节点不被占用后开始运行。

图8 初始解生成方式Fig.8 Initial solution generation

为使初始解满足式(6)和式(7)描述的时空关系，ST-SA算法初始解计算步骤如下。

步骤1初始化仓库场景R、路网状态信息表，生成并整合拣货订单。

步骤2将K个拣货任务分配给K台AGV，并根据任务先后按照由高到低的顺序确定优先级：AGV(1)>AGV(2)>…>AGV(K)，初始化预规划AGV编号k=1。

步骤3生成AGV(K)的一维物理网络下的可行解。

步骤4将AGV(K)的一维物理路径扩展为二维时空网络路径。

步骤4.1若k=1，考虑构建时空网络旅行弧及拣货弧，将AGV(k)的一维物理路径扩展为二维时空网络路径，转至步骤6。

步骤4.2若k>1，按照NS表中路网节点占用情况，确定时空网络旅行弧、等待弧及拣货弧的建立，将AGV(k)的一维物理路径扩展为二维时空网络路径。

步骤5根据NS表中路网状态信息，利用FC判断AGV(k)的时空网络路径是否满足式(6)和式(7)，满足，转至步骤6；不满足，转至步骤3。

步骤6将AGV(k)运行路径方案保存到STR，并把该AGV路径信息记录到NS表中，k=k+1。

步骤7若k≤K，返回步骤 3，若k>K，输出初始可行解STR。

3.3 邻域搜索

提出近优代换(near-optimal replace，NOR)规则来实现邻域解的生成，NOR规则生成新候选解有两种方式。

(1)选择当前路径中的等待节点n1，从与n1位置相关联的节点集(n2,n3,n4)中筛选一个代换节点，将选取的节点与原路径中该等待节点的下一个节点(即拥堵点)进行替换(n1,n2)→(n1,n3)或(n1,n2)→(n1,n4)，如图9(a)所示，使AGV运行方向发生改变。

(2)对于无等待节点但存在多余路段而影响作业效率的路径，其在仓库运行时间过长而并非拥堵所导致的，则需进行优化，剔除无效路段，如图9(b)所示。

图9 邻域搜索及解的修复Fig.9 Neighborhood search and solution repair

由于仓库布局中各节点之间存在位置及时序的关联性，代换产生的新解一般会打破这一关系，产生不合理的解，因此需要进行解的修复，具体分为顺序修复(order repair，OR)和逆序修复(reverse repair，RR),其中OR为位置向前、时间递增方向修复，而RR是位置向后、时间递减方向修复。修复过程如图9(a)、图9(b)所示。例如机器人V=5运行至巷道内部节点n=95时发生等待，需在该巷道对应的巷道口节点n=14处进行方向调整，将节点n=93代换为节点n=20，再以原路径节点n=21为起点搜索最优路段直至两部分完成对接。

ST-SA算法具体步骤如下。

步骤1生成K台AGVS初始运行方案(space-time route，STR)。

步骤2设置约束条件Const，初始温度W，临界温度w，小循环次数q，降温系数m。

步骤3在STR中随机选择AGV(k)路径r，按照NOR规则对路径节点进行替换，记为b1，若该路段中b1与其上一节点b′存在关联性，执行OR完成修复；若与其下一节点b″相关联，则采用RR进行修复。

步骤4确定当前AGV的优先级，清空NS表中该AGV及其优先级以下AGV路网状态信息，再按照NS表将AGV的一维物理路径扩展为二维时空网络路径。

步骤5由FC判断该路径是否满足式(6)和式(7)，若满足，将当前AGV路径方案保存到STR，更新NS表，转至步骤6；若不满足，STR及NS保持不变，返回步骤3。

步骤6生成AGV(k+1)的一维物理网络下的可行解，并根据NS表中路网节点占用情况，确定时空网络旅行弧、等待弧及拣货弧的建立，将AGV(k)的一维物理路径扩展为二维时空网络路径。

步骤7根据NS表中路网状态信息，利用FC判断AGV(k+1)的时空网络路径是否满足式(6)和式(7)，满足，转至步骤8；不满足，返回步骤6。

步骤8将AGV(k+1)路径方案保存到STR，并把该AGV路径信息记录到NS表中，k=k+1。

步骤9若k+1≤K，返回步骤6，若k+1>K，输出优化方案STR′。

步骤10计算AGVS总时间消耗f(STR′)，若f(STR′)

步骤11判断当前温度是否满足条件W

步骤12输出AGVS完成总任务的最小花费时间和此时的最佳路径方案，算法结束。

4 算例分析

为验证模型及算法的有效性和合理性，本文将ST-SA和无规则随机调整(random adjustment，RA)进行对比，RA指随机选择初始方案中的某一路径重新生成，对总时间消耗进行优化，评价算法的指标选择任务完成总时间和平均等待时间优化效果。由于不同的实验场景与仓库中同时作业的AGV数量对拣选效率产生影响，因此对实验因子的设定如表2所示。

表2 实验因子设定Table 2 Setting of experimental factors

算法参数设定如表3所示，运用MATLAB R2019a进行仿真实验，运行环境WIN10、64bit操作系统、8 GB内存。

表3 算法参数设定Table 3 Algorithm parameter setting

因子水平由仓库布局(warehouse layout，WL)、订单数量(order quantity，OQ)及订单规模(order size，OS)决定，因此可将三者的不同组合表示为(WL，OQ，OS)。

4.1 算法收敛性验证

在初始仓库布局、订单数量和订单规模相同的情况下，分别利用ST-SA和CPLEX对因子水平为(3,3,12)和(3,3,20)的最优路径问题进行求解，实验结果如表4所示。

由表4可知，在因子水平为(3,3,12)情况下,ST-SA和CPLEX分别耗时270.43 s和186.93 s，AGVs完成拣货任务的最优时间分别为212 s和207 s；在因子水平为(3,3,20)情况下，ST-SA和CPLEX分别耗时325.96 s和1 743.63 s，AGVs完成拣货任务的最优时间分别为248 s和240 s。对两种不同因子水平的问题求解，ST-SA算法求解的收敛过程与CPLEX的求解结果对比如图10(a)所示。

表4 ST-SA算法收敛过程Table 4 The convergence process of ST-SA algorithm

为保证ST-SA能够在合理时间范围内寻找到近优解，分别选取因子系数组合为(3，3，12)、(3，5，12)、(3，5，20)、(5，5，20)、(5，5，30)和(5，10，30)6种方案进行求解，实验结果如图10(b)所示。

图10 ST-SA收敛性验证Fig.10 ST-SA convergence verification

这表明，对于不同因子水平的最优路径问题，当AGV数量较少，仓库规模较小时，ST-SA能在较短时间内实现平稳收敛，并能找到与CPLEX求解结果相似的解。随着AGV数量的增多和仓库规模的增大，CPLEX的计算时间出现大幅增长，甚至无法在可接受时间范围求得最优解，而ST-SA却可以在合理时间内寻找到近优解，这说明ST-SA在解的质量和计算时间方面符合实际需求。

4.2 实验结果

分别对3种不同的实验场景和9种订单量进行组合，总共27(3×9)种实验场景。ST-SA和RA分别与AGVS按照最短路径完成拣货任务总时间进行比较，并取各实验因子分别在9种不同情况下对AGV路径优化效果的平均值进行比较，其中优化效果为运行总时间的降低值与优化前运行总时间的比值，实验结果如图11所示。

由图11(a)可知，在仓库巷道数量分别为12、20和30的情况下，ST-SA对AGV完成拣货任务总时间的优化效果分别为5.96%、5.20%和4.94%，而RA的优化效果为4.02%、3.33%和3.26%，由此可知，随着仓库巷道数量的持续增加，ST-SA和RA对AGV拣货任务总时间的优化性能减弱，但是ST-SA在3种不同实验场景下的优化效果明显高于RA。

由图11(b)可知，在订单数量分别为3、5和10三种实验场景下，ST-SA对AGV完成拣货任务总时间的优化效果分别为3.23%、5.06%和7.83%，RA的优化效果为2.12%、3.62%和4.87%。所以，随着订单数量的增加，ST-SA与RA对AGV完成拣货任务总时间的优化效果也在不断增加，同时，ST-SA的优化效果高于RA，而且订单数量越多，二者的差距越明显。

由图11(c)可知，当订单规模分别为3、5和10时，ST-SA对AGV完成拣货任务总时间的优化效果分别为3.03%、5.58%和7.51%，RA的优化效果为2.09%、3.43%、5.09%。由此可得，订单规模的不断增加导致了ST-SA与RA对AGV完成拣货任务总时间的优化效果的不断提升，不仅ST-SA的优化效果高于RA，而且订单规模越大，ST-SA的优势也就越明显。

图11 ST-SA和RA实验结果对比Fig.11 Comparison of experimental result of ST-SA and RA

为了进一步突出ST-SA的优势，在不同仓库规模情况下，取ST-SA与RA对AGV运行过程中的等待时间优化效率的平均值进行对比，实验结果如图12所示。

分析图12可知，在AGV运行过程中，ST-SA可将等待时间缩短50%以上，比RA高出20%左右，大幅提升AGV拣货效率。

图12 ST-SA与RA等待时间优化对比Fig.12 Comparison of waiting time optimization between ST-SA and RA

4.3 实际算例实验

为保证上述实验过程及结果的可靠性，采用文献[22]中某电商企业的AGV智能仓库案例进行实验，场景包含100种商品，存放在20个货架上，每个货架上有5个拣货位。该公司某段时间内收到订单总数为100且订单规模在3～6随机分布。本文抽取其中20%订单样本(同一规模的订单数量为5)计算，实验参数为巷道数量20，订单数量5，订单规模3～6，在此实验参数下得到拣货任务总时间优化效率及AGV等待时间优化效率如图13所示。

图13 ST-SA和RA实验结果对比Fig.13 Comparison of experimental result of ST-SA and RA

从计算结果上看，ST-ST较RA有明显改善，在4种不同实验场景下总拣货时间与总等待时间均有所降低，与RA相比，AGV总拣货时间平均降幅2.64%，总等待时间平均降幅22.77%。因此，提出的模型和算法具有一定的全局优化能力，能够避免仓储物流系统中AGV拥堵、系统死锁等问题。

5 总结

针对仓储物流系统中多AGV路径规划问题，提出一种规避拥堵的系统优化策略，利用时空网络模型获取路网实时状态信息，并以此为约束对AGV展开路径搜索，从而避免系统中冲突和拥堵的发生。从AGV系统的运输效率角度，以系统中AGV总耗时最小为目标，建立考虑拥堵的AGV时空路径优化模型，设计了基于系统优化策略的将离散时空网络与模拟退火算法相结合的启发式算法，并通仿真案例对该方法的有效性进行验证。得出如下结论。

(1)时空网络可以有效刻画路网中各节点及路段的实时状态信息，并对AGV运行、等待及拣货过程进行实时跟踪，而系统优化策略能够依据路网状态为AGV规划出较优的运行路径，避免系统中冲突及拥堵情况的发生。

(2)相比于RA，ST-SA速度更快、准确性更高、运算结果与实际情况更为接近。ST-SA能够规划出冲突和拥堵发生频次最少的运行轨迹集合，大幅降低多AGV运输系统耗时，提高物流系统的作业效率，节约成本。