Research On The Three-dimensional Packing Problem Optimization With Multiple Constraints Considering Volumetric Weight Balance

With the rapid growth of the economy,the less-than-truckload is growing rapidly.The lessthan-truckload carriers need to load and transport a large number of cargoes with different packaging type,weight,and volumetric weight,which makes the cost of less-than-truckload logistics transportation high.The question of how to optimize the loading combination of light and heavy cargoes to maximize truck’s utilization is the most concern of less-than-truckload.It is also an urgent problem to be solved.In this paper,the three-dimensional bin packing problem with volumetric weight of lessthan-truckload is researched with consideration of the balance of light and heavy cargoes.In view of the actual constraints of the load-bearing relationship between light and heavy cargoes,the geometric dimensions,weight and the way of placing cargoes,a mixed integer programming model with the goal of minimizing the number of bins and maximizing the volume and the payload utilization of bins simultaneously is built to achieve the goal of reducing the gap and enhancing the stability of the packing problem.The three-dimensional packing problem with volumetric weight is decomposed into the master problem,the restricted master problem and the sub problem by Dantzig-Wolfe decomposition and a branch-and-price algorithm is designed to solve it.For the nodes of branch-and-price algorithm,a box sequencing heuristics algorithm based on dual variables and volumetric weight is designed to determine the cargo loading order and a heuristic packing algorithm based on extreme points and dynamic volumetric weight is embed to column generation to improve the efficiency of solution.Finally,taking the time complexity and calculation accuracy of algorithm as the standard,the branch-and-price algorithm is compared with the column generation algorithm,biased random key genetic algorithm and non-dominated sorting genetic algorithms.Computational results show the branch-and-price algorithm to be capable of finding high-quality,satisfactory solutions in short computing times,which can efficiently and realistically help less-thantruckload optimize their truck loading.The sensitivity analysis also shows that the branch-andprice algorithm has good stability when the volumetric weight of the loaded cargoes changes greatly,and it can provide decision support for the loading of less-than-truckload cargoes.