组合装箱问题模型与算法研究

发布时间：2018-01-07 02:01

本文关键词：组合装箱问题模型与算法研究　出处：《上海交通大学》2015年硕士论文　论文类型：学位论文

【摘要】：本文研究近年新提出的汽车物流组合装箱问题。该问题在国内汽车物流领域实际存在,并且伴随着中国汽车工业的迅速发展,凸显出来,对物流运输公司造成了很大的困扰。因此,针对性的解决该问题具有非常重要的现实意义。通过研究该问题,提出有效的解决方案,并应用到实践中,对于汽车物流来说,能够非常有效的降低成本并且提高效率。首先,本文在研究其他经典装箱问题的基础上,将组合装箱调研与实践中遇到的目标需求与操作要求进行分析与整理,将其转化为问题的目标与约束,形成完整的问题描述,并且建立混合整数规划模型。其次,为了快速、有效的求解该问题模型,本文设计了两种算法,一种是基于分枝定界思想的精确求解算法,针对本文所研究的问题以及模型,分别给出了分枝定界算法的分枝策略、上界、下界、搜索模式和支配规则,并且给出了详细的算法流程。另一种算法则是基于贪婪思想的启发式算法。本文详尽介绍了贪婪算法的基本思想以及算法流程。最后,通过数值实验验证所提出模型与算法的有效性。本文使用ILOG CPLEX优化工具和设计的算法对模型进行求解,进行数值实验,通过比较一些指标,分析实验结果来对模型的有效性以及设计的算法的高效性进行验证。同时,对组合装箱调度的实际数据进行实例验证,通过与实际人工调度的结果比较待装载商品车完成数量以及高紧急程度的商品车的完成比例,证明建立的模型以及算法较人工调度的优势,从而验证了实际应用价值。本文通过构建数学模型、设计有效算法,为组合装箱问题提供了高效的、智能化的解决方案。通过数值实验表明,本文研究成果可直接应用于实践活动,对组合优化的理论与方法的发展具有一定的推动作用。
[Abstract]:This paper studies the combined packing problem of automobile logistics in recent years. The new problems in the domestic auto logistics field, and with the rapid development of automobile industry, Chinese emerged, caused great distress to the logistics company. Therefore, to solve this problem has very important practical significance. Through the study of the problem and propose effective solutions, and applied to practice, for the automotive logistics, can effectively reduce the cost and improve the efficiency. Firstly, based on the study of other classical bin packing problems, the combination of demand and operation encountered packing investigation and practice requirements of collation and analysis, will be transformed into objectives and constraints, the formation of a complete description, and a mixed integer programming model is built. Secondly, in order to quickly and effectively solve the problem of the model. Two kinds of algorithm design, an exact solution algorithm is based on the idea of branch and bound, in view of the problems studied in this paper and the model of the branch and bound algorithm are given branching strategy, upper bound, lower bound, the search mode and control rules, and gives the detailed algorithm process. Another algorithm is a greedy heuristic algorithm based on the idea. This paper introduces the basic idea and algorithm of greedy algorithm. Finally, the effectiveness of the proposed model and algorithm is verified through numerical experiments. This paper uses ILOG CPLEX optimization tools and design the algorithm to solve the model by numerical experiments, through the comparison of some indicators, analysis of the experimental results to the validity of the model the design and efficiency of the proposed algorithm is verified. At the same time, the actual data to verify the combination of scheduling cases, compared with the actual results than manual scheduling Is to be loaded goods vehicles complete volume and high degree of completion of the emergency vehicle proportion, the established model and algorithm with artificial scheduling advantage, which proves the practical value. This paper constructs the mathematical model, the design of effective algorithm, provides a combination of packing problem efficiently, intelligent solution by numerical. Experiments show that the results of this study can be directly applied to practice, has a certain role in promoting the development of the theory and method of combinatorial optimization.

【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F426.471;F252

【相似文献】