【附代码】【MILP建模】3D装箱问题（3D-Bin Packing Problem）_三维装箱优化算法的数学模型

技术文档

文章目录

相关教程
相关文献
问题描述
建模思路——carton 方向
- 平行轴建模方法（9变量6约束）
- 平行轴建模方法（4变量8约束）
- 枚举建模方法（6变量1约束）
建模思路——carton 位置
- 平行轴建模方法
- 枚举建模方法
Bin长宽一定，求最小高度（Three-dimensional bin packing problem with variable bin height）
- 完整建模
- - 指标集（Indices）
  - 常量（Parameters）
  - 决策变量（Decision variables）
  - 目标函数（Objective function）
  - 约束（constraints）
- 完整建模（少变量版本）
- - 指标集（Indices）
  - 常量（Parameters）
  - 决策变量（Decision variables）
  - 目标函数（Objective function）
  - 约束（constraints）
- 代码

作者：小猪快跑

基础数学&计算数学，从事优化领域7年+，主要研究方向：MIP求解器、整数规划、随机规划、智能优化算法

如有错误，欢迎指正。如有更好的算法，也欢迎交流！！！——@小猪快跑

问题描述

三维装箱问题（3D Bin Packing Problem, 3D-BPP）是一个经典的组合优化问题。它涉及到在有限的三维空间内如何有效地放置不同尺寸的物品，以最大化容器的利用率或最小化所需的容器数量。具体来说，就是将一系列具有不同形状和大小的物品最优地填充到一个或多个容器中，使得容器的空间利用率最大，并且满足所有装载约束条件。

这个问题在物流、制造业、仓储管理等地方有着广泛的应用，例如集装箱装载、货车装载、仓库布局等。解决三维装箱问题通常需要采用高效的算法，因为这是一个NP难问题，意味着随着物品数量和种类的增加，找到精确解的计算复杂度会迅速增长。

常用的算法包括：

启发式算法：如First-Fit（首次适应算法）、Best-Fit（最佳适应算法）、Worst-Fit（最差适应算法）和First-Fit Decreasing（先降序排列再首次适应算法）。
元启发式算法：如遗传算法、模拟退火算法和禁忌搜索算法。
数学规划算法：如整数规划和约束规划。

假设：

carton ：被装入bin中的小纸盒，每个都是规则的长方体，长宽高体积确定，放入bin中必须和坐标轴平行
bin：包含carton的大纸盒，都是规则的长方体

建模思路——carton 方向

【附代码】【MILP建模】3D装箱问题（3D-Bin Packing Problem）_三维装箱优化算法的数学模型

平行轴建模方法（9变量6约束）

对于任意一个 carton，最多有六种不同方向的装箱（如上图）。我们希望通过建模表示实际X、Y、Z轴 carton 的边长分别是多少。

$(l, w, h)$ ：carton的长、宽、高
$X_l,Y_l,Z_l)$ ：carton的长是否平行于X、Y、Z轴
$X_w,Y_w,Z_w)$ ：carton的宽是否平行于X、Y、Z轴
$X_h,Y_h,Z_h)$ ：carton的高是否平行于X、Y、Z轴

于是我们有

X轴 Y轴 Z轴

X_l

X_w

X_h

Y_l

Y_w

Y_h

Z_l

Z_w

Z_h

l w h 1 0 0 0 1 0 0 0 1 l h w 1 0 0 0 0 1 0 1 0 w l h 0 1 0 1 0 0 0 0 1 w h l 0 1 0 0 0 1 1 0 0 h l w 0 0 1 1 0 0 0 1 0 h w l 0 0 1 0 1 0 1 0 0

我们很容易就写出他们的约束：

$\\begin{cases} X_l + X_w + X_h = 1 \\\\ Y_l + Y_w + Y_h = 1 \\\\ Z_l + Z_w + Z_h = 1 \\end{cases}$

$\\begin{cases} X_l + Y_l + Z_l = 1 \\\\ X_w + Y_w + Z_w = 1 \\\\ X_h + Y_h + Z_h = 1 \\end{cases}$

这种建模一共有 9 个变量，6 个约束。

平行轴建模方法（4变量8约束）

如果在上述建模方法求解过程中变量太多成为瓶颈，那我们可以通过等价变换让变量少一些。至少需要 $9 - 6 + 1 = 4$ 个变量。

不妨设 4 个变量为 $X_l,Y_w,Z_h,Z_l$ 。我们给出一个很简单的推导过程：
$\\begin{cases} \\textbf X_l + X_w + X_h = 1 \\\\ Y_l + \\textbf Y_w + Y_h = 1 \\\\ \\textbf Z_l + Z_w + \\textbf Z_h = 1 \\\\ \\textbf X_l + Y_l + \\textbf Z_l = 1 \\\\ X_w + \\textbf Y_w + Z_w = 1 \\\\ X_h + Y_h + \\textbf Z_h = 1 \\\\ \\end{cases} \\Rightarrow \\begin{cases} \\textbf X_l + X_w + X_h = 1 \\\\ \\textbf Y_l + \\textbf Y_w + Y_h = 1 \\\\ \\textbf Z_l + \\textbf Z_w + \\textbf Z_h = 1 \\\\ \\textbf X_l + \\textbf Y_l + \\textbf Z_l = 1 \\\\ X_w + \\textbf Y_w + \\textbf Z_w = 1 \\\\ X_h + Y_h + \\textbf Z_h = 1 \\\\ \\end{cases} \\Rightarrow \\begin{cases} \\textbf X_l + \\textbf X_w + X_h = 1 \\\\ \\textbf Y_l + \\textbf Y_w + \\textbf Y_h = 1 \\\\ \\textbf Z_l + \\textbf Z_w + \\textbf Z_h = 1 \\\\ \\textbf X_l + \\textbf Y_l + \\textbf Z_l = 1 \\\\ \\textbf X_w + \\textbf Y_w + \\textbf Z_w = 1 \\\\ X_h + \\textbf Y_h + \\textbf Z_h = 1 \\\\ \\end{cases} \\Rightarrow \\begin{cases} \\textbf X_l + \\textbf X_w + \\textbf X_h = 1 \\\\ \\textbf Y_l + \\textbf Y_w + \\textbf Y_h = 1 \\\\ \\textbf Z_l + \\textbf Z_w + \\textbf Z_h = 1 \\\\ \\textbf X_l + \\textbf Y_l + \\textbf Z_l = 1 \\\\ \\textbf X_w + \\textbf Y_w + \\textbf Z_w = 1 \\\\ \\textbf X_h + \\textbf Y_h + \\textbf Z_h = 1 \\\\ \\end{cases}$
于是我们有
$\\begin{cases} Z_w = 1 - Z_l - Z_h \\\\ Y_l = 1 - X_l - Z_l \\\\ Y_h = X_l -Y_w + Z_l \\\\ X_w = -Y_w + Z_l + Z_h \\\\ X_h = 1 - X_l + Y_w - Z_l - Z_h \\end{cases}$
上面的变量都是 0-1 变量，所以我们增加约束如下：
$\\begin{aligned} &Z_l+Z_h\\leqslant 1\\\\ &X_l+Z_l\\leqslant 1 \\\\ &X_l -Y_w + Z_l\\leqslant 1\\\\ &-X_l +Y_w - Z_l\\leqslant 0 \\\\ &-Y_w + Z_l + Z_h\\leqslant 1\\\\ &Y_w - Z_l - Z_h\\leqslant 0\\\\ &- X_l + Y_w - Z_l - Z_h\\leqslant 0\\\\ &X_l - Y_w + Z_l + Z_h\\leqslant 1 \\end{aligned}$
这种建模一共有 4 个变量，8 个约束。（但如果求LP的解不一定快，因为增加了自由变量后等价于之前的建模）

枚举建模方法（6变量1约束）

对于任意一个 carton，最多有六种不同方向的装箱。我们希望通过建模表示实际X、Y、Z轴 carton 的边长分别是多少。

$(l, w, h)$ ：carton的长、宽、高
$(l\', w\', h\')$ ：carton的在 X、Y、Z轴边长分别是多少
$\\delta_{i}$ ：0-1变量，代表 carton 方向

$\\begin{cases} \\delta_1+\\delta_2+\\delta_3+\\delta_4+\\delta_5+\\delta_6=1 \\\\ l\'=\\delta_1l+\\delta_2l+\\delta_3w+\\delta_4w+\\delta_5h+\\delta_6h \\\\ w\'=\\delta_1w+\\delta_2h+\\delta_3l+\\delta_4h+\\delta_5l+\\delta_6w \\\\ h\'=\\delta_1h+\\delta_2w+\\delta_3h+\\delta_4l+\\delta_5w+\\delta_6l \\end{cases}$

建模思路——carton 位置

【附代码】【MILP建模】3D装箱问题（3D-Bin Packing Problem）_三维装箱优化算法的数学模型

平行轴建模方法

$l_i,w_i,h_i)$ ：carton $i$ 的长、宽、高
$(L, W, H)$ ：Bin的长、宽、高
$x_i,y_i,z_i)$ ：连续决策变量，carton $i$ 的左下后方点的坐标
$X_{l_i},Y_{l_i},Z_{l_i})$ ：布尔决策变量，分别表示 carton $i$ 的长是否平行于 bin 的 X、Y、Z轴
$X_{w_i},Y_{w_i},Z_{w_i})$ ：布尔决策变量，分别表示 carton $i$ 的宽是否平行于 bin 的 X、Y、Z轴
$X_{h_i},Y_{h_i},Z_{h_i})$ ：布尔决策变量，分别表示 carton $i$ 的高是否平行于 bin 的 X、Y、Z轴
$a_{ij},b_{ij},c_{ij}$ ：布尔变量，分别表示 carton $i$ 和 carton $j$ 的相对位置：若 $i$ 在 $j$ 的前面（X轴），右面（Y轴），上面（Z轴），则为1，否则为0
$M$ ：足够大的常数

carton 不重叠
$\\begin{cases} x_i + l_i X_{l_i} + w_i X_{w_i} + h_i X_{h_i} \\leqslant x_j + M(1 - a_{ij}) ,\\quad i\\neq j \\\\ y_i + l_i Y_{l_i} + w_i Y_{w_i} + h_i Y_{h_i} \\leqslant y_j + M(1 - b_{ij}) ,\\quad i\\neq j \\\\ z_i + l_i Z_{l_i} + w_i Z_{w_i} + h_i Z_{h_i} \\leqslant z_j + M(1 - c_{ij}) ,\\quad i\\neq j \\end{cases}$

carton 都在 bin 中
$\\begin{cases} x_i + l_i X_{l_i} + w_i X_{w_i} + h_i X_{h_i} \\leqslant L \\\\ y_i + l_i Y_{l_i} + w_i Y_{w_i} + h_i Y_{h_i} \\leqslant W \\\\ z_i + l_i Z_{l_i} + w_i Z_{w_i} + h_i Z_{h_i} \\leqslant H \\end{cases}$
carton 相对位置限制
$a_{ij}+a_{ji}+b_{ij}+b_{ji}+c_{ij}+c_{ji}\\geqslant1,\\quad i\\neq j$

枚举建模方法

$l_i,w_i,h_i)$ ：carton $i$ 的长、宽、高
$l_i\', w_i\', h_i\')$ ：carton $i$ 在 X、Y、Z轴边长分别是多少
$\\delta_{i1},\\delta_{i2},\\delta_{i3},\\delta_{i4},\\delta_{i5},\\delta_{i6}$ ：0-1变量，代表 carton $i$ 方向
$(L, W, H)$ ：Bin的长、宽、高
$x_i,y_i,z_i)$ ：连续决策变量，carton $i$ 的左下后方点的坐标
$a_{ij},b_{ij},c_{ij}$ ：布尔变量，分别表示 carton $i$ 和 carton $j$ 的相对位置：若 $i$ 在 $j$ 的前面（X轴），右面（Y轴），上面（Z轴），则为1，否则为0

carton 不重叠
$\\begin{cases} x_i + l_i\' \\leqslant x_j + L(1 - a_{ij}) ,\\quad i\\neq j \\\\ y_i + w_i\' \\leqslant y_j + W(1 - b_{ij}) ,\\quad i\\neq j \\\\ z_i + h_i\' \\leqslant z_j + H(1 - c_{ij}) ,\\quad i\\neq j \\\\ \\end{cases}$

carton 都在 bin 中
$\\begin{cases} x_i + l_i\' \\leqslant L \\\\ y_i + w_i\' \\leqslant W \\\\ z_i + h_i\' \\leqslant H \\\\ \\end{cases}$
carton 相对位置限制
$a_{ij}+a_{ji}+b_{ij}+b_{ji}+c_{ij}+c_{ji}\\geqslant1,\\quad i\\neq j$

Bin长宽一定，求最小高度（Three-dimensional bin packing problem with variable bin height）

完整建模

指标集（Indices）

$\\in I$ ：carton 的指标集

常量（Parameters）

$l_i,w_i,h_i)$ ：每个carton的长、宽、高
$M$ ：足够大的常数
$(L, W)$ ：Bin的长、宽

决策变量（Decision variables）

$x_i,y_i,z_i)$ ：连续决策变量，carton $i$ 的左下后方点的坐标
$X_{l_i},Y_{l_i},Z_{l_i})$ ：布尔决策变量，分别表示 carton $i$ 的长是否平行于 bin 的 X、Y、Z轴
$X_{w_i},Y_{w_i},Z_{w_i})$ ：布尔决策变量，分别表示 carton $i$ 的宽是否平行于 bin 的 X、Y、Z轴
$X_{h_i},Y_{h_i},Z_{h_i})$ ：布尔决策变量，分别表示 carton $i$ 的高是否平行于 bin 的 X、Y、Z轴
$a_{ij},b_{ij},c_{ij}$ ：布尔变量，分别表示 carton $i$ 和 carton $j$ 的相对位置：若 $i$ 在 $j$ 的前面（X轴），右面（Y轴），上面（Z轴），则为1，否则为0
$\\widetilde{H}$ ：Bin的高

目标函数（Objective function）

$\\mathrm{min} \\quad \\widetilde{H}$

约束（constraints）

carton 方向
$\\begin{cases} X_{l_i} + X_{w_i} + X_{h_i} = 1 \\\\ Y_{l_i} + Y_{w_i} + Y_{h_i} = 1 \\\\ Z_{l_i} + Z_{w_i} + Z_{h_i} = 1 \\end{cases}$

$\\begin{cases} X_{l_i} + Y_{l_i} + Z_{l_i} = 1 \\\\ X_{w_i} + Y_{w_i} + Z_{w_i} = 1 \\\\ X_{h_i} + Y_{h_i} + Z_{h_i} = 1 \\end{cases}$

carton 都在 bin 中
$\\begin{cases} x_i + l_i X_{l_i} + w_i X_{w_i} + h_i X_{h_i} \\leqslant L \\\\ y_i + l_i Y_{l_i} + w_i Y_{w_i} + h_i Y_{h_i} \\leqslant W \\\\ z_i + l_i Z_{l_i} + w_i Z_{w_i} + h_i Z_{h_i} \\leqslant \\widetilde{H} \\\\ \\end{cases}$
carton 相对位置限制
$a_{ij}+a_{ji}+b_{ij}+b_{ji}+c_{ij}+c_{ji}\\geqslant1,\\quad i\\neq j$

完整建模（少变量版本）

指标集（Indices）

$\\in I$ ：carton 的指标集

常量（Parameters）

$l_i,w_i,h_i)$ ：每个carton的长、宽、高
$M$ ：足够大的常数
$(L, W)$ ：Bin的长、宽

决策变量（Decision variables）

$x_i,y_i,z_i)$ ：连续决策变量，carton $i$ 的左下后方点的坐标
$X_{l_i},Z_{l_i})$ ：布尔决策变量，分别表示 carton $i$ 的长是否平行于 bin 的 X、Z轴
$Y_{w_i}$ ：布尔决策变量，表示 carton $i$ 的宽是否平行于 bin 的 Y轴
$Z_{h_i}$ ：布尔决策变量，表示 carton $i$ 的高是否平行于 bin 的 Z轴
$a_{ij},b_{ij},c_{ij}$ ：布尔变量，分别表示 carton $i$ 和 carton $j$ 的相对位置：若 $i$ 在 $j$ 的前面（X轴），右面（Y轴），上面（Z轴），则为1，否则为0
$\\widetilde{H}$ ：Bin的高

目标函数（Objective function）

$\\mathrm{min} \\quad \\widetilde{H}$

约束（constraints）

carton 方向
$\\begin{aligned} &X_{l_i}+Z_{l_i}\\leqslant1\\\\ &Z_{l_i}+Z_{h_i}\\leqslant1\\\\ &Z_{l_i}-Y_{w_i}+Z_{h_i}\\leqslant1\\\\ &Z_{l_i}-Y_{w_i}+Z_{h_i}\\geqslant0,\\\\ &1-X_{l_i}-Z_{l_i}+Y_{w_i}-Z_{h_i}\\leqslant1\\\\ &1-X_{l_i}-Z_{l_i}+Y_{w_i}-Z_{h_i}\\geqslant0\\\\ &X_{l_i}+Z_{l_i}-Y_{w_i}\\leqslant1\\\\ &X_{l_i}+Z_{l_i}-Y_{w_i}\\geqslant0 \\end{aligned}$
carton 不重叠
$\\begin{cases} x_i+l_iX_{l_i}+w_i(Z_{l_i}-Y_{w_i}+Z_{h_i})+h_i(1-X_{l_i}-Z_{l_i}+Y_{w_i}-Z_{h_i})\\leqslant x_j+M(1-a_{ij}),\\quad i\\neq j\\\\ y_i+w_iY_{w_i}+l_i(1-X_{l_i}-Z_{l_i})+h_i(X_{l_i}+Z_{l_i}-Y_{w_i})\\leqslant y_j+M(1-b_{ij}),\\quad i\\neq j\\\\ z_i+h_iZ_{h_i}+w_i(1-Z_{l_i}-Z_{h_i})+l_iZ_{l_i}\\leqslant z_j+M(1-c_{ij}),\\quad i\\neq j\\\\ \\end{cases}$

carton 都在 bin 中
$\\begin{cases} x_i+l_iX_{l_i}+w_i(Z_{l_i}-Y_{w_i}+Z_{h_i})+h_i(1-X_{l_i}-Z_{l_i}+Y_{w_i}-Z_{h_i})\\leqslant L\\\\ y_i+w_iY_{w_i}+l_i(1-X_{l_i}-Z_{l_i})+h_i(X_{l_i}+Z_{l_i}-Y_{w_i})\\leqslant W\\\\ z_i+h_iZ_{h_i}+w_i(1-Z_{l_i}-Z_{h_i})+l_iZ_{l_i}\\leqslant\\widetilde{H} \\end{cases}$
carton 相对位置限制
$a_{ij}+a_{ji}+b_{ij}+b_{ji}+c_{ij}+c_{ji}\\geqslant1,\\quad i\\neq j$

代码

【附代码】【MILP建模】3D装箱问题（3D-Bin Packing Problem）_三维装箱优化算法的数学模型

枚举方法建模代码如下

import plotly.graph_objects as goimport gurobipy as gpfrom gurobipy import GRB, quicksumdef add_box(fig, x, y, z, dx, dy, dz): \"\"\"向图形添加一个立方体\"\"\" fig.add_trace(go.Mesh3d( x=[x, x + dx, x + dx, x, x, x + dx, x + dx, x], y=[y, y, y + dy, y + dy, y, y, y + dy, y + dy], z=[z, z, z, z, z + dz, z + dz, z + dz, z + dz], i=[7, 0, 0, 0, 4, 4, 6, 6, 4, 0, 3, 2], j=[3, 4, 1, 2, 5, 6, 5, 2, 0, 1, 6, 3], k=[0, 7, 2, 3, 6, 7, 1, 1, 5, 5, 7, 6], opacity=1, flatshading=True, ))class HeightProblemModel: \"\"\" Bin长宽一定，求最小高度（Three-dimensional bin packing problem with variable bin height） 解决的是3D装箱问题的一个变种。不考虑 carton 的重量约束，仅仅考虑长宽高，方向可变，使得能装进尽可能多的东西。 - carton ：被装入bin中的小纸盒，每个都是规则的长方体，长宽高体积确定，放入bin中必须和坐标轴平行 - bin： 包含carton的大纸盒，模型中假设底面积不变，高度是随着放入carton数量而变化的 \"\"\" def __init__(self, carton_size, bin_size): \"\"\" carton_size = [ [36, 36, 36], [59, 39, 20], [54, 40, 21], [58, 37, 21], [52, 33, 20], [40, 31, 21], [31, 31, 17], [31, 17, 16], [26, 23, 14], [33, 21, 4], ] bin_size = [80, 58,100] Args: carton_size: 纸箱的长宽高 bin_size: 纸盒尺寸 \"\"\" self.L = bin_size[0] self.W = bin_size[1] self.H = bin_size[2] # 纸盒最大高度 self.l = [i[0] for i in carton_size] self.w = [i[1] for i in carton_size] self.h = [i[2] for i in carton_size] self.l2 = {} self.w2 = {} self.h2 = {} self.sigma = {} self.x = None self.y = None self.z = None self.m = None self.c = None self.b = None self.a = None def create_solver(self, params: dict = None): self.m = gp.Model(\"Bin Packing - Height Problem\") if params is None: params = {} for param_name, new_val in params.items(): self.m.setParam(param_name, new_val) def add_vars(self): self.x = {} self.y = {} self.z = {} self.a = {} self.b = {} self.c = {} for i in range(len(carton_size)): self.x[i] = self.m.addVar(lb=0, ub=self.L, vtype=GRB.CONTINUOUS, name=\"x(%s)\" % i) self.y[i] = self.m.addVar(lb=0, ub=self.W, vtype=GRB.CONTINUOUS, name=\"y(%s)\" % i) self.z[i] = self.m.addVar(lb=0, ub=self.H, vtype=GRB.CONTINUOUS, name=\"z(%s)\" % i) for j in range(6): self.sigma[i, j] = self.m.addVar(vtype=GRB.BINARY, name=\"x_l(%s)\" % i) \"\"\" l\'=\\delta_1l+\\delta_2l+\\delta_3w+\\delta_4w+\\delta_5h+\\delta_6h w\'=\\delta_1w+\\delta_2h+\\delta_3l+\\delta_4h+\\delta_5l+\\delta_6w h\'=\\delta_1h+\\delta_2w+\\delta_3h+\\delta_4l+\\delta_5w+\\delta_6l \"\"\" self.l2[i] = self.sigma[i, 0] * self.l[i] + self.sigma[i, 1] * self.l[i] + self.sigma[i, 2] * self.w[i] + \\ self.sigma[i, 3] * self.w[i] + self.sigma[i, 4] * self.h[i] + self.sigma[i, 5] * self.h[i] self.w2[i] = self.sigma[i, 0] * self.w[i] + self.sigma[i, 1] * self.h[i] + self.sigma[i, 2] * self.l[i] + \\ self.sigma[i, 3] * self.h[i] + self.sigma[i, 4] * self.l[i] + self.sigma[i, 5] * self.w[i] self.h2[i] = self.sigma[i, 0] * self.h[i] + self.sigma[i, 1] * self.w[i] + self.sigma[i, 2] * self.h[i] + \\ self.sigma[i, 3] * self.l[i] + self.sigma[i, 4] * self.w[i] + self.sigma[i, 5] * self.l[i] for j in range(len(carton_size)): if i == j:  continue self.a[i, j] = self.m.addVar(vtype=GRB.BINARY, name=\"a(%s,%s)\" % (i, j)) self.b[i, j] = self.m.addVar(vtype=GRB.BINARY, name=\"b(%s,%s)\" % (i, j)) self.c[i, j] = self.m.addVar(vtype=GRB.BINARY, name=\"c(%s,%s)\" % (i, j)) self.H = self.m.addVar(lb=0, ub=self.H, vtype=GRB.CONTINUOUS, name=\"H\") def set_obj(self): self.m.setObjective(self.H, GRB.MINIMIZE) def add_carton_direction_cons(self): for i in range(len(carton_size)): self.m.addConstr(quicksum(self.sigma[i, j] for j in range(6)) == 1, \"carton_direction_cons(%s)\" % i) def add_carton_no_overlap_cons(self): for i in range(len(carton_size)): for j in range(len(carton_size)): if i == j:  continue self.m.addConstr(self.x[i] + self.l2[i] <= self.x[j] + self.L * (1 - self.a[i, j]),  \"carton_no_overlap_x_cons(%s,%s)\" % (i, j)) self.m.addConstr(self.y[i] + self.w2[i] <= self.y[j] + self.W * (1 - self.b[i, j]),  \"carton_no_overlap_y_cons(%s,%s)\" % (i, j)) self.m.addConstr(self.z[i] + self.h2[i] <= self.z[j] + self.H * (1 - self.c[i, j]),  \"carton_no_overlap_z_cons(%s,%s)\" % (i, j)) def add_carton_in_bin_cons(self): for i in range(len(carton_size)): for j in range(len(carton_size)): if i == j:  continue self.m.addConstr(self.x[i] + self.l2[i] <= self.L, \"carton_in_bin_x_cons(%s,%s)\" % (i, j)) self.m.addConstr(self.y[i] + self.w2[i] <= self.W, \"carton_in_bin_y_cons(%s,%s)\" % (i, j)) self.m.addConstr(self.z[i] + self.h2[i] <= self.H, \"carton_in_bin_z_cons(%s,%s)\" % (i, j)) def add_carton_limit_cons(self): for i in range(len(carton_size)): for j in range(len(carton_size)): if i == j:  continue self.m.addConstr(  self.a[i, j] + self.a[j, i] + self.b[i, j] + self.b[j, i] + self.c[i, j] + self.c[j, i] >= 1,  \"carton_limit_cons(%s,%s)\" % (i, j)) def add_conss(self): self.add_carton_direction_cons() self.add_carton_no_overlap_cons() self.add_carton_in_bin_cons() self.add_carton_limit_cons() def solve(self): self.m.optimize() return self.get_sol() def get_status(self): if self.m.status == GRB.status.OPTIMAL: return \'OPTIMAL\' elif self.m.status == GRB.status.TIME_LIMIT: return \'TIME_LIMIT\' def get_sol(self): status = self.get_status() gap = self.m.MIPGap lb = self.m.ObjBoundC ub = self.m.ObjVal runtime = self.m.Runtime return {\'gap\': gap, \'status\': status, \'lb\': lb, \'ub\': ub, \'runtime\': runtime} def make_model(self, params: dict = None): self.create_solver(params) self.add_vars() self.add_conss() self.set_obj() def plot(self): fig = go.Figure() for i in range(len(carton_size)): add_box( fig, self.x[i].X, self.y[i].X, self.z[i].X, self.sigma[i, 0].X * self.l[i] + self.sigma[i, 1].X * self.l[i] + self.sigma[i, 2].X * self.w[i] + \\ self.sigma[i, 3].X * self.w[i] + self.sigma[i, 4].X * self.h[i] + self.sigma[i, 5].X * self.h[i], self.sigma[i, 0].X * self.w[i] + self.sigma[i, 1].X * self.h[i] + self.sigma[i, 2].X * self.l[i] + \\ self.sigma[i, 3].X * self.h[i] + self.sigma[i, 4].X * self.l[i] + self.sigma[i, 5].X * self.w[i], self.sigma[i, 0].X * self.h[i] + self.sigma[i, 1].X * self.w[i] + self.sigma[i, 2].X * self.h[i] + \\ self.sigma[i, 3].X * self.l[i] + self.sigma[i, 4].X * self.w[i] + self.sigma[i, 5].X * self.l[i], ) fig.update_layout(scene=dict( xaxis_title=\'X\', yaxis_title=\'Y\', zaxis_title=\'Z\', )) fig.show()if __name__ == \'__main__\': carton_size = [ [36, 36, 36], [59, 39, 20], [54, 40, 21], [58, 37, 21], [52, 33, 20], [40, 31, 21], [31, 31, 17], [31, 17, 16], [26, 23, 14], [33, 21, 4], ] bin_size = [80, 58, 200] model = HeightProblemModel(carton_size, bin_size) model.make_model() print(model.solve()) model.plot()

【附代码】【MILP建模】3D装箱问题（3D-Bin Packing Problem）_三维装箱优化算法的数学模型

文章目录

相关教程

相关文献

问题描述