带时间窗约束的AGV集配货绿色路径规划问题研究＊
时间：2023-04-25 13:00:05 来源：千叶帆 本文已影响人
郑晓军 高 峰 高 佳 郭星泽
（大连交通大学机械工程学院工业工程系，辽宁 大连 116028）
作为柔性制造车间内物料运输系统的重要载具之一，AGV通常要在规定的服务时间窗内对车间不同工序的工位执行集配货的物流运输任务，因此AGV的工作效率直接影响车间的整体运营效率。随着国务院《关于加快建立健全绿色低碳循环发展经济体系的指导意见》的发布，节能减排已成为我国制造业现阶段的主要发展目标。而如何对AGV行驶路径进行合理规划以降低其运输能耗是亟待解决的首要问题。
因此，本文以柔性制造车间为研究背景，在集配货绿色车辆路径规划问题（the green vehicle routing problem with pick-up and delivery，GVRPPD）的基础上，综合考虑车间的整体运营效率以及节能减排的发展目标，将GVRPPDTW（GVRPPD with time windows）作为本研究的重点。
目前针对集配货车辆路径规划问题的研究大都以配送费用最小及配送满意度最大[1−2]作为组合优化目标：Zou W Q等[3]以最大化配送满意度与最小化配送成本作为优化目标建立AGV路径规划模型，并设计了一种多目标进化算法进行求解。刘雪梅等[4]以物料配送成本最低以及物料到达工位的满意度最高为优化目标建立数学模型，并利用NSGA-Ⅱ算法对模型进行求解。而目前对GVRPPD的研究大都集中在城际物流中，将燃油费用[5]与碳排放量[6]作为优化目标。为实现车间物流运输和节能减排协同发展[7]，学者们针对柔性制造车间内的GVRPPD问题进行深入研究，主要分为两个研究方面：一方面是以AGV的运动状态和路径平滑度[8]作为研究对象：Gao J等[9]从AGV的车身结构与运动状态对AGV能耗特性进行分析，将行驶距离和运输总能耗作为优化目标，建立了针对异构AGV车队的节能路径规划模型；
郭兴海等[10]以行驶路径最短与路径平滑度最大为优化目标，设计了一种以改进QPSO算法与Bezier曲线相结合的两阶段全局路径规划方法。另一方面，在柔性制造车间的物流运输过程中，AGV能耗与车身负载重量成正比例关系[11]。因此，考虑集配货过程AGV车身负载量[12]的变化成为另一研究重点：周炳海等[13]针对混流装配线中AGV先集货后配货的过程将AGV的总重量及行驶时间作为组合优化目标，并提出了一种改进的多目标引力搜索算法对问题进行求解。Wang H F等[14]将AGV运输过程中的车身负载量与AGV行驶速度作为优化目标建立AGV行驶能耗模型，并通过加权指数的方式对配送费用与能耗两优化目标之间进行评估与权衡。
上述学者对集配货车辆路径规划问题作出了拓展性的研究，且均对柔性制造车间内的GVRPPDTW问题的研究有一定的启发与帮助，本文在当今学者研究的基础上，构建一种以AGV集配货过程能耗与时间偏离能耗之和最小化为优化目标的GVRPDPTW模型。并针对所研究问题特性，利用变邻域搜索算法对遗传算法局部搜索能力较弱的劣势进行弥合[15]，设计了一种包含5种邻域结构的改进变邻域搜索的混合遗传算法，最后通过对数值实验进行对比分析，验证本文模型及算法的可行性与有效性。
根据生产作业排程安排与工件加工工艺的要求，车间通常需要多道工序间的配合来共同完成对工件的加工。某柔性制造车间对一同种类型的工件进行加工，AGV在其内部执行物料运输任务，车间内部含有n个工位点，此工件的加工需要两道工序配合完成，将两道工序分别定义为p1和p2，工序之间存在加工顺序优先级的约束，即p1>p2，且每道工序对应的工位均为并行工位。为了保证车间内整体运营效率，要求AGV不能在超过规定时间窗口的最晚时间对工位点进行集配货操作，车间内每个运输周期完成后，AGV将返回充电站进行充电。
为了有效说明所研究的问题作出如下基本假设：
（1）假设车间内部平稳生产，不会出现停机、故障和AGV碰撞等现象发生。
（2）各工位的服务时间窗、二维地理坐标、集配货量已知。
（3）充电站内部存有多台同质AGV，其装载量一致且已知。
（4）AGV执行运输任务时从充电站出发，完成对应运输任务后，最终返回至充电站。
（5）AGV行驶速度恒定，其行驶能耗只与车身负载质量与行驶距离有关。
2.1 符号及变量定义
将AGV运输网络抽象为一个无向图G=(V,A)，其中 V={0}∪{V0}，其中节点0点为AGV的充电站，V0={1,2,···,n}表示工位点集合；
A表示连接各个节点的所有边的集合，A={(i,j)|i,j∈V}。
本文所需变量定义如下：
k为AGV集合K={1,2,3,···,m}中的任意一辆车，m为最大车辆数；
Uijk为第k辆AGV从工位点i行驶工位点j到配货量，(∀i,j∈V0,i≠j)；
Vijk为第k辆AGV从工位点i行驶工位点j到集货量，(∀i,j∈V0,i≠j)；
ETi为 工位点i的时间窗下限；
LTi为 工位点i的时间窗上限；
Ti为AGV到达工位点i的 时间；
dij为AGV从工位点i到工位点j的行驶距离；
xijk为决策变量，若第k辆AGV从工位点i直接到达工位点j，则xijk=1，否则为0。
本文所需常量定义如下：
Q为AGV的最大车身负载量；
Q0为AGV的自身重量；
Pt为 AGV待机功率；
g为重力加速度；
Cr为滚动系数。
2.2 目标函数与约束条件
根据问题描述，建立以柔性制造车间AGV运输过程总能耗最小为优化目标的GVRPDPTW模型。模型的总能耗分别由集配过程能耗与时间偏离能耗两部分组成。
（1）集配过程能耗
为了在充分说明AGV在工位点之间集配货过程的能耗情况，本文以Briand C[16]所提AGV能耗计算方式为建模基础，并根据所提问题特性，现将集配过程能耗Ep定义如式（1）。
（2）时间偏离能耗
由于AGV车身所配置的电池容量有限，过长的待机时间不仅会造成AGV执行车间内部的装载任务时的准时率下降，还有可能导致AGV电池电量过度消耗而无法支持剩余任务的完成。
基于上述分析，为保证对AGV运输过程中能耗问题考虑的全面性，本文定义时间偏离能耗Et如式（2）所示。
上述公式中，式（4）确保派出的AGV数不超过AGV的总数；
式（5）确保每个工位点只被一辆AGV访问，且只被访问一次；
式（6）为消除子回路约束；
式（7）表示AGV从充电站出发后又返回充电站；
式（8）确保AGV运输路线的任一节点的车身负载重量均不超过车身最大负载量，并保证AGV先驶至p1所在工位点进行集货操作后，驶至p2所在的工位点配货；
式（9）～（10）确保AGV从充电站出发并完成所对应的运输任务后返回充电站时，车身负载为0；
式（11）表示AGV对工位点i服务的时间不能超过i点的时间窗上限。
针对柔性制造车间内带时间窗的AGV集配货绿色路径规划问题，所设计的改进变邻域搜索的混合遗传算法流程图如图1所示，其中Gen为当前迭代次数；
GenMax为 预设最大迭代次数；
Iter与IterMax为变邻域搜索当前次数与总次数。
图1 混合遗传算法流程图
3.1 编解码设计
常见的染色体编码方式有二进制编码、整数编码、矩阵编码等。本文根据GVRPPDTW问题特性，采用整数编码的方式对其进行编码操作。针对该柔性制造车间染色体基因总数为n+m。工位点编号为{1,2,···,n−1,n}，AGV小车的编号为{n+1,n+2,···,n+m}，通过向前插入AGV编号使染色体的基因组成多个基因片段，每个基因片段表示集配货任务中的一条路径。
例如：当n=10，m=3时，待服务的工位编号集合为 {1,2,3,4,5,6,7,8,9,10}，AGV编号为 {11,12,13}，则一个可行的染色体为{2,5,4,12,1,6,7,11,9,6,10,8,3,13}，具体编解码操作如图2所示。
图2 解码示意图
3.2 根据集配特性产生初始种群
本文根据集配货问题的特性将初始种群以工位的优先级选择顺序和随机遍历相结合的方式生成初始路径，并对每条路径进行时间偏离优化进而生成初始种群。具体步骤如下：
Step 1：根据车间工位点的编号，分别确定集货点和配货点集合I1、I2。
Step 2：遍历所有工位点，分别从I1、I2中随机选择满足AGV车身最大负载量的集货点和配货点组成一条初始路径。
Step 3：判断集合剩余工位点的货物量是否大于AGV最大车身负载重量，若剩余货物量大于车身负载量则回到Step2，否则收集剩余集合工位点生成最后一条路径。
Step 4：对生成的初始路径在满足集配货问题约束的前提下，根据工位的左时间窗对所有路径进行时间偏离优化，生成初始种群。
3.3 适应度函数
为提高算法求解效率与寻优质量，本文根据所提问题特性，引入惩罚策略对路径进行约束。因此染色体个体Su的适应度函数f(Su)定义如式（12）所示：
其中：α和β表示一个极大数值；
li表示若第u个染色体路径存在违反容量约束的路径则lu=1否则lu=0；
wu表示若第u个染色体路径存在违反时间约束的路径则wu=1，否则wu=0。
3.4 交叉算子
为产生不同的AGV集配货任务分配方案，本文通过OX交叉算子来扩大解空间的搜索范围。如图3所示，首先针对执行交叉操作的两个染色体的交叉位置进行随机选择，进而确定交叉片段，以子代2的生成为例：将父代1中序列4-5-6-7-8作为子代2的第一段，将父代2筛去点位4、5、6、7和8后的序列作为子代2的第二段，同理生成子代1。
图3 染色体交叉操作
3.5 自适应变异算子
为维持种群多样性，防止算法陷入局部最优解，本文在传统的单点变异方式基础上采用一种自适应变异方式对算法全局进行扰动，如式（13）所示。通过染色体的适应度值进行变异概率的自适应确定，减少优秀染色体被变异操作破坏的可能性，从而提高寻优计算效率，加快算法收敛速度。
式中：fmax为迭代过程中种群的最大适应度值；
favg为种群平均适应度值；
f为当前染色体适应度值，k1、k2为常数且k1、k2∈(0∼1)。
3.6 变邻域搜索算法
考虑到遗传算法在求解过程易陷入局部最优解，为了进一步改善解的质量，本文引入变邻域搜索算法对种群中部分最优染色体进行局部搜索操作。并针对本文问题模型特点，设计了基于5种邻域结构的搜索机制，旨在保证算法局部搜索能力的前提下，增加邻域结构的多样性。
（1）基于逆序反转的搜索策略
在染色体内部随机挑选两个基因位置，将两者之间的全部基因进行逆序反转操作。如图4a所示。
图4 邻域结构示意图
（2）不同路径间的搜索策略
①2-2交换：随机选择两条路径，在路径1和路径2中分别随机选取两个工位点进行互换操作。如图4b所示。
②2-0插入：随机选择两条路径，在路径1中随机选取两个工位点依次插入到路径2中。如图4c所示。
（3）同一路径内的搜索策略
①1-1交换：对于同一条路径，随机选择两个工位点进行位置互换。如图4d所示。
②1-0插入：对于同一条路径，随机选择一个工位点将其插入此路径内的任一位置。如图4e所示。
因本文设计的邻域结构较多，每次循环需遍历所有邻域结构。而在算法迭代的不同时期，种群所需的扰动强度不同，为提升算法求解速率，本文采取一种自适应的搜索次数策略。在算法迭代初期采用较低的迭代次数，以此来加快种群收敛；
在迭代后期增加搜索次数，对染色体进行深度搜索。具体公式如式（14）所示。
式中:NSnum表 示第gen代染色体的变邻域搜索次数；
ρ1表 示变邻域搜索的最小次数；
ρ2表示自适应搜索次数；
MAXgen表示算法预设的最大迭代次数；
⎿」表示向下取整。
变邻域搜索操作步骤如下：
Step 1：初始化参数，并根据式（14）自适应确定最大搜索次数IterMax。
Step 3：随机选择两条路径，对路径1和路径2分别进行2-2交换以及2-0插入的搜索操作，得到满足≥f(Su)的新解。
Step 4：遍历所有AGV的运输路径，针对路径内部进行1-1交换和1-0插入。得到满足≥f(Su)的新解。
Step 5：判断是否达到自适应搜索次数的最大值，若Iter>IterMax则重新编码生成优化后的染色体，否则回到Step2。
本节实验共分为两组，第一组实验采用Solomon的标准算例库进行数值实验，并与已知国际最优解进行数据对比，验证本文设计算法的可行性；
第二组实验以某工厂柔性制造车间实际生产过程中某一时段的生产数据作为实验案例，通过与GA和VNS算法所求结果进行实验对比，验证本文算法有效性。
所有仿真实验均在加速频率为2.6 GHz的Inter i5-9400处理器、运行内存为16 GB的Windows10PC平台进行，其中程序编译和运行环境为MATLAB R2018b。算法的实验参数设置如下：种群规模P=100、迭代次数GenMax=300、交叉概率Pc=0.9、自适应变异式中k1=0.05,k2=0.1、自适应变邻域搜索次数式中 ρ1=20,ρ1=100，模型中的g=9.8N/kg，Cr=0.71。
4.1 算法可行性验证分析
柔性制造车间内部的GVRPPDTW问题为经典VRP的延伸问题，为了验证本文算法的可行性，本文测试数据选自Solomon标准测试数据集[17]。该数据集共分为6大类，即C1、C2、R1、R2、RC1、RC2，其中C类与R类分别表示客户点分布为密集和随机；
RC类则介于两者之间，1和2作为时间窗紧密和宽松的表达形式。
为保证数值实验的全面性与完整性，本文分别针对客户点规模、客户地理位置分布情况选取部分算例进行实验,并对每个算例重复计算10次，取10次结果中的最优值，计算结果如表1-3所示。
表1 客户规模为25的算例求解结果
表2 客户规模为50的算例求解结果
表3 客户规模为100的算例求解结果
由表中数据分析可知，客户数量为25的小规模算例相较于国际最优算例的平均偏差为0.27%；
客户数量为50的中规模算例平均偏差为0.41%；
客户数量为100的大规模算例平均偏差为1.27%；
从上述求解结果来看，本文算法与已知国际最优解偏差较小，对于不同规模的算例均能求得近似满意解。因此，本文算法的可行性得以验证。
4.2 算法有效性验证分析
以某工厂柔性制造车间为背景，所建立的车间拓扑地图如图5所示，共由包括AGV充电站在内的27个节点，32条边组成。其中编号0为AGV充电站，编号1～13与14～26分别表示集货工位点与配货工位点。本文通过截取实际生产过程中某一时段的生产数据来构造本次实验案例，如表4所示。
表4 工位点信息
图5 车间拓扑地图
车间内共有5辆AGV，本次实验所需AGV具体参数如表5所示。
表5 AGV参数
为了验证本文算法求解的有效性，在本文设计的案例条件下与GA，VNS算法的计算结果进行实验分析。3种算法实验条件及参数相同，每种算法重复计算10次，取计算结果中的最优值，如表6所示。
表6 各算法运行结果比较
根据实验所得数据，本文所设计的算法在集配过程能耗与时间偏离能耗方面，较GA优化了3.9%与67.7%，较VNS算法优化了0.7%与37.4%，在AGV运输总能耗方面能够分别降低7.1%与1.6%。这是因为本文将两种算法优势互补与改进，优化了总运输路线中AGV对工位点的服务顺序，从而使AGV运输过程的能耗与行驶距离得到平衡，并且本文所设计的算法所求解的行驶路线能够将AGV对更多工位的服务时间控制在其对应的时间窗口内，因此在优化AGV运输过程总能耗问题中，本文所设计的算法求解质量更高，且针对实际生产案例也表现出良好的寻优能力，使得本文算法的有效性得以验证。
本文针对柔性制造车间背景下带时间窗约束的AGV集配货绿色路径规划问题进行了研究，得出结论如下：
（1）以最小化AGV集配过程能耗及时间偏离能耗作为组合优化目标，构建AGV绿色车辆路径规划模型，能够相对客观全面地反映柔性制造车间内部AGV运输总能耗的情况。
（2）设计了一种改进变邻域搜索的混合遗传算法用于求解本文所研究的问题，并针对问题特性设计了5种邻域结构的搜索机制；
首先通过Solomon算例验证本文所设计算法的可行性，然后与GA和VNS算法进行实验仿真，最终的实验结果表明，本文所设计的算法在求解质量上均优于GA和VNS算法。
本文研究的带时间窗约束的AGV集配货绿色路径规划问题柔性制造车间运输能耗问题，为了进一步实现车间节能减排的发展目标，后续，将针对节能视角下的加工资源和运输资源集成调度问题进行深入研究，并对求解算法作出进一步优化。
猜你喜欢算例邻域工位LCA在焊装车间人工上件工位应用和扩展汽车工艺师(2021年7期)2021-07-30精确WIP的盘点方法物流技术与应用(2020年5期)2020-06-25工位大调整意林(2020年10期)2020-06-01稀疏图平方图的染色数上界吉林大学学报（理学版）(2020年3期)2020-05-29基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20关于-型邻域空间周口师范学院学报(2016年5期)2016-10-17基于振荡能量的低频振荡分析与振荡源定位（二）振荡源定位方法与算例中国学术期刊文摘(2016年2期)2016-02-13滨江:全省首推工位注册杭州(2015年9期)2015-12-21互补问题算例分析新乡学院学报(2015年6期)2015-11-06基于CYMDIST的配电网运行优化技术及算例分析电网与清洁能源(2015年2期)2015-02-28 相关热词搜索：路径，约束，配货，
