基于约束规划的二维装箱问题模型与算法研究开题报告

1. 研究目的与意义（文献综述）

从20世纪70年代初开始,装箱问题就引起了广泛的探讨和研究。然而装箱问题可以追溯到1831年高斯(gauss)开始研究布局问题，因为装箱问题和布局问题本质上是一样的,到现在已有百余年的历史。虽然经过几代人的努力,但迄今尚无成熟的理论和有效的数值计算方法。由于目前np完全问题不存在有效时间内求得精确解的算法,装箱问题的求解极为困难,因此,从70-80年代开始,陆续提出的装箱算法都是各种近似算法,如下次适应、首次适应、降序下次适应和调和算法等。

装箱问题是复杂的离散组合最优化问题。所谓组合优化,是指在离散的、有限的数学结构上,寻找一个满足给定条件,并使其目标函数值达到最大或最小的解。一般来说,组合优化问题通常带有大量的局部极值点,往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的np完全问题。装箱问题也不例外,同许多组合最优化问题,如旅行商问题、图的划分问题等一样属于np-hard问题。经典的装箱问题要求把一定数量的物品放入容量相同的一些箱子中,使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。

装箱问题广泛存在于工业生产,包括服装行业的面料裁剪、运输行业的集装箱货物装载、加工行业的板材型材下料、印刷行业的排样和现实生活中包装、整理物件等。在计算机科学中,多处理器任务调度、资源分配、文件分配、内存管理等底层操作均是装箱问题的实际应用,甚至还出现在一些棋盘形、方块形的数学智力游戏中。装箱问题的研究文献分布面很广,在运筹学、计算机辅助设计、计算机图形学、人工智能、图像处理、大规模集成电路逻辑布线设计、计算机应用科学等诸多领域都有装箱问题最新的研究动态和成果出现,从这个角度来讲,布局问题涉及到了工业生产的方方面面,也足以证明了装箱问题的应用前景日趋广泛而重要。

2. 研究的基本内容与方案

本次研究的是二维空间中的装箱问题。为了让研究更贴近实际情况，将研究的情形设定为托盘的码放情况，矩形方块就是不同规格的托盘而容器就是货车的装载面积。

首先阅读文献，利用学校图书馆、知网以及其他电子资源数据库，查阅大量文献，对二维装箱问题形成基本的认知并构建一个基本框架，然后对文献中使用的研究思路和方法进行分析研究，归纳总结不同方法的优缺点，并了解各个方法的原理，研究拟采用数学规划法来解决二维装箱问题。接下来配合ilog cp^[2]求解器为研究的二维装箱问题建立模型。模型搭建完成后就是实验计算过程，通过实验得出的结果验证算法是否合理，如果不合理还需对算法进行改进。具体研究按以下内容展开：

1. 文献综述：查找和阅读近5年来国内外研究二维装箱问题算法理论和二维装箱问题在港口决策管理中的应用相关的文献，重点在使用约束规划和精确求解方法的综述，文献数量不少于20篇；

   剩余内容已隐藏，您需要先支付后才能查看该篇文章全部内容！

   3. 研究计划与安排

   第1～3周

   查阅相关文献，完成英文文献翻译，同时构思毕业论文撰写思路。

   第4～5周

   剩余内容已隐藏，您需要先支付后才能查看该篇文章全部内容！

   4. 参考文献（12篇以上）

   [1]two-dimensional packing problems: a survey, andrea lodi, silvanomartello,michele monaci, european journal of operations research 141 (2002) 241-252.

   [2] ilog cp optimizer user manual.

   [3]chapters 1-4, handbook of constraint programming, f. rossi, p. van beek and t. walsh.

   剩余内容已隐藏，您需要先支付 10元 才能查看该篇文章全部内容！立即支付