BFD混合禁忌搜索在一维装箱问题中的应用

发布时间：2025-06-19 02:46

　　 针对经典的一维离线装箱问题,本文首次提出了利用降序最佳适应BFD算法与禁忌搜索算法混合使用来解决此类问题的方法,并用Microsoft Visual C++编程得以实现,详细说明了算法的关键内容与步骤,并通过算例与简单遗传算法和单纯使用禁忌搜索算法解决装箱问题进行了对比,得到以下结论:在求解一维离线装箱问题时,BFD算法与禁忌搜索算法混合使用要比单纯地使用禁忌搜索算法和简单遗传算法效果好,实用价值良好。

【文章页数】：5 页

【部分图文】：

图1(a)某装箱问题的解1

(2)初始解:对于给定的m个物品按重量从大到小进行排序，然后用BFD算法求得初始解，该初始解即为禁忌搜索的初始迭代起点。图1(b)某装箱问题的解2

图1(b)某装箱问题的解2

图1(a)某装箱问题的解1(3)邻域结构:即对m个物品(x[0]～x[m-1])解的序列中2个物品位置的变化，其中规定第一个物品的位置固定不变，在领域的映射为解的2-opt。如图1(a)中的解将x[3]与x[4]位置调换后变成了图1(b)中解的情况，即为一次邻域搜索过程，且规定第....

图2 算例中各物品的重量信息

为了便于说明BFD算法与禁忌搜索算法混合使用的优越性，本文将其与单纯使用禁忌搜索算法和简单遗传算法进行比较，算法由MicrosoftVisualC++编程实现。图3为单纯使用禁忌搜索算法得到的最优装箱方案。图4为BFD算法与禁忌搜索算法混合使用所得到的最优方案。图3单独使用....

图3 单独使用禁忌搜索算法的求解情况

图2算例中各物品的重量信息图4BFD与禁忌搜索混合使用的求解情况

本文编号：4050735