基于多約束二維排樣的艦載機(jī)最大密度布列算法

林信海，楊大鵬，鞏常蘭，李文學(xué)

1 中國(guó)艦船研究設(shè)計(jì)中心，湖北 武漢 430064

2 華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院，湖北 武漢430074

0 引 言

艦載機(jī)是航空母艦（簡(jiǎn)稱“航母”）的主要作戰(zhàn)力量，搭載更多數(shù)量的艦載機(jī)對(duì)提升母艦作戰(zhàn)效能具有重要意義[1]?？紤]到航母甲板空間有限，需在滿足作戰(zhàn)性能要求的前提下，對(duì)艦載機(jī)開展小型化設(shè)計(jì)，并優(yōu)化其外形輪廓，來(lái)提高搭載艦載機(jī)的數(shù)量和上艦適配性[2]。為量化評(píng)估某型艦載機(jī)在航母飛行甲板和機(jī)庫(kù)占地面積的指標(biāo)，美海軍基于近百年的航母艦載機(jī)使用經(jīng)驗(yàn)，提出了“最大密度布列因子”這一指標(biāo)[3-4]。

“最大密度布列因子”簡(jiǎn)稱“布列因子”，是可有效表征停放某型艦載機(jī)所需占用飛行甲板和機(jī)庫(kù)空間的一個(gè)經(jīng)驗(yàn)指數(shù)，布列因子越大，表明艦載機(jī)占用的航母甲板面積越大。艦載機(jī)布列因子的計(jì)算流程具體如下[5]：

1） 設(shè)定F/A-18C飛機(jī)為基準(zhǔn)艦載機(jī)，并規(guī)定其布列因子為1。

2） 按指定規(guī)則和約束，用基準(zhǔn)艦載機(jī)填滿“尼米茲”號(hào)航母的飛行甲板（不含著艦區(qū)）和機(jī)庫(kù)，記錄飛行甲板、機(jī)庫(kù)布列飛機(jī)數(shù)量之和，設(shè)其為a。

3） 按同樣規(guī)則布列某型艦載機(jī)，記錄布列艦載機(jī)的總架數(shù)，假設(shè)為b。

4） 基準(zhǔn)艦載機(jī)布列總架數(shù)和某型艦載機(jī)布列總架數(shù)的比值，即a/b，就是某型艦載機(jī)的布列因子。

艦載機(jī)最大密度布列是布列因子計(jì)算的核心，目前國(guó)內(nèi)外艦載機(jī)最大密度布列通常由具有經(jīng)驗(yàn)的人員借助CAD軟件手工完成，設(shè)計(jì)周期冗長(zhǎng)且要耗費(fèi)大量人力，導(dǎo)致艦載機(jī)布列因子計(jì)算效率低下，因此，急需一種可快速自動(dòng)生成艦載機(jī)最大密度布列方案的算法。

艦載機(jī)最大密度布列問題可歸屬于多約束條件下的二維不規(guī)則物體排樣問題[6]。由于二維不規(guī)則物體排樣問題的解空間較大，早期研究人員主要通過拼接和組合方式，將其轉(zhuǎn)化為較易處理的規(guī)則多邊形排樣問題[7-8]，但利用該方法對(duì)極不規(guī)則物體進(jìn)行排樣時(shí)，易造成較大浪費(fèi)。為此，Adamowicz等[9]基于多邊形表示法，提出臨界多邊形（NFP，no fit polygon）算法，通過計(jì)算不規(guī)則多邊形的NFP來(lái)判定多邊形之間是否干涉。張思[10]采用基于重心NFP算法開展了艦載機(jī)自動(dòng)布列軟件的設(shè)計(jì)，但并沒有考慮艦載機(jī)最大密度布列時(shí)的多個(gè)約束條件。

基于上述情況，本文將以二維排樣算法為基礎(chǔ)，重點(diǎn)研究艦載機(jī)最大密度布列多個(gè)約束條件的數(shù)學(xué)表達(dá)、處理策略及基本計(jì)算，并分別提出飛行甲板和機(jī)庫(kù)最大密度布列算法。

1 艦載機(jī)最大密度布列約束條件概述

通常來(lái)講，與常規(guī)的二維排樣算法相比，艦載機(jī)在飛行甲板和機(jī)庫(kù)最大密度布列要滿足以下約束條件：

1） 距離約束。為滿足布列安全要求，艦載機(jī)之間、艦載機(jī)與母艦邊界/船體結(jié)構(gòu)之間要保證一定的安全間距。其中，艦載機(jī)與母艦邊界/船體結(jié)構(gòu)的距離又包括機(jī)與艦外邊界（如甲板邊界、安全停機(jī)線）的距離、機(jī)與船體結(jié)構(gòu)（如島式上層建筑、機(jī)庫(kù)壁、機(jī)庫(kù)防火分隔門等）的距離，根據(jù)艦載機(jī)布列轉(zhuǎn)運(yùn)要求，艦載機(jī)之間、艦載機(jī)和島式上層建筑等的間距不一樣。

2） 超邊界約束。艦載機(jī)身與船體結(jié)構(gòu)、飛行甲板安全停機(jī)線應(yīng)保持一定安全間距，不可發(fā)生干涉。但是，在靠近飛行甲板舷邊布列時(shí)，在保證艦載機(jī)輪與甲板邊緣有一定安全間距的前提下，艦載機(jī)機(jī)身可超出甲板邊緣，即在布列時(shí)需動(dòng)態(tài)考慮艦載機(jī)的外形邊界。

2 艦載機(jī)最大密度布列的數(shù)學(xué)表達(dá)

2.1 艦載機(jī)、飛行甲板和機(jī)庫(kù)的幾何表達(dá)方法

艦載機(jī)、飛行甲板和機(jī)庫(kù)外形輪廓均屬不規(guī)則圖形，其幾何表達(dá)涉及到圖形的存儲(chǔ)、判交、平移、旋轉(zhuǎn)等相關(guān)操作，直接影響到布列算法的耗時(shí)和精度。目前，主要采用以下方法來(lái)表達(dá)二維不規(guī)則形狀：原始曲線表達(dá)法、多邊形表示法和包絡(luò)法等。本文選用多邊形表示法進(jìn)行艦載機(jī)、飛行甲板和機(jī)庫(kù)的幾何表達(dá)。

多邊形表示法是指采用連通多邊形的形式表達(dá)參與布列的甲板和艦載機(jī)圖形，若艦載機(jī)、甲板輪廓存在曲線邊，則根據(jù)一定的精度將曲線邊近似成直線段來(lái)替代，如圖1所示。

圖1 多邊形表示法Fig.1 The polygon-based representation

連通多邊形的定義如下。

定義1：平面連通N邊形P是指N個(gè)矢量端點(diǎn)的有序集合。以上矢量端點(diǎn)頭尾相連并按逆時(shí)針（順時(shí)針）方向排列，且各矢量之間不發(fā)生內(nèi)點(diǎn)相交。

其數(shù)學(xué)表達(dá)式為P={P1(X1,Y1),P2(X2,Y2),···,Pi(Xi,Yi),···Pn(XN,YN),i=1···N}。

多邊形表示法降低了圖形之間的操作運(yùn)算量，提高了排樣速度。雖然在一定程度上會(huì)導(dǎo)致不規(guī)則圖形精度的降低，但只要離散精度足夠高，就能夠滿足布列精度需求。

2.2 距離約束數(shù)學(xué)模型及處理策略

如圖2所示，將距離約束劃分如下：l1為艦載機(jī)的間距，l2為艦載機(jī)和母艦外邊界的間距，l3為艦載機(jī)和島式上層建筑等母艦內(nèi)邊界的間距。

圖2 二維排樣中的距離約束Fig.2 The distance constraints of two-dimensional shapes nesting

本文采用等距縮放的策略來(lái)處理該距離約束，即對(duì)艦載機(jī)、甲板的邊界按照一定間距進(jìn)行放大或者縮小，再開展最大密度布列。設(shè)艦載機(jī)的實(shí)際間距為l′1，母艦內(nèi)、外邊界的實(shí)際間距分別為l′3和l′2，具體見式（1）。之后艦載機(jī)以間距l(xiāng)′1將邊界進(jìn)行放大；甲板以間距l(xiāng)′2將外廓進(jìn)行等距收縮，以間距l(xiāng)3′將內(nèi)廓進(jìn)行放大。

之后，利用分段偏移法對(duì)艦載機(jī)和母艦進(jìn)行等距處理，具體流程如下：

步驟1：將艦載機(jī)、母艦邊界的每條線段均按等距方向進(jìn)行等距操作。如圖3所示，線段的起始端分別為Ps(xs,ys)和Pe(xe,ye)， 法向量為n，間距為d。進(jìn)行等距處理后線段起始點(diǎn)為和，為點(diǎn)Ps到Pe的有向線段，則

圖3 直線的等距計(jì)算Fig.3 The offset calculation for lines

步驟2：對(duì)等距操作后得到的邊緣進(jìn)行封閉處理。等距操作后多邊形相鄰兩邊Ci與Ci+1如相交，需對(duì)其進(jìn)行剪裁；如相離，需將其連接至一起，如圖4所示。

圖4 線段等距后幾何關(guān)系Fig.4 Geometric relation of lines after offsetting operation

本文采用直線延長(zhǎng)的方式對(duì)相離兩線段進(jìn)行連接（圖5）。

圖5 線段的直線連接方式Fig.5 Connecting operation between lines

步驟3：對(duì)生成的原始等距邊界進(jìn)行檢查，刪除無(wú)效的邊界，獲得最終有效邊界。

2.3 超邊界約束數(shù)學(xué)模型及處理策略

飛行甲板上排樣存在超邊界的約束條件，二維超邊界排樣問題可表述為：一組二維不規(guī)則外形的零件P1,P2,···,Pn， 每個(gè)零件包含特征點(diǎn){D1,D2,···,Dm}。需基于以下約束條件，在樣板P中以最大密度排放以上零件P1,P2,···,Pn，需滿足：

1） 任一零件Pi，Pj互不干涉。

2） 零件Pi的特征點(diǎn){D1,D2,···,Dm}與樣板P的外邊界保持一定間距。

圖6是艦載機(jī)超邊界擺放的情況，即艦載機(jī)的機(jī)身邊界可以超出飛行甲板停放，只要艦載機(jī)的機(jī)輪（通常為1個(gè)前輪和2個(gè)主輪）等特征點(diǎn)未超出飛行甲板邊界即可。

圖6 艦載機(jī)超邊界布列方案Fig.6 Aircraft spotting plan under the constraint of overlapping the boundary

傳統(tǒng)的排樣算法無(wú)法滿足超邊界排樣計(jì)算需求。考慮到可將樣板分為飛行甲板邊緣處的超邊界排樣區(qū)域和甲板內(nèi)的常規(guī)排樣問題，可采用不同的算法對(duì)其按先后次序進(jìn)行計(jì)算。如先排布甲板邊緣、再排布甲板內(nèi)部，則為外圍收縮次序；如先排布甲板內(nèi)部，再排布外板，則為中心膨脹次序（圖7）。

圖7 甲板不同區(qū)域情況Fig.7 The different regions of flight deck

本文采用的外圍收縮排樣順序可概括為：在飛機(jī)機(jī)輪不超出甲板邊界的前提下，將飛機(jī)盡可能多地向甲板邊緣和最小重心點(diǎn)移動(dòng)，依次將飛行甲板外邊界布滿飛機(jī)，再開始對(duì)甲板內(nèi)部區(qū)域進(jìn)行飛機(jī)排布。

綜上所述，超邊界布列的定位步驟為：

1） 利用某圖形格式導(dǎo)入飛機(jī)和飛行甲板的外形邊界信息，在飛機(jī)圖形中以不同圖層標(biāo)識(shí)飛機(jī)的特征點(diǎn)。

2） 獲取飛機(jī)的特征點(diǎn)，根據(jù)特征點(diǎn)是否超出甲板區(qū)域，判定飛機(jī)是否越過邊界。

3） 基于外圍收縮順序進(jìn)行排樣，即先進(jìn)行飛行甲板邊緣的飛機(jī)布列，再進(jìn)行甲板內(nèi)部區(qū)域的飛機(jī)布列。

3 機(jī)庫(kù)艦載機(jī)排樣算法

艦載機(jī)在機(jī)庫(kù)內(nèi)的最大密度布列可視為非等距約束下的不規(guī)則物體二維排樣算法，其優(yōu)化目標(biāo)就是使機(jī)庫(kù)內(nèi)艦載機(jī)數(shù)量最大化。本文擬基于最低重心NFP算法[11]對(duì)其進(jìn)行處理，機(jī)庫(kù)最大密度布列算法流程圖如圖8所示。

圖8 機(jī)庫(kù)最大密度布列流程圖Fig.8 The workflow of maximum density spotting plan on the hangar deck

機(jī)庫(kù)最大密度布列算法的步驟為：

1） 利用.dxf格式導(dǎo)入飛機(jī)和機(jī)庫(kù)外形邊界信息，并利用多邊形表示法將其轉(zhuǎn)化為離散點(diǎn)。

2） 根據(jù)最大密度布列準(zhǔn)則要求，分別輸入飛機(jī)之間，飛機(jī)與機(jī)庫(kù)防護(hù)分隔門、機(jī)庫(kù)壁的間距。

3） 基于式（1）和式（2），利用擴(kuò)展等效策略處理艦載機(jī)和機(jī)庫(kù)邊界。

4） 利用最低重心NFP算法布列艦載機(jī)。最低重心NFP算法的排樣規(guī)則將飛機(jī)放在重心最低的位置。其出發(fā)點(diǎn)是在不產(chǎn)生干涉的前提下，使布列艦載機(jī)的重心最低，為后面布列的艦載機(jī)留出更多的布列空間。其步驟為根據(jù)飛機(jī)外形邊界得出其重心；然后以指定的角度間隔（本文為1°）旋轉(zhuǎn)飛機(jī)，求解各旋轉(zhuǎn)角度下的重心NFP，記錄最低重心位置及對(duì)應(yīng)的旋轉(zhuǎn)角度，對(duì)飛機(jī)進(jìn)行定位。采用最低重心NFP方法，獲得最低重心的示意圖（圖9）。

圖9 最低重心NFP算法Fig.9 Lowest-gravity-center NFP algorithm

5） 從機(jī)庫(kù)甲板上除去已布列飛機(jī)的面積，獲得新的機(jī)庫(kù)輪廓（圖10），再進(jìn)行下一步布列。

圖10 新機(jī)庫(kù)邊界的合成Fig.10 Regeneration of the hanger deck contour

6） 重復(fù)以上步驟，直至剩余的機(jī)庫(kù)空間不足以容納1架飛機(jī)為止。

4 飛行甲板艦載機(jī)排樣算法

針對(duì)飛行甲板艦載機(jī)最大密度布列，本文基于外圍收縮順序[12]，分別對(duì)飛行甲板邊緣和內(nèi)部依次按最大密度排布的方式進(jìn)行計(jì)算。首先利用啟發(fā)式靠邊定位算法對(duì)甲板邊緣處的飛機(jī)進(jìn)行布列，直到飛行甲板邊緣無(wú)法超邊界布列飛機(jī)；然后采用機(jī)庫(kù)最大密度布列飛機(jī)的NFP算法，對(duì)飛行甲板內(nèi)部的飛機(jī)進(jìn)行排樣，直到甲板內(nèi)布滿飛機(jī)。飛行甲板艦載機(jī)排樣的算法流程如圖11所示。

圖11 超邊界約束下的艦載機(jī)布列算法流程圖Fig.11 The algorithm workflow for aircraft spotting under the constraint of overlapping the boundary

啟發(fā)式靠邊定位算法的主要思想為：對(duì)于邊L1（圖12），將甲板的最左最下位置作為“零件局部最優(yōu)”位置，沿L1的反方向采用該定位策略逐一布列艦載機(jī)，直至沿該方向無(wú)法布列艦載機(jī)為止；之后先后沿L2～L4的反方向采用類似的方式放置剩下的艦載機(jī)，只不過它們的“零件局部最優(yōu)位置”則分別更新為最右最下位置、最右最上位置、最左最上位置，最終完成甲板邊緣所有艦載機(jī)的布列。

圖12 啟發(fā)式靠邊定位算法流程圖Fig.12 The workflow of heuristic algorithm for keep-to-the-boundary spotting

基于該算法的飛行甲板邊緣艦載機(jī)最大密度布列的具體步驟如下（圖12）：

1） 以飛行甲板的艉部最右側(cè)為起點(diǎn)，沿著右側(cè)甲板邊緣，按自艉向艏的方向，基于最艉最右位置為“零件局部最優(yōu)”位置為原則開始布放飛機(jī)，直到該方向無(wú)法布列飛機(jī)。

2） 沿著艏部、左舷等甲板邊緣，分別基于最艏最右、最艏最左位置為“零件局部最優(yōu)”位置，完成飛行甲板邊緣艦載機(jī)的布列。

5 算法實(shí)驗(yàn)結(jié)果

利用上述算法對(duì)F/A-18C飛機(jī)進(jìn)行最大密度布列（圖13），其中飛行甲板和機(jī)庫(kù)的外形尺寸及邊界根據(jù)文獻(xiàn)[13]確定，飛行甲板和機(jī)庫(kù)分別布列了76架和53架，總計(jì)129架飛機(jī)，與美軍公布的飛行甲板和機(jī)庫(kù)可最大密度布列130架F/A-18C飛機(jī)[14]基本吻合。

圖13 F/A-18C飛機(jī)在飛行甲板和機(jī)庫(kù)的最大布列圖Fig.13 Maximum spotting pattern of the F/A-18C aircraft on the flight and hangar deck

以F/A-18C飛機(jī)為基準(zhǔn)艦載機(jī)，對(duì)F-35C飛機(jī)進(jìn)行最大密度布列（圖14），飛行甲板和機(jī)庫(kù)分別布列了69架和46架機(jī)，即可最大布列115架F-35C飛機(jī)，根據(jù)定義，其布列因子為1.12，與美軍公布的F-35C飛機(jī)布列因子[4]為1.11基本相當(dāng)。

圖14 F-35C飛機(jī)在飛行甲板和機(jī)庫(kù)的最大布列圖Fig.14 Maximum spotting pattern of the F-35C aircraft on the flight and hangar deck

6 結(jié) 語(yǔ)

本文以最低重心NFP算法為基礎(chǔ)，針對(duì)艦載機(jī)最大密度布列的距離和超邊界約束進(jìn)行分析，提出了距離約束的數(shù)學(xué)模型及處理策略，以及利用啟發(fā)式靠邊定位算法來(lái)處理超邊界約束，并基于飛行甲板和機(jī)庫(kù)艦載機(jī)布列具體約束，分別提出了飛行甲板和機(jī)庫(kù)最大密度布列的算法。利用該算法得到“尼米茲”航母可最大密度布列129架F/A-18C或115架F-35C飛機(jī)，以及F-35C飛機(jī)布列因子為1.12等有意義的結(jié)論，與美軍相關(guān)文獻(xiàn)公布的艦載機(jī)布列數(shù)據(jù)基本吻合，證明了算法的實(shí)用性。