多目标复合AGV调度系统建模及在电力计量检定中的应用

邵雪松，高雨翔，宋瑞鹏，冯泽龙，帅　率，马吉科

（1.国网江苏省电力公司电力科学研究院国家电网电能计量重点实验室，江苏南京210019；2.江苏方天电力技术有限公司，江苏南京211102）

多目标复合AGV调度系统建模及在电力计量检定中的应用

邵雪松1，高雨翔1，宋瑞鹏1，冯泽龙1，帅率2，马吉科2

（1.国网江苏省电力公司电力科学研究院国家电网电能计量重点实验室，江苏南京210019；2.江苏方天电力技术有限公司，江苏南京211102）

提出了一种基于车辆行驶距离、任务等待时间与搬运任务优先级的自动导引小车（AGV）多目标复合任务调度模型，通过调整不同因素的权重系数，动态调整模型的性能指标；设计了基于A*算法的AGV调度系统最短路径搜索策略，保证了AGV任务执行效率的最大化；调度模型在超大规模电力计量检定数字化车间中的进行了应用，结果表明该调度模型与路径规划算法具有良好的适应性与可推广性。

自动导引小车；调度系统；路径规划；多目标复合；电力计量检定

自动导引小车（AGV）是依靠电磁、激光、视觉等导航设备，沿着工作站点之间的导向路径，在调度系统的控制下完成一系列运输、装配等作业任务的自动化智能无人搬运车辆［1］。实际生产环境中，通过多个AGV协同作业，以快速高效地完成系统物料搬运、仓储运输等任务。AGV自动运输系统的调度，是指以特定的系统参数为优化目标，对运输任务和车辆进行权重化排列，在此基础上确定合理的分配方案，实现运输任务和车辆间的最佳匹配，从而达到提升系统整体效率、降低运行成本的目的。

AGV系统作为未来自动化物流的重要组成部分，具有广阔的发展前景，调度技术作为AGV自动运输系统的核心技术，应进一步加强其研究。作为一个并发系统，多个AGV同时运行时必然会带来冲突、死锁等问题［2］，将严重影响系统运转效率，降低系统运行可靠性。传统的控制系统一般采用集中调度策略，多AGV的路径规划算法和任务调度过程都在一个中央控制器中实现，当系统中AGV数量增大时，系统的结构和路径规划算法十分复杂。在AGV系统调度方面，柳赛男等给出了在遗传算法的基础上，考虑工艺路线的调度算法［3］；雷定猷等从柔性制造系统的角度，考虑不同任务优先级，提出了以最小化路径总长度为目标的调度模型［4］；金芳等以仓库运输系统作为研究对象，研究了排队理论在AGV调度中的应用［5］；针对混合区域内多AGV的协调调度，也有学者进行了相关研究［6］，Kusiak和Cyrus提出了一种最小化空闲运行时间的遗传算法来解决AGV调度问题［7］。但是，大多数调度策略都是基于“推式策略”（push strategy），不能适应生产模式的需求。

文中从生产系统实际应用需求出发，重点围绕AGV调度系统建模和AGV路径规划，研究多目标复合任务调度模型与AGV路径搜索算法，适应复杂生产场景任务搬运需求，提高系统整体运行效率。

1　多目标复合任务调度模型

1.1多AGV任务调度模型分类

在多AGV系统中，任务调度决定了搬运任务执行的先后顺序和时间长短，任务调度算法的合理性和实用性是影响生产系统运行效率的关键因素，目前常用的AGV任务调度策略有静态任务调度模型和动态任务调度模型2种［1］。

对于静态调度模型，所有的搬运任务已知，在车辆执行任务之前，每一辆车的运行路径都得到了优化确认，离散调度模型算法简单，但是任务环境适应性较差，无法处理实时增加的搬运任务，同时无法应对车辆拥堵、任务变更、车辆充电等情况，因而多AGV静态调度模型已经无法适用生产情况复杂的搬运需求。多AGV动态调度模型实时获取搬运任务状态和车辆状态，根据搬运任务需求灵活调整搬运任务执行顺序，从而能够最小化搬运任务优先级变化、生产任务变更及车辆停用等不确定因素对生产带来的影响。动态调度模型需要实时更新系统状态，在线求解任务分配方案，系统运算复杂度随着选取时间间隔的减小而增大，因此在多AGV动态调度算法中，通常根据实际生产情况确定计算频率，保证系统动态响应的实时性。

1.2多目标复合调度模型

多AGV调度系统多是基于等待时间、队列长度、系统吞吐量、运行距离、车辆利用率等指标所建立。考虑到实际生产过程中，搬运任务执行效率主要反映在车辆运行距离、任务等待时间和任务优先级，文中提出一种基于总的行驶距离、等待时间和搬运任务优先级的多AGV任务调度模型。目标函数如（1）所示：

式中：m为当前任务数；k为当前可用AGV车数；xij=1表示第i个任务被第j辆AGV执行，否则xij=0；dij表示第i个任务被第j辆AGV执行产生的路径长度；ti为当前时刻第i个任务的等待时间；pi为当前时刻第i个任务的优先级；u1，u2，u3为权重系数。

当前复合调度模型的权重系数尚未有明确的分配理论，难以定量分析权重系数的分配方式是否合理，因此文中采用经验法确定权重系数，根据系统表现，动态调整权重比例。

2　路径规划

为了获取AGV初始位置与搬运起始点和目标点之间的最段距离，需要规划AGV行驶路径，同时保证多AGV运行环境下的行驶畅通。

2.1路径特征描述

AGV路径规划中通常存在位置冲突、相向冲突和同向冲突3种冲突类型。位置冲突为多辆AGV同时到达同一位置节点；相向冲突为同一条路径同时只允许1台AGV通过，而2辆AGV相向行驶互不相让发生冲突；同向冲突为多辆AGV在同一路径沿相同方向行驶，后面的AGV行驶速度较快，与前面车辆发生追尾碰撞。针对这3种冲突，在路径设置时应加以限制，避免冲突发生。为了提高AGV系统的适应性和可靠性，AGV路径特征描述如下：

（1）每辆AGV同时只能接收一个任务，在AGV未进入取货路段之前允许任务变更，在AGV进入取货路段之后不允许任务变更，必需执行完当前任务才能接收下一搬运任务；

（2）每辆AGV行驶速度设置相同，根据实际运行情况选择直线速度、转弯速度；

（3）每辆AGV在驶近目标点和驶离目标点时的减速度和加速度设置相同；

（4）每条路段均为单相行驶路线，并且行驶方向固定；

（5）每条路段允许多台AGV同时运行；

（6）车辆之间设置行驶安全距离，避免发生追尾碰撞；

（7）任意2条平行路段之间设置足够的行驶间距，避免发生占道刮擦；

（8）每个路径交叉区域均为单车行驶区域，同一时刻只允许1辆AGV驶入。

2.2A*路径规划算法

当地图环境已知时，为了求解最短路径，国内外学者研究了许多算法，比如遗传算法、神经网络算法、Dijkstra算法及A*算法等［3］。遗传算法模拟染色体的遗传及变异特性，通过编码随机选择初始种群，计算适应函数和选择率，进而模拟交叉、变异行为，判断下代是否满足需求，对于最优路径的求解需要多次迭代，运算复杂度较高。Dijkstra算法的特点在于采用类似等势线的逐级扩展搜索策略，只对部分连接节点进行搜索即可。A*算法作为一种启发式搜索算法，加入了一些限定条件，可以有效舍弃一些路径点，从而增加搜索效率，但是由于A*算法并没有完全遍历所有可行解，所得到的结果不一定是最优解。

综合考虑路径搜索效率，文中选择A*算法搜索最短路径。A*算法可用式（2）描述：

图1　A*路径搜索算法流程

从图1中可以看出，首先将AGV起始位置点设置为起点k，搜索与起点k相连的路径点，并计算k与所有路径点的距离，选择距离最小的路径点作为新的搜索起点继续执行，直到找到目标点为止。

3　电力计量检定车间中的应用

文中提出的多AGV复合指标动态任务调度模型在江苏省电力公司超大规模电力计量检定数字化车间进行了实际应用测试。江苏电能表自动化检定基地采用“机器人+AGV+检定装置”的检定方案，分布有电能表检定装置、自动挂卸表机器人、AGV运输小车及转接台等。智能机器人实现自动挂卸表、条码扫描及视觉定位功能；自动检定装置实现自动压接、翻转及功能检测；AGV小车完成箱垛的输送任务。检定任务开始时，智能电能表通过AGV输送单元从库房接驳处输送到检定单元，智能机器人把电能表从周转箱取出挂到电能表自动化检定装置，机器人挂表的同时完成身份识别；电能表自动化检定装置完成耐压测试、功能及误差检测，检定完成后由机器人把电能表下到周转箱；再由AGV输送到库房接驳处，送至封印贴标线，最后送到自动化库房。在整个任务流程中，AGV系统负责电能表的转接输送，AGV调度系统的可靠性和合理性对电能表自动化检定任务的执行效率起着关键作用［8-12］。

电能表自动化检定AGV路线区域分布如图2所示，检定区根据区域位置划分为4个区：A区、B区、C区、D区，A区设置A1-A5共5条检定线，B区设置B1-B9共9条检定线，C区设置C1-C4共4条检定线，D区设置D1-D4共4条检定线，其中A5线、B1线、B9线、C1线、C4线、D1线、D4线为AGV单边输送路线，其余2条检定线共用1条输送路线，AGV双边伸叉输送。为避免相向冲突，每条输送路径的AGV行驶方向固定，如图中黄色箭头所示。

图2　电能表自动化检定AGV路线区域分布

检定区包含253个取货工位，253个送货工位；接驳区负责检定区和仓储库房的转运接驳，包含3个取货工位和3个送货工位；充电区设置4个充电站点，当AGV电量小于设定阈值时，车辆自动触发充电任务。此外，检定区内设置了若干临时待命点，当车辆处于空闲状态时会自动前往待命点等待任务分配。临时待命点根据区域繁忙程度和车辆行驶便捷性分配，如接驳区承担了整个检定区的电能表转接任务，吞吐量高，因此在接驳区设置了5个临时待命点，以保证接驳任务能够及时搬运。AGV系统共配置了12辆AGV小车，为了避免车辆在路径交叉口处出现死锁和碰撞，为每个交叉口划分唯一车辆通行区域，同一时刻只允许1辆AGV通行，其余车辆原地等待。

图3为某一时刻生产环境中AGV系统测试任务分布情况。对于当前系统缓存里所有AGV任务，调度系统根据任务位置、任务优先级与任务等待时间自动搜索需要先执行的AGV任务。这种多目标复合调度模型能保证AGV任务得到及时执行，确保在整个生产系统AGV数量最小配置下任务执行效率最大化。

图3　AGV任务分布与列表

考虑车辆等待时间、队列长度、系统吞吐量、运行距离、车辆利用率等因素。将AGV多目标复合调度模型与基于时间优先的通用调度策略任务执行能力进行比较，在正常8 h满负荷生产条件下，多目标复合调度策略AGV执行搬运次数1386次，完成单相电能表检定32 080只，三相电能表检定3389只；时间优先调度策略AGV执行搬运次数1155次，完成单相电能表检定26 661只，三相电能表检定3106只。可见，时间优先调度的AGV任务执行效率仅为多目标复合调度下AGV任务执行效率的83%。

4　结束语

针对AGV系统调度及路径规划，提出了基于车辆行驶距离、任务等待时间和搬运任务优先级的AGV多目标复合任务调度模型，解决了实际生产中搬运效率与紧急任务的处理需求。综合考虑车辆冲突、死锁，运行安全性等因素，采用A*算法进行AGV路径规划，求解AGV最短路径，具有较强的实用性。文中提出的AGV任务调度模型与路径规划算法在超大规模电力计量数字化车间取得了较好的应用效果，具有一定的推广应用价值。

［1］白帅福.基于混合区域控制模型的多AGV系统调度研究［D］.南京：南京航空航天大学，2011.

［2］任小龙，温浩宇，李华.基于无向Petri网的多AGV最优路径方法研究［J］.西安电子科技大学学报，2008，35（3）：517-522.

［3］柳赛男，柯映林.一种解决有AGV小车约束的车间智能调度问题的算法［J］.中国机械工程，2007，18（15）：1810-1813.

［4］雷定猷，张兰.AGV系统的调度优化模型［J］.科学技术与工程，2008，8（1）：66-69.

［5］金芳，方凯，王京林.基于排队论的AGV调度研究［J］.仪器仪表学报，2004，25（4）：844-846.

［6］朱琳，范秀敏，何其昌.柔性生产系统配料区多自动导航小车调度优化［J］.计算机集成制造系统，2012（6）：1168-1175.

［7］KUSIAK A，CYRUS JP.Routing and Scheduling of Automated Guided Vehicles［J］.International Journal of Flexible Manufacturing Systems，1995，9（4）：35-42.

［8］黄奇峰，蔡奇新，郑飞.超大规模智能电能表自动化检测研究与仿真［J］.电测与仪表，2013，50（5）：91-94.

［9］刘建，黄奇峰，王忠东，等.基于PlantSimulation的AGV输送系统仿真分析及其应用［J］.现代制造工程，2013（11）：13-15，19.

［10］邵雪松，蔡奇新，黄奇峰，等.电能表自动化检定机器人可靠挂卸表方案设计与实现［J］.电测与仪表，2014，51（16A）：151-155.

［11］黄奇峰，王忠东，蔡奇新，等.电能表自动化检定压接过程动力学仿真分析［J］.科技咨询，2013（33）：109-110.

［12］许海清，黄敏.浅谈电力大数据对信息运行的影响［J］.江苏电机工程，2015，34（2）：62-65.

Multi-target Com pounded AGV Scheduling System M odeling and App lication in Electric Power Metering Calibration

SHAO Xuesong1，GAO Yuxiang1，SONGRuipeng1，FENG Zelong1，SHUAIShuai2，MA Jike2
（1.State Grid Key Laboratory of Electric Energy M etering，StateGrid Jiangsu Electric Pow er Com pany Electric Pow er Research Institute，Nanjing 210019，China；2.Jiangsu Fangtian Electric Technology Co.Ltd.，Nanjing211102，China）

This subm ission proposesamulti-target compounded AGV（Automated Guided Vehicle）scheduling system model based on the driving distance，the taskwaiting timeand the task priority.Themodel'sperformance indicator can beoptimized automatically through adjusting theweight coefficientsof different factors.In order to ensure themaximum efficiency of AGV task execution，the shortest path search strategy is designed according to the A*algorithm.The AGV schedulingmodel is tested in the electric pow ermetering digitalw orkshop.The results show that the proposed method has good adaptability and replicability.

AGV；scheduling system；path planning；multi-target com pounded；electric powermetering calibration

TP391.9，TM 743

A

1009-0665（2016）05-0024-04

邵雪松（1987），男，安徽淮南人，博士，从事自动控制和电能表自动化检定技术研究工作；

高雨翔（1989），男，江苏南京人，工程师，从事电测量技术和自动控制技术研究工作；

宋瑞鹏（1988），男，河南新乡人，工程师，从事电力计量检定技术研究工作；

冯泽龙（1981），男，江苏南京人，工程师，从事电力计量和自动控制技术研究工作；

帅率（1984），男，江苏南京人，助理工程师，从事电力信息化系统设计研究工作；

马吉科（1980），男，甘肃兰州人，从事电力计量检定控制研究工作。

2016-07-01；

2016-07-09