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

摘要

研究了民航客改货飞机的载重平衡问题,分析了客改货飞机与客机和纯货机在载重平衡问题所存在的差异,建立了具备主货舱指派问题和下货舱背包问题组合优化特性的客改货载重平衡问题的线性整数规划模型,实现业载量最大和配载重心偏离指定目标重心最小的多目标函数,包含了实际操作中客改货机型的货舱及其位置约束、各种质量约束、上下舱联合约束与飞机重心包线约束等;设计了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。