三维装箱问题分类
目录
三维装箱问题在电商业务中有重要应用，例如订单打包和商品装车。下面我们列举一些电商业务中可能用到的三维装箱问题。
基本概念
首先我们把问题分为两类：
- 判定问题 (Decision Problem)：这类问题的答案只有两种：是 或 否。
- 优化问题 (Optimiation Problem)：这类问题一般有一个优化目标，问题的最优解使得目标达到最优。
为了方便描述，我们先介绍一些术语和假设。
物品
物品有两种类型：
普通物品 (Normal 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 \end{aligned} $$
装箱
我们说物品集合 $I$ 能被装入盒子当且仅当：
- $I$ 中所有物品都在盒子的内部；
- $I$ 中任意两个物品不相交。
装袋
我们说物品集合 $I$ 能被装入袋子当且仅当存在一个由袋子形变的盒子能装入 $I$ 中所有物品。
命名规范
命名按照如下方式：
- [问题类型]-[箱子类型]-[箱子数量]-[物品类型]
- 问题类型：O – 优化问题；D – 判定问题
- 箱子类型：A – 盒子；B – 袋子
- 箱子数量：S – 单个箱子；M– 多个箱子
- 物品类型：N – 普通物品；S – 柔性物品
判定问题
DASN
考虑普通物品和单个盒子。
- DASN
已知长宽高为 $(L, W, H)$ 的盒子和 $n$ 个普通物品。物品的长宽高分别是$(l_i, w_i, h_i)$, $i=1, 2, \ldots, n$且允许90度旋转。判断物品是否可以被全部装入盒中。
DASS
考虑柔性物品和单个盒子。
- DASS
已知长宽高为 $(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 度旋转。判断物品是否可以被全部装入盒中。
DBSN
考虑普通物品和单个袋子。
- DBSN
已知长宽为 $(L, W)$ 的袋子和 $n$ 个普通物品。物品的长宽高分别是$(l_i, w_i, h_i)$, $i=1, 2, \ldots, n$且允许90度旋转。判断物品是否可以被全部装入袋中。
DBSS
考虑柔性物品和单个袋子。
- DBSS
已知长宽为 $(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 度旋转。判断物品是否可以被全部装入袋中。
优化问题
OASN
考虑普通物品和单个盒子的装箱。
- OASN
已知 $m$ 个盒子，其长宽高为 $(L_j, W_j, H_j)$，$j=1,2,\ldots,m$；$n$ 个物品，长宽高为 $(l_i, w_i, h_i)$，$i=1, 2, \ldots, n$。物品允许90度旋转。找一个体积最小的盒子使得它能装下所有商品，否则返回不存在。
OASS
考虑柔性物品和单个盒子的装箱。
- OASS
已知 $m$ 个盒子，长宽高为 $(L_j, W_j, H_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度旋转。找一个体积最小的盒子使得它能装下所有物品，否则返回不存在。
OAMN
考虑普通物品和多个盒子的装箱。
- OAMN
已知 $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度旋转。找一些盒子使得它们能装下所有物品，且盒子的总体积最小；否则返回不存在。
OAMS
- OAMS
已知 $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度旋转。找一些盒子使得它们能装下所有柔性物品，且袋子的总面积最小，否则返回不存在。
OBSN
- OBSN
已知 $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度旋转。找一个成本最低的袋子使得它能装下所有物品，否则返回不存在。
OBSS
- OBSS
已知 $m$ 个袋子，长宽为$(L_j, W_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度旋转。找一个面积最小的袋子使得它能装下所有物品，否则返回不存在。
OBMN
- OBMN
已知 $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度旋转。找一些袋子使得它们能装下所有物品，且袋子的总面积不超过 $M$，否则返回不存在。
OBMS
- OBMS
已知 $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 度旋转。找一些袋子使得它们能装下所有柔性物品，且袋子的总体积最小；否则返回不存在。