移动机器人智能交通管理系统的应用 [复制链接]

潘永平1滕旭辉2王平1林树茂2李扬11苏州罗伯特木牛流马物流技术有限公司苏州北京起重运输机械设计研究院有限公司北京

摘要：移动机器人智能交通管理系统是专用于自动导引车系统（AGVS）的智能调度软件。它的主要功能包括管理、监控和调度AGV执行搬运作业任务。文中介绍了一种基于移动机器人的交通管理系统AGVS车辆调度路径优化策略方法，通过实际应用案例，验证该方法可实现最优策略下的单车调度和多车调度，提高了AGV的运行效率。

关键词：移动机器人；智能交通管理系统；车辆调度

中图分类号：TH文献标识码：B文章编号：-（）11--05

0引言现代工业中AGV的应用日渐显示出优越性，其适用性好、可靠性高、柔性好、能实现生产和搬运功能的自动化和集成化，在国内外各行业中都得到了广泛应用。近年来国内对AGV的需求量迅猛增长，如仓储、生产线、码头港口等[1]，随着计算机集成制造系统技术的逐步发展和工厂自动化的实现，以及自动化立体仓库和柔性制造系统的广泛应用，AGV作为调节和联系离散型物流系统使作业连续化的搬运手段，它的智能化、精确性、高效性在其中起着至关重要的作用。

1交通管理系统功能概述移动机器人智能交通管理系统是自由开源的移动机器人AGV交通控制软件系统，实现系统中车辆的优化控制及交通管理。

交通管理系统的主要功能是管理、监控和调度AGV执行搬运作业任务。一方面，它与上一级的信息管理系统（SAP/ERP/WMS/MES等）主机进行通讯，产生、发送以及回馈搬运作业任务，另一方面，通过无线网络系统与单台或多台AGV进行通讯，按照一定规则发送物料搬运任务，进行智能化交通管理、自动调度AGV完成搬运物料任务，同时接受AGV反馈的状态信息，监控系统的任务执行情况，并向上一级信息管理系统报告任务的执行情况。交通管理系统的主要功能：1）AGV与管理系统通讯在同一局域网内，通过TCP/IP进行数据交互；2）AGV调度策略任务分配之后，选择最优路径，并分配给空闲车辆，实现资源的有效利用；3）AGV多车调度可同时调度多台车辆，遇到多车交汇的情况，遵循先到先得原则；4）AGV地图模型路径模型可视化，在运行时显示车辆行驶的动画，掌握车辆行驶的状况；5）接口具有开放性接口，可与WMS、ERP、MES等软件对接，接收运输订单，完成相应任务。

2最优路径选择方法交通管理系统中进行路径选择时，采用最短路径的策略。最短路径是指在一个赋权图的两个节点之间找出一条具有最小权的路径。在实际应用中，为提高AGV工作效率，在车间内或仓储过程中常常遇到最优行驶路线选择问题，因此在AGV的交通调度中对最短路径问题的研究和应用对生产效率的提高具有重要意义和实用价值[2]。

最短路径算法中较为常用的三个算法是Floyd算法、Dijkstra算法和Bellman-Ford算法，每种算法都有其特点和优势，本文所述交通管理系统采用Dijkstra算法。Dijkstra算法是求解最短路径问题的经典算法之一，它是一种按路径长度递增的次序产生最短路径的算法，可求单源、无负权的最短路径。适用于有向图和无向图，时效性较好，时间复杂度为O（V*V+E）。可用优先队列进行优化，优化后时间复杂度变为0（v*lgn）[3]。

设G=(V,E)是一个带权有向图（见图1），将图中顶点集合V分成两组。第一组为已求出最短路径的顶点集合，用S表示，初始时S中只有一个源点，之后每求得一条最短路径,就将其加入到集合S中，直到全部顶点都加入到S中，算法结束。第二组为其余未确定最短路径的顶点集合，用U表示，按最短路径长度的递增次序依次将第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中顶点的距离是从v到此顶点的最短路径长度，U中顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度[4]。

图1带权有向图

算法步骤：1）初始时，S只包含源点，即S＝{v}，v的距离为0，U包含除v外的其他顶点，即U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞；2）从U中选取一个距离v最小的顶点k，加入S中，所选定距离就是v到k的最短路径长度；3）以k为新考虑的中间点，修改U中各顶点的距，若从源点v到顶点u的距离（经过顶点k）比原距离（不经过顶点k）短，则修改顶点u的距离值，修改距离值后的顶点k的距离加上边上的权[5]；4）重复步骤2）和3），直到所有顶点都包含在S中。由北京起重运输机械设计研究院有限公司承建的某物流园生产厂房智能化物流系统连接着3座生产厂房及立体库，每座厂房有4层，各层皆为独立的生产车间，总建筑面积7.5万m2。该系统包括库存管理系统、采购收货、生产排程、生产发退料、生产入库、销售发货、品质管理等。连续型物流系统采用输送线方式，离散型物流系统采用AGV方式，本项目采用3台激光导向AGV系统，其中1台为叉车式AGV，2台为背拖式AGV。

以所述移动机器人智能交通管理系统项目来说明Dijkstra算法在调度策略中的应用。在该项目中，有34个DP点，初始时，选择一个DP点作为源点，即DP1＝{v}，v的距离为0。DPn包含除v外的其他DP点，即DPn={其余顶点}，若v与DPn中顶点u有边，则u,v有正常的COST值，若u不是v的出边邻接点，则u,v的COST值为∞。从DPn中选取一个距离v最小的顶点k，加入DP1中（选定的距离就是v到k的最短路径长度），以k为新考虑的中间点，修改DPn中各顶点的距离。若从源点v到顶点u的距离（经过顶点k）比原距离（不经过顶点k）短，则修改顶点u的距离值，重复以上步骤直到所有点都包含在DP1中，最终得到源点和其他DP点之前的最小距离。

在实验室调试过程中，分别采用了不含Dijkstra算法的调度系统和含有Dijkstra算法的调度系统分三种情况对AGV进行调度：1）路径中只有两个DP点，两种调度耗时一样；2）路径中含有N个DP点：有Dijkstra算法的调度系统耗时比不含算法的调度系统少(N-2)*[(△L1/△S1)+(△L2/△S2)]；3）路径中含N个DP点、M个转弯，有Dijkstra算法的调度系统耗时比不含算法的调度系统少(N-2)*[(△L1/△S1)+(△L2/△S2)]+Tt；上述算法中△L1为减速距离，△S1为减速度，△L2加速距离，△S2为加速度，Tt为可能产生的多余转弯耗时。通过上述步骤完成项目中34个DP点的最短路径的计算。

3交通管理系统的项目应用所述交通管理系统经试验室测试成功后已应用于北京起重运输机械设计研究院有限公司承建的某物流园生产厂房智能化物流系统中。该智能化物流系统连接企业的ERP系统，通过生产线MES系统和WMS系统调配AGV，按照生产线需求，AGV将原材料、半成品从自动化立体仓库自动发运到生产线上，或将生产线上的成品按照指令自动运送到自动化立体仓库内进行存储。当客户端发出一个任务的指令后，移动机器人智能交通管理系统按照图2所示任务路径流程图调度AGV完成搬运任务。从图2中可以看出，AGV调度策略是在任务分配之后，系统自动选择最优路径，并分配给空闲车辆，实现资源的有效利用。可同时调度多台车辆，遇到多车交汇的情况，遵循先到先得原则。

图2任务路径流程图

图3为该物流园某一车间内AGV路径图及车辆动态示例图。图中线条代表着路径，箭头代表车辆行进方向，一条线两端皆带有箭头，则表明该路径可以双向行驶，图中数字代表车辆的停靠点，车辆可以在停靠点停顿，在货位点进行取货或者放货，当AGV低电量报警时，车辆在交通管理系统的指挥下可以到充电位进行自动充电。

在交通管理系统接收到上位系统指令时，自动选择最短路径，分配给空闲车辆。例如“号车从停靠点P-28出发至货位点L-08的底层取货”，交通管理系统接收到有效指令，生成有效路径（如图4中的粗实线）并派遣指令，AGV按照指令执行任务。如果号车在站点P-05时电池电量低于30%，系统自动报警并生成从该点至充电位的路径，见图5，同时向该车发出指令回充电位充电。AGV在执行完当前任务后会自动去充电位充电。充电结束后，继续接收下一条新的任务指令。

图3某一车间内AGV路径图及车辆动态示例图

图4AGV执行某指令路径及车辆动态示例图

图5AGV回充电位充电路径及车辆动态示例图

4总结介绍了移动机器人智能交通管理软件系统在某物流园生产厂房智能化物流系统中的应用。分析最佳路径算法的原理，采用Dijkstra算法，以最短路径策略应用于车辆调度管理中，并通过实际项目进行验证，提高了AGV的作业效率。

参考文献[1]焦福明.自动化仓储系统AGV调度研究与实现[D].济南：山东大学，.[2]杨丽萍.最短路径算法在校园导游系统中的应用[J].计算机时代,(2).[3]吴家琴.基于迪杰斯特洛模型的物流运输最短路径的选择[J].物流技术,(11).[4]龚劬.图论与网络最优化算法[M].重庆:重庆大学出版社,.[5]卢开澄,卢华明.图论及其应用[M].北京:清华大学出版社,.