变尺寸装箱问题的迭代/贪婪动态规划算法

针对船舶建造中管材切割规划这一类特殊的变尺寸装箱问题,提出了一种迭代贪婪/动态规划算法(IGDP)并对其进行求解。首先,提出了求解子集和问题的贪婪操作与动态规划的组合解法。然后,基于贪婪操作与动态规划的组合解法实现对整个问题的构造启发式求解,并且通过迭代的拆箱/再分配操作提高了算法的局部搜索能力。最后,通过8个算例的仿真实验,对所提算法与现有算法进行了性能比较。结果表明:IGDP的性能优于现有算法,且具有可以接受的计算耗费。

Iterative/Greedy Dynamic Programming Algorithm for Variable Size Binning Problem

Aiming at the special variable size packing problem of pipe cutting planning in ship construction,an iterative greedy/dynamic programming algorithm(IGDP)is proposed and solved.First,a combined solution of greedy operation and dynamic programming to solve the subset sum problem is proposed.Then,the combined solution method based on greedy operation and dynamic programming realize the constructive heuristic solution to the whole problem.The local search ability of the algorithm is improved through the iterative unboxing/redistribution operation.Finally,through simulation experiments of eight examples,the performance of the proposed algorithm is compared with the existing algorithm.The results show that the performance of IGDP is better than the existing algorithm,and it has an acceptable computational cost.