Research On Modeling And Algorithm For Combinatorial Bin Packing Problem

This paper focuses on new combinatorial bin packing problem recently. This problem is a real problem in automobile logistics. With the development of China automobile industry, this problem has a serious impact in logistics companies. So, doing research into this problem and providing solutions can cut cost and improve efficiency.First of all, based on the research of other classical bin packing problems, this paper change the practical demands and rules into the objectives and constraints of the problem, giving the problem description. And establish a mixed integer programming model.Secondly, in order to quickly, effectively solve the problem, this paper designs two algorithms. One is the exact algorithm based on branch and bound method. This paper gives branching strategy, branch and bound algorithm for the upper bound, lower bound, the search mode and the rules for this combinatorial bin packing problem.And also provide the detail process of the algorithm. Another algorithm is a heuristic algorithm based on greedy method. This paper introduces the basic idea and algorithm flow of greedy algorithm in detail.Finally, this paper verifies the effectiveness of the proposed exact and heuristic algorithm in this paper through numerical experiments. Using the ILOG CPLEX tools for optimization and designed algorithm to solve the model, this paper compares some indexes, and analyses the experimental results to show the validity of the model and the efficiency of the design of the algorithm. At the same time, using the actual data for the logistics scheduling this paper compares the results of the numbers of loading items and high urgency completion ratio between manual scheduling and algorithm scheduling, to verify the established model and algorithm advantage.By constructing the effective mathematical model, algorithm design, this paper provides efficient, intelligent solution for combined loading problem. Through the example, research results of this paper can be directly applied to production and service activities, has important practical significance to guide the practice of logistics, has a certain role in promoting the development of the theory and method of combinatorial optimization.