1 电商仓储货架选择问题

现今电子商务快速生长
，对仓储物流提出了快速配送的要求。电商货仓中往往需要贮存多种商品
，并且这些商品趋向小型化。电商仓储往往需要小批次高频率进出库商品
，因此订单拣选效率尤为重要。

目前电商仓储经常接纳货到人拣货模式。电商仓储系统的货到人拣货模式与古板仓储系统的拣选模式差别：在电商仓储系统的订单拣选历程中
，机械人将可移动货架搬运到拣选台
，供拣选员拣选订单中需求的商品
，订单拣选完毕后
，可移动货架被机械人搬运回货架存放区域；而古板仓储系统接纳的是牢固式货架
，需要由拣选人员会见货架来拣选商品。相较于古板的拣选人需要移动收集订单商品的模式
，可移动机械人拣货模式更适用于电子商务
，具有拣选速度更快、不易漏选和对拣选员更友好的优点[1]。电商仓储通�；谑枭⒋娲⒄铰越�
，即一个货架可以存放多种商品
，每种商品也被存放在多个货架上。研究标明疏散存储战略可以降低货架资源争夺的水平[2]。疏散存储战略意味着有多种货架组合可以满足拣选单的需求。新的货到人拣选模式也给电商仓储系统的拣选带来了新的挑战
，选择适当的货架组合直接影响着拣选效率和拣选本钱
，但货架选择问题相关的研究并不充分。

针对电商仓储系统的货架选择问题
，本文首先建立了货架选择问题的优化模型
，其次设计了启发式求解算法
，并用数值实验验证启发式算法的有效性和可行性。

2 货架选择问题的优化模型

考虑一个具有R个货架、N种商品和一个拣选台的电商仓储系统。订单对商品i的需求量为qi(i=1,2
，…
，N）
，货架r(r=1,2
，…
，R）中商品i的库存为Sir�；跫苎≡裎侍饧词侨范ㄊ褂媚男┗跫艿目獯胬绰愣┑バ枨�。代表货架是否会被选择的决策变量xr是0-1变量。提出如下两点合理的假设：

1）假设保存一个确定的订单
，即在对该订单进行处理的历程中不会有新的订单加入
，因此该模型是针对静态货架选择问题建立的；

2）从任意货架中取出的商品数目必须为整数
，这切合仓储系统的运行纪律。

因此建立如下电商仓储系统货架选择问题的优化模型：

式（1）为货架选择问题优化模型的目标函数。目标函数是最小化货架被使用次数
，差别于以往的研究经常使用最小化搬运距离或本钱
，本文使用最小化货架被搬运次数作为目标函数的原因有以下三点：

1）货架存放的位置在仓储系统中可能是不牢固的
，难于精确盘算搬运本钱；

2）货架被搬运的次数少
，意味着搬运机械人的任务减少
，以利于减少机械人的路径冲突；

3）货架搬运次数也直接决定了拣选台的事情效率。

式（2）是商品供应约束
，确保了订单中任一种商品需求qi都能被选中的货架库存满足；式（3）排除了不存储任何订单中需求商品种类的货架
，意为当且仅当货架未存储任一种订单需求的商品
，有利于缩小问题规模；式（4）是货架选择问题决策变量xr的0-1约束�；跫苎≡裎侍馐且桓鯪P难问题
，启发式算法常用于求解NP难问题。

3 启发式求解算法

首先界说变量代表货架r满足订单需求的潜能
，即货架能提供订单需求的商品数量越多
，种类越多
，那代表选择该货架更有可能满足订单的需求
，也即该货架的潜能越大。启发式算法求解货架选择问题的办法如下：

Step 1.盘算货架的孝敬度：盘算每个货架的Ir值
，并将货架凭据Ir值由大到小的顺序排序。

Step 2.生成初始解：按Step 1中获得的货架顺序遍历货架
，被遍历的货架r加入荟萃Φ
，如果
，则停止遍历
，Φ即为货架选择问题的初始解。

Step 3.去除冗余货架：凭据Φ中货架的Ir值由小到大地遍历Φ
，关于目今货架r′
，若
，则该货架r′为冗余货架
，从解集Φ中删除。

Step 4.提高解质量：将未被选中的货架r″?Φ按Ir值由大到小的顺序依次加入解荟萃Φ
，每次按Step3盘算能够去除冗余货架的数量。若能够去除的冗余货架的数量大于1
，则从Φ中去除这些冗余货架
，并将目今遍历的货架r″加入解荟萃Φ
，反之货架r″不会加入解荟萃。

以上四步运行完毕后
，获得的荟萃Φ即为货架选择问题的解�
？梢宰⒁獾揭陨习旆ㄖ邪碔r从小到大的顺序删除冗余货架
，按Ir从大到小的顺序在解集中加入新货架
，这是为了保存解集中满足订单潜能较大的货架。

4 数值实验

数值实验将启发式算法与Cplex求解器比照。Cplex求解器是著名的优化求解器
，在线性计划问题的求解上具有较好的求解性能。为了验证启发式算法的效果
，实验接纳文献[3]中提供的实例。表1为较小规模订单的处理
，表2为较大规模订单的处理。Cplex求解器和启发式算法求解后的解均为货架选择问题中需要搬运货架的次数
，盘算时间用T(s）体现
，启发式算法获得的解与Cplex最优解的比照用百分比偏差体现。

比照结果显示
，启发式算法应用在小规模算例和大规模算例中耗时明显比Cplex求解器短；启发式算法在货架选择问题规模较小的情况下可以找到比Cplex更优的解；启发式算法的解与Cplex解的差别最大不凌驾18.75%
，这说明启发式算法能够迅速找到可以接受的次优解。当货架选择问题的订单规模较小时
，启发式算法可以找到比Cplex求解器的解值更优的解
，其中解的百分比偏差为负数。当货架选择问题规模较大时
，如表2的1000种商品和500个货架
，Cplex求解器的盘算时间长达272.42 s
，而启发式算法用时仅需0.152 s
，并且启发式算法的解仅比Cplex求得的最优解多使用了4个货架
，这说明启发式算法对大规模订单下的货架选择问题很有优势。

表1 小规模订单的货架选择问题下启发式算法与Cplex求解器比照  下载原图

表2 大规模订单的货架选择问题下启发式算法与Cplex求解器比照  下载原图

5 结束语

电商仓储系统中的货架选择关于拣选的效率和本钱有着直接的影响。针对电商仓储系统中的货架选择问题
，本文关注货架满足订单的潜能
，并设计了易于实现、庞漂后较低的启发式算法来求解。数值实验证明启发式算法在解决货架选择问题中具有耗时极短、解值质量高的特点。尤其在订单规模较大的情况下
，启发式算法的优点更为突出。