Research On Two-dimension Bin Packing Problem Of Heuristic Algorithms

The Bin Packing Problem exists widely in carriage loading,container loading,and pallet loading in logistics and transportation industry,and material cutting,product packaging,and facility layout planning in factory enterprises,and activities of organization of goods,schedule,and money management in people’s daily life.It belongs to Cutting and Packing Problems in the literature,which is a kind of classical NP-Hard problem.Under the current economic environment,activities of inventory and logistics are increasingly showing their importance,technologies related with Inventory and logistics have attracted more and more attention from scholars.How to reduce the cost of inventory and logistics becomes a very important and urgent problem.If more efficient use of the space of the container,the labor and time of transportation will be saved,then the inventory pressure and transport costs will be reduced,and the efficiency of inventory and logistics will be improved,at last,the corporate profits will significantly increase.This is of great significance to reduce the cost of enterprise operation and meet the needs of customers.Due to the characteristics of NP-Hard problem of bin packing,It is unwise to use directly exact algorithms for solving optimal solution of large-scale packing problem.The purpose of packing is to obtain a reasonable solution,therefore,heuristic algorithms become the first selection of theoretical research and practical application to ensure the approximate solution that can be gotten in limited time.The paper has researched on the two-dimension single bin size bin packing problem(2D-SBSBPP),namely the strongly heterogeneous two-dimensional rectangular items set exist,and its size is fixed,and the number of single rectangular boxes is unlimited,a packing scheme is pursued to load all of the items,to ensure that the items do not overlap and present an orthogonal state,also the requirements of guillotine-cut constraint condition is satisfied.The optimization goal is minimum consumption of total containers.To solve the problem of 2D-SBSBPP,this paper has put forward three distinctive algorithms: VCH-RI,VCH-SP and HHBP.VCH-RI is a kind of constructive heuristic algorithm with a pattern of layer packing.Algorithm mainly consists of three steps:(1)items are divided into a plurality of layers after a process of combination;(2)a multi-knapsack algorithm is used to put layers into several boxes;(3)the best optimal packing pattern is selected for inclusion into the solution set after replacement and insertion.The three step procedure is repeated for the remainder of the items,each of which is to obtain constituent elements of a solution,until the final box is generated,and all the boxes are generated to form a packing scheme.After several iterations,the best packing solution is chosen as the final solution.During the packing process,the value correction strategy is used to avoid the phenomenon of local optimum instead of global optimum due to the excessive use of some items.VCH-SP is a kind of heuristic algorithm for the pattern of non layer packing.The algorithm uses the list of space sets to design effective partition and the packing strategies for the current remainder space,and the combination of adjacent space fragments can improve the utilization rate of area.Whenever a box filled with items or residual spaces have no any use value,a new empty box is opened for packing until the number of remaining items is zero,eventually a solution is generated.The algorithm adjusts the order of items packing by correcting the value of items,then a new value of the collection is formed,at last,a new solution is generated after packing again,then better solutions are gained gradually after a number of iterations.HHBP is a kind of hybrid algorithm that combines exact algorithms and heuristic algorithms,and adopts a two-staged pattern.The algorithm is divided into two phases,each of which produces a solution,and from which the best is selected.During the phase 1,the residual problem is solved with column generation(CG)algorithm,and partial admitting procedure is used to select part of the patterns as the solution of the phase 1.the pattern set generated in the phase-1 is taken as the constraint of solution,then integer linear programming problems are resolved with CPLEX,then a solution in the phase 2 is obtained.Because of the time constraint used in the phase 2,the solution in the phase 2 is not necessarily the optimal solution,and the HHBP algorithm should select and output the optimal solution between the two solutions in the two phases based on the actual situation.Finally a summary and analysis are carried out with experimental data of the three algorithms,and a performance comparing with the other similar algorithms was assessed.The results show that the three algorithms have their respective characteristics,and the quality of the solution and time performance are acceptable.the horizontal comparison with other algorithms also verify the excellent performance of the new algorithms,which shows that these algorithms can solve the two-dimensional packing problem,then Improve the efficiency of logistics management,moreover,have a strong guiding significance to the actual operation of the enterprise.