基于贪婪算法的仓库货位优化问题研究

来源：本站 | 发布日期：2023-03-24

1 引言

近年来,我国物流业发展迅速,物流设施明显改善,服务水平与作业效率不断提高。随着物流业的发展,物流企业之间的竞争不断加剧,为了在激烈的市场竞争中站稳脚跟,物流企业纷纷采取各种措施提高服务质量,降低物流成本。仓储是物流系统中的关键环节,高效合理的仓储可以帮助企业加快物资流动的速度,降低物流成本,保障生产的顺利进行,并可以实现对资源有效控制和管理。

分拣作业是仓储活动中的重要一环,分拣作业成本大约占了仓储成本的三分之一,合理的货位安排可以提高拣选作业的效率并降低拣选成本,进而提高仓储效率,降低仓储成本。

近年来,越来越多的学者开始关注分拣作业问题,并对直接影响分拣成本的立体仓库的货位分配问题进行了研究。如:肖建和郑力[1]考虑了货物需求的相关性,对多巷道仓库货位分配优化问题进行了研究;李诗珍[2]考虑货物之间的相似性,以均衡分区同步拣货的工作量为目标对货位进行分配优化。这些研究大部分都只考虑了仓库的运行效率,没有考虑分拣过程中的能量消耗。随着世界能源紧缺问题的日趋严重,如何通过优化储位分配方案降低存储及分拣过程中的能耗问题受到诸多学者的关注。陈月婷和何芳[3]考虑了货物重量以及货架的稳定性,并基于改进粒子群算法对货位进行分配优化;李小笠和刘桂芝[4]考虑了存储能耗、货架稳定性以及运行效率等问题,建立了仓库货位优化数学模型;刘志帅等[5]在考虑货物重量前提下以人工订单拣选作业导致的人体能耗最小为目标对货位进行分配优化;银光球,何福英等[6]在考虑货物重量和需求频率前提下建立了货物存取能耗最小的货位分配优化数学模型,有效地降低仓库的运行成本。以上研究均假设各货物的需求相互独立,在实际中,有些货物的需求并不是独立的,比如螺钉和螺母,由于两者经常同时出现在一张订单中,从提高拣选效率的角度考虑,它们最好被放置在相邻的货位上。但是按照已有文献中的方法,不考虑两种货品的相关性,而是单纯考虑能耗,这两种货品往往被放置在相距很远的两个货位上。

本文拟在综合考虑货品相关性、拣选频率以及单件货品质量等因素的前提下,研究货位优化问题。首先根据货品间的相关性,以及货品的需求频率和单件货品质量,提出修正货品的统计质量指标,并以拣选能量消耗最小为目标建立货位优化问题的数学模型,对存放货品的库区以及货位进行优化分配,进一步设计求解模型的启发式算法,并利用具体算例对模型和算法进行验证。

2 货位优化问题的数学模型

考虑到在实际的订单中,有些货品常常被一起订购,如果只考虑货品的重量和拣选频率来分配货位,被经常一起订购的货品可能会被摆放在相距很远的货位上,这样会降低取货效率。为了提高拣货效率,应该将经常被同时订购的货物就近存放。针对该问题,本文采用如下策略对货位进行分配:首先,根据一段时间内的订单信息计算出各货品间的关联度。然后,结合货品的质量和需求频率,以拣选作业能耗最小为目标,建立货位优化问题的数学模型。

2.1 货位优化模型假设

为了简化问题,本文提出以下假设:(1)每个订单订购多种不同的货品,但每种货品的数量较少;(2)每种货品只存放在一个货架上;(3)不考虑拣选过程中的缺货情况;(4)货位至出库口的距离采用直线距离(曼哈顿距离)计算;(5)订单拣选作业的能耗指设备搬运货品所做的功,包括两部分,一部分是传送设备将货品从货位处传送至出库口的过程中克服摩擦力所做的功,另一部分是搬运设备将货品从立体仓库的货位上搬运到传送设备上克服重力所做的功。

2.2 货位优化模型

假设仓库中有q种货品,d个货位。已知一段时间内的n个订单中,每个订单中的货品种类,现欲将q种货品进行货位分配。

首先将货品按一定的顺序从1到q进行编号,定义订单k的货品特征向量:Ak=(x1k,x2k,…,xqk)T k=1,2,…,n

其中:

这样n个订单可以表示为:

令P=A=(P1,P2,…,Pn)T,其中Pi代表的是第i种货品在各订单中出现情况的行向量,利用Pi,Pj,计算两种货品被同时订购的关联度rij,并用表格表示。其中关联度rij的计算公式为:

为了建立数学模型,先定义如下的变量和符号

si:单位货品i的质量;

Ri:货品i的关联度;

fi:货品i的需求频率;

lc:货位c离出库口的水平距离;

hc:货位c离出库口的垂直距离;

u:货品与传送设备之间的摩擦系数;

g:重力加速度;

,i=1,2,…,q;c=1,2,…,d;

rij:货品i与货品j的关联度;

Mi:货品i的修正统计质量;

dc(h,l):货位c的单位质量能耗。

由于考虑了货品间的相关性,定义每个货品的修正统计质量为:

其中：

根据物理知识,在拣选作业过程中只有克服摩擦力和重力所导致的能量消耗,则以拣选作业过程中能量消耗最小为目标的数学模型可表示为

目标函数(2)表示极小化各类货品的出入库总能耗之和;约束条件(3)表示i货品的关联度等于i货品与其它货品之间的关联度之和;约束条件(4)表示货位的单位质量能耗函数;约束条件(5)表示i货品的修正统计质量等于i货品的关联度、单位货品质量以及其需求频率的乘积;约束条件(6)表示每个货位最多放一种货品;约束条件(7)表示每种货品只能放在一个货位上;约束条件(8)为决策变量的取值约束。

3 启发式算法

由储位优化问题的数学模型可以看出,各种货品出入库所消耗的能量与各自的修正统计质量Mi和货位对应的单位质量能耗函数d(h,l)有很大的关系。货品的修正统计质量越大,出入库消耗的能量就越多;货位单位质量能耗函数越大,货品出入库消耗的能量也就越多,因此,应该尽量将修正统计质量较大的货品放置在单位质量能耗较小的货位上。基于此,本文设计贪婪算法求解货位优化模型,求解步骤如下:

Step 1:计算每一种货品的修正统计质量Mi、每一个货位到出库口的单位质量能耗dc(h,l)。

Step 2:将货品按照Mi值降序(非增序)排列编号,设G(g)为Mi值排序后的数列,其中g为顺序号;

Step 3:将货位按照dc(h,l)值升序(非降序)排列编号,设B(b)为dc(h,l)值排序后的数列,其中b为顺序号;

Step 4:将具有最大修正质量Mi值的货品存储在dc(h,l)值最小的货位中,即把数列G(g)中编号为1的那一种货品指派到数列B(b)编号为1的货位中,然后把编号为2的那一种货品指派到数列B(b)编号为2的货位中,重复这一过程,直到把数列G(g)中的所有货品指派完毕。