考虑出库不确定性的船舶舾装件立库入库优化

赵天毅, 李娜, 李明昊, 蒋祖华

(1.上海交通大学 机械与动力工程学院, 上海 200240; 2.招商局重工(江苏)有限公司, 江苏 南通 226113)

随着信息科技的迅猛发展和管理系统的高度信息化,自动化立体仓库逐渐成为制造型企业进行仓储管理的重要设施,其高度自动化的管理方式与管理能力影响着企业仓储管理系统的整体效率[1]。船舶行业近年来也逐步引入了自动化立体仓库,用于储存例如UPS和分电箱等部分尺寸合适的舾装件。

对舾装件立体仓库货位的货位分配进行优化可以提高仓库出入库与管理效率,实现对生产需求的快速响应,具有重要的现实意义。然而,由于船舶行业按订单生产,订单船型及数量随市场需求的波动而频繁变化,且船舶的生产周期较长[2],因此生产过程具有较高程度的不确定性,导致其舾装件出库计划往往有较多的不确定性。同时,生产所需的舾装件具有品种多,标准化程度低的特点,因此虽然出库总量大,但是单个种类的舾装件使用频率不高,其出库计划数据也相对较少,这种情况下,需求不仅不确定,而且难以通过历史数据进行准确预测。此外,舾装件出库的效率评估也与一般的库存问题不同,由于多种舾装件需要在同一时间点用托盘配齐,进而服务后续生产过程,齐配效率的考虑与提高成为了舾装件入库优化的独特特点。因此,本文希望构建模型和算法对舾装件立体仓库独特的入库货位分配优化问题进行深入的研究。

近年,针对立体仓库仓储货位分配策略优化问题的研究大部分假设立库出库计划需求为确定性计划,构建确定性优化模型,并根据问题的实际属性设计目标,探索相应的算法进行优化求解。杨玮等[3]以指令分组、货位分配及子行程作业模式与顺序3个角度进行优化,将优化方法与堆垛机运作规律相结合,构建了以提高多载具进出库作业效率为优化目标的集成优化模型。高楠等[4]考虑了存储安全性、存储效率以及仓库工人的有效工作时间,针对拣选型自动化立体仓库货位分配问题,设计了遗传算法进行优化。吴炳等[5]针对存储特殊材料(铝型材)的自动化立体仓库进行研究,结合铝型材尺寸与重量的特点,以货架稳定性、货架平衡性以及出入库效率为主要目标,通过模拟退火算法与遗传算法结合的方法对立体仓库进行货位优化。黄鹏等[6]建立了以出入库效率、货架稳定性和堆垛机负载均衡为优化目标的货位分配优化模型,并将遗传算法和延迟接受爬山算法相结合,提出了求解模型的两阶段混合算法。Yang等[7]根据仓储空间分配原则,以货架稳定性和存取效率为优化目标,设计了仓储位置分配优化函数,通过分析出库作业策略,建立了数学模型对货位分配进行优化。Yan等[8]运用动态的货位分配策略,构建了立体仓库多目标货位分配模型,对电子产品在立体仓库中的仓储优化和货位分配问题进行研究。Quintanilla等[9]以最大化仓库货位空间利用率为目标,通过基于邻域搜索的元启发式算法对货位分配问题进行优化。Li等[10]基于ABC分类法以及货物间的相关关系,针对动态货位分配问题,设计了基于数据挖掘的启发式算法(PABH)对问题进行求解。Zhang等[11]考虑了不同货物需求之间的相关性,以最小化堆垛机行驶距离为目标,设计了启发式算法和仿真优化的方法对立体仓库货位进行分配。

综上所述,本文不同于现有文献中对需求的确定性假设,而是假设各类舾装件出库频次的需求未知,仅可获得其均值和方差的模糊估计,在这个基础上,根据舾装件立库存储需求的独特性,提出以立体仓库货架安全性、舾装件齐配就近性以及舾装件出库高效性为优化目标的多目标立体仓库货位分配优化模型。本文首先将建立各个优化目标的确定性模型,然后结合出库计划的不确定性,构造了出库频率分布的模糊集,将出库高效性目标的模型转化为分布式鲁棒优化模型,进一步根据模型数学结构的特点,设计了利用遗传算法热启动的分支定价算法,该算法一方面克服了启发式算法无法获得精确解的缺点,另一方面克服了传统优化算法求解时间过长的问题,可以在有效的时间内求得模型的精确解。最后,通过数值算例证明了该算法对求解实际问题的有效性和高效性。

1 舾装件立体仓库入库规划模型

1.1 模型假设

假设舾装件立体仓库的货架共有a排,每排货架有b列c层,每次入库舾装件共有d种;每个货位坐标设为(l,m,n),其中l=1,2,…,a,m=1,2,…,b,n=1,2,…,c。假设每排货架分配专属堆垛机进行出入库操作,即在执行出入库操作时,各货架对应的堆垛机可同时进行动作,但对于同一排货架,堆垛机每次仅能进行一种动作(取或存一个货位存储的舾装件)。

假设每个货位高度为L0,长度为L1,宽度为L2,货位(l,m,n)对应的质量承载上限为Qlmn,该货位的可使用状态为Nlmn,若该货位可用,则Nlmn=1,若该货位不可用,则Nlmn=0。

1.2 货位分配规则建模

通过对舾装件立体仓库存储的实际场景进行研究和分析,发现船舶舾装件仓库货位分配主要需要考虑3个因素。首先需要保证仓库货架中货位的稳定性,若货架不稳定,在自动化管理的过程中极有可能会出现安全问题。其次,由于出库齐配率是舾装件库存评价的重要指标,该指标对于后续项目的继续进行有着重要影响,因此提高舾装件齐配率,对于存储舾装件的立体仓库货位规划具有十分重要的意义。此外,舾装件出库速度也是评价仓库货位规划效果的一个直接且重要的指标,舾装件的出库速度是影响船舶生产过程的关键因素之一。因此,本研究采用了货位稳定性原则、舾装件齐配就近原则和舾装件出库速度最快原则作为货位分配的优化目标。

1.2.1 货位稳定性原则

为了保证货架在仓储管理过程中的稳定性,货位分配应按照“质量较大的物品分配较低层的货位,质量较轻的物品分配较高层的货位”的规则,从而使货架整体更加稳定。尤其是舾装件类型较多,不同类型舾装件的质量差别较大。例如,分电箱的整托存储质量为100 kg,而UPS的整托存储质量为1 000 kg,因此为保证整个货架的稳定性,应按照“货架重心越低则货位越稳定”的原则,将UPS存储在低层货位,将分电箱存储在相对较高层的货位。立体仓库整体货架重心可以通过托盘上舾装件质量与所对应的货位层数的乘积来表示,该乘积的值越小则代表舾装件立体仓库中该货架的整体重心越低,该立体仓库货位更稳定。根据此规则,将货位稳定性原则建立数学模型为:

1.2.2 齐配就近性原则

船舶生产过程中,当且仅当同一托盘的舾装件配齐时,该托盘的舾装件才会出库。因此对于出库时常放于同一托盘的舾装件,要尽可能靠近存放,以便于进行同时的存取操作,进而提高出库时舾装件的齐配率。舾装件齐配就近性可以通过计算舾装件存储货位和与其常放于即同一托盘(即同托)的舾装件的距离进行衡量。本文结合船厂实际情况,最终通过计算舾装件距离该类同托舾装件中心货位坐标的距离对齐配就近性进行评估。根据此规则,将齐配就近性原则建立数学模型为:

(m-mk)(n-nk)

1.2.3 出库速度最快原则

出库速度是衡量货位分配的重要指标之一,立体仓库管理中,出库速度取决于堆垛机搬运过程的速度,而堆垛机搬运舾装件的速度与堆垛机移动距离以及货叉的操作距离有关,因此物品存放位置会直接影响堆垛机运行速度和效率。为了提高舾装件出库速度,应该将出库频率高的舾装件分配靠近巷道出入口的货位。根据此规则,将出库速度最快原则建立数学模型,其中出库频率为不确定参数:

由于在入库操作时往往无法获得未来出库计划的准确信息,仅能通过历史数据对未来出库计划进行估计,因此要使模型在实际应用中具有较好的效果,需要大量的舾装件历史出库计划数据对出库频率概率分布进行描述。然而在实际情况中,因为舾装件种类多且标准化程度不高,所以部分舾装件的使用频率不高,导致该类舾装件历史出库计划数据较少,难以通过历史数据对该类舾装件的出库频率进行准确预测,也无法通过历史数据对出库频率的概率分布进行较为准确的描述,所以如果直接使用历史数据的期望值作为出库频率进行货位分配有可能会使决策的实际效果较差。为了解决这一问题,本文利用分布式鲁棒优化的方法对该目标函数进行转换。分布式鲁棒优化首先基于可以观察到的数据建立不确定参数的模糊集,该模糊集包含了真实的不确定参数分布,然后通过考虑该模糊集中的最差情况得到稳健性较强且可靠性较高的决策,因此该方法可以通过有限的不确定参数概率分布信息实现统计与优化之间的平衡[12],可以应用于历史数据不足以刻画全部分布信息的情况。转换后的模型可以在计算中减少历史数据数量的影响,并在没有具体概率分布假设的情况下对决策进行优化。

在本文所考虑的问题中,由于单个种类的舾装件出库数据有限,很难进行分布的拟合;而矩信息则可以由数据中直接进行无偏估计,故考虑基于矩信息的模糊集构建方法。

该模糊集包含了期望和方差符合历史数据情况的所有分布函数,因此也包含了出库频率的真实分布。通过分布式鲁棒优化,目标函数f3可以转化为:

命题1f3可以转化为a个独立的目标函数之和,即:

证明：设l为被分配到货架l上的所有舾装件的出库频率的联合分布,集合Kl为该货架上的舾装件因此模糊集Zl为模糊集Z在l上的投影:

证毕。

根据文献[13]中的引理1,可以得到命题2。

1.3 多目标舾装件立体仓库货位分配模型

在对舾装件立体仓库货位分配进行优化时,需要同时考虑货位稳定性原则、舾装件齐配就近原则和舾装件出库速度最快原则,因此货位分配模型中需要同时优化f1、f2、f33个目标函数,即:

约束条件为:

(1)

(2)

(3)

(4)

(5)

式中:约束(2)要求每个货位仅能存储一类舾装件,约束(3)要求每个舾装件只能分配到一个货位,约束(4)要求舾装件不能分配到无法放置货物的货位且存储的总质量不能超过所分配的货位的质量上限,约束(5)定义了决策变量的定义域。

为3个目标函数分配3个不同的权重系数ω1、ω2、ω3作为影响因子,采用权值分配的方法将多目标优化问题转换成单目标函数求极值的问题。由于3个目标函数的量纲不同,为了使目标函数值具有可比性和物理意义,对f1、f2、f3进行归一化处理,消除量纲的影响,转化为:

最终,多目标优化模型形式为:

2 基于遗传算法热启动的分支定价算法

舾装件立体仓库入库规划模型可以通过商业求解器直接进行求解,但若货架数量过多,模型的求解难度会大大增加。而本文模型的数学结构具有可分解性,因此可将问题基于不同货架分解为相互关联的单货架入库货位分配优化问题。基于这一特点,设计了分支定价算法对问题进行求解,以加快模型的求解速度。而分支定价算法的收敛速度与初始解的质量有关,因此本文设计了遗传算法对分支定价算法进行热启动,即通过遗传算法得到一个次优解并将这个解作为分支定价算法的初始解,以实现在实际应用中大规模问题的实时优化。

2.1 Set Partitioning主问题模型

设所有满足货位分配模型约束条件的可行货位分配方案集合为Ψ,其中φ∈Ψ表示可行的单货架货位分配方案。本文所求解的问题可以转化为从可行货位分配方案集合Ψ中选择若干个单货架货位分配方案φ组合组成一个可行解并且使得货位分配模型中的目标函数值最小。

为了便于描述Set Partitioning主问题的形式,定义当第k类舾装件被分配到货架时δkl=1,否则δkl=0,cl为可行货架货位分配方案φl对应的目标函数值。通过上述定义,可以将舾装件立体仓库入库规划模型转化为下面的Set Partitioning模型,并将其定义为分支定价算法的主问题 (master problem,MP):

(6)

(7)

(8)

φl={0,1},∀l∈{1,2,…,a}

(9)

约束(7)表示每类待入库舾装件只能分配到一个货架,约束(8)规定了立体仓库中年货架总数量的上限,约束(9)定义了决策变量的定义域。

2.2 子问题模型

令ε0、εk分别是约束(7)和约束(8)对应的对偶变量,那么主问题MP的检验数(reduced cost)为:

(10)

(11)

(12)

(13)

(14)

(15)

式(10)表示在可行货架货位分配集合Ψ中找到使得检验数最小的可行单货架货位分配方案。在求解子问题时,若目标函数值小于零,则将对应的最优解作为新的列加入到主问题中进行迭代求解,以使LMP 问题的目标函数值达到更优。若在求解子问题时不能找到使得目标函数值小于零的解,说明当前的结果已是LMP 问题的最优解。

2.3 分支策略

为了快速得到混合整数规划问题的整数解,本文在分支定界算法框架中使用了局部深度优先搜索策略[14]。该策略使用最佳优先准则选择分支定界树中的一个子节点,并使用深度优先策略探索该节点上的子树。如果其父节点的下界和未探测节点的最佳下界在给定的容差范围内,则对该节点所对应的子树进行搜索。当子树的局部搜索完成后,使用最佳优先准则选择下一个节点进行搜索。重复此过程,直到完成搜索。这种混合搜索策略可以通过使用最佳优先准则控制搜索节点的总数量,从而加快算法的收敛速度。

2.4 热启动遗传算法设计

本文设计了遗传算法对货位分配模型进行求解,以获得较优的货位分配方案作为分支定价算法的初始解,对分支定价算法进行热启动,从而进一步加快分支定价算法的求解速度。遗传算法的设计如下。

编码方案:采用整数编码的方式,每一条染色体都代表立体仓库中舾装件的货位分配方案。基因值为包含排数、列数、层数等信息的货位存储坐标。例如,1号基因值为(1,1,1)表示1号舾装件的分配货位为1排1列1层。

选择操作:采用轮盘选择法对染色体进行选择,选择适应度函数较大的一组(2个)个体,分别作为父染色体和母染色体。

交叉操作:根据交叉概率(本文设置交叉概率为0.5)将选择操作得到的2个染色体的某一基因进行互换,从而产生2个新的舾装件分配方案。例如,将父染色体的3号基因值与母染色体的4号基因值进行互换。

变异操作:根据变异概率(本文设置变异概率为0.3)选择染色体上2个不同位置的基因进行互换,即相当于互换一个舾装件分配方案中的2个舾装件对应的货位。例如,将染色体的1号基因值与4号基因值进行互换。

终止条件:迭代总数达到300,或者在5次迭代中最优适应度函数值没有得到提升。

3 数值实验

3.1 算法能力分析

本文使用Python语言对基于遗传算法热启动的分支定价算法进行编写。运行环境采用i7-8750 @2.20 GHz的CPU 8.00 GB 内存。本文分别使用基于随机初始解的分支定价算法(B&P)、基于遗传算法热启动的分支定价算法(B&PGA)和Gurobi对货架数量不同的随机算例进行求解。其中,每种货架数量进行3次不同随机算例的运算,并取3次求解时间的平均值作为最终的求解时间,比较3种方法的求解时间,对算法能力进行分析。实验结果如表1所示,实验中的求解时间以秒为单位进行统计,设置求解时间上限为2 000 s,即超过2 000 s则算法停止运行,并将结果计为>2 000。

表1 不同货架数量下算法求解时间比较Table 1 Comparison of algorithm solution time under different shelf numbers

结果表明,当货架数量较小时,Gurobi算法的平均求解时间略短于2种分支定价算法的平均求解时间。然而,当货架数量大于6时(符合船厂仓库一般规模),2种分支定价算法求解速度更快,且求解时间随货架数量增加的增长率低于Gurobi算法。同时,表中数据表明B&PGA算法的求解速度总是比B&P算法的速度快,在实验中有17%～50%的速度提升,效率提升效果明显。因此,可以得出结论通过遗传算法对分支定价算法进行热启动可以进一步加快算法的求解速度。综上所述,本文设计的基于遗传算法热启动的分支定价算法能够有效解决船厂的实际问题。

3.2 货位优化效果分析

本节基于某船厂真实数据对模型和算法的有效性进行验证,根据船厂专家的建议,选择VDR系统、气象传真系统、MCT以及雷达系统等舾装件作为研究对象。通过其立体仓库设计规划获得包括立体仓库货位数量以及尺寸等货位信息,通过计划存入立体仓库的舾装件规划获得舾装件尺寸和质量等数据,通过相关舾装件的历史出入库信息获得不同舾装件出库频率的期望和方差等分布信息的估计值。部分舾装件优化前的货位信息如表2所示。

表2 优化前部分舾装件货位信息Table 2 Outfitting information examples before optimization

通过调整不同货位分配原则在目标函数中的影响因子大小,分别对货位分配进行优化,并对优化结果进行分析。本文共考虑了3种不同的权重分配情景,其中,情景Ⅰ(以货位稳定性原则为主)中的ω1、ω2和ω3分别为0.8、0.1和0.1,情景Ⅱ(以齐配就近性原则为主)中的ω1、ω2和ω3别为0.1、0.8和0.1,情景Ⅲ(以出库速度最快原则为主)中的ω1、ω2和ω3别为0.1、0.1和0.8。算例的优化结果如表3、4所示。从表中可以看出,优化后的目标函数值与优化前相比,都得到了明显的提升,表明货位分配结果在优化后得到了明显的改进。其中,在不同的权重分配下,货位稳定性原则的优化效果最好,即仓储安全性的提升效果最明显。

表3 优化前后货位分配总评价指标比较Table 3 Comparison of total evaluation indexes of cargo space allocation

表4 优化前后子目标函数差值Table 4 Differences of sub-objective functions before and after optimization

3.3 出库不确定性影响分析

本文考虑到出库频率分布信息难以通过历史数据进行准确刻画的情况,构造了出库频率分布的均值-方差模糊集,并通过分布式鲁棒优化的方法对模型进行了转化,以使货位分配决策表现更好。为了验证该方法的有效性,对使用分布式鲁棒优化方法的模型(distributionally robust model, DRM)以及使用历史数据期望进行决策的模型(expectation model, EM)的解进行了比较和分析。本实验首先使用DRM和EM 2种模型对现有货位进行了优化,其3个优化原则的权重均设为0.33。然后根据历史出库数据的期望值,改变出库数据的方差,模拟200次出库操作,基于模拟的出库数据计算目标函数值的期望,并将其中出库速度最快原则对应指标作为评价指标,对2种模型进行了比较。本实验分别比较了出库数量服从正态分布、指数分布和韦布尔分布3种不同分布的情况下,随着变异系数(Coefficient of Variation)的增加,DRM与EM 2种模型评价指标的差值,其中,变异系数相当于出库频率的不确定性越高。实验结果如表5～7所示。

表5 出库数量服从正态分布的评价指标比较Table 5 Comparison of evaluation indicators when outgoing quantity obeying normal distribution

表7 出库数量服从韦布尔分布的评价指标比较Table 7 Comparison of evaluation indicators when outgoing quantity obeying Weibull distribution

由此可知,出库数据服从正态分布、指数分布和韦布尔分布时,不同变异系数下DRM的评价指标(出库速度原则对应的目标函数值)都要低于EM的评价指标,且差值随着变异系数的增加而增加。因此,本文提出的模型的表现要优于使用期望值进行货位优化的方法,且出库数据的离散程度越高,使用分布式鲁棒优化的模型优化效果越好。

4 结论

1) 针对船舶舾装件立体仓库的入库货位分配优化问题,对舾装件齐配率这一舾装件仓储管理的关键评价指标进行了优化。

2) 考虑了由于舾装件种类多、标准化程度低导致的舾装件出库频率的分布信息难以通过历史出库计划数据进行准确预测的问题,根据历史数据的期望和方差构建了出库频率分布的模糊集,并通过分布式鲁棒优化的方法对出库速度评价指标进行了转化,最终建立了以货位稳定性原则、舾装件齐配就近原则和舾装件出库速度最快原则为优化目标的多目标优化模型。

3) 设计了通过遗传算法进行热启动的分支定价算法对模型进行求解,实现了对大规模问题的高效求解。

4) 通过数值实验证明了方法的有效性,该方法对真实案例中的舾装件立体仓库货位分配问题具有明显的优化效果。