The work aims to propose a package loading scheme that allows the cargo to change size on the premise of constant volume, to solve the problem of fresh packaging and loading optimization in cold chain transportation, and maximize the space utilization rate of containers. A nonlinear mixed integer programming model was proposed to formulate the varietal package packing problem. To solve the nonlinear mixed integer programming model by solvers including CPLEX or Lingo, the internalization method was adopted to linearize the nonlinear integer programming model. Due to the NP-hardness of the studied problem, CPLEX or LINGO could not solve large-scale problems. An algorithm which effectively combined genetic algorithm and deepest bottom left with fill (DBLF) was designed. The experimental results of large and small scale examples showed that the hybrid genetic algorithm could obtain the optimal solution or approximate optimal solution in a reasonable time, which verified the performance of the algorithm. The proposed variable-size package scheme effectively improves the loading rate and could benefit both customers and the express delivery company.