混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题

唐捷凯, 胡蓉, 钱斌, 金怀平, 向凤红

电子学报 ›› 2022, Vol. 50 ›› Issue (7) : 1621-1630.

PDF(1027 KB)
PDF(1027 KB)
电子学报 ›› 2022, Vol. 50 ›› Issue (7) : 1621-1630. DOI: 10.12263/DZXB.20210320
学术论文

混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题

作者信息 +

Hybrid Imperialist Competitive Algorithm for Solving Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery

Author information +
文章历史 +

本文亮点

针对供应链中一类广泛存在的带多行程批量配送的多工厂集成调度问题(Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery,MFISP_MTBD),建立其数学模型并提出基于贝叶斯统计推断的混合帝国竞争算法(Hybrid Bayesian statistical inference-based Imperialist Competitive Algorithm,HBICA)进行求解.根据MFISP_MTBD问题特性,结合多行程标签机制设计新型编解码策略,并基于该策略构造新型启发式规则以提高初始解的质量.为有效保留优质解的模式信息,采用贝叶斯概率模型学习机制替换标准帝国竞争算法中的同化机制.为更加明确地引导搜索方向,算法每代均利用各帝国中的精英国家(即精英解或个体)重构贝叶斯概率模型,进而对其采样生成新种群.利用9种有效邻域操作动态构造各帝国中每个国家的局部搜索,并对由各帝国内部相邻国家间竞争所确定的强势国家(即获胜国)执行其局部搜索,进而对各帝国中的殖民国家(即该帝国内的最强国家)依次执行所有弱势国家的局部搜索.仿真实验和算法比较验证了所提算法可有效求解MFISP_MTBD.

HeighLight

Aiming at a kind of widely existing multi-factory integrated scheduling problem with multi-trip batch delivery(MFISP_MTBD) in the supply chain, this paper establishes the mathematical model, and a hybrid Bayesian statistical inference-based imperialist competitive algorithm(HBICA) is proposed to solve it. According to the characteristics of the MFISP_MTBD, a new encoding and decoding strategy based on multi-trip labeling mechanism is proposed, on this basis, a new heuristic rule is constructed to improve the quality of the initial solution. To effectively preserve the pattern information of the high-quality solution, the Bayesian probability model learning mechanism is used to replace the assimilation mechanism in the imperial competition algorithm. Afterwards, each generation of the algorithm reconstructs the Bayesian probability model by using the elite countries(i.e. elite solution or individual) in each empire to guide the search direction explicitly, and new population is generated by sampling it. The local search for each country in each empire is dynamically constructed by 9 effective neighborhood operations. Local search is carried out on the strong country(i.e. the winning country) determined by the competition among neighboring countries within the empire, and local search of weak countries is carried out in turn for the colonial countries in each empire(i.e. the strongest countries in the empire). Simulation experiments and comparisons on different instances demonstrate that the proposed algorithm can effectively solve MFISP_MTBD.

引用本文

导出引用
唐捷凯 , 胡蓉 , 钱斌 , 金怀平 , 向凤红. 混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题[J]. 电子学报, 2022, 50(7): 1621-1630. https://doi.org/10.12263/DZXB.20210320
TANG Jie-kai , HU Rong , QIAN Bin , JIN Huai-ping , XIANG Feng-hong. Hybrid Imperialist Competitive Algorithm for Solving Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery[J]. Acta Electronica Sinica, 2022, 50(7): 1621-1630. https://doi.org/10.12263/DZXB.20210320
中图分类号: TP273   

1 引言

在经济全球化趋势下,大量企业的生产模式已由传统集中式向分布式转变,并进一步构建起集生产和运输为一体的供应链1~3.为应对分布式供应链所带来的车辆成本上升,则要提高车辆的利用率,使用相同车辆分批次多行程运输已成为必然趋势4~6.基于上述背景,研究带多行程批量配送的多工厂集成调度问题(Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery,MFISP_MTBD)具有重要的经济效益.
当前生产和运输集成调度问题的研究主要有两类.第一类为单工厂生产与运输配送集成调度问题,现有研究分别对带多行程运输7、批量运输78和多车型运输9等约束条件的此类问题进行了建模与求解.第二类为多工厂生产与运输配送集成调度问题110.由文献调研可知,目前对于第二类集成调度问题的研究还十分有限,且尚未考虑实际生产中广泛存在的各工厂间生产效率差异与多行程运输等约束条件.因此,建立考虑上述约束条件的MFISP_MTBD数学模型,并设计求解该问题的有效算法具有重要的理论价值和实践意义.
贝叶斯概率模型是一种基于贝叶斯统计推断所提出的统计概率模型11,该概率模型继承了先验分布这一独特的统计学特征.因其良好的统计推断效果12,近年来基于该模型的学习型智能算法13被广泛用于求解可重入作业车间调度问题14、低碳分布式流水线调度问题15和带时间窗的车辆调度问题16.
帝国竞争算法(Imperialist Competitive Algorithm,ICA)是一种具有高效全局搜索能力的群智能算法,已被广泛应用于求解生产调度1718、路径规划19等领域的问题.然而,ICA的同化机制在一定程度上导致其存在过早收敛的问题20,针对该问题现有算法的主要改进可以分为两类.第一类为引入接受差解的机制,在一定程度上缓解ICA的过早收敛2021.第二类为引入概率模型对ICA同化机制进行优化22,使之成为学习型智能算法.然而,现有学习型ICA所采用的二维概率模型仅能学习编码间的相邻关系信息,却无法学习编码所在的位置信息.因此,将贝叶斯概率模型与ICA相结合将更加有利于引导帝国对解空间进行更加高效且深入的探索.
本文研究了MFISP_MTBD的建模与求解.针对实际供应链体系中各工厂间生产效率差异与多行程运输等约束条件,建立以最小化加工与运输总成本为目标的MFISP_MTBD模型.根据MFISP_MTBD特性提出基于多行程标签机制的两阶段编解码策略,同时设计新型启发式规则以提升初始种群的质量.设计基于贝叶斯统计推断的混合帝国竞争算法(Hybrid Bayesian statistical inference-based Imperialist Competitive Algorithm,HBICA)对其进行求解.该算法一方面引入基于贝叶斯概率模型的学习型同化机制,实现优质解的高效学习与算法全局的高效引导;另一方面设计“殖民掠夺”变邻域局部搜索机制进行有侧重的深入搜索.通过仿真实验和算法对比验证了HBICA求解MFISP_MTBD的有效性.

2 MFISP_MTBD的问题描述

2.1 符号定义

MFISP_MTBD涉及的有关数学符号定义如表1所示.
表1 符号表
符号 说明
i,j 工件或客户下标,i,j=1,2,,N
f 工厂编号f=1,2,,F
k 车辆编号k=1,2,,Kf
w 车辆行程编号w=1,2,,Wkf
Esum 各工厂加工产生的总功耗kWh
Ce 单位电价
qi 工件i的重量t,qi0,Q
Wk 车辆的自重t
Nelite 车辆在客户i到客户NeliteE=NEmpE×Pelite的货运负载t,Li,j0,Q
Dij 客户i到客户j的距离km
CBkfw fk车的第w批次配送开始时间
Ai 工件i送达客户i的时间
λL 车辆与加速度、滚动阻力、重力等相关的油耗系数
λk 车辆与空气密度和车辆前表面积等相关的油耗系数
Gij 车辆在客户i到客户j的耗油量
Gsum 配送阶段产生的总油耗
Cg 单位油价
Ti 工件i违规超时时常
λp 违约超时的惩罚系数
Vjf 如果工件j分配在f厂加工则为1,否则为0,Vjf0,1
Xijf 如果工件j在紧接着工件i之后在f厂加工则为1,否则为0,Xijf{0,1}
Yijkfw 若客户jfk车的第w批次行程配送则为1,否则为0,Yjkfw0,1
Zijkfw 若客户i紧接着客户jfk车的第w批次行程配送则为1,否则为0,Zijkfw0,1
注:为方便计算,引入虚拟工件0N+1作为各工厂生产的第一个工件与最后一个工件,同时客户0N+1表示工厂的往返.

2.2 问题模型

MFISP_MTBD可描述为:将N个客户的工件订单分配至F个分布在不同地理位置且具备加工能力的工厂分别按照πf的顺序进行加工,工件加工完成后通过各工厂的车队按照πkwf的顺序分批配送给客户.该模型主要分为生产阶段和配送阶段.在生产阶段,各工厂加工具有相同的单位能耗EpkWh,但各工厂对同一工件存在差异化的加工时间Pif.所有工件均可安排在任意工厂进行加工,工件被分配至某一工厂后便不能再次分配至其他工厂,各工厂在同一时间只能加工一个工件.不同工件之间相互独立且在加工时不允许发生抢占.在配送阶段,各工厂的车队拥有足够数量具有相同速度V和载重约束Q的同质车辆,启用新车辆的固定成本为FC.已启用的车辆在配送计划批次中工件都完工后从工厂出发将工件送达客户并返回,当车辆返回工厂后经过时长为tm的维护后,在CRkfw时刻即可开始新的行程.各工厂依据工件的完工时间Ci、截止交货期di等约束,灵活规划车辆数量和每辆车各批次运输路线将工件配送给客户.MFISP_MTBD示意图如图1所示.
f=0FVjf=1,j1,2,,N
(1)
Xijf+Xjif1,i,j0,1,,N+1
(2)
i=0NXi,jf=Vi,jf,j=1,2,,N+1,f=1,2,,F
(3)
Cπf(1)=Pπf(1),f,f1,2,,N
(4)
Cπf(x)=Cπf(x-1)+Pπf(x),f,f1,2,,F
(5)
Esum=Ep×f=1FmaxCπf(x)×Vπf(x)f,x1,2,,N
(6)
k=1Nfw=1NkfYjkfw=Vjf,j=1,,N
(7)
i=0NZijkfw=Yjkfw,f=1,2,,F,k=1,2,,Kfw=1,2,,Wkf,j=1,2,,N+1
(8)
i=0NZiekfw-j=1N+1Zejkfw=0,e=1,2,,N
(9)
j=1NYjkfw×qjj=1NZ0jkfw×Q
(10)
CRkf0=0,f=1,2,,F,k=1,2,,Kf
(11)
CBkfW=maxCRkfw-1,maxCπkwf ,w=1,2,,Wkf
(12)
Aπkwf(1)=CBkfw+t0,πkwf(1)
(13)
Aπkwf(y)=Aπkwf(y-1)+tπkwf(y-1),πkwf(y)
(14)
CRkfw=maxAπkwf(y)+tπkwf(Nkwf),N+1+tm
(15)
Lπkwf(Nkwf),N+1=0
(16)
Lπkwf(y-1),πkwf(y)=Lπkwf(y),πkwf(y+1)+qπkwf(y)
(17)
图1 MFISP_MTBD示意图

Full size|PPT slide

Gπkwf(y-1),πkwf(y)=Dπkwf(y-1),πkwf(y)×λLWk+Lπkwf(y-1),πkwf(y)+λk×V2
(18)
Gsum=i=0Nj==1N+1Gij×Zijkfw
(19)
Tj=max(0,Aj-dj),j1,2,,N
(20)
TC=Ce×Esum+Cg×Gsum+f=1FFC×Kf+j=1nTj×λp
(21)
MFISP_MTBD的优化目标为在集成调度问题中找到最优排序π*,使得总成本TC最小.
π*=argTCmin
(22)
其中,式(1)保证每一个工件都被分配到一个工厂.式(2)式(3)保证每一个工件都有一个前置和后续工件在工厂中被加工.式(4)式(5)计算各工件在生产阶段的完工时间.式(6)计算所有工厂在生产阶段产生能耗的总和.式(7)保证每一个工件都被分配到所在工厂的一个配送行程.式(8)式(9)保证每一个客户都有一个前置和后续客户在配送行程中被服务.式(10)保证配送行程均满足车辆载重约束.式(11)~(15)计算配送行程的往返时间及各工件送达客户的时间.式(16)式(17)计算各车在配送行程中各路段的货运负载.式(18)计算各车在配送行程中各路段产生的油耗8.式(19)计算所有车在配送行程中产生的总油耗.式(20)计算各工件总违规超时时长.式(21)计算由工厂能耗费用、车辆油耗费用、车辆固定成本以及违规超时惩罚所组成的总成本.

3 HBICA求解MFISP_MTBD

MFISP_MTBD的本质是一个复杂的组合优化问题,高效求解此类问题的关键在于如何针对问题特性设计合理的编解码策略和改进算法设计.
HBICA中,国家π就是原问题的一个解;定义NPop(G)={πG,1,πG,2,,πG,Nna}为HBICA第G代的国家种群,其中NnaNPop的规模,PImp为初始化中殖民国家在Nna的占比,NImpNPop中殖民国家的规模,NColNPop中殖民地的规模;定义EmpPopE(G)为第G代第E帝国的国家种群,EmpPopE(G)={πEG,1,πEG,2,πEG,NEmpE},其中NEmpE为该帝国所包含的国家数量,πEG,1为该帝国的殖民国家,πEG,1,c{2,3,,NEmpE}为该帝国殖民地.

3.1 编码与解码

3.1.1 国家编码与解码

在编码过程中,每个国家编码π首先按工厂编号递增的顺序依次将各厂的工件加工顺序录入,然后在工厂工序间插入取值为(N,N+F)(F-1)个工厂分隔符.以规模为N=8F=3的问题为例,编码9与10为工厂分隔符,其编码如图2所示.
图2 编码示意图

Full size|PPT slide

在解码过程中,针对优化目标为最小化TC的MFISP_MTBD设计了一种融合了多行程标签4的新型解码策略.该解码策略分为2个阶段,首先在π中通过识别工厂分隔符依次读取各工厂工件的加工顺序;然后以各工件完工时间作为释放时间,按照先完工先运输(First Completed First Transported,FCFT)的规则,以最大化利用车辆为目标对车辆路径进行规划.具体步骤如下所示:
步骤1: 若当前解码位置α=0,则将当前工厂编号设置为f=1,分配到工厂的工件数Nf=0,令α=α+1;转至步骤2.
步骤2: 若π(α)N,则将π(α)置于πk中的第Nf+1位,令α=α+1Nf=Nf+1;若π(α)>N,则令当前工厂编号f=f+1,令Nf=0α=α+1.转至步骤3.
步骤3: 若α(N+F-1),按照式(1)~(5)计算得到πf(Nf)的完工时间Cπf(Nf),转至步骤2;若α>(N+F-1),令F=ff=1,工厂启用车辆数为k=0,转至步骤4.
步骤4: 若k=0Nf>0,则将πf(1)置于π11f中的第1位,令k=1w=1Nkwf=1,配送工件在工厂的位置δf=1,按照式(10)~(15)计算当前车辆行程信息创建多行程标签,转至步骤7.
步骤5: 若L0,πkwf(1)+qδf<QTπkwf(y)<0,y{1,2,,
Nkwf+1},则将πf(δ+1)置于πkwf中的第Nkwf+1位,令δf=δf+1Nf=Nf+1,更新多行程标签,转至步骤7;否则,转至步骤6.
步骤6: 若min(CRkfw)<Cπf(δ)min(CRkfw)+t0,πf<Tπf,将πk(δ+1)置于πk(w+1)f中的第1位,令w=w+1Nkwf=1;否则,将πk(δ+1)置于πKf+1,1f中的第1位,令Kf=Kf+1k=Kfw=1Nkwf=1.更新多行程标签,转至步骤7.
步骤7: 若Nf>δf+1,则转至步骤5;否则,转至步骤8.
步骤8: 若f+1F,令f=f+1k=0,转至步骤4;否则,输出加工序列和运输序列.

3.1.2 资源编码与解码

针对本文提出的“殖民掠夺”变邻域搜索,HBICA将与各国家π相对应的局部搜索具象为资源个体Λ.每个Λ均由9种不同的邻域搜索操作LSs排列而成,其邻域搜索操作次数为η,且同一Λ中允许出现相同的LSs.解码Λ时,对π从左到右依次执行Λ中的邻域搜索操作.每执行完一次邻域搜索操作,就将得到的新解与旧解进行对比,若新解优于旧解,则用新解替换旧解,否则,舍弃新解.以η=5的资源个体Λ为例,其示意图如图3所示.
图3 资源个体示意图

Full size|PPT slide

3.2 初始化帝国

3.2.1 初始化国家

本文针对MFISP_MTBD这类问题的性质1,设计启发式规则产生高质量初始解,其步骤如下:
步骤1: 随机生成包含全部工件的工件序.
步骤2: 从左到右依次取出工件,按式(6)~(21)计算其插入各工厂加工序的最后所带来的TC增量.
步骤3: 将当前工件安排在TC增量最小的工厂进行加工.若尚有工件未分配工厂,则转至步骤2,否则,输出由启发式规则生成的新国家.
同时为兼顾初始种群的质量和分散性,根据启发式规则使用概率PH来随机选择启发式规则生成与随机生成两种方式对NPop(1)进行初始化.然后,随机生成Nna个资源个体并与NPop(1)各国家建立一一对应的关系.

3.2.2 构建帝国

构建帝国首先需要计算所有初始国家的TC,将NPop(1)TC较小的NImp个国家作为殖民国家存入各帝国种群EmpPopE(1)中的πE1,1,同时将对应的资源个体存入帝国资源域ERPopE(1)中的ΛE1,1.
然后将殖民国家力量进行归一化,并以此划分殖民地,其具体计算如式(23)~(25)所示:
NImp=Nna×PImp
(23)
PTCE=1TCπE1,1
(24)
PE=PTCEi=1NImpPTCi
(25)
其中,式(23)为初始殖民国家数量(即初始帝国数量)的计算式,PImp为初始殖民国家占比;式(24)为殖民国家的实力PTC的计算式;式(25)πE1,1获取殖民地的概率PE的计算公式,且E=1NImpPE=1.
最后,依据PE以轮盘赌的方式依次将NCol个殖民地及其资源个体分别划分至EmpPopE(1)ERPopE(1)从而完成初始帝国的构建.

3.3 同化

HBICA的同化阶段是通过在各帝国使用贝叶斯网络学习精英国家的结构信息,分别构建NImp个贝叶斯概率模型,继而通过采样各帝国所属贝叶斯概率模型更新全部殖民地以实现同化.其中,精英国家为各帝国中按TC递增排序的前Nelite个国家,其中Nelite的计算如下:
NeliteE=NEmpE×Pelite
(26)
式(26)为每个帝国中精英国家的数量计算式,其中Pelite为精英国家占比.

3.3.1 构建贝叶斯概率模型

贝叶斯网络作为贝叶斯概率模型记录国家信息的核心,由(n×n)的节点所构成,节点Ni,j表示国家中第i个位置存放的编号为j,文中n=(N+F-1).从Ni,jNi+1,k的定向弧所具有的权重为该帝国中精英国家序列存在Ni,jNi+1,k的数量.以规模为N=3F=2的问题为例,假设某一帝国NeliteE=6,精英国家分别为:π1elite=[1,4,2,3]π2elite=[2,1,4,3]π3elite=[3,4,2,1]π4elite=[3,2,4,1]π5elite=[3,4,2,1]π6elite=[4,2,1,3].则该帝国贝叶斯网络如图4所示.
图4 精英国家贝叶斯网络图

Full size|PPT slide

通过将节点间定向弧权重归一化可以获得贝叶斯概率模型,其相邻节点间概率计算如下所示:
P(N1,1)=1/6P(N1,2)=1/6P(N1,3)=3/6P(N1,4)=1/6
P(N2,4N1,1)=1P(N2,1N1,2)=1P(N2,2N1,3)=1/3P(N2,4N1,3)=2/3P(N2,2N1,4)=1
P(N3,4N2,1)=1P(N3,1N2,2)=1/2P(N3,4N2,2)=1/2P(N3,2N2,4)=1
P(N4,3N3,1)=1P(N4,1N3,2)=2/3P(N4,3N3,2)=1/3P(N4,1N3,4)=1/2P(N4,3N3,4)=1/2
显然,上述贝叶斯概率模型存在如下问题:(1)在后续采样过程易产生非法解,例如N1,3N2,2N3,1N4,3;(2)部分定向弧概率为0,则意味着在更新殖民地时将永远无法得到此序列,这将不利于算法跳出局部最优解;(3)部分定向弧概率为1,则新殖民地在此节点的序列均相同,这将导致算法过早收敛.
针对上述问题,本文对初始化贝叶斯网络进行了以下改进:(1)赋予所有可行的定向弧权重1/n-1,该操作在避免产生非法解的同时提升了国家的多样性;(2)引入最低国家数量标准γ,其中γ=Nna/Nna×PImp.若NEmpE>γ,则挑选当前帝国中精英国家构造贝叶斯网络;否则,以殖民国家为原型随机使用LSs生成(λ-NEmpE)个虚拟国家扩充至帝国,再挑选其中的精英国家构造贝叶斯网络,该操作有助于提升小规模帝国搜索的有效性.

3.3.2 采样

为了提高采样的执行效率,本文结合贝叶斯概率模型的特点,提出了一种融合了禁忌表的轮盘赌采样方式,其采样步骤如下:
步骤1: 建立与编码长度相同的禁忌表Tabu=[Φ1,Φ2,,ΦN+F-1],令Φ=True.使用轮盘赌的方法选择第一个节点N1,i,将N1,i存入新国家编码第1位,令Φi=False,国家编码位置x=2.
步骤2: 将满足Φj=TrueNx-1,iNx,j定向弧权重归一化计算P(Nx,jNx-1,i),继而使用轮盘赌选择下一节点Nx,j.
步骤3: 将Nx,j存入新国家编码第x位,令Φj=Falsei=jx=x+1.若x<N+F,则跳转至步骤2;否则,输出国家编码替换旧殖民地.

3.4 革命

殖民地革命作为一种对殖民地国家编码的操作方式,其无序扰动策略使某些国家在解空间中的位置产生突变,增加了算法的搜索范围并预防整个搜索进程过早进入局部最优3.
具体来说,首先对所有殖民地以PR的革命发生概率随机判断是否革命;然后对发生革命的殖民地随机选择邻域搜索操作LSs进行扰动,若扰动后殖民地TC发生改善,则更新殖民地;最终,在各帝国中选出该帝国当前最优国家成为新的殖民国家,从而实现对各帝国的革命.

3.5 殖民掠夺

将局部搜索作为优化工具融入ICA,将有利于提升国家的适应度,进而促进算法性能的加强16.然而,使用局部搜索势必造成算法计算复杂度的提升,占用较多计算资源,进而降低算法迭代效率.因此,设计合理的局部搜索的分配规则将有助于提升局部搜索策略使用效率的提升.故本文提出了“殖民掠夺”变邻域局部搜索机制,该机制利用9种针对MFISP_MTBD设计的邻域搜索操作动态构建局部搜索,并通过资源竞争与掠夺来对局部搜索进行分配,从而实现了局部搜索合理高效的运用.

3.5.1 邻域搜索操作

本文设计9种不同的邻域搜索操作,如下所示:
(1)LS1:国家编码序列交叉操作,从国家编码序列中随机选择2位进行交换.
(2)LS2:国家编码序列前向插入操作,从国家编码序列中依次随机选择2位,将先选中的编码插到后选中的编码之前.
(3)LS3:国家编码序列逆序操作,从国家编码序列中随机选择2位,将包含所选2位及其之间的编码颠倒排列顺序.
(4)LS4:国家编码序列相邻交换操作,从国家编码序列中随机选择一位,以相同的概率随机选择其与其向前或向后相邻的编码进行交换.
(5)LS5:工厂加工序列交叉操作,随机选择一个Kf2的工厂,再从该工厂加工序中随机选择2位进行交换.
(6)LS6:工厂加工序列前向插入操作,随机选择一个Kf2的工厂,再从该工厂加工序中随机选择2位,将先选中的工件插到后选中的工件之前.
(7)LS7:工厂加工序列逆序操作,随机选择一个Kf2的工厂,再从该工厂加工序中随机选择2位,将包含所选2位及其之间的工件颠倒排列顺序.
(8)LS8:车辆行程服务序列交叉操作,随机选择2个车辆行程服务序列,将2个车辆行程所包含的工件全部交换.
(9)LS9:车辆行程服务序列逆序操作,随机选择一个车辆行程服务序列,将该车辆行程服务序列的工件颠倒排列顺序.
在此基础上进一步将邻域搜索操作组合成不同的局部搜索并作为HBICA的资源个体Λ提供给国家使用,将有利于Λ对国家在多种邻域结构下持续的优化,从而实现对解空间深入有效的搜索.

3.5.2 资源竞争与掠夺

HBICA将帝国内部的国家按编号依次连接,通过在各帝国内部展开资源竞争与掠夺实现细致而有侧重的局部搜索.其具体步骤如下所示:
步骤1: 令帝国编号E=1,国家编号i=1.
步骤2: 当i=1时,令(i-1)=NEmpE.
步骤3: 若TCπEG,i<TCπEG,i-1TCπEG,i<TCπEG,i+1,则使用ΛEG,iπEG,i进行优化.
步骤4: 若πEG,i执行局部搜索后的TC优于执行前,则ΛEG+1,i=ΛEG,i;否则,挑选ΛEG,i中一段任意长度的编码重新生成,并将新的局部搜索存入ΛEG+1,i.
步骤5: 若i+1NEmpE,令i=i+1,转至步骤3.
步骤6: 在E帝国内进行殖民关系转换操作,依次使用弱势国家的ΛπEG,1进行优化.
步骤7: 若E+1NImp,令E=E+1i=1,转至步骤2;否则,结束殖民掠夺.

3.6 帝国竞争与删除

帝国竞争的本质是各帝国按照帝国实力ETCE对殖民地的争夺.帝国实力由殖民国家实力与殖民地实力2部分所组成,其具体计算如下:
ETCE=1TCπEG,1+ξ×c=2NEmpE1TCπEG,c/NEmpE-1
(27)
其中,1/TC为帝国中各国家的实力;ξ为殖民地实力对帝国实力的影响系数.
在帝国竞争过程中,首先确定最弱小的帝国,并从中割让一块殖民地.然后其余帝国依据帝国实力以轮盘赌的方式决定殖民地的新归属,其具体计算如下:
ETPE=ETCEi=1NImp-1ETCi
(28)
其中,ETPEE帝国获取殖民地的概率.
由于HBICA在同化中使用贝叶斯概率模型学习精英国家结构信息.因此,若割让的殖民地满足成为新帝国精英国家的条件,则最弱小帝国的部分优质结构信息也将被新帝国所接纳.故HBICA选择πEG,NEmpE而不是传统的maxπEG,c作为被割让的殖民地,进而保证被割让殖民地信息有更高的概率被新帝国贝叶斯概率模型学习,从而实现帝国间的优质信息交互.
在完成帝国竞争后,HBICA进入帝国删除阶段.即检查此时最弱小帝国所拥有的殖民地数量,若该帝国丧失全部的殖民地,则该帝国的殖民国家将沦为殖民地并划归其他帝国,至此该帝国灭亡.

3.7 帝国重构

针对HBICA帝国兼并速度加快的特点,设计了“帝国重构”扰动机制.即算法在未满足终止条件前,若所有国家兼并为单一帝国,则在保留国家种群中具有最优秀TC值的NImp个编码不同的国家作为新的殖民国家,并重新划分由初始化国家操作重新生成的殖民地以实现帝国的重新构建.
该扰动机制有助于提升算法后期对多个优质解区域同时搜索的能力,减缓过早收敛,从而实现HBICA的整体性能.

3.8 算法流程

据算法描述,HBICA算法流程如图5所示.
图5 HBICA流程图

Full size|PPT slide

4 实验分析与比较

由于目前尚无适合MFISP_MTBD的标准算例,本文所有的测试算例均在Gharaei等1为解决MFISP_BD所提供的数据分布区间上随机生成共计27个按照N×F组合的测试算例.所有算法和实验均由Delphi 2010编程实现,操作系统为Windows 10,CPU为2.90 GHz,内存为16 GB.

4.1 参数设置

在HBICA中,启发式规则使用概率PH、初始殖民国家占比PImp、精英国家占比Pelite和资源个体的邻域搜索次数η为关键参数.本文对中等规模问题(90×6)采用实验设计(Design Of Experiment,DOE)[24]行实验分析,得出HBICA的最佳参数组合为PH=0.4PImp=0.020Pelite=0.3η=6.

4.2 仿真结果比较与分析

本节将每种算法放在各测试问题上以相同时间((N×F×100) ms)下独立运行21次.其中,AVG为算法独立运行21次输出最优结果的平均值,Average为所有规模问题通过相关算法获得的每个性能指标输出结果的平均值,NB为所有规模问题通过相关算法获得的每个性能指标最优值的总数,在各指标下的占优值用粗体进行标识.

4.2.1 验证算法改进的有效性

为验证HBICA中“贝叶斯概率模型同化机制”与“殖民掠夺”自适应变邻域局部搜索机制2种关键改进的有效性,本节将HBICA与ICA及其变形算法进行比较,其结果如表2所示.其中,ED_ICA为采用二维概率模型同化机制的ICA,B_ICA为采用贝叶斯概率模型同化机制的ICA.
表2 ICA、ED_ICA、B_ICA与HBICA的有效性对比结果
问题规模 ICA ED_ICA B_ICA HBICA
AVG AVG AVG AVG
20×4 14 450.9 14 988.0 14 340.5 14 199.9
25×4 14 494.4 15 357.3 13 815.2 13 873.7
30×4 26 201.7 26 782.9 25 864.8 25 596.4
35×5 31 427.5 32 927.3 30 487.5 30 053.6
40×5 30 568.0 31 770.0 29 822.2 28 684.1
45×5 38 818.3 40 691.0 38 403.7 36 964.1
50×5 35 008.1 36 311.2 34 476.0 33 051.3
55×5 43 688.4 48 533.1 42 848.4 40 734.6
60×5 39 830.7 41 186.8 38 931.9 36 048.2
70×6 55 374.2 57 541.4 53 308.9 49 980.1
75×6 58 836.0 60 235.3 56 007.4 51 461.8
80×6 66 920.6 68 368.6 65 620.3 61 159.9
85×6 72 998.5 75 846.1 70 183.5 65 691.7
90×6 81 412.9 84 581.4 79 584.2 74 158.8
95×6 92 680.9 95 428.5 89 531.7 82 419.5
100×7 103 939.1 106 037.4 100 467.0 95 075.9
110×7 105 511.1 107 240.7 101 652.1 94 401.1
120×7 107 714.9 110 023.9 102 244.8 92 399.4
130×8 114 532.1 115 963.7 111 945.5 104 564.7
140×8 130 273.5 130 546.4 126 380.4 117 835.0
150×8 145 919.3 147 666.2 139 694.2 129 909.8
160×9 141 979.5 142 290.3 133 988.9 123 245.0
170×9 158 330.2 159 327.2 146 520.4 135 854.0
180×9 162 768.5 163 943.6 151 614.8 141 274.3
160×10 143 235.6 144 221.7 135 621.1 125 496.7
170×10 152 592.7 153 493.5 148 342.6 139 855.0
180×10 145 698.1 145 956.9 135 022.7 126 678.4
Average 85 748.4 87 305.9 82 100.8 76 691.4
NB 0 0 1 27
表2可知,B_ICA解的质量相较于ED_ICA与ICA有明显的提升,验证了贝叶斯概率模型同化机制的有效性.HBICA解的质量相较于B_ICA有显著的提升,验证了“殖民掠夺”变邻域局部搜索机制的有效性.

4.2.2 HBICA与其他算法的比较

为验证HBICA的有效性,将HBICA与近年来求解相关问题的有效算法(IWOA10、HGA4和TS8)进行对比,各算法比较结果如表3所示.
表3 HBICA与3种有效算法的对比结果
问题规模 IWOA HGA TS HBICA
AVG AVG AVG AVG
20×4 14 268.2 14 414.9 14 354.4 14 199.9
25×4 13 961.2 13 862.3 14 080.1 13 873.7
30×4 26 025.5 25 769.6 25 820.0 25 596.4
35×5 31 076.8 30 842.0 30 187.0 30 053.6
40×5 30 139.5 29 559.6 28 858.1 28 684.1
45×5 39 016.5 37 960.4 36 910.6 36 964.1
50×5 34 448.4 33 998.9 33 250.6 33 051.3
55×5 43 948.9 42 758.1 41 259.7 40 734.6
60×5 38 744.0 38 069.4 36 709.2 36 048.2
70×6 54 328.0 52 822.6 50 091.9 49 980.1
75×6 55 981.9 55 393.9 51 828.6 51 461.8
80×6 65 762.8 64 385.1 60 943.9 61 159.9
85×6 71 195.4 69 467.9 66 918.4 65 691.7
90×6 80 101.6 77 252.1 73 970.9 74 158.8
95×6 89 302.6 87 123.2 83 528.2 82 419.5
100×7 99 500.5 99 212.0 97 535.8 95 075.9
110×7 103 555.3 100 595.5 96 217.9 94 401.1
120×7 103 871.5 101 820.3 96 041.8 92 399.4
130×8 111 969.6 110 147.8 105 902.3 104 564.7
140×8 125 733.7 123 363.5 118 681.5 117 835.0
150×8 142 677.4 137 137.8 132 839.5 129 909.8
160×9 138 169.1 131 364.5 126 731.4 123 245.0
170×9 153 361.2 143 737.1 143 447.1 135 854.0
180×9 158 705.4 150 812.5 145 711.6 141 274.3
160×10 137 840.0 132 938.2 128 748.5 125 496.7
170×10 149 058.4 146 947.9 142 150.4 139 855.0
180×10 141 476.2 134 507.9 131 902.1 126 678.4
Average 83 489.6 80 972.8 78 319.3 76 691.4
NB 0 1 3 24
表3可知,HBICA在大部分问题上的测试结果都明显优于对比算法,表明HBICA是求解MFISP_MTBD的有效算法.HBICA一方面利用贝叶斯概率模型同化机制实现对优质解信息的高效学习与殖民地的再建构,有利于快速发现问题解空间中优质区域;另一方面利用“殖民掠夺”引导局部搜索对优质解区域进行集中优化,有利于算法对优质解区域进行较深入的搜索,从而能高效地发现复杂问题的优质解.因此,HBICA能在上述实验中取得较好结果.

5 结论

为综合考虑存在于多工厂供应链的实际运输中常见的车辆重复使用情况,本文提出了一种基于贝叶斯统计推断的混合帝国竞争算法,求解以最小化总成本为目标的MFISP_MTBD.首先,设计了基于多行程标签机制的新型编解码策略,并构造新型启发式规则以提高初始解的质量.然后,采用贝叶斯概率模型学习机制替换标准帝国竞争算法中的同化机制,将各种群向优质解区域进行快速引导.其次,采用“殖民掠夺”变邻域局部搜索机制,实现对优质区域细致而有侧重的搜索.最后,通过在不同测试问题上的仿真实验与算法比较,验证了HBICA是求解MFISP_MTBD的有效算法.

参考文献

1
GHARAEIA, JOLAIF. A multi-agent approach to the integrated production scheduling and distribution problem in multi-factory supply chain[J]. Applied Soft Computing, 2018, 65: 577-589.
2
MOONSS, RAMAEKERSK, CARISA, et al. Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion[J]. Computers & Industrial Engineering, 2017, 104: 224-245.
3
ZHENL, MAC L, WANGK, et al. Multi-depot multi-trip vehicle routing problem with time windows and release dates[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 135: 101866.
4
WANGY, LEIL F, ZHANGD X, et al. Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels[J]. Transportation Research Part B: Methodological, 2020, 139: 38-63.
5
WASSANN, WASSANN, NAGYG, et al. The multiple trip vehicle routing problem with backhauls: Formulation and a two-level variable neighbourhood search[J]. Computers & Operations Research, 2017, 78: 454-467.
6
LEEJ, KIMB I, JOHNSONA L, et al. The nuclear medicine production and delivery problem[J]. European Journal of Operational Research, 2014, 236(2): 461-472.
7
WANGJ, YAOS, SHENGJ C, et al. Minimizing total carbon emissions in an integrated machine scheduling and vehicle routing problem[J]. Journal of Cleaner Production, 2019, 229: 1004-1017.
8
GANJIM, KAZEMIPOORH, HADJI MOLANAS M, et al. A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows[J]. Journal of Cleaner Production, 2020, 259: 120824.
9
ABDOLLAHZADEHV, NAKHAIKAMALABADII, HAJIMOLANAS M, et al. A multifactory integrated production and distribution scheduling problem with parallel machines and immediate shipments solved by improved whale optimization algorithm[J]. Complexity, 2018, 2018: 5120640.
10
詹文法, 邵志伟. 一种集成电路测试流程分级动态调整方法[J]. 电子学报, 2020, 48(8): 1623-1630.
ZHANW F, SHAOZ W. Hierarchical dynamic adjustment method for integrated circuit testing process[J]. Acta Electronica Sinica, 2020, 48(8): 1623-1630. (in Chinese)
11
何小娟, 曾建潮. 基于Bayesian统计推理的分布估计算法求解柔性作业车间调度问题[J]. 系统工程理论与实践, 2012, 32(2): 380-388.
HEX J, ZENGJ C. Solving flexible job-shop scheduling problems with Bayesian statistical inference-based estimation of distribution algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(2): 380-388. (in Chinese)
12
姚友杰, 钱斌, 董钰明, 等. 基于EDA的绿色零等待作业车间调度问题求解[J]. 电子学报, 2021, 49(2): 225-232.
YAOY J, QIANB, DONGY M, et al. EDA-based for the green no-wait job shop scheduling problem[J]. Acta Electronica Sinica, 2021, 49(2): 225-232. (in Chinese)
13
CHENS F, QIANB, LIUB, et al. Bayesian Statistical Inference-Based Estimation of Distribution Algorithm for the re-Entrant Job-Shop Scheduling Problem with Sequence-Dependent Setup Times[M]//Intelligent Computing Methodologies. Cham: Springer International Publishing, 2014: 686-696.
14
杨晓林, 胡蓉, 钱斌, 等. 增强分布估计算法求解低碳分布式流水线调度[J]. 控制理论与应用, 2019, 36(5): 803-815.
YANGX L, HUR, QIANB, et al. Enhanced estimation of distribution algorithm for low carbon scheduling of distributed flow shop problem[J]. Control Theory & Applications, 2019, 36(5): 803-815. (in Chinese)
15
PÉREZ-RODRÍGUEZR, HERNÁNDEZ-AGUIRREA. Simulation optimization for the vehicle routing problem with time windows using a Bayesian network as a probability model[J].The International Journal of Advanced Manufacturing Technology, 2016, 85(9/10/11/12): 2505-2523.
16
李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度[J]. 控制理论与应用, 2019, 36(6): 893-901.
LIM, LEID M. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory & Applications, 2019, 36(6): 893-901. (in Chinese)
17
LEID M, LIM, WANGL. A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold[J]. IEEE Transactions on Cybernetics, 2019, 49(3): 1097-1109.
18
ARDALANZ, KARIMIS, POURSABZIO, et al. A novel imperialist competitive algorithm for generalized traveling salesman problems[J]. Applied Soft Computing, 2015, 26: 546-555.
19
HOSSEINIS, KHALEDA AL. A survey on the imperialist competitive algorithm metaheuristic: Implementation in engineering domain and directions for future research[J]. Applied Soft Computing, 2014, 24: 1078-1094.
20
MARANDIF, FATEMI GHOMIS M T. Integrated multi-factory production and distribution scheduling applying vehicle routing approach[J]. International Journal of Production Research, 2019, 57(3): 722-748.
21
裴小兵, 于秀燕, 王尚磊. 混合帝国竞争算法求解旅行商问题[J]. 浙江大学学报(工学版), 2019, 53(10): 2003-2012.
PEIX B, YUX Y, WANGS L. Solution of traveling salesman problem by hybrid imperialist competitive algorithm[J]. Journal of Zhejiang University(Engineering Science), 2019, 53(10): 2003-2012. (in Chinese)
22
QIANB, WANGL, HUANGD X, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 36(1): 209-233.
23
MONTGOMERYD C. Design and Analysis of Experiments[M]. Hoboken: John Wiley and Sons, 2005.

基金

国家自然科学基金(62173169)
云南省基础研究重点项目(202101AS070097)
PDF(1027 KB)

1064

Accesses

0

Citation

Detail

段落导航
相关文章

/