Weight balance problem modeling and two-stage Benders decomposition heuristic algorithm design of non-ULDs

To explore the potential of loading non-unit load devices (non-ULDs) in civil aviation cargo aircraft, the weight balance problem (WBP) of loading non-ULDs in cargo aircraft was studied. The differences between loading non-ULDs and ULDs in WBP were compared. The cargo hold was regarded as a rectangular plane and the non-ULDs as rectangular items, a two-stage weight balance optimization model was constructed for loading non-ULDs. In the two-dimensional geometric constraint model in the first stage, constraints of non-ULDs were considered such as no overlapping, not exceeding the cargo hold boundaries, and orthogonal rotation. The maximum utilization of the aircraft cargo hold plane area was taken as the objective function. In the weight balance model in the second stage, constraints of various aircraft were considered such as weight and stability. The maximum payload and minimum center of gravity (CG) deviation were selected as the multi-objective function. The Benders algorithm was designed and used based on logical decomposition. The WBP of cargo aircraft loading non-ULDs was decomposed into a master problem and a sub-problem. The master problem used improved genetic simulation and the lowest horizontal line algorithm to determine the loading sequence and position of non-ULDs. The sub-problem employed the y-check algorithm to check various constraints, such as weight and stability. The Benders' cut constraint model was provided. The two scenarios where the area of non-ULDs was greater than and less than the cargo hold area were designed. The model was verified and compared using four methods: the proposed algorithm, Gurobi^*, Gurobi, and expert stowing for two different loading constraint requirements. Experimental results show that, when testing a two-dimensional geometric position allocation model for left-right balance in the cargo hold, Gurobi^* achieves the best solution quality and speed. The average payload, cargo hold area utilization rate, CG deviation, and solution time are 19 872 kg, 65.88%, 2.08%MAC and 61.18 s, respectively. The expert stowing method is the worst, with its average payload, cargo hold area utilization rate, CG deviation, and solution time reaching 18 494 kg, 65.21%, 2.79%MAC, and 986.98 s, respectively. As a heuristic algorithm, the proposed algorithm gets an average payload of 18 874 kg, slightly worse than the optimized solutions of Gurobi^* and Gurobi. The average cargo hold area utilization rate and CG deviation are 71.87% and 2.76%MAC, respectively. The average solution time is 175.97 s, much faster than Gurobi's of 1 082.92 s. The proposed two-stage weight balance optimization model and algorithm can provide a reference for determining the loading positions and directions of non-ULDs.