基于改进遗传算法的集装箱装载优化方法研究-软件工程专业论文.docxVIP

A Dissertation Submitted to Shanghai Jiao Tong University for Master Degree A SOLUTION FOR CONTAINER LOADING PROBLEM BASE ON GENETIC ALGORITHM Author：Zhongrong Zhao Specialty： Software Engineering Advisor： Prof. Wang Dong School of Software Shanghai Jiao Tong University Shanghai，P.R.China February，2010 第 第 I 页 基于改进遗传算法的集装箱装载优化方法研究 摘 要 集装箱装载优化问题是物流配送中的重要问题。在物流业快速发展 的当今社会，集装箱运输作为物流配送的主要方式已经成为物流配送过 程中的一个重要环节。集装箱运输的一个关键问题就是集装箱装载问题， 如何提高集装箱的装载效率，进而减少企业的物流成本，提高企业竞争 力已成为国内外学者关注的焦点。集装箱装载问题属于 NP-hard 问题， 学者们大都把研究的重点转向人工智能算法，但人工智能算法都有其局 限性和不足之处，因此改进智能算法并使之适用于实际的装载优化的任 务就摆在了各国学者面前。 本研究基于遗传算法的一般过程，在分析遗传算法特性的基础上， 结合最优个体保存策略和模拟退火算法的思想开发了一种改进遗传算 法。对一个集装箱装载问题，首先由启发式算法得到遗传算法的初始种 群，克服遗传算法随机初始种群的相对盲目性，使搜索方向相对明确； 接着在遗传算法的迭代过程中，根据遗传算法不同阶段的特性，以及模 拟退火思想和最优个体保存思想的特性，将上述两种方法同时引入到在 遗传算法中，从而克服了遗传算法的缺点，使得遗传算法的优点得到较 大程度的提升。 本文首先对集装箱装载优化问题的研究现状做了综述，分析和比较 了多种优化方法的特性并指出现有优化算法的问题；其次，在深入分析 遗传算法优缺点的基础上，提出了一种基于最优个体保存策略和模拟退 火思想相结合的改进遗传算法，提出了算法的框架；最后，实现了系统， 第 第 II 页 并用具体算例对本文算法进行了验证。 关键词：集装箱装载，遗传算法，模拟退火算法，最优个体保存策略 第 第 PAGE IV 页 A SOLUTION FOR CONTAINER LOADING PROBLEM BASE ON GENETIC ALGORITHM ABSTRACT The problem of container loading optimization is one of the important issues in logistics and distribution. Container transport , which as one of the leading in logistics and distribution, has become an important process of logistics and distribution in a developing rapidly in contemporary era. One of the key point is that container loading problem, which how to improve the efficiency of container loading to reduce the logistics cost for increasing competitiveness of enterprise, have become the focus of attention of scholars from domestic and foreign. Container loading problem are NP-hard problem, that scholars put their almost focus on the study of artificial intelligence algorithms. However, intelligence algorithms has its limitations and shortcomings. Thus the point that to improve and make the intelligent algorithms applied to the carrying task has been taken in front of the scholars f