0 引言
在保障抢险救灾等紧急任务时需要一次性投送多型号多台次大型装备,在装载前需针对不同运输投送任务进行装载方案规划,而装载方案直接影响航空投送效率。为保证货运飞机飞行安全的前提条件下尽可能提高航空运输的效率,需综合分析运输机的载重、重心平衡和空间约束,使得各项参数处于安全许可范围内,保证装载安全,同时尽可能利用最少架次运输机完成一次投送任务。
目前,关于航空装载方案规划问题可简化为带有约束的装箱问题[1]或背包问题[2],针对不同应用场景建立一维、二维或三维矩形物体布局模型[3],是典型的NP-hard问题[2],求解方法包括图论法、模拟退火算法、遗传算法、禁忌搜索算法[4]、数学规划法[5]等。孟冲等[6]将空间布局约束转换成0～1整数线性规划,实现对0～1整数线性规划空运装载问题的求解;Bertsimas等[7]提出了在诸多限制条件下利用混合整数规划模型解决美军人员和货物以最小延迟和最大可用飞机利用率交付需求为目标的空运规划问题;Roesener 等[4,8]针对货物装载在最少数量的空运飞机问题,提出了禁忌邻域搜索算法求解混合有效载荷空运装载问题和动态空运装载问题;海军等[9]以军用运输机装载质量最大、空间利用率最高作为优化目标建立多目标优化模型,利用蚁群算法进行求解;陈丙成等[10]主要将精英选择策略的精英遗传算法与轮盘赌的简单遗传算法相结合,用于装箱问题求解;刘胜等[11]提出了一种启发式正交二叉树搜索算法用于三维装箱问题的求解;李建等[12]针对大规模同时集散货物路线问题,提出了一种集成大量邻域搜索方法的禁忌搜索算法,用于提高求解能力。
目前针对尺寸较小、单体质量较轻物体的航空运输装载优化及优化算法本身相关问题研究较多,并取得了很好的研究成果。但大型装备具有单装尺寸大、吨位重,同时不同机型货舱的不同区域地板的设计承重强度不同[13],装备装载位置对于运输机安全性有直接影响,专门针对大型装备特点进行的相关研究较少。
前期通过与空军勤务学院合作开展了关于单台大型装备空运适应性的理论研究、虚拟仿真和装载试验,该项成果确保了用于装载优化问题研究的大型装备均可用运输机进行装载运输。为确保运输机安全,结合大型装备的特点,在综合考虑了运输机装载大型装备总重限制、空间限制、平衡制约基础上,增加了对运输机地板分区载重约束的考虑,以完成单次运输任务所需最少运输机为优化目标,建立了大型装备军事航空运输装载优化模型。航空运输装载优化属于NP-hard问题,用启发式算法求解该类问题较为合适[4]。
1 装载优化模型建立
现需要使用货运飞机将一批大型装备通过航空运输部署到任务区,待运输工程装备型号、数量及相关运输性参数已知。运输机的货舱有效长、宽、高,空载重量,空载满油重心位置,总载重量均已知。另外,如图1所示,可用于大型装备装载的运输机货舱有A、B、C、D等4个分区,每个分区的总载重量、长度已知。
图1 运输机货舱ABCD 4个分区示意图
Fig.1 Aircraft bay ABCD compartment diagram
为了便于使用运输机的重心限制图进行运输机重心计算,建立运输机的货舱直角坐标系。坐标系原点O位于货舱前部,沿运输机纵向中轴线为X轴,由机头向机尾方向为正方向,沿运输机的横轴方向为Y轴,沿运输机的立轴方向为Z轴。货舱直角坐标系,如图2所示。由于装备的装载是由内向外,先进入货舱的装备在内,后进入货舱的装备在外,装备沿X轴线正方向排列。因此装备的位置可用该装备最左端在X轴的位置表示。
图2 货舱直角坐标系
Fig.2 Aircraft bay coordinate diagram
1.1 模型假设
基于前期对大型装备空运适应性研究成果,为了便于模型构建,对不规则的运输机货舱内部空间、不规则的大型装备外形轮廓进行简化。
1) 大型运输机货舱的横截面并不是规则的圆形或矩形,为了便于建模计算,将运输机货舱的可用装载空间简化为长方体,如图2所示。
2) 大型装备形态各异,外形不规则,将待运大型装备最大外形轮廓简化为长方体[13],将不同装备处于装载时姿态的实际重心作为装备模型重心。
3) 假设所有待装载大型装备可以任意装载在若干架次运载飞机货舱内。
4) 大型装备由于尺寸较大,难以横向摆放或横向摆放后难以转向。因此,假设待装载大型装备只能沿X轴线摆放。
5) 待运大型装备不可以层叠摆放。
6) 待运大型装备优先装载在运输机货舱的某个分区中,当大型装备长度超过某一货舱分区长度时,可以占用相邻2个或3个分区。
7) 考虑到只有紧凑排列才能使运输机货舱被占用长度最小,因此假设同一机舱内的所有装备紧凑排列,任意相邻2台装备系留间距为国军标[14]规定的最小间距300 mm。
1.2 优化模型
以使用最少数量的运输机为优化目标,将一批次各型装备合理地装到运输机上,以提高投送效率,约束条件包括:重心位置约束、飞机总载重量约束、空间约束、飞机分区载重约束[15],以此建立运输装载优化模型,有
(1)
s.t. Xmin(k)≤Xk≤Xmax(k)
(2)
(3)
(4)
(5)
式(1)—(5)中:βk表示当第k架次运输机Fk装载装备的决策变量,当装载时βk=1,否则βk=0;Xk表示第k架次运输机装载后的重心坐标,Xmin(k),Xmax(k)分别表示第k架次运输机最小,最大重心坐标位置;P={Pi|i=1,2,…,N}={pij|pij∈Pi;i=1,2,…,N, J=1,2,…,ni}表示待运装备集合,其中N为待运装备的种类数,i为集合中装备的种类号,ni为第i类装备的总辆数, j为某类装备中的件数号;αijk表示当运输机Fk装载装备pij的决策变量,当装载时αijk=1,否则为αijk=0;PMi、PLi分别表示第i类装备的质量和长度,i=1,2,…,N;δ1为装载后相邻2台装备之间的最小距离,δ2为装载后所运装备、物资的顶部或四周与飞机内部结构之间的最小间隙;Mkmax、Lkmax、Mklmax分别表示第k架运输机可用于装载的最大载重量、最大机身长度、第l分区最大载重量。
2 算法设计
2.1 初始解获取
通过随机搜索算法获取一个初始解。具体步骤如下:
步骤1 数据初始化:输入运输机与待运装备基本参数。
步骤2 终止条件:迭代N次,且之后某次所用运输机数量小于前面计算的各次,则终止,得到一个可行解。否则,继续步骤3。
步骤3 将所有型号的所有待运装备编号,随机排列得到一个装备编号序列。
步骤4 利用货舱长度、载重约束,分割装备子序列,得到初步装机方案。
步骤5 利用货舱长度约束,计算每架运输机上装备子序列的重心范围。
步骤6 装备子序列的重心范围与运输机重心可用范围有交集,则继续第7步。否则,终止本次搜索,返回步骤2。
步骤7 取交集,得到每架运输机上装备子序列的实际重心范围与装备首部(最左端)坐标。
步骤8 校核运输机地板分区最大载重约束,如满足,则记录所用装载方案;否则,终止本次搜索,返回步骤2。
2.2 禁忌搜索算法
禁忌搜索算法可用于解决组合优化问题,由于采用类似于人类记忆功能的禁忌策略,容易跳出局部最优。当某些搜索策略或搜索区域适应值较好,可能在没被禁止到一定周期就解除禁忌,这称为藐视条件,更容易搜索到全局最优。禁忌搜索算法的步骤不再赘述。算法流程如图3所示。
图3 算法流程图
Fig.3 Algorithm flow chart
2.3 禁忌搜索算法要素的确定
用禁忌搜索算法求解大型装备航空运输装载优化问题,需要确定解的表示、解的评价、邻域点产生方法、算法终止准则、禁忌对象、禁忌长度及候选集等要素[16]。
采用将待运大型装备直接排列的表示方法,即将所有类型待运的装备按照一定的顺序直接排列成为一个序列,并对其连续编号。这个自然数数列就构成了一个解,并对应了一种装载方案。邻域点产生方法采用两换位法,产生若干个邻域点,指定迭代步数作为算法终止准则,采用解的简单变化作为禁忌对象,以待运装备数量作为禁忌长度,邻域中随机选择若干评价值较好的邻居作为候选集。
3 数值计算
程序设计利用模块化思想,对主要功能函数进行封装,以便于修改、调试与调用。程序主要包括装备与运输机运输性数据读取模块、运输机货舱总长度与总重量约束计算模块、运输机重心范围约束计算模块、运输机分区载重约束计算模块、禁忌搜索算法模块以及结果分析呈现模块。利用MATLAB软件编程,对装备航空运输装载方案优化进行计算,得出最优解。
某次远程投送任务待装载的装备为9型15台装备,型号用字母代替如表1所示。
表1 待运装备型号、数量等相关参数
Table 1 Parameters of equipment to be loaded
序号型号数量编号长/mm重心/mm质量/t1a21,27 3902 85017.9002b23,47 654328627.5403c157 0003 34535.0004d164 10020527.0005e27,87 5903 22519.9006f197 7004 44010.4367g210,114 0002 1304.5008h212,133 4801 6206.0009i214,155 6202 5208.100
利用所建立的优化算法可计算得出装载方案,结果显示,使用6架次货运飞机即可完成此次装备投送装载任务,6架次货运飞机装载的装备型号分布如表2所示。待运装备在各架次运输机的位置,相对于货舱前部的坐标如表3所示。待运装备的装载方案图如图4所示。
表2 待运装备型号分布
Table 2 Distribution of equipment to be loaded
飞机架次装备1装备2装备31ab2dga3hic4ihb5fe6eg
表3 待运装备相对于货舱前部X坐标
Table 3 X coordinate of equipment to be loaded
飞机架次装备1/mm装备2/mm装备3/mm12 829.210 519.022 054.26 454.210 754.03450.84 230.810 151.04778.16 698.110 478.052 750.410 750.066 418.814 309.0
图4 待运装备的装载方案图
Fig.4 Loading scheme of equipment to be loaded
图4横坐标为运输机货舱中轴线X轴坐标,单位(1 000 mm),纵坐标为运输机使用数量。竖直虚线代表运输机货舱分区界线,横向点划线代表某一架次运输机货舱。粗实线代表某一台装备,线上编号代表装备编号,“△”代表装备的首部坐标,“★”表示在本架次运输机上所装载装备组成的装备序列的重心坐标(相对于货舱前部)。如第1架运输机,装载了编号为1和3的装备,首坐标分别为2 829.2、10 519 mm,由编号为1和3的2台装备组成的紧密装备序列的重心坐标为10 500.0 mm。从图4中可以看出优化后装载方案,装备居运输机中部装载,符合一般装载规律,空间利用合理。各架次运输机装备子序列重心可移动范围如图5所示。
图5 各架次运输机装备子序列重心可移动范围
Fig.5 Center of gravity range of equipment sequence in every airpcraft
图5中运输机可用重心范围表示某架次运输机装载的装备序列重心还有一定的可调整范围。如第1架次运输机装载了编号为1和3的2台装备组成的装备序列,这个装备序列的重心可用范围为10 500～10 781 mm,实际上运输机X轴方向装载重心允许范围在10 500～13 500 mm。因此这3台装备组成的装备序列首坐标、装备间的最小间距均可在小范围内调整,只要重心仍在可用范围10 500～10 781 mm内即可。
图6为各运输机分区载重利用率。图7为各运输机空间与总载重量利用率,运输机总体空间与载重利用率较高。运输机的空间平均利用率83.8%,而运输机的载重平均利用率66.8%。因此,大型装备的长度是制约装载方案优化的主要因素。
图6 各架次运输机分区载重利用率
Fig.6 Usage of ABCD compartment in every aircraft
图7 各架次运输机空间与载重利用率
Fig.7 Usage of space and weight in every aircraft
多台大型装备跨分区装载优化问题的算法,不仅可以适用于只使用某一个相同型号运输机多架次装载,通过输入不同型号运输机的参数,也同样适用于采用不同型号运输机装载优化问题,实现不同型号运输机同时混编运输的装载方案规划。
4 结论
1) 考虑了运输机的货舱总载重量、分区载重量限制、总长度限制条件,以最少架次运输机完成航空装载为目标,首先运用随机搜索算法获得初始解,然后利用禁忌搜索算法求解大型装备航空运输装载问题,可生成针对投送任务的装备装载优化方案,有助于实际装载方案拟制。
2) 采用运输机货舱总长度与总载重量约束作为分割装备序列的依据,符合大型装备普遍较长、线重比(重量与长度的比值)较大的特点。计算结果同样表明,长度是制约大型装备装载的主要因素。
3) 为了便于计算,将大型装备视为质量均匀分布的长方体,后续研究可考虑装备底盘型式、载重分布的实际情况,按照轮式、履带式装备分别校核运输机货舱分区载荷要求,使模型更加贴合装备实际特征。
4) 为了使装备重心范围严格约束,采用了运输机满载时的重心可用范围,然而在实际装载中如果运输机未满载,重心可用范围较满载时更宽,因此,下一步研究中,可结合运输机载重,限制重心可用范围。
[1] GUERET C,JUSSIEN N,LHOMME O,et al.Loading aircraft for military operations[J].Journal of the Operational Research Society,2003,54(5):458-465.
[2] HOMSI G,JORDAN J,MARTELLO S et al.The assignment and loading transportation problem[J].European Journal of Operational Research,2021,289(3):999-1007.
[3] 查建中,唐晓君,陆一平.布局及布置设计问题求解自动化的理论与方法综述[J].计算机辅助设计与图形学学报,2002,14(8):705-712.
ZHA Jianzhong,TANG Xiaojun,LU Yiping.An overview of the theory and methods of automatic layout and layout design problem solving[J].Journal of Computer Aided Design and Graphics,2002,14(8):705-712.
[4] NANCE R L,ROESENER A G,MOORE J T.An advanced tabu search for solving the mixed payload airlift loading problem[J].Journal of the Operational Research Society,2017,62(2):337-347.
[5] KALUZNY B L,SHAW R.Optimal aircraft load balancing[J].International Transactions in Operational Research,2010,16(6):767-787.
[6] 孟冲,宋华文,陈柏松.基于0-1整数线性规划军事空运装载优化算法[J].西南交通大学学报,2011,46(3):500-505.
MENG Chong,SONG Huawen,CHEN Baisong.Optimization algorithm of military air transport loading based on 0-1 integer linear programming[J].Journal of Southwest Jiaotong University,2011,46(3):500-505.
[7] BERTSIMAS D,CHANG A,MISIC V,et al.The airlift planning problem[J].Transportation Science,2019,53(3):773-795.
[8] ROESENER A G,BARNES J W.An advanced tabu search approach to the dynamic airlift loading problem[J].Logistics Research,2016,9(1):1-18.
[9] 海军,苑德春,王守辉,等.基于多目标优化装载算法的军用运输机数量规模量化测算[J].军事交通学院学报,2016,18(1):10-14.
HAI Jun,YUAN Dechun,WANG Shouhui,et al.Quantitative calculation of the quantity and scale of military transport aircraft based on multi objective optimal loading algorithm[J].Journal of Military Transportation Academy,2016,18(1):10-14.
[10] 陈丙成,李艳华.基于混合遗传算法的多航空集装器装箱优化设计[J].包装工程,2021,42(5):181-186.
CHEN Bingcheng,LI Yanhua.Optimal packing design of multiple aviation containers based on hybrid genetic algorithm[J].Packaging Engineering,2021,42(5):181-186.
[11] 刘胜,朱凤华,吕宜生,等.求解三维装箱问题的启发式正交二叉树搜索算法[J].计算机学报,2015,38(8):1530-1543.
LIU Sheng,ZHU Fenghua,LV Yisheng,et al.Heuristic orthogonal binary tree search algorithm for 3D packing problem[J].Journal of Computer Science,2015,38(8):1530-1543.
[12] 李建,鲁植雄,高谋荣.大规模同时集散货物路线问题的新禁忌搜索算法设计[J].西南交通大学学报,2009,44(5):787-793.
LI Jian,LU Zhixiong,GAO Mourong.New tabu search algorithm design for large scale simultaneous distribution cargo routing problem[J].Journal of Southwest Jiaotong University,2009,44(5):787-793.
[13] 罗经瑞,杜永现,刘宝新.民航货机集装化装运军事装备之可行性研究[J].国防交通工程与技术,2009,7(6):20-37.
LUO Jingrui,DU Yongxian,LIU Baoxin.Feasibility study on the integrated loading of military equipment by civil aviation cargo aircraft[J].National Defense Traffic Engineering and Technology,2009,7(6):20-37.
[14] 中央军委装备发展部.GJB8849—2016,大型运输机军事装备运输装载要求[S].北京:国家军用标准出版发行部,2016.
Equipment Development Department of the Central Military Commission.GJB8849—2016,Loading requirements for military equipment transportation of large transport aircraft[S].Beijing:National Military Standards Publishing and Distribution Department,2016.
[15] 陈璇,樊永生,余红英,等.自适应烟花算法在重型装备装载中的应用[J].科学技术与工程,2016,16(25):296-300.
CHEN Xuan,FAN Yongsheng,YU Hongying,et al.Application of adaptive fireworks algorithm in heavy equipment loading[J].Science Technology and Engineering,2016,16(25):296-300.
[16] 高立杰,王帅.基于禁忌搜索算法的铁路运输汽车专用车配载优化[J].铁道货运,2015,33(6):29-33.
GAO Lijie,WANG Shuai.Optimization of special vehicle loading for railway transport vehicles based on tabu search algorithm[J].Railway Freight Transport,2015,33(6):29-33.