考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化.pdf

第2 9卷第8期计算机集成制造系统V o l.2 9N o.82023年8月C o m p u t e r I n t e g r a t e dM a n u f a c t u r i n gS y s t e m sA u g.2 0 2 3D O I:1 0.1 3 1 9 6/j.c i m s.2 0 2 3.0 8.0 2 2收稿日期:2 0 2 1-0 4-1 5;修订日期:2 0 2 1-0 5-2 3。R e c e i v e d1 5A p r.2 0 2 1;a c c e p t e d2 3M a y2 0 2 1.基金项目:国家自然科学基金资助项目(6 1 4 7 3 2 1 6);陕西省自然科学基础研究计划资助项目(2 0 2 3-J C-Y B-5 8 2,2 0 2 0 J M-4 8 9);陕西省教育厅自然科学基金资助项目(1 7 J K 0 4 5 9);西安建筑科技大学自然科学基础研究资助项目(Z R 1 8 0 4 9);陕西省重点研发计划资助项目(2 0 2 1 G Y-0 6 6)。F o u n d a t i o n i t e m s:P r o j e c t s u p p o r t e db yt h eN a t i o n a lN a t u r a lS c i e n c eF o u n d a t i o n,C h i n a(N o.6 1 4 7 3 2 1 6),t h eN a t u r a lS c i e n c eB a s i cR e s e a r c hP r o g r a mo fS h a a n x i P r o v i n c e,C h i n a(N o.2 0 2 3-J C-Y B-5 8 2,2 0 2 0 J M-4 8 9),t h eN a t u r a l S c i e n c eF o u n d a t i o no f S h a a n x i P r o v i n c i a l E d u c a t i o nD e-p a r t m e n t,C h i n a(N o.1 7 J K 0 4 5 9),t h eN a t u r a l S c i e n c eB a s i cR e s e a r c hF o u n d a t i o no fX i a nU n i v e r s i t yo fA r c h i t e c t u r ea n dT e c h n o l o g y,C h i n a(N o.Z R 1 8 0 4 9),a n d t h eK e yR e s e a r c ha n dD e v e l o p m e n tP r o g r a mo fS h a a n x i P r o v i n c e,C h i n a(N o.2 0 2 1 G Y-0 6 6).考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化熊福力,曹劲松,张 杏(西安建筑科技大学 信息与控制工程学院,陕西 西安 7 1 0 0 5 5)摘 要:生产调度、装车组合与交通拥塞是影响预制构件制造企业生产运营效率及成本的重要主客观因素,如何在考虑交通拥塞时变特性的情况下有效集成生产调度与工件装车组合方案是预制构件制造企业迫切需要解决的问题。针对该集成优化问题,首先以最小化总提前拖期惩罚和车辆运输费用之和为目标,建立了预制构件生产调度与工件装车组合集成优化数学模型。随后为降低问题求解困难,通过深入分析问题解结构特点,提出了一种基于自适应多邻域协同搜索的果蝇优化算法(AMN C S-F OA)。其主要特点是:设计了一种带有插零操作的集成决策编码方式用于表示生产调度和工件装车组合方案;在算法的嗅觉搜索阶段,基于组内交换、组间交换、组内插入和组间插入四种邻域构造,提出了一种自适应概率邻域选择策略;在视觉搜索阶段,为提高算法全局搜索能力,以一定概率接受劣解作为种群中心进一步执行迭代搜索。计算结果显示,AMN C S-F OA算法在求解该集成优化问题时具有更快的收敛速度以及更好的求解质量。与预制构件制造企业常用的规则启发式方法相比,提出算法在求解质量上具有不低于1 3%的平均改进率,有望显著增加预制构件企业净利润并提高客户满意度。关键词:预制构件生产调度;时变运输时间;工件装车组合;提前拖期惩罚;果蝇优化算法中图分类号:T P 1 8 文献标识码:AI n t e g r a t e dp r e c a s tp r o d u c t i o ns c h e d u l i n ga n d l o a d i n gc o m b i n a t i o nw i t hc o n s i d e r i n g t i m e-v a r y i n gc h a r a c t e r i s t i c so f t r a f f i cc o n g e s t i o nX I ONGF u l i,C A OJ i n s o n g,ZHANGX i n g(C o l l e g eo f I n f o r m a t i o na n dC o n t r o lE n g i n e e r i n g,X i a nU n i v e r s i t yo fA r c h i t e c t u r ea n dT e c h n o l o g y,X i a n7 1 0 0 5 5,C h i n a)A b s t r a c t:P r o d u c t i o ns c h e d u l i n g,j o bl o a d i n gc o m b i n a t i o na n dt r a f f i cc o n g e s t i o na r ei m p o r t a n ts u b j e c t i v ea n do b j e c t i v e f a c t o r sa f f e c t i n gt h ep r o d u c t i o na n do p e r a t i o ne f f i c i e n c yo fp r e f a b r i c a t e dm a n u f a c t u r i n ge n t e r p r i s e s.T h e r e-f o r e,h o wt o i n t e g r a t ep r o d u c t i o ns c h e d u l i n ga n d j o b l o a d i n gc o m b i n a t i o ns c h e m e e f f e c t i v e l y i s a nu r g e n t p r o b l e mf o rp r e f a b r i c a t e dc o m p o n e n t sm a n u f a c t u r e r sw i t hc o n s i d e r i n gt h et i m e-v a r y i n gc h a r a c t e r i s t i c so ft r a f f i cc o n g e s t i o n.T od e a lw i t ht h e i n t e g r a t e do p t i m i z a t i o np r o b l e m,am a t h e m a t i c a lm o d e l f o rt h ei n t e g r a t e do p t i m i z a t i o np r o b l e m w a sf o r m u l a t e dt om i n i m i z e t h es u mo fp r o d u c t i n v e n t o r yc o s t,t a r d i n e s sp e n a l t ya n dv e h i c l e t r a n s p o r t a t i o nc o s t.T or e-d u c e t h ed i f f i c u l t yo f s o l v i n g t h ep r o b l e m,a nA d a p t i v eM u l t i p l eN e i g h b o r h o o d sC o l l a b o r a t i v eS e a r c h-b a s e dF r u i tF l yO p t i m i z a t i o nA l g o r i t h m(AMN C S-F OA)w a sp r o p o s e d.I t sm a i nc h a r a c t e r sw e r ea s f o l l o w s:a n i n t e g r a t e dd e c i s i o nc o d i n gm e t h o dw i t hz e r o i n s e r t i o no p e r a t i o nw a sd e s i g n e d t o r e p r e s e n t t h e c o m b i n a t i o ns c h e m e o f p r o d u c t i o ns c h e d u-l i n ga n d j o b l o a d i n g;i n t h eo l f a c t o r ys e a r c hp h a s eo f t h e a l g o r i t h m,a na d a p t i v ep r o b a b i l i s t i cn e i g h b o r h o o ds e l e c t i o n计算机集成制造系统第2 9卷s t r a t e g yw a sp r o p o s e db a s e do n f o u rn e i g h b o r h o o ds t r u c t u r e s i n c l u d i n g i n t r ag r o u pe x c h a n g e,i n t e r g r o u pe x c h a n g e,i n t r ag r o u p i n s e r t i o na n d i n t e rg r o u p i n s e r t i o n;i nt h ev i s u a l s e a r c hs t a g e,t o i m p r o v e t h eg l o b a l s e a r c ha b i l i t yo f t h ea l g o r i t h m,t h e i t e r a t i v es e a r c hw a sp e r f o r m e dw i t ha c e r t a i np r o b a b i l i t y t oa c c e p t t h e i n f e r i o r s o l u t i o na s t h ep o p u l a-t i o nc e n t e r.T h e r e s u l t s s h o w e d t h a tAMN C S-F OAa l g o r i t h mh a d f a s t e r c o n v e r g e n c e s p e e da n db e t t e r s o l u t i o nq u a l i-t yf o rd e a l i n gw i t ht h e i n t e g r a t e do p t i m i z a t i o np r o b l e m.C o m p a r e dw i t ht h er u l e-b a s e dh e u r i s t i c sc o mm o n l yu s e di np r e f a b r i c a t e dc o m p o n e n tm a n u f a c t u r i n ge n t e r p r i s e s,t h ep r o p o s e da l g o r i t h mh a da na v e r a g e i m p r o v e m e n t r a t eo fn ol e s s t h a n1 3%i ns o l v i n gq u a l i t y,w h i c hw a se x p e c t e dt os i g n i f i c a n t l y i n c r e a s e t h en e tp r o f i t o fp r e f a b r i c a t e dc o m p o-n e n t e n t e r p r i s e sa n d i m p r o v ec u s t o m e r s a t i s f a c t i o n.K e y w o r d s:p r e c a s tp r o d u c t i o ns c h e d u l i n g;t i m e-v a r y i n gt r a n s p o r t a t i o nt i m e;j o bl o a d i n gc o m b i n a t i o n;e a r l i n e s s/t a r-d i n e s sp e n a l t i e s;f r u i t f l yo p t i m i z a t i o na l g o r i t h m0 引言装配式建筑作为推动建筑业转型升级、绿色发展的关键,对建筑工业化建设有着重要意义。然而,针对目前装配式建筑的发展现状,在设计和管理投入不足的情况下,出现了预制构件生产调度不合理、交通运输情况复杂、车辆分配不合理、施工效益明显下降等问题,严重阻碍了装配式建筑的推广。因此,考虑交通流量时变特性的预制构件生产运输集成优化研究对现阶段预制构件生产调度问题具有重要的理论意义和实用价值。预制供应链由生产、运输和现场组装三部分组成,每个阶段使用的人力物力资源都产生相应的成本。研究表明,如果调度决策得到协调,将会有大量节约机会1-3。因此,预制构件供应链的科学管理对降低生产成本、提高生产效率至关重要。在预制构件生产 调度问题上,近年来已取 得一定的 成果。KO等4建立了基于预制构件生产现状的流水车间排序模型,并应用多目标遗传算法以最小完工期和最小拖期惩罚来搜索解;WANG等5提出了预制件生产的两层模拟-遗传混合算法对预制件生产操作进行优化,并基于遗传算法和离散事件模拟对工作流程的工艺等待时间进行建模研究;崔琪等6提出了一种变邻域改进遗传算法有效求解了混合流水车间调度问题;L I U等7考虑了以最小化最大完工时间为目标的单机成组调度问题,提出了基于枚举的算法、启发式算法和分支定界算法,计算结果表明,分支定界算法在获得最优解方面是非常有效的,但仅限于求解小规模问题。因此,在求解复杂的大规模生产调度问题时往往需要通过高效的启发式算法去进行求解。T ANG等8提出了一种混合离散粒子群 优 化 算 法(H y b r i d D i s c r e t eP a r t i c l eS w a r mO p t i m i z a t i o n,HD P S O),并将其与模拟退火算法(S i m u l a t e dA n n e a l i n g,S A)相结合,HD P S O-S A有效求解了多目标柔性作业车间调度问题。果蝇优化算法(F r u i tF l yO p t i m i z a t i o nA l g o r i t h m,F OA)9作为一种新颖的群体智能优化算法,由于其控制参数少、寻优速度快和较好的收敛效果,也已被成功地应用于生产调度领域。在考虑运输调度问题方面,Z E GO R D I等1 0考虑了两阶段供应链环境下产品和车辆的调度问题,并提出了一种考虑两个不同染色体的非等价结构的性别遗传算法(G e n d e rG e n e t i cA l g o r i t h m,G GA)有效求解了该问题;CHE N等1 1定义了具有批处理和运输的物流调度(L o g i s t i cS c h e d u l i n gw i t hB a t c-h i n g a n d T r a n s p o r t a t i o n,L S B T);P UN D OO R等1 2研究了以配送成本和订单最大延迟加权和最小化为目标的供应链调度问题,并设计了一种快速启发式算法求解该问题;CHAN等1 3考虑了工件加工后分批运输的单机排序问题,产生的每批工件都会产生相应的运输成本;L I等1 4总结指出预制构件运输效率低下是预制建筑面临的挑战之一;WANG等1 5在考虑生产和运输阶段的预制构件生产调度优化时,选择夜间配送预制构件的方案,以避开车流高峰期,减少运输时间。上述研究为考虑交通流量时变特性的预制构件生产调度与工件装车组合集成优化问题(I n t e g r a t e dP r e c a s tP r o d u c t i o n S c h e d u l i n g a n dJ o b L o a d i n gC o m b i n a t i o n,I P P S J L C)提供了良好 的理论基础。但同时也看到,目前的研究大多集中在单一的预制生产阶段或运输阶段,且并未很好地将预制运输时间随交通流量变化而改变的特性融入到问题模型中,使研究的问题模型与实际偏差较大,应用价值较低。因此本文在充分考虑交通拥塞时变特性的基础上,结合预制构件生产的特殊性(工序之间的差异性较大,工序处理周期长),以最小化总提前拖期惩罚、2672第8期熊福力 等:考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化运输费用之和为目标,研究了带有交通拥塞时变特性的I P S C S J L C问题并建立了其相应数学优化模型。考虑该集成优化问题的复杂性,基于带有插0操作的集成决策编码方式,提出了一种基于自适应多邻域协同搜索的果蝇优化算法(A d a p t i v eM u l t i p l eN e i g h b o r h o o d s C o l l a b o r a t i v e S e a r c h-b a s e d F r u i t f l yO p t i m i z a t i o nA l g o r i t h m,AMN C S-F O A)求解此问题,通过大 量 仿 真 实 验 与 变 邻 域 搜 索 算 法(V a r i a b l eN e i g h b o r h o o dS e a r c h,V N S)和果蝇算法(F O A)进行对比分析,验证了所提算法的有效性和可行性。1 I P P S J L C问题描述与建模1.1 问题背景本文研究的预制构件生产运输系统包含9个阶段:模具制造;模具组装;钢筋预埋;混凝土浇筑;蒸汽养护;脱模;整理精修;存储;运输。在生产阶段每道工序仅有一台机器(即单生产线工作模式)。预制构件生产不同于传统流水车间问题,根据生产工艺的特征可将工序分为并行工序(可同时处理多个工件)和串行工序(当进行到该工序下的工件未处理完前,不可对下一工件进行处理)。其中工序5蒸汽养护、工序8存储以及预制构件生产完成后的运输阶段为并行处理,其余工序为串行处理。结合实际生产物流情形,本文在预制构件完工后的运输阶段设定了3种不同类型的车辆对工件运输配送,同时考虑了每种类型车辆的最大可装载容量Vj、基本租用费用qj和装载单位容量的费用系数wj。车辆的运输费用由基本租用费用和容量费用组成,每种类型运输车辆一旦被启用,不论装载工件的数量多少,都会产生基本租用费用,而车辆装载的工件数量越多,占用车辆容量也就越多,因而会产生更高的容量费用。本文研究的是单制造商到单客户的整点发车物流配送模式1 6(工件会生产完成装车后会等到整点时刻发车运输),而D A B I A等1 7研究发现在城市中,即便同一路段车辆的行驶时间也会随不同时刻下的交通密度发生很大变化。为了让问题模型更具有实用参考价值,本文将不同发车时间点导致的时变运输时间纳入准时交付计划。根据交通拥堵状况分为轻交通,正常交通,拥堵交通和重度拥堵交通,以此设定了制造商到客户间不同发车时间点fj对应的运输时间t用于模型仿真。如图1所示,在本文的模型中,将一天2 4小时划分为2 4个整点发车时间。根据每个发车时间点的平均交通密度设置了对应的运输时间(2.5,3.2,4.5,5),以表现不同发车时间点的交通拥堵度情况对运输时间的实际影响。1.2 问题描述基于以上预制构件生产运输背景介绍,I P P S J L C问题可以描述为:n个预制构件按照相同的处理顺序经过M道工序预制构件生产工序处理,且工件在每道工序上只能处理一次。工件加工完成后即运送至预先分配好确定的运输车辆上等待配送,待被分配到同一运输车辆上的工件全部完工且装车完毕,到整点时刻即发车运输,抵送达客户处时完成交付。为了避免运输车辆长时间等候待配送工件全部装车,本文对分配到同一运输车辆上配送的工件进行绑定生产(即分配至同一运输车辆上的工件在进行生产调度时安排在前后相邻的位置),以便生成完成后及时装车运输。所研究的问题是以最小化工件提前拖期费用和运输费用之和为目标,同时优化生产调度方案和工件装车组合方案。对于该集成优化问题,本文做出如下假设:3672计算机集成制造系统第2 9卷(1)预制构件生产与运输环节执行三班倒2 4小时工作制,不考虑工厂停工休整情况;(2)所 有 工 件、机 器 在 调 度 零 时 刻 均 为 可 用状态;(3)不考虑机器故障、工人缺勤等突发情况;(4)每个运输车辆运输一次,抵达客户处后不予回收;(5)每个工件在生产前需要预先分配给确定的运输车辆,生产完成后即刻装车等待运输;(6)工件从加工完成运送至对应配送车辆上的转移时间,忽略不计。需要指出的是,在目标函数中同时考虑了工件的提前拖期惩罚费用和工件在不同车辆间的装车组合产生的配送费用。为优化该目标函数,需要同时确定工件的生产调度方案和装载工件车辆分配方案,而分配至同一车辆上的工件会进行绑定生产,所以工件的车辆分配方案会影响工件调度方案的优化空间,因此需要对两个方案进行集成决策。1.3 数学模型问题描述和建模中用到的符号定义如下:标引和输入参数:n为工件总数;M为工序总数;h为运输车辆数;R为发车时区间总数;i为工件标号,i=1,2,n;j为运输车辆标号,j=1,2,h;i 为位置标号,表示一个调度序列中的第i 个位置,i=1,2,n;k为工序标号,k=1,2,8;r为发车时区间标号,r?=1,2,R;i为工件i单位时间提前惩罚系数;i为工件i单位时间拖期惩罚系数;qj为表示车辆j的租用费用;wj为表示车辆j装载单位容量产生的费用;vi为为工件i需占用的车辆容量;Vj为表示车辆j的最大装载容量;di为为工件i对应的交货期;TIr-1,TIr 为发车时间区间;pi,k为工件i在工序k上的处理时间,k=1,2,8;决策变量:Ci ,k为调度序列中第i 个位置的工件在工序k上的完工时间;Sj为车辆j的发车时间;t rj为车辆j的运输时间,需要指出的是,运输时间随发车时间变化而变化,因此也是决策变量Ej为车辆j的到货时间;zi,i 为布尔变量,如果工件i被分配到生产调度序列中的第i 个位置,取值为1,否则为0;xi j为布尔变量,如果工件i被分配到车辆j,取值为1,否则为0;yj为布尔变量,表示如果车辆j被使用为1,否则为0。根据以上符号和假设建立数学模型如下:m i nni=1iMa x(0,hj=1Ejxi j-di)+iM a x(0,di-hj=1Ejxi j)+hj=1ni=1wjvixi j+hj=1qjyj。(1)s.t.ni=1zi,i=1,i;(2)ni=1zi,i=1,i;(3)Ci ,kCi-1,k+ni=1zi,i pi,k,k=1,2,3,4,6,7,i;(4)Ci ,kCi ,k-1+ni=1zi,i pi,k,i,k;(5)Ci ,k=Ci ,k-1+ni=1zi,i pi,k,i,k=5,8;(6)xi jyj,i,j;(7)ni=1xi jviVj,j;(8)hj=1xi j=1,i;(9)Sj=m a xi=1,2,nxi jni=1zi,i Ci ,8,j;(1 0)t rj=t1 TI0SjTI1 tR TIR-1SjTIR;(1 1)Ej=Sj+t rj,j;(1 2)yj0,1,j;(1 3)xi j0,1,i,j;(1 4)Ci ,k,Sj,t rj,Ej0。(1 5)4672第8期熊福力 等:考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化式(1)表示目标函数为最小化工件提前拖期惩罚费用和车辆配送费用之和;式(2)确保调度序列中的每个位置恰好只指派给一个工件;式(3)确保每个工件恰好只指派到调度序列中的一个位置;式(4)使得工件在工序上的处理时间不早于上一工件在此工序上的完工时间,第5道工序蒸汽养护和第8道工序存储为并行处理过程,不需要满足此约束;式(5)确保工件在工序上的开始处理时间不早于该工件上一工序的完工时间;式(6)为并行工序完工时间的计算公式;式(7)确保只有在车辆使用时才为车辆分配工件;式(8)表示分配到车辆j上所有工件的总容量不超过车辆j最大装载容量;式(9)确保每个工件只会分配给确定的一辆车,不会对其再次分配;式(1 0)表示车辆j的发车时间为所有分配到该车工件的最大生产完工时间的上取整值;式(1 1)表示车辆j的运输时间t是与该车整点发车时间Sj相关的的阶梯函数;式(1 2)表示分配到车辆j上工件i的交货时间Ej为车辆j的发车时间Sj加上该发车时刻下对应的运输时间t(fj);式(1 3)(1 5)定义了各决策变量的取值范围。决策变量Sj在模型中的具体作用过程是首先通过式(1 0)计算出车辆j的发车时间Sj,然后通过式(1 1)确定发车时间为Sj时需要的运输时间t rj,最后通过式(1 2)计算车辆j的到货时间Ej,进而求得目标函数值。该集成优化模型具有如下特点:(1)与传统流水车间调度模型不同的是,该模型具有串并行工序混合的特点,工序间差异性较大,工序处理周期长;(2)为克服以往预制构件生产与配送方案不匹配的问题,该模型目标函数中综合考虑了生产与运输费用;(3)考虑了不同发车时间点交通拥塞情况对运输时间的影响,建立了时变运输时间模型以描述运输时间随不同发车时刻变化的特性;(4)模型中需要确定最优工件装车组合方案,同时涉及到不同装车组合方案下的批调度问题。2 基于自适应多邻域协同搜索的果蝇优化算法 传统的流水车间调度问题,已被证明是一个N P-h a r d问题1 8-1 9,问题解空间大,复杂度高,通常传统的精确算法如分支定界等方法在求解该类问题时,求解时间会随问题规模呈指数增长,对于中大规模问题难以在合理时间内找到最优解,无法满足工业实际需求。本文研究的是预制构件生产调度和工件车辆分配集成优化问题,两个决策子问题之间具有强耦合关系,比传统的流水车间调度更为复杂,问题求解难度更大。鉴于元启发式算法在求解复杂调度优化问题上的优势,因此需要根据问题结构特点设计高效的元启 发式算法用 以 解 决 该 集 成 优 化问题。2.1 果蝇优化算法果蝇优化算法(F OA)是一种基于果蝇觅食行为而提出的新型群体智能优化算法,将果蝇种群的觅食过程模拟为算法寻找优化解的过程,基于果蝇觅食行为中的嗅觉和视觉行为来设计相应的操作,通过不断对果蝇种群中心位置的优化,进而找到 食 物 存 在 的 位 置。果 蝇 优 化 算 法 的 流 程如下9:步骤1 初始化种群中心位置;步骤2 嗅觉搜索。根据种群中心位置随机产生NP个邻域解;步骤3 评价个体,计算每个个体的评价值;步骤4 视觉搜索。选择最优邻域解,替换更新种群中心位置;步骤5 判断终止准则是否满足。是则输出最优解;否则,转步骤2。2.2 AMN C S-F O A算法设计与传统 智 能 算 法 相 比,F OA算 法 控 制 参 数少、收敛速度快,局部搜索能力强,已被广泛地用于求解调度领域问题2 0-2 1。考虑到I P P S J L C问题中工件生产调度和工件车辆分配两个子问题之间互相影响,而工件车辆分配方案的结果将影响工件生产调度的决策,而同时确定两个子问题的决策方案是评估目标值必不可少的条件。因此本文结合问题结构特点提出了带有插0操作的集成决策编码方式,使得决策解能同时表达工件生产调度和工件车辆分配方案。基于该编码方式设计了组内交换、组间交换、组内插入和组间插入四种独特邻域动作方式生成种群。在算法的嗅觉搜索阶段,采用了基于自适应邻域学习机制,在保证算法局部开发性的前提下,增强算法的全局探索能力;在算法 的 视 觉 搜 索 阶 段,受 模 拟 退 火 算 法2 2启发,引入了概率接受准则,当算法在循环迭代陷入局部最优时,允许算法以一定概率接受劣解做为种群中心进一步执行嗅觉搜索,增大搜索到全局5672计算机集成制造系统第2 9卷最优解的可能性。AMN C S-F OA算法的流程如图2所示,首先初始化参数设置,初始化邻域选择概率,随机生成一个满足容量约束的初始解作为种群中心,公平起见,设置四种邻域的初始选择概率均为0.2 5。之后进入嗅觉搜索阶段,对当前种群中心进行多邻域协同搜索,按照邻域选择概率生成种群。统计每个邻域构造中产生优于种群中心的解个数,通过后面2.2.3节中的式(1 6)和式(1 7)计算进入下一次嗅觉搜索四种邻域动作方式的选择概率,更新嗅觉搜索方式。然后进入视觉搜索阶段,首先评估当前各邻域结构下产生种群个体的目标值,将当前种群最佳解与种群中心比较,如果当前种群最佳解对应的目标值更优,则替换为种群中心,否则按模拟退火算法中的接受准则以概率替换种群中心。最后判断算法是否满足停止准则,满足则输出种群中心,即最佳解,否则进入下一次迭代循环。2.2.1 解的编码与解码方式I P P S J L问题的难点在于需要对工件生产调度和装车组合方案进行同时决策,进而优化计算目标函数值。为了在对工件进行生产调度的同时体现工件到车辆的分配方案,本文采用了基于插0法的集成编码解码方式,如图3所示。该方法通过使用0元素将分配到不同车辆上的工件隔开,以表示工件在不同车辆间装车的组合。为便于理解,以一个具有6个工件和3辆运输车辆的简单I P P S J L C问题来说明AMN C S-F O A算法解的编码和解码的过程。图3中,解的表示形式为(32061504),工件分配由分隔元素0确定,即该解表示将工件3,2 分配给车辆1,工件6,1,5 分配给车辆2,工件4分配给车辆3。对解(32061504)从左向右搜索元素0,并将其删除以获得工件的生产调度序列(326154)。根据该调度序列将工件依次排入生产线上加工处理,首先在工序1上处理工件3。由式(4)式(6)计算工件3在工序1上的完成时间,并作为其紧后处理的工件2在工序1上的开工时间,再通过式(4)(6)计算工件2在工序1上的完成时间,依次类推计算得出生产调度序列(326154)内所有工件在1到8工序上的开工时间、完工时间。对于工序9输运过程,为便于理解,以工件3和工件2为例。由于工件2和3被分配至同一运输车辆上配送,两工件具有相同的发车时间,此时通过式(1 0)计算车上所有工件在工序8上的最晚完工时间,并向上取整得出该车辆上工件共同的发车时间。各工序调度甘特图如图4所示。6672第8期熊福力 等:考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化2.2.2 邻域构造解的邻域是表示空间中所有可能解的集合,通过在当前解中执行有规则的局部移动来寻优更新目标解。为了克服在单一邻域搜索方式易陷入局部最优的困难,本文基于解的编码方式,结合问题模型特点设计了四种独特的邻域解动作方式进行邻域搜索(如图5):(1)组内交换在各组块(即被元素0分隔开的工件集合)中随机生成两个交换位置并交换两个位置的内容,保持0位置不变。如图5 a所示,执行组内交换运算后,初始序列由(12 3 0 4 5 0 6 7 8)更新为(3 2 1 0 5 4 0 8 7 6)。(2)组间交换随机产生两个组块的位置,并整体交换两个块的内容。如图5 b所示,随机地生成两个块位置1和3。执行组间交换后,初始序列由(1230450678)更新为(6780450123)。(3)组内插入在各个组块内部,随机生成两个位置,并第二个位置的内容插入到第一个位置之前,然后其余位置的内容依次往后移动一位。如图5 c所示,执行组间插入后,初始序列由(1230450678)变化为(3120540867)。(4)组间插入在所有组块里随机生成两个位置,并将位置最前沿的块交换到位置靠后块的位置,位置靠后块与其前面的块整体右移一位如图5 d所示,随机生成两个组块位置1和3。执行组间插入后,初始序列由(1230450678)变化为(6780123045)。7672计算机集成制造系统第2 9卷2.2.3 基于自适应邻域学习机制的嗅觉搜索与传统果蝇优化算法使用单一邻域结构生成种群的操作不同,本文在算法的嗅觉搜索阶段采用了多邻域并行搜索方式,并结合问题模型特点设计了四种独特的邻域动作方式,通过概率选择同时利用四种邻域构造生成种群个体,增加了种群的多样性。同时在每次种群产生后,利用自适应邻域学习机制,根据该次嗅觉搜索每种邻域中产生优于当前种群中心解的数量情况,及时调整下次迭代生成种群时每种邻域构造的选择概率,优化种群生成机制,让算法动态地向最佳的邻域搜索方式靠拢,并最终收敛,使得算法在集中性和分散性之间达到较好平衡。以Fgu表示第g次迭代使用邻域结构v生成种群个体的概率,Bgu表示第g次迭代通过邻域结构v得到产生优于当前种群中心解的邻域解个数,则Fg1、Fg2、Fg3和Fg4分别表示第g代迭代选择通过组内交换、组间交换、组内插入和组间插入生成种群个体的概率,Bg1、Bg2、Bg3和Bg4分别表示在第g次迭代通过组内交换、组间交换、组内插入和组间插入产生优于种群中心解的邻域解个数。公平起见,初次迭代时F11、F12、F13和F14均设定为0.2 5。在之后迭代中,Fgu的计算公式如下:Fgu=m a x0.1,Bg-1u4t=1Bg-1t,u=1,2,3,(1 6)Fg4=1-Fg1-Fg2-Fg3。(1 7)设置各邻域 动作方式的 最低被选择 概率为0.1。如果该次迭代中各邻域结构中都未产生优于种群中心的邻域解,即式(1 6)出现分母为0的情况,则令下次迭代时的Fg1、Fg2、Fg3和Fg4均为0.2 5。2.2.4 基于概率接受准则的视觉搜索传统果蝇算法中每次嗅觉搜索结束仅接受当前搜索到的最好解作为种群中心进入下一次迭代寻优,这种基于贪婪思想的搜索方式有利算法快速收敛,但同时会导致算法易陷入局部最优。为了克服这种缺陷,本文在果蝇算法的视觉搜索阶段结合了模拟退火算法中的概率接受准则,在算法陷入局部收敛,通过嗅觉搜索无法寻得更佳种群中心时,以一定概率接受当前种群最佳解替换种群中心,从而为算法提供一个扰动,使其跳出局部最优,走向更广阔的解空间,增大了算法找到全局最优解的可能性。接受准则为若当前种群最佳解目标值优于当前种群中心的目标值,则接受新解,否则以概率e(-E T)接受当前种群最佳解,其中E为该次迭代的当前种群最佳解目标值与当前种群中心目标值