基于启发式算法的电商仓储货架分配问题研究

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

目前电商仓储常常采用货到人拣货模式。电商仓储系统的货到人拣货模式与传统仓储系统的拣选模式不同：在电商仓储系统的订单拣选过程中，机器人将可移动货架搬运到拣选台，供拣选员拣选订单中需求的商品，订单拣选完毕后，可移动货架被机器人搬运回货架存放区域；而传统仓储系统采用的是固定式货架，需要由拣选人员访问货架来拣选商品。相较于传统的拣选人需要移动收集订单商品的模式，可移动机器人拣货模式更适用于电子商务，具有拣选速度更快、不易漏选和对拣选员更友好的优点^[1]。电商仓储通常基于分散存储策略建立，即一个货架可以存放多种商品，每种商品也被存放在多个货架上。研究表明分散存储策略可以降低货架资源争夺的程度^[2]。分散存储策略意味着有多种货架组合可以满足拣选单的需求。新的货到人拣选模式也给电商仓储系统的拣选带来了新的挑战，选择适当的货架组合直接影响着拣选效率和拣选成本，但货架选择问题相关的研究并不充分。

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

考虑一个具有R个货架、N种商品和一个拣选台的电商仓储系统。订单对商品i的需求量为q_i(i=1,2，…，N），货架r(r=1,2，…，R）中商品i的库存为S_ir。货架选择问题即是确定使用哪些货架的库存来满足订单需求。代表货架是否会被选择的决策变量x_r是0-1变量。提出如下两点合理的假设：

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

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

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

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

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

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

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

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

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

Step 1.计算货架的贡献度：计算每个货架的I_r值，并将货架按照I_r值由大到小的顺序排序。

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

Step 3.去除冗余货架：按照Φ中货架的I_r值由小到大地遍历Φ，对于当前货架r′，若，则该货架r′为冗余货架，从解集Φ中删除。

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

以上四步运行完毕后，得到的集合Φ即为货架选择问题的解。可以注意到以上步骤中按I_r从小到大的顺序删除冗余货架，按I_r从大到小的顺序在解集中加入新货架，这是为了保留解集中满足订单潜能较大的货架。

数值实验将启发式算法与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个货架，这说明启发式算法对大规模订单下的货架选择问题很有优势。

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