[考虑无效移动次数的订单分批问题研究]

管梦城
想法来源于之前看过的一篇文章面向供应链挖掘 “商品关系链”价值｜大数据与智慧物流（二）。

1.问题描述

kiva system中有$M$ 个货架，$N$ 种商品，共有$O$ 个订单需要拣选，现有仓库物品储位数据，历史订单数据。根据实际情况，需对订单进行分批拣选，每个批次包含的订单总数不得超过$L$，问如何分批才能使得货架无效移动次数最少？

无效移动:搬运一个货架至工作站进行拣选，货架上没有被拣选的商品种类总数分别记录一次无效移动。例:一个货架上有10种商品，搬运该货架至工作站拣选了一种商品，其余9种商品分别记录一次无效移动。

2.模型

Indices   |   
$i$   |   商品索引，$i=1,...,N$
$m$   |   货架索引，$m=1,...,M$
$b$   |   批次索引，$b=1,...,B$
**Parameters**   |   
$M$   |   货架总数
$N$   |   商品总数
$B$   |   批次总数
$L$   |   单个批次最大订单数限制
$O$   |   订单总数
$t_m$   |   货架$m$ 上的商品种类总数
$d_{io}$   |   =1如果订单$o$ 包含商品$i$ ;否则为0
$c_{im}$   |   =1如果货架$m$ 上有商品$i$ ;否则为0

Decision variables

$$x_{bm} = \begin{cases} 1, & \text{如果拣选批次$b$ 需要搬运货架$m$} \\\ 0, & \text{否则} \end{cases}$$ $$h_{im} = \begin{cases} 1, & \text{如果需要从货架$m$ 上拣选商品$i$} \\\ 0,& \text{否则} \end{cases}$$ $$y_{ob} = \begin{cases} 1, & \text{如果订单 $o$被分配到批次$b$} \\\ 0,& \text{否则} \end{cases}$$ $$z_{ib} = \begin{cases} 1, & \text{如果批次$b$ 中包含商品$i$} \\\ 0,& \text{否则} \end{cases}$$

[$p_{bm}$ :拣选批次$b$ 时，货架$m$ 的无效移动次数]
模型:

$$min \quad \sum_{b=1}^B\sum_{m=1}^M (x_{bm}\sum_{i=1}^N (c_{im}-h_{im}))\tag{1}$$ $$\sum_{b=1}^B y_{ob} =1,\qquad \forall \quad o \tag{2}$$ $$\sum_{o=1}^{O} y_{ob} \leq L, \qquad \forall \quad b \tag{3}$$ $$Oz_{ib}\leq \sum_{o=1}^O d_{io}y_{ob},\qquad \forall \quad i,b \tag{4}$$ $$h_{im}\leq c_{im},\qquad \forall \quad i,m\tag{5}$$ $$\sum_{m=1}^{M}x_{bm}c_{im}\geq z_{ib},\qquad \forall \quad b,i\tag{6}$$ $$x_{bm}\geq h_{im},\qquad \forall \quad b,i,m \tag{7}$$ $$x_{bm},h_{im},y_{ob},z_{ib}\in \lbrace0,1\rbrace,\qquad \forall \quad b,i,m,o \tag{8}$$

目标函数为(1)，表示最小化无效移动次数。
约束(2)确保每个订单仅被分配到一个批次；
约束(3)保证每个批次中的订单总数小于阈值$L$;
约束(4)为批次中包含的商品与该批次中所有订单包含的商品之间的关系；
约束(5)表示只有当货架上有商品$i$ 时，才能搬运货架$m$ 并拣选其上的商品$i$；
约束(6)表示拣选批次$b$ 所需搬运的所有货架上包含的商品种类能满足该批次中包含的商品种类；
约束(7)表示只有当货架$m$ 被选中进行拣选时，才能拣选其上的物品；
约束(8)为基本变量约束。

3.算法

初步实现了用模拟退火算法求解，有待优化。

3.1.生成初始解:

(1) 根据余弦相似度计算订单之间的相似度，得到订单-订单相似度矩阵，根据该矩阵成成订单分批初始解。
(2) 或考虑货架上的商品信息，设计新的相似度度量方法，与之前清华论文类似，得到订单-订单相似度矩阵，根据该矩阵成成订单分批初始解。

3.2.优化

采用模拟退火算法进行优化，每个温度下做多次邻域搜索，邻域算子为:交换两个批次中的任意两个订单。

3.3.数值实验

实验数据:50种SKU,21个货架,300个订单

  分批方法    |   订单关联分批   |   随机分批 |    降低百分比
无效移动次数   |   406   |   809   | 49.815%

目标函数迭代情况:

4.可以改进的地方

1.更改订单间相似度度量。
2.加禁忌列表，邻域搜索时避免重复搜索。
2.与CPLEX求解对比，能否用CPLEX求解该模型有待研究。