作者: 项溪，柳长春，缪立新-清华大学工业工程系^[1]

摘要

本文研究了Kiva系统中的储位分配及订单分批问题。储位分配模型旨在决定哪些商品放在哪些货架上从而使得商品相似度最大，订单分批模型旨在最小化命中货架个数。为了解决订单分批问题，提出了一个启发式算法，分批策略以最大化订单相似性或最小化订单疏离性为目标，采用VNS(变领域搜索算法)。数值实验证明了算法及模型的有效性。

1.Introduction

介绍了Kiva系统

Kiva系统中一个重要的决策问题就是需要决定哪些商品应该放在哪些货架上才能使得AGV的运行距离最短。由于货架的存储位置是自适应的，决定于货架上商品的种类以及顾客的订单，所以AGV的运行距离很难估计。然而，如果很多顾客同时订购的某些商品放置在同一货架上，那么需要搬运的货架数量会大大降低，也就降低了AGV的运行距离。因此，本文对商品进行分配，使得每个货架上的商品是经常被订购的。混合整数线性规划模型用来解决该问题。因为这是一个策略层面的问题，计算时间不是很重要，因此该模型采用CPLEX求解。为了降低命中货架个数，工人们可以同时拣选多个订单，也就是订单可以被组合成不同的批次，进而工人们按批次订单进行拣选。订单分批问题对时间要求很高，因此提出一个启发式算法进行求解。

2.Related work

For a comprehensive overview of the order batching problem, please refer to the review given by Ma and Zhao (2014).Ma and Zhao (2014) analyzed and summarized the range and idea of order batching by giving a review of the different solution approaches that have been suggested in the literature, and indicating the tendency of future research in order batching.
Ma, T., and P. Zhao. 2014. “A Review of Algorithms for Order Batching Problem in Distribution Center.” In International Conference on Logistics Engineering, Management and Computer Science, 172–175. Atlantis Press. doi:10.2991/lemcs-14.2014.40.

3.Problem description

储位分配问题和订单分批问题分解成两个阶段如图所示:

第一阶段是策略层面的储位分配问题，第二阶段是运作层面的订单分批问题。
假设如下:

• 假设一开始货架均为空且商品不会发生缺货。
• 假设顾客订单所需的商品数量远小于一个货架上能放置该商品的数量。即一个货架能满足一个订单中一个商品的需求。
• 货架一次只能去一个工作站
• 一个货架上能放置的商品种类是有限制的，因为将不同种类的商品在补货时放置在同一货架上是比较困难的。
• 一个商品能被存储到不止一个货架上。
• 一个货架有6层，每层只能存放一种商品。
• 每个商品需要的存储空间已给出，可通过层数估计^[2]。
  图解如下:

一共有4个货架，6种商品，每种商品所需的存储空间分别为6,8,1,4,3,2.

4.Storage assignment probelm for Stage Ⅰ

索引:
$i,j$:商品种类编号，$i,j=1,\cdots,P$
$n$:订单编号，$n=1,\cdots,N$
$m$:货架编号，$m=1,\cdots,M$
参数:

$$\Sigma=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}*(x^{(i)})^T$$

$P$:商品种类总数
$N$:订单总数
$M$:货架总数
$L$:一个货架的层数，本文中$L=6$
$B$:一个货架能够存放商品种类的最大数量
$s_{ij}$:商品$i$ 与商品$j$ 的相似度值，取值范围0-1
$S$:商品相似度矩阵
$D_i$:商品$i$ 需要被分配的层数，$\sum_{i=1}^PD_i=LM$ ^[3]
$s_{ii}$:设为常数1，$i\neq j$ 时:

$$s_{ij}=\frac{\qquad \text{同时包含}i,j\text{的订单个数}}{N}$$

商品相似度矩阵$S$定义为:

$$\begin{bmatrix} s_{11}&s_{12}&\cdots&s_{1p}\\\ s_{21}&s_{22}&\cdots&s_{2p}\\\ \vdots&\vdots&\ddots&\vdots\\\ s_{p1}&s_{p2}&\cdots&s_{pp} \end{bmatrix}$$

$s_{ij}$和$S$能从历史订单数据中得到。
决策变量:

$$x_{im} = \begin{cases} 1, \text{如果商品$i$在货架$m$上} \\\ 0, \text{否则} \end{cases}$$

$y_{im}$:整数变量，商品$i$分配到的在货架$m$上的层数。
目标函数为最大化所有货架上所有商品的相似性:

$$max \sum_i\sum_{j>i}\sum_m\frac{s_{ij}x_{im}x_{jm}}{M} \tag{1}$$

约束为:

$$\sum_i y_{im}=L,\quad \forall m\tag{2}$$ $$\sum_m y_{im}=D_i,\quad \forall i\tag{3}$$ $$y_{im}\leq Lx_{im},\quad \forall i,m\tag{4}$$ $$y_{im}\ge x_{im},\quad \forall i,m\tag{5}$$ $$\sum_i x_{im}\leq B,\quad \forall m\tag{6}$$ $$x_{im}\in \\{0,1\\},y_{im}\ge0,\quad \forall i,m\tag{7}$$

Equation (2) stipulates that L layers in each pod are to be assigned. Equation (3) ensures that the total demand number of layers for product type i is satisfied. Constraint (4) requires that the number of layers that product i occupies in the mth pod is no more than the maximum number of layers in the pod. Constraint (5) indicates that pod m can serve product i only if it is selected to store product i. Constraint (6) states that the number of product types stored in a pod is restricted to no more than B types. Constraint (7) is a basic constraint.

因为目标函数中$x_{im}x_{jm}$是非线性的，需要被线性化改写。令$X_{ijm}=x_{im}x_{jm}\in\\{0,1\\}$，改写如下:

$$max\sum_i\sum_{j>i}\sum_m\frac{s_{ij}X_{ijm}}{M}$$ $$X_{ijm}\leq x_{im},\quad \forall i,j,m$$ $$X_{ijm}\leq x_{jm},\quad \forall i,j,m$$ $$X_{ijm}\ge x_{im}+x_{jm}-1,\quad \forall i,j,m$$

5.Order batching problem for Stage Ⅱ

索引:
$k$:批次序号，$k=1,\cdots,K$
参数:
$K$:批次总数
$E$:一个批次中最多包含的订单个数

$$a_{in}= \begin{cases} 1,&\text{如果订单$n$包含商品$i$} \\\ 0,&\text{否则}\\\ \end{cases}$$ $$x_{im}^*= \begin{cases} 1, \text{如果货架$m$包含商品$i$} \\\ 0, \text{否则}\\\ \end{cases}$$

$x_{im}^*$是StageⅠ的输出
决策变量:

$$z_{nk}= \begin{cases} 1,\text{如果订单$n$被分配到批次$k$} \\\ 0,\text{否则}\\\ \end{cases}$$ $$w_{km}= \begin{cases} 1,\text{如果货架$m$需要搬运至批次$k$} \\\ 0,\text{否则}\\\ \end{cases}$$ $$u_{ik}= \begin{cases} 1,\text{如果批次$k$包含商品$i$} \\\ 0,\text{否则}\\\ \end{cases}$$

目标函数是最小化需要搬运货架个数:

$$max \sum_k\sum_mw_{km} \tag{8}$$

约束条件为:

$$\sum_k z_{nk}=1,\quad \forall n\tag{9}$$ $$\sum_n z_{nk}\leq E,\quad \forall k\tag{10}$$ $$\sum_n a_{in}z_{nk}\leq N*u_{ik},\quad \forall i,k\tag{11}$$ $$\sum_m x_{im}^*w_{km}\ge u_{ik},\quad \forall i,k\tag{12}$$ $$z_{nk},w_{km},u_{ik}\in \\{0,1\\},\quad \forall i,m,n,k\tag{13}$$

Equation (9) ensures that an order must be assigned to one batch. Constraint (10) states that the number of orders assigned to a batch is restricted to a maximum of E orders. Constraint (11)determines which batch contains which product. Constraint (12) indicates that the pods carried to the work station must cover all the products in a batch. Constraint (13) is a basic constraint.

(9)式确保每个订单都会被分配到一个批次。(10)式保证一个批次中订单数量不超过规定的最大数量。(11)式确定哪些批次应该包含哪些商品。(12)式表示搬运至工作站的货架必须能够满足该工作站对应批次的所有商品。(13)式为取值约束。
订单分批问题是运作层面的问题，并已被证明为NP难问题，因此本文提出启发式算法进行求解。

6.Solution approach for StageⅡ

订单分批问题要两个部分，第一部分是生成批次，第二部分是确定需要的货架。Section6.1使用启发式方法生成批次，Section6.2提出算法通过分配正确的货架至每个批次使得所需要的货架最少。

6.1.Generate a batch schedule

该章节旨在生成批次，首先使用Algorithm 1,通过最大化订单关联性或稀疏性来得到初始的分批批次，然后采用Algorithm3 的VNS变领域搜索算法来提升。

6.1.1.Obtain an initial batch schedule

Definition 1(Product correlation matrix($PCM_{p\times p}$))商品关联矩阵
如果商品$i$ 与商品$j$ 存储在同一货架上，则称他们是相关的。
如果商品$i$ 与商品$j$ 相关，则$PCM_{ij}=1$，否则为0。
Definition 2(Order association matrix($AS_{N\times N}$)订单关联矩阵
订单$n$ 与$n’$ 的关联系数由这两个订单中共同存放在同一个货架上的商品对的数量决定。关联系数由两部分组成:1.内部关联系数。2.订单间关联系数
Definition 3(Order alienation matrix($AL_{N\times N}$)订单疏离矩阵
订单$n$ 与$n’$ 的疏离系数由这两个订单中不存放在同一个货架上的商品对的数量决定。疏离系数由两部分组成:1.内部疏离系数。2.订单间疏离系数。

6.1.2.Improve the solution

采用VNS变邻域域搜索算法。
Definiton4 (SwapOrder)交换订单邻域算子
随机选取两个批次，并分别从两个批次中各选一个订单进行交换。如图:

伪代码如图:

局部搜索方法(local search,LS)被重复地用来搜索得到邻域中的局部最优解。而邻域算子则是LS方法的基础。邻域算子可以延伸为本地搜索:SwapOrder-LS,重复执行本地搜索的同时解空间也发生了变化。

6.2.Assigning pods to a batch

确定批次之后需要确定哪些货架需要搬运，这个问题类似于集合覆盖问题

This problemis similar to the set cover problem of Cardinal and Dumeunier (2008).

贪心策略是最简单有效的启发式算法之一，可以用于解决众多组合优化问题。本文设计了一个贪心策略来确定每个批次的初始所需货架然后通过局部搜索来优化。算法如下图:

首先定义两个邻域算子:交换货架及删除货架。
Definition 5(SwapPod)交换货架
交换货架邻域算子:从当前批次对应的初始货架池中任取两个货架，从货架池外的其他货架中任取一个货架进行交换。
Definition 6(DeletePod)删除货架
删除货架邻域算子:从当前批次对应的初始货架池中随机挑选一个货架并移出。
两个算子示意图如下:

6.3.Complexity analysis

7.Computational experiments

7.1.Generate problem examples

由于缺少合适的算例，本文算例采取随机生成的方法。320组数据，由32种x每种10组数据组成。生成规则如下:商品种类($P$),货架数量($M$),订单数量($N$)被设置为:
$P/M/N \in \\{8/5/50,8/5/100,10/6/100\\}$以及
$P/M/N \in \\{40/20/50,40/20/100\\}$
从中等规模到大规模问题。

40种商品，20个货架，100个订单就能叫大规模？？？
货架层数$L$设置为6层，一个货架能最多存放商品的种类设置为$B \in \\{3,4\\}$，一个批次中允许包含的最大订单数量设置为$E \in \\{2,5\\}$。生成20000个历史订单来计算StageⅠ的矩阵$S$。
商品$i$ 所需的层数生成方式:$D_i=KL(p_i/\sum_ip_i),p_i \sim U(30,80)$
订单$n$ 中商品种类生成方式:

$$a_{in}= \begin{cases} 1,& \text{if rand}(0,1)\leq 5\times \frac{p_i}{\sum_ip_i} \\\ 0,& \text{otherwise} \end{cases}$$

数值实验流程示意图:

7.2.Performance analysis on the proposed algorithm

略

8.文章不足分析

• 储位分配模型中该文章认为所有商品能占满所有货架的所有空间是极为不合理的，是对问题的简化。
• 储位分配模型未考虑同一种商品放在同一货架上的情况。
• 商品跟自身的相似度设为1是否合理。
• 文章假设一个货架能够满足货架中商品被一次订购是对货架选择问题的简化。
• 储位分配模型通过CPLEX求解只能解决小规模问题，大规模问题不适用。
• 文章算例设计不具有参考性，相关指标太小，不具有实际意义。
  改进思路：

  设计求解大规模储位分配问题的算法，并需要考虑不同商品所需储位的优化，更改储位分配模型目标为所用货架最少且商品相似度最大。
  

  感想：
  1.模型及算法是关键部分，需要学习CPLEX等求解器的运用。
  2.算例可随机生成，英文期刊注重对算例的分析及模型的敏感性分析，注重对比分析，需要大量的实验数据支撑，可学习本文使用小算例。

1. 清华大学工业工程系管理科学与工程专业运筹与物流管理方向博导，清华-伯克利深圳学院智能交通与物流系统专业博导， ↩
2. 属于人为添加条件。 ↩
3. 极为不合理，仓库中物品不一定正好全部用完所有货架的所有存储空间。 ↩