考虑软时间窗约束的多车型AGV路径优化*

郑晓军，高 佳，宁诗铎

(大连交通大学机械工程学院，大连 116000)

0 引言

近年来，智能工厂在工业4.0的背景下迅速发展，AGV作为智能工厂柔性制造车间内部的主要运载工具，其能耗始终居高不下[1-3]。因此在AGV配送过程中将节能、低碳排放等因素作为综合评价AGV性能的新指标，结合传统经济指标共同构建面向柔性制造车间的AGV调度模型，获得了高度关注[4]。

当AGV在工厂车间执行配送任务时，电池消耗速度与AGV行驶里程、AGV工作时间成正比例关系，因此如何在保持生产效率的同时降低AGV的能耗，实现经济效益与绿色节能的综合优化是未来AGV发展的重要方向和趋势[5-6]。

国内外学者针对有关于节能AGV调度问题开展了广泛研究。ZHANG等[7]为了解决制造车间中AGV调度问题提出了一种采用禁忌搜索算法求解的混合整数线性最优化模型。MOUSAVI等[8]围绕提高AGV运行效率这一问题，研究了AGV的最小使用数以及时间成本的多目标优化。WANG等[9]提出了AGV作业的综合模型用来揭示其动态特征，实现节能调度优化。NOUIRI等[10]以AGV最大完成时间最小化为目标，提出一种改进粒子群算法求解该问题。李强等[11]在估价函数中考虑了AGV行驶和转向时间消耗成本，使用改进后的A*算法搜索其最短时间路径。宋启松等[12]针对AGV行驶路径优化问题，提出了一种改进的遗传算法，引入平滑的适应度函数来光滑及缩短路径。郭亚铭等[13]建立了基于时间窗的单AGV系统路径规划数学模型，并使用A*算法求解。鲁建厦等[14]建立了包括产品成本、多车型、多车辆在内的多约束AGV路径模型，并设计求解该模型的改进混合蛙跳算法。潘迎新等[15]通过优化AGV的任务分配，建立了混合整数规划模型，减少了装卸作业时间，提高了码头生产效率。张博晖等[16]提出了一种基于取货点距离的多载具任务分组算法，优化了AGV的装载效率。

上述学者们均对作业、流水车间中的AGV能耗及其调度问题进行了各式拓展性研究，且均对AGV节能路径的研究有一定帮助，然而较少有学者对AGV配送货物时转弯所带来的能耗进行具体分析。由于AGV转弯运行时速明显低于直线运行时速，可能会造成AGV配送时间延长、配送不及时的现象发生。同时，考虑到单一调用轻载AGV会使车间内部车流量过大，导致AGV陷入路径冲突而造成死锁，延误其配送货物时间；单一调用重载AGV致使单台AGV任务链过长导致配送任务延误的同时难以保证其优良的经济效益，因此传统的单一车型AGV调度很难实现优良的节能效果。

本文在以上研究的基础上，以某工厂的柔性制造车间为研究对象，重点考虑AGV运行过程中直行和转弯两种不同行为模式，建立配送过程中总能耗与软时间窗惩罚成本等多目标节能优化模型，并运用遗传算法求解该模型，最后通过实例验证模型和算法的有效性。

1 问题描述

柔性制造车间中，AGV一般先从始发位置出发，到指定位置装取货物后再送至目标点。此时，需要针对实际情况合理地分配AGV车型及车辆、规划出能够遍历所需任务点的AGV行驶路径。考虑到实际问题的复杂性和不确定性，现预先做出如下基本假设：

(1)车间内只有一个配送中心，陆续驶出轻载AGV及重载AGV，所有从配送中心驶出的AGV完成相应的配送任务后返回配送中心；

(2)轻载AGV单次装载的最大承载能力为100套货物；重载AGV单次装载最大承载能力为200套货物；

(3)AGV运行过程中只包含直行与转弯两种运动状态且都匀速变化；

(4)每个任务点的货物不允许拆分放置于多辆AGV中；

(5)AGV配送过程中不考虑车间具体生产情况、AGV剩余电量及其路径冲突问题等因素。

2 模型建立

2.1 符号及变量定义

2.2 配送过程能耗分析

2.2.1 总成本分析

配送过程中总成本共包括如下3部分：

(1)充电费用Cek：充电时所耗电能与AGV电池剩余电量负相关，设充电时每千瓦时充电费用为Ce，则：

Cek=(EsS+EuU)Ce

(1)

(2)时间窗惩罚成本Ctk：

(2)

若到达时间早于LTn，则需要承担一定的惩罚费用；其中C1为软时间窗的惩罚因子；C2为一个极大值。

(3)AGV响应成本Cwk：在柔性制造车间中，AGV因为之前的装载任务未完成致使新的任务发生时不能及时前往装载点装载物料，导致AGV响应时间较长。因此，若车辆晚于左时间窗LTn抵达装载任务点n，AGV响应成本计算公式为：

Cwk=Ew×(tkn-LTn)

(3)

2.2.2 运动过程能耗分析

由于AGV每次通过路口节点均有直行与转弯两种运动情况，且不同车型的AGV在其运行过程中转弯所产生能耗不同，故需要对直行与转弯的能耗进行具体分析。现设AGV直行总能耗Esum与转弯总能耗Eu，计算如下[13]：

Ft=mtotalgf

(4)

(5)

(6)

(7)

(8)

式(4)中，Ft代表AGV驱动力；g代表重力值，取9.8 N/kg；f代表滚动摩擦系数。式(5)中，Esum代表AGV直行总能耗；v1代表AGV直行速度；t代表AGV直线行驶时间；η为AGV驱动力能效因子与AGV和货物的总体质量、现场环境的动摩擦因数有关。式(6)中，R代表车体转弯半径，与AGV的重心位置有关；v2代表AGV转弯速度。式(7)中，R1、R2、R3、R4分别代表AGV车体中4个车轮的转弯半径；B为车身宽度；L为车身长度。式(8)表示AGV转弯总能耗，其中n代表AGV转弯节点数。

2.3 数学模型与约束条件

根据问题描述，以总配送成本最小化为优化目标，建立带软时间窗的多车型AGV节能路径总目标优化模型如式(9)～式(13)所示。

(1)目标函数

(9)

(2)约束条件

mmin≤mtotal≤mmax

(10)

(11)

(12)

(13)

式(9)为模型的总目标优化函数，保证AGV在行驶过程中产生的总成本最小；式(10)～式(13)为约束条件；式(10)表示AGV与货物的总质量约束；式(11)表示调度车数不超过配送中心车辆总数；式(12)表示每个任务点的货物不允许拆分放置于多辆AGV中；式(13)为决策变量。

3 模型求解

通常求解路径择优问题的算法有Dijkstra算法、A*算法、遗传算法、蚁群算法、粒子群算法等。由于多车型AGV调度问题属于NP-hard问题，约束条件复杂，规模大，而遗传算法具有简便易行、全局择优度佳、鲁棒性好等特点，对复杂的AGV调度问题具有极佳的求解效果，因此本文采用遗传算法作为求解多车型AGV调度方案的模型[12]。

对于所建立的多车型AGV配送过程能耗计算模型，基于遗传算法的节能路径求解流程图如图1所示。

图1 遗传算法节能路径求解流程图

4 实例研究

4.1 实例参数

该柔性制造车间使用的AGV参数规格如表1所示，规定每台AGV在任务点固定停留10 s装取货物。

表1 AGV参数规格表

4.2 数值实例

针对某柔性制造车间的生产数据，AGV配送中心分别对如下20个任务点进行配送服务。配送中心内含2种类型AGV车辆(轻载、重载各10辆，共20辆)以供调度。AGV任务点坐标、装载量、时间窗信息分别如表2所示。设AGV在左时间窗之前到达任务点的等待时间惩罚成本为0.6元/min，AGV转弯时转弯半径R1=R2=1.22 m；R3=R4=0.644 m。利用遗传算法对上述实例进行模拟求解，设置遗传算法参数如下：种群大小M=100，最大迭代次数T=200，以迭代次数作为终止算法的标准，交叉概率pc=0.9，变异概率pm=0.1。

表2 某柔性制造车间生产数据

4.3 实例分析

由于在实际配送货物中，调用不同车型的AGV对总装载成本有很大影响，因此需要合理采用多车型AGV配送方案，以在合理减少车间内部车流量的同时降低AGV配送成本。以3.2 GHz处理器、4.0 GB内存的计算机、MATLAB 2016b作为实验平台，使用遗传算法对上述实例进行仿真。图2为混合AGV配送路径方案图，以每10 m为一个标准单位建立坐标轴，数字“0”表示AGV配送中心，数字“1…20”表示任务点；为遗传算法迭代图。将上述模型重复计算10次，取10次中结果的最小值作为最优值。

图2 混合AGV配送路径方案图 图3 遗传算法迭代次数图

继续采用上述实例对AGV车型分配及路径规划问题进行结果分析，算法求解结果如表3和表4所示。

表3 单一车型调度与混合车型调度路径汇总表

表4 实验结果比对汇总表

在柔性制造车间中，为了确保各个装载点的装载物料准时配送，必须避免多AGV的运动冲突与相遇死锁。此时，应在保证经济效益最佳的情况下合理减少在车间内部执行任务的AGV数量。但当AGV数量过少时，势必会由于单台AGV任务链过长而造成整个柔性制造车间内部的配送任务难以及时响应，影响整个车间的任务准时率；而AGV数量过多，则必然会使AGV运动冲突频繁且引发相遇死锁，导致任务准时率下降甚至造成配送中断现象。因此采用多车型配送方案可以在保证经济效益的同时及时完成装载任务，合理减少车间内部的车流量，降低路径冲突发生的概率。

在柔性制造车间中需同时考虑配送时效性、装载效率及能耗3个方面，同时由于AGV在转弯前需要减速，可能导致配送不及时的现象发生。因此需能在保证其时效性、装载率的同时降低总配送成本。由表4可知，混合车型调度方案与单一轻载AGV调度方案相比：总路径长度缩短近32.8%、减少配送成本近10%、降低转弯次数近12%、减少车间内部约22%的车流量。实现以较少AGV高效完成工件配送任务，有效减少AGV路径死锁发生概率，达到降低能耗、大幅度降低AGV行驶里程，减少工人劳动强度的目的。与单一采用重载AGV配送相比：虽然总路径增加21.9%，但装载率提升至94.4%，转弯成本减少21.3%，总配送成本减少近21.1%。因此采用多车型AGV调度在能够有效减少AGV响应成本、保证平均装载率的同时大幅度降低AGV的配送成本，提升柔性制造车间的自动化程度。

5 结束语

首先，根据AGV在柔性制造车间内配送货物的情况，在考虑转弯对能耗和配送时间影响的情况下，建立了以AGV总能耗最小和软时间窗惩罚成本最小为目标的组合优化模型；其次，设计了基于遗传算法的模型求解方法；实验结果表明在考虑AGV实际装载状况下，路径长度最短并非配送成本最低，因此使用所建立组合优化模型对解决柔性制造车间内部的AGV任务分配及调度问题有较大的实际意义。由于在实际的柔性制造车间中，环境复杂且约束条件较多，因此下一步的研究方向是将多配送中心、AGV拥堵状况等更多实际因素考虑到AGV配送成本的模型中。