散套装货物混合装载问题优化算法研究

发布时间：2018-01-18 09:28

本文关键词：散套装货物混合装载问题优化算法研究　出处：《大连理工大学》2015年硕士论文　论文类型：学位论文

【摘要】：集装箱配载优化问题是集装箱运输行业中的关键问题,是一种典型的NP-hard问题,具有高度复杂性,寻找一个有效的解决多约束集装箱配载优化问题的方法有重要现实意义。本文首先对集装箱装载问题进行简单介绍,并总结了当前的研究现状,在对传统的精确算法及基于规则的启发式算法和基于搜索的启发式算法分析比较之后,对带角件约束的散套装混合装载问题提出了一种基于货物块和空间的构造式启发式算法。首先选择一个当前装载空间,然后按照货物优先级对货物初步排序,并按空间尺寸生成货物块,选择空间利用率最大的货物块装载,并切割空间。另外,针对角件约束,提出了一种基于空间切割,及“试空间”方法,有效规避角件,使角件周围的空间充分利用。针对套装约束,提出一种基于“估计套装装载数”的套装装载迭代算法,通过比较当前剩余空间体积和单套货物体积,估计装载套装数,试装载估计套装数并不断调整直至套装能够成套装载,该算法能保证货物成套装载在同一容器或指定的容器内。为验证算法的有效性,本文采用120组随机算例进行测试,与同类问题的算法比较,结果显示本文算法在计算稳定性以及计算时间方面都比较优秀,验证了算法的有效性。此外,对带角件约束和套装约束的实际问题设计测试算例,采用的是国际标准尺寸的集装箱和角件数据,实验结果表明本文所提的角件规避算法以及套装装载迭代算法有效,在引入新的约束后,空间利用率会稍微有所下降但是仍维持在较高的水平,计算时间上会有所增加,但仍在可接受的范围内。
[Abstract]:Container stowage optimization is a key problem in container transportation industry. It is a typical NP-hard problem with high complexity. It is of great practical significance to find an effective method to solve the problem of multi-constraint container stowage optimization. Firstly, this paper briefly introduces the container loading problem, and summarizes the current research situation. After analyzing and comparing the traditional exact algorithm and the rule-based heuristic algorithm and the search-based heuristic algorithm. In this paper, a constructive heuristic algorithm based on cargo block and space is proposed to solve the mixed loading problem of bulk packages with corner constraint. Firstly, a current loading space is selected, and then the goods are preliminarily sorted according to the priority of the goods. The cargo blocks are generated according to the space size, and the cargo blocks with the highest space utilization are selected to load and cut the space. In addition, a method based on spatial cutting and "test space" is proposed for the constraint of corner parts. In order to avoid corner parts effectively and make full use of the space around corner parts, a set loading iterative algorithm based on "estimating the number of loads" is proposed for suit constraints. By comparing the current volume of the remaining space with the volume of a single set of goods, estimate the number of loads, try to load the number of sets and adjust them until the package can be loaded in a complete set. In order to verify the validity of the algorithm, 120 sets of random examples are used to test and compare with similar algorithms. The results show that the algorithm is very good in terms of computational stability and computation time, which verifies the effectiveness of the algorithm. In addition, a test example is designed for practical problems with angular and set constraints. The data of containers and corner parts of international standard size are used. The experimental results show that the corner circumvention algorithm proposed in this paper and the iterative algorithm of package loading are effective, after introducing new constraints. There will be a slight decline in space utilization but it will remain at a high level, and the computing time will increase, but within acceptable limits.
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U169.6

【参考文献】