Bin Packing Objective function



首先我想澄清英语不是我的母语,所以请耐心等待:)

我正试图解决三维箱子包装问题,只使用一个容器(背包),我有一个关于目标函数公式的问题。我有一个集装箱和一份包裹清单:

集装箱:

  • 宽度
  • 深度
  • 高度
  • 容量
  • 三维矩阵

包装:

  • 宽度
  • 深度
  • 高度
  • 位置(X、Y、Z)
  • 重量
  • 位置系数

每个包裹都有一个位置因子,它告诉我们您想在哪个位置装载包裹,因子范围从1到5,1意味着包裹应该放在容器的前面,5放在容器后面。

现在我的目标函数是最大化集装箱上的空间,具有较大系数的包裹必须在集装箱的后部,具有较低系数的包裹在卡车的前部。

如果我想最大化空间,我只需要最大化所有包裹体积的总和,但我应该将其与目标函数的惩罚相结合,例如,当一个因子为5的包裹位于容器前面的位置时。

我想通过一个排列成一行的相同尺寸的示例包来澄清一些事情

  1. 背面5 1 5 4 4 3 2 2正面
  2. 背面5 5 4 4 3 3 2 1 2正面

在第一个分发包中,您可以看到因子为1的包几乎位于容器的后面,而在第二个分发包,因子为1,包位于应该是(前面),所以第二个分布更好。

问题是数据包大小不同,可以放在任何位置。我希望你能帮我:D!

目标函数的特定形式取决于求解方法。

由于装箱问题是NP难问题,我想你会使用一些启发式方法来解决它。在这种情况下,候选解决方案是由所有具有填充位置(X,Y,Z)属性的包(p)组成的集合。目标函数看起来像:

F({P}) -> int

所以你可以通过包装因子来增加结果的权重:据我所知,最好的布局是从1到5对因子进行排序。它和当前布局之间的差异是你的系数(使用最小二乘法):

ideal:   back 5 5 4 4 4 3 3 2 2 1 front
current: back 5 1 5 4 4 4 3 3 2 2 front 
coefficient: (5-5)^2 + (5-1)^2 + ... + (1-2)^2

相关内容

  • 没有找到相关文章

最新更新