一些三维装箱问题

三维装箱问题在电商业务中有重要应用, 例如订单打包和商品装车. 下面我们列举一些电商业务中可能用到的三维装箱问题.

基本概念

首先我们把问题分为两类:

判定问题(Decision Problem). 这类问题的答案只有两种: 是或否.
优化问题(Optimiation Problem). 这类问题一般有一个优化目标, 问题的最优解使得目标达到最优.

为了方便描述, 我们先介绍一些术语和假设.

物品

物品有两种类型:

普通物品(Item). 它是长方体且无弹性. 用长宽高来描述普通物品的尺寸.
柔性物品(Soft Item). 它有 $k \geq 1$ 种尺寸, 即 $(l_1, w_1, h_1), (l_2, w_2, h_2), \ldots, (l_k, w_k,h_k)$ . 要求所有尺寸对应的体积相同, 即 $l_iw_ih_i = l_jw_jh_j$ , $\forall i\neq j$ . 普通物品可以看成是只有一种尺寸的柔性物品.

箱子

箱子有两种类型:

盒子(Box). 它是长方体的表面, 且无弹性. 用长宽高来描述盒子的尺寸.
袋子(Bag). 它是高度为零的长方体表面. 用长和宽描述袋子的尺寸. 此外, 袋子是柔软的. 换句话说它可以变形成盒子, 要求其表面积等于袋子的表面积, 且水平和垂直方向的周长不超过袋子在水平和垂直方向上的周长. 设袋子的长和宽分别为 $L$ 和 $W$ , 它变形成的盒子的长宽高分别是 $l,w,h$ . 因此我们要求:
$\begin{aligned} & l + h \leq L\\ & w+ h \leq W \\ & lw + wh +hl = LW \end{aligned}$

装箱

我们说物品集合 $I$ 能被装入盒子当且仅当:

$I$ 中所有物品都在盒子的内部;
$I$ 中任意两个物品不相交.

装袋

我们说物品集合 $I$ 能被装入袋子当且仅当存在一个由袋子形变的盒子能装入 $I$ 中所有物品.

判定问题

3D装盒-单盒 (Three-dimensional box packing with single box)

输入. 长宽高为 $(L, W, H)$ 的盒子和 $n$ 个物品. 物品的长宽高分别是 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ 且允许90度旋转.
问题. 物品是否可以被全部装入盒中?

3D装盒-单盒-柔性物品 (Three-dimensional box packing with single box and soft items)

输入. 长宽高为 $(L, W, H)$ 的盒子和 $n$ 个柔性物品, 其中每个柔性物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ . 允许物品90度旋转.
问题. 柔性物品是否可以被全部装入盒中?

3D装袋-单袋 (Three-dimensional bag packing with single bag)

输入. 长宽为 $(L, W)$ 的袋子; $n$ 个物品, 其长宽高是 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 物品是否可以被全部装入袋中?

3D装袋-单袋-柔性物品 (Three-dimensional bag packing with single bag and soft items)

输入. 长宽为 $(L, W)$ 的袋子; $n$ 个物品, 其中每个物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 柔性物品是否可以被全部装入袋中?

优化问题

3D装盒-单盒 (Three-dimensional box packing with single box)

输入. $m$ 个盒子, 其长宽高为 $(L_j, W_j, H_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个物品, 长宽高为 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 找一个成本最低的盒子使得它能装下所有商品, 否则返回不存在.

3D装盒-单盒-柔性物品 (Three-dimensional box packing with single box and soft items)

输入. $m$ 个盒子, 长宽高为 $(L_j, W_j, H_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个物品, 其中每个物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 找一个成本最低的盒子使得它能装下所有柔性物品, 否则返回不存在.

3D装盒-多盒 (Three-dimensional box packing with mutiple boxes)

输入. $m$ 个盒子, 长宽高为 $(L_j, W_j, H_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个物品, 长宽高为 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ ; 总成本 $M$ . 物品允许90度旋转.
问题找一些盒子使得它们能装下所有物品且总成本不超过 $M$ , 否则返回不存在.

3D装盒-多盒-柔性物品 (Three-dimensional box packing with multiple boxes and soft items)

输入. $m$ 个盒子, 长宽高为 $(L_j, W_j, H_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个柔性物品, 其中每个柔性物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ ; 总成本 $M$ . 物品允许90度旋转.
问题. 找一些盒子使得它们能装下所有柔性物品且总成本不超过 $M$ , 否则返回不存在.

3D装袋-单袋 (Three-dimensional bag packing with single bag)

输入. $m$ 个袋子, 长宽为 $(L_j, W_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个物品, 长宽高为 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 找一个成本最低的袋子使得它能装下所有物品, 否则返回不存在.

3D装袋-单袋-柔性物品 (Three-dimensional bag packing with single bag and soft items)

输入. $m$ 个袋子, 长宽为 $(L_j, W_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个柔性物品, 其中每个物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ . 物品允许90度旋转.
问题. 找一个成本最低的袋子使得它能装下所有物品, 否则返回不存在.

3D装袋-多袋 (Three-dimensional bag packing with multiple bags)

输入. $m$ 个袋子, 长宽为 $(L_j, W_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个物品, 长宽高为 $(l_i, w_i, h_i)$ , $i=1, 2, \ldots, n$ ; 总成本 $M$ . 物品允许90度旋转.
问题. 找一些袋子使得它们能装下所有物品且总成本不超过 $M$ , 否则返回不存在.

3D装袋-多袋-柔性物品 (hree-dimensional bag packing with multiple bags and soft items)

输入. $m$ 个袋子, 长宽为 $(L_j, W_j)$ , 成本为 $c_j$ , $j=1,2,\ldots,m$ ; $n$ 个柔性物品, 其中每个物品 $i$ 有 $k_i$ 种尺寸, 即 $(l_i^1, w_i^1, h_i^1), \ldots, (l_i^{k_i}, w_i^{k_i}, h_i^{k_i})$ , $i=1, 2, \ldots, n$ ; 总成本 $M$ . 物品允许90度旋转.
问题. 找一些袋子使得它们能装下所有柔性物品且总成本不超过 $M$ , 否则返回不存在.