李苏琪 朱孔金
摘 要：使用自動导引小车（Automatic Guided Vehicle，AGV）运输包裹能够提高物流分拣的效率，但当系统规模较大时，如何保证分拣系统仍然具有较高的分拣效率这一问题还没有得到很好的解决。该文在离散网格环境下设计基于AGV的物流分拣系统，并构建了多AGV分拣系统仿真模型。模型中使用改进标号修正法结合路径更新时间间隔对AGV进行动态路径规划，制定AGV移动规则并辅以死锁检测和恢复算法来解决系统死锁问题。仿真结果表明，该模型能够适用于大规模物流分拣。针对该文分拣场景，系统容纳的AGV数量应控制在260辆以下。且当系统容量大于200时，较小的路径更新时间间隔对分拣系统效率的作用明显优于较大的路径更新时间间隔。
关键词：物流分拣 AGV 路径规划 分拣效率
中图分类号：TP27 文献标识码：A文章编号：1672-3791（2021）05（a）-0001-05
Abstract： Using AGV to transport parcels can improve the efficiency of logistics sorting， but when the system scale is large， how to ensure the sorting system still has a high sorting efficiency has not been solved. In this paper， the multi-AGV logistics sorting system is designed in the discrete grid environment， and the simulation model of multi-AGV sorting system is built. In the model， the dynamic path planning of AGV is carried out by using the improved label correcting method combined with the path update time interval. The AGV movement rule is formulated， and the deadlock detection and recovery algorithm is supplemented to solve the system deadlock problem. The simulation results show that the model can be applied to large-scale logistics sorting. In this paper， the number of AGV can be accommodated in the system is about 260. When the system capacity is more than 200， the smaller path update time interval has a better effect on the efficiency of sorting system than the larger path update time interval.
Key Words： Logistics sorting; AGV; Path planning; Sorting efficiency
随着电商的蓬勃发展，人们的购物方式已经发生了很大的改变，随之而来的是大量的物流包裹亟待运输。物流分拣中心是整个物流过程的运输瓶颈所在，其分拣效率对于物流行业的整体水平影响巨大。当传统的分拣设备无法满足快速增长的物流需求时，多AGV物流分拣系统成为物流产业需要研究的一个重要课题，且有着很大的应用潜力和应用前景。AGV小车是一种无人驾驶的、按照预先设定路线运输货物的车辆，使用AGV代替传送带和人工进行包裹的分拣和运输，能够在较小的面积内实现一系列分拣作业，可以提高物流分拣效率。
虽然多AGV物流分拣系统已经在实践中得到了应用，但该领域的详细文献和指导理论还不是很丰富。因此，该文旨在使用建模仿真的方法设计一个多AGV物流分拣系统，提高物流分拣效率，保证系统的正常高效运行。
1 环境描述
由于AGV分拣系统效率和成本效益的性质，建模已被确定为改善设计、操作和维护AGV系统的重要途径之一。越来越多的学者使用建模仿真的方式来对AGV系统进行研究[1-3]。De Ryck等人[4]对AGV系统相关控制算法和技术进行了综述。陈胜军[5]使用改进的A*算法对基于AGV调度的物流分拣系统中AGV小车的路径规划问题进行了研究，通过仿真模拟实验验证提出方法的合理性。武星等人[6]研究了多载量AGV系统的交通管控问题，提出了AGV避碰和系统死锁预测与避免方法，通过仿真验证所提方法的有效性。陈香玲等人[7]提出了一种AGV充电需求和电量消耗优化模型，仿真结果表明该模型能够有效提高AGV分拣效率。近几十年来，学者们使用建模方法从不同的角度对AGV系统进行研究[8-10]。因此，该文采用建模仿真的方法研究多AGV分拣系统，基于离散网格对分拣平台进行描述，构建多AGV分拣系统仿真模型。
该文研究的是一个具有双层结构的分拣平台，上层用于包裹分拣，下层用于包裹收集，并采用中心控制器集中控制[11]的方法来控制整个分拣系统的运行。整个上层分拣平台由m×n个大小相同的元胞组成，如图1所示。平台左右两侧的黑色矩形代表栅栏等障碍物，平台外围的箭头表示AGV在该行或该列的运动方向。依据元胞的功能，该文把分拣平台的元胞划分为5种类型：入口元胞、出口元胞、储货元胞、卸货元胞和普通元胞。入口元胞是系统的入口，空AGV在该类元胞上装载包裹;出口元胞是系统的出口，空AGV通过该类元胞离开分拣系统;储货元胞是储存包裹的地方，是AGV的分拣目的地，其下方连接有揽货箱，分拣包裹从该类元胞掉落到相应的揽货箱内，同一揽货箱内的包裹具有相同的目的地;卸货元胞与储货元胞相邻，装载包裹的AGV在这类元胞上将包裹卸载入储货元胞中;不具备以上4种功能的元胞称之为普通元胞，AGV可在该类元胞上进行移动、停止、转弯等操作。一个AGV一次只能携带一个包裹，且同一时刻一个元胞只能容纳一个AGV。
单AGV运行流程如图1所示，其中标号为1的AGV表示处于载货状态的AGV，标号为2的AGV表示处于空载状态的AGV。空AGV在入口元胞处装载包裹并获取其包裹目的地，AGV将此信息上传至中心控制器，中心控制器接收信息并为该AGV规划从入口元胞到储货元胞的可行路径，AGV根据路径信息进行移动，直至到达目的卸货元胞执行卸货任务。AGV完成卸货任务后将此信息反馈给中心控制器，中心控制器为该AGV再次规划一条从当前元胞到出口元胞的路径，AGV沿此路径离开分拣平台。AGV在移动过程中将自身位置、速度等信息不断反馈给中心控制器，中心控制器根据反馈信息对分拣平台进行交通控制。
对于AGV的运行，该文做出如下假设：（1）不考虑AGV离开系统后重新进入系统的调度问题，且系统外有足够多的空AGV可以进行调度;（2）系统承担的是轻型包裹的分拣，忽略AGV的加减速时间;（3）AGV必须静止通过旋转调整运动方向;（4）AGV只能将包裹沿着行进方向的右侧投入储货元胞，且AGV在卸货元胞需要花费1个单位时间将包裹投递到储货元胞。
2 仿真模型构建
改进标号修正算法[12]是解决最短路径问题的一种常用算法。使用改进标号修正法进行路径规划前，需要基于分拣平台构建AGV运行网络。以分拣平台中的元胞作为网络中的节点，添加虚拟节点0+作为空载AGV的虚拟目的地节点，将节点按照分拣平台中元胞与元胞之间的可行方向进行连接得到弧。出口元胞到虚拟元胞0+连接得到的弧权重为0，卸货元胞与储货元胞相连得到的弧权重也为0，因这两种弧对路径更新无影响。AGV路径规划的目标是最小化运送包裹的时间，因此，其余弧以AGV在弧上通行花费的时间作为网络中弧的权重，即AGV通过元胞所花费的时间。为了达到动态更新最优路径的目的，该文在计算AGV通过元胞花费时间时引入时间变量，称为路径更新时间间隔f。每隔f个时间步，中心控制器可根据t-f时刻到t时刻时间段内分拣平台内AGV运行状况，重新计算AGV通过每个元胞花费的时间，更新AGV运行网络中弧的权重，从而为AGV重新规划从当前元胞到目的元胞的时间最短路径，使AGV按照新路径继续行驶。
分拣系统类似于一个简化的城市交通网络，在平台中AGV按照中心控制器规划的路径移动。AGV沿着既定路径在分拣平台内的移动可以看作AGV从一个元胞向另一个元胞移动的过程。因此，该文采用元胞自动机模型中的Nagel-Schreckenberg（NS）规则作为AGV移动规则。AGV是一种完全可控的小车，因此忽略了NS规则中的随机慢化条件，仅使用其余条件来指导AGV的运行。
AGV在运动的过程中，会不可避免地发生冲突和死锁问题，需要额外的交通控制策略来加以管控。根据环境设置，平台中可能出现的碰撞可以分为两种类型：追击碰撞和交叉碰撞，具体见图2，图中用实心圆表示AGV。当两辆AGV在同一行（列）行驶，且后面AGV的速度大于两AGV之间的距离时，追击碰撞就会发生，具体见图2（a）。因该文采用NS规则作为控制单AGV的移动规则，因此可避免追击碰撞，也可通过安装在AGV上的传感器来避免这种类型的碰撞。若同一时刻两辆AGV在交叉路口同时争夺未被其他AGV占用的同一元胞时，交叉碰撞即会发生，具体见图2（b）。该文采用的是集中控制的方式来控制系统的运转，上位机系统可根据各个AGV的优先级顺序来对交叉碰撞进行管理控制。规定速度高的AGV比速度低的AGV拥有优先通过权。若两辆AGV的速度相同，则随机选择一辆AGV优先通行。
在物流分拣系统中，有大量的AGV同时移动。AGV在移动过程中可能出现首尾相连的情况，形成一个死锁环路，导致局部瘫痪，具体见图2（c），这种情况不利于AGV的正常运行。死锁检测与恢复策略允许死锁的产生，且对AGV进入系统并无限制，是解决死锁问题常用的方法。该文采用死锁检测与恢复方法来处理分拣系统中的死锁问题，通过一种有效的识别死锁算法发现死锁，并实时选择死锁中的某辆AGV，改变其路径来解决死锁问题。
3 结果与讨论
该文建立了一个大规模的仿真环境来评价提出的模型。图3展示了一个由55×40个元胞组成的分拣平台，平台中共设置了12个入口元胞作为分拣入口，204个储货元胞作为分拣出口。仿真实验研究在固定的10 000个时间步内AGV在平台内的运行情况。每次实验重复100次，结果取平均值。
为了研究系统内AGV数量与系统仿真算法性能的关系，该文提出了系统容量（SC）的概念，系统容量是指分拣平台内部最大可容纳的AGV数量。在仿真系统中，若分拣平台内部的AGV数量小于SC，则新AGV可通过入口元胞进入分拣平台。一旦分拣平台内部的AGV数量等于SC，则新的AGV不允许进入分拣平台。
针对图3中的仿真场景结构，该文对分拣平台所能容纳的AGV数量进行研究。图4（a）展示了系统容量为200、250、300时，分拣平台内AGV数量随时间的变化关系，其中路径更新时间间隔f均取10。当sc=200时，分拣平台内AGV数量在增加到稳定值后几乎保持不变，振幅很小。当sc=250时，平台内AGV数量也接近系统容量，但与sc=200时相比，曲线的振幅相对更大。然而，这一现象在sc=300时并不成立，在此系统容量下，AGV数量随时间的变化曲线明显是动荡的，振幅較大，AGV平均数量取值为256辆，远小于系统设置的容量300辆，即系统内实际运行的AGV数量明显小于系统容量。
因此，在图3这种分拣平台布局结构中，系统容量应设置小于260辆。即使AGV数量继续增加，实际运行在分拣平台中的AGV数量也无法达到系统容量。与此同时，随AGV数量的增多，交通控制的复杂性、碰撞和死锁的概率也越来越高。
规定时间内AGV包裹分拣的数量是衡量分拣系统效率的一个重要指标。图4（b）展示了SC和f的变化对仿真系统总投递包裹数量的影响。从图中可以看出，随SC的增加，仿真系统总投递包裹数量总体上呈上升趋势。当sc>200后，无论f取何值，总投递包裹数曲线斜率明显下降。sc=250和sc=300时，总投递包裹数量差距非常小。甚至sc=300，f=90时，其总投递包裹数量相较于sc=250，f=90时不增反降。且当sc>200，后，f对分拣系统效率的影响开始凸显，拥有较小f值的系统其总投递包裹数量总体上大于较大的f值。
造成这一现象的原因是，在sc<200时，系统容量约束是限制AGV进入分拣平台的主要因素，这种情况下分拣平台内部AGV占比少，f对仿真系统的影响可以忽略。当sc>200后，限制AGV进入分拣平台的主要因素由系统容量约束转变为分拣平台中入口分布、路线设置等其他原因。此时，即使不断提高系统容量的上限值，AGV也由于其他因素的影响导致无法进入到分拣平台。当sc>250后，这种情况下分拣平台内部基本已经达到了饱和的状态。此时，f对仿真系统的调节作用也由此凸显出来，较小的f值其对分拣系统效率的作用明显优于较大的f值。较小的f值可以更真实地反映路径信息的变化，使AGV尽可能走时间最短的路线。但是，f的调节作用是有限的，继续增加系统容量，使更多的AGV进入分拣平台不仅不能提高分拣系统的效率，反而会适得其反。这不仅浪费资源，提高成本，而且使得分拣平台中的交通控制更加复杂。f值小也意味着算法計算效率低，在实际应用时，建议根据分拣系统内部运行AGV数量和实际需求选取合理的f值。
4 结语
采用二维离散网格对物流分拣平台的环境进行建模，使用改进标号修正法结合路径更新时间间隔为AGV动态规划路径。将NS规则作为单AGV移动规则并辅以交通控制策略来管理分拣系统的长久运转。使用该模型对分拣系统进行仿真，研究了系统容量和路径更新时间间隔对系统分拣效率的影响。仿真结果表明，针对该文分拣场景，系统容纳的AGV数量应控制在260辆以下。且路径更新时间间隔在系统容量小时，对分拣系统效率几乎无影响;而当系统容量大于200时，较小的路径更新时间间隔对分拣系统效率的作用明显优于较大的路径更新时间间隔。
参考文献
[1] zou w，pan q，meng t，et al.An Effective Discrete Artificial Bee colony Algorithm for Multi-AGVs Dispatching Problem in a Matrix Manufacturing Workshop[J].Expert Systems with Applications，2020（161）：113675.
[2] 张闯，张国涛，赵龙葛，等.基于VR的物流分拣仿真系统设计[J].中小企业管理与科技，2020（9）：192-193.
[3] qi m，li x，yan x，et al.On the evaluation of AGVS-based Warehouse Operation Performance[J].Simulation Modelling Practice and Theory，2018（87）：379-394.
[4] De Ryck，Versteyhe M，Debrouwere F.Automated Guided Vehicle Systems，State-of-the-art Control Algorithms and Techniques[J].Journal of Manufacturing Systems，2020，54（1）：152-173.
[5] 陈胜军.基于多台AGV调度的物流分拣系统[D].深圳大学，2017.
[6] 武星，翟晶晶，肖海宁，等.多载量AGV系统防死锁路口通行顺序优化及避碰[J/OL].[2021-05-12].http：//kns.cnki.net/kcms/detail/11.5946.TP.20201130.1726.002.html.
[7] 陈香玲，郭鹏，温昆，等.考虑充电需求和时间窗的多AGV调度优化建模[J].河北科技大学学报，2021，42（2）：91-100.
[8] 韩潇，张炜昊，刘畅，等.一种基于AGV小车的智能物流分拣系统[J].山东工业技术，2018（16）：115.
[9] 梁彧.基于改进Dijkstra算法的AGV智能车路径规划[J].科技与创新，2020，168（24）：165-167.
[10] 龙永红，向昭宇.基于颜色Petri net的多AGV防死锁系统综述[J].电子世界，2019（2）：64-66.
[11] 周忠太.多AGV物流分拣系统的设计与关键技术研究[D].华南理工大学，2018.
[12] Guerriero F， Musmanno R. Label correcting methods to solve multicriteria shortest path problems[J].Journal of Optimization Theory & Applications，2001，111（3）：589-613.
