混合模拟退火及分散搜索优化过道布置问题

毛丽丽，张则强，朱立夏

西南交通大学 机械工程学院，成都 610031

1 引言

合理的设施布局可以节约10%～30%的搬运和等待成本，提高生产效率[1]。过道布置问题（Corridor Allocation Problem，CAP）作为设施布局问题[2-4]的一种特例，是典型的NP-hard问题，求解难度较大，且在工业和服务部门中应用广泛[5-6]，如教学楼、医院、行政办公楼、大型购物中心、半导体生产线等的布置。因而，该问题自2012年首次提出以来便引起了广大学者的高度关注。

过道布置问题指将一系列给定数目的设施布置到过道的两侧，并寻求一种最优布置，使全部设施对间的总流量（物流量、人流量）成本最小，要求同一行任意两相邻设施间没有间隙，且上下两行设施均从过道的最左边同一点开始布置。

Amaral[7]首先提出了过道布置问题，建立了该问题的混合整数规划模型，并采用三种启发式方法对规模不超过30的测试问题进行试验，结果表明启发式方法的求解效率明显优于精确方法，但其求解时间仍有待进一步改善。为提高求解效率，Ghosh等[8]应用遗传算法和分散搜索算法来求解该问题，试验结果表明两种智能算法均能获得近优解，且在运行效率上分散搜索算法较遗传算法更具优势。但在求解设施数为42和49规模的测试问题时，分散搜索的最大求解时间为3 716.16 s，还有进一步提升的空间。Ahonen等[9]采用模拟退火算法和禁忌搜索算法对不同规模的过道布置问题进行了验算与对比，模拟退火算法在求解质量和求解效率方面表现出了更优的搜索性能。但文中模拟退火算法求解问题规模为15的测试例子时，其平均求解时间为12.02 s，而在求解问题规模为30的测试例子时，其平均求解时间仅为4.58 s，不符合问题规模越大求解时间越长的规律。上述文献为过道布置问题的研究提供了参考，但求解性能还有进一步改善的空间。

分散搜索算法采用其框架中的一系列系统性方法代替搜索过程的随机性实现对问题的优化，具有全局搜索能力强、灵活性好、易与其他算法相结合等优点。目前已成功应用于许多组合优化问题，如无人机路径规划问题[10]、拆卸序列优化问题[11]、车间调度问题[12]、配电系统规划问题[13]等。参考已有文献，尚未发现有关分散搜索算法和模拟退火算法相结合求解过道布置问题的公开报道。

鉴于现有研究的不足，本文结合过道布置问题特点以及分散搜索算法求解组合优化问题的优势，提出一种混合分散搜索算法（Hybrid Scatter Search，HSS）求解该问题。通过引入模拟退火操作[14]，对参考集中的解进行局部优化，并设计了双层参考集、动态参考集更新方法等多种改进机制。通过对大量不同规模的测试问题的试验与对比，验证了所提算法求解过道布置问题良好的求解性能。

2 过道布置问题

2.1 问题描述

过道布置问题如图1所示，指将n个不同的矩形状设施布置到过道两侧，找到一种使全部设施对间的总流量（物流量、人流量）成本最小的布置方案，确定过道两侧每一行上的设施数量及其排列顺序，要求同一行任意两相邻设施间没有间隙，且上下两行设施均从过道的最左边同一点开始布置。图中有阴影部分的小圆圈表示流量交互点，表明每个设施的流量交互点均位于设施靠过道边线中点。

图1 过道布置问题

2.2 基本假设条件

（1）每个设施靠过道边线的宽度及各设施对间的流量为已知量。

（2）每个设施的流量交互点均位于设施靠过道边线中点。

（3）同一行相邻两设施间没有间隙。

（4）上下两行设施均从过道最左边同一点开始布置。

（5）假设上下两行设施间的过道宽度为0。

（6）设施布置不受场地大小及其他条件限制。

2.3 变量与参数定义

为描述方便，模型中用到的数学符号的意义如下：

n：问题规模，即设施的数目；

I：设施集合，I={1,2,…,n}；

i,j：设施编号，i,j∈ I；

cij：设施i,j之间的流量成本， ∀i∈I1,∀j∈I2，I1={1,2,…,n-1},I2={i+1,i+2,…,n};

li：设施i的宽度；

dij：设施i和设施j靠过道边线中点间的横坐标距离；

αij：二进制变量，若设施i,j分配在同一行，且设施i布置在设施 j的左边，则αij=1，否则αij=0。

2.4 数学模型

过道布置问题的混合整数规划模型[7]M1如下：

式中，目标函数（1）表示最小化总流量成本，约束（2）和（3）用于计算各设施间的距离，约束（4）用以防止同行的设施位置发生重叠放置，约束（5）～（8）用于确定决策变量αij，式（9）给定决策变量αij的定义域。

3 混合模拟退火及分散搜索算法

3.1 多样性初始解产生方法

解的编码和解码示意图如图2所示，本文结合过道布置问题的特点，采用一种基于设施编号的编码方式，通过这种方式可将一种布置方案编码成一个设施编号的序列。对于设施数目为8的过道布置问题，随机排列8个不同的自然数就可得到该问题的一个可行解，例如x=[1 4 6 3 7 5 2 8]。假设此时布置在上下行的设施个数分别为3个和5个，图中用符号“|”表示分隔点，则解x解码为：从过道最左边为起始点，从左往右排列，布置在第一行的各设施编号依次为1、4、6，布置在第二行的各设施编号依次为3、7、5、2、8。

图2 解的编码和解码

由于分散搜索算法对初始解的依赖性强且及其敏感，故初始种群中的解必须是高质量和多样性好的解。鉴于此，本文采用Kothari和Ghosh[15]提出的多样性产生方法DIV-1代替随机法构建初始种群，使初始解在解空间具有良好的分散性。解的多样性评价标准见公式（10）：

式中，解x1和x2之间的偏离距离d(x1,x2)为解x1和x2对应位置上两个设施编号差值的绝对值加权和。定义解x1和x2之间的最小偏离距离为解x1和x2之间的偏离距离与解x1和x2的倒置解之间的偏离距离的最小值。

过道布置问题的多样性初始种群的产生过程为：首先，随机交换种子解x=[1,2,…,n]中两个设施的位置产生US个候选解构成候选种群，并从中选出ES个目标函数值最小的候选解构成精英种群，接着将精英种群中最大最小偏离距离对应的两个精英解作为初始解移到初始种群中。然后循环以下操作，直至产生PS个初始解：计算当前精英种群中任意一个精英解和初始种群中所有解的最小偏离距离，将最大最小偏离距离对应的精英解从精英种群移到初始种群中。

3.2 参考集产生方法

针对传统参考集中仅包含高质量解，容易陷入局部最优的不足，本文采用包含b个高质量和多样性解的双层参考集[16]来为增加解的多样性，扩大搜索范围，避免算法过早收敛。双层参考集Refset由两个子集Refset1和Refset2组成，即 Refset={Refset1，Refset2}，Refset1、Refset2中分别包含b1个高质量解和b2个多样性解，且满足b1+b2=b。高质量和多样性解通过目标函数值选取，即在初始种群中选取b1个总流量成本最小的解作为高质量解、b2个总流量成本最大的解作为多样性解，得到初始 Refset={x1,…,xb1,xb1+1,…,xb}。其中，解 xk(k∈I)的总流量成本 f(xk)按从小到大排列，即 f(x1)最小，f(xb)最大。

3.3 子集产生方法

根据分散搜索算法的原理，采用子集产生方法对Refset中的解进行操作，产生一系列用于子集合并方法的候选解集。为避免产生重复的子集，提高求解效率，改进常用的二元子集产生方法，生成两种类型的二元子集，用 X1、X2表示：X1型的子集由Refset中未更新的解连续成对选取得到；X2型的子集由Refset中新添加的解和未更新的解组合得到。

3.4 子集合并方法

针对二元子集的特点，采用部分映射交叉算子对子集产生方法产生的子集进行合并操作，如图3所示。首先，在父代解中随机产生两个交叉点，用“|”表示，则交叉点间的元素即为映射元素，图3中6和2、3和1、7和4均互为映射元素。然后将父代解复制到子代解中，交换子代解交叉点间的映射部分，并将映射部分之外和映射部分相同的元素修改为其对应的映射元素，如子代解1中的第一个元素为1，而映射部分已存在该元素，故将其修改为对应的映射元素3，以此类推，即可得到交叉后的最终解。

3.5 解改进方法及模拟退火操作

图3 部分映射交叉

本文采用插入法作为局部搜索方法，对初始种群中的解或子集合并产生的新解进行局部改进。进而利用模拟退火操作较强的局部搜索能力及其跳出局部最优的机制再次优化参考集中的解，以提高获得全局最优解的概率。基于此，提出一种两阶段混合改进策略。

第一阶段：针对每一个子集合并产生的解，采用插入法将设施序列中的某个设施从其所在的位置移除，并插入到该序列的另外一个位置产生一个新解；比较插入前后解的目标函数值，保留目标函数值较小的解。重复执行该操作，直至完成所有插入邻域的搜索，最终输出的最小目标函数值对应的解即为改进后的解。插入法的原理如图4所示。

图4 插入法

第二阶段：为减小运算量，提高算法求解效率，仅将Refset中目标函数值最小的解x1作为初始解，运用模拟退火操作作为局部改进法进一步优化解x1。

模拟退火操作中各参数定义为：初始温度T0，终止温度Tend，降温速率q，链长L。Metropolis接受准则为：

其中，增量df=f(x)-f(x1)，f为目标函数值，T为当前退火温度，解x为随机交换解x1中的设施产生的新解。

3.6 参考集更新方法

比较解改进方法后产生的新解与当前Refset中解的质量或多样性，更新Refset。为实时更新参考集，及时利用新解的优良特征，加快算法的收敛速度，本文采用动态参考集更新方法[16]，即每生成一个新解，就对Refset进行一次更新。若新解的质量或多样性优于Refset中的解，则用新解替换Refset中质量或多样性方面最差的解。

3.7 算法步骤

本文以分配给第一行的设施数nu大于所设定的第一行最大设施数T2为算法的终止准则。HSS流程如图5所示。

HSS具体步骤如下：

步骤1算法参数初始化：n,PS,b,T0,Tend,L,q，内循环最大迭代次数iItermax等，令nu=T1。

步骤2按照多样性初始解产生方法生成初始种群。

步骤3插入法优化初始种群。

步骤4生成初始参考集。

步骤5初始化算法全局近优解xopt=x1，其中，x1为初始参考集中目标函数值最小的解；令计数器count和i均为0。

步骤6按照3.3节～3.6节内容进行子集产生、子集合并、插入法改进解、更新参考集操作。

步骤7运用模拟退火操作对当前参考集中目标函数值最小的解x1进行进一步优化。

图5 HSS流程图

步骤8比较算法全局近优解xopt的目标函数值f(xopt)和当前解x1的目标函数值f(x1)的大小，若f(x1)＜f(xopt)，则xopt=x1，令count=0；否则count=count+1。

步骤9若count＞h1，即在当前nu下全局近优解xopt连续h1次未改进，则nu=nu+1，转步骤11；否则i=i+1，直接进入下一步。

步骤10若i＞iItermax，则nu=nu+1，进入下一步；否则转步骤6。

步骤11若nu≤T2，则转步骤2；否则输出算法全局近优解xopt及其目标函数值f(xopt)，算法终止。

3.8 算法复杂度分析

从HSS算法的流程可以看出，算法的计算时间主要花费在迭代过程中，对于分配给第一行的设施数为nu、参考集规模为b、问题规模为n、内循环最大迭代次数为iItermax的问题，算法的时间复杂度主要由以下几个部分组成：产生多样性初始种群的时间复杂度为O(n2)，插入法的时间复杂度为O(3n4)，生成初始参考集的时间复杂度为O(1)，产生子集的时间复杂度为O(1)，合并子集的时间复杂度为O(1)，内循环中插入法的时间复杂度为O(3b2n4/2-3bn4)，更新参考集的时间复杂度为O(1)，模拟退火操作的时间复杂度为O(2 292n3-458n3lg(n-1))。因此，内循环迭代iItermax次时，总的时间复杂度最差为：

本文中参数nu的取值区间跨度为3，因此，整个HSS算法的时间复杂度为：

4 实验结果与分析

为验证所提HSS的有效性，针对设施数从9～49不同规模的24个过道布置问题，应用所提HSS进行测试，并与基本SA、SS的求解结果进行对比。算法实验采用的计算机硬件配置为Intel Core i3-2100 M，3.1 GHz，2 GB内存，在Windows 7操作系统下使用MATLAB R2010b软件开发了所提算法的实验程序。测试数据来源于文献[7，17-20]。

兼顾求解性能与求解效率，经多次运算测试，算法部分参数设置如下：T1=floor(n/2)-2,T2=floor(n/2),nu=[T1,T2]，Tend=0.1/n，L=2n，q=0.99，b=8，b1=b2=4，iItermax=200；针对n不超过15的小规模问题，T0=100，h1=5，US=2floor((n-1)/2)，ES=14，PS=12；针对 n大于 15的大规模问题，T0=10 000，h1=15，US=1 000，ES=500，PS=40。其中，参数nu的取值区间设置参考文献[7]。

为更准确地说明所提算法的求解性能，针对每种算法，每个测试问题均运行10次，共计720个计算结果。为更加简洁直观地展现三种算法的计算结果，对其进行了整理、归纳，得到表1所示结果，包含了目标函数值f和解的偏差gap。其中，与当前已知最优目标函数值f0的偏差gap定义为gap=(f-f0)/f0×100%，“*”表示文献[7]中用精确方法求得的最优解的目标函数值，“+”表示启发式方法求得的近优解的目标函数值，“++”表示文献[9]求得的近优解的目标函数值。

从表1可以看出：针对设施数小于15的8个小规模测试问题，HSS均求得了最优解；针对大规模测试问题，HSS求得的近优解的f与f0的偏差均不超过0.03%，特别是对于问题 N-30-01、N-30-02、N-30-03、N-30-04、N-30-05、sko-42-01和sko-49-01，HSS均求得了 f0，偏差为0，验证了HSS求解CAP的有效性。

对比表1中三种算法的求解结果：在所测试的24个问题中，HSS求得的近优解的f均比SA、SS求得的f更接近 f0；SA、SS的求解结果与 f0的最大偏差分别为0.18%、8.88%，大于HSS的最大偏差0.03%，表明HSS较SA、SS更具有求解优势。

表1 HSS和SA、SS的求解结果比较

图6 SA和HSS的求解偏差对比

为更直观地观察HSS的求解优势，根据表1中的计算结果，绘制了HSS分别与SA、SS的求解偏差对比图，如图6、7所示。由图可知，针对每个测试问题，HSS的求解偏差gap均小于等于SA、SS的gap，表明HSS具有良好的求解性能；随着问题规模的增加，SA的求解偏差曲线波动剧烈，SS的求解偏差呈逐渐上升的趋势，而HSS的求解偏差增长平缓，体现了HSS具有良好的求解平稳性。由此可知，所提混合分散搜索算法较单一搜索算法和模拟退火算法在求解质量和平稳性方面具有优势。

为进一步验证所提混合分散搜索算法的求解性能，将HSS与文献[7]中的精确方法和启发式方法、文献[8]中的遗传算法（CAP-GA）和分散搜索算法（CAP-SS）的求解结果进行对比，得到如表2所示结果，包含了目标函数值f和CPU运算时间。

图7 SS和HSS的求解偏差对比

分析表2可知，对于小规模测试问题，HSS均求得了和文献[7]中精确方法相同的最优解，但HSS的求解时间远小于精确方法。随着问题规模的增大，精确方法的求解时间呈指数级增长，最大求解时间为10 298.01 s，且当问题规模为15时，已无法在合理的时间内求得最优解，而HSS的求解时间增长缓慢，最大求解时间仅为16.57 s，远小于精确方法的求解时间。针对设施数为30的测试问题，启发式方法和HSS求得了相同的近优解，但启发式方法的平均求解时间为HSS的24倍，表明HSS的求解性能优于启发式方法。

表2 HSS和不同算法的比较

将HSS与CAP-GA的求解结果进行对比：在求解质量方面，对于设施数不超过30的测试问题，CAP-GA和HSS的求解结果相同，但对于设施数为42和49的测试问题，HSS的求解质量明显优于CAP-GA；在求解时间方面，针对每个测试问题，HSS的求解时间均远小于CAP-GA，且随着问题规模的增大两者之间的求解时间差距大幅度增加，尤其对于测试问题sko-49-01，CAPGA的求解时间为HSS的15倍，表明HSS较CAP-GA具有求解优势。

对比CAP-SS和HSS的求解结果可知，对于前15个测试问题，HSS以略大于CAP-SS的求解时间得到了相同的解，但对于更大规模的测试问题，HSS的平均求解时间仅为CAP-SS的1/2，特别是对于测试问题sko-42-03、sko-42-04、sko-42-05、sko-49-01，HSS 比 CAP-SS 求得了更优的解。由此可知，较对比的CAP-SS，HSS具有求解优势。

根据表中数据，绘制了如图8所示的CPU运算时间曲线图。需要指出的是，HSS的求解时间随问题规模的增大而缓慢增加，增长幅度小于所对比的CAP-GA和CAP-SS，究其原因，主要在于HSS中设置了在当前主循环nu下，若算法全局最优解xopt连续h1次未改进则跳出该次内循环的机制。故随着问题规模的增加，测试问题在算法终止时的总内循环迭代次数增幅不大，因而HSS的求解时间较CAP-GA和CAP-SS增长缓慢。

图8 三种算法的CPU运算时间比较

5 结束语

（1）针对过道布置问题的求解复杂性，提出了一种混合模拟退火及分散搜索算法进行求解。将模拟退火操作嵌入到分散搜索的解改进方法中，进一步优化参考集中的解，充分利用分散搜索算法的全局搜索能力和模拟退火操作的局部搜索能力，提高获得全局最优解的概率。

（2）结合问题特征，在基本分散搜索算法的基础上设计了双层参考集，增加解的多样性，扩大搜索范围，避免算法陷入局部最优；采用动态参考集更新方法，实时更新参考集，加快算法的收敛速度；改进子集产生方法，避免产生重复的设施序列，提高算法运行效率。

（3）应用所提算法对24个不同规模的过道布置问题进行验算与对比，结果表明所提改进分散搜索算法在求解质量和平稳性方面优于基本模拟退火算法和分散搜索算法，且较已有的4种方法更具求解优势。

[1]Drira A，Pierreval H，Hajri-Gabouj S.Facility layout problems：A survey[J].Annual Reviews in Control，2007，31（2）：255-267.

[2]Anjos M F，Hungerländer P.A semidefinite optimization approach to space-free multi-row facility layout[J].Zhurnal Mikrobiologii Epidemiologii I Immunobiologii，2012（5）：74-85.

[3]Nordin N N，Zainuddin Z M，Salim S，et al.Mathematical modeling and hybrid heuristic for unequal size facility layout problem[J].Journal of Fundamental Sciences，2009，5（1）：79-87.

[4]张则强，程文明.双行布局问题的分解策略及启发式求解方法[J].计算机集成制造系统，2014，20（3）：559-568.

[5]Izadinia N，Eshghi K.A robust mathematical model and ACO solution for multi-floor discrete layout problem with uncertain locations and demands[J].Computers&Industrial Engineering，2016，96：237-248.

[6]Lin Q，Liu H，Wang D，et al.Integrating systematic layout planning with fuzzy constraint theory to design and optimize the facility layout for operating theatre in hospitals[J].Journal of Intelligent Manufacturing，2015，26（1）：87-95.

[7]Amaral A R S.The corridor allocation problem[J].Computers&Operations Research，2012，39（12）：3325-3330.

[8]Ghosh D，Kothari R.Population heuristics for the corridor allocation problem[J].Tetrahedron Letters，2012，98（2）：33-40.

[9]Ahonen H，De Alvarenga A G，Amaral A R S.Simulated annealing and tabu search approaches for the corridor allocation problem[J].European Journal of Operational Research，2014，232（1）：221-233.

[10]白杰，杨根科，潘常春，等.基于改进分散搜索算法的无人机路径规划[J].上海交通大学学报，2011，45（2）：173-178.

[11]Guo X，Liu S，Zhou M，et al.Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and petri nets[J].IEEE Transactions on Cybernetics，2015.

[12]González M，Vela C，Varela R.Scatter search with path relinking for the flexible job shop scheduling problem[J].European Journal of Operational Research，2015，245（1）：35-45.

[13]Grazielle B D P S，Sanches Mantovani J R，Cossi A M.Planning medium-voltage electric power distribution systems through a scatter search algorithm[J].IEEE Latin America Transactions，2015，13（8）：2637-2645.

[14]范志强.供应链订单分配优化模型及其模拟退火算法[J].计算机工程与应用，2012，48（25）：28-33.

[15]Kothari R，Ghosh D.A scatter search algorithm for the single row facility layout problem[J].Journal of Heuristics，2014，20（2）：125-142.

[16]Martí R，Laguna M，Glover F.Principles of scatter search[J].European Journal of Operational Research，2006，169（2）：359-372.

[17]Simmons D M.One-dimensional space allocation：An ordering algorithm[J].Operations Research，1969，17（5）：812-826.

[18]Amaral A R S.An exact approach to the one-dimensional facility layout problem[J].Operations Research，2008，56（4）：1026-1033.

[19]Anjos M F，Vannelli A.Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes[J].Informs Journal on Computing，2008，20（4）：611-617.

[20]Anjos M F，Yen G.Provably near-optimal solutions for very large single-row facility layout problems[J].Optimization Methods&Software，2009，24（4/5）：805-817.