Study On 2D Orthogonal Packing Problem With Unloading Constraints

We intends to study the two-dimensional orthogonal packing problem with unloading constraints(2DOPU)in this paper,and it is a practical problem often encountered in logistics distribution.Logistics distribution is the problem of deliver goods from the distribution center to various customer sites.Before delivery,specified goods need to be boxed first.and when these goods to be filled are household appliances or other fragile goods,because they cannot be stacked,whether the goods can be loaded successfully depends on the bottom surface of the goods on the underside of the carriage(two-dimensional orthogonal packing problem).In addition,a vehicle needs to deliver goods to different customer points usually,in order to meet the convenience of unloading operations,the unloading sequence of goods must be also considered in packing process(Last In First Out).thus,the packing problem is considered to be a two-dimensional orthogonal packing problem with unloading constraints.In addition,2DOPU is an extension of the classic twodimensional orthogonal packing problem,researching on it can improve efficiency and can cut down expense of time and economic in logistics distribution,at the same time,it also can enrich the content of combinatorial optimization,and can provide reference for follow-up scholars too.In order to study the efficient algorithm for a two-dimensional orthogonal packing problem with unloading constraints,we studies the two-dimensional strip packing(2DSPU)with unloading constraints in this paper at first,and converted it into 2DOPU by setting the length of a large rectangular container to a finite value.finally,we define the packing solution as a feasible solution for 2DOPU by comparing the actual minimum load length of 2DSPU with the finite value.The research ideas of 2DSPU are as follows: first,a mathematical model of 2DSPU is established;then according to the characteristics of this problem,an “open space” is used to represent the loading position and a first fit algorithm based on open space is proposed;the analysis the maximum number of open spaces is performed at next.and an efficient implementation method for the first fit algorithm is given by using line segment tree.finally,an iterative search algorithm is used to improve the quality of solution.In order to test the efficiency of IS algorithm,we respectively tested the sample set 1(825 examples)and the sample set 2(3282 examples)in experimental section,and the results show that the performance of IS algorithm is superior to the best algorithm GRASP in most test cases of 2DSPU,and also superior to B&C algorithm on a large scale for 2DOPU(the former finds most or all feasible solutions within one tenth of the latter),besides,it also found feasible solutions for 283 open examples during the effective time.Therefore,an open space-based first fit packing algorithm is very suitable for the packing problem with unloading constraints.