动态多目标三维装箱问题的研究及其应用

发布时间：2018-04-02 13:32

本文选题：三维装箱问题　切入点：动态装箱　出处：《东北电力大学》2017年硕士论文

【摘要】：装箱问题具有广泛的应用性。在实际应用中,受到装箱问题影响最直接和显著的领域是物流运输行业。在当今物联网、互联网+的时代,“人工智能”已经成为一种标志,而物流运输中装载工作还是根据经验来完成的,这就很难保证货箱空间利用率和企业成本问题。三维装箱问题的研究,对于物流公司提高装箱空间利用率、减少物流成本意义重大。本文基于三维装箱问题的实际情况,建立了多货箱、多货物及多目的地的三维装箱问题的整数规划模型;针对货箱、货物规格及目的地单一的三维装箱问题,设计了相应的基于底层优先的动态装箱的启发式算法,并将研究结果应用于实际三维装箱问题进行实证研究。首先,构建了三维装箱问题的整数规划模型。系统地分析了装箱全过程,考虑了装箱稳定性和平行性等约束,通过引入0-1变量等方法,对约束条件进行数学描述,构建了货箱、货物规格和目的地单一的三维装箱问题的整数规划模型。并以此为基础,分别构建了货箱规格和目的地单一、货物规格多种的三维装箱问题的优化模型、货箱规格单一、货物规格和目的地多种的三维装箱问题的优化模型和货箱、货物规格和目的地多种的三维装箱问题的优化模型。然后,相应地设计了货箱、货物规格和目的地单一的三维装箱问题的基于底层优先动态装箱的启发式算法。三维装箱问题中货物装载时,是按照“由左向右、由下向上”的顺序依次装箱。因此,底层装箱方案尤为重要,它直接影响到货箱空间的利用率。本文以装箱体积最大为目标设计优化模型,求得底层最优装箱方案,并以此类推求得剩余空间最优装箱方案,并对装箱方案进行稳定性验证,对不符合稳定性要求的方案进行调整,从而得到整箱最优装箱方案。最后,对本文研究结果进行了实例验证。将本文建立的整数规划模型应用于乘用车装载方案,综合考虑装载约束,建立模型快速求解,得到了乘用车使用数量较少的装载方案;以文献中的经典算例为例,应用本文设计的启发式算法进行求解,并与文献结果进行比对,验证了算法的合理性,使得装箱利用率达到了百分之九十以上。实证研究结果表明,本文构建的整数规划优化模型能够在满足装箱全部约束的条件下快速得到合理的方案,设计的启发式算法能够得到较高装箱空间利用率的装箱方案。
[Abstract]:Packing problem has wide application. In practical application, the most direct and significant field affected by packing problem is logistics transportation industry. In the age of Internet of things and Internet, "artificial intelligence" has become a symbol. However, the loading work in logistics transportation is completed according to experience, so it is very difficult to ensure the utilization ratio of container space and the cost of enterprises. It is of great significance to reduce the cost of logistics. Based on the actual situation of the three-dimensional packing problem, the integer programming model of the three-dimensional packing problem of multi-container, multi-cargo and multi-destination is established in this paper. This paper designs a heuristic algorithm based on the underlying priority dynamic packing algorithm, and applies the results to the actual three-dimensional packing problem. The integer programming model of 3D packing problem is constructed. The whole process of packing is systematically analyzed, and the constraints such as packing stability and parallelism are considered. By introducing 0-1 variables, the constraint conditions are mathematically described, and the container is constructed. Based on the integer programming model of three-dimensional packing problem with single cargo specification and destination, the optimization model of three-dimensional packing problem with single container specification and single destination and multiple cargo specifications is constructed, and the box specification is single. The optimization model of three dimensional packing problem of goods specification and destination, the optimization model of cargo box, the optimization model of three dimensional packing problem of goods specification and destination, and the corresponding design of cargo box, A heuristic algorithm based on the underlying priority dynamic packing problem for a single three-dimensional packing problem with a single cargo specification and destination. In the 3D packing problem, the loading order is "from left to right, from bottom to top". The bottom packing scheme is especially important, which directly affects the utilization rate of the container space. In this paper, the optimal packing scheme is obtained by using the maximum volume of the container as the objective, and the optimal packing scheme of the remaining space is obtained by analogy. The stability of the packing scheme is verified, and the scheme that does not meet the requirements of stability is adjusted to get the optimal packing scheme for the whole box. Finally, The integer programming model is applied to the loading scheme of passenger vehicle, and the model is solved quickly by considering the loading constraints, and the loading scheme of passenger vehicle is obtained. Taking the classical examples in the literature as an example, the heuristic algorithm designed in this paper is used to solve the problem, and the results are compared with the results in the literature. The rationality of the algorithm is verified, and the case utilization ratio reaches more than 90%. The integer programming optimization model constructed in this paper can quickly obtain a reasonable scheme under the condition of satisfying all packing constraints, and the heuristic algorithm designed can obtain a packing scheme with high packing space utilization ratio.
【学位授予单位】：东北电力大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4

【参考文献】