Research On The Algorithm Of Bin Design And Packing Problem

With the rapid development of e-commerce,the e-commerce platform processes hundreds of millions of orders every day,and the cost of order packaging becomes increasingly important.The size of the packing case has a fundamental influence on the order packaging cost,and it is of great economic value to make scientific decision.We name this problem as the bin design and packing problem(BDPP).The BDPP,is the problem of designing the dimensions of several types of bins to pack a set of items and get the bin type plan and bin packing plan.The objective is to minimize the total cost s of used bins and the cost of bin is function of bin's length,width and height.BDPP belongs to open dimension problem(ODP)and because the BDPP is closely related to threedimensional multiple bin-size bin packing problem(3D-MBSBPP)and the three dimensions of each bin type are opening,BDPP is the most complex and difficult problem in ODP and there was no previous research on this problem.Therefore,our research also has great theoretical research value.Firstly,we conduct the literature review of ODP and 3D-MBSBPP.Secondly,we build mathematical models of BDPP and linearize the high-order terms in the objective function.Then,we decompose BDPP into six decision problems and analyze them in sequence.On this basis,four heuristic algorithms are proposed.The first two algorthms-deterministic constructive heuristic algorithm(DCHA)and tabu search-variable neighborhood search hybrid heuristic algorithm(TSVNSHHA)are employed to solve 3D-MBSBPP and the latter two algorithms-hybrid genetic algorithm(HGA)and hybrid differential evolution algorithm(HDEA)are for BDPP.The DCHA is a heursitic for solving 3DMBSBPP and is built on the concept of composite space structure that integrates point and sphere.The solution obtained byDCHA is used as initial solution of TB-VNSHHA and DCHA also serves as inner algorithm of HGA and HDEA to solve 3D-MBSBPP.All above algorithms can solve the problems with or without item placing orientation limitation and considering the items' fragility constraints.At last,in the numerical experiments,we test the eight strategy combinations of DCHA at the beginning,then designate strategy combination 2 and 8 as the default configuration of DCHA when solves the problem s with or without item placing orientation limitation separately.In the experiment of 3DMBSBPP,we prove the TSVNSHHA get a better solution than GRASP* in equal times: Without item orientation limitation,the GAP between TSVNSHHA's solution and lower bound is 3.34% less than GRASP*'s GAP;with limitation,the decrease becomes 10.71%.In the experiment of BDPP,through applying HDEA to design bins' dimension,the total cost is 16.47% less than the condition not designing when packing same set of items;while the HGA can lower the total costs by 27.28%.Testing on the The actual operation data of e-commerce,the HDEA can reduce cost by 37.56% while HGA lower cost by 35.7%.The results of BDPP's above experiment provide a strong demonstration that we can slash the bin packing costs by designing bins' dimensions.