An Improved Migrating Bird Optimization Algorithm for Multi-AGV Scheduling in Job Shop under Delivery Constraints
-
摘要:
在矩阵式排列的加工车间中,工件由自动导引车(automated guided vehicle,AGV)从加工站转运到下游物料超市,且需满足极其紧凑的下游交货期限制,以便稳定生产秩序、缩减在制库存、降低运输成本。为此,本文建立多AGV调度规划模型,并提出改进多目标候鸟优化算法,以实现及时送达率高、运输成本小的目标。其中,以目标为导向,提出基于最早交货期的交付时间确定和AGV分配规则,实现无延迟、少库存的可行解解码;设计融入贪婪操作、基于理想点的局部搜索算子,促成Pareto前沿推进;设计融入高价值信息的两点交叉算子与劣解接收准则,确保Pareto解集多样性和收敛性。实验表明所提算法可有效求解该问题,获得的Pareto前沿解集在超体积率和逆世代距离指标上性能更优。
Abstract:In a matrix-arranged job shop, the finished workpieces are transported via automated guided vehicles (AGVs) from processing stations to downstream material supermarkets. This process needs to satisfy extremely tight time constraints of downstream delivery to stabilize production flow, reduce work-in-process inventory, and minimize transportation costs. To this end, a multi-AGV scheduling model is formulated and an improved multi-objective migrating bird optimization algorithm is proposed with the objectives of maximizing on-time delivery ratios and minimizing transportation costs. Specifically, objective-oriented delivery time determination and AGV allocation rules based on the earliest delivery deadline are proposed to achieve feasible decoding with no delay and minimal inventory. A Pareto front advancement mechanism is facilitated through a greedy operation combined with an ideal-point-based local search operator. A two-point crossover operator and an acceptance criterion of inferior solutions considering high-value information are proposed to ensure the diversity and convergence of the Pareto solution set. Experimental results indicate that the proposed algorithm can solve the problem effectively, achieving superior performance in terms of IGD and HVR indicators for the obtained Pareto frontiers.
-
随着客户个性化程度增加,生产模式从传统的单品种、大批量、长周期逐步转变为多品种、小批量、少库存,部分企业的产品制造过程也演变为加工和装配两个核心阶段[1]。加工阶段重在完成差异化、个性化的零部件制造,装配阶段将零部件焊装、铆装或组装到一起,形成终端产品。由于个性化,零部件之间的互换性减小,装配过程中很难互相替代,在从加工到装配的物料转运过程中,需重点关注各零部件的及时配送,避免因物料短缺导致下游生产中断,造成重大经济损失。零部件准时化供应是制造过程连续生产的关键[2],自动导引车(automated guided vehicle,AGV)承担着上下游工序之间的物料转运任务。如何进行多台AGV的并行调度,在尽量满足下游工序指定的零部件交货期的前提下,低成本地完成物料转运任务是亟须解决的问题。
多AGV调度是在小车装载量、下游工序交货期等限制下,给每台AGV的各趟行程指派物料转运任务、规划行走路线,完成取货、运货、卸货、返回等一系列的作业指令[3]。围绕多AGV调度,Zou等[4]聚焦了矩阵布局加工车间内的原料提货和成品配送;徐立云等[5]考虑了柔性加工单元内的在制品流转;李昆鹏等[6]关注了制造过程中半导体的批次转运;Zhou等[7]研究了从物料超市到混流装配线的零部件配送。不同于上述研究,本研究的下游工序是装配,生产中断的损失极大,如特斯拉 Model 3/Y停产一天损失高达8.2亿;此外,拉式生产使得制造过程前后工序衔接紧凑,物料转运时间裕量不大。故而,在从加工车间到下游工序的物料转运时,会明确设置交货期,避免延期交付,导致该问题转化为一类交货期限制下的多AGV调度问题。在求解时不仅应关注单台AGV的多行程运输作业和多台AGV的并行调度,更应关注每台AGV每趟行程的任务分配,保证物料的准时交付。
多AGV调度问题是NP难问题[4],主要有精确算法、启发式和元启发式3类求解方法。在精确算法层面,Li等[8]提出分支定界法,Fazlollahtabar等[9]采用改进的网络单纯形算法,求解到小规模案例的最优解。在启发式和元启发式算法方面,Zeng等[10]提出了融合时间表与局部搜索的两阶段启发式算法,Zhang等[11]提出了改进的迭代贪婪算法,Dang等[12]将局部搜索融合到自适应大邻域搜索算法中,均用于求解中到大规模问题。交货期限制下的加工车间多AGV调度问题 (job shop automated guided vehicle scheduling,JS-AGVS) 更具挑战性。首先,AGV物料转运受上游加工完成时间限制,还受下游交货期限制,转运时间间隔小,难以产生可行调度解;其次,既要保证交付及时性,又要降低在制品库存,难以实现二者间的平衡。为此,需要设计高效的多目标调度算法,合理编制AGV转运方案。候鸟优化算法具有收敛性强、结构简单的优势,在生产调度[13]、车辆路径规划[14]等问题中已取得良好的效果。然而,算法存在对初始解质量和问题特性敏感、解空间探索能力有限等局限性,需改进算法,提高其收敛性和鲁棒性。
为此,本文针对交货期限制下加工车间多AGV调度问题,建立混合整数线性规划模型,并提出改进多目标候鸟优化算法 (improved multi-objective migrating birds optimization algorithm,IMMBO) 进行求解,改进之处包括:1) 以目标为导向,提出基于最早交货期的交付时间确定和AGV分配规则,实现无延迟、少库存的可行解解码;2) 设计融入贪婪操作、基于理想点的局部搜索算子,靶向搜索优质解空间,促成Pareto前沿推进;3) 设计融入高价值信息的两点交叉算子与劣解接收准则,平衡全局探索与局部勘探,确保算法多样性及收敛性。在下游工序期望交货期限制下,最大化利用每台AGV的运输能力,为企业带来更高的经济效益。
1. 问题描述与模型建立
1.1 问题描述
加工车间和下游工序物料超市相距较远,由一条具有无限能力的运输道路连接。为满足下游工序所需物料的准时化供应,AGV需往返于加工单元和下游工序物料超市间,成批、准时地进行物料转运(见图1)。道路起点是AGV停靠点,与加工车间相连;终点是下游工序的物料超市。在各零部件完成加工后,AGV从停靠点出发,依照最短路径从加工车间序次取走物料,送抵下游工序物料超市;继而返回AGV停靠点,等待下一趟行程。加工车间依据工艺中心原则进行矩阵式布局,不同颜色片区为不同的加工中心,如车削、铣削、刨削、磨削;物料超市负责接收零部件,及时响应下游工序生产需求。
交货期限制下加工车间多AGV调度问题 (JS-AGVS) 是以满足交货期约束为前提,基于AGV数量、运输能力、运输速度等信息,确定每辆车每趟行程执行的任务数、任务号及运输路径,准时配送物料到下游超市,避免因物料短缺造成下游工序生产中断;同时最小化运输趟数,以降低运输成本。
为简化问题,做出如下假设:1) 车间生产和运输设备正常工作,不考虑设备故障停机及AGV避障等;2) 每台AGV配置相同;3) 每趟转运始于停靠点,依规划路径顺次取走物料,抵达物料超市,再回到停靠点;4) AGV装卸货时长固定;5) 每个转运任务仅由一台AGV在一趟行程中完成;6) 每个任务须在规定时间窗内完成,以满足交货期限制;7) 每趟行程载重不超过AGV装载能力;8) AGV匀速行驶。
1.2 符号定义
为描述本文求解问题,引入以下参数和变量,如表1所示。
表 1 符号和定义Table 1. Symbols and their definitions种类 符号 说明 集合 C 任务集合,i,j∈C,i,j=0,1⋯n,n+1,其中0为停靠点,n+1为下游工序物料超市 K AGV集合,k∈K,k=1⋯K′ M 零部件集合,m∈M,m=1⋯M′ R 运输趟数集合,r∈R,r=1⋯R′ 参数 n 任务数 K′ AGV总数 M′ 零部件种类数 R′ 单台AGV的最大趟数 xi 任务i的横坐标 yi 任务i的纵坐标 ci 任务i的呼叫时间 di 任务i的最晚交付时间 a 每个任务的装货时长 β 每个任务的卸货时长 dij 任务i到任务j的行驶距离 taij 任务i到任务j的行驶时间 φ 足够大的正数 wm 单个零部件m的重量 nmi 任务i所转运零部件m的总数量 qmi 任务i所转运零部件m的总重量,qmi=nmiwm s 每台AGV一趟行程所能执行的最大任务数 q 每台AGV最大载量 qik 第k台AGV执行任务i后的载重 w1 单台AGV执行每趟行程的启用成本 w2 单位运输距离所耗费的成本 Ct AGV启用成本 Cv AGV行驶成本 变量 Xijkr 0-1变量,若AGV k在r趟行程中从任务i所在位置直达任务j位置,xijkr=1;否则xijkr=0 Ukr 0-1变量,若AGV k需执行第r趟行程,则Ukr=1;否则Ukr=0 Tbkr 连续变量,AGVk在第r趟行程从停靠点出发的时间 Tekr 连续变量,AGVk在第r趟行程回到停靠点的时间 DAi 连续变量,任务i到达物料超市的时间 Tsj 连续变量,加工阶段执行任务j的零部件装货时间 1.3 模型建立
根据所描述的问题,建立如下模型。
minf1=n∑i=1(di−DAi); (1) minf2=Ct+Cv=w1K∑k=1R∑r=1Ukr+w2K∑k=1n+1∑i=0n+1∑j=0R∑r=1xijkrdij。 (2) s.t. Ukr⩾Uk,r+1,∀k∈K,r<R; (3) n+1∑i=1n+1∑j=0xijkr⩽s,∀k∈K,r∈R,i≠j; (4) φUkr⩾n∑i=1n+1∑j=0xijkr,∀k∈K,r∈R,i≠j; (5) n+1∑j=1xijkr=Ukr,∀k∈K,r∈R,i=0; (6) n+1∑i=1xijkr=Ukr,∀k∈K,r∈R,j=n+1,i≠j; (7) K∑k=1n∑i=0R∑r=1xijkr=1,∀j∈V∖{0,n+1},i≠j; (8) K∑k=1n+1∑j=1R∑r=1xijkr=1,∀i∈V∖{0,n+1},i≠j; (9) xijkr+xjikr⩽Ukr,∀i∈V∖{0,n+1},j∈V∖{0,n+1},i≠j; (10) Tbkr+taij⩾Tsj−φ(1−xijkr),∀k∈K,r∈R,i=0,j∈V∖{0}; (11) Tbkr+taij⩽Tsj+φ(1−xijkr),∀k∈K,r∈R,i=0,j∈V∖{0}; (12) Tsi+a+taij−Tsj⩽φ(1−xijkr),∀k∈K,r∈R,i∈V/{0,n+1},j∈V/{0,n+1},i≠j; (13) Tsi+a+taij−Tsj⩾−φ(1−xijkr),∀k∈K,r∈R,i∈V/{0,n+1},j∈V/{0,n+1},i≠j; (14) Tsi⩾ci,∀i∈V∖{0,n+1}; (15) Tsi⩽di,∀i∈V∖{0,n+1}; (16) Tekr⩾Tsi+a+taij+tan+1,0−φ(1−xijkr),∀k∈K,r∈R,i∈V/{0,n+1},j=n+1; (17) Tekr⩽Tsi+a+taij+tan+1,0+φ(1−xijkr),∀k∈K,r∈R,i∈V/{0,n+1},j=n+1; (18) DAi⩾Tekr−ta0,n+1−φ(1−n+1∑j=0xijkr),∀k∈K,r∈R,i∈V/{0,n+1}; (19) DAi⩽Tekr−ta0,n+1+φ(1−n+1∑j=0xijkr),∀k∈K,r∈R,i∈V/{0,n+1}; (20) DAi⩽di,∀i∈V/{0,n+1}; (21) Tekr⩽Tbk,r+1,∀k∈K,r<R; (22) n+1∑i=1n+1∑j=0M∑m=0qmixijkr⩽Q,∀k∈K,r∈R,i≠j。 (23) 式 (1) ~ (2) 为目标函数,分别优化及时送达率及运输总成本。考虑到所有物料必须在规定交货期送达,同时期望降低下游超市的总库存量,故使用实际与期望交付时间的偏离值来表征物料送达的及时性程度,偏离值越小,及时送达率越高。运输总成本包含了执行多趟运输任务的AGV启用成本和行驶成本。
1) 运输顺序约束,聚焦于是否执行每趟行程及该行程的任务执行顺序。围绕每趟行程,式 (3) ~ (5) 强调每台AGV一定是执行完前一趟行程后,才开始下一趟;每趟行程所执行任务数不大于给定值;即便某趟行程仅有一个任务,也须执行。围绕每趟行程的任务执行顺序,式 (6) 要求从停靠点“0”出发;式 (7) 表示每趟行程需经物料超市“n+1”;式 (8) ~ (9) 确保每趟行程除第一个和最后一个任务外,各任务仅有一个前序和一个后序;式 (10) 表示两个任务
i 和j 若在一趟行程中连续执行,可i 在j 之前,或j 在i 之前,两者不可并存。2)每趟行程时序约束,每趟行程从停靠点出发、在加工车间序次装载物料、到下游超市下货、回到停靠点4个过程。式 (11) ~ (12) 规定了每趟行程首个任务物料装载开始时间,等于其开始时间加上从停靠点到该任务所在位置的行驶时间。式 (13) ~ (14) 依照任务执行顺序,在前一任务的物料装车后,按照最短路径行驶到后一任务所在位置。式 (15) ~ (16) 强调须保证每个任务在规定时间窗内执行。式 (17) ~ (18) 表示每趟行程结束时间为全部物料装车完成,经停靠点“0”行驶到下游超市下货后,回到停靠点“0”的时间。式 (19) ~ (20) 表示物料交付时间即为到达下游超市时间。式 (21) 限制每个任务的物料交付时间不晚于期望交付时间,确保下游生产按计划进行。
3)同一AGV连续两趟行程间的时序约束,式 (22) 针对同一辆AGV相邻两趟行程,其前一行程的完成时间应不晚于后一行程的开始时间。
4)运输装载约束,式 (23) 要求每台AGV每趟行程的装载量低于最大载重。
该模型为混合整数线性规划模型 (Mixed Integer Linear Programming,MILP),可使用商业化数学软件GAMS/Cplex或IBM/Cplex进行求解。该模型通过将优化问题转化为数学形式为算法提供了优化框架,使得算法能够直接操作这些数学对象进行求解。算法可以针对MILP模型中的目标函数和约束条件,设计搜索策略、启发式算法等来求解问题。
2. 改进多目标候鸟优化算法
候鸟优化算法是一种元启发式算法,它模拟候鸟迁徙过程,由比较强壮的鸟在前面领飞,其他鸟排列在领飞鸟左右两侧,整个鸟群呈V字形。在鸟群飞行过程中,利用前方鸟翅膀扇动形成的气流减少跟飞鸟的能量消耗,完成整个鸟群的迁徙。本文选取该算法主要原因包括:1) 该算法实现了种群个体之间的信息共享和交流,从而在搜索空间中能更快速地找到全局最优解;2) 该算法由Duman等[15]首次提出用于求解二次分配问题并被证明所获得的解优于遗传算法、模拟退火算法等,已在生产调度[13]、车辆路径规划[14]等问题得到很好的实验结果。尽管其具有较优的性能,但用该算法在求解多AGV调度问题的研究较少。因此,针对JS-AGVS这一特定问题,设计了改进多目标候鸟优化算法 (IMMBO)。
面向MILP模型中的目标,设计特定的编码方式并提出基于最早交货期的交付时间确定和AGV分配规则;考虑到问题的多种约束条件,设计基于最早交货期的可行性判定规则,以确保解码的有效性;设计搜索策略,以实现算法的整体高效寻优。
2.1 编码
假定加工阶段有
n 个任务,采用z趟运输将其转运到物料超市,需采用长度为z+n+1的一维向量来表示。该编码形式为
π={0,π1,0,π2,0,⋯,0,πm,0} ,其中πk=(πk,1,πk,2,⋯,πk,nk) 表示第k 趟行程及其任务执行序列,nk 为第k 趟行程的总任务数,0用于分隔每趟行程,0出现的总次数为z+1。以10个任务为例,假设其编码为{0, 8, 7, 9, 0, 3, 2, 1, 0, 5, 4, 6, 0, 10, 0},则需要4趟运输。其中第1趟任务执行序列为{8, 7, 9},第2趟为{3, 2, 1},第3趟为{5, 4, 6},第4趟为{10}。2.2 基于最早交货期的时序确定和AGV分配规则
为保证及时交付,实际交付时间须早于交货期,才能确保下游生产顺行,避免因物料延迟造成下游生产中断。此外,实际交付时间与交货期的偏离程度应该尽量低,以减少物料超市库存。为提高及时送达率和AGV的使用率,故提出如下两个规则:
1)基于最早交货期的交付时刻确定规则。每趟行程实际交付时间 (
Tekr−Ta0,n+1 ) 等于其最早交付零部件的交货期(minidi) ,并依据装车顺序及最短路径,倒推该趟行程开始时间、每个任务装货时间,并顺推出回到停靠点的时间等。由于每趟行程按照最晚时间(即最早交付零部件的交货期),故而不存在交付延迟,所产生的在制品库存也最少。并且,基于本规则,确定了每趟行程的理想开始时间、理想结束时间。2)基于贪心策略的AGV多行程分配规则。面向每趟行程的理想开始时间,按照“先空闲、先使用”规则,从多台可用AGV中选择最早抵达停靠点者执行下一趟行程,即
k∗=argmink,rTekr。 (24) 以图2为例,针对指定的编码,可计算得出每趟行程最早交货期(红色虚线),且算出每趟行程、每个任务的装货和卸货时间。再按照AGV多行程分配规则,将第4趟行程分给第2辆AGV,获得多AGV转运甘特图。
2.3 基于最早交货期的可行性判定规则
上述解码过程设定了恰好在最早交付零件的交货期,将当次行程的全部物料一起送达。由于AGV数量受限、各零部件加工完成后可配送时间受限、每趟行程最大载重量和任务总数受限,所生成的编码很可能是不可行的。为此,需快速判断解的可行性,剔除不可行解,制定解的可行性判断逻辑。
算法1:解的可行性判定 输入:一个完整解(图2(a)); 输出:该解的可行性。 步骤1 计算每趟行程的任务数,若其大于规定值 s ,则判定该解不可行,退出该程序;否则执行下一步。步骤2 计算每趟行程装载量,若其大于规定量 Q ,则判定该解不可行,退出该程序;否则执行下一步。步骤3 计算各任务在加工阶段的装货时间 Tsi 。针对每趟行程,确定最早交付零部件的交货期mini{di} 和回到停靠点的时间;考虑行驶时间和装料时间,依照编码顺序,由后向前顺次反推各任务在加工阶段的开始时间Tsi 。若开始时间Tsi 早于该任务的加工完成时间,即Tsi<Ci ,则判定该解不可行,退出该程序;否则执行下一步。步骤4 计算每趟行程的开始时间和完成时间。 步骤5 依照每趟行程的最早开始时间,依次进行AGV分配。若即将进行AGV分配的行程的开始时间小于当前各AGV正在执行行程的完成时间,即无AGV可用,则判定该解不可行,退出该程序;否则判定该解为可行解。 2.4 种群初始化
初始解性能对算法求解的速度和质量有较大影响,为加快算法收敛,融合随机初始化与可行性判定,生成高质量可行初始解。其中,基于随机的初始解生成方法如下。
随机产生完成全部任务所需的总趟数
m=rand(K,n) ,其中K 表示AGV总数,n 表示总任务数;随机生成除最后一趟行程外的每趟行程执行任务数s′=rand(1,s) ,将余下尚未分配的任务数全部分给最后一趟行程,且需保证最后一趟行程所分得的任务数满足s′⩽s ;将每个任务随机分配给上述行程中的任一趟。在每个解的生成方法基础上,利用下述流程得到一个具有可行性的初始种群。具体为:反复启用随机方法,产生初始化个体,直至获得
2N+1 个可行解;在此基础上,利用Pareto占优关系和拥挤距离进行排序,挑选出排在前面的N+1 个个体,构建部分初始种群;再次启用随机方法,产生N 个可行解,置入初始化种群中,形成规模为2N+1 的初始化种群。2.5 贪婪操作算子
为引导个体朝着期望方向进化,邻域结构的设计起着重要作用。为了改善算法整体的搜索性能和收敛速度,本文针对领飞鸟的进化过程采用了贪婪交换操作和贪婪插入操作两种邻域结构,具体操作为:贪婪交换(插入)操作是从当前领飞鸟所表示的解中随机选取一个任务
i ,将其与当前解中其他任务进行交换(或插入到其他任一位置),产生n−1 个邻域解。对这n−1 个邻域解根据Pareto占优关系和拥挤距离进行排序,找到当前邻域解集中排序第一的解,获得当前最优邻域解。2.6 融入高价值信息的交叉操作
针对跟飞鸟进化过程,设计了一种基于非支配解中高价值信息的两点交叉算子,具体分为如下两步。
第一步是基于非支配解中高价值信息,生成一个优质个体。具体如下:针对非支配解集,去除每个解中的“0”,然后对每个任务在每个位置出现的次数进行统计;在每个位置放置出现次数最多的任务,从而生成一个综合性能较优的优质个体。假设有7个任务,有6个非支配解,分别为{1, 5, 4, 7, 2, 3, 6}、{1, 3, 4, 7, 5, 2, 6}、{1, 5, 4, 6, 2, 3, 7}、{1, 6, 7, 4, 3, 2, 5}、{3, 5, 7, 4, 2, 6, 1}、{1, 5, 4, 7, 6, 3, 2}。可以看出,在第一个位置任务1出现5次,任务3出现了1次。因此将任务1放置到第一个位置,依次类推,可得优质个体{1, 5, 4, 7, 2, 3, 6}。
第二步是结合优质个体信息,设计基于两点交叉的跟飞鸟交叉操作。其步骤为:选取当前与同侧随后的两个跟飞鸟作为父代1和2个体;将两个编码中的“0”去除;将父代1个体与优质个体相比对,将相同位置相同任务放到子代1个体的同一位置上;随机选取两个位置,将父代1中首/尾片段信息直接赋给子代1,将父代2中余下信息依序赋给中间片段;最后,将“0”随机插回编码中,生成最终子代个体。
2.7 接受准则
在原始MBO算法的跟飞鸟进化过程中,仅当邻域解比当前解好时才会替换,导致算法易于陷入局部最优。因此,引入式 (25) 所示的概率接受准则,在一定程度接受劣解。其机理是:随机从两个目标中选出一个目标
fx 。如果生成的新解s′ 在该目标上好于当前解s 则保留新解;否则通过一定的概率接受。具体概率接受操作如下:首先依照式 (25) 计算接收概率P ,接着生成一个0 ~ 1随机数,如果P 大于该数,则替换当前解;否则,保留当前解[16]。 其中,T 为当前温度。P=exp(−fx(s′)−fx(s)Tfx(s))。 (25) 2.8 基于理想点的局部搜索
为了加强算法的局部勘探能力,需将其引导到更富潜力的解空间。为此,采用了基于理想点的局部搜索策略,驱动算法朝着理想点(即所有维度目标值均为当前最好值的点)前进。该驱动过程是在执行邻域搜索后,比较当前解或新解与理想点的欧氏距离,利用贪婪准则接受新解。其中,欧氏距离用式 (26) 计算。
d(πi)=√(f1(πi)−α1)2+(f2(πi)−α2)2,i=1,2,⋯,n。 (26) 其中,
f1(πi)、f2(πi) 分别表示邻域解πi 对应的第一、第二个目标函数值,即及时送达率和运输总成本。α1 、α2 分别表示当前目标函数f1、f2 的最好值,即理想点α 为 (α1,α2 )。当解离理想点的距离d(πi) 越小,该解的综合性能越优。针对JS-AGVS问题,设计了两种局部搜索算子:反转操作算子和基于参考解的插入操作算子[17]。反转操作算子是在任意一条路线或者两个不同的路线中,随机选择两个任务位置进行对调,其他位置保持不变。基于参考解的插入操作算子具体见文献[17]。基于参考解的插入操作算子具有显著的有效性,但其计算复杂度大,计算时间成本高。因此,采用一种随案例规模变化的适应性算子选择概率公式[4],如式 (27) 所示。
p=2n/103n/10。 (27) 其中,
n 为总任务数。从公式中可以看出,随着总任务数的增加,概率降低,基于参考解的插入操作算子的使用将会减少。故此,基于理想点的局部搜索步骤为:1)生成一个0 ~ 1的随机数并依据适应性算子选择概率公式计算选择概率
p 。2)若该随机数不小于p ,则对当前解执行10次反转操作算子,从而获得10个邻域解,选取距离理想点α 最近的解π′i 替换当前解πi ,否则,保留当前解。循环上述步骤,直到实现对整个种群的更新。3)当随机数小于p 时,对当前解执行基于参考解的插入操作算子,获得n 个邻域解。同样选取其中距离理想点α 最近的解π′i 替换当前解πi ,否则,保留当前解。循环上述步骤,直到实现对整个种群的更新。2.9 算法框架
所提算法主要从局部和全局搜索两方面强化搜索能力: 1) 基于理想点设计局部搜索策略和使用贪婪操作算子,提高局部勘探能力; 2) 设计融入高价值信息的双点交叉和劣解接受准则,促成Pareto前沿推进。具体算法流程如下。为便于描述,定义了以下变量:PS表示初始鸟群的个数,
β 表示围绕每个个体产生的邻域解数量,γ 表示每个个体传给下一个体的共享解数量,G 为巡回次数,T 为初始温度,α 冷却速率。流程1:改进多目标候鸟优化算法流程 输入: PS 、β 、γ 、G、T、α 。步骤1 初始化鸟群。融合随机初始化与可行性判定生成初始种群后,基于Pareto占优关系和拥挤距离进行排序,将排在第一的个体设为领飞鸟,其余个体按顺序依次分到左右两个跟飞鸟队列中。设置巡回次数 g=1 。步骤2 执行巡回操作,直至 g=G 。步骤2.1 领飞鸟进化。等概率执行贪婪交换/插入操作。围绕领飞鸟产生 β 个可行邻域解,根据Pareto占优和拥挤距离排序,选出排在第一的解。若其性能优于领飞鸟,则进行替换;否则保持不变。从余下的邻域解中选取γ 个较优解,形成左/右队列首个跟飞鸟的共享解集PL/PN。步骤2.2 跟飞鸟进化。随机生成一个数,若其小于0.5,执行基于价值信息的交叉操作,否则执行插入操作,直至生成 β−γ 个可行邻域解。联合当前共享解集PL/PN,生成左/右队列跟飞鸟邻域解集,由排在第一的解与当前跟飞鸟相比较。若性能更优则替换;否则基于接收准则进行劣解保存。同上,利用余下邻域解更新共享解集PL/PN。重复上述操作,直至所有跟飞鸟完成进化。步骤2.3 更新非支配解集EA。 步骤2.4 基于理想点的局部搜索。将当前所有解与非支配解集EA合并,对其进行局部搜索并更新非支配解集。 步骤3 若 g<G ,则g=g+1 ,跳到步骤2;否则令g=1 ,将当前领飞鸟随机移动到左或右队列的尾部,选取当前非支配解集中排序第一的个体作为下一回合的领飞鸟。从左和右队列中随机选择一个个体进行交换,实现队列间的信息交流。步骤4 终止条件判断。若满足终止条件,则输出最优非支配解;否则,跳回步骤2。 3. 实验分析与讨论
为评估所提出的IMMBO算法性能,设计两组实验分别对改进算子和算法性能进行比对。所有算法均采用MATLAB R2019b编程,电脑配置为Intel (R) Core (TM) i5-
12600 ,CPU@3.30 GHZ,16 GB RAM。为保证对比公平性,每个测试案例测试20遍,运行终止时间相同均为lgN⋅10s ,其中N 为案例中总任务数。3.1 案例描述及评价标准
针对JS-AGVS问题,目前没有直接可用的标杆案例集。因此,在一个在线材料分享网站(http://soa.iti.es/problem-instances)的AGV调度案例集的基础上进行如下修正,以生成JS-AGVS案例集。假定各任务需运送的零部件个数服从均匀分布
U[1,20] ;4种需运送零部件的单位重量为{0.75,1.05,2.05,4.5};每台AGV一趟行程最多执行4个任务;AGV停靠点坐标为 (60.5,44);停靠点到物料超市的距离为302.5;每台AGV最大载量为200;单台AGV执行每趟行程的启用成本为100;单位运输距离所耗费的成本为1;再参考文献[18]以生成与实际生产相吻合的各任务加工完成时间及交货期,将其替换标杆案例中各任务的时间窗。案例集可分为4种规模:案例集1 (T5I1-T5I5) 、案例集2 (T10I1-T10I5) 、案例集3 (T15I1-T15I5) 、案例集4 (T20I1-T20I5),所涉及的总任务数分别为{5,10,15,20}。随着总任务数的增加,对AGV的需求也随之增加。在总任务数较小时,任务之间冲突较少,AGV之间的协调相对简单,通过少量AGV多趟运输即可满足转运需求。但随着总任务数增加,需更多的AGV来处理任务之间的冲突,以确保任务及时完成,提高生产系统的整体效率。为尽可能使用最少数量的AGV去完成全部运输任务,通过多次实验,在确保能产生可行调度方案情况下,设定各总任务数对应所需AGV数量分别为{2,3,7,8}。以T5I1为例,表2指明了其包含的全部信息。
表 2 T5I1任务信息Table 2. Information of task T5I1任务
编号节点
序号节点
坐标到停
靠点
距离加工
完成
时间从该节点
经物料超市
回停靠点
的时间最晚
交付
时间运送
零部件
种类运送
零部件
数量1 24 (16.5,35.2) 52.8 10 657.8 1220 1 20 2 46 (27.5,52.8) 41.8 100 646.8 1310 3 2 3 96 (55, 52.8) 14.3 196 619.3 1406 2 17 4 30 (16.5, 88) 88.0 280 693.0 1490 4 15 5 54 (33, 35.2) 36.3 360 641.3 1570 4 20 为便于算法性能评价,采用超体积率 (hypervolume ratio, HVR) 、逆世代距离 (inverted generational distance, IGD) [4]作为评价指标,IGD值越小或HVR越大,算法的收敛性和多样性越好。
3.2 参数校验
算法参数的设置对算法整体性能有着较大的影响,因此在对算法测试之前,需将算法参数调整到合适的值,以确保算法能够发挥最佳性能。为全面评估算法的性能,选取了不同规模的8个算例,确保其在各种情况下都能有效运行,并找到适合不同规模的最佳参数设置。每个算例求解20次,基于IGD值比较并采用田口实验方法对各个算法的参数进行标定。参数校验结果详见表3。
表 3 各测试算法参数校验结果Table 3. Parameter verification results of test algorithms算法 参数 水平 取值 IMMBO 种群规模 11, 13, 15 15 邻域数量 5, 6, 7 7 共享解数量 2, 3 ,4 2 巡回次数 5, 10, 15 5 初始温度 0.4, 0.5, 0.6 0.4 冷却因子 0.90, 0.95, 0.99 0.90 EMOEA 种群规模 20, 30, 40 30 交叉概率 0.7, 0.8, 0.9 0.8 重启动阈值 4, 5, 6 4 NSGA-Ⅱ 种群规模 60, 80, 100 80 交叉率 0.7, 0.8, 0.9 0.9 突变率 0.1, 0.2, 0.3 0.1 MOSA 初始温度 0.5, 1, 1.5 1.5 冷却因子 0.90, 0.95, 0.99 0.99 温度变化前的迭代次数 500, 1000 , 2000500 重启次数 4, 5, 6 4 MOABC 种群大小 80, 90, 100 100 解最大未更新迭代次数 5, 6, 7 6 3.3 改进算子有效性分析
改进多目标候鸟优化算法(IMMBO)进行了4处改进,包含融入贪婪算子的领飞鸟进化、融入高价值信息两点交叉和概率接受准则的跟随鸟进化、基于理想点的局部搜索策略。为此,依次去除本文提出的改进算子,得到去除接受准则 (MMBO_GTL) 、再去除局部搜索策略 (MMBO_GT) 、再去除两点交叉算子 (MMBO_G) 及贪婪算子,直至转变为原始的多目标候鸟优化算法 (MMBO) [15]。必须申明,相关实验的初始解生成方法相同。
共采用8个测试案例:T5I1、T5I2、T10I1、T10I2、T15I1、T15I2、T20I1及T20I2,经8×20×5=800次实验后,获得图3所示的对比图。
分析可知,综合性能从好到差依次是IMMBO> MMBO_GTL> MMBO_GT> MMBO_G>MMBO,证明改进措施是有效的。原因如下:1)在MMBO基础上引入贪婪算子 (MMBO_G) 后,IGD指标显著改善,但HVR变化不大,证明收敛性有所提高,但多样性改善有限,解质量略有提升;2)引入两点交叉算子 (MMBO_GT) 后,全局探索搜索能力提高,两个指标都明显变好,算法的收敛性和解质量有明显提升;3)引入基于理想点的局部搜索操作 (MMBO_GTL) 后,局部勘探能力得到提升,收敛性和多样性明显改善,解质量呈逐步变好趋势;4)引入接受准则 (IMMBO) 后,跳出了局部最优,故而收敛性和鲁棒性更好。相较于前4种算法,IMMBO的解质量和收敛性显著提升,能够更快地获得更优解。
3.4 算法性能分析
为评估IMMBO算法综合性能,将其与带精英策略的快速非支配排序遗传算法 (NSGA-Ⅱ) [19]、多目标人工蜂群算法 (MOABC) [20]、多目标模拟退火算法 (MOSA) [21]、多目标进化算法 (EMOEA) [4]进行对比。为保证实验公平性,各算法的初始解生成方式相同。表4为实验结果,加粗部分为最好解。结果对比如图4所示。
表 4 IMMBO和其他对比算法的平均HVR、IGDTable 4. Average HVR and IGD values using IMMBO and other comparison algorithmsHVR IGD 案例 AGV台 NSGA-Ⅱ MOABC MOSA EMOEA IMMBO NSGA-Ⅱ MOABC MOSA EMOEA IMMBO T5I1 2 0.93 0.94 1 1 1 0.004 0.010 0 0 0 T5I2 2 0.87 0.98 1 1 1 0.012 0.015 0 0.004 0 T5I3 2 1 0.97 1 1 1 0 0 0 0 0 T5I4 2 1 0.96 1 1 1 0.001 0.007 0 0.002 0 T5I5 2 1 1 1 1 1 0.008 0.008 0 0 0 T10I1 3 0.82 0.91 0.95 0.99 1 0.052 0.040 0.007 0.012 0.001 T10I2 3 0.73 0.81 0.95 0.99 1 0.073 0.023 0.005 0.012 0.001 T10I3 3 0.81 0.90 0.97 0.97 1 0.033 0.026 0.004 0.008 0.002 T10I4 3 0.83 0.84 0.98 0.99 1 0.028 0.021 0.004 0.007 0.002 T10I5 3 0.80 0.72 0.97 0.98 1 0.042 0.030 0.002 0.003 0.000 T15I1 7 0.71 0.74 0.89 0.90 0.99 0.026 0.024 0.016 0.014 0.004 T15I2 7 0.73 0.74 0.88 0.95 0.98 0.019 0.021 0.009 0.007 0.003 T15I3 7 0.74 0.78 0.91 0.92 0.97 0.017 0.014 0.012 0.008 0.003 T15I4 7 0.73 0.79 0.92 0.91 0.94 0.021 0.020 0.013 0.010 0.006 T15I5 7 0.73 0.77 0.91 0.96 1 0.021 0.019 0.011 0.010 0.003 T20I1 8 0.64 0.68 0.83 0.90 0.97 0.029 0.028 0.025 0.025 0.014 T20I2 8 0.62 0.69 0.86 0.85 0.96 0.031 0.028 0.022 0.028 0.014 T20I3 8 0.66 0.69 0.85 0.86 0.95 0.034 0.029 0.024 0.030 0.012 T20I4 8 0.67 0.69 0.84 0.88 0.96 0.032 0.025 0.022 0.028 0.015 T20I5 8 0.65 0.69 0.84 0.84 0.93 0.033 0.029 0.023 0.036 0.018 分析可见IMMBO算法在所有案例的HVR、IGD指标上都取得了最好结果,收敛性和多样性显著更优,特别是鲁棒性有较大幅度的提升。具体而言,针对T5I1 ~ T5I5的5个小规模案例,5种算法均能找到较好解;但随着案例规模增大,IMMBO的优势愈加显著,在HVR、IGD两个指标上持续最优。
4. 结论
针对交货期限制下加工车间多AGV调度问题,以及时送达率最高及总运输成本最低为目标,建立了混合整数线性规划模型,提出了改进多目标候鸟优化算法 (IMMBO) 来求解,获得了收敛性更优、鲁棒性更强的解。主要贡献如下。
1) 提出基于最早交货期的交付时间确定和AGV分配规则,实现了无延迟、少库存、均衡AGV利用率的目标。
2) 提出改进多目标候鸟优化算法,其中融入贪婪操作、基于理想点的局部搜索算子,靶向探索优质解空间,加速了Pareto前沿收敛;设计融入高价值信息的两点交叉与接收准则,提高了Pareto前沿解集的多样性,促进了算法局部勘探与全局探索的有效平衡。
未来研究将聚焦于零部件从加工车间直送到装配线边、考虑充电及生产过程中的不确定性因素的多趟AGV动态调度问题,并研究算子和参数的自适应推荐,以提升算法性能。
-
表 1 符号和定义
Table 1 Symbols and their definitions
种类 符号 说明 集合 任务集合,,其中为停靠点,为下游工序物料超市 AGV集合, 零部件集合, 运输趟数集合, 参数 任务数 AGV总数 零部件种类数 单台AGV的最大趟数 任务的横坐标 任务的纵坐标 任务的呼叫时间 任务的最晚交付时间 每个任务的装货时长 每个任务的卸货时长 任务i到任务j的行驶距离 任务到任务的行驶时间 足够大的正数 单个零部件的重量 任务所转运零部件的总数量 任务所转运零部件的总重量, 每台AGV一趟行程所能执行的最大任务数 每台AGV最大载量 第台AGV执行任务后的载重 单台AGV执行每趟行程的启用成本 单位运输距离所耗费的成本 AGV启用成本 AGV行驶成本 变量 0-1变量,若AGV 在r趟行程中从任务所在位置直达任务位置,;否则 0-1变量,若AGV 需执行第r趟行程,则;否则 连续变量,AGV在第r趟行程从停靠点出发的时间 连续变量,AGV在第r趟行程回到停靠点的时间 连续变量,任务到达物料超市的时间 连续变量,加工阶段执行任务j的零部件装货时间 表 2 T5I1任务信息
Table 2 Information of task T5I1
任务
编号节点
序号节点
坐标到停
靠点
距离加工
完成
时间从该节点
经物料超市
回停靠点
的时间最晚
交付
时间运送
零部件
种类运送
零部件
数量1 24 (16.5,35.2) 52.8 10 657.8 1220 1 20 2 46 (27.5,52.8) 41.8 100 646.8 1310 3 2 3 96 (55, 52.8) 14.3 196 619.3 1406 2 17 4 30 (16.5, 88) 88.0 280 693.0 1490 4 15 5 54 (33, 35.2) 36.3 360 641.3 1570 4 20 表 3 各测试算法参数校验结果
Table 3 Parameter verification results of test algorithms
算法 参数 水平 取值 IMMBO 种群规模 11, 13, 15 15 邻域数量 5, 6, 7 7 共享解数量 2, 3 ,4 2 巡回次数 5, 10, 15 5 初始温度 0.4, 0.5, 0.6 0.4 冷却因子 0.90, 0.95, 0.99 0.90 EMOEA 种群规模 20, 30, 40 30 交叉概率 0.7, 0.8, 0.9 0.8 重启动阈值 4, 5, 6 4 NSGA-Ⅱ 种群规模 60, 80, 100 80 交叉率 0.7, 0.8, 0.9 0.9 突变率 0.1, 0.2, 0.3 0.1 MOSA 初始温度 0.5, 1, 1.5 1.5 冷却因子 0.90, 0.95, 0.99 0.99 温度变化前的迭代次数 500, 1000 , 2000500 重启次数 4, 5, 6 4 MOABC 种群大小 80, 90, 100 100 解最大未更新迭代次数 5, 6, 7 6 表 4 IMMBO和其他对比算法的平均HVR、IGD
Table 4 Average HVR and IGD values using IMMBO and other comparison algorithms
HVR IGD 案例 AGV台 NSGA-Ⅱ MOABC MOSA EMOEA IMMBO NSGA-Ⅱ MOABC MOSA EMOEA IMMBO T5I1 2 0.93 0.94 1 1 1 0.004 0.010 0 0 0 T5I2 2 0.87 0.98 1 1 1 0.012 0.015 0 0.004 0 T5I3 2 1 0.97 1 1 1 0 0 0 0 0 T5I4 2 1 0.96 1 1 1 0.001 0.007 0 0.002 0 T5I5 2 1 1 1 1 1 0.008 0.008 0 0 0 T10I1 3 0.82 0.91 0.95 0.99 1 0.052 0.040 0.007 0.012 0.001 T10I2 3 0.73 0.81 0.95 0.99 1 0.073 0.023 0.005 0.012 0.001 T10I3 3 0.81 0.90 0.97 0.97 1 0.033 0.026 0.004 0.008 0.002 T10I4 3 0.83 0.84 0.98 0.99 1 0.028 0.021 0.004 0.007 0.002 T10I5 3 0.80 0.72 0.97 0.98 1 0.042 0.030 0.002 0.003 0.000 T15I1 7 0.71 0.74 0.89 0.90 0.99 0.026 0.024 0.016 0.014 0.004 T15I2 7 0.73 0.74 0.88 0.95 0.98 0.019 0.021 0.009 0.007 0.003 T15I3 7 0.74 0.78 0.91 0.92 0.97 0.017 0.014 0.012 0.008 0.003 T15I4 7 0.73 0.79 0.92 0.91 0.94 0.021 0.020 0.013 0.010 0.006 T15I5 7 0.73 0.77 0.91 0.96 1 0.021 0.019 0.011 0.010 0.003 T20I1 8 0.64 0.68 0.83 0.90 0.97 0.029 0.028 0.025 0.025 0.014 T20I2 8 0.62 0.69 0.86 0.85 0.96 0.031 0.028 0.022 0.028 0.014 T20I3 8 0.66 0.69 0.85 0.86 0.95 0.034 0.029 0.024 0.030 0.012 T20I4 8 0.67 0.69 0.84 0.88 0.96 0.032 0.025 0.022 0.028 0.015 T20I5 8 0.65 0.69 0.84 0.84 0.93 0.033 0.029 0.023 0.036 0.018 -
[1] 邓超, 胡蓉, 钱斌. 混合分布估计算法求解考虑同步性和准时性的三阶段装配集成调度问题[J]. 控制理论与应用, 2020, 37(5): 1090-1102. DOI: 10.7641/CTA.2019.90736 DENG Chao, HU Rong, QIAN Bin. Hybrid estimation of distribution algorithm for three-stage assembly integrated scheduling problem considering assembly synchronization and delivery punctuality[J]. Control Theory & Applications, 2020, 37(5): 1090-1102. DOI: 10.7641/CTA.2019.90736
[2] 陆志强, 胡鑫铭, 朱宏伟. 物料供给不确定环境下的飞机移动生产线动态调度方法[J]. 同济大学学报(自然科学版), 2019, 47(5): 723-730,738. DOI: 10.11908/j.issn.0253-374x.2019.05.019 LU Zhiqiang, HU Xinming, ZHU Hongwei. Dynamic scheduling method for aircraft moving assembly line under uncertain supply of material[J]. Journal of Tongji University(Natural Science), 2019, 47(5): 723-730,738. DOI: 10.11908/j.issn.0253-374x.2019.05.019
[3] 付建林, 张恒志, 张剑, 等. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675. FU Jianlin, ZHANG Hengzhi, ZHANG Jian, et al. Review on AGV scheduling optimization[J]. Journal of System Simulation, 2020, 32(9): 1664-1675.
[4] ZOU W, PAN Q, WANG L. An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery[J]. Knowledge-Based Systems, 2021, 218: 106881. DOI: 10.1016/j.knosys.2021.106881
[5] 徐立云, 陈延豪, 高翔宇, 等. 混流柔性加工单元自动导引小车的调度优化[J]. 同济大学学报(自然科学版), 2017, 45(12): 1839-1846,1858. DOI: 10.11908/j.issn.0253-374x.2017.12.014 XU Liyun, CHENG Yanhao, GAO Xiangyu, et al. AGV scheduling optimization in mixed flexible manufacturing cell[J]. Journal of Tongji University(Natural Science), 2017, 45(12): 1839-1846,1858. DOI: 10.11908/j.issn.0253-374x.2017.12.014
[6] 李昆鹏, 刘腾博, 阮炎秋. 半导体生产车间智能AGV路径规划与调度[J]. 计算机集成制造系统, 2022, 28(9): 2970-2980. LI Kunpeng, LIU Tengbo, RUAN Yanqiu. Intelligent AGV routing scheduling with applications insemi-conductor production[J]. Computer Integrated Manufacturing Systems, 2022, 28(9): 2970-2980.
[7] ZHOU B, HE Z. A novel hybrid-load AGV for JIT-based sustainable material handling scheduling with time window in mixed-model assembly line[J]. International Journal of Production Research, 2021, 61: 796-817.
[8] LI C, ZHANG L, ZHANG L. A route and speed optimization model to find conflict-free routes for automated guided vehicles in large warehouses based on quick response code technology[J]. Advanced Engineering Informatics, 2022, 52: 101604. DOI: 10.1016/j.aei.2022.101604
[9] FAZLOLLAHTABAR H, HASSANLI S. Hybrid cost and time path planning for multiple autonomous guided vehicles[J]. Applied Intelligence, 2017, 48: 482-498.
[10] ZENG C, TANG J, YAN C. Scheduling of no buffer job shop cells with blocking constraints and automated guided vehicles[J]. Applied Soft Computing, 2014, 24: 1033-1046. DOI: 10.1016/j.asoc.2014.08.028
[11] ZHANG X, SANG H, LI J, et al. An effective multi-AGVs dispatching method applied to matrix manufacturing workshop[J]. Computers & Industrial Engineering, 2022, 163: 107791.
[12] DANG Q-V, SINGH N, ADAN I, et al. Scheduling heterogeneous multi-load AGVs with battery constraints[J]. Computers & Operations Research, 2021, 136: 105517.
[13] 袁帅鹏, 李铁克, 王柏琳. 无关并行机类型混合流水车间成组调度问题的改进候鸟优化算法[J]. 计算机集成制造系统, 2022, 28(12): 3910-3920. YUAN Shuaipeng, LI Tieke, WANG Bailin. Enhanced migrating birds optimization algorithm for hybrid flowshop group scheduling problem with unrelated parallel machines[J]. Computer Integrated Manufacturing Systems, 2022, 28(12): 3910-3920.
[14] ALP G, ALKAYA A F. An investigation of nature inspired algorithms on a particular vehicle routing problem in the presence of shift assignment[J]. Computers & Operations Research, 2022, 141: 105685.
[15] DUMAN E, UYSAL M, ALKAYA AF. Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences, 2012, 217: 65-77. DOI: 10.1016/j.ins.2012.06.032
[16] LI Z, TANG Q, ZHANG L. Minimizing energy consumption and cycle time in two-sided robotic assembly line systems using restarted simulated annealing algorithm[J]. Journal of Cleaner Production, 2016, 135: 508-522. DOI: 10.1016/j.jclepro.2016.06.131
[17] PAN Q, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers & Operations Research, 2009, 36(8): 2498-2511.
[18] CHENG L, TANG Q, ZHANG L, et al. Inventory and total completion time minimization for assembly job-shop scheduling considering material integrity and assembly sequential constraint[J]. Journal of Manufacturing Systems, 2022, 65: 660-672. DOI: 10.1016/j.jmsy.2022.10.013
[19] XU Z T, ELOMRI A, POKHAREL S, et al. A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows[J]. Computers & Industrial Engineering, 2019, 137: 106011.
[20] BARADARAN V, SHAFAEI A, HOSSEINIAN A H. Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows: Mathematical modeling and solution approach[J]. Computers & Industrial Engineering, 2019, 131: 187-199.
[21] PILATI F, TRONCONI R. Multi-objective optimisation for sustainable few-to-many pickup and delivery vehicle routing problem[J]. International Journal of Production Research, 2023, 1-30.