智能物流系统也称作物料搬运系统，其中输送系统是物料搬运系统中不可或缺的一部分．输送货物时通常采用输送机、自动引导搬运车和叉车等设备，以满足复杂的物料搬运系统需求[1]．输送设备运输货物产生的物料搬运成本与物流量和生产设施的布局密切相关．在制造业处于加速实现智能制造转型升级的关键时期[2]，制造企业希望通过降低物流成本来增加公司利润以提升竞争力，因此设施布局是实现智能制造的关键技术之一．设施布局问题(facility layout problem，FLP)[3-4]是制造产业和服务产业中的一个关键问题．设施布局问题是将须要布置的设施合理分配到指定场地，合理的设施布局能够减少物料运输距离，缩短运输时间，提高生产效率，从而极大降低企业制造成本．据统计，物料的搬运成本占据制造总成本的20%～50%，而合理的设施布局能够降低制造总成本的10%～30%[5]，因此该问题具有巨大的研究意义和实际应用价值，一直以来都是学术界和制造商的密切关注对象[6-8]．行布局问题是设施布局问题中的一种经典的构型，即车间内部所有设施排成行．行布局问题包括单行、双行、多行、环形和开放式布局，其中过道布置问题(corridor allocation problem，CAP)是双行布局的衍生物．因为过道布置问题拥有良好的布局结构和高效的物流运输效率，被广泛应用到服务行业和制造行业，是设施布局领域的新研究热点[9-11]．在实际工业生产中，产品需求量可能在一定时间段发生变化(按季度或周变化)，或者产品组合在加工期间发生变化而导致设施间物流量发生改变．为了应对这类问题，有研究者考虑调整周期之间的设施布局，以寻求跨多个周期的最低物料搬运成本与设施重新布置成本．文献[12]提出了动态设施布局问题(dynamic facility layout problem，DFLP)，并基于动态规划公式开发了精确和启发式程序．基于这项研究，文献[13]提出了一种改进的禁忌搜索算法来解决动态不等面积设施布局问题．文献[14]提出了动态单行设施布局问题，并建立混合整数线性规划模型和两种元启发式算法进行求解，通过计算20个算例验证了算法的优越性．文献[15]提出了不确定每个周期具体行数的动态行设施布局问题，并用混合进化算法求解最小化物料搬运成本和重组成本之和．以上研究均探讨了动态设施布局在实际生产活动中的重要性，然而对过道布置问题的研究通常仅考虑静态布局，本课题则开展动态环境下过道布置问题的研究．近几年相关研究将设施之间的物流量假设为固定不变的，然而随着市场繁荣、竞争激烈，传统制造逐渐发展成以消费者为导向的柔性制造．“多样化、小规模、周期可控”的柔性化生产导致设施之间的物流量以一定周期发生改变；同时，考虑到用地成本是制造业生产要素，布局面积会直接影响用地成本．近年来，土地价格增长迅速，考虑布局面积对降低布局成本很有研究价值，因此本研究首次提出了一种双目标动态过道布置问题(bi-objective dynamic corridor allocation problem，bi-DCAP)．最小化物料搬运成本和重组成本与最小化布局面积，两个量纲不同的目标可以产生多种布局方案，以灵活应用于不同场地，不同决策者也会有不同选择．双目标动态过道布置问题具有多项式复杂程度的非确定性问题(NP难题)特性，本研究提出了一种改进的猫群算法以减少求解时间．该算法采用整数编码，采用离散化后的跟踪操作和搜寻操作更新个体，并嵌入一种局部搜索操作，最后引入帕累托占优和拥挤距离机制处理双目标结果．为证明改进猫群算法的有效性和优越性，用该算法与其他算法结果进行了对比．1 双目标过道布置问题的数学模型1.1　问题描述由于市场产品的多样性和复杂性，导致车间生产计划不断调整，动态过道布置会根据生产需求调整设施布局，而静态过道布置只布置一次设施，忽略了整个规划期设施之间物流量会发生改变．为减少自动引导搬运车的搬运成本，在智能车间过道布置中，每个周期的布局取决于相邻周期物流量的变化程度．若设施布局发生变化，则将重新布置设施的成本定义为设施重组成本．图1为第一周期的布局示意图，图中：H为布置宽度；L1为上行布置长度；L2为下行布置长度．在周期1情况下，x为横坐标，下标为设施编号，x1=15.5 m，x2=3.5 m，x3=3.0 m，x4=16.0 m，x5=9.5 m，x6=9.5 m．因为物流量的变化，所以导致下一个周期的布局发生改变．在周期2情况下，x1=15.5 m，x2=9.5 m，x3=3.0 m，10.13245/j.hust.240684.F001图1动态过道布置问题示意图x4=16.0 m，x5=3.5 m，x6=9.5 m．由于设施2和设施5的位置发生变化，因此产生了设施2和设施5的重组成本．1.2　基本假设条件以下条件是为方便准确描述该问题做出的假设：a．设施形状为矩形；b．设施的物料交互点在设施沿过道一侧的中点上；c．上下两行设施均沿过道边线最左侧开始布置；d．设施布置不受场地及其他条件限制；e．过道宽度忽略不计．1.3　数学模型定义如下参数以方便模型的描述：n为设施总数量，即问题规模；I为设施编号集合，i，j，k为设施编号，i，j，k∈I；r为设施行数；T为动态周期总数；cijt为第t周期时，设施i和设施j之间的单位距离物流成本；xit为第t周期时，设施i物料交互点的横坐标；dijt为第t周期时，设施i和设施j的物料交互距离；H为设施深度，即布置宽度；li为设施i沿x轴的长度；L为布局长度；Ci为设施i的移动成本；M为一个很大的正整数．决策变量如下：yirt=1      (设施i在t周期位于第r行),0      (否则);pijrt=1      (设施i和设施j在t周期都位于r行,且设施i在设施j的左侧),0      (否则);bit=1      (设施i在t周期相比于t-1周期发生位移),0      (否则).目标函数如下：F=min{F1,F2}; (1)F1=∑t=1T∑i=1n-1∑j=i+1ncijtdijt+∑t=2T∑i=1nbitCi; (2)F2=2HL．(3)约束条件如下：L≥xit+li/2,∀t∈{1,2,⋯,T},∀i∈I; (4)dijt≥xit-xjt,∀i,j∈{Ii≠j},∀t∈{1,2,⋯,T}; (5)dijt≥xjt-xit,∀i,j∈{Ii≠j},∀t∈{1,2,⋯,T}; (6)∑inyirt≥1,∀t∈{1,2,⋯,T},∀r∈{1,2}; (7)∑r=1Ryirt=1,∀t∈{1,2,⋯,T},∀i∈I,∀r∈{1,2}; (8)pijrt+pjirt≤(yirt+yjrt)/2,∀t∈{1,2,⋯,T},∀i,j∈{Ii≠j},∀r∈{1,2}; (9)pijrt+pjirt+1≥yirt+yirt,∀t∈{1,2,⋯,T},∀i,j∈{Ii≠j},∀r∈{1,2}; (10)xit+12li+lj≤xjt+M1-∑r2pijrt,∀i,j∈{Ii≠j},∀t∈{1,2,⋯,T}; (11)xit=li+∑s=1,s≠inls(∑r=12pijrt),∀i∈n; (12)qijt=∑r2(pijrt+pjirt),∀i,j∈{Ii≠j},∀t∈{1,2,⋯,T}; (13)yirt-yirt-1≤Mbit,∀t∈{2,3,⋯,T},∀i∈I,∀r∈{1,2}; (14)yirt-1-yirt≤Mbit,∀t∈{2,3,…,T},∀i∈I,∀r∈{1,2}; (15)xit-xit-1K≤Mbit,∀t∈{2,3,⋯,T},∀i∈I; (16)xit-1-xit≤Mbit,∀t∈{2,3,⋯,T},∀i∈I. (17)所建模型中引入决策变量yirt和pijrt是为确定设施i的精确位置，bit是为确定设施i相对于上个周期是否发生位移．式(1)表示最小化F1和F2，在基本过道布置问题模型的基础上增加了一个目标；式(2)为设施之间的物料搬运和设施重组总成本F1；式(3)为设施布局面积，其中H为设施深度，忽略掉过道宽度，则2H为布局宽度；式(4)用于确定整个制造周期中最长的布局长度；式(5)和式(6)为设施的横坐标位置；式(7)约束每个阶段中两行均有布置设施；式(8)约束每个设施在每个阶段只能处于一行；式(9)和式(10)用于确定决策变量式pijrt；式(11)为防止同行设施发生重叠；式(12)为设施坐标约束；式(13)用于确定决策变量qijt；式(14)～(17)用于确定决策变量bit．2 多目标改进猫群优化算法猫群优化(cat swarm optimization，CSO)算法是一种基于猫的行为的全局优化算法，同时具有良好的全局搜索能力和局部搜索能力，能克服遗传算法搜索慢和粒子群算法易陷入局部的缺点．自提出以来，猫群优化算法已成功应用于各种优化问题[16-18]，均体现出猫群优化算法收敛快、寻优能力强的特点．因此，本研究采用猫群优化算法求解动态过道布置问题．2.1　编码与解码本研究中双目标动态过道布置问题编码方式参考静态过道布置问题，采用基于设施序列的整数编码方法．每一只猫表示一条解序列，定义第i只猫为qi={m1，m2，…，mT；qi1，qi2，…，qit，qit+1，…，qiT}，其中：m为上行设施数量；qit为第t周期的设施序列编号．qit={xt1，xt2，…，xtj，xtj+1，…，xtn}，其中n为总设施数量；xjt为第j个位置设施的编号．定义猫种群P={q1，q2，…，qpop}，其中P为种群大小．2.2　搜寻模式搜寻模式是指改进猫群优化算法的全局搜索过程．根据双目标动态过道布置问题的特点，采取一种策略将搜寻模式离散化，基本猫群优化算法搜寻模式的离散操作如下．a. 将初始猫群中每一个qi个体复制j份副本放在记忆池S中，j的大小为ceil(n/2)．b. 对记忆池中的每个个体副本Sis进行搜寻，操作步骤为：随机生成一组n个(0，1)的小数，按照升序排列；变化数D为随机生成的一个[1，n]的整数，根据变化数D的大小随机产生D个n以内的整数，对应须要改变小数的位置；之后添加扰动，改变位置；根据S×rand(∙)(S根据经验一般取0.2)产生随机数与随机生成的一组对应位置小数相加，最后对其顺序索引，产生新的解个体．为便于理解，以阶段T=2，设施数量n=8的副本个体为例，其具体操作如图2所示．10.13245/j.hust.240684.F002图2搜寻模式的离散化操作c. 分别计算记忆池中所有候选解的适应度值．d. 将适应度值进行帕累托选择，代替当前猫的位置，完成猫的位置更新．2.3　跟踪模式跟踪模式是指模拟猫跟踪目标时的情况．通过改变猫的每一维的速度来更新猫的位置，速度的改变是通过增加一个随机的扰动来实现的．与粒子群算法更新速度公式不同之处在于跟踪模式中个体是向最优个体靠近，不会向其他个体靠近．本研究对跟踪模式进行离散化处理，对原跟踪模式的参数和数学运算进行重新定义．跟踪模式是根据位置共享，个体向帕累托最优解集中的个体靠近来更新个体新位置．即vik(t+1)=(Xbestk(t)ΘXik(t)),k∈{1,2,⋯,T},i∈{1,2,⋯,n}; (17)Xik(t+1)=Xik(t)⊕r⊗vik(t+1), (18)式中：vik(t+1)为更新后第k阶段、第i个解的交换对集合；Xbestk(t)为猫群中第k阶段当前帕累托最优解集中猫的位置；Xik(t)为当前第k阶段、第i只猫的位置；Xik(t+1)为更新后第k阶段第i只猫的位置；r为(0，1)之间的一个随机值．重新定义的参数如下．减法运算定义：将Θ定义为离散化减法运算，将当前的解序列Xbestk和Xik中对应元素相减，减法结果定义成交换对集合vik(t+1)．交换对就是保留两个解序列对应不相等的元素且合并在一起产生交换对集合vik(t+1)=vik(t+1)∪Is-(Xbestk(t)ΘXik(t))，若对应元素相等，则Is-(Xbestk(t)ΘXik(t))=∅．乘法算法定义：将⊗定义为离散化乘法运算，定义运算结果为从交换对集合中选取ceil(r⊗vik(t+1))个交换对．加法运算定义：将⊕定义为离散化加法运算，定义运算结果为已选交互对分别与解序列Xik(t)发生交换，产生ceil(r⊗vik(t+1))个解序列．2.4　邻域搜索操作离散化猫群算法在搜寻模式和跟踪模式都采用的贪婪搜索策略会失去猫群多样性，猫个体在迭代过程中易陷入局部最优解．且在跟踪模式下，猫个体是以一定概率执行交换对的交换操作的，减少了个体产生数量，加快算法陷入局部最优．为跳出局部收敛状态，增加种群多样性，引入了变邻域搜索操作．该操作的主要思路是采用两点交叉操作的邻域构造方法对个体进行局部搜索，并设置阈值k．k为自适应调节搜索深度，为确保猫个体连续k次搜索适应度值不变时跳出当前个体搜索，执行下一个个体．搜索深度的更新是根据猫个体更新前后的适应度值相比较而进行的．2.5　算法步骤求解双目标动态过道布置问题的多目标改进猫群优化(ICSO)算法流程如图3所示．10.13245/j.hust.240684.F003图3改进猫群优化算法流程图3 模型与算法验证3.1　模型与算法相互验证本研究所有实验均在Intel(R) Core(TM)i5-8400 CPU、2.5 GHz主频、8 GiB内存、Windows10环境下运行．目前尚无对双目标动态过道布置问题的研究和仿真，为验证所建模型的正确性，本研究先采用CPLEX20.1.0精确求解器开发相应程序，分别对单个目标进行精确求解，之后采用算法对12个不同规模算例进行仿真测试．将算法结果中的极端值与精确算法单目标值进行对比，双向验证模型和改进猫群优化算法的正确性．12个不同规模算例的设施重新布置成本是随机产生的．由表1可知改进猫群优化算法所求极端值与CPLEX求解器求得单目标值相同，双向验证了模型和算法的正确性．然而随着设施数量逐渐增多，CPLEX求解器的运行时间大幅增长，甚至得不到最优解，而改进猫群优化算法能够求到比精确算法更好的解，证明了改进猫群优化算法在求解该问题上的优越性能．10.13245/j.hust.240684.T001表1CPLEX求解器与改进猫群优化算法求解bi-DCAP的结果序号算例n方案CPLEX求解器改进猫群优化算法F1F2时间/sF1F2平均时间/s1S9-Z-f55F1best724.50—0.37724.50160.007.05F2best—150.000.11784.50150.002S9-H9-f55F1best590.00—0.52590.00190.008.02F2best—180.000.14594.00180.003S10-S11-f55F1best402.50—0.54402.50140.006.29F2best—120.000.12485.50120.004S9-Z-f66F1best934.50—8.07934.50190.008.53F2best—170.004.50987.00170.005S9-H9-f66F1best934.00—5.87934.00200.008.61F2best—190.000.33964.00190.006S9-Z-f77F1best1 454.00—24.171 454.00210.0019.89F2best—200.00.1.521 506.00200.007S9-H9-f77F1best1 548.00—198.471 548.00230.009.75F2best—220.001.511 551.00220.008S9-Z-f88F1best2 250.00—123.562 250.00250.0042.89F2best—240.002.892 265.00240.009S10-S11-f88F1best2 133.50—408.792 133.50260.0036.13F2best—240.0024.362 150.50240.0010S9-Z-f99F1best*—*2 315.50280.0034.80F2best—280.0014.3911S9-H9-f99F1best*—*3 673.50300.0026.28F2best—300.0025.3612D2020F1best*—*26 909.501 290.002 304.45F2best—1 110.00276.3226 996.501 110.00注：—表示本轮不计算该目标；*表示运行内存不足．3.2　算法评价将S9-Z-f6算例作为研究对象，采用改进猫群优化算法与粒子群优化(PSO)算法、蚁群优化(ACO)算法和差分进化(DE)算法进行求解，从世代距离(GD)、逆世代距离(IGD)、超体积(HV)和分布性(Spread)四个指标进行评价，以验证改进猫群优化算法的性能．表2的结果是每个算法运行10次取平均值，从表2可以看出指标均是改进猫群优化算法最优．为更详细地描述算法求解特征，选取算例D20绘制了如图4所示帕累托前沿图，从图中可以看出改进猫群优化算法求解的帕累托解集更接近真实帕累托前沿，且分布均匀，再次验证了所提的改进猫群算法收敛性好，寻优能力强．10.13245/j.hust.240684.T002表2S9-Z-f6算例的各指标对比算法GDIGDHVSpread时间/sPSO11.0621.12177 3940.664.33ACO19.3825.46174 6930.437.51DE5.2711.56179 9750.386.96ICSO0.000.00185 9950.888.5310.13245/j.hust.240684.F004图4D20算例的前沿比较3.3　关于其他问题的求解由于目前暂无关于双目标动态过道布置问题的研究，为了进一步验证改进猫群优化算法的普适性和优越性，用所提算法求解了文献[9-10]研究的扩展过道布置问题，并与文献[9-11]的求解结果进行对比．表3仅展示了部分算例对比，可知除3个算例外(AKV60-1，AKV60-3和AKV75-3)，均是改进猫群优化算法所求的解更优，在计算时间上都远远少于其他算法，表明改进猫群优化算法在求解质量和求解效率两个方面都更优于其他三个算法，再次验证了改进猫群优化算法求解的优越性能．10.13245/j.hust.240684.T003表3改进猫群优化算法不同算例的运行结果对比序号测试算例nF1F2时间/s1AKV60-160739 069.000.10450.95739 052.000.002AKV60-360324 224.501.991 277.44324 442.500.053AKV70-170764 668.000.461 205.08764 691.000.044AKV70-370759 595.500.22694.19759 616.500.005AKV75-1751 197 157.500.931 234.071 197 283.500.006AKV75-375624 635.000.43898.32624 681.000.007AKV80-1801 034 751.500.501 362.941 034 779.500.008AKV80-3801 626 095.000.801 365.031 626 566.000.004 结语智能物流是智能制造的关键．而智能车间布局是智能物流系统须要着重考虑优化的方面之一．为使制造企业能够实现降本增效，一个合理的设施布局是非常必要的，因此本文研究了考虑生产制造中物流量动态变化的过道布置问题．同时，考虑到设施布局面积对动态过道布置的成本影响很大，为减少企业生产成本，本研究提出了以最小化物料搬运成本与重组成本之和及最小化布局面积为目标的动态过道布置问题，并建立了混合整数规划模型．根据问题的特性，提出了一种改进猫群优化算法求解该问题，然后通过大量实验证明了该算法在求解质量和求解效率方面的优越性．在未来的研究中还可以进一步考虑每个周期内物流量的模糊性和随机性，使其物流量能在一定范围内发生波动．