Research On Algorithm Of Online Packing Problem For Ellipsoidal Fruits And Vegetables

Before being delivered,the booked fruits and vegetables should firstly be sorted and packed according to the customers’requirements.Traditionally,the packing work is manual.However,due to the labor intensity and long working time,the manual working is usually subjected to low efficiency and high errorrate.Because of the characteristics of random shape,large quantity,and packing refusal in the fruits and vegetables,the packing problem for fruits and vegetables is a tougher challenge than the classic packing problem.With taking variable size,space limitation,and rejection of repacking characteristics into consideration,this paper proposes a novel variable size bin packing problem with multiple constraint and desired weight.Based on the space-constrained packing framework,the closed-box criterion is modified,and theBRF_k online algorithm is proposed which is then improved and its parameters are analyzed.Finally,the effectiveness of the algorithm is verified by the test prototype.The specific works are as follows:(1)According to the characteristics of fruit and vegetable packing,this paper proposes the variable size bin packing problem with multiple constraint and desired weight.While keeping the framework of variable size packing model and taking the constraints of space-constraint and packing refusal into consideration,by setting a desired weight related to the customers’order and a full-load weight which is much larger than the desired weight,the proposed model is an optimum model in which the objective is to minimize the error of the real weight of fruits and vegetables and the desired weight.(2)Based on the space-constrained packing frame,we propose a BRF_k online packing algorithm based on Best Fit strategy which modifies the closing criterion according to the desired weight.Considering the packing refused fruits and vegetables can be repacked,the reward of those conditions is set to 0.Secondly,using the idea of dynamic programming,we improve theBRF_k packing algorithm.In the algorithm,the on-line boxed fruits and vegetables are regarded as batch arrival.The number of fruits and vegetables in a single batch is set up,and the local off-line optimization of each batch is carried out.Finally,the results of two algorithms are compared under the same conditions.The improvedBRF_k algorithm has better packing results,which is the main algorithm for the follow-up study.(3)In order to determine the optimal parameter of the algorithm such as the number of opened boxes,the number of fruits and vegetables in a single batch and the type of fruits and vegetables,a three-factor four-level orthogonal test has been designed.The range and variance analysis are verified by SPSS software.Then we use the regression fitting model to study the quantitative relationship,select the best fitting model and determine the relationship between each parameter and the packing result.According to the fitting model,it is determined that the number of open boxes in the algorithm is 6,and the number of fruits and vegetables in a single batch is 9,which is the optimal parameter scheme.Finally,the BF,BFD and the improvedBRF_k algorithms are compared under the same conditions.The experimental results show that the average packing result of theBRF_k algorithm is 48.73%and 62.29%of the BF and BFD algorithms,and the algorithm reduces the amount of fruits and vegetables packaging result by 51.27%and 37.71%,respectively,which has the better optimal results(4)In order to verify the effectiveness of the algorithm,combined with the fruit and vegetable packing operating process,a fruit and vegetable packing test prototype using pallets for reciprocating transportation is designed through 3D modeling and assembly of the fruit and vegetable trays,unloading mechanism in CREO software,and the algorithm validity verification is carried out.The results show that as the weight of single fruit and vegetable increases,the overloaded quantity continues to increase.During the test,the prototype runs smoothly,and the algorithm does not delay.It can pack each fruit and vegetable in a reasonable time.According to the practical application requirements,this paper proposes the variable size bin packing problem with multiple constraint and desired weight and the improvedBRF_k algorithm based on batch arrival.Compared with the traditional bin packing model and algorithm,it has better adaptability and optimization effect,and provides certain reference significance.