电商业务中的纸箱推荐问题

背景

在电商业务中, 一个核心的生产环节是打包: 把用户购买的商品打包装入纸箱.

纸箱成本一般与纸板面积成正比. 为了节约打包成本, 我们希望从候选纸箱中选择最小的纸箱来装用户购买的商品. 在实际操作中, 工人一般倾向于选择较大的纸箱, 不仅能减少选择纸箱的时间, 而且能降低装箱难度, 从而加快生产效率. 但这样做会显著增加生产成本.

能不能利用算法来告诉工人如何选择纸箱, 从而节约纸箱成本?

装箱问题

从算法角度解决上述问题有如下难点:

1. 商品的形状不规则. 有些商品没有外包装, 例如啤酒瓶是圆柱状, 而垃圾桶是中空的.
2. 商品的材质软硬不同. 毛巾, 衣服等商品可以折叠, 那么如何测量其几何形状? 装箱时是否可以折叠?
3. 商品的摆放方式*. 在业务允许的前提下, 商品可以旋转, 倾斜, 折叠等方式进行摆放.
4. 判定纸箱是否能装下商品. 给定商品信息和纸箱三维长度, 如何判定商品能否装下?

因此, 需要把问题适当简化. 我们做如下假设:

1. 把每个商品看成长方体, 并测量其长宽高.
2. 不考虑可以折叠和中空的商品.
3. 所有商品能够以90°旋转.

剩下的问题是如何用算法来判定给定的商品是否能装入给定的纸箱. (如果这个问题得到解决, 我们就可以对每个纸箱求解一次该问题, 从而选择能装下所有商品的最小箱子.)

---

装箱问题

• 输入: 给定$n$n个商品和一个纸箱, 商品的长宽高为$(l_i, w_i, h_i)$(li​,wi​,hi​), $i=1,2,\ldots,n$i=1,2,…,n, 纸箱的长宽高为$(L, W, H)$(L,W,H). 假设商品是长方体, 长度不可变(没有弹性). 装箱时可以对商品进行90度旋转, 但不能倾斜.
• 输出: 判断所有商品是否能装入纸箱.

---

从计算复杂性的角度来, 该问题属于NP-complete¹. 在NP$\neq$​= P的假设下², 该问题不能在多项式时间内求解. 换句话说, 我们找不到"又快又好"的算法求解该问题. 在实际中, 我们经常采用效率换质量的策略来求解这一类问题. 即, 允许算法不是最优解, 但要求在可以接受的时间内返回可行解(feasible solution).

这样一来可能出现算法推荐不正确的问题:

1. 推大用小. 算法推荐的纸箱比工人实际使用的纸箱大. 在这种情况下, 工人的操作会比算法推荐更节约成本.
2. 推小用大. 算法推荐的纸箱比工人实际使用的纸箱小. 在这种情况下, 工人的操作会失败, 不仅会误导工人, 而且降低生产效率.

因此, 算法要避免产生推小用大的错误. 换句话说, 算法推荐的纸箱一定要能装下所有商品.

启发式算法

比较容易想到的是设计一些装箱的规则, 例如最大体积优先, 最大面积优先等, 其缺点是我们无法保证得到最优解. 我们以二维装箱为例, 下图的例子考虑5个商品, 方块中的数字代表长$\times$×宽, 箱子的大小为$8\times 4$8×4. 最大面积优先和最长边优先的装箱策略均无法得到最优解.

整数线性规划

下面介绍一种求最优解的方法. 基本思想是把该问题用数学语言来描述, 从而建立优化目标和不等式组. 利用数学规划求解器来解对应的数学问题, 从而得到最优解. 难点在于如何建立该问题的数学模型³.

1. 下标

为方便描述, 我们用下标$i, j$i,j代表商品, $k$k代表商品摆放方式.

• $i, j \in \{1, 2, \ldots, n\}$i,j∈{1,2,…,n} – 商品
• $k \in \{1, 2, \ldots, 6 \}$k∈{1,2,…,6} – 商品的摆放方式(对应$\sigma_k$σk​)

2. 输入参数

算法的输入称为参数. 该问题的参数如下.

• $n$n – 商品数量
• $L, W, H$L,W,H – 箱子的长宽高
• $l_i, w_i, h_i$li​,wi​,hi​ – 商品$i$i的长宽高

3. 决策变量

我们把算法需要求解的变量称为决策变量. 下面我来定义该问题的决策变量. 给定长方体$(L, W, H)$(L,W,H)(代表商品或纸箱), 我们用如图所示的左手坐标系, 把长方体置于原点(使得长方体中所有点的坐标非负). 因此, 任意一个长方体可以用图中的$a, b$a,b两点来确定位置. 我们把**$a$a点称为长方体的位置**.

定义商品的$a$a点和$b$b点坐标:

• $x_i \in [0, L], y_i \in [0, W], z_i \in [0, H]$xi​∈[0,L],yi​∈[0,W],zi​∈[0,H] – 商品$i$i的位置坐标(即$a$a点坐标)
• $\hat{l}_i \in [0, L], \hat{w}_i \in [0, W], \hat{h}_i \in [0, H]$l^i​∈[0,L],w^i​∈[0,W],h^i​∈[0,H] – 商品$i$i的$b$b点坐标

如图所示, 上述长方体的位置为$(0,0,0)$(0,0,0), $b$b点坐标为$(L, W, H)$(L,W,H). 允许90°旋转的条件下, 它一共有6种摆放方式, 即$(L, W, H)$(L,W,H)的所有置换(Permutation):
$\sigma_1: \quad (L, W, H) \\ \sigma_2: \quad (L, H, W) \\ \sigma_3: \quad (W, L, H) \\ \sigma_4: \quad (W, H, L) \\ \sigma_5: \quad (H, L, W) \\ \sigma_6: \quad (H, W, L)$σ1​:(L,W,H)σ2​:(L,H,W)σ3​:(W,L,H)σ4​:(W,H,L)σ5​:(H,L,W)σ6​:(H,W,L)

$k=1,2,\ldots, 6$k=1,2,…,6表示按上述第$k$k种摆放方式$\sigma_k$σk​. 我们用$\delta_{ik}$δik​来表示商品$i$i是否按照第$k$k种方式摆放.

• $\delta_{ik} \in \{0, 1 \}$δik​∈{0,1} – 商品$i$i按第$k$k种方式摆放.

考虑任意两个商品$i, j$i,j. 它们一共有6种相对位置:

• $a_{ij}$aij​ – $i$i在$j$j的左侧
• $b_{ij}$bij​ – $i$i在$j$j的右侧
• $c_{ij}$cij​ – $i$i在$j$j的后面
• $d_{ij}$dij​ – $i$i在$j$j的前面
• $e_{ij}$eij​ – $i$i在$j$j的下面
• $f_{ij}$fij​ – $i$i在$j$j的上面

• $a_{ij}, b_{ij}, c_{ij}, d_{ij}, e_{ij}, f_{ij} \in \{ 0,1 \}$aij​,bij​,cij​,dij​,eij​,fij​∈{0,1} – 商品$i$i和$j$j的6种位置关系

4. 约束

下面我们建立$(l_i,w_i,h_i)$(li​,wi​,hi​)与$(\hat{l}_i, \hat{w}_i, \hat{h}_i)$(l^i​,w^i​,h^i​)之间的对应关系. 回顾$\delta_{ik}$δik​代表商品$i$i的第$k$k种摆放方式, 我们有
$\hat{l}_i = \delta_{i1}l_i + \delta_{i2}l_i + \delta_{i3}w_i + \delta_{i4}w_i + \delta_{i5}h_i + \delta_{i6}h_i\\ \hat{w}_i = \delta_{i1}w_i + \delta_{i2}h_i + \delta_{i3}l_i + \delta_{i4}h_i + \delta_{i5}l_i + \delta_{i6}w_i\\ \hat{h}_i = \delta_{i1}h_i + \delta_{i2}w_i + \delta_{i3}h_i + \delta_{i4}l_i + \delta_{i5}w_i + \delta_{i6}l_i$l^i​=δi1​li​+δi2​li​+δi3​wi​+δi4​wi​+δi5​hi​+δi6​hi​w^i​=δi1​wi​+δi2​hi​+δi3​li​+δi4​hi​+δi5​li​+δi6​wi​h^i​=δi1​hi​+δi2​wi​+δi3​hi​+δi4​li​+δi5​wi​+δi6​li​
注意到商品$i$i不能同时存在两种摆放方式, 因此
$\sum_{k=1}^6\delta_{ik} = 1.$k=1∑6​δik​=1.

考虑任意两个商品$i,j$i,j, 它们之间有6种位置关系: $i$i在$j$j的左侧, 右侧, 后面, 前面, 下面, 上面. 分别用$a_{ij}, b_{ij}, c_{ij}, d_{ij}, e_{ij}, f_{ij}$aij​,bij​,cij​,dij​,eij​,fij​表示. 回顾商品$i$i的位置坐标为$(x_i,y_i,z_i)$(xi​,yi​,zi​). 以$i$i在$j$j的左侧为例, 即, 当$a_{ij}=1$aij​=1时, 我们有$x_i + \hat{l}_i \leq x_j$xi​+l^i​≤xj​. 如图所示.

类似地, 我们有

• $a_{ij} = 1 \Rightarrow x_i + \hat{l_i} \leq x_j$aij​=1⇒xi​+li​^​≤xj​
• $b_{ij} = 1 \Rightarrow x_j + \hat{l_j} \leq x_i$bij​=1⇒xj​+lj​^​≤xi​
• $c_{ij} = 1 \Rightarrow y_i + \hat{w_i} \leq y_j$cij​=1⇒yi​+wi​^​≤yj​
• $d_{ij} = 1 \Rightarrow y_j + \hat{w_j} \leq y_i$dij​=1⇒yj​+wj​^​≤yi​
• $e_{ij} = 1 \Rightarrow z_i + \hat{h_i} \leq z_j$eij​=1⇒zi​+hi​^​≤zj​
• $f_{ij} = 1 \Rightarrow z_j + \hat{h_j} \leq z_i$fij​=1⇒zj​+hj​^​≤zi​

把上述关系写成不等式, 我们得到

$\begin{aligned} & x_i+\hat{l_i}\le x_j +(1-a_{ij})L \\ & x_j + \hat{l_j}\le x_i +(1-b_{ij})L \\ & y_i +\hat{w_i}\le y_j +(1-c_{ij})W \\ & y_j +\hat{w_j}\le y_i +(1-d_{ij})W \\ & z_i +\hat{h_i}\le z_j + (1-e_{ij})H \\ & z_j +\hat{h_j}\le z_i + (1-f_{ij})H .\\ \end{aligned}$​xi​+li​^​≤xj​+(1−aij​)Lxj​+lj​^​≤xi​+(1−bij​)Lyi​+wi​^​≤yj​+(1−cij​)Wyj​+wj​^​≤yi​+(1−dij​)Wzi​+hi​^​≤zj​+(1−eij​)Hzj​+hj​^​≤zi​+(1−fij​)H.​

在上述6种相对位置中, (左, 右), (前, 后), (上, 下)每一对关系不能同时存在, 因此
$\begin{aligned} & a_{ij} + b_{ij} \leq 1\\ & c_{ij} + d_{ij} \leq 1\\ & e_{ij} + f_{ij} \leq 1. \end{aligned}$​aij​+bij​≤1cij​+dij​≤1eij​+fij​≤1.​
但是, 这6种相对位置至少有一种必须存在. 我们有
$a_{ij} + b_{ij} + c_{ij} + d_{ij} + e_{ij} + f_{ij} \geq 1.$aij​+bij​+cij​+dij​+eij​+fij​≥1.

已知商品$i$i的位置是$(x_i, y_i, z_i)$(xi​,yi​,zi​), 它的$b$b点坐标为
$(x_i+\hat{l}_i, y_i+\hat{w}_i, z_i + \hat{z}_i).$(xi​+l^i​,yi​+w^i​,zi​+z^i​).
由于装入纸箱的商品不能超过纸箱的长宽高, 因此
$\begin{aligned} & x_i + \hat{l}_i \leq L\\ & y_i + \hat{w}_i \leq W\\ & z_i + \hat{h}_i \leq H . \end{aligned}$​xi​+l^i​≤Lyi​+w^i​≤Wzi​+h^i​≤H.​

5. 数学模型

综上所述, 我们得到如下的数学规划问题.
$\begin{aligned} \min\ & 0 \\ \text{s.t. } &a_{ij}+b_{ij}\le 1, \quad \forall i<j \\ &c_{ij}+d_{ij}\le 1, \quad \forall i<j\\ &e_{ij}+f_{ij}\le 1, \quad \forall i<j \\ &a_{ij}+b_{ij}+c_{ij}+d_{ij}+e_{ij}+f_{ij}\ge 1, \quad \forall i<j\\ &\sum_{k=1}^6\delta_{ik}=1,\quad \forall i\\ &\hat{l}_i = \delta_{i1}l_i +\delta_{i2}l_i +\delta_{i3}w_i +\delta_{i4}w_i +\delta_{i5}h_i +\delta_{i6}h_i, \quad \forall i\\ &\hat{w}_i = \delta_{i1}w_i +\delta_{i2}h_i +\delta_{i3}l_i +\delta_{i4}h_i +\delta_{i5}l_i +\delta_{i6}w_i, \quad \forall i\\ &\hat{h}_i = \delta_{i1}h_i +\delta_{i2}w_i +\delta_{i3}h_i +\delta_{i4}l_i +\delta_{i5}w_i +\delta_{i6}l_i, \quad \forall i\\ & x_i+\hat{l}_i\le x_j +(1-a_{ij})L, \quad \forall i<j\\ & x_j + \hat{l}_j\le x_i +(1-b_{ij})L, \quad \forall i<j\\ & y_i +\hat{w}_i\le y_j +(1-c_{ij})W, \quad \forall i<j\\ & y_j +\hat{w}_j\le y_i +(1-d_{ij})W, \quad \forall i<j\\ & z_i +\hat{h}_i\le z_j + (1-e_{ij})H, \quad \forall i<j\\ & z_j +\hat{h}_j\le z_i + (1-f_{ij})H, \quad \forall i<j\\ & x_i+\hat{l}_i\le L, \quad \forall i\\ & y_i+\hat{w}_i\le W, \quad \forall i\\ & z_i+\hat{h}_i\le H, \quad \forall i\\ & \delta_{ik},a_{ij},b_{ij},c_{ij},d_{ij},e_{ij},f_{ij}\in \{0,1\}, \quad \forall i < j, \forall k\\ & x_i,y_i,z_i\ge 0, \quad \forall i \end{aligned}$min s.t. ​0aij​+bij​≤1,∀i<jcij​+dij​≤1,∀i<jeij​+fij​≤1,∀i<jaij​+bij​+cij​+dij​+eij​+fij​≥1,∀i<jk=1∑6​δik​=1,∀il^i​=δi1​li​+δi2​li​+δi3​wi​+δi4​wi​+δi5​hi​+δi6​hi​,∀iw^i​=δi1​wi​+δi2​hi​+δi3​li​+δi4​hi​+δi5​li​+δi6​wi​,∀ih^i​=δi1​hi​+δi2​wi​+δi3​hi​+δi4​li​+δi5​wi​+δi6​li​,∀ixi​+l^i​≤xj​+(1−aij​)L,∀i<jxj​+l^j​≤xi​+(1−bij​)L,∀i<jyi​+w^i​≤yj​+(1−cij​)W,∀i<jyj​+w^j​≤yi​+(1−dij​)W,∀i<jzi​+h^i​≤zj​+(1−eij​)H,∀i<jzj​+h^j​≤zi​+(1−fij​)H,∀i<jxi​+l^i​≤L,∀iyi​+w^i​≤W,∀izi​+h^i​≤H,∀iδik​,aij​,bij​,cij​,dij​,eij​,fij​∈{0,1},∀i<j,∀kxi​,yi​,zi​≥0,∀i​

利用开源工具OR-Tools或商用求解器(例如Gurobi)求解上述问题, 如果有可行解则表示纸箱能装入所有商品.

Remark 该精确算法的计算时间随商品数量成指数增长. 因此仅限于求解小规模问题, 例如商品数量限定在10个以内. 在实际应用中, 小规模问题我们可以使用精确算法, 而大规模问题可以考虑启发式算法.

参考文献

---

1. https://en.wikipedia.org/wiki/NP-completeness ↩︎

2. https://en.wikipedia.org/wiki/P_versus_NP_problem ↩︎

3. Chen C S, Lee S M, Shen Q S. An analytical model for the container loading problem[J]. European Journal of Operational Research, 1995, 80(1): 68-76. ↩︎