基于自动导引车辆的物流分拣系统交通控制策略

李苏琪，朱孔金

(合肥工业大学 汽车与交通工程学院，安徽 合肥 230009)

电子商务的蓬勃发展带动了现代物流业的快速进步，通常物流中心需要对快递包裹按照目的地进行分拣作业，分拣效率是整个物流系统效率的关键，而传统的手工分拣已经远远不能满足日益增长的任务需求。近年来，基于自动导引车辆(automatic guided vehicle， AGV)的自动分拣受到越来越多的关注，这主要得益于AGV系统具有工作效率高、安全性强、人力投入少、出错率低等优势[1-2]。京东物流、阿里巴巴、顺丰快递等企业均在大力发展基于AGV的自动分拣系统。

通常，基于AGV的分拣系统可以建立在离散网格环境下，网格大小与AGV大小和分拣包裹大小相适应，AGV在系统内的运行可以看作是沿着规划路线从一个网格向另一个网格的连续移动过程。AGV的运动和作业，可以是基于中央控制器的集中控制，也可以是基于无线通信的分散控制[3]。对大规模的基于AGV的自动分拣系统而言，系统内AGV的行驶路径规划和交通控制是其核心问题。

路径规划是指在周围环境存在障碍物的情况下，为AGV规划一条安全的从起点到终点的最优路径[4]。Qiu等[5]对AGV系统的路径规划问题进行了详细的讨论。根据路径规划算法的特点，可以大致分为静态路径规划和动态路径规划。静态路径规划是在AGV运动之前规划其行驶路径，并在移动过程中不随系统交通状况的变化而改变；而动态路径规划是指AGV的路径会随着系统内交通状态的变化而更新[6]。动态路径规划中涉及到对动态信息的采集与处理，增加了问题的复杂性，但可为AGV规划出符合真实交通状况的最优路径。

交通控制主要解决系统内AGV运动过程中因运动路线冲突引发的碰撞以及多辆AGV相互干扰而导致的死锁。多AGV运动冲突是指当多辆AGV同时对同一资源进行竞争时，就可能造成潜在的碰撞问题。已有研究中主要采用路径网络设计法、区域控制法或路径规划法来避免碰撞[7]，相对于前两种方法，路径规划方法的系统柔性好，得到了广泛的应用。现有文献中处理死锁问题主要有三种方法：死锁避免、死锁预防以及死锁检测与恢复[8]。其中，死锁避免、死锁预防两种方法不允许出现死锁，通常运行效率较低。而死锁检测与恢复方法[9]允许死锁的产生，一旦出现死锁，系统可以自动检测出来，并通过重新分配资源将系统恢复到无死锁状态。死锁检测与恢复方法在掌握系统全局信息的前提下，简单方便，很容易在集中控制策略下实现。

随着分拣系统规模的增大，由于缺乏适当的交通控制和路径规划方法，还不能很好地解决系统中AGV运动过程中的冲突和死锁等交通问题，尤其是有上百辆AGV同时存在时，无法保证系统的分拣效率和系统稳定性[10]。因此，本文针对大规模的基于AGV的自动分拣系统，在离散网格环境下，借鉴道路交通网中的交叉口不停留规则，采用基于Label Correcting算法的动态路径规划方法，提出了融合交叉口不停留策略和死锁检测与恢复方法的交通控制策略，旨在从系统运行效率和系统性能两方面设计基于AGV的自动分拣系统。

1 系统描述

如图1所示，分拣平台建立在网格环境下，并采用基于中央控制器的集中控制策略。AGV在入口处加载包裹并将获取到的包裹目的地信息上传至中央控制器，中央控制器根据接收到的信息和系统当前的状态为其规划移动路径，并对其发送操作指令，操作指令包括移动、转弯、静止、卸载等。AGV根据接收到的指令在可行的元胞之间移动，直至到达包裹目的地，并完成卸载包裹。系统中每个元胞最多可容纳一辆AGV，网格的大小与AGV的大小相适应。根据元胞功能的不同，系统中元胞可分为7种类型，其中拣货元胞、卸货元胞和出口元胞的类型并不唯一，其同时也属于决策元胞。

注：箭头表示处于该行(列)的元胞所允许的移动方向；红色AGV表示处于载货状态；蓝色AGV表示处于空载状态； 红色虚线为载货AGV可行的移动路径；蓝色虚线为卸载后空AGV离开系统的路径。图1 分拣平台示意图Fig.1 Schematic of the sorting platform

图1中，拣货元胞(CP)为系统的入口，空AGV在该类元胞上加载待分拣包裹，如图1中的元胞(4,13)和(5,13)。卸货元胞(CU)是载货AGV停车卸载包裹的地方，如图1中的元胞(3,3)和(3,5)。储货元胞(CD)是包裹的目的地出口，其下方连接有揽货箱，分拣的包裹从该类元胞掉落到相应的揽货箱内，同一揽货箱内的包裹具有相同的目的地，AGV不允许进入该类元胞，该类元胞相当于障碍物，如图1中的元胞(3,4)、(3,7)、(6,4)和(6,7)。空AGV通过出口元胞(CE)离开系统,如图1中的元胞(1,13)、(2,13)、(4,1)和(5,1)。AGV在交叉口元胞(CJ)上可以通过旋转改变运动方向,如图1中的元胞(1,2)、(1,3)和(1,5)。通常一个完整的交叉口由4个交叉口元胞组成，图1中蓝色实线框所围成的区域即为一个交叉口。无用元胞(CL)为系统中当前未被利用的空间，如图1中的元胞(3,1)、(3,13)、(6,1)和(6,13)，该类元胞可预留用于AGV充电、维修等。决策元胞(CR)是AGV调整行驶状态的地方，AGV只能在该类元胞上对行驶路径进行动态调整，如图1中的元胞(1,1)、(1,13)、(3,3)、(3,12)和(4,13)。

2 数学模型

为仿真分析大规模的物流分拣系统，本文基于有向网络构建AGV运行网络，中央控制器再基于运行网络对所有AGV行驶路径进行规划，并在规定的时间间隔内根据系统状态进行更新。为协调众多AGV同时移动时的交通问题，本文采用交叉口不停留规则对分拣系统内的AGV进行交通控制。交叉口不停留规则要求AGV只能在决策元胞进行决策判断，即停留还是继续行驶，一旦进入交叉口，则AGV除转弯外不允许停留。

2.1 符号和定义

表1列出了本文所用到的符号及其定义。

表1 符号及其定义Table 1 Symbols and their definitions

2.2 运行网络

本文不考虑AGV离开系统后的调度问题，因此需在系统中增加一个虚拟目的地元胞0+作为空载AGV离开系统时的目的地。为了描述AGV的行驶路径，分拣平台环境可由有向网络G=(N,A)表示。其中，N=CR∪CD∪{0+}为网络G的节点构成的集合，A为网络G的弧构成的集合。网络G中的弧分为三类：(1)运行弧。对于任意交叉口，供AGV驶入该交叉口的决策元胞与供AGV驶出该交叉口的决策元胞之间相连构成的弧。(2)卸货弧。卸货元胞与自己对应的储货元胞之间相连构成的弧。(3)驶出弧。任意出口元胞与虚拟元胞0+相连构成的弧。

每条运行弧均是由其路径上的交叉口元胞和决策元胞构成。根据分拣系统中各元胞的可行方向，可以确定网络G中所有可能出现的运行弧和卸货弧的轨迹，图2(a)～(e)列举了AGV在图1中红色实线所围成的区域内所有可能的运行弧和卸货弧的运行轨迹。AGV在上行路线上的运行弧和卸货弧的运行轨迹如图2(f)～(j)所示。图2(e)和(j)为AGV在卸货弧上的运行轨迹，其余图为AGV在运行弧上的运行轨迹。

目前实用的子带合成方案有3种：合成距离包络法[14]、时域合成法和频域合成法[15]。3种方法各有优缺点，合成距离包络法效率最高，但是存在能量溢出，导致距离向形成虚假峰，而且该方法对速度误差敏感。时域合成包含了时移、误差补偿和频谱叠加，效率最低。频域合成在完成子带内和子带间误差补偿以后，只需进行频谱的拼接，具有运算量小、实现简单、性能好等优点[16]。通过以上比较，本文采用的是频域合成法。频域合成其实就是频谱的合成，根据频率步进关系，将各子带信号进行频移，然后进行叠加即可。频域子带合成示意图如图1所示。

图2 AGV在运行弧和卸货弧上的运行轨迹Fig.2 Trajectories of AGV on running and unloading arcs

中央控制器根据AGV运行网络对AGV进行路径规划，得到的路径信息为弧的有序集合，中央控制器将弧的集合转换为元胞的有序集合，AGV根据元胞的有序排列在栅格地图上移动。

网络G中卸货弧的权重和驶出弧的权重均设置为0。由于采用交叉口不停留规则，AGV相当于以自由流速度通过交叉口，但AGV可能会在决策元胞上花费额外的等待时间，基于以上考虑，我们采用公式(1)来确定网络G中运行弧a在时段t的权重：

(1)

2.3 交通控制

图3 移动指令判断流程图Fig.3 Flow chart of movement instruction assessment

移动指令的确定是依据仿真系统当前状态判断的，容易出现判断不充分的情况，因此本文引入最大循环判断次数kmax来进行重复循环判断，最大化调动系统内可移动的AGV。

AGV移动过程中若出现AGV首尾相连，则形成死锁循环，如图1中红色实线所示,处于死锁循环中的AGV相互阻止其他AGV的移动。在交叉口不停留交通控制策略下，AGV死锁只会阻塞处于决策元胞上的AGV。因此，使用死锁检测与恢复算法[12]检测系统中是否出现死锁时，只需检测决策元胞上的AGV状态。选择死锁循环中决策元胞上的某辆AGV，改变其运动方向并重新规划行驶路径。若此时仍未解开死锁，则重新选择死锁循环中的其他AGV，直至解开死锁。

3 结果与讨论

本文仿真实验所采用的分拣平台如图4所示，平台划分为40×55个元胞。平台中均匀设置有12个拣货元胞，204个储货元胞。假设待分拣包裹数量无限大，且其目的地服务均匀分布。仿真实验中还做如下假设：

图4 仿真分拣平台示意图Fig.4 Schematic of the simulation sorting platform

(1) 每辆AGV一次只能携带一个包裹；

(2) AGV的转弯操作需消耗一定的时间，本文中假设为1个单位时间步；

(3) 每个储货元胞两侧各有一个卸货元胞，AGV只能将包裹沿着行进方向的右侧投入储货元胞，且AGV在卸货元胞需要消耗一定的时间进行卸载操作。

3.1 路径更新时间间隔对分拣系统性能影响

AGV从一个元胞运行到相邻元胞所花费的时间称为一个时间步,仿真实验进行10 000个时间步，每种工况重复30次，结果取其平均值，kmax取值为6。图5展示了路径更新间隔时间f对分拣系统性能的影响。

在图5(a)中，系统总投递包裹数量随着f的增大先快速下降而后缓慢下降，同时，相同工况下重复仿真结果的离散程度随着f的增大也在增大。中心控制器根据运行网络当前状态对系统内AGV进行行驶路径更新，f越小，运行网络的权重计算越接近真实的路段情况，相应地，所得到的行驶路径也更为有效。相反，f越大，中心控制器更新计算出的路径，可能因为权重计算的偏差不是系统内的最优路径，这也是图5(b)中系统死锁发生次数随f增大而逐渐增多的原因。此外，随着f的增大，AGV的平均运行速度总体上呈下降趋势。

图5(c)为随着f增大AGV平均旅行时间的变化情况，可以看出，空载AGV的平均旅行时间基本不受f值的影响，载货AGV的平均旅行时间明显随着f值的增大而增加。对于载货AGV，分拣系统内的储货元胞多，拣货元胞少，载货AGV在分拣平台内的旅行时间与拣货元胞到目的储货元胞的距离、路径状态相关，因此受f值影响大。而空载AGV只有一个虚拟的目的元胞，出口元胞多，AGV从卸货点到出口元胞的距离近，因此基本不受f值影响。图5(d)展示了仿真程序运行时间与f的关系。随着f的增加，运行时间先大幅降低，然后趋于稳定。

图5 路径更新间隔对系统性能的影响Fig.5 Impact of the update interval of the path on the performance of the system

3.2 路径更新间隔对分拣系统容量的影响

为深入分析路径更新时间间隔f对分拣系统容纳AGV能力的影响，我们对比分析了两种更新时间间隔下分拣系统内不同状态的AGV数量随时间步的演化情况，如图6所示。图6(a)展示的是分拣系统内容纳的AGV总数量随时间步的变化情况，可以看出，系统很快达到稳定状态，相比较而言，f=300时系统内容纳的AGV数量波动更为明显，这主要是因为死锁出现次数增加。在图6(b)中，载货AGV和空载AGV的数量在f=20时始终高于f=300时，f=300时系统内载货AGV数量的波动最为明显。图6(c)展示的是移动AGV和停止AGV数量随时间步的变化情况，可以发现，不同更新时间间隔下系统内停止AGV的数量基本维持在相同的水平，但移动AGV的数量在f=20时始终高于f=300时的数量。

图6 不同状态AGV数量随时间的变化Fig.6 Number of AGVs in different states changes over time

4 结论

本文在离散网格环境下设计了基于AGV的大规模物流包裹分拣系统，系统采用基于中央控制器的集中控制策略，中央控制器根据运行网络和系统状态，采用Label Correcting算法，对AGV进行行驶路径规划，并定期进行更新。采用交叉口不停留策略对系统内AGV进行交通控制，并实时进行死锁检测与恢复，保证系统能够持续高效运行。

基于所建立的分拣系统，通过开展仿真实验对系统进行了测试，重点分析了更新间隔时间对系统运行性能的影响。结果表明，随着更新间隔时间的增大，虽然仿真运行效率有显著提升，但系统的运行性能呈现下降趋势。更新间隔时间越大，系统规定时间内完成的包裹分拣次数越小，而系统内死锁产生次数和AGV平均旅行时间均越大。因此，在实际应用中，确定更新间隔时间时，需兼顾系统运行时间和系统运行性能两方面的指标。需要说明的是本文中假定包裹的服务目的地是均匀分布的，而实际中会出现不均匀分布的情况，这也是下一步工作中将要解决的问题。