求解非标准货物货机群装载问题的启发式搜索算法

货机装载问题属于三维装箱问题,是一类NP-hard组合优化问题。而与传统车辆装箱问题不同,货机装载后的重心位置是要考虑的重要约束条件,以重心偏移率和货舱空间利用率为目标函数,针对非标准货物的货机群三维装载问题进行启发式算法研究。该算法基于空间管理思想,将"砌墙"式建构算法与一种四规则深度优先搜索法相结合,排除大量不可行解,缩短了可行解的搜索时间。最后实验结果表明,本算法可以在满足各项约束条件下正确地为货机群三维装载问题找出可行装载结果,对解决实际货机群装载问题具有现实意义。

A Heuristic Algorithm for Solving the Cargo Aircrafts Group Loading Problem with Non-standard Goods

The cargo loading problem belongs to the 3D-packing problem, and thus it is a kind of NP-hard combinatorial optimization problem. Different from the traditional vehicle 3D-packing problem, the position of the center of gravity of the cargo aircraft after being loaded is an important constraint to be considered. In this paper, a heuristic algorithm is developed to solve the 3D-cargo aircrafts group loading problem of non-standard goods, with the multi-objectives of minimizing the deviation rate of the center of gravity and maximizing the space utilization of the cargo space. The proposed algorithm is based on the idea of space management and it combines the "wall building" construction algorithm with a four-rule depth-first search method. This heuristic algorithm could greatly reduce the solution searching time by eliminating a large number of infeasible solutions. Finally, the experimental results show that the algorithm can correctly find the feasible loading results for the 3D-loading problem of the cargo aircrafts group with satisfying all constraints. Thus, the proposed method has the practical significance for solving the realistic cargo aircrafts group loading problems.