船舶生产过程为分批分段建造，物料需求具有严格的顺序性，船体不同段位需求的钢板规格、数量及期限也严格列出。分段，即钢板生产部门根据船厂生产计划将钢板依次运输至堆场存储，并为其中指定段位所用钢板设分段属性标识。由于生产顺序和周期与需求之间的差异性，存储垛位先入后出的规则，多批次不同类型钢板相互积压，形成倒垛操作。另一方面，船体不同段位所需钢板规格种类繁多，造船厂对船板供应商提出“分段集批，段齐交货”的原则。钢板堆场出入库作业成本是存储和操作成本中占比不可忽视的一部分。目前造船业相关研究主要集中于实现自动化和信息化管理，相近领域也有炼钢厂热轧板堆场作业优化的研究。造船领域中，施敏等提出了垛位自动预约技术以实现船板自动入库空间分配^[1]。徐萍等为应对管理现状与供货要求，提出了构建堆场管理信息系统的开发方案^[2]。刘建峰等为船板入库滚动作业建立了基于优化算法的仿真模型，研究钢板入库分配策略^[3]。在热轧炼钢行业，蒋如宏等针对板坯出库作业建立静态和动态数字化仿真模型，提高堆场管理信息化水平^[4]。唐立新等针对倒垛问题提出了整数规划模型，采用动态启发式算法优化解决方案^[5]，李耀华等为热轧板坯出库建立倒垛决策模型，运用粒子群算法以最小化倒垛量^[6]。以上研究从不同角度探讨了堆场管理改进方案。但无委托热轧板堆场相关研究主要对出入库或倒垛作业进行优化，不考虑指定分段的特殊属性。造船厂钢板堆场为带分段属性板单独分配存储区域，忽略了指定分段属性钢板独立存储方式的潜在问题。如因缺少部分段位延迟交货、占用堆场空间、堆积变形、垛位过高和存储周期过长等。

针对钢板堆场部分钢板带有指定分段的属性，存储限制条件苛刻，需求必须及时响应的问题特殊性。在上述研究的基础上，本文将研究指定分段和无指定分段两种钢板混合存储方式，由于混合存储方式可能带来分段属性不同的钢板相互积压增加倒垛量的问题，因此从出入库作业成本、时间和倒垛量三个维度，建立基于入库决策的出库整数规划分配决策模型。并提出了高度适应问题特殊性的基于模拟退火概率接受准则的双层遗传算法，通过实验分析对比验证算法的有效性。

1 问题描述 1.1 问题背景

船厂钢板堆场管理流程具体描述为：1)根据生产计划汇总订单合同，钢板到达堆场后进入缓冲区堆放，按分段、尺寸等属性分类，等待入库操作；2)确定入库序列，桥吊空闲时依次从缓冲堆取出钢板移入堆场指定垛位，存储在主堆场中；3)确定出库集合，按出库计划从指定的位置取出目标钢板，若目标板在顶层，则直接移至预处理临时垛位并转5)，否则转4)；4)目标板上积压有其他钢板，为倒垛集合中的钢板选择然后移至新的存储垛位，直到目标板暴露在顶层，取出钢板并移至预处理临时垛位；5)在截止时间前依次将经过预处理的钢板放置在出场传送带上，组合出库。

主堆场中的钢板堆放限制条件包括：规格较大钢板不能压在小钢板之上；属性(包括分段号、终端用户、交货地、厚度、材质强度等级)相同或接近的钢板放置在同垛；垛位累积不能超过最大高度；每个垛位只能放置同一天出库的钢板^[7]。基于本文研究的堆场布局，假设当前堆场以混合存储方式堆放大量钢板，以此为初始状态。如图 1所示，建立堆场坐标，X/Y分别代表垛位列/行编号顺序：

1) 主堆场垛位数量Y=RC，堆场以左上角为坐标原点，由一个桥吊承担出入库搬运作业；

2) 钢板从左端缓冲堆入库，进入堆场后由起始坐标搬运至预分配垛位；

3) 堆场每行(列)按照出库日期及尺寸划分，不考虑分段属性。从坐标原点开始，随着横(纵)坐标增大均匀分布；

4) 钢板可以在不同行(列)之间进行倒垛优先选择同列不同行，桥吊主体梁横向(或起重小车纵向)移动，且只考虑单张钢板搬运；

5) 假设堆场起始状态不为空，且以现有方式存储了一定量的钢板，并设垛位坐标P_i(C_i, R_i), (i=1, 2, …, Y)

混合存储情况下，堆场垛位分割只考虑尺寸和出库日期属性，针对分段的特殊属性再进行后续出入库方案优化。因此从预分配的角度，按照全部钢板的尺寸大小概率分布，以均衡各个垛位钢板数量为主要目的进行区域划分。如图 2，堆场按尺寸界限值：下限(L, W)_d=(L_d, W_d)，上限(L, W)_u=(L_u, W_u)划分为Ar块区域，每个区域按照出库日期D依次分配垛位。

假设造船厂全部入库钢板尺寸分布服从概率函数f (l, w):

$ {f_i} = \iint\limits_{\left( {l,w} \right)d < \left( {l,w} \right)i \leqslant \left( {l,w} \right)u} {f{{\left( {l,w} \right)}_i},i \in \left[ {0,Y} \right]} $

(1)

$ \Delta f = \sqrt {\sum\limits_{i = 1}^Y {{{\left( {{f_i} - \mu } \right)}^2}} } $

(2)

式中：l和w分别代表钢板属性长和宽，Y为堆场垛位总数，μ为概率均值。式(1)为任意垛位i尺寸范围概率，表示累计垛位i尺寸范围内出现的概率；堆场垛位布局预划分时计算式(2)^[8]，为保证堆场中各个垛位钢板数量分布均衡，以概率方差Δf值为控制变量，不超过指定最大值时可保证分布均衡。根据式(1)计算的频率，式(2)计算频率方差，方差越小，各个垛位钢板数量在概率上保证相近。从管理者角度来看式(1)、(2)，可以确定划分界限，防止堆场划分界限造成堆场运行管理过程中，部分区域钢板密集，垛位过高。同时按规则划分存储区域也便于出库时可按照尺寸和出库日期快速锁定所在垛位范围，能够加快查找速度，降低搜索算法的运行空间。

1.2 出入库作业流程

对于造船厂，入库作业即为到货钢板安排合理垛位，出入库日期确定的前提下，入库钢板应尽量避免将出库日期临近的带分段属性板积压在下层，引起大量不必要的倒垛。由于钢板的分段属性，无分段板只需满足订单数量规格要求，带分段板须按分段先集齐段位后组合出库。因出库方式不同，所以出库作业分两种：1)取出符合出库要求规格和数量的钢板；2)从指定位置取出入库前作特殊分段号标记的钢板集合。

根据在库板存储限制条件和本文研究问题的特殊性提出以下入库规则：钢板分段号、尺寸大小及材质＞出库日期＞垛位高度.按堆场放置原则逐个选择，放置在垛位最上层，不进行预倒垛。

出入库作业和堆场状态变化之间相互关系如图 3所示。

为解决本文混合存储出入库组合优化问题，合理安排钢板进入堆场的次序，为钢板预分配存储空间，优化出库分配计划，建立整数规划模型。

2 数学模型 2.1 堆垛及倒垛约束模型

设垛位t中钢板的最大尺寸为L_{max t}，最小尺寸为L_{min t}，根据现有的船厂钢板堆场管理信息系统，入库钢板在到达堆场前7、8 d就对堆场发出预约垛位信息，按分段号将订单汇总分类整理。为防止同一垛位钢板尺寸不同，会造成相互积压变形，增加矫正工序，必须降低同一垛位钢板尺寸差异，因此建立以下约束模型。全部钢板包括指定分段和不指定分段属性钢板入库选择垛位时都需要满足以下尺寸约束，降低同一垛位钢板尺寸偏差。同理，倒垛即为出库目标板以上的钢板集合重新选择垛位^[9]。z为初始设定值，同一个垛位钢板的长度宽度之差约束如下，j/k为垛位t中任意两块板。r_ij/c_ij为出库板i对应出库集合中板j所在行/列，X_ij=1表示钢板j选为出库P_ij对应板，X_ij=0时则反之，i=1, 2, …, M；X_ijr：代表出库板i对应板j所在垛位第r层钢板，存在时为1。限制垛位相邻两块板宽度(长度)差在一定范围内：

$ \left| {{W_j} - {W_k}} \right| \le {W_m} + \left( {2 - {X_{ijr}} - {X_{ikr}} - 1} \right)Z $

(3)

$ \left| {{W_j} - {W_k}} \right| \le {W_m} + \left( {2 - {X_{ijr}} - {X_{ikr + 1}}} \right)Z $

(4)

$ \left| {{L_j} - {L_k}} \right| \le {L_m} + \left( {2 - {X_{ijr}} - {X_{ikr - 1}}} \right)Z $

(5)

$ \left| {{L_j} - {L_k}} \right| \le {L_m} + \left( {2 - {X_{ijr}} - {X_{ikr + 1}}} \right)Z $

(6)

为保证垛位内任意两块板与垛位内最大板长度差在一定范围内, 则

$ {L_{\max t}} - {L_j} \le {\delta _{\max }} + \left( {1 - \sum\limits_{r - 1}^H {{X_{ijr}}} } \right)Z $

(7)

$ \begin{array}{*{20}{c}} {{L_j} - {L_{\min t}} \le {\delta _{\max }} + \left( {1 - \sum\limits_{r - 1}^H {{X_{ijr}}} } \right)Z}\\ {r = 1,2, \cdots ,{H_m}} \end{array} $

(8)

目前对于倒垛作业优化的研究已经较为成熟，倒垛模型假设选择的垛位大部分都是在原垛位附近，以加快算法运行速度降低问题复杂度，重新选择的垛位满足以上垛位尺寸约束同时还要满足：

$ \begin{array}{*{20}{c}} {\left| {{{r'}_{ij}} - {r_{ij}}} \right| + \left| {{{c'}_{ij}} - {c_{ij}}} \right| \le 2,\left| {{{r'}_{ij}} - {r_{ij}}} \right| \le 2}\\ {\left| {{{c'}_{ij}} - {c_{ij}}} \right| \le 2} \end{array} $

(9)

式(9)保证重新选择的垛位分布在原垛位周围，移动距离不超过限定值。根据堆场划分方式初步确定倒垛垛位号，根据式(9)可倒垛位分布如图 4所示：1)优先选择同列垛位即满足c′_ijk=c_ijk∧r′_ijk > r_ijk；2)同列垛位无可倒垛位，则选择相邻列倒垛c′_ijk=c_ijk±1∧r′_ijk=r_ijk；3)二次或以上倒垛往原列或行倒垛或往相邻列或行倒垛r″_ijk=r′_ijk∓1∧c′_ijk=c_ijk或c″_ijk=c′_ijk∓1∧r″_ijk=r′_ijk。

2.2 目标函数及约束

根据问题约束和优化目标建立数学模型，D_ij为出库板i对应钢板j翻板数量，优化目标为最小化桥吊翻板及运输所需钢板行驶的时间为

$ M\;{\inf _1}\left( x \right) = \sum\limits_{i = 1}^M {\sum\limits_{j \in {S_i}} {{W_{ij}}{X_{ij}}} } $

(10)

完成板i出库作业需要的操作时间为

$ {W_{ij}} = 2{t_c}\left( {{c_i} - {c_0}} \right) + {t_0} + \left( {{t_s} + {t_u}} \right){{D'}_{ij}} $

(11)

式中：t_c为桥吊横向移动单位距离时间，t₀代表桥吊取板上下移动时间，t_s桥吊倒垛平移时间；t_u桥吊倒垛上下移动时间。

取出(i-1)块板后，第i块板预计倒垛量：

$ \begin{array}{*{20}{c}} {{D_{ij}} = \max \left\{ {{D_j} - \max \left\{ {{X_{ij}},{D_{j + 1}}\left| {I'} \right. = } \right.} \right.}\\ {\left. {\left. {1,2, \cdots ,\left( {i - 1} \right) \wedge {{P'}_{ij}} = {P_{ij}}} \right\},0} \right\}} \end{array} $

(12)

在出入库作业全过程中，计算出桥吊行驶距离成本为

$ M\;{\inf _2}\left( {x,z} \right) = \sum\limits_{i = 1}^M {\sum\limits_{j \in Si} {{X_{ij}}\left\{ {{C_c}\left( {{c_{ij}} - {c_0}} \right) + {C_{{\rm{shuffle}}}}\left( {i,j} \right)} \right\}} } $

(13)

为取出出库板i对应符合条件的板j的付出的倒垛成本公式为

$ \begin{array}{*{20}{c}} {{C_{{\rm{shuffle}}}}\left( {i,j} \right) = \sum\limits_{k = {y_{ij}}}^{{K_m}} {\left\{ {\left( {{C_r}\left| {{{r'}_{ijk}} - {r_{ijk}}} \right| + } \right.} \right.} }\\ {\left. {\left. {2{C_c}\left| {{{c'}_{ijk}} - {c_{ijk}}} \right|} \right)} \right\}{Z_{ijk}}} \end{array} $

(14)

若钢板P_ij(R_ij, C_ij, Y_ij)所在垛位坐标(行、列、层)，则该垛共有k_m块板，(i-1)块板出库后，出库计划中钢板i对应出库板j的倒垛板集合AP_ij={AP_ij1, AP_ij2, …AP_ijk}，AP_ijk可倒垛位集合Q_ijk={Q_ijk1(r_ijk1, c_ijk1), Q_ijk2(r_ijk2, c_ijk2), …, Q_ijkn(r_ijkn, c_ijkn)}，Z_ijkq=1表示板j选作板i对应板上AP_ijk从P_ij(r_ij, c_ij)倒垛至Q_ij(r′_ij, c′_ij)，Z_ijkq=0反之，其中AP_ijk∈AP_ij。

每一个垛位中钢板堆放的总高度限制为

$ \sum\limits_{i = 1}^M {\sum\limits_{j \in Si} {\sum\limits_{k = {y_{ij}}}^{{k_m}} {{h_i}{X_{ij}}{Z_{ijk}}} } } \le H - h $

(15)

限制钢板出库时间在其上倒垛板完成倒垛之后作业时间为

$ \sum\limits_{I = 1,j \in Si}^M {\sum\limits_{{A_j} = {y_i}} {{W_{i'j}}{X_{ij}}} } \le {T_i} $

(16)

保证对应出库序列中无分段板有符合要求数量的板、带分段板有且只有一块板被选作目标板，则：

$ \sum\limits_{j \in Si} {{X_{ij}} = {N_i},i = 1,2, \cdots ,M} $

(17)

$ \sum\limits_{i = 1}^M {{X_{ij}} \le 1} ,i = 1,2, \cdots ,M,j \in {U_i} $

(18)

由以上描述及模型可知问题属于多目标组合优化问题^[10]。为求解该问题，本文将改进现有方法，针对可行解空间大而难以找到最优解的问题，提出基于模拟退火概率接受准则的两层嵌套遗传算法，通过出库作业内层解对外层入库作业计划的动态适应，求解研究周期内堆场物流周转方案。这种算法具有特殊问题适应性，从而更能找到本文提出的混合存储优化问题的较优解。

3 模拟退火双层遗传算法 3.1 编码方式

本文提出基于模拟退火概率接收准则的两层遗传算法来解决文中的问题，设E_i为入库清单整合规格序列E_i{e₁, e₂, …, e_i, …, e_M}，M为出库计划中钢板总数，钢板出库序列P=(P₁, P₂, …, P_M)，Ω_t堆场在研究周期T状态，出库计划中的第i个钢板P_i的规格参数为e_i=(L_i, W_i, H_i, G_i, Seg, N_i)，分别对应长、宽、厚、材质、分段号、需求数量，不指定分段板Seg值为空，编码方式如下所述：

1) 外层入库排序编码，设规格为e_i的板入库NN_i张，入库船板数共$NN=\sum\limits_{i=1}^{M}{N{{N}_{i}}}$。采用自然数编码方式，如图 5所示，按照编码对应自然数为入库集合包含的规格清单分配入库次序。

2) 堆场状态Ω编码以及内层选择匹配组合出库编码，若堆场内钢板以数组堆栈存储，E[i][k](i∈[1, Y], k∈[1, H_m])。将符合规格e_i的板设为i×10+1，十位以上为外层染色体出库次序编号。无板层设为0，有板层设为1，堆场可数字化为表 1所示。

3) 设符合规格e_i的钢板i对应的钢板集合U_i=(P_i1, P_i2, …P_ij, …, P_ini)，出库钢板候选板集合中元素个数$N=\sum\limits_{i=1}^{M}{{{n}_{i}}}$，n_i为钢板i可选集合U_i中元素个数，$U = \bigcup\limits_{i = 1}^M {{U_i}} $所有出库钢板的候选板集合；根据出库候选板集合U_i中元素个数n_i初始化内层出库组合染色体，如图 6所示，采用0-1编码，1代表被选作对应出库板P_ij，第i段为1的个数符合出库序列钢板P_i需求数量N_i。

4) 倒垛按步骤3染色体中为1的基因位确定目标板集合。倒垛集合也随之确定，为每块倒垛板建立可倒垛位集合。对于集合中每一个垛位，通过移动堆场状态编码中原位置和新位置的值反映钢板移动。每次移动令累积倒垛次数(shuffling number)S_N=S_N+1，最终在可倒垛集合中选择为完成该板出库作业预估倒垛量(S_N值)最小的垛位组合。

另一方面，本文采用的对比算法为一般遗传算法，编码方式采用以上两层染色体拼接为一条染色体的方式，如图 7所示。

3.2 算法流程

本文采用的基于模拟退火两层遗传算法进行优化求解，其中选择策略是基于模拟退火的概率接受准则，可降低内层算法对外层解的模糊化，采用概率接受准则增加种群原始解的保存率，防止内层算法对外层基因的破坏。具体算法流程如图 8所示。

4 实例验证与数值分析 4.1 参数设置

为证明上面提出的算法在该问题背景下的实用性和有效性，采用实例验证算法可行性并与一般遗传算法性能作对比。算法是在Windows7系统下基于Matlab2011b实现，选取某大型造船厂实际数据验证，当前研究的是在堆场状态不为空的情况下一个调度周期内出入库作业计划。表 2是实例数据以及参数基准单位设置。

遗传算法的参数设置在文献中有相关研究，根据文献[10-12]，为保证种群多样性增加变异概率，根据实验后的种群收敛性确定，基于模拟退火概率接受准则的双层遗传算法参数选择为：外层迭代次数NC₁=100，种群大小N₁=20，内层迭代次数NC₂=50次，种群大小N₂=30，内外层选择比例GAP=0.8，交叉概率为XOVER=0.7，变异概率MUTR=0.2。

为了验证并与本文算法进行对比，GA算法的参数选取为：迭代次数NC=100，种群大小N=50，选择比例GAP=0.8，交叉概率XOVER=0.7，变异概率MUTR=0.2。

4.2 实例验证与分析

已有研究中不考虑分段属性是将指定分段钢板单独分配垛位存储，主堆场中只存放无指定分段钢板。一般遗传算法实例验证采用与本文混合存储方式相同的堆场参数，表 3为将混合存储与不指定分段属性钢板存储方式的性能进行对比。其中Cost、t和S_N分别是式(15)完成出入库倒垛作业所需的人工设备总成本、式(12)作业时间和倒垛量:${S_N} = \sum\limits_{i = 1}^M {\sum\limits_{j \in {S_i}} {{D_{ij}}} } $。表中的数值代表分段的种类数量，Y指定分段种类数量为0时即表示堆场不考虑分段属性。

表 3显示混合存储在出入库规则约束下，对目标函数无明显影响。是由于堆场空间利用率的影响，因此表 4数据证明了混合存储方式在规则约束下的可行性。

表 4分析了随入库钢板数量，包括指定分段和不指定分段板同步增加时堆场运行代价的变化趋势。考虑到部分指定分段钢板混合存储在堆场中，出库时不仅有出入库钢板相互堆叠^[11]形成倒垛作业的增加，更有指定分段和不指定分段板之间相互堆叠，因此调度方案优化方向为避免取出指定分段板时对积压在其上的其他分段属性钢板大量移动。表 4中对比数据可以看到，对于算例1和2，在钢板数量较少时两个算法都能求得最优解。当钢板出入库的规格种类数较多，移动总数量超过200时，比如算例10，运输成本和时间急剧增加，GA不能完成作业优化，而SA-HGA算法则可以对两层操作进行动态协调，找到令出库组合最优的入库方式，同时得到与之相适应的倒垛和出库作业计划，使得出库作业高效且控制成本。本优化算法得到的作业方案，明显优于GA得到的作业方案。以算例8为例，应用本算法，倒板数量减少13.4%，桥吊作业成本减少14.1%，作业时间缩短10.1%。

为验证算法有效性，算法求解优化模型需要的时间随问题规模变化曲线如图 9所示。由于本文采用的双层嵌套遗传算法运行时间比一般遗传算法运行时间稍慢，但也在实际堆场作业管理可接受范围内，因此算法是可行且有效的。

以算例9为例，进一步将两种优化算法的收敛性^[12]作对比。SA-HGA内外层目标函数变化曲线如图 10所示，可以看到算法运行时表现出较好的收敛性。

由于遗传操作的局限性，一条同时携带出入库计划方案的染色体可能会同时在多个位置发生变化，容易破坏解的质量甚至陷入早熟收敛。而与传统的遗传算法相比，采用模拟退火概率接受准则的双层遗传算法对内外层染色体协调优化，出入库作业方案相互配合，保证了外层较优解的持久度，而遗传操作同时不断更新种群，防止早熟收敛。因此从表 4及图 10可知，传统遗传算法收敛性较好，能较快寻得较优解。

5 结论

1) 提出了基于堆场当前状态，带分段属性和无分段属性两类钢板混合存储的方法，针对本文提出的多目标组合优化问题，建立了整数规划模型，进一步优化出入库作业成本和时间；

2)为适应于该多约束组合优化问题，提出运用模拟退火双层遗传算法优化作业计划，通过算法实例演算结果表明，算法能在一定的迭代次数内寻得较优解；提供堆场管理作业方案，大幅度降低堆场作业成本和时间、减少倒垛量并且具有较高的规模适应性。并与GA相比较，证明本文提出SA-HGA的可行性和有效性。

本文尚需完善堆场空间利用率的计算，同时也为两类分段板的存储方式研究提供了新的方向。