考虑设施方向的双目标过道布置问题建模与优化
2022-07-07张则强刘俊琦王沙沙
陈 凤，张则强+，刘俊琦，王沙沙
(1.西南交通大学 机械工程学院，四川 成都 610031；2.轨道交通运维技术与装备四川省重点实验室，四川 成都 610031)
0 引言
设施布局问题(Facility Layout Problem, FLP)指按确定的布局形式，在满足一定约束的情况下，对其所属的多个设施单元进行布置。设施布局是影响生产效率和成本的重要因素之一，科学的设施布局可以有效提高空间利用率、合理化物流路径，降低生产过程中10%～30%的物料搬运成本并提高生产效率[1]。由于其重要的研究意义和实际应用价值，工业界和学术界对FLP进行了一系列研究与实践[2-6]。
过道布置问题(Corridor Allocation Problem, CAP)是FLP中的一个分支，由AMERAL[7]于2012年首次提出，其主要特点为：以最小化设施间的总物料搬运成本为目标，通道两侧的设施从同一起点开始布置，且相邻设施间无间隙。由于CAP具有较好的物流运输结构和效率，被广泛应用于工业和服务领域，如医院走廊两侧各职能房间的布置[8]、学校学习及办公室的安排[9]、大型购物中心商铺的布局、半导体生产线的布置[4]等。针对CAP问题的NP-hard属性，众多学者设计了不同的智能算法，均取得较好的结果[10-11]。为进一步深入探究CAP，学者们结合实际应用不断对传统CAP进行拓展。刘思璐等[12]提出考虑设施深度的CAP，并采用烟花算法进行求解；ZHANG等[13]在传统CAP的基础上加入过道宽度约束，采用改进分散式搜索算法进行仿真求解；管超等[14]考虑双层布局更节约布局用地成本，以及实际生产中场地受限制等情况，提出以最小化物料搬运成本为目标的双层CAP，建立双层CAP的混合整数规划模型，随后设计改进花授粉算法进行求解[15]；王沙沙等[16]结合生产中的环形布局特征，提出多路径交互环形CAP，并采用改进蚁狮算法进行求解。以上研究主要集中在优化物料搬运成本，而在实际车间布局中还需要同时优化布局成本、空间利用率等多个目标。KALITA等[17]在2014年考虑通道长度对布局成本的影响，以最小化过道长度和物料搬运成本为目标，首次提出双目标过道布置问题(bi-objective CAP, bCAP)，并设计多目标遗传算法求解，然后于2019年设计融合局部搜索技术的改进遗传算法求解bCAP[18]。随后，学者们考虑通道宽度和设施受约束等情况对基础bCAP问题进行拓展[19-20]。贾林等[21]在环形布局问题中将布局面积作为优化目标之一，建立了双目标环形CAP的数学模型，并对面积成本与总物流成本作无量纲处理，将两个目标统筹为总成本进行优化，结果证明设施布置方案对布局面积有较大影响。然而，在与直线型CAP相关的研究中，鲜有学者考虑优化布局面积。布局面积又是影响布局用地成本的重要因素之一，对于利润空间较小的制造业，即使用地成本的小幅下降也可能转化为可观的额外利润，因此将最小化布局面积作为新增优化目标能更好地提高面积利用率，降低车间用地成本。另外，物料搬运成本与布局面积的量纲存在差异，而且不同决策者对两方面的侧重点不同，针对上述两个目标优化布局问题能够提供多个较优决策方案来满足不同场景的需求。
设施方向是设施布置约束之一[22]，不等面积布局研究中通常考虑设施方向对目标函数的影响[23]。在CAP问题上通常默认设施布置方向一定，而在生产或服务部门，各矩形设施宽度和深度不同的情况比较常见，在设施布置方向无特殊规定时，矩形设施可以以相邻两侧的任意一侧靠近过道。此时，即使设施布置顺序相同，矩形设施布置方向的变化也会导致设施的物料交互点位置改变，最终使设施间的物料搬运成本和布局面积出现差异。因此，在矩形设施的深度和宽度不同的CAP中，考虑设施的布置方向可以避免占用多余的用地面积，减少物流成本。
综上所述，由于布局面积直接影响布局成本，而且考虑矩形设施布置方向可有效降低物流成本，提高面积利用率，本文以最小化物料搬运成本和布局面积为目标，考虑设施布置方向，提出一种扩展双目标过道布置问题(extend bi-objective Corridor Allocation Problem, ebCAP)，并构建了该问题的混合整数非线性规划模型(Mixed Integer Nonlinear Programming model, MINLP)，然后通过LINGO软件精确求解证明所提模型的正确性，并为算法提供参考依据。由于精确求解需遍历整个解空间，求解大规模问题难度高，本文提出一种基于Pareto占优和模拟退火搜索的多目标改进分散搜索(Multi-objective Improved Scatter Search, MISS)算法。该算法以双层编码构造可行解，采用自适应模拟退火操作双向改进精英参考集，动态更新参考集以及时利用新个体优势，并设置阈值减少多余迭代过程。应用所提算法求解设施布置方向不受限的双目标CAP，再通过与精确算法计算结果对比，证明了MISS算法的有效性。为进一步说明MISS算法的优越性，应用所提算法求解bCAP问题，并与其他算法的求解结果对比，证明了MISS算法具有更高的求解效率和质量。
1 ebCAP数学模型
1.1 问题描述
传统CAP以最小化物料搬运成本为目标，将给定的n个大小不同的矩形设施合理地排布在过道两侧。在CAP中要求相邻设施间无间隙，两行设施均从左侧同一水平线开始向右布置，各矩形设施的物料交互点位于设施靠近通道一侧的中点。物料交互点的坐标可以直接根据所有设施的相对位置确定。与传统CAP相比，ebCAP以最小化总物料搬运成本和布局面积为目标，考虑了通道宽度对物流成本的影响，且矩形设施的布置方向灵活可变。因此，处理ebCAP时需确定设施的布置顺序，并明确设施的布置方向。然而，ebCAP不仅为以上两个问题叠加，设施布置顺序还会影响设施布置方向；反之，设施布置方向不同时，最优设施布置序列也会变化。因此,ebCAP的关键在于找到最适配的设施布置顺序和设施布置方向，以实现物料搬运成本和布局面积的最小化。
另外，设施布置方向对物料搬运成本和布局面积有较大影响，如图1所示的9规模设施布局方案，3个方案中设施的相对位置相同(第1行{9 1 5 2}，第2行{4 7 8 6 3})，图1a中任意设施i只能以边L1i靠近过道，图1b和图1c则分别为设施方向不固定时物料搬运成本最小和布局面积最小所对应的布局方案。图中c，H，L0分别表示通道宽度、布局宽度和通道长度，L1i和L2i分别为矩形设施i相邻两边的长度。由图1明显可见，图1a～图1c中部分设施方向的变化影响了布局的宽度H和通道长度L0，进而影响了布局方案的面积。同时，设施物料交互点也随之变动，导致设施间的物料搬运成本发生变化。
1.2 基本假设条件
(1)设施形状为矩形，且设施间的单位距离物流交互成本已知。
(2)设施的物流交互中心位于设施靠近通道一侧的中点。
(3)相邻设施之间无间隙。
(4)上下行设施均从最左侧起沿通道边线布置，即各行布置起点的横坐标为0。
(5)设施布置方案不受场地大小及其他条件限制。
(6)矩形设施的布置方向不固定。
1.3 数学模型
为便于描述模型，给出参数与变量的定义，如表1所示。
表1 参数与变量定义
续表1
本文采用曼哈顿距离计算设施间的物料搬运距离，如图2所示。图中虚线表示设施间的物流交互路径，设施的物流交互点位于设施靠过道一侧的中点，用“■”表示。若设施同行布置，如设施i和设施m，则设施间的物流交互距离dim为设施横坐标差xm-xi；若设施异行布置，如设施i和设施j，则设施间的物流交互距离为c+xj-xi。
根据双行布局问题中布局面积的定义[24-25]，布局面积为能覆盖布局方案中所有设施的最小矩形区域的占地面积，其中矩形区域的宽度称为布局宽度H，尺寸由每行中最深的机器确定。如图2所示，H等于上下行设施深度最深的设施m和j的深度与通道宽度c的和；矩形区域的长度等于通道长度L0，为最左侧起点到最右侧设施右端点的水平距离。
如图3所示，本文统称设施靠过道一侧的边长为设施的宽度，与过道垂直的边的长度为设施深度。矩形设施i的宽度有L1i，L2i两种情况，决策变量ri用于确定设施i的宽度和深度，ri=1表示设施i的宽度为L1i，ri=0表示设施i的宽度为L2i，因此设施i的宽度wi和深度Di分别为：
wi=ri·L1i+(1-ri)·L2i,1≤i≤n；
(1)
Di=ri·L2i+(1-ri)·L2i,1≤i≤n。
(2)
当ri=1时(1-ri)=0，设施i以边L1i靠近过道，因此设施i的宽度为L1i，深度为L2i。
综上所述，设施布置方向不受限的ebCAP数学模型如下：
目标函数：
F=min{F1,F2}；
(3)
(4)
F2=L0·H。
(5)
s.t.
(6)
dij≥xi-xj,1≤i (7) dij≥xj-xi,1≤i (8) (9) 1≤i,j≤n,i≠j； (10) (11) H≥Di·yiU+Dj·yjD+c, 1≤i,j≤n,i≠j； (12) 1≤i (13) Zijk+Zjik+1≥yik+yjk, 1≤i (14) 1≤i,j≤n,i≠j； (15) (16) yik∈{0,1},1≤i≤n,k∈K； (17) qij∈{0,1},1≤i,j≤n,i≠j； (18) ri∈{0,1},1≤i≤n； (19) Zijk∈{0,1},1≤i,j≤n,i≠j,k∈K。 (20) 本文在模型中引入决策变量yik，qij，ri，Zijk，以确定各设施的排列顺序和布置方向，进而确定设施的相对位置和精确位置。式(3)表示两个目标函数最小化。式(4)为目标函数F1，表示总物料搬运成本，其中dij+c(1-qij)为设施i，j之间的物流交互距离，若两个设施布置在同行，则qij=1，设施间的物流交互距离为dij；若两设施异行布置，则qij=0，物流交互距离为dij+c。式(5)表示最小化设施布局方案的总面积，其取值为能够包围布局方案的最小矩形区域的面积，F2达到最小意味着在该布局方案下，所有设施所在的矩形区域中未被利用的空余面积最小，此时平面空间利用率最高，其中布局方案的总占地面积表示为L0H，H为布局宽度，H=max{Di×yiU,Di×yiD}，L0为通道长度，L0=max{wi×yiU,wi×yiD}。 约束条件中，式(6)为设施的坐标约束，用以确定各设施的物流交互中心位置；式(7)和式(8)用于确定各设施之间沿过道的水平距离dij；式(9)确保每个设施只能布置在过道一侧；式(10)避免布置在同一行的两相邻设施重叠，若设施i与设施j布置在同行，且设施i在设施j的左侧，则Zijk=1，两设施满足xj-xi≥(wi+wj)/2，即约束布置在同一行的两相邻设施坐标的最小距离；式(11)和式(12)分别用于约束布局区域总长度和宽度；式(13)和式(14)用于约束二进制变量Zijk；式(15)和式(16)用于约束变量qij；式(17)～式(20)限定0-1决策变量的取值。 分散搜索(Scatter Search, SS)算法[26]是一种元启发式进化算法，具有能同时兼容多种调节机制的柔性框架，易与其他算法结合[27]。该算法采用系统性的方法构造新解，并兼顾种群的最优性和多样性，适用于求解多目标优化问题。SS算法最初是为连续性的单目标优化问题而设计的，近年来许多学者将分散搜索算法与其他算法融合，用于求解多目优化问题[28-30]，并取得了较为满意结果。因此，针对ebCAP问题的离散优化和多目标优化特性，本文开发了一种基于Pareto占优和模拟退火搜索的MISS算法。MISS算法的主要思想为： (1)采用双层编码定义可行解，每个可行解由代表设施布置的实数序列和代表设施布置方向的0-1编码序列表示。 (2)随机产生初始种群，并通过非支配排序选择精英参考集，根据多样性指标选择多样性参考集。 (3)在参考集中选取父代，基于双层交叉和双层变异算子产生子代，并通过连续局部变异操作扰动第2层编码来改良子代个体。 (4)动态更新参考集以及时利用子集优势，设立外部档案避免遗失非劣解。 (5)为避免可行解陷入局部最优，采用局部变异算子改进参考集，通过自适应模拟退火双向改进机制提高参考集的质量，并自适应终止算法，避免重复性的迭代工作。 解的编码方式对算法的求解效果极其重要，根据所提问题特点，本文采用双层编码方式定义可行解。可行解表示为{π,Y}，其中：π为第1层编码，是可行解的前n个单元，采用实数编码，用有序的设施编号排列表示设施布置方案，排列中设施编号的位置即为相对应设施的位置；Y为第2层编码，是可行解的n+1～2n单元，采用0-1编码，Y作为设施宽度索引确定设施宽度取值，当索引值为1时，表示设施宽度为L1i。若设施数为n，则随机排列设施集合{1,2,3,…,n}中的设施有n！种可行解。用参数m表示布置在通道上行的设施数，m∈{1,2,3,…,n/2}，因此通道两侧设施数量的分布情况有⌊(n-1)/2⌋种组合方式(⌊⌋表示向下取整)。确定上下行设施布置顺序后，需确定各个设施的宽度和深度，以0-1编码作为设施宽度索引，每个设施的布置方向有两种方案，每种设施布置顺序下设施宽度或深度有2n种可能，因此对于问题规模为n的设施宽度不定的CAP，共有(n-1)·n!·2n-1种布局方案。 为更加直观地展示编码与解码过程，以设施规模n=6的ebCAP问题为例，具体示例如图4所示。一个可行解x={4 1 3 2 5 6 1 0 0 1 1 0}，其中m=2表示布置在第1行的设施数为两个，其设施布置序列为{4 1}，设施宽度索引序列为{10}，布置在第2行的设施序列为{3 2 5 6}，设施宽度索引序列为{0 1 1 0}。 如图4所示，假设上述可行解中各矩形设施相邻两边L1i和L2i对应的向量为L1=[6 6 4 3 3 1]，L2=[4 4 6 2 1 3]。可行解x={4 1 3 2 5 6 1 0 0 1 1 0}，m=2时，设施4与设施1的宽度索引值分别为1和0，表示设施4以边L14靠近过道边线，设施1以边L21靠近过道边线，因此设施4与设施1的宽度w4=3×1+2×(1-1),w1=6×0+4×(1-0)。同理确定其余设施的宽度和深度，得到宽度向量W和深度向量D，W=[4 6 6 3 3 3]，D=[1 6 4 4 1 1]；最后根据上述数据可以确定设施坐标、布局宽度和长度，进一步得到可行解的布局面积和物料搬运成本,并根据两个目标评价可行解，详见第1.3节。 目前，与CAP相关的大部分研究主要以最小化总物料搬运成本为唯一目标，本文在最小化总物料搬运成本的基础上新增目标F2(最小化总布局面积)。与单目标优化问题相比，多目标问题的各个目标之间存在冲突和量纲差异，无法直接比较解的大小。为此，本文用Pareto占优思想处理双目标问题，对于任意两个可行解x1和x2存在支配、被支配和互不支配3种关系。若任意两个可行解x1和x2满足式(21)，则称x1支配x2，或称x1Pareto占优于x2。若可行解x1不被任何解支配，则称x1为非劣解。多目标问题的非劣解通常不止一个，由多个非劣解组成的非劣解集对应的目标矢量组成的曲面或曲线称为Pareto前沿。 (21) 为避免在迭代过程中丢失高质量解，算法每次迭代产生的非劣解都会记录到外部档案并进行更新。外部档案非劣解数量过多会降低算法运行速率，兼顾求解质量和运算效率，引入带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)中的拥挤距离机制[31]使解集均匀分布，并设置外部档案的容量为10。拥挤距离由相邻个体的几何距离确定，分别基于目标F1，F2对可行解进行升序排列，在目标s下排序为第i的可行解对应Fs的拥挤距离为 (22) 关于两个目标的第i个非劣解xi的拥挤距离为 (23) 因为分散搜索算法注重参考集的多样性和内部最优性，所以结合ebCAP的特点对文献[32]的多样性产生方法进行改进，提出如式(24)所示的多样性评价标准构建多样性初始参考集。 D(x1,x2)= (24) 分散搜索算法中子代解来源于参考集refset，通过精英解集和多样性解集组合产生新解。考虑可行解的双层编码结构特点，本文基于部分映射杂交法(Partial-Mapped Crossover, PMX)设计双层交叉算子，具体过程如图5所示。其中双层交叉运算的两个父代个体为Parent1={πp1,Yp1}，Parent2={πp2,Yp2}，交叉后生成的子代个体分别为Offspring1={πs1,Ys1}，Offspring2={πs2,Ys2}，随机选择两个父代个体的第1层编码πp1，πp2中的基因片段进行交叉操作，并对第2层编码序列Yp1，Yp2中对应的基因片段进行交叉处理，最后采用部分映射方法消除编号冲突。 变异算子包括双层变异算子和局部变异算子，如图6所示。双层变异算子通过交换任意两个基因产生新个体，操作过程中两层基因需同步互换变异，即随机选择第1层序列πs1上的两个位置，将两个位置上的基因互换，同时确定第2层序列Ys1上相对应的两个位置并互换基因。由于本文所提ebCAP考虑矩形设施布置方向，为使设施布置方向改变产生新解，针对第2层编码序列Ys1设置局部变异算子，随机选择序列Ys1中的任意基因g，通过公式g=abs(1-g)进行变异操作。 参考集refset由精英参考集refset1和多样性参考集refset2组成。对当前种群进行非支配排序，排序等级在前b1位的高质量可行解构成精英参考集refset1，refset2则按多样性评价标准从剩余P-b1个个体中选取与精英参考集多样性程度最高的2个解放入多样性参考集refset2，然后在剩余个体中选取与当前refset2中已有个体的多样性程度最高的解放入refset2，重复该过程直到完成多样性参考集refset2的构造。 当前个体xo与精英参考集refset1的多样性程度 (25) 当前个体xo与当前多样性参考集refset2所含个体的多样性程度 (26) 因为子集中的解来源于参考集，所以在精英参考集和多样性参考集中随机选取两个父代个体组合为新个体。针对ebCAP双层编码的特性，子集的产生分为两个阶段：①对父代个体进行双层交叉和双层变异操作，得到设施布置顺序改变但设施布置方向保持不变的新个体；②对当前新个体的第2层编码(设施宽度索引序列Y)采用局部变异操作，以优化新个体的设施布置方向，最终产生子代个体。子集的产生流程如下： Input:精英参考集中的父代个体x1、多样性参考集中的父代个体x2、连续局部变异次数L0 Initialization parameter：l=0； Begin while l if Δf1(Δf2)<0 or Δf1(Δf2)=0∩Δf2(Δf1)<0； end if l=l+1； end while 传统的分散搜索算法采用局部搜索改进当前种群的每一个体，虽然能在一定程度上改进当前解，但是耗时较长。参考集在迭代过程中指导解的进化方向，保持高质量的参考集能获得高质量的子集。因此，本文仅针对参考集中的个体进行改进，将解的改进分为两部分：①针对参考集中所有个体的第2层编码(设施宽度索引序列Y)，采用局部变异算子进一步优化设施布置方向，以改进目标值；②针对精英参考集，采用自适应模拟退火操作来双向改进精英参考集中的全部个体，指导精英参考集向两个目标极值方向优化。模拟退火双向改进机制详见2.8节。 为及时更新参考集，避免算法陷入局部最优，针对精英参考集设计模拟退火双向改进机制。针对目标函数F1，将精英参考集升序排列，排序序数为奇数的个体分配到真子集1，序数为偶数的个体分配至真子集2，真子集1中的个体以目标F1为优先改进对象，目标F2为次优化对象，真子集2中的个体以目标F2为优先改进对象，目标F1为次优化对象。由于所提ebCAP是双目标优化问题，需要对Metropolis准则进行改进，具体为：当优先改进对象为目标F1时，若F1(xnew)-F1(xold)<0，则接受xnew替代xold；若F1(xnew)-F1(xold)=0且F2(xnew)-F2(xold)<0，则接受xnew替代xold；若F1(xnew)-F1(xold)>0，则在区间(0,1)内随机产生一个随机数P用于决定是否接受新解，若P>rand则接受当前解，否则拒绝新解。同理，当优先改进对象为目标F2时，若F2(xnew)-F2(xold)<0，则接受xnew替代xold；若F2(xnew)-F2(xold)=0且F1(xnew)-F1(xold)<0，则接受xnew替代xold；若F2(xnew)-F2(xold)>0，则在区间(0,1)内随机产生一个随机数P，若P>rand则接受当前解，否则拒绝新解。概率P的计算公式为： P= (27) 式中：Δf0=Fo(xnew)-Fo(xold),Δfc=Fc(xnew)-Fc(xold)，Δf0表示新解xnew与当前解xold在主要优化目标Fo上的差值，Δfc表示新解xnew与当前解xold在次要优化目标Fc上的差值，Fo，Fc∈{F1,F2}且Fo≠Fc。下面为模拟退火双向改进机制的伪代码： Input:参考集中的精英解x、开始温度T0、终止温度Tend、连续未优化次数NoptIters、链长L0 Initialization parameter x→xbest； Begin while T for l0=1:L0 x′=Mutate(x)/采用双层变异算子和连续局部变异算子进行贪婪搜索，产生新个体x′； 计算可行解x′与x在目标函数F1(F2)上的差量Δf1(Δf2)； Δf1<0 or Δf1=0∩Δf2<0；/优先改进对象为目标F1时 (if Δf2<0 or Δf2=0∩Δf1<0；)/优先改进对象为目标F2时 x′→x； else依据式(32)计算接受概率P，随机数rand∈(0,1)； if P>rand x′→x； end if end if end for else inter=inter+1/降温过程中最优解保持不变的次数； end if if inter>NoptIters/如果连续未更新次数达到NoptIters，则终止迭代。 Break； end if T=T·q； end while Output:xbest 为兼顾求解质量和效率，算法采用自适应模拟退火操作对精英参考集进行双向改进。自适应模拟退火操作通过在算法中设置双阈值实现，参数glob为外部档案连续未更新的次数，参数switch为进行模拟退火双向改进的次数。若迭代过程中外部档案未更新，则glob=glob+1，否则glob=0。当外部档案连续未更新次数达到阈值glob_max(即glob=glob_max)，则触发模拟退火操作来双向改进精英参考集，并令glob=0,switch=switch+1，当执行双向改进机制的次数switch达到阈值switch_max时，不再执行该操作。 参考集更新涉及refset1与refset2更新。为提高算法收敛性能，及时利用新个体优势，本文采用动态方法更新参考集，即每产生一个新个体，将其与精英参考集中个体逐一比较，若新个体能够支配精英参考集的解，则将原精英参考集中被支配的解移除，将新个体加入精英参考集，否则将其与多样性参考集中的个体进行比较，根据式(26)计算新个体与多样性参考集中个体的多样性程度，若新个体的多样性优于多样性参考集中的个体，则用新个体替换refset2中多样性最差的个体。 在保证求解质量的前提下，为提高算法求解效率，设置阈值避免多余的迭代次数。当不再执行模拟退火双向改进机制(switch=switch_max)时，若迭代过程中外部档案连续未更新次数达到glob_max次，则终止迭代。 综上所述，所提多目标MISS算法流程如图7所示,具体操作步骤如下： 步骤1初始化参考集容量b、内循环最大迭代次数count_max、外部档案连续未更新最大次数glob_max、第1行能布置设施数量的上限m_max和双向改进机制最大次数switch_max等，令计数器glob=0，switch=0，count=0。 步骤2按照多样性初始解产生方法生成初始种群，产生初始参考集refset。 步骤3采用模拟退火双向改进机制改进精英参考集refset1，对参考集refset中的所有个体进行局部变异，并建立外部档案。 步骤4针对参考集中任意两个解，采用双层交叉算子和变异算子产生子集，更新参考集，直到参考集中两两个体完成上述操作。 步骤5对参考集中的所有个体进行局部变异，并更新外部档案。若外部档案更新则glob=0，否则glob=glob+1。若glob>glob_max且switch 步骤6采用模拟退火双向改进机制改进精英参考集refset1,并重置计数器glob，令glob=0。 步骤7令count=count+1，若count>count_max则结束内循环，令m=m+1，并执行步骤8；否则，重复执行步骤4和步骤5。 步骤8若m>m_max则算法终止，否则，初始化参数设置，并重复执行步骤2～步骤8。 为分析所提算法性能，采用趋近度指标CM[33]和间距指标SM[31]评价Pareto非劣解集的收敛性和分散程度。CM表示算法所得的Pareto非劣解目标空间与真实Pareto前沿的趋近程度，其值越小，所得Pareto解集越趋近真实Pareto前沿；SM表示算法所得非劣解在目标空间的分布范围，SM=0表示所得非劣解完全均匀分布，其值越小表示分散程度越高。 CM指标表达式为： (28) (29) SM指标表达式为： (30) (31) (32) 本文所有实验采用的计算机硬件配置为Intel(R)Core(TM)i5-8300、主频2.30 GHz、内存8 GB，Windows 10操作系统。由于ebCAP尚无测试算例的运算结果，采用LINGO优化器根据MINLP数学模型开发相应程序求解小规模算例，以验证所提模型的正确性，并为本文所提算法提供依据。为验证所提MISS算法的求解性能，应用MATLAB R2016b对40个不同规模的测试算例进行仿真试验，测试算例S5为本文所提算例，其余算例均来自文献[12]，设置模型中的通道宽度为各设施深度和宽度的最小值，即c=min(min(L1),min(L2))。经过大量算例测试和程序调试后，确定的参数设置如表2所示，另外兼顾求解效率与质量，在大量数据测算后总结得出两行分界点m的取值区间为[floor(n/2)-2,floor(n/2)+1]。参数含义详见第2.8节。 表2 算法参数设置 表3 MISS算法和精确算法求解ebCAP的结果 续表3 对比LINGO求解器与MISS算法求解结果，对于算例S5，所提MISS算法求解得到的极端值与精确算法所得的全局最优解相同，证明所建MINLP数学模型的正确性以及所提MISS算法的有效性。然而，随着问题规模的增大，精确求解方法的求解难度增加。设置LINGO求解器的运行时间为3 600 s时，精确求解器求解问题规模大于5的算例的结果略差于MISS算法求得的极端值，且MISS算法得到较优解的时间较短。 为验证算法性能，权衡求解结果和计算时间，以S9，Am13a，H20，N25_03，N30_02，ste_36_02，sko_42_02，sko_49_02为对象，采用MISS算法对上述8个算例重复运行10次，将所得的10组数据合并进行Pareto筛选，并将得到的非劣解作为各算例的真实Pareto前沿，分别计算8个算例运行10次得到的Pareto前沿所对应的10个CM和SM指标，根据上述指标绘制箱型图，如图8所示。图中，上下框线、箱内虚线与箱内实线分别对应各指标的上下四分位点、平均值和中位值，上边缘和下边缘分别表示对应指标的最大值和最小值，“+”表示异常值。 鉴于目前尚无对ebCAP的研究及仿真运算，为验证算法的求解质量和效率，采用本文所提MISS算法求解文献[17]提出的以最小化物料搬运成本和最小化过道长度为目标的bCAP。由于ebCAP和bCAP在编码方式上的差异(ebCAP采用双层编码表示可行解，bCAP采用单层实数编码表示可行解)，MISS算法求解bCAP时不涉及对第2层编码的交叉与变异操作，而且参数设置也不同。因此，兼顾求解效率与质量，经过大量算例测试和程序调试后确定的求解bCAP参数设置如表4所示。 表4 MISS求解bCAP的参数设置 在求解中小规模bCAP算例时，考虑对比的公平性，每个算例连续运行30次，与文献[17]运算次数相同，并选取一组最优Pareto非劣解与文献[17]进行比较。表5所示为MISS算法与文献[17]中pGA(permutation-based genetic algorithm)算法求解中小规模bCAP测试算例结果的对比，表中第4列和第5列为MISS算法求解的Pareto最优解，第6列为算法求解时间。表中，加粗的数值表示pGA算法与MISS算法求解的Pareto最优解相同，括号内的的数值表示pGA算法求解的Pareto最优值，画下划线的数值表示对应算法所得结果更优。由表5可得，对比中小规模测试算例，除测试算例N30_5外，MISS算法均能求得文献[17]所求10个算例的最优极端值，而且对于Am12b，Am13a测试问题，MISS算法不但所得结果更优，而且求得与pGA算法所得Pareto最优解互不占优的非劣解。综上所述，MISS算法在求解多目标中小规模问题上更具优势。 表5 MISS算法与其他算法求解bCAP中小规模算例结果的对比 续表5 表6 MISS算法与其他算法求解bCAP大规模算例结果的对比 续表6 对比表中3种算法的求解结果，MISS算法所得结果均能支配文献[17]中pGA算法所得的两个最优解；与文献[18]的混合pGA算法相比，对于算例AKV60-4和AKV80-4，混合pGA算法所得最优解与MISS算法所得最优解互不占优，均分布在Pareto前沿上，在其余算例的对比上，除测试算例AKV60-5，AKV70-5和AKV75-5外，MISS算法所得非劣解完全支配混合pGA的解，求解质量更高。综上，本文所提算法拓宽了Pareto解集的宽度，而且在求解质量上更具优越性。在求解效率方面，由于文献[18]未给出求解时间，仅对比MISS算法与pGA算法的求解时间，结果表明MISS算法运行30次的平均时间均低于pGA算法，其求解效率更高。由以上对比可知，相比pGA算法和混合pGA算法，MISS算法在求解质量和求解效率上具有明显优势。 针对现有CAP研究中忽略布局面积对成本的影响以及未考虑矩形设施布置方向的不足，本文以最小化总物料搬运成本和布局面积为目标，提出考虑设施方向的双目标CAP，并提出一种MISS算法求解ebCAP，然后通过大量实验证明所提算法的优越性。本文的主要工作如下： (1)考虑矩形设施布置方向，以最小化物流成本和布局面积为目标，建立了ebCAP的MINLP模型，并通过LINGO精确求解器验证该模型的正确性。 (2)由于ebCAP具有NP-hard属性，本文提出一种基于Pareto占优的MISS算法，采用双层编码方式构造可行解，据此设计双层交叉和变异算子，并引入拥挤距离机制保证非劣解的均匀分布；为提高算法搜索效率，本文采用自适应模拟退火双向改进机制优化参考集，并设置阈值减少多余迭代次数。 (3)采用MISS算法对40个不同规模(5～49)的ebCAP算例进行求解，并与精确算法求解结果对比，结果表明针对问题规模小于9的算例，MISS算法所得结果与精确解相同，证明了所提算法的有效性。另外，采用MISS算法求解bCAP问题，并与pGA算法和混合pGA算法对比，证明了所提算法在求解质量和求解效率上均更具优势。 (4)以不同规模的8个算例为对象，重复运算10次，计算每次趋近度指标和间距指标，数据结果表明MISS算法具有良好的收敛性，所得Pareto非劣解集具有更好的分散性。 未来研究将进一步考虑相邻设施间工作区域的干扰对布局方案的影响，使其更加贴合实际情况。另外，还可以考虑由于产品迭代或周期性生产订单导致的物流动态变化对具体布局结果的影响，以权衡车间内的物流成本和设备重排成本。2 求解ebCAP的MISS算法
2.1 解序列的编码和解码
2.2 多目标处理方法
2.3 多样性评价标准
2.4 交叉算子与变异算子
2.5 产生初始参考集
2.6 子集的产生
2.7 解的改进
2.8 模拟退火双向改进机制
2.9 参考集更新和停止准则
2.10 算法流程
2.11 Pareto解集评价指标
3 算法验证
3.1 ebCAP问题验证
3.2 算法评价
3.3 中小规模算例
3.4 大规模算例
4 结束语
