面向多运输任务的节能单负载AGV路径规划研究*

李俊兰 张中伟 吴立辉 武照云

(河南工业大学机电工程学院，河南 郑州 450001)

智能制造已成为全球制造业发展的重要趋势，在“工业4.0”智能制造框架内，智能物流被认为是实现智能制造的核心与关键[1]，而自动导引运输车(automated guided vehicle，AGV)则是实现智能物流的重要物料运输设备。随着全球应对气候变化压力的持续增大，制造业节能减排意识不断提高。物料运输系统是车间制造系统的重要组成部分，其能耗是车间生产能耗中不可忽视的部分。然而，车间节能生产研究长期聚焦在机床，以AGV为代表的物料运输设备较少被关注[2]。因此，研究AGV运输过程的能耗优化问题，对于车间节能生产具有重要的现实意义。

能耗建模是能耗优化的基础技术。围绕AGV能耗建模，目前主要从车辆运动角度进行能量分解，考虑一些实际应用环境因素，如车辆结构特性，电池充放电效率等，基于物理运动学理论进行研究[3-5]。这些工作为量化评估和预测AGV运输能耗提供了指导。进而，一些学者开展了AGV能耗优化研究，例如：王晨曦[6]研究了作业车间AGV绿色物流调度问题，建立了以AGV能耗和调度时间为目标的AGV物流调度优化模型，并提出了一种改进遗传粒子群算法进行求解；笔者研究团队建立了以运输距离和能耗为优化目标的节能单负载AGV路径规划模型，分别提出了两阶段求解方法和基于粒子群优化算法(particle swarm optimization，PSO)的求解方法[5-7]。然而，目前AGV能耗优化研究非常有限，总结可得出结论：①节能路径规划是提升AGV使用能效的一种可行方法，能耗可作为AGV路径规划的独立优化目标；②当AGV执行多项运输任务时，任务的执行顺序会影响节能效果，但当前研究主要面向单负载AGV和单项运输任务，缺乏有效的面向多运输任务的节能AGV路径规划(energy-efficient AGV path planning，EAPP)理论和方法指导。

针对现有AGV能耗优化研究存在的问题和不足，本文以离散制造车间环境下的单负载AGV为研究对象，进行面向多运输任务的EAPP研究，建立了以运输距离和能耗为优化目标的EAPP模型，进而提出一种两阶段求解方法，并通过案例研究验证了模型的节能有效性。

1 问题描述与建模

1.1 模型假设

面向多运输任务的EAPP研究用拓扑地图表示车间环境，将AGV运输网络抽象为一个无向图G=(V,A)，其中V={1,2,…，n}是车辆装/卸货、道路交叉位置等具有特殊意义的节点集合，A={(i,j):i,j∈V,i≠j}是节点之间路径的边集合，且边(i,j)的权重用直接连接节点i和j的路段距离dij表示。在笔者研究团队前期AGV运输过程能耗建模研究假设的基础上[7]，本研究增加以下与运输任务相关的假设条件：

(1)所有运输任务零时刻下达，且AGV可用。一旦AGV开始执行运输任务，不能中断或者取消。

(2)AGV初始不在任意运输任务的起始节点，执行各运输任务时不允许后退或形成回路。当执行完最后一项运输任务，AGV停在其目标节点。

1.2 模型表示

对于零时刻下达的m项运输任务，各任务k(k=1,2,…,m)的取货起始节点Pk和运输目标节点Ck事先给出，Pk,Ck∈V，且Pk≠Ck。定义决策变量xkq表示运输任务k和q(q=1,2,…,m，且k≠q)的执行顺序：

设AGV空载质量为m0，最大载重量为Q。基于研究假设，AGV执行完全部运输任务，交替出现的空载和负载运输阶段总数为2m。AGV在各运输阶段的行驶路径可用其遍历过的有序节点组成的集合Sl表示，l=1,2,…,2m，Sl⊂V，且2≤|Sl|≤n。当l=1,2,…,m时，Sl表示AGV在与运输任务序号相对应的负载运输阶段行驶路径；当l=m+1,m+2,…,2m时，Sl表示AGV在第l-m个空载运输阶段行驶路径。给定Sl时，基于研究假设和物理动力学理论可确定AGV到达各运输任务k起始节点、目标节点的时间TPk和TCk。进而，以全部运输任务的总完成时间Ttotal作为分析AGV能耗的时间边界，其可表示为：

Ttotal=max{TCk},k=1,2,…,m

(1)

分析AGV总运输Etotal需要先计算各运输阶段的AGV能耗，然后累加求和。时间边界以及AGV运输过程能耗的分析计算方法可参考文献[7]。此外，定义整数决策变量yijl来反映各运输阶段AGV行驶经过的边信息：

AGV总运输节点间距离D则可表示为：

(2)

EAPP模型优化目标可表示为：

(3)

约束为：

m0≤Mk≤m0+Q,∀k

(4)

TPq-TCk+H(1-xkq)≥0,∀k,q

(5)

TPk-TCq+Hxkq≥0,∀k,q

(6)

(7)

(8)

(9)

约束条件式(4)中Mk为AGV执行运输任务k时的车辆和货物总重，该式表示AGV在任一负载运输阶段的载荷不应超过其载重极限。式(5)和(6)表示任意两个负载运输阶段不允许时间重叠，其中H是一正极大数，从而可以确定运输任务执行顺序。式(7)和(8)分别表示在各运输阶段规划路径Sl中包含的每个节点只能被访问一次和只能通过一条边离开。式(9)用来约束AGV在各运输阶段不允许后退和环路行驶。

2 模型求解

AGV在各空载/负载运输阶段的可行规划路径Sl往往不唯一，各运输阶段路径规划最优难以保证整体路径规划效果最优。为此，提出一种两阶段方法求解EAPP模型，其流程如图1所示。

在第1阶段，借鉴现有研究成果，例如利用PSO[7]搜索AGV在车间任意两个不同节点间空载行驶时的最佳节能路径，记录对应的Pareto解集。由于各运输任务初始节点、目标节点和工件质量等信息已知，针对每项运输任务对应的负载运输阶段，同法搜索AGV最优节能运输路径，并记录对应的Pareto解集。这些记录信息作为第2阶段利用非支配排序遗传算法(non-dominated sorting genetic algorithm-II，NSGA-II)解决运输任务优化排序以及局部运输阶段最优运输路径的组合优化问题，进而获得完成全部运输任务的最优运输路径的基础信息。在第2阶段，研究重点关注反映问题可行解的种群个体编码方案和遗传算子设计。

(1)个体编码

个体编码应能够反映影响优化目标的决策变量xkq和yijl的信息，设计了一种分段编码的个体编码方案，其示例如图2所示。

个体染色体长度统一为3m，采用实数编码，全部运输任务序号随机分布在前m个基因上；中间m个基因从左到右，按运输任务序号由小到大的顺序依次记录与各运输任务对应的负载运输阶段选择的最优运输路径；最后m个基因从左向右，按空载运输阶段顺序依次记录各空载运输阶段选择的最佳行驶路径。

(2)遗传算子

选择算子沿用标准NSGA-II中的锦标赛选择策略[8]，构建容量是种群规模一半的配对池，后续交叉、变异操作以从配对池中随机选择的个体为父代。

设计了两种交叉算子，示例如图3所示。若两父代个体前m个基因相同，则对它们的后2m个基因进行双点交叉操作；否则先双点交叉前m个基因，并进行合法性校验：依次比对交叉后的子代和父代个体的前m个基因，然后将父代剩余基因按顺序依次替换子代多余基因。进而，子代个体根据交叉后的前m个基因，为各空载运输阶段重新选择最优路径，更新最后m个基因。

针对变异操作，设计了3种使用几率均等的变异算子：①在前m个基因中任选两个不同的基因位，交换其基因值，进而为各空载运输阶段重新选择最优行驶路径，更新最后m个基因；②保持前m个基因不变，随机选择一项运输任务，从其对应的最优运输路径Pareto解集中随机挑选一个不同于当前选择的解，进而更新相应基因位的值；③保持前m个基因不变，随机选择一个空载运输阶段，从其对应的最优行驶路径Pareto解集中随机挑选一个不同于当前选择的解，并更新相应基因位的值。

NSGA-II中非支配排序、拥挤度计算等关键算法过程可参考文献[8]，在此不再赘述。

3 案例研究

结合某航空制造企业的一个制造车间[7]进行案例研究，该车间运输网络拓扑地图如图4所示。

车间现有表1所示的5项常见运输任务。AGV初始停靠在节点44，其技术参数可参考文献[7]。两阶段EAPP模型求解方法在Intel core(TM)i7-8700 3.20GHz CPU，24GB RAM，Windows 10的PC用Matlab语言实现，阶段1利用PSO[7]搜索AGV执行各运输任务的最优节能路径(如表2所示)和在车间任意两个不同节点间空载行驶的最优节能路径；阶段2使用NSGA-II时的关键参数设置如表3所示。

表2 AGV执行各运输任务的最优节能路径

表3 NSGA-II参数设置

为验证应用EAPP模型的节能效果，分两种情形讨论。情形1与车间现行计划一致，AGV按照任务序号依次执行运输任务；情形2下AGV执行运输任务的顺序可优化调整。两种情形下求解模型得到的Pareto解对应的优化目标值如图5所示。

为对比能耗优化效果，在两种情形下分别随机选择一个对应最低运输能耗的Pareto解进行分析，如图6所示。情形2与情形1相比，Etotal降低了15.2%，D缩短了14.5%。然而，两种情形下负载运输阶段的总能耗和总节点间距离相等，说明负载运输阶段优化效果相同。情形2下总体优化效果之所以更优是因为运输任务执行顺序的改变使空载运输阶段总能耗和总节点间距离得以优化。

此外，进一步验证所提EAPP模型求解方法的有效性。阶段1所用PSO的有效性已在文献[7]中进行了论证，故本文针对阶段2使用的NSGA-II，将其与求解多目标优化问题常用的多目标粒子群优化算法(multi-objective PSO，MOPSO)[9]进行对比。

借鉴目前利用PSO解决车间调度以及最短路径搜索问题常用的粒子编码方案[10]，将每个粒子表示为(X1,X2,…,X3m,V1,V2,…,V3m)的形式：前3m个元素标记粒子位置信息，取值分别为[0, 1]内的随机数；后3m个元素记录粒子在搜索空间各维的速度信息，其取值范围为[-1, 1]。由于问题可行解是通过粒子空间位置表达的，对任一粒子，其位置信息的前m个元素用于确定运输任务执行顺序：首先将前m个元素的值按照从大到小排列，然后将各元素的值替换为其粒子编码的位置序号，从而得到运输任务执行顺序。粒子位置信息的中间m个元素从左到右，依次与运输任务编号1～m相对应，视为确定AGV在各负载运输阶段选择哪条优化路径的概率。类似地，粒子位置信息中的最后m个元素从左到右，依次与运输作业任务执行顺序决定的各空载运输阶段相对应，视为确定AGV在各空载运输阶段选择哪条优化路径的概率。在各负载/空载运输阶段，可能存在多条最优运输路径，这些路径被选中的概率相等，具体选择哪条根据轮盘赌法确定。

针对本案例，MOPSO关键参数设置如表4所示。

表4 MOPSO参数设置

基于阶段1提供的基础信息，将NSGA-II和MOPSO分别运行5次，发现两算法得到的Pareto前沿相同，如图5b所示。解码对应最低运输能耗的Pareto解，发现运输任务的最优执行顺序为“2→5→1→3→4”和“1→5→2→3→4”。然而，NSGA-II的平均运行时间(18.816 s)小于MOPSO的(40.675 s)。因此，阶段2所用NSGA-II在同时解决运输任务优化排序和各空载/负载运输阶段最优运输路径选择方面是有效的。

4 结语

针对车间节能生产需求，以单台单负载AGV为研究对象，建立了面向多运输任务，以运输距离和能耗为优化目标的EAPP模型，并提出了一种两阶段模型求解方法。案例研究验证了模型的有效性，当AGV执行多项运输任务时，合理安排运输任务执行顺序和规划运输路径能够提升AGV使用能效。后续将对多负载AGV进行节能路径规划研究。