客改货飞机载重平衡问题建模与Benders分解算法设计

Weight balance problem modeling and benders decomposition algorithm design of preighter

研究了民航客改货飞机的载重平衡问题,分析了客改货飞机与客机和纯货机在载重平衡问题所存在的差异,建立了具备主货舱指派问题和下货舱背包问题组合优化特性的客改货载重平衡问题的线性整数规划模型,实现业载量最大和配载重心偏离指定目标重心最小的多目标函数,包含了实际操作中客改货机型的货舱及其位置约束、各种质量约束、上下舱联合约束与飞机重心包线约束等;设计了Benders分解算法对该模型求解,把原问题分为主问题和子问题两部分;设计了改进模拟退火算法求解主问题,改进了离散变量的编码、变异以及个体修正等策略;设计了基于逻辑检查的y-check算法,用于检查子问题的上下舱联合限重、重心包线等复杂约束,给出了Benders’Cut约束模型;设计了以B757-200客改货飞机为例的20组不同规模算例,基于Gurobi、Lingo、人工配载和本文提出的算法对模型进行验证。研究结果表明:Gurobi求解质量和速度最好,平均业载量为29 517.3 kg,重心偏差为0.02%,求解时间为0.13 s;人工配载方法最差,平均业载量为27 131.9 kg,重心偏差为5.26%,求解时间为581.75 s;本文提出的算法由于采用了智能启发式算法,平均业载量为28 379.1 kg,与Gurobi和Lingo的最优解相比稍差,但重心偏差为0.05%,可以忽略不计,平均求解速度为20.33 s,远快于Lingo的7 370.65 s。

The weight balance problem(WBP) of civil aviation preighter was studied.The WBP differences between preighter,passenger aircraft,and cargo aircraft were compared.A linear integer programming model of preighter WBP was built with the combined optimization characteristics of main cargo compartment assignment problem and lower cargo backpack problem.The multi-objective function of the maximum payload and the minimum deviation of the center of gravity(CG) from the specified target was realized,including the cargo holds and their position constraints,various mass constraints,joint constraints on upper and lower cabins,as well as the CG envelope constraints of the preighter in actual operation.The benders decomposition algorithm was designed to solve the model,dividing the original problem into two parts:the main problem and the subproblem.To solve the main problem,a modified simulated annealing algorithm was proposed,which improved the coding,variation,and individual modification strategies of discrete variables.The y-check algorithm based on logical check was designed to check the complex constraints such as joint weight limits of upper and lower cabins and the CG envelope of subproblems.The benders' cut constraint model was given.Twenty groups of examples with different scales were designed by taking a B757-200 preighter as an example.The Gurobi,Lingo,artificial stowing,and the proposed algorithm were tested to verify the model.Research results show that the Gurobi has the best resolution quality and speed,whose average payload,CG deviation and solution time are 29 517.3 kg,0.02%,and 0.13 s,respectively.The artificial stowing method is the worst,and its average payload,CG deviation,and solution time reach 27 131.9 kg,5.26%,and 581.75 s,respectively.As an intelligent heuristic algorithm,the proposed algorithm gets a payload of 28 379.1 kg,which is slightly worse than the optimized solutions of Gurobi and Lingo.Its CG deviation is only 0.05%,which can be ignored.The average solution speed is 20.33 s,much faster than the Lingo's 7 370.65 s.7 tabs,10 figs,32 refs.