假设越库系统仅有一个卸货平台和一个装货平台, 在装货平台前存在临时库存。当到达装货平台的货物与当前送货车辆的需求不匹配时, 物品可以存储在临时库存中, 等到合适的送货车辆进入卸货平台后再将货物进行装载。越库系统作业流程如图1所示。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 越库作业流程图Fig.1 Flow chart of cross docking

建立模型前需进行如下假设:

(1)所有的集、送货车辆都可以被使用, 且集、送货作业可以同时进行。

(2)禁止送货车辆同时从集货车辆和临时库存装货。

(3)临时库存大小没有限制, 但物品不允许长期存储于临时库存中。

(4)每种类型的集货物品总数等于每种类型的送货物品总数。

(5)集货车辆所装载的不同类型的物品卸货顺序可以随意确定。

(6)送货车辆物品装货顺序与集货车辆物品卸货顺序保持一致。

(7)所有集、送货车辆因交替装卸货所导致的延迟时间一致。

(8)所有物品从集货平台到装货平台的移动时间相等。

(9)集、送货车辆每次只能卸载或装载一个物品, 物品装卸货均耗1单位时间。

本文以越库作业完工时间T为目标函数建立数学模型, 首先对建模所需数学符号做如下定义:T为总运作时间; c_i为集货车辆i进入集货平台的时刻; F_i为集货车辆i离开集货平台的时刻; d_j为送货车辆j进入装货平台的时刻; L_j为送货车辆j离开装货平台的时刻。v_ij=1表示有物品从集货车辆i移动到送货车辆j, v_ij=0表示其他情况。p_ij=1表示在集货车辆序列中集货车辆i排在集货车辆j之前, p_ij=0表示其他情况。q_ij=1表示在送货车辆序列中送货车辆i排在送货车辆j之前, q_ij=0表示其他情况。R为集货车辆数; S为送货车辆数; N为物品种类数; r_ik为最初装载在集货车辆i中的k物品总数; s_jk为最初送货车辆所需要k物品的总数; D为因装卸货车辆交替所耽搁的时间; V为物品从集货平台到装货平台移动时间; x_ijk为集货车辆i转移物品k到送货车辆j的数量; M为较大正实数。

目标函数P₀ 为:

minTs.t. T≥Lj, j∈∀(1)∑jSxijk=rik, i∈∀, k∈∀(2)∑i=1Rxijk=sjk, j∈∀, k∈∀(3)xijk≤Mvij, i∈∀, j∈∀, k∈∀(4)Fi≥ci+∑k=1Nrik, i∈∀(5)cj≥Fi+D-M(1-Pij)(6)i∈∀, j∈∀, i≠jci≥Fj+D-Mpij(7)pii=0, i∈∀(8)Lj≥dj+∑k=1Nsjk, j∈∀(9)dj≥Li+D-M(1-qij)(10)i∈∀, j∈∀, i≠jdi≥Lj+D-Mqij(11)i∈∀, j∈∀, i≠jqii=0, i∈∀(12)Lj≥ci+V+∑k=1Nxijk-M(1-vij)i∈∀, j∈∀(13)

以上所有变量均大于等于零。

集货车辆货品一部分直接搬送到送货车辆上, 一部分暂存于临时库存中。货品直接转移到送货车辆上比转移到临时库存后再转移到送货车辆上所需时间少。为此, 货品转移到临时库存中的数量越少, 总越库作业所需时间越少。储存在临时库存中的物品数量多少由集、送货车辆之间的排序引起, 因此集、送货车辆排序的优劣可以通过临时库存中物品数量的多少判断。

为此, 求解越库数学模型需设计计算临时库存所存储物品数量的方法, 首先对符号进行如下定义: tri为集货车辆i; tsj为送货车辆j; T^r为已被安排顺序的集货车辆组; T^s为已被安排顺序的送货车辆组; L_k为临时库存中各种货品数量集合; r'_ik为在某一次迭代次数中集货车辆i所装载的产品类型k的物品数量; s'_jk为在某一次迭代次数中送货车辆j所需要的产品类型k的物品数量; PijRT为集、送货车辆都被排序后, 由集货车辆i转移到临时库存的物品总数; PjAT为由送货车辆j对应的集货车辆发送到临时库存的物品总数; P^AT为所有的集货车辆发送到临时库存的物品总数。

目标函数P₁为:

minPATPAT=∑j=1SPjAT(14)

Step1 生成T^r={ tr1, tr2, …, trR-1, trR},

T^s={ ts1, ts2, …, tsS-1, tsS}。

Step2 根据集、送货车辆顺序, 将集货平台上集货车辆 tri上的货品装载到装货平台上送货车辆 tsj上。

Step2.1 如果送货车辆 tsj没有装满所需货品, 即, 如果 ∑k=1N[max{s'_jk-r'_ik, 0}]≠ 0。

将临时库存中L_k货品装入送货车辆 tsj中, 更新L_k、s'_jk。若装满所需货品, 进入Step3; 若没有装满所需货品, 将集货车辆 tri上的货品放入临时库存L_k中, 更新L_k、 tri'、s'_jk, 计算 PijRT, 进入Step2。这里 PijRT计算公式如下:

PijRT=∑k=1N[max{r'ik-s'jk, 0}](15)

Step2.2 如果送货车辆 tsj装满所需货品, 即, 如果 ∑k=1N[max{s'_jk-r'_ik, 0}]=0。

计算 PijRT, 进入Step3。这里 PijRT计算公式如下:

PijRT=∑k=1N[max{(r'ik-s'jk)-s'jk, 0}](16)

Step3 计算 PjAT。

PjAT=∑i=1RPijRT(17)

Step4 若存在送货车辆没有装满所需货品, 更新送货车辆 tsj、r'_ik, 进入Step2; 若所有送货车辆均装满所需货品, 计算P^AT:

pAT=∑j=1SpjAT(18)

和声搜索(Harmony search, HS)算法由Geem等于2001年提出^[9]。首先在和声解集HM内随机生成HMS组初始解, 然后以记忆库取值概率HMCR选择是在HM内搜索新解, 还是在和声记忆库外取值。若解来自于HM内, 则需依据音调调整概率PAR选择是否对新解作频宽BW大小的局部扰动。最后, 判断新解目标值是否优于HM内的最差解。若是, 则用新解替换最差解, 继续迭代, 直至满足终止条件为止。

基本的和声搜索算法其参数是固定的, 但参数在不同迭代时期有不同的表现形式。例如, 在迭代初期较大的BW搜索较优结果的能力较好, 但在迭代末期较小的BW有更好的表现^{[10, 11]}。为提高HS算法的搜索能力, IHS算法在音调调整步骤对PAR和BW做动态调整。BW和PAR的计算过程如式(19)(20)(21)所示:

PAR(gn)=PARmin+(PARmax-PARmin)NI×gn(19)BW(gn)=BWmaxexp(c×gn)(20)c=lnBWminBWmax/NI(21)

式中:PAR(gn)、BW(gn)分别为每一次迭代的PAR和BW的值; PAR_max、PAR_min分别为PAR的最大值和最小值; BW_max、BW_min分别为BW的最大值和最小值; gn为迭代次数; NI为总迭代次数。

田口试验被广泛地应用于工程设计中, 用来确定最优的试验条件。每个参数的影响能力可以通过信噪比(Signal to noise ratio, SNR)表示, 通过SNR在控制因子中寻找变异量小的组合。根据HS算法和IHS算法参数特点, 设置不同参数水平如表1和表2所示。以试验组1中数据为基础, 通过MINITAB软件得到两种算法的参数在不同水平下的信噪比主效应图如图2和图3所示。

表1

Table 1

表1(Table 1)

表1 HS算法的因子及其水平 Table 1 Levels of parameters for HS 变量 HS变量水平 L1 L2 L3 L4 HMS 5 10 15 20 HMCR 0.7 0.9 0.95 0.99 PAR 0.2 0.4 0.6 0.7 BW 0.01 0.35 0.7 1.0

表1 HS算法的因子及其水平 Table 1 Levels of parameters for HS

表2

Table 2

表2(Table 2)

表2 IHS算法的因子及其水平 Table 2 Levels of parameters for IHS 变量 HS变量水平 L1 L2 L3 HMS 10 15 20 HMCR 0.70 0.85 0.99 PARmin 0.05 0.25 0.40 PARmax 0.60 0.80 0.90 BWmin 0.05 0.25 0.40 BWmax 0.80 0.90 1.00

表2 IHS算法的因子及其水平 Table 2 Levels of parameters for IHS

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 HS参数的信噪比主效应图Fig.2 Main effects plot for SNR of HS factors

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 IHS参数的信噪比主效应图Fig.3 Main effects plot for SNR of IHS factors

根据图2可知, HS算法的4种参数中, HMS对信噪比的影响最大, PAR的影响次之, 然后分别是BW和HMCR。根据图2选取参数HMS为20, HMCR为0.9, PAR为0.2, BW为0.7。

根据图3可知, IHS算法的6种参数中, HMS对信噪比的影响最大; BW_min和BW_max的影响分别次之; 然后是PAR_max和PAR_min; 最后是HMCR。根据图3选取参数HMS为20; BW_min和BW_max分别为0.05和0.9; PAR_max和PAR_min分别为0.8和0.05; HMCR为0.99。