数学规划法(Mathematieal Programming)

数学规划法包括分枝定界法(Branch一and一boundAlgorithm)、动态规划法(Dynamic programming)、整数规划法(Integer Programming)和线性规划法(Linear programming)等。该方法利用某一优化问题的数学模型,通过修改该模型的精确求解过程得到有效的启发式算法。这四种方法中分枝定界法应用较广泛。该方法的基本思想是试图通过枚举解空间中的有限个解来获得NP完全问题的局部最优解。它由分枝和定界两个操作步骤组成,分枝操作用于将规模较大的原始问题逐步分解为规模较小且易于求解的子问题;而定界操作主要用于评价各分枝的优劣,来减小搜索范围。二维切割问题中,“一刀切”问题是该方法的经典应用,如玻璃切割、纸张裁剪等。

构造法(Construetion Algorithms)

装箱启发式算法中使用最多的方法是构造性算法。构造启发式算法通过一个一个地增加解的构造元素来求得一个可行解。构造性算法的循环次数与问题解的构造元素个数成正比,而与解空间的大小无关,因此其计算速度通常很快。

装箱问题中构造法基本上由两类规则组成。第一类为定序规则(orderingrules),它被用来确定待布局物体放入布局空间的先后顺序:第二类为定位规则(Placement rules),它用来确定每一个布局物体在布局空间摆放的位置。由于定序规则和定位规则的不同,也就产生不同的构造布局方法。常用的定序规则有:

(l)按照待装物体最短边边长递减的顺序进行定序:

(2)按照待装物体最长边边长递减的顺序进行定序;

(3)按照待装物体体积递减的顺序进行定序;

(4)按照待装物体最小面积递减的顺序进行定序;

(5)按照待装物体可行域递减的顺序进行定序:

许多学者对布局问题中定位规则进行了研究,提出了如下一些规则和策略:

(1)占角策略,即将待装物体摆放在布局容器的某一角:

(2)顺放策略,即从布局容器的某一角开始将待装物体沿着容器某一边摆放;

(3)在底盘装载中,将待装物体先沿着边放置,最后摆放到底盘中心;

(4)在三维规则装箱中,从布局容器的某一面墙开始,一层一层地布局;在某一面墙上,再确定一条边,最后归结为一个角:

(5)在三维规则装箱中,先按“右、前、上”的顺序找寻剩余空间,然后按照“左、后、下”的顺序摆待装局物体:

数值优化方法(optimal Algorithms)

数值优化方法具有较为成熟的理论和算法,广泛应用于工程设计领域；取得了许多有效成果,装箱问题是它的一个应用分支,但是数值优化方法依赖于数学模型,且只能找到局部最优解,它只适用于小规模物体的装箱问题。对于规模大的装箱问题用数学模型很难准确描述,即使能用简化的数学模型来描述,由于局部最优解数目的急剧增加,其求解质量也将严重变坏。此外,数值优化方法所得解的质量在很大程度上还依赖于初始解的选择。

现代优化方法

主要有遗传算法(GenetiC Algorithm,GA),模拟退火法(SimulatedAnnealing,SA)两种。其中，遗传算法是一种基于生物学进化原理的搜索算法。在解决高维空间、高复杂及非线性问题的优化中具有全局最优、效率高及易于并行计算等优点,有很强的解决问题的能力,但有着收敛速度慢和易陷入局部最优解的缺点。

由于一般组合优化问题与物质的退火过程具有很大的相似性,因此,模拟退火算法被广泛的用来解决组合优化问题,在这方面已有一些成功的应用实例,模拟退火算法可用来解决连续、离散等优化问题,尤其是解空间状态不良的问题。尽管模拟退火算法是一种有可能得到优化问题的全局最优解的问题求解方法,并且已经逐步成为一种用于优化问题求解的一般、通用的方法,但是这是以极其漫长的退火过程即问题求解过程为代价的。2100433B