一些三维装箱问题

作者: 胡拉哥 | 来源:发表于2019-10-30 11:37 被阅读0次

一些三维装箱问题
世界级难题：把不同物品装进箱子，如何使箱子表面积最小？
一个三维装箱问题的搜索树算法
深入剖析Java中的装箱和拆箱
装箱问题
装箱问题
开始DOCKER的学习
住人集装箱的基础是怎么牢固的？
三维文件格式知多少 | abc、glTF、fbx、obj、dae
三维实景修饰，看看SVSMeshEditor

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

基本概念

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

判定问题(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$ , 否则返回不存在.

一些三维装箱问题
三维装箱问题在电商业务中有重要应用, 例如订单打包和商品装车. 下面我们列举一些电商业务中可能用到的三维装箱问题....
世界级难题：把不同物品装进箱子，如何使箱子表面积最小？
导读：三维装箱问题是一类经典的组合优化问题，具有巨大的学习研究和实际应用价值。传统的三维装箱问题都是给定了箱子的...
一个三维装箱问题的搜索树算法
三维装箱问题的业务场景可以参考<电商业务中的纸箱推荐问题>. 文中考虑了如下问题. 输入 : 长宽高为的箱子和个...
深入剖析Java中的装箱和拆箱
自动装箱和拆箱问题是Java中一个老生常谈的问题了，今天我们就来一些看一下装箱和拆箱中的若干问题。本文先讲述装箱和...
装箱问题
问题假设有编号分别为0、1、……、n-1的n种物品，体积分别为V0、V1、……、Vn-1。将这n种物品装到容量都...
装箱问题
贪心算法装箱问题问题描述：求解思路：代码实现：
开始DOCKER的学习
因为工作的需要，需要部署一些轻量级的web应用， Docker的思想来源于集装箱，集装箱解决了什么问题？试想...
住人集装箱的基础是怎么牢固的？
住人集装箱房这几年慢慢火起来了，可是客户经常咨询一些问题，下面厂家列举出一些常见问题，告诉大家答案。 1】住人集装...
三维文件格式知多少 | abc、glTF、fbx、obj、dae
三维文件格式三维软件之间互相导入导出一般会涉及到一些格式不兼容的问题，这里就给大家普及一下这些常用的三维文件格式...
三维实景修饰，看看SVSMeshEditor
通常，我们在实景三维建模中通过现有建模软件生成的三维模型由于一些原因会出现瑕疵。大概有以下几种问题： 1.地理条件...