C# 装箱问题 - 切割库存求解器

• 下载 DriverExampleOriginal.rar
• 下载 DriverExampleMinRejects.rar
• 下载 BinPacking_CuttingStockSolver.rar

 

引言

本文的初衷是为了解决两个著名的运筹学问题：具有多种箱子/库存尺寸的装箱问题和裁剪库存问题。尽管这项工作仅限于一维问题，但所介绍的方法可以用于解决二维和三维问题。这项工作还包括一些有用的功能，例如在搜索解决方案时考虑成本和数量限制的可能性。最后，秉承CodeProject的精神，还增加了两个非设计时功能：最小废料限制，以及通过进行“局部移动”来改进解决方案的方法——请参阅下面的“历史记录”部分以及相关的“评论和讨论”部分。

 

背景

在装箱问题中，一组物品必须被装入特定尺寸（箱子容量）的箱子中：目标是最小化箱子的总数。

在裁剪库存问题中，一组物品必须从特定尺寸（库存长度）的库存中裁剪出来：目标是最小化库存的总数。

过去，研究人员开发了许多不同的方法来解决这两个非常有趣且实用的问题，包括线性规划、启发式算法和进化算法，如遗传算法和蚁群优化系统[1, 2, 3, 4, 5]。众所周知，在运筹学中，只有小型问题才能被穷尽地研究以找到“绝对最优”解，因此任何求解器的尝试都旨在找到一个更通用的“最优解”，而这仅仅有时才是“绝对最优”。

为了使问题复杂化，应该注意到在实践中，经常会遇到具有多种尺寸箱子或多种长度库存的问题。这会导致问题规模呈指数级增长。
从给定的定义可以清楚地看出，装箱问题和裁剪库存问题具有共同的性质。本文提出的算法能够同时处理这两种问题。

 

使用应用程序

为了理解这个应用程序的工作原理，我们将跟随一个我从以下来源获得的例子：

https://codeproject.org.cn/Questions/553711/optimizedpluscuttingplussolutionplus-knapsack-2fbi

为了简单起见，我直接在这里写下问题：

引用

您好，

我需要以下解决方案，并且一直在努力解决。我也到处寻找但找不到任何可以使用的东西。也许是我自己没有足够理解我的问题。

我需要能够以编程方式找到切割绳索/管道长度的最佳方法。

这是场景

我目前有以下长度的库存：3 X 4.7m 5 X 7.4m 3 X 11.2m 4 X 9.8m（这是我目前拥有的绳索长度）。

我需要为订单切割以下长度：2 X 3m 4 X 1.2m 1 X 6m 2 X 5.4m

 

该应用程序利用了一个适合方便数据输入的 Windows 窗体。在此示例中，原始问题增加了虚拟的最小废料限制。

 该窗体暴露了两个 DataGridView 及其各自的 BindingNavigators 和一些 Buttons：

• SEARCH，启动当前问题的求解过程
• RESET，清除两个 DataGridView 以设置新问题
• OPEN，加载一个已保存问题的文件
• SAVE，将当前输入数据保存到文件中

还有一个 CheckBox，在研究过程的某个时刻会出现红字，在窗体的最底部有一个 ToolStrip，其中包含一个 ProgressBar 和一个 Label，用于提供有关正在发生的事情的信息。

在窗体的右上角，可以看到一句符合 CodeProject 精神的消息。

用户应在 DataGridViewItems 中插入物品的尺寸和数量。

默认情况下，如果用户没有明确输入，程序将自动考虑为刚插入的物品至少需要 1 件。BindingNavigatorItems 中嵌入的 TextBox 将显示物品的实时总和。

DataGridViewStocks 应填写每种库存的尺寸、成本以及可用件的最大数量（如果有限制）。为了在计算中有效考虑此上限，需要通过 CheckBox 进行确认。这就是为什么可以通过勾选或取消勾选复选框来模拟不同场景。

请注意，算法始终只考虑库存尺寸，这将在查看流程图后变得清晰。

还有一点关于成本。显然，这是库存的成本，但为了进一步分析，该值可以包含其他参数，例如运输成本等。这样，相同尺寸的库存可以以两种不同的成本和最大件数进行评估。

在上面提到的驱动程序示例中，可以在文章顶部下载，没有关于成本的信息，所以我固定了它们以展示可以找到多少结果。

但是，当输入完成后，必须按“SEARCH”按钮，程序将按照以下流程图运行。

 

 

第一步是建立一个快速解决方案，而不考虑成本或可用件的数量限制。
此解决方案的名称为“边界解决方案”，将是任何进一步改进尝试的上界。
第二步是深入寻找更好的解决方案，此时“可选参数”成本和最大件数开始发挥作用。

正如运行应用程序并使用给定输入数据可以看到的，此时我们的驱动程序示例找到了两个解决方案：一个是“最佳成本解决方案”，另一个是“最佳尺寸解决方案”。

现在，如果问题足够小，并且如果尚未达到“绝对最佳尺寸解决方案”（数学意义上的找到的总解决方案尺寸），则会执行进一步搜索。此最后一步的目的是拟合具有最小总和的众多箱子/库存组合之一。不能保证这样的解决方案存在，并且此过程可能耗时。此时，将出现前面提到的带有红色文本“End Search”的 CheckBox，如下面的图片所示。勾选后，搜索算法将停止并立即显示结果。

 

此快照可以了解结果

 

:

顺便说一句，对于驱动程序示例，不存在“绝对最佳尺寸解决方案”。 但是，如果您想看看这种情况发生，可以稍微修改尺寸为 5.4 的物品：将其尺寸更改为 5.8，并只要求 1 件，然后按“SEARCH”等待几秒钟。

 

算法概览

按下“SEARCH” Button 时，将构造一个 CuttingStock 对象，并按照之前的流程图开始求解过程。

边界解决方案是通过利用“贪婪首次适应”算法获得的。简单来说，该算法处理所有物品，并将它们分配给最大的可用箱子/库存。当箱子/库存无法容纳物品时，它会尝试将其分配给第一个可以容纳它的箱子/库存。如果没有箱子/库存有足够的空间，则使用新的箱子/库存。分配程序后，算法会按照以下有序步骤寻求改进：

1. 尝试减小某些箱子/库存的尺寸，如果它的大小小于或等于另一个可用箱子/库存的尺寸。这是通过调用DownSize(列表<Bin> mySolution)方法的新参数。
2. 尝试对解决方案进行“合格”处理：调用QualifySolution(列表<Bin> mySolution)方法，它通过一系列局部移动来探索释放箱子/库存中空间的可能性。下面的简短段落将提供有关此想法的更多详细信息。
3. 再次尝试对解决方案进行 DownSize。

一旦获得边界解决方案，应用程序将利用 BranchAndBound 类构建一组潜在的改进解决方案。该类受到分支定界策略的启发，该策略在运筹学中相当常见，并返回一个潜在的更好解决方案的 List，该列表按成本和尺寸排序，并传递给“贪婪最佳适应”算法，直到找到新的解决方案。此贪婪算法的工作方式类似于“贪婪首次适应”，主要区别在于现在它尝试使用分支定界派生的集合来拟合物品，并且当箱子/库存无法容纳物品时，它会尝试将该物品分配给可以容纳该物品且废料最小的箱子/库存。然而，如果成功运行，它能够返回所谓的“最佳尺寸解决方案”和“最佳成本解决方案”，这两者都已由前面提到的方法处理。QualifySolution(列表<Bin> mySolution)方法的新参数。

此时将执行新的搜索，以仅使用应用于分支定界空间中尺寸等于“绝对最优”值的分支的“贪婪下次适应”算法来实现绝对最佳尺寸。如果“最佳尺寸解决方案”也是“绝对最佳”或者物品太多（设计选择为 12），则不执行此步骤。此贪婪算法是最简单也是最快的：物品被放置在箱子/库存中，直到它足够空，然后添加一个新的箱子/库存。但是，为了确保尝试了 ListOfItems 中物品的所有可能排列以适应给定的箱子/库存集合。这就是我选择对要处理的物品数量设置限制的主要原因。这个看似简单的想法花费了许多行代码，我将代码中的注释保留以更好地阐明概念。

 

什么是合格的解决方案？

根据背景部分中的陈述，装箱问题或裁剪库存问题的目标是最小化原材料（箱子或库存）的数量。如果我们能够达到这个目的，我们可以考虑一个更高级的目标：获得一个允许我们良好地重新利用废料的解决方案。给定一个问题及其解决方案，假设它们具有相同的总箱子/库存尺寸，我们可以将给出仍可用于下一份工作的废料的解决方案视为“更合格”的解决方案。相反，我们可以将废料不可重用且因此完全无用的解决方案视为“不太合格”的解决方案。尽管这个方面似乎很有趣，但我没有在研究领域的工作中找到相关的参考。同样，我也没找到优化“成本”或限制某些库存数量的关注点——这是我在设计时决定在应用程序中设置的两个功能。为了满足“更合格”解决方案的需求，已将专用方法QualifySolution(列表<Bin> mySolution)添加到代码中。此“合格”处理背后的基本计划是通过尝试将物品从一个箱子/库存移动到另一个箱子/库存来释放箱子/库存中的空间：后者是使用“最佳适应”标准选择的，而要移动的物品是从最大到最小选择的，从最后一个箱子/库存反向运行到检查解决方案中的第一个箱子/库存。

 

要求最小废料是个好主意吗？

正如我在引言中所说，本文的主要目的是找到一个良好且可能快速的解决方案来解决传统的装箱/裁剪库存问题，即使对于小集合的箱子/库存和少量物品，其求解时间也可能无法接受。这个概念意味着目标函数是最小化所使用的原材料。因此，我们可以认为所有不增加原材料消耗的想法都是好的选择——无论接下来会发生什么，或者再接下来……“合格解决方案”的“局部移动”就是受这个原则启发。 “最小废料”限制可能导致一个并非最差的解决方案。在这种情况下，这将是我们工作的另一个好的“局部移动”。另一方面，结果可能更糟。在这种情况下，我建议至少将这些结果与排除最小废料获得的结果进行比较。在这里，读者和用户可以积累经验，可能通过“评论和讨论”部分向 CodeProject 社区提供合理的反馈。

 

关注点   

这是我的第一个 C# 应用程序，我必须说，虽然我根本不是软件开发人员，但我遇到了 C# 和 .NET 框架的几个有趣功能，我希望它们对其他初学者有用：

• 使用 DataGridView 控件以及内存中数据结构而不是物理数据库；
• 为 List 集合实现多种排序方法；
• 有用的 Linq 查询以及将查询结果放入单独集合的方法；
• 强大的 BinaryFormatter 和 FileStream 类组合，可以轻松地将许多对象集合存储在一个文件中。

 

参考文献 

[1] P.C. Gilmore, R.E. Gomory. A linear programming approach to the cutting stock problem. Operations Research, 9:848-859, 1961。
[2] Silvano Martello, Paolo Toth. Knapsack Problems, Algorithms and Computer Implementations. John Wiley and Sons Ltd., England, 1990。
[3] Emanuel Falkenauer, Alain Delchambre. A genetic algorithm for bin packing and line balancing. Proceedings of the IEEE 1992 International Conference on Robotics and Automation, Nice, France, May 1992。
[4] Emanuel Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5-30, 1996。
[5] Rhyd Lewis. A General-Purpose Hill-Climbing Method for Order Independent Minimum grouping Problems: A Case Study in Graph Colouring and Bin Packing. Computers and Operations Research, vol. 36(7), pp. 2295-2310。

历史  

• 2014-01-04  
  • 原始文章
• 2014-01-06
  • 修改后的下载部分
• 2014-08-02
  • 由于 2014 年 5 月 25 日的帖子，修改了文章和代码
    • 添加了 QualifySolution 方法
    • 更新了文章