离散需求下基于两阶段思想的分布式仓储研究

鲍福光

(浙江工商大学信息学院，浙江杭州310018)

0 引言

目前求解背包问题的算法有递归回溯法、分支定界法、动态规划法等精确算法以及贪婪法、遗传算法、交叉熵方法、蚁群算法、粒子群算法、禁忌搜索算法等算法［1、2］。因此，本文研究的问题是涉及需求离散的，动态的，但货物存储周期是统一的第三方物流仓储企业的动态分布式仓储能力分配策略。首先建立了基于随机背包思想［4］的动态规划和两阶段模型，再对该模型设计了采用贪婪思想［5］修复无效解的遗传算法。最后进行数值仿真分析。

1 问题假设与符号说明

由于各种货物的仓储条件和客户的类型不同，不同客户不同货物的存储费率不同，给仓储企业的收益也不同。结合背包问题“有N件货物和一个容量为M的背包。第ij件货物占用的体积是dij，收益是gij。求解将哪些货物装入背包可使收益总和最大。”第三方物流仓储企业该如何将其有限的仓储能力进行合理的分配，接受谁，放弃谁，这就是一个典型的动态规划问题。假设第三方物流仓储企业仓储能力为M(有限且确定)。为了使问题的关键部分更为凸显，本文还对上述问题进行了如下假设:(1)某第三方物流仓储企业能够为不同客户不同类型的货物提供不同的物流仓储服务，而且各种客户能为本第三方物流仓储企业带来的效益贡献也不同;(2)货物存放在仓库中的任何位置可以通过现代物流技术实现寻找与存取;(3)储存周期都是从期初到期末;(4)各种等级货物仓储容量的需求不确定且离散。其目标就是如何确定分配给各种等级货物和各种客户的仓储能力，才能使得企业的总体收益最大，并且便于统一协调管理。在建模之前，对模型中所用变量说明如表1所示。

表1 符号意义说明

2 模型构建

(1)数学模型，普通的背包问题就是往容量为M的“背包”中放入尽可能大价值(收益)的货物。而本文研究的还要涉及不同货物类型要区分不同区域，然而本研究中只是总仓储能力确定，每个类型的区域却可以动态变化的。这就给本文的工作带来了一定的难度。假设根据货物类型可以分为3个区域(ABC)。每个区域请求仓储空间的货物属性主要有货物标号、占用空间和收益贡献等。可以建立如下动态仓储能力分配模型:

式中，G表示仓储企业总收益，M表示第三方仓储企业的总仓储能力，i代表不同客户，j代表不同类型的货物(存放的区域不同)，dij表示不同客户不同货物的占用空间，gij表示不同客户不同货物的收益，Ij表示j区域最后一个选中的货物标号。简易需求表如表2所示。

表2 动态规划分布式仓储

本文为了便于编程处理，将所有货物进行统一编号(即将ij统一于i)，那么上述的数学模型就可以进行如下转化:设xi为二进制变量。如果货物i被放入背包，则xi=1，否则xi=0。数学模型描述如下:

在N个货物中，前N/3个xi表示A区域货物是否被选中，中间N/3个xi表示B区域货物是否被选中，后N/3个xi表示C区域货物是否被选中。ABC(j)区域划分模型如下:

(2)贪婪算法与遗传算法有效结合。贪婪算法是一种一步式启发算法，每使用一次贪婪准则所做出决策是不可撤回的。该算法无法在两个可行解之间进行比较选择，算法在结束时只能得到一个可行解。常用的贪婪准则是收益占用比gi/di，选择准则思想是:从剩余货物中选择可以装入背包的gi/di值最大的货物。将贪婪算法与遗传算法有效结合构成混合遗传算法，可以通过遗传算法不断地重复执行复制选择、交叉与突变以及贪婪算法的修正等操作的一个过程，不断地择优，使得所求解不断地接近最优解。1)编码。本文采用二进制方法进行编码，在编码串中“1”表示对应的货物存入背包，而“0”表示未存入。例如“10011100110011000…00011”就代表一个解，它表示第1，4，5，6，9，10，…，n －1，n 号货物存入背包中，其它的货物则不存放。这个二进制的编码既符合0/1背包问题的精髓，又有效解决了遗传算法的选择、交叉和突变等操作。2)基于贪婪算法的染色体修复。二进制基因编码的方法是比较直观的，但也存在着一个问题:在对任意几组编码串，进行交叉，突变等相关操作后产生的一个个新个体，它们未必就满足本文的约束条件，也就说不一定是可行解，产生许多无效的染色体。那么如何处理这些不满足约束条件的染色体呢?本文利用贪婪算法进行修复。修复的基本思想为:在所有被选择中(xi=1)的货物之中，将收益占用比(gi/di)最小的货物取出，一直到满足背包的容量限制为止。这样产生的新染色体都会满足约束条件，而且其染色体的质量也相对较好。3)适应度函数。在采用贪婪算法修正染色体已经确保了所有的染色体都是有效的，所以在个体适应度计算时就不用引入惩罚数了。当然惩罚数的方法也可以解决这个问题。但是，算法的求解性能(主要指计算速度和解的质量)远远不如本文的方法(基于贪婪算法的染色体修复)。本文可以直接采用目标函数作为适应度函数，即:

(3)分布式处理模型(第二阶段处理)。在运用背包问题求解完毕，可以知道哪些货物给予仓储空间，哪些货物源被放弃。然后利用不同货物的类型将已被选中的货物进行分布式存储。模型如下:

3 算例模拟与分析

(1)算例数值模拟。假设根据货物的性质可以将仓储区域大致分为3个大区(ABC)，而每个区域请求仓储能力的货物情况如表3所示。本文根据动态背包模型设计了采用贪婪算法策略排除无效解的混合智能算法，并编写了对应的MATLAB程序，运行的最优期望收益是372.8。分配如表3所示。

表3 动态规划分布式仓储模拟数据

(2)基于算例的算法性能分析。针对采用不同策略排除无效解的遗传算法进行算法性能分析，主要包括:解的质量，求解的稳定性以及求解的时间等等。本算例实验的系统配置为2.93GHz，1.98GB内存(不同的运行环境会使得运行时间有所差异)。在这个系统环境下，运行结果如图1、表4、5所示。从图1中可以发现采用“贪婪算法”策略修复无效解的遗传算法10次运行结果都好于采用“惩罚因子”策略排除无效解的混合智能算法10次运行结果，且比较稳定。

图1 采用不同排除策略的遗传算法运行结果比较

表4 采用不同排除策略的遗传算法10次运行结果比较表(期望收益)

表5 采用不同排除策略的遗传算法10次运行时间比较表

从表4中可以发现，采用“惩罚因子”策略排除无效解的遗传算法10次运行的平均值为357.07，而采用“贪婪算法”策略修复无效解的混合智能算法10次运行的平均值为371.8，期望收益最优值为372.8。表5中可以发现，它们的运行时间都在1.5s左右，都比较理想。它们的差别也属于随机差别。但是，如果采用“惩罚因子”策略却想要达到如同采用“贪婪算法”策略的解的质量，就必须增加遗传代数。经过试验发现，将遗传代数从200改为1 000，运行时间就达到16倍之多，但还是没达到采用“贪婪算法”策略的解的质量。

4 结束语

背包问题是属于动态规划的一个经典类型，它包含了背包问题中设计状态、方程的最基本思想。另外，在实际问题求解时，还要考虑算法的时间和空间复杂度等问题。本文以背包问题为基础，进行两阶段分布式存储，构建了离散需求情境下基于两阶段思想的分布式仓储模型。进而设计了采用“贪婪思想”修复无效解的遗传算法。并且与普通采用“惩罚因子”排除无效解的遗传算法进行性能比较，发现本文设计的采用“贪婪思想”修复无效解的遗传算法求解的稳定性、解的质量和时间等方面都好于后者。

［1］王莉，绍定宏，陆金桂.基于遗传算法的0/1背包问题求解［J］.计算机仿真，2006，23(3):154－156.

［2］王联国，洪毅，施秋红.全局版人工鱼群算法［J］.系统仿真学报，2009，21(23):7 483－7 486.

［3］卢长先，陆一平，查建中.求解0/1背包问题的交叉熵方法［J］.计算机仿真，2007，24(7):183－186.

［4］邓长寿，梁昌勇.求解武器—目标分配问题的混合编码差异演化算法［J］.计算机应用研究，2009，26(1):74－76.

［5］Ravindra K Ahuja，James B Orlin，Ashish Tiwari.A greedy genetic algorithm for the quadratic assignment problem［J］.Computers＆ Operations Research，2000，27(1):917 －934.