基于遗传算法的库位优化问题

周兴建， 刘元奇， 李 泉 ZHOU Xing-jian,LIU Yuan-qi,LI Quan

（1.武汉科技学院 经济管理学院，湖北 武汉 430073；2.武汉理工大学 交通学院，湖北 武汉 430063）

1 库位优化的提出

邯郸交通运输集团有限公司 （简称 “邯运集团”）是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购 （天信运业及天昊、天诚、天恒等）、快递服务 （飞马快运）、汽贸业务 （天诚汽贸）及仓储配送 （河北快运）等。其中，邯运集团的仓储配送业务由河北快运经营，现有仓库面积总共40 000㎡，主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送，其中以医药为主。邯运集团库存货物主要涉及两个方面：一个是大宗的供应商货物，如医药，化工产品等；另一方面主要是大规模的小件快递货物，如日用百货等[1]。经分析，邯运集团在仓储运作方面存在如下问题：

（1）存储货物繁多而分拣速度低下。仓库每天到货近400箱，有近200多种规格，缺乏一套行之有效的仓储管理系统。

（2）货架高度不当而货位分配混乱。现在采用的货架高度在2米以上，而且将整箱货物直接码垛在货架上，不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子，增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的，分拣和搬运速度较慢。

（3）拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成，出库效率低，出错率难以控制。

（4）存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势，现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。

当前邯运集团的货位分配主要采用物理地址编码的方式，很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率，还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时，结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素，对仓库货位进行规划，以提高仓储效率。

2 库位预分区规划

在进行仓库货位规划时，作如下假设： （1）货物的存放种类已知； （2）货物每种类的单位时间内存放的数量己知； （3）每一种货物的存取频率已知。

在仓库货位优化中一个重要的环节即预分区。所谓预分区，是指没有存放货物时的分区，分区时只考虑仓储作业人员的速度这一个因素。即如果对某些货格，仓储作业人员从原点到达该批货格中的任一货格所用的时间都相等，则这批货格归为一类[2]。

因此，仓储作业人员执行一批指令 （n条）需要的作业时间T为：

式中，T1——仓储作业人员执行第一条指令所需时间，T2——仓储作业人员从当前库位到下一库位所需时间，T3——仓储作业人员从当前库位到原点来回所需时间，T4——仓储作业人员送回库位后从该库位回到原点所需时间。

图1 邯运仓库货格分配图

3 预分区步骤及数学模型

在上面的分析基础上，具体的库位预分区步骤如下[3]：

第一步：设仓储作业人员从原点到某一货格所需时间为t，其中i为货格编码号。设某一时间值t（t的大小与分区数目有关）。该货格所处的区由下式 （2）确定：

如果i货格满足上式，则i货格位于k区。

第二步：经过第一步得到的分区可能各个小区所包含的货格数目不相等。如果各区的货数相差很大则需进行修正，修正的原则 “就近取多补少”，即如果某个区的货格数较少，则从含货格数较多相邻区取货格。取货格时，如果是从高区取货格，则在高区内先取运行时间较少的。如果是从低区取的话，则先取运行时间较多的。无须强求所有区内的货格相同。

第三步：将货物按照出入库频率分类，其数目等于仓库分区的数目。

第四步：建立权值矩阵，单位时间内堆垛机取放某种货物的工作量与该货物的出入库频率不该货物存放的位置有关，将该货物的出入库频率乘以仓储作业人员到达存放位置所用时间作为权值因子，即：

式中，i——i种货物的出入库频率，j——仓储作业人员从原点到j区取放的标准时间ti=j×tij（ ）。

经过以上处理，仓库的初始分区及第一次开始存放变为一个区内放入一种货物，某一种货物放入某一区后即不能再放入其他区，某一区放入某一货物后也不能再放其他货物，即变成为指派问题，其数学模型如下[4]。

目标函数：

约束条件：

考虑到仓库中不同重量的货物放在不同的位置，因此还要考虑货物的出入库频率及货物重量问题，这时可以将仓库货位分配问题建立为二次指派问题。设aijkl为相关因子，即当i类货物分配给j区，k类货物分配给1区时的对货架重力的影响系数。则该库位优化问题数学模型的目标函数为：

4 遗传算法优化方案

邯运集团仓库中的货物种类很多，各类货物的出入库频率也不一样，这时相应分区的数目就很大。对于此类问题再利用前面的方法来求解最优分配货物时就相当复杂，往往无法求解。由于遗传算法在解决组合优化问题时操作简便、寻优能力强，本文用遗传算法对邯运集团的仓库货位优化问题进行研究[5]。

4.1 算法步骤

第一步：编码

遗传算法应用的瓶颈之一是编码问题，本方案中编码采用顺序表达法。以邯运集团河北快运仓库为例，仓库分为9个区存放9类货物，采用顺序表达法时的某个染色体为 [923547681]，该染色体表示第1个区放第9类的货物，第2个区放第2类货物，依次类推。

第二步：适应度函数。如货格分成n个区时，相应的权值矩阵仍用下式建立：

式中：cij——权值矩阵i行j列的元素，是出入库频率与员工从原点到j区的时间之积；f1——i种货物的出入库频率；t1——仓储作业人员从原点到j区取放的标准时间t1=j×t间（ ）。

第三步：初始种群

初始种群的产生和选择机制，重复上面的三步直到产生规定数目的染色体为止。选择过程采用转轮选择机制，适应度函数采用当前代中评估函数的最大值减去该评估函数值。

第四步：遗传算子交叉

步骤1：任何在双亲中指派到相同位置的货物在后代中仍占据这个位置；步骤2：对于剩下的位置由双亲中指派到该位置的两类货物中随机选一类货物，从左到右进行；步骤3：将剩下的未指派的货物分派给尚空闲的位置。

4.2 实现过程

根据以上算法步骤，其求解实现过程为：

（1）建立有n个元素的数组，对每个元素都赋给一个随机数 （随机数值范围从1到:1）。程序如下：

（2）计算数组各元素在数组中按照大小所处的位置。如果有些元素相等，则按数组下标排序，下标值小的元素位置在前面，大的在后面。

（3）将数组b[i]中的值按下标顺序排列，组成一个染色体。

重复上面的三步直到产生规定数目的染色体为止。

以上过程用图2说明：

（4）利用MATLAB进行编程计算并得出最优划分方案，最后得到优化后的结果并利用MATLAB里面的仿真工具箱画出仿真图像。

图2 遗传算法实现过程

[1] 教育部高等学校物流类专业教学指导委员会. “邯运杯”第二届全国大学生物流设计大赛案例[M].北京：北京交通大学出版社，2008.

[2] 银光球，何福英，盛冬发.自动化立体仓库中库位优化模型研究[J].福建工程学院学报，2006(3):347－351.

[3] 邱建东，唐定普，高博,等.重力式立体仓库管理系统核心模块设计[J].起重运输机械，2008(4):37－41.

[4] 卫军朝，任建平，王宗彦.自动化仓库模块化单元式货架的优化设计[J].起重运输机械，2008(6):60－63.

[5] 玄光男，程润伟.遗传算法与工程优化[M].北京：清华大学出版社，2004.

[6] ZHOU Xing－jian,DU Cheng－xiang.A Model of Cost－oriented Price－Making for Logistics Service[C]//International Conference of Production and Operation Management.SPRINGER Press,2008.

[7] J.A.Erskine,M.R.Leenders,L.A.Mauffette,Leenders.Teaching with Case[M].Research and Publication division,School Business Administration,the university of western Ontrario,London,Canada,1981:150.

[8] Bloom,B.S.The Search for Methods of Group Instruction as Effective as One－to－one Tutoring[J].Educational Leadership,1986(10):4－8.