基于双层遗传算法的仓库拣选路径优化问题研究

李永伟,刘树安,郭晋秦

(1.太原工业学院,山西 太原 030008;2.东北大学信息科学与工程学院,辽宁 沈阳 110004)

引言

普通立体仓库是由低层货架构成,采用单元货格式货位,并由人工寻址、人工拣选完成货物出入库操作的一种仓库。由于其具有结构简单、配套设备较少、维护费用低、出入库灵活等优势,使其得以在信息技术高速发展的潮流中广泛应用于物流仓储业中[1-2]。本文以某轴承仓库为研究对象,对出库货位优化问题进行研究。

该轴承仓库主要的仓储区包括理货区和货架区。理货区位于仓库出入库口,主要用来对出入库货物起缓冲作用或者存放特殊规格的货物;货架区并列成排,立于仓库的中心,采用随机存储的策略存放货物。仓库的搬运设备以叉车为主。出库过程中,仓库工作人员接到客户的货物需求,凭借经验和记忆去相应的货位拣选货物,并利用搬运设备完成出库操作,最后更新相应的仓库基本信息。

拣选基本路线为工作人员操作搬运设备从理货区出发,并进入货区拣选货物,最后回到理货区,在货区拣选货物过程中完全凭借经验进行,并没有给出确定的路线,不仅耗费体力,而且大大降低了仓库的周转效率。为了提高仓库运作效率,本文以出库作业单的生成为切入点,力求仓库管理系统能够生成带有优化的出库作业单,即对于出库单除了包含出库货物信息外,还应包含对应的拣选路径和拣选批次。围绕以上问题,建立出库货位优化模型,并设计算法对模型进行求解,最后通过仿真实验验证算法的有效性。

1 出库货位优化模型的建立

为了便于对出库过程的数学表述,给仓库货位进行编号。设货区共有N个货位,从靠近理货区出发,自上而下、由近及远依次对每个货位进行编号:k=1,2,…,N,并设理货区的编号为0。在出库过程中工作人员如何合理地从成百上千个货位中拣选出所需的货物,并对拣选路径进行合理选择是出库货位优化时需要解决的问题。由于叉车载重的限制,出库过程中需由多个批次来完成所需货物的拣选工作。因此可以把货位优化问题进一步表述为,旨在解决如何合理地确定每件所需货物出库时所在的出库货位和出库批次,以及如何合理地确定相应的拣选路径。通过解决该问题,进而提高仓库的出库效率。基于以上分析,定义如下决策变量及相关参数。

1.1 单批次载重约束

制定每一批次的出库计划时,需要考虑叉车负重能力的约束,假设单批次载重上限为W,则在出库过程中单批次载重约束为:

(1)

其中TO—所有待出库货物的种类总数,wi—单位i类货物的重量(Kg),W—单批次载重的上限(Kg),j—出库作业的批次编号,q—完成出库作业用的总批次数。上式(1)表示在任意批次的出库作业中,叉车所载货物的总重量不得超过单批次的载重上限。

1.2 出库货物种类约束

在出库拣选过程中,对于所需的第i类货物只能选择从存放该类货物的货位中拣选,因此可以通过货位状态变量Sk和对应的k货位中货物z是否选择出库共同决定决策变量yjkz的取值情况:

(2)

1.3 出库订单数量约束

出库过程分多个批次完成的,其目的是把出库单上的所有货物从相应的货位中拣选齐全,所以有如下约束:

(3)

1.4 货位出库次数的约束

出库过程分q个批次完成对需求货物的拣选工作,由于单批次载重量远大于单个货位的容量限制,为了防止在多个出库作业批次中对某些货位重复进行拣选工作,规定在整个出库过程中每个货位只到达一次,结合前文论述,可得到货位出库次数限制的约束条件为:

Ka∩Kβ=Ø,α,β=1,2,…,p且α≠β

(4)

(5)

1.5 模型目标

本文以工作人员在出库过程中走过的总路程最小为优化的目标。由前文可知,整个出库过程分q个批次来完成,设在第j个批次走过的货位集合为Kj,如果求得第j个批次的拣选路径,并求得相应的路程,最后累加q个批次的路程即可得到出库货位优化模型的目标函数,由此可得到出库货位优化的目标函数:

(6)

其中zuv∈{0,1},u,v∈Kj且u≠v

duv—货位u和货位u之间的距离(米),d0v—理货区和货位v之间的距离(米),du0—货位u和理货区之间的距离(米)。上式(6)表示完成出库作业时工作人员走过的总路程。

2 算法设计

出库过程中,决定着问题优化结果的因素可以归结为出库时经过了哪些货位,即选哪些货位完成出库操作;对于每个需要经过的货位,对应的出库货物的种类和数量分别是多少;出库时,每个货位所在批次,及批次内经过每个货位的先后顺序,即根据所选货位的出库量进行划分作业批次,并按一定的顺序完成出库操作。因此,出库货位优化可分为两层:首先,选择哪些货位进行出库操作,即货位选择优化层;其次,对已选货位完成出库操作时的批次划分及先后顺序的确定,即货位顺序优化层。

由模型和问题本身的分析可知,该问题随着货位数量和货物种类的增多,模型的求解工作量会呈现指数式增长,属于组合优化问题[3]。对于组合优化问题,多采用智能算法进行求解,而遗传算法作为经典的智能算法,其具有鲁棒性好、寻优能力强的优点[4-5]。因此,针对货位优化模型的两层优化,将两个遗传算法嵌套分别对货位选择层和货位顺序层进行求解。下面用变量X代表货位选择优化层,用变量Y代表货位顺序优化层,算法的具体流程如图1所示。

图1 双层遗传算法流程图

遗传算法中主要的算子包括编码、交叉、变异和选择策略的设计。由于本文算法方面的创新点主要在于算法结构的设计,所以对于内部算子不作过多研究[6-7]。货位选择优化层中,由于货物种类较多,分别采用均匀交叉和互换变异,而货位顺序优化层采用顺序交叉和互换变异,选择策略采用轮盘赌的方式。下面主要针对双层遗传算法的编码、染色体修复及解码进行设计。

2.1 出库货位选择优化层编码

货位选择层主要解决选择哪些货位完成出库操作的问题。所以,在编码时可用整数1表示出库时选择该货位中的货物出库,整数0表示不选择。染色体的具体结构设计如图2所示。

货位的选择:0111001101110

图2染色体结构

很显然,从以上染色体还不足以得到每个可用货位的选择情况,所以设计辅助字符串,确定货位的选择情况。首先在选择可用货位时必须满足条件:mki>0,∀i∈I2,即所选货位k中含有需要出库的货物。

另外,为了便于后续的算法设计,对可用货位按货物种类分段,并以货位的可出库货物量Yjk由小到大排序,货位的可出库量可由公式(7)得到。

(7)

由此,染色体的辅助字符串中还需包含每个货位拥有货物量的信息及对应的货物种类。另外,为了满足在整个出库过程中每个货位只服务一次的条件,初步设定每个选中出库货位的实际出库量等于该货位可出库的货物量,即每到达一个货位,把该货位的货物全部出库。最后,根据货物的计划出库量要求对每个货位的实际出库量作适当修正。由以上分析可得出,染色体的辅助字符串的结构设计如图3所示。

货物种类:货位编号:可出库货物量:实际出库量:11112222333335131418921020136712192101216113611581718230101216006110817180

图3辅助字符串

结合染色体和辅助字符串的信息,可以得到在出库过程中从第k个货位中拣选货物的数量。具体在哪一个批次完成货物的拣选,需经过货位顺序层进一步确定。

2.2 染色体的修复

本文针对出库时实际出库量不等于计划出库量的情况对染色体进行修复,具体修复策略如下:

2.3 货位顺序层编码设计

货位顺序层是在货位选择优化层的基础上进行优化的。出库时,经过货位选择层确定了选那些货位出库后,结合货位选择层染色体的辅助字符串信息,可得到如图4所示的信息。

货物种类:货位编号:实际出库量:11122233331314179201671215101225111208171827

图4选择层结果

由此,可确定出库过程中所要到达的货位和每个货位需要出库的货物量。另外,搬运设备有相应的载重约束。货位顺序优化层需要合理确定出库操作时走过货位的顺序,然后在解码时划分货物的出库批次,即可得到出库方案。所以,本文采用基于整数的编码方式,染色体的每一个基因代表一个货位,基因顺序表示完成出库操作时所经货位的先后顺序。染色体的结构设计如图5所示。

染色体:1314179201671215

图5染色体结构

图5编码表示,在出库过程中按货位顺序13-14-17-9-20-1-6-7-12-5完成出库作业。另外,由于受搬运设备载重的限制,要得到完整的出库方案,还需要结合各个货位的出库量,按叉车的载重约束划分出库批次,所以还需要设置染色体的辅助字符串,表示相应货位的出库量和对应的货物种类,辅助字符串的设计如图6所示。

货物种类:实际出库量:1112223333101225111208171827

图6辅助字符串

2.4 解码

解码的过程实际上是根据搬运设备的载重约束,结合染色体的辅助字符串信息,把染色体对应的货位依次划入各个批次的出库任务中,进一步确定出库路径,然后根据货位间的距离得到工作人员在出库过程中经过的总路程,以此来评价当前染色体对应的出库效果,经算法的迭代,不断搜索到质量更优的解。下面以图5所示的染色体及其辅助字符串信息为例,并假设叉车载重为50(Kg),每类货物的单位重量为1,进一步说明解码过程。

按如下步骤得到出库方案:首先将货位13纳入到第一个出库批次,然后判断货位14是否可以纳入到第1个批次,由于货位13和货位14对应的货物量之和满足载重约束,即10+12<50,所以可以将货位14纳入到第1个批次。同理，可以把货位17、货位9纳入到第1个批次。然后判断货位20是否可以纳入到第1个批次,假设可以,则该批次对应的货物量之和不满足载重约束,即10+12+25+1+11>50,所以货位20不可纳入到第1批次。由于叉车从理货区出发,最终回到理货区,所以可以得到在第1个出库批次中,叉车所走的路径为0—13—14—17—9—0。同理,可以得到：第2个批次路径为0—20—1—6—0;第3个批次路径为0—7—12—0;第4个批次路径为0—15—0。

到此,得到了完整的出库方案,然后根据仓库货位之间,以及货位和理货区之间的距离计算得到出库过程中工作人员走过的总路程,即目标函数的值,并以此评价该出库方案的好坏。

3 仿真实验与结果分析

本文以轴承仓库某次出库过程为例,对上述货位优化模型和算法进行验证。已知叉车载重为500 Kg,仓库内部货位间的距离及货位的存储状态已知,出库货物的种类、数量及库存量如表1所示。

表1 出入库相关信息

3.1 参数试验

由于所设计的双层遗传算法的参数较多,本文采用控制变量法进行参数实验,且实验过程中均采用10计算取均值的方法。由理论分析和实验结果可得,种群规模越大,迭代次数越多,结果越精确。但随着种群规模和迭代次数的增多,算法执行时间成指数式增加。综合可得,货位选择优化层最佳参数为交叉率0.8、变异率0.2、种群规模100、迭代次数200;货位顺序优化层最佳参数为交叉率0.7、变异率0.1、种群规模50、迭代次数250。

3.2 优化结果分析

利用双层遗传算法对算例进行求解,然后结合模型参数对求解得到的出库分配方案进行详细的分析。在建立出库货位优化模时,定义了决策变量yjkz,表示在第j个出库作业批次,是否选择货位k中的货物z出库。由于每个货位货物的数量较多,不可能对每个货物的选择与否进行表示,这里只表示出每个货位的实际出库量。所以,引入中间变量Yjk:表示在第j个批次货位k的出库量,通过实验得到出库拣选方案如表2所示。

表2 出库货位优化结果

由上文可知,本文对仓库货位采用依次编号的形式进行表示,即相邻编号的货位,意味着货位间的距离相近。通过分析表2的求解结果可以发现,所有批次内货位编号没有大的跳跃,说明算法在求解货位优化问题的过程中,对出库目标货位的选择是比较合理;在出库方案中,单批次内总有相邻编号的货位先后进行出库,说明货位顺序层对货位选择层选中的目标货位进行了出库顺序优化;大部分批次的载重量接近叉车载重:500 kg,说明算法在求解货位优化问题的过程中对批次的划分是比较合理。对于表2中的批次5,批次载重量为278.0 kg,与叉车的载重量差距比较大,这是因为该批次所经过的货位集中在理货区附近,单独划分一个批次来完成相应的出库操作更为合理。

由以上分析可得到,在利用双层遗传算法求解货位优化模型时,在货位选择优化层、货位顺序优化层、出库批次划分3个关键点都取得了比较满意的效果。

4 结论

本文以普通立体仓库为研究对象,针对货物出库时拣选作业路径进行了优化研究。首先建立了拣选路径优化模型,将这一优化问题分为货位选择优化层和货位顺序优化层,并利用双层遗传算法进行求解,通过对算例的求解,验证了模型及算法的可行性和合理性。但由于遗传算法是多点搜索,使用双层遗传算法求解货位优化问题时效率极其低,在下一步的研究中,可就算法效率方面进行研究。