求解三维装箱问题的遗传算法研究【毕业论文】.doc

- PAGE I - 本科毕业设计 （20 届） 求解三维装箱问题的遗传算法研究 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 PAGE I 摘　要 【摘要】三维装箱问题是合理地选择需要租用的集装箱并将给定数量的木箱全部装进租用的集装箱中。木箱的装载方案和集装箱的选择方案都会对集装箱的空间利用率及租用的总成本产生很大的影响，所以如何在两方面进行有效的优化，是目前装箱问题上最需关注的话题。本文先对装箱问题及目前的研究现状进行了阐述，然后提出了单箱装箱问题的启发式算法，接着在此基础上，提出了多集装箱装箱问题的遗传算法，最后通过实例证明了该方法能得出该问题的较优解。 【关键词】三维装箱问题；启发式算法；遗传算法。 Abstract 【ABSTRACT】Three-dimensional packing problem is a reasonable choice of container for stuffing a given number of boxes. Wooden boxes loading programs and the options of the container will have a huge effect on the space utilization of container and the total cost of renting. So how to make an effective optimization on the two aspects is the key problem now. The article focuses on packing problems and current research are surveyed in detail. A single box packing heuristic algorithm and a genetic algorithm on multi-container loading problem were proposed. The simulation results show that the proposed algorithms can obtain the optimum solution of the problem. 【KEYWORDS】Three-dimensional Packing Problem；Heuristic；Genetic Algorithm。 目　录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc295632088 摘　要 PAGEREF _Toc295632088 \h II HYPERLINK \l _Toc295632089 Abstract PAGEREF _Toc295632089 \h III HYPERLINK \l _Toc295632090 目　录 PAGEREF _Toc295632090 \h IV HYPERLINK \l _Toc295632091 1 绪论 PAGEREF _Toc295632091 \h 1 HYPERLINK \l _Toc295632092 1.1 装箱问题 PAGEREF _Toc295632092 \h 1 HYPERLINK \l _Toc295632093 1.2 现有装箱问题的解决方法 PAGEREF _Toc295632093 \h 1 HYPERLINK \l _Toc295632094 1.3 课题研究内容 PAGEREF _Toc295632094 \h 2 HYPERLINK \l _Toc295632095 2 面向单箱装箱问题的启发式算法 PAGEREF _Toc295632095 \h 3 HYPERLINK \l _Toc295632096 2.1 单箱装箱要求 PAGEREF _Toc295632096 \h 3 HYPERLINK \l _Toc295632097 2.2 算法思想 PAGEREF _Toc295632097 \h 3 HYPERLINK \l _Toc295632098 2.2.1 放置点介绍 PAGEREF _Toc295632098 \h 3 HYPERLINK \l _Toc295632099 2.2.2 放置点的合并 PAGEREF _Toc2956