基于贪婪算法的货位优化模型

刘志帅，仝凌云，魏利鹏，朱 凯，茜晓立

LIU Zhi-shuai1,TONG Ling-yun1,WEI Li-peng2,ZHU Kai1,QIAN Xiao-li1

（1.河北工业大学 经济管理学院，天津 300401；2.天津理工大学 中环信息学院，天津 300380）

(1.School of Economics&Management,Hebei University of Technology,Tianjin 300401,China;2.Zhonghuan Information College,Tianjin University of Technology,Tianjin 300380,China)

伴随科技的进步和经济的发展，尤其是改革开放以来，我国仓储业取得了快速发展，仓储设施得到明显改善，服务水平与作业效率有所提高。但从总体上看，我国仓储业的传统经营方式还没有根本性改变，仓储自动化、标准化与信息化管理仍处于较低水平，造成我国流通企业商品库存时间过长、占压资金过多。2007至2011年，我国总物流费用占国内生产总值的比重由18.2%下降到17.8%，而保管费用占国内生产总值的比重却由5.8%上升到6.1%[1]。企业往往从运营成本角度考虑，导致依赖人工作业的仓库和配送中心仍占据较大比重。

仓库和配送中心作为供应链的一个重要组成部分，其订单拣选作业系统的效率是影响仓库和配送中心整体运行效率的关键因素，进而也影响整个供应链的运营效率。仓库或配送中心大约50%～75%运营成本都来源于订单拣选作业[2]。订单拣选作业是仓储工作人员根据顾客订单在货位上拣取货品的整个作业流程，其效率的高低受到货位布局和企业运营策略的影响。而通过货位优化可以改善订单拣选作业的效率。

当前，国内外学者货位优化的研究较多，主要集中在以一段时期内的订单拣选作业成本最小、订单拣选时间最小、行走距离最短、货架重心最低等为目标建立相关的货位优化模型研究方面，较少考虑到货品特性中的质量对订单拣选作业影响。从人因工程学的角度来考虑，在实际的订单拣选作业过程中，货品质量也是影响搬运效率的重要因素之一，尤其是完全依赖人工作业的仓库或配送中心。

基于分类存储策略，本文通过对一段时期内的有效订单进行统计，以人工订单拣选作业导致的人体能耗最小为目标，建立了货位优化模型，然后利用贪婪算法对该数学模型较为快速地进行求解。

1 货位优化模型

1.1 分类存储策略

存储策略即决定货品在仓库或配送中心存储区域位置的指派方法及相关原则，合适的存储策略可以减少出入库移动的距离、缩短作业时间，甚至能够充分利用存储空间。常见的存储策略有固定货位存储策略、随机存储策略、分类存储策略、分类随机存储策略和共同存储策略。其中分类存储策略是指把货品按照类别进行存储，并且每一类别的货物都有其固定的存储区域，而同属一类的不同货品又按照一定的原则来指定货位。分类存储策略方便畅销货品的存取，具有固定货位存储策略的所有优点[3]。故本文选用其作为存储策略，考虑如何将仓库或配送中心的货位安排给各个分类，最终实现人工订单拣选作业所致的人体能耗的最小化。

1.2 货位优化模型假设

为了构建货位优化数学模型，提出以下假设：

仓库或配送中心只有一个出入口；同一货位仅存储同一类别货品，不允许混放；同一类别货品可以有多个货位；每个货位存放的货品以容积为限；所有货位及托盘尺寸一致；订单拣选作业人员匀速行走；订单拣选作业人员人体能耗只由货品质量引起，工作人员自身质量和拣选设备质量不计，且只计算在货位至出库口的克服摩擦力导致的能耗，不计从货位拣取至设备上的人体能耗；订单拣选作业拣取货品的货位始终为该类别货品距离出口最近的货位；货位至出库口的距离采用直线距离（曼哈顿距离）计算。

1.3 建立模型

设置优化模型参数如下：

Hi——第i类货品，1≤i≤I

Hij——第i类中的第j种货品，1≤i≤I，1≤j≤J

Qm——第m个货区，1≤m≤M

Qmn——第m货区中的第n个货位，1≤m≤M，1≤n≤N

Lmn——第m货区的第n个货位至出库口平面直线距离，1≤m≤M，1≤n≤N

μ——搬运设备与仓库或配送中心地面的摩擦系数

mij——第i类中的第j种货品的单件质量，1≤i≤I，1≤j≤J

nij——第i类中的第j种货品的出货数量，1≤i≤I，1≤j≤J

Mij——第i类中的第j种货品的总出货质量，1≤i≤I，1≤j≤J——第i类货品的总出货质量，1≤i≤I，1≤j≤J

XHiQm——表示若第i类货品存储在第m货区中，则XHiQm=1，否则 XHiQm=0，1≤i≤I，1≤m≤M

XHijQmm——表示若第i类中的第j种货品存储在第m货区中的第n个货位中，则XHijQmn=1，否则XHijQmn=0，1≤i≤I，1≤j≤J，1≤m≤M，1≤n≤N

以任意某一段时期内的有效订单为研究对象，结合物理学相关知识，订单拣选作业导致的人体能量消耗主要来自于克服搬运设备与地面摩擦力，从货位Qmn拣取货品Hij的人体能耗，则可以表示为：

其中，g为重力加速度，取9.8N/kg，其他计量单位均为相对应的国际标准单位。

因此，可得到目标函数：

其中，目标函数（1）表示货位优化之后，使得人工订单拣选作业所导致的人体能耗最小；约束条件（2）和（3）保证把总出货质量较大的货品类指派到距离出口较近的货区中；约束条件（4）和（5）确保把同一类中总出货质量较大的货品种别指派到距离出口较近的货位上；约束条件（6）表示货区存储的唯一性，即货区Qm仅存储同一类别的货品；约束条件（7）表示货位存储的唯一性，即货位Qmn仅存储一种货品品项；约束条件（8）和（9）为决策变量的取值约束；约束条件（10）表示货区数目和货品类别数目必须一致。

2 贪婪算法求解模型

2.1 贪婪算法

贪婪算法（又称贪心算法）是一种常用的求解最优化问题的简单、迅速的方法。在求解问题时，贪婪算法总是做出在当前看来最好的选择，它所作的每一个选择都是在当前状态下某种意义的最好选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解[4-5]。其基本思路为：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止[6]。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

对于企业而言，耗费大量的人力、财力和时间去求解目标函数的最优解是不经济的，尤其是对那些出货差异较大的仓库和配送中心而言，因为最优解是伴随时间而不断变化的。因此，本文针对此类配送中心或仓库，采用了贪婪算法进行快速求解。

2.2 模型求解

贪婪算法求解次货位优化模型的步骤如下：

Step 1：计算每一个货品品项的总质量Mij、每一类货品品项的总质量Mi、每一个货区到出口的距离的Lm和每一个货位到出口的距离Lmn；

Step 2：将货品类别按照Mi值降序（非增序）排列编号，设A（）a为排序后的数列，其中a为顺序号；

Step 3：将货区按照Lm值升序（非降序）排列并编号，设B（）b为排序后的数列，其中b为顺序号；

Step 4：将具有最大Mi值的货品类别Hi存储在Lm值最小的货区中，即把数列A（）a中编号为1的那一类货品指派到数列B（b）编号为1的货区中，然后把编号为2的那一类货品指派到数列B（b）编号为2的货区中，重复这一过程，直到把数列A（a）中的所有类别的货品指派完毕；

Step 5：将同一类下的货品类别按照Mij值降序（非增序）排列编号，设C（）c为排序后的数列，其中c为顺序号；

Step 6：将同一货区的货位按照Lmn值升序（非降序）排列并编号，设D（）d为排序后的数列，其中d为顺序号；

Step 7：将具有最大Mij值的货品类别Hij存储在Lmn值最小的货位中，即把数列C（）c中编号为1的那一类货品指派到数列D（d）编号为1的货位中，然后把编号为2的那一类货品指派到数列D（d）编号为2的货位中，重复这一过程，直到把数列C（c）中的所有类别的货品指派完毕；

Step 8：重复step5～7这一过程，直到把所有类别的货品指派到特定的货位中。

3 结束语

与之前的货位优化目标函数不同，本文从人因工程学的视角，结合分类存储策略，提出了以人工订单拣选作业所致的人体能耗最小的目标函数，并建立了相关的货位优化模型，最后利用贪婪算法这一快速求解算法进行求解。此模型不仅可以对不同时期具有明显差异订单的仓库或配送中心的货位进行快速优化，还因此降低了订单拣选工作人员的劳动强度，提高了劳动效率。从而，进一步提高了仓库或配送中心的运营效率，具有一定的实用性和实际意义。

[1]中华人民共和国商务部流通业发展司.商务部关于仓储业转型升级的指导意见[EB/OL].(2012-12-18)[2013-07-06].http：//www.mofcom.gov.cn/article/b/g/201304/20130400075343.shtml.

[2]John J.Coyle,Edward J.Bardi,C.John Langley.The management of business logistics[M].St.Paul,MN：West Pub.,1996.

[3]田源，张文杰.仓储规划与管理[M].北京：清华大学出版社，2009：134-135.

[4]S.A.Curtis.The classification of greedy algorithms[J].Science of Computer Programming,2003,49：125-157.

[5]Seungmo Kang,Yanfeng Ouyang.The traveling purchaser problem with stochastic prices：Exact and approximate algorithms[J].European Journal of Operational Research,2011,209：265-272.

[6]魏英姿，赵明扬，黄雪梅,等.求解TSP问题的贪心遗传算法[J].计算机工程，2004,30(19)：19-20.