基于AGVs路径规划的物流智能调度系统设计与实现

宋颖颖

(上海济光职业技术学院 经管系，上海 201901)

0 引言

在当前电子商务和互联网技术的迅猛发展下，世界范围内的物流、快递行业进行不同程度的优化和改造。目前物流行业希望可以通过大规模的升级改造，将物流体系在时空间上的收益最大化，首当其冲的就是需要对多领域多行业的商品货物进行接受整合，在装箱、储存、管理和配送方面对货物的需求和体量进行规范化操作[1-4]。因此，不同领域、不同行业的公司企业都将物流的调度进行了多方面的应用，类似于机场、大型库房、海湾码头或者各类集装箱基地等物流调度场所并不少见。而在目前经济全球化和一体化的国际背景下，高效率、高集成化和高自动化的智能物流调度系统就成了主要的研究对象。

电子商务和网络购物不断发展，像“618”、“双十一”等电商狂欢节逐渐被年轻的商务群体和学生团体所青睐。在活动期间，客户在互联网商务平台选购了自己喜欢的商品，而店家在接受订单之后进行成千上万的物品邮寄，最终传送到客户手中。面对大规模、大体量的商品货物，物流企业或者各大仓库经常会面临货物堆积、配送迟缓或者商品丢失的情况，这也就导致了客户大规模投诉或者巨大的经济赔偿等问题[5]。而物流企业内亟需解决的问题就是如何能够将上述问题合理规范、有效预防，降低财务和声誉上的损失。

细化来说，物流企业或者仓库在进行货物储存或者传送的过程中，需要着重关注货物装卸和道路运输的各项成本。无论是时间成本、人力成本还是资源成本，物流行业都需要建立一套低消耗、低成本的物流调度方[6-7]。通过多方面的调研得知，在整个过程中，花费在货物装卸、道路运输中的时间竟然达到了70%以上，而财务方面的花销也仅仅达到了成本总额的20%～50%左右。也就是说，相比财务上的开销成本，时间上的消耗才是最需要解决的问题，如何能够制定出一套高效快捷、容错率高的智能物流调度系统将是最大的难题。

随着自动化技术和人工智能的快速发展和广泛应用，物流行业从最初的人力搬运发展到了自动化搬运，进而发展到了计算机人工智能技术与智能物流调度相结合的前沿科技，具有较大的行业竞争力[8]。截止2020年底，我国的物流行业发展依然呈现出爆炸式的增长态势，总值达到了22 048亿元，而这个数字也在国家服务行业总产值占据了19.62%的主要地位，以此来推算未来的很长一段时间内，世界范围内的物流行业仍会持续增长。然而，尽管物流行业的发展依然迅速，可是大部分的物流企业或者仓库仍然在物流的调度方面存在很多问题，降低了企业效益，损坏了行业声誉，更是遏制了物流行业的进一步发展[9-11]。究其原因，大部分物流企业并没有科学规范的物流调度系统，在整个布局和规划上存在很多漏洞，并且在国家乃至世界上日益严重的人口老龄化背景下，昂贵的人力成本和复杂的企业结构也将导致更严重的问题出现。

为了解决上述的各种问题，一种具备电磁驱动、光学导航定位功能的自由移动智能机器人——自动导引运输车(AGV，automated guided vehicle)出现了。AGV具有被物流行业所需求的各项优势，除了自身的高智能化和高自动化特点之外，还能够准确定位目的地，具有较高的安全性和可靠性，一度成为了物流行业和柔性电子行业争相研究的对象[12-13]。AGV具有不可估量的发展前景和应用价值，能够从根本上解决物流行业效率低下、各项成本过高和规范程度低的问题，在未来的现代化物流行业内，将会以AGV作为智能操作核心而受到重视[14]。

本文深入分析了目前物流行业和库房管理在调度过程中所面临的问题，充分调研了物流智能调度、AGV路径规划和人工智能算法方面的研究成果，设计了基于AGV机器人和路径规划优化的智能物流调度系统。该系统将硬件和软件相结合，设计了AGV的物流调度硬件，又结合了路径规划理论，开发了基于Petri网络的路径规划算法，并且对所设计的系统进行实现和测试。本文所设计的系统很大程度上解决了物流行业内效率低、成本高和可靠性低的诸多问题，提高了生产过程中的自动化程度，有效推动了商业模式和市场规范的发展。

1 AGV硬件结构设计

为了能够便于修改和完善AGV的结构框架和需求功能，同时也能使智能物流调度系统尽快地适应企业日常工作和库房日常运作，本文将通过模块化的设计思想来设计AGV结构，并以此实现AGV各项需求功能。在下位机的功能模块方面将会以下4个方面着手：导航模块、定位模块、通讯模块和驱动模块。因此，本文针对4个模块在整体的设计思路上给出了详细的说明，如图1所示。

图1 AGV调度系统总体设计框架

1.1 AGV导航模块

AGC的导航方式有很多种，通常情况下会被划分为5种：视觉导航、电磁导航、二维码导航、磁带导航和激光导航[15]。磁带导航的优点是能够在沿途铺设灵敏度较高的传感器，并且成本也非常低，因此本文针对AGV的整体需求功能和物流行业工作环境的综合考虑，采用了磁带导航的方式，如图2所示。本文所采用的磁带导航方式较为方便设计，磁带本身均匀分布了8个灵敏度很高、分布点距离为10 mm的霍尔传感器。在整体布局上，库房地面会在各条道路上铺设宽度均为4位的磁带。当AGV在行驶过程中捕捉到了电磁信号时，信号接收端则会记录为“0”，而如果没有检测到电磁信号，就会自动记录为“1”。AGV在行驶过程中会不断向终端传递自己的状态信号，如果将“11000011”作为AGV的运动状态基准，那么AGV在运行过程中就会不断将自身运动状态所对应的8位信号传递至终端，同时会利用PID算法进行姿态矫正。在进行了多轮测试实验之后，本文发现磁带导航的机动性良好，在不同的环境和灯光条件下仍然能够保证准确定位，符合本文的设计要求。

图2 磁导航传感器

1.2 AGV定位模块

上文所设计的AGV导航模块只能使得AGV按照事先预定好的路径进行行驶，但是不能记录整个行驶过程的路程信息。因此，为了能够对AGV的路程信息进行远距离的把控和记录，本文利用无感识别技术——无线射频识别技术(RFID)设计了AGV的定位模块[16-17]。RFID的工作原理简单有效，主要包含射频部件和读写部件，其中射频标签小巧方便，携带了读写器的AGV一旦判别到设别区域内有射频标签的存在，就能够迅速识别，在读写器记录此时此刻AGV的路程信息之后，对AGV下一步的路线进行预判，并将预判记录储存在读写器内。本文在工作开展的过程中，将射频标签设置在物流库房路径的每一条磁带下，并且对每一个射频标签都进行了读写操作的设置。当携带了读写器的AGV运动至不同的射频节点处，读写器会将识别区域覆盖范围内的所有射频标签的信号进行读写，并将数据直接上传到终端的上位机，以此实现路径信息的记录和AGV的精准定位。本文在实际操作过程中发现，AGV的定位精度很高，误差只有不到5 mm，而且识别速度很快，几乎没有信号延迟，这也说明了本文所设计的AGV定位模块完成定位任务的性能良好。本文所采用的读写装置和射频标签如图3所示。

图3 AGV定位系统

1.3 AGV通讯模块

为了能够对AGV进行实时准确地指令控制，本文使用了Zigbee模块来设计通讯结构，并依托上位机向AGV发送控制指令。Zigbee模块能够从上位机传出、下位机接收实时传输十六进制的数据信号[18]，本身具有成本消耗低、功能齐全和传输距离短等优点，能够对AGV进行快速准确地指令传送和信息传递，因此本文使用Zigbee进行通讯模块的设计。本文在上位机和下位机的信息传输和指令传送的过程中加入了不同符号的识别帧头，目的就是为了能够降低通讯过程中的失误和出错，而通过实际的操作可以得到，本文基于Zigbee所设计的通讯模块传输信号准确率高、传输速度快，能够很好地完成调度系统的各项指令。本文所采用的Zigbee通讯模块原理如图4所示。

图4 Zigbee通讯模块原理

1.4 AGV驱动模块

本文对AGV的驱动模块进行设计，采用的是差速驱动方式，设计的前轮为可以随时改变行动方向的万向轮，设计的后轮是驱动轮，搭配了MOXA的直流伺服电机，减速比为18∶1，轮胎半径为24 cm。同时，本文的驱动器是威龙的双路12A直流有刷电机驱动器，并采用串口指令设置，通过实际操作得知，本文所设计的驱动系统反应效果非常灵敏，操作方法简单易懂，AGV的驱动效果很好。

最后，本文将以上所设计的所有模块进行整合，将硬件和软件结合到一起，设计完成了本文的AGV结构，原理如图5所示。并且在之后的验证工作中发现，本文所设计的AGV结构能够较好地完成物流行业或库房的调度任务。

图5 磁导引小车

2 基于Petri网络的智能路径规划算法

2.1 物流仓库的Petri网模型构建

Petri网的提出是作为一种并发、分布式的建模工具存在的，目前在规划、管理、网络和通讯等方面最为常见[19]。本文为了能够对不同环境、不同领域下的物流行业或库房仓库进行调度过程中的多路径规划，并且将整体的动态特征进行描述，实现网络资源和实体资源的转移，并且最终实现智能物流调度系统的模型构建和性能优化。

为了能够对物流企业的调度任务进行全面地描述(图6)，本文在基于时间Petri网络模型的初始便定义了六元组TPN={P,T,ω,θ,Mk,rk}，六元组的各项参数分别表示为：物流企业目前的资源状态——定义为有限库所集P={p1,…,pn}，企业目前所消耗的资源和正在参与的工作状态——定义为有限变迁集T={t1,…,tn}，某一时刻k所对用的企业运行状态是通过库所集和变迁集之间的关联矩阵实现的，也就是ω:(P×T)∪ (T×P)→Z+，并且在此基础上，将库所集和变迁集的两个关键矩阵定义为A+和A-，即：(A+)ji=ω(tj,pi)，(A-)ji=ω(pj,ti)，而Petri网络模型在实际过程中的触发时间则用θ表示，在某一时刻k智能调度系统数据库的状态变化则会用来表示，最终设定rk:(t1,…,tn)→ti∈{0,1}为一组bool类型变量组成的向量，其中，“变迁触发”所对应的变迁值为“1”，如果对应“0”则意味着不触发。

图6 物流调度仓库Petri网络模型

本文所设计的Petri网络模型不同于其他的普通模型，在设计之初便加入了物流资源的限制矩阵Pc，而Pc(Type(Pc)=1)触发条件也相应地变为M(Pc)-I(Pc)+O(Pc)≥0(Pc∈P)。在资源限制矩阵Pc的加入下，触发时所引起的令牌变化也会出现不同的状态，也就是说，令牌数量的增加或者减少与Pc中的令牌数量变化成对应关系，分别由输入变迁和输出变迁所控制。本文加入资源闲置矩阵的目的是为了将Petri网络整体并发运行能力大幅度增加，而之后的效果也能说明本文的方法是正确有效的。该做法能够有效防止AGV在物流企业实际调度过程中出现的路径冲突或者AGV死锁的问题，将物流仓库的多方面安全隐患降到了最低，避免了道路资源、时间资源和人力成本的浪费。图7为图6(a)在加入了资源限制矩阵之后的Petri网络模型。

图7 双AGV位于十字型仓库Petri网示意图

2.2 基于Petri可达树的智能路径规划算法

从上文对Petri网络的描述中可以看出，只要存在变迁，就会对网络中的令牌数量产生增加或者减少的影响，这种性质被称为“可达性”。如果Petri网络正处在一个初始状态M0，在r1,r2,…,rn触发序列的作用下将M0转化为Mn，则Mn是从M0可达的。本文在此将Petri网可达树引入到本文所设计的路径规划算法和智能物流调度系统中，目的是为了将AGV在起始节点和终止节点之间的任意路径都能够在网络模型中体现出来，以此实现视觉可视化。本文将可达树的树根设置为初始状态M0，而M0通过一系列的变迁则会将不同的路径或者工作状态作为可达树的各个节点，库所集和变迁集之间的关系就是通过不同节点之间的连线来确定的。算法如下：

本文在设置可达树树根M0的同时，会对new进行特殊标识，本操作设置为算法第一步；当可达树的所有状态量均转化为old之后，可达树则会正式成立，此时代表算法正式结束，本操作设置为算法第二步；算法第三步是，如果计算机自动检测到仍然有剩余的new存在，则会重复进行以下操作：

1)选择标识为new的状态量M；

2)如果在可达树算法构建的过程中存在于M相同的标识，也就是说找到了重复项，new会直接转化为old，并且自动转移至另一个new；

3)如果检测到此时已经检测不到存在的变迁M标识，M会自动将状态转化为dead-end，并且直接跳转到算法步骤的第二步；

本文在设计算法的过程中进行上述操作，目的是为了能够解决传统可达树算法所存在的计算复杂度高、整体性能较低的问题，大幅度提高物流智能调度系统的运算时间，降低物流企业的时间成本，而本文所设计的可达树能够对不同物流企业的库房进行不同节点的路径规划。在上述算法中，本文还在传统可达树算法中加入了Mf作为不同目标节点的标记数值，并且在可达树的构建过程中不断与new节点的状态量M值进行对比，如果二者相等，则意味着可达树的构建过程停止，这也大大减少了计算机地图路径的数量，降低了资源成本，极大地提高了计算效率。

2.3 智能路径规划算法验证对比

对于一个高效、准确的调度系统来说，AGV的调度路径是效率和准确度的关键所在。为了能够找到路径规划最合理的智能算法，本文对国内外主流的路径规划算法进行验证，并与本文所设计的算法在MATLAB中进行结果分析对比，将相同环境、相同调度任务的不同算法进行了路径规划结果和AGV运动时间的对比分析[20-22]。最终的智能路径规划算法对比结果如图8所示。具体的实验数据如表1所示，分别描述了不同算法在路径长度、执行时间和迭代步数上的差异。

图8 不同路径规划算法的结果对比

表1 各路径规划算法实验结果

从图8和表1结果可以看出，在调度路径的规划方面，4种算法的构造结果虽然不同，但是仍然能够得到较为理想的调度结果。但是从表格中的各项数据分析得知，A*算法的迭代步数和运算时间(3.96)是最少的，但是却得到了最长的路径(914 m)；人工势场算法的计算过程较为复杂，需要在过程中对AGV的目标节点和初始节点进行不断地迭代计算，虽然路径长度(797 m)较低，但是消耗的时间较高(5.19 s)，在调度效率较低的同时也提高了整体计算的复杂程度；蚁群算法是目前应用最为广泛的方法，迭代步数达到了200，并且消耗了最长的时间(7.33 s)，路径长度也不理想(868 m)，整体调度效率最低；而本文基于Petri网络所设计的可达树算法路径的长度较低(801 m)，迭代步数只需要10次，运算时间也比较少(4.27 s)，整体的调度效率是最准确、最高效的。并且可达树算法能够迅速对地图网络中的冗杂节点进行选择性的淘汰，并针对初始节点和目标节点之间的距离进行最佳调度路径的规划。因此，本文基于Petri网络所设计的智能路径规划算法能够保证较高的准确率和工作效率，在物流智能调度系统中更好地应用。

3 基于AGVs的物流智能调度系统实现

在经过了AGV硬件和软件的设计之后，并基于Petri网络设计了路径规划算法，最终实现了本文所设计的物流智能调度系统，打开系统的初始界面如图9所示。主界面所包含的内容共涉及到5个部分，其中包括AGV车辆工作状态管理、地图智能路径规划、AGV通讯管理、AGV工作状态和信息交互管理。物流智能调度系统将5个模块进行整合，在进行协同运作的同时共同完成物流仓库的调度工作任务。

图9 主操作界面

3.1 地图设计模块实现

在智能调度系统的主界面上，右上角的是系统的智能路径规划模块。路径规划模块能够针对物流行业或者仓库库房的实际工作条件进行最优路径的选择，将AGV的运动轨迹以适当的比例缩小，并且将AGV的实际运动过程中的路线动态实时地呈现在地图模块上。本文所设计的路径规划模块能够对库房地图进行最优路径绘制、路线保存和自动删除等功能操作，并且在AGV的实际运动或者路径优化过程中，用户可以通过观察实时的AGV运动路径进行直观地显示和更改，在过程中可以根据自身的需要添加物流库房中AGV的数量，进行障碍物或者货物搁置点数量的更改，以此适用不同类型或者不同区域范围内的物流行业。例如图10中的空心圆代表AGV的运动轨迹，AGV可以对编号的不同节点进行运动状态的改变，并且将直线表示为AGV运行的双向路径；实心圆表示的是同一个区域内的不同AGV。图10为基于Petri网络通过PIPE进行绘制的地图。

图10 Petri网地图

3.2 系统管理模块实现

关于AGV的信息管理部分和任务查询部分在操作系统的左下方，而左上角则是AGV的工作状态列表。不同的AGV对应了不同的工作状态，“工作中”、“维修中”和“空闲中”所对应的指示灯颜色分别为“红色”、“黄色”和“绿色”。AGV的工作状态只有智能调度系统的工作人员点击主操作界面的按钮才能进行AGV的状态设定，而如果AGV的工作状态出现异常，则会上传AGV的维修指令，此时需要操作人员对AGV的状态进行“维修”设定，并且将故障AGV的编号、故障原因和故障时间上传到系统终端，这样会更有利于后台终端对故障AGV进行数据记录。如果需要执行货物调度任务，工作人员需要在实际操作过程中输入执行任务的编号、起始地图坐标、终点目标坐标和调度任务的缓急程度，并且下达命令之后，后台数据库会在任务工作表中自动记录本次任务信息。此时主操作界面会自动显示新添加的任务为“未执行”状态，同时自动匹配“空闲中”的AGV进行调度任务。一旦AGV与未执行的任务相互匹配，AGV的“空闲”状态转变为“工作中”，而“未执行”任务也会变为“执行中”；在任务完成后，AGV状态恢复为“空闲中”，任务列表则会显示为“已完成”。操作人员能够在此模块中进行“添加”、“更改”和“删除”任务的操作，并且在任务列表可以随时查看过去执行过的任务信息，如图11所示。

图11 AGV系统状态管理

3.3 信息交互模块实现

本文所设计的智能调度系统是通过计算机调度软件和多个AGV的传输信息进行交互的。AGV运输信息呈现在系统主界面的最下方，通过信息交互模块可以查询到此时正在执行调度任务的AGV，并且能够基于Zigbee的功能在车辆数据库中上传所有AGV的车辆信息。在数据库中，工作人员可以查询AGV的编号、剩余电量、运行状态和当前所在的位置，并且能够实时查询到所有AGV的工作进度，如图12所示。而过去完成的调度任务可以通过“历史任务”列表进行查询，如图13所示。

图12 状态信息监测模块

图13 历史任务查询界面

3.4 物流智能调度系统测试结果

本文在本节中进行了智能调度系统的实验验证，通过8项调度任务来验证智能调度系统是否能够在众多物流行业或者库房储存中进行正常工作，实验过程如图14所示。调度任务的匹配是通过离目标点最近的AGV的编号与此点的调度任务进行相互匹配的，主操作界面的任务列表详细介绍了调度任务的起始点、目标点和所对应的AGV信息。举例来说，AGV#4刚好匹配了任务K4，此时所在位置为地图节点90，此任务的起始点为31，在11∶25时正式接受K4任务，并从90移动至31，接着朝着地图节点100进行移动。本文所设计的智能路径规划算法会根据各个AGV所接受的任务和起始点对AGV的下一步路径移动进行智能规划，并且将地图路径信息通过Zigbee网络将数据信息传递给所对应的AGV，接下来智能调度系统的监控模块开始实时关注AGV的运动状态，详细路径规划结果如图15所示。

图14 AGV任务列表

图15 AGV运行情况

综上所述，本文所设计的基于AGVs路径规划的物流智能调度系统能够在各种物流环境或者库房基地完成调度任务，很好地解决了物流企业或者库房仓库在忙碌期的繁杂调度问题，不仅提高了物流调度的自动化程度，也极大地降低了物流行业的时间成本和资源成本，保证了物流调度和道路运输的效率。

4 结束语

传统的物流调度系统或者路径规划算法仅仅针对的是调度任务较少、AGV调度车辆不足的情况，随着调度任务的加重和库房规模的扩大，调度系统的工作压力和算法计算复杂度会急剧增长，导致工作效率很低。为了解决上述难题，本文深入分析了目前物流行业和库房管理在调度过程中所面临的问题，充分调研了物流智能调度、AGV路径规划和人工智能算法方面的研究成果，设计了基于AGV机器人和路径规划优化的智能物流调度系统。该系统将硬件和软件相结合，设计了AGV的物流调度硬件，又结合了路径规划理论，开发了基于Petri网络的路径规划算法，并且对所设计的系统进行实现和测试。

系统测试结果显示，本文所设计的基于AGVs路径规划的物流智能调度系统能够在各种物流环境或者库房基地完成调度任务，很好地解决了物流企业或者库房仓库在忙碌期的繁杂调度问题，不仅提高了物流调度的自动化程度，也极大地降低了物流行业的时间成本和资源成本，保证了物流调度和道路运输的效率。