双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法

管 超 张则强 朱立夏 毛丽丽

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

0 引言

设 施 布 局 问 题 （facility layout problem，FLP）通常以最小化总物流成本为目标，对空间中的设施或设备进行组合优化。据估计，合理的布局优化可以降低生产过程中10%～30%的物料搬运成本［1］，正因为该问题所具有的重要研究意义和实际应用价值，近几十年来一直受工业界和学术界的关注。

过道布置问题（corridor allocation problem，CAP）作为一种特殊的布局问题，由AMARAL［2］提出。该问题将一定数目的设施布置在过道两边，以最小化总物流成本为目标，寻求设施序列的最优布置。CAP问题与双行布局问题［3］相似，但两者区别主要在于CAP中相邻设施之间没有间隙，且上下两行设施序列均从过道的最左边同一点开始布局。在工业制造领域，CAP应用于微芯片在集成电路板中的布局设计、半导体生产线的布局设计［4］等，具有重要的潜在应用价值，因此，该问题自提出以来便快速成为设施布局领域一个新的研究热点。

AMARAL［2］建立了CAP的混合整数规划（mixed－integer programming，MIP）数学模型，提出3种启发式算法，通过大量算例运算验证了所提算法的有效性。GHOSH等［5］应用混合遗传算法和结合路径再连接的分散搜索算法，对过道布置问题进行了求解，进一步提高了求解效率。ANJOS等［6］提出了一种针对无间隙多行布局问题的半正定规划方法，该方法对小规模测试问题具有良好的求解效果，针对难度更大的问题也可求得高质量的函数值下限。KALITA等［7］以最小化总物流成本和过道长度为目标，通过大量运算验证了遗传算法求解双目标过道布置问题的有效性。

上述文献均是对单层过道布置问题的研究，然而在实际生产或服务部门中，设施在多层空间中的布局设计越来越多地被采用。当布局场地面积受限时，无法对数量庞大的设施进行单层过道布置，设施被迫布局到多层空间；另一方面，设施的多层布置也可以实现土地的集约利用并减少占地成本。由此可知，设施在多层空间中的布局研究越来越有必要。

模拟退火 （simulated annealing，SA）算法在求解组合优化问题中表现出良好的求解性能。AHONEN等［8］采用禁忌搜索算法和模拟退火算法分别对不同规模测试算例进行了验算和对比，在求解质量和求解效率方面，模拟退火算法性能更加优异。韩伟等［9］将模拟退火思想引入温度参数以控制权重的变化率，通过对ESICUP标准运算数据测试，证明了所提温控散列函数能有效提高排样效率与排样产出率。祝恒云等［10］将粒子群算法和模拟退火算法有机结合，通过实例仿真验证了所提算法的有效性和实用性。

本文考虑生产实际中布局用地成本以及布置场地受限等情况对过道布置的影响，提出了双层过道布置问题，建立了该问题的混合整数非线性规 划 （mixed-integer nonlinear programming，MINLP）模型。应用GUROBI软件首先对所选24个测试问题进行精确求解，验证了模型的正确性；随后提出一种改进的模拟退火 （improved simulated annealing，ISA）算法求解该问题；最后，通过与精确算法和基本模拟退火算法运算结果作对比，验证了所提算法的求解有效性。

1 双层过道布置问题

1.1 问题描述

单层过道布置问题以最小化物流成本为目标，将n个不同形状的矩形设施布置到通道两侧，并确定分配到每一行的设施数目、设施序列以及每个设施的精确位置。在此基础上，本文考虑用地成本等因素、布置场地受限等情况对设施布局的影响，提出了双层过道布置问题。图1为该问题示意图。

图1 双层过道布置问题示意图Fig.1 Schematic diagram of a double layer corridor allocation problem

与传统过道布置问题相比，双层过道布置问题考虑设施在两层空间中的布置，分配到各层中的设施沿过道两边线进行布局。双层过道布置问题不是单层过道布置问题的简单叠加，不同层各设施之间也存在物流交互，且交互通道为放置在过道最左边的货梯。结合该问题特点，需要对各层空间中的设施进行组合排序，期望找到最优布置序列，并确定此时各层设施布置排列顺序，从而最小化总物流成本。

1.2 基本假设条件

为简化问题作如下假设：①设施间物流量和每个矩形设施靠近过道边线的宽度为已知量；②各设施的流量交互中心位于设施靠近过道边线的中点；③相邻两设施之间没有间隙；④上下两层设施均从最左边同一点开始并沿过道两边布置，即不同层起始点的横坐标均为0；⑤假设上下两层过道的宽度为0；⑥不同层设施之间通过货梯进行物流交互，且搬运距离为货梯的运输路程；⑦货梯布置在过道最左边，即货梯口与每层过道0横坐标零点重合。

1.3 数学模型

为方便描述，模型中出现的数学符号的意义如下：n为问题规模，即需要布置的设施数目；设施编号集合N＝｛1，2，…，n｝；L 为所有设施长度之和；h为货梯运输路程；i、j为设施标号，i，j∈N；xi为设施i在布置中的位置；k为行标号，k∈K ＝｛U1，D1，U2，D2｝，其中，U1、D1分别表示第一层中布置设施的上行和下行标号，U2、D2分别表示第二层中布置设施的上行和下行标号；cij为设施i、j之间的流量成本，i∈I1，j∈I2，I1＝｛1，2，…，n－1｝，I2＝｛i＋1，i＋2，…，n｝；li为设施i的长度；dij为设施i和设施j中心点间的横坐标距离；Lk为布置在k行的设施总长度。

其中，3种决策变量描述如下：

所建MINLP数学模型为

引入三个决策变量：yik表示设施i是否布置在第k行，若在第k行，则yik＝1，否则yik＝0；zkij表示设施i、j是否均布置在第k行且设施i布置在设施j的左边，若成立则zkij＝1，否则zkij＝0；Fij表示设施i、j是否在同一层，若成立则Fij＝1，否则Fij＝0，该变量由yik确定。已知设施总数目N、设施靠过道边线长度li、设施间物流成本cij，以最小化总流量成本为目标，如式（1）所示。

约束条件说明：式（2）～式（4）为设施距离约束，其中，式（2）、式（3）用于确定布置在相同层各设施之间的距离，式（4）确定不同层各设施之间的距离；式（5）确保每个设施仅分配至一行；式（6）保证各行均有设施布置；式（7）防止各层中同行设施位置发生重叠放置；式（8）用于计算每行设施布置的总长度；式（9）、式（10）用于确定xi的取值范围，其中，式（9）保证第i个设施绝对位置坐标值不小于li／2，式（10）则确定xi的上界为li／2，即设施i所在行的设施总长度减去设施i长度的一半，以此保证不同行设施布置始点为绝对位置0点；式（11）用于确定决策变量Fij；式（12）与式（13）保证设施i和j同时位于k行，此时，二进制变量zkij或zkji为1。此外，该约束限制zkij和zkji同时为1的情况。如果设施i和j同时位于k行，则zkij或zkji为1；式（14）～式（16）限定变量取值。

本文将传统CAP问题扩展到双层过道布置问题，使之更加满足设施多层布局的实际要求。针对双层过道布置问题的特点，本文考虑了设施在两条过道上的布置，并构建了相应约束以表达所提问题。双层过道布置问题是多层布局中的一个特例，其问题复杂度较单层过道布置问题更大，从模型中可以看出，双层过道布置问题模型较单层过道布置问题模型约束更多，组合情况由原来的（n－1）n！／2增加为（n－1）（n－2）n！／4，求解难度更大。

2 求解双层CAP的ISA算法

2.1 解序列的编码和解码

根据所提问题特点，本文采用一种基于设施序列的表达方式。双层过道布置问题作为典型的组合优化问题，其可行解序列可由一个有序排列的设施集合来表达。以设施数目n＝9的问题为例，一个可行解s＝［5 3 1 7 9 6 2 8 4］，其中，u＝5，nu1＝2，nu2＝3，即布置在第一层、第一行的设施序列为［5 3］，第一层、第二行的设施序列为［1 7 9］；布置在第二层、第一行的设施序列为［6 2 8］，第二层、第二行设施序列为［4］。上述可行解的编码和解码如图2所示。

图2 解的编码与编码Fig.2 Encoding and decoding of solutions

2.2 改进模拟退火算法

2.2.1 记忆功能

为避免搜索过程中因执行Metropolis接受准则而遗失当前最优解，在模拟退火过程中内嵌记忆解sbest用于保存搜索过程中所得最优解。算法开始时，以初始解s0初始化sbest，即sbest＝s0。算法随机搜索过程中，当产生新解s1时，则比较f（sbest）与f（s1），其中，f（s）为解序列的图标函数值。若f（sbest）＞f（s1），则令sbest＝s1，f（sbest）＝f（s1）；否则sbest、f（sbest）不变。通过对f（sbest）和f（s1）的比较，不断更新sbest，算法终止时输出的解sbest即为整个搜索过程中的最优解。

2.2.2 改进抽样过程

为提高算法求解质量，对局部搜索过程进行改进。本文采用一种自适应搜索策略代替原模拟退火算法中固定的马氏链长度，将问题规模作为算法的抽样次数。改进的抽样过程如下：

（1）确定最小抽样次数Mstep，初始化累记抽样次数q＝0，初始解s0，并将该初始解作为当前最优解s′best，即s′best＝s0；

（2）状态产生函数产生新解s1，计算目标增量 ΔC＝f（s1）－f（s0）；

（3）若ΔC＜0，则s1＝s0，f（s0）＝f（s1），q＝0；否则以概率exp（－ΔC／Tc）接受新解，若s1被接受，则s0＝s1，f（s0）＝f（s1），q＝0，否则保持s0、f（s0）不变，q←q＋1；

（4）比较f（s1）与f（s′best）的大小，若f（s′best）＞f（s1），则令s′best＝s1，f（s′best）＝f（s1）；否则保持s′best与f（s′best）不变；

（5）若q≥Mstep，则执行步骤（6）；否则执行步骤（2）；

（6）输出当前最优解s′best与f（s′best）。

2.2.3 回火操作

由式（17）可知，随着温度的降低，算法接受劣解的概率逐渐减小，此时容易陷入局部最优。为对解空间进行充分搜索，本文加入回火操作，在迭代过程中，若当前最优解sbest连续若干次没有进行更新时增大温度值，并以当前最优解sbest作为初始解s0重新进行搜索，提高获得全局最优解的概率。

2.2.4 设置双阀值的改进退火过程

为提高算法求解效率，在保证求解质量前提下，设置双阈值，消除多余迭代次数。在抽样过程中，以Metropolis抽样稳定为终止准则，即在各温度下当前最优解s′best连续Rin（抽样阈值）次保持不变，则结束此次抽样过程；若连续Rout（退火阈值）次降温过程中所得的最优解sbest保持不变，则认为退火过程收敛，继而进行回火操作或跳出降温过程。改进退火过程如图3所示。

图3 改进退火流程图Fig.3 Flow chart of improved annealing process

图3中，参数cin、cout分别表示抽样过程中s′best与降温过程中sbest连续保持不变的次数；参数switch为布尔变量，当退火过程收敛，即满足阈值条件时，若switch＝false，则令当前温度Tc为初始温度（即Tc＝T），Rout←2Rout／3，升高温度并降低阈值条件，进行下一次的退火操作，否则终止此次退火操作，返回sbest。

2.3 算法步骤

本文所提改进模拟退火算法主要对退火过程及抽样过程进行改进，具体步骤如图4所示。图4中，nu1、nu2分别为布置在第一层第一行和第二层第一行的设施数目，Tend为模拟退火算法的终止温度。

3 实验结果与分析

为验证双层过道布置问题模型的正确性，针对设施数目从9～49不同规模的24个基准算例，首先应用数学规划软件进行精确求解，测试数据来源于文献［2，11-15］。计算试验采用的计算机硬件配置：CPU 为 E6700＠3.2GHz，内存为4GB，在 Windows 7 操作系统下运行GUROBI 7.0.1优化器求出精确解。

图4 改进模拟退火算法流程图Fig.4 The flow chart of improved simulated annealing algorithm

对于所选24个基准算例，假设货梯运输路程h＝10，运用GUROBI软件，依据2.4节给出的MINLP模型，采用数学规划法进行求解。经测试，对于设施数目小于13的6个小规模测试问题，GUROBI优化器可在合理时间内找到问题最优解，验证了所提数学模型的正确性。测试问题S9、S9H、S10、S11、Am12a、Am12b的求解时间分别为191.10s、2 263.97s、600.32s、4 749.20s、21 876.65s、26 032.73s，对于测试问题 Am13a，GUROBI软件求解了48 726.00s之后仍未找到全局最优解，程序终止时所得局部最优解为3 032.5。由此可知，随着问题规模的增大，数学规划方法的计算时间大幅度增加，且难以在合理时间内求解大规模问题。为给所提智能算法求解结果提供参考依据，兼顾求解效率，针对设施数目大于13的测试问题，GUROBI软件中设置的运行时间为1 200s。将所得结果列于表1，其中，第2列为测试问题名称，第3、4列表示精确方法求得的目标函数值f0及其CPU运算时间。

为验证所提算法求解双层过道布置问题的有效性，在同一运行环境下使用 MATLAB R2012a软件开发了ISA算法和SA算法的试验程序，并应用两算法分别求解24个基准算例，通过对比运算结果，证明了ISA算法的求解优势。算法参数设置方面，为兼顾求解质量和求解效率，经大量试验测试得相关参数，如表2和表3所示，表中“—”表示相关参数在算法中没有设置。其中，参数即布置在第一层的设施数目u的上限U2＝5、下限U1＝2。通过对传统过道布置问题的研究可知，当过道两边设施数目相差不大时，总物流成本最小，由此确定nu1与nu2的相关参数：T1＝max（1， u／2 －3），T2＝u／2；T1＊＝max（1， （n－u）／2－3），T2＊＝ （n－u）／2，其中， · 表示向下取整。

为准确对比ISA算法与SA算法的求解性能，针对每个测试问题，两种算法均运行10次，共获得48 0个计算结果。为更加简洁、直观地表示两种算法的运算特点，对所得数据进行整理、归纳，并列于表1的第5～16列，各基准算例的最优解及最优解序列见表4。其中包含了目标函数f的最小值、最大值、平均值、标准差、解偏差以及平均CPU运算时间。平均目标函数值f与f0的偏差定义为（fi－f0）／f0，i＝1，2。

表1 SA算法和ISA算法的计算结果Tab.1 The calculation results of SA algorithm and ISA algorithm

表2 算法参数设置1Tab.2 The parameter setting1of algorithms

表3 算法参数设置2Tab.3 The parameter setting2of algorithms

对表1所得结果分析可知，对于GUROBI所能求得的6个小规模测试问题，ISA算法均可求得，且求解时间远短于GUROBI软件的求解时间；对于其他规模的测试问题，ISA算法也可在短于GUROBI的求解时间内求得更优解，表明了所提算法求解双层过道布置问题的有效性；针对所选24个测试问题，ISA算法所得目标函数值的最小值、最大值、平均值均不大于SA算法所得结果，表明ISA算法较SA算法具有更优的求解质量；ISA算法所得目标函数值f的标准差均小于SA算法所得标准差，且对于测试问题S9、S9H、S10、S11、Am12a、Am12b、Am13a、Am15、Am17，ISA计算结果的标准差均为0，表明该算法具有更好的求解稳定性。

由于本文设置了回火操作，ISA算法在退火过程收敛时需从初温开始重启一次退火操作，因此，所提算法的CPU运算时间长于SA算法的求解时间。另一方面，为提高运算效率，在ISA算法中设置了双阈值，从而减少不必要的迭代运算，故对于测试问题S11、Am18、H20、N25＿02、N25＿03、N25＿04、N25＿05，ISA 算法的 CPU 运算时间短于SA算法的求解时间。

为更直观地说明所提ISA算法的求解性能，针对GUROBI软件所能求得的6个不同规模测试算例，应用本文所提两种算法重新运算60次，并计算两种算法与精确求解结果的偏差，绘制偏差箱形图（图5），其中，箱线图的上下框线、中间线，点画线分别表示该组计算结果的上下四分位数、中位值、平均偏差，上下框线之外的延伸线表示最大值（最小值）到上（下）四分位数的取值区间，符号“＋”表示不在正常值分布区间的异常值。由图5可以看出，ISA算法的平均偏差为0，远小于SA算法的平均偏差，说明ISA算法具有良好的求解性能；ISA算法方盒长度为0，而SA算法方盒长度较大，尤其是测试问题Am12b，其偏差取值范围为0～1.65%，且对于测试问题S9、S10、S11、Am12a，SA算法所得异常值较多，表明ISA算法较SA算法具有更好地求解稳定性。

表4 改进模拟退火算法求得的最优设施序列Tab.4 Optimal facility sequence of ISA

随后，为更加详细地说明ISA算法的求解特点，选取H20规模问题，对比ISA算法和SA算法求解该基准算例的运算过程，并绘制了相应的算法收敛图见图6。此时，部分参数设置为u＝2，nu1＝1，nu2＝8，其他参数如表2、表3设置。

图5 ISA算法和SA算法的求解质量Fig.5 Quality of solution between ISA algorithm and SA algorithm

图6 ISA算法与SA算法收敛曲线Fig.6 The convergence curve for ISA algorithm and SA algorithm

从图6中可以看出，与SA算法相比，ISA算法具有更高的收敛速度和收敛精度。SA算法在执行176次退火操作后陷入局部最优，此时局部最优值为8 591.0。ISA算法降温130次之后，求得局部最优解为8 567.0，随后算法重启退火过程，进行回火操作，在降温262次时求得最优解8 505.0。由此可知，ISA算法具有跳出局部最优进行全局搜索的能力。本文在ISA算法中设置了双阈值，提前结束不必要的局部搜索，因此，ISA算法只需迭代51 506次，少于SA算法的55 080次，且取得了更高质量的解。

为更加直观地表现回火操作在ISA算法中的作用，图7绘制了该算法的迭代过程曲线。算法迭代到26 686次时进行回火操作，并将此时搜索到的局部最优解作为下一次退火过程的初始解，最终求得全局最优解8 505.0，且优于回火之前的8 567.0。

图7 ISA算法迭代曲线Fig.7 The iterative curve of ISA algorithm

4 结论

（1）针对实际布局活动中对多层过道布置的需求，本文提出了考虑设施空间布局的双层过道布置问题，并建立了该问题的混合整数非线性规划模型。应用GUROBI优化器对所选24个测试问题进行精确求解，验证了所提模型的正确性。

（2）结合问题特征，提出一种改进模拟退火算法，该算法由改进退火过程与改进抽样过程构成。通过引入记忆功能以避免遗失搜索过程中遇到的最优设施序列；为进一步提高算法全局搜索能力，在退火过程收敛稳定时引入回火操作，并以此时搜索到的最优解作为初始解进行下一次的降温过程，试验证明，该操作增强了算法跳出局部最优的能力；在保证求解质量的前提下，通过设置双阈值，进一步提高算法求解效率。应用该算法对所选24个不同规模基准算例进行测试，将所得结果与基本模拟退火算法和GUROBI精确方法运算结果作对比，验证了所提算法在求解稳定性和求解质量方面具有明显优势。

在未来的研究中，将在目标函数中考虑占地成本因素或进行多个目标的优化，进一步完善双层过道布置问题；在求解方法层面，寻求更加优异的智能算法，进一步提高搜索效率与求解质量。