基于果蠅優(yōu)化算法的備件柜布局優(yōu)化*

王尚龍，王崴，2，瞿玨，劉明

（1.空軍工程大學防空反導學院，西安710051；2.西安交通大學機械制造系統(tǒng)工程國家重點實驗室，西安710049）

基于果蠅優(yōu)化算法的備件柜布局優(yōu)化*

王尚龍1，王崴1，2，瞿玨1，劉明1

（1.空軍工程大學防空反導學院，西安710051；2.西安交通大學機械制造系統(tǒng)工程國家重點實驗室，西安710049）

備件車是保障維護其他裝備正常運行的車輛，其備件柜的布局是否優(yōu)化決定備件的更換速率，甚至影響整個系統(tǒng)的工作效率。針對備件柜的布局進行了深入研究，并通過計算實現(xiàn)了備件柜的布局分布。在備件柜的布局優(yōu)化過程中運用了剩余矩形匹配的布局策略，并結合備件柜的布局特點對該算法進行了相應改進，使其更好地運用在本研究的布局問題中。同時運用果蠅優(yōu)化算法來確定剩余矩形匹配權重的計算，在布局過程中將傳統(tǒng)的布局策略和智能算法相結合以達到優(yōu)化的目的。

備件車，布局優(yōu)化，剩余矩形匹配算法，果蠅算法

0 引言

通用備件車是一種新型通用的備件器材裝載平臺，可完成武器裝備的機械備件、液壓件及電子元件的儲存和運輸，可實現(xiàn)備件的計算機管理，可作為部隊（倉庫）周轉器材的儲運平臺，是地空導彈武器系統(tǒng)的直接支援車輛，在軍事裝備中有重要的作用。通用備件車主要由軍用越野汽車底盤、備件艙、備件柜、工作臺、備件管理系統(tǒng)、配電系統(tǒng)、空氣調節(jié)系統(tǒng)、駐車自取力發(fā)電與控制系統(tǒng)等組成。其中備件艙是該備件車功能實現(xiàn)的核心部件，用來裝載其他操作設備和各種備件。因此，備件艙中的備件布局優(yōu)化問題顯得尤為重要，備件布局的優(yōu)化決定了整個系統(tǒng)的效率，同時給操作人員也帶來了便利。所有的備件都是裝載在不同類型的備件柜中，各備件柜的優(yōu)化與否決定了艙的空間利用率，同時備件柜的優(yōu)化是備件得以優(yōu)化的保障。該問題可描述為在一定體積的空間中如何實現(xiàn)備件柜的布局，使備件柜在整個艙中所占空間較小，提高備件艙的空間利用率，提升備件車的運用價值。

備件柜的總體結構是三維模型，而在布局的過程中只考慮備件柜正前方的矩形即可，因此，該布局問題實則屬于二維布局問題。二維布局問題的研究取得了一定的成就，提出了許多算法。如：通過尋找矩形在空間中的可行域來確定待布矩形的位置［1］；提出以站角和凹陷程度為啟發(fā)性規(guī)則的啟發(fā)性算法［2］；在布局過程中采用最下最左原則［3］等。同時也已經將智能算法融入到了布局優(yōu)化求解中，如：遺傳算法在下料模型的使用［4］、約束問題中的粒子群算法［5-6］、各種改進的智能算法［7-8］以及其他布局算法［9］。

1 果蠅優(yōu)化算法

果蠅優(yōu)化算法是由Wen-TsaoPan提出的基于果蠅覓食行為推出的尋求全局優(yōu)化的方法［10］。果蠅的嗅覺特別靈敏，能夠感覺到40 km以外的食物源和氣味，并向產生該氣味的方向靠攏，同時向其他同伴靠攏，最后利用視覺發(fā)現(xiàn)食物和同伴聚集的位置。其基本步驟如下：

①隨機初始果蠅群體位置：

②賦予個體利用嗅覺搜尋食物的隨機方向和距離：

③估計與原點的距離（Dist），以求出該果蠅個體位置的味道濃度（S）（距離的倒數(shù)）：

④將味道濃度判定值（S）代入味道濃度判定函數(shù)以求出該果蠅個體位置的味道濃度（Smelli）：

⑤找出此果蠅群體中味道濃度最高的果蠅（求極大值）：

⑥保留最佳味道濃度值與x、y坐標，群體會向該位置飛去，形成新的群聚位置：

⑦迭代尋優(yōu)，重復以上步驟，并判斷味道濃度是否優(yōu)于前一次迭代味道濃度，若是則執(zhí)行（6）。

2 剩余矩形匹配算法及其改進

根據(jù)本問題的特點，本文運用了剩余矩形匹配的算法來求解備件柜的優(yōu)化［11］。剩余矩形匹配算法在二維布局和下料中都取得了有效的運用，該方法的基本思想是在一個固定面積的矩形中，通過每個待布物依次與所剩矩形空間之間的匹配來選擇待布物在所有剩余矩形中的具體位置，在匹配的過程中強調了面積和邊的兩者共同組合匹配的原則，通過選擇匹配度最高的面積，確定待布矩形的布局位置。基本步驟如下：

①將要布入的小矩形塊按照面積大小依次進行排序，并依次記為Ri（i=1，2，…n）；

②以大矩形的整個面積為第1個剩余矩形，且該剩余面積只有一個，只需將第1個要布入的小矩形塊R1根據(jù)約束要求放入該大矩形中，規(guī)定其放入的位置為小矩形的左下角的頂點和大矩形的左下角的頂點重合；

③由于在大矩形中已經布入了一個小矩形的緣故，在剩余的空間中就會產生兩個矩形面積。對剩余區(qū)域矩形的劃分方法不同，將會產生兩種不同的矩形面積，分別如圖1所示，依次來分析所有可能出現(xiàn)的剩余矩形。

設第1個矩形R1的長為a，寬為b，整個大矩形的左下角頂點的坐標為（x0，y0），右上角的頂點坐標為（x1，y1），以兩個頂點的坐標來表示矩形，從而可定義其剩余矩形分別為：

④根據(jù)剩余矩形面積匹配的準則，將第2 個要放入的矩形塊R2依次放入4 個剩余矩形中，根據(jù)如下公式計算出最大值：

然后根據(jù)計算結果，選取4個矩形中匹配度最高的那個剩余矩形作為第2個矩形R2的布局位置；

⑤第2個布入的規(guī)則依舊是該矩形塊的左下角的頂點與所選擇的剩余矩形的頂點重合；

⑥繼續(xù)劃分剩余矩形，當布入的矩形為n時，其相應的剩余矩形就為n+1，依次按照上述方法將所有矩形布入大矩形中為止。

以上是傳統(tǒng)剩余矩形的匹配算法，在該算法中開始選擇的矩形會對后續(xù)矩形的選擇造成影響，即后面的矩形選擇會受到前面矩形的約束。而本文在此基礎上進行改進，每次對剩余矩形劃分的時候不受前面矩形的影響，重新對所有矩形進行劃分，以選擇出適合當前矩形的剩余區(qū)域。如圖1為例進行說明，如果在布入第1個矩形R1的過程中選取了圖中的剩余矩形r，傳統(tǒng)剩余矩形算法在之后的選擇中不能選擇圖1所示的r3和r4。本文改進了剩余矩形算法中對剩余矩形的選擇，以在一個12×11的大矩形中布入R1為8×3.5，R2為5.5×3.5，R3為3×3.5的3個小矩形為例說明。如圖2所示將R2布入到r1中：

分別計算每個剩余矩形匹配度為：

顯然，m1=m4，又在r2區(qū)域無法布入R3，因此，不予考慮。比較上式的結果，r6的匹配度最高。從而可得，按傳統(tǒng)的算法可能會錯過一些匹配度更高的矩形區(qū)域，本文在運用剩余矩形算法的過程中，會根據(jù)要布入矩形的大小重新劃分矩形區(qū)域，使其在計算過程中找到匹配度更高的矩形區(qū)域。

3 備件柜的布局優(yōu)化

3.1 問題描述

通用備件車的備件艙用來存放備件和其他設備，因此，備件柜的優(yōu)化將決定其他設備的存放和整艙的規(guī)劃。備件艙的整體尺寸為（長×寬×高）：6 000 mm×2 000 mm×2 400 mm。要布入該備件艙的備件柜從結構上劃分有：便攜式備件箱、大抽屜、小抽屜，其各自的數(shù)量分別為28，8，36。便攜式備件箱雖有方便攜帶的掛鉤，但整體結構依舊是長方體。根據(jù)需要每種類型的備件柜又有不同的尺寸大小，備件柜尺寸和類型的不同給布局增加了一定的難度。各備件柜的具體類型和尺寸如下頁表1所示。

該問題需要把這些不同尺寸的備件柜布入整個備件艙中，使其所占空間最小。由于整個備件艙要方便操作人員工作以及通行，因此，將備件柜分別布在備件艙的兩側，中間留出相應的通道。根據(jù)此要求可以進行以下操作，把備件柜均勻地分成兩組，在計算的過程中只考慮備件艙一側的備件柜布局即可，另一側可按相同的結果進行布局。結合備件要方便取存的特點，備件柜必須不能相互干涉，且各備件柜的口全部靠向里側以方便工作人員操作。從而，該問題轉化為將其中的36個矩形布在一個大小為2 400 mm×6 000 mm的矩形中，使其所占面積較小。

表1 便攜式備件箱及抽屜規(guī)格

3.2 布局優(yōu)化

3.2.1 布局約束和要求

結合具體情況，制定該問題的布局約束和具體要求：

①必須將36個不同型號的備件柜全部布在備件艙的一側；

②各備件柜之間不能相互重疊；

③每個備件柜布入的形式只有一種，即小矩形塊的長邊必須要和大矩形的長邊平行且柜子的底部向下；

④為使備件柜占的空間小，規(guī)定布局的過程中各備件柜必須填滿該矩形寬邊方向的空間，使其在矩形的長邊方向所占的空間盡可能少。

3.2.2 布局結果

由圖5計算結果可以得出m=0.160 7，當取得最大值時對應的果蠅的坐標為x=2.192 5，y=1.126 9，據(jù)此可以算得=0.4。

由圖6計算結果可以得出m=0.984 7，當取得最大值時對應的果蠅的坐標為x=2.376 5，y=4.66，據(jù)此可以算得=0.2。

由圖7計算結果可以得出m=0.257 2，當取得最大值時對應的果蠅的坐標為x=3.893 1，y=2.942 4，據(jù)此可以算得=0.2。

在圖8中，由于大矩形的長較長，只取了其中的一部分，其余矩形及大矩形的寬均按比例所取。在實際操作中，可按該方案分別對備件艙的兩側進行布局。

4 結論

本文針對通用備件車中備件柜的布局優(yōu)化問題，提出了改進的剩余矩形匹配算法的布局策略。在剩余矩形匹配算法中利用了果蠅優(yōu)化算法，通過該算法算得面積匹配度。最后通過計算匹配度最高的矩形區(qū)域，將各備件柜布在備件艙中，從而使得備件艙的空間利用比較合理。

本文探討了規(guī)則的備件柜布局問題，下一步將會研究非規(guī)則的備件布局，以及如何實現(xiàn)將備件布在已布的備件柜中，將是今后深入研究探討的問題。

［1］王金敏，張鵬程.矩形布局可行域的確定［J］.計算機輔助設計與圖形學報，2008，19（2）：246-252.

［2］HUANG W Q，CHEN D B，XU R C.A new heuristic algorithm forrectangle packing［J］.Computers&Operations Research，2007，34（11）：3270-3280.

［3］LIU D，TENG H.An improved BL algorithm for genetic al-gorithm of the orthogonal packing of rectangles［J］.Euro-peanJournalofOperationalResearch，1999，112：413-420.

［4］陳勇，王玫.采用遺傳算法的矩形件優(yōu)化下料模型［J］.現(xiàn)代制造工程，2009，31（1）：63-66.

［5］周馳，高亮.基于粒子群優(yōu)化算法的約束布局優(yōu)化［J］.控制與決策，2005，19（1）：36-40.

［6］REZAZADEH H.An extended discrete particle swarm optimization algorithmfor the dynamic facility layout problem［J］. Zhejiang UnivSci A，2009，10（4）：520-529.

［7］CHENG S，CHEN M Y.Optimal placement of distributed generation units indistribution systems via an enhanced multi-objectiveparticle swarm optimization algorithm［J］.Comput&Electron，2014，15（4）：300-311.

［8］付國江，王少梅.一種新型的粒子群算法［J］.計算機工程與應用，2005，42（23）：80-83.

［9］王金敏，簡其和.矩形布局問題中的群組策略［J］.計算機輔助設計與圖形學學報，2004，15（4）：572-575.

［10］潘文超.應用果蠅優(yōu)化算法優(yōu)化廣義回歸神經網絡進行企業(yè)經營績效評估［J］.太原理工大學學報（社會科學版），2011，29（4）：1-5．

［11］曾鳳華.剩余矩形匹配算法在矩形件排樣中的應用［J］.機電工程技術，2006，35（3）：64-65．

［11］吳坤，康建設，楊東.果蠅算法優(yōu)化的相關向量機在電子裝備中的應用［J］.火力與指揮控制，2016，41（3）：106-110.

Layout of the Spare Cabinets Based on Fruit Fly Optimization Algorithm

WANG Shang-long1，WANG Wei1，2，QU Jue1，LIU Ming1
（1.School of Air-Defense And Anti-Missile，Air Force Engineering University，Xi’an 710051，China；
2.State Key Laboratory for Manufacturing System Engineering，Xi’an Jiaotong University，Xi’an 710049，China）

The spare vehicle is used to maintain other equipment that can work normally.The layout of spare cabinets determines spare parts replacement rate，and affect the working efficiency of all equipment.To solve this problem，this paper deeply researches on the layout of spare cabinets and achieves the layout of cabinets distribution by using some algorithm.In this paper，the matching algorithm of remaining rectangular is applied in the layout of spare cabinets.In order to meet the layout requirements，the matching algorithm of remaining rectangular is improved.The fruit fly optimization algorithm is used to calculate parameters of matching algorithm of remaining rectangular. The traditional layout strategy and intelligent algorithmcombining method are used for layout of spare cabinets.

spare vehicle，layout optimization，matching algorithm of remaining rectangular，fruit fly optimization algorithm

TH69

A

1002-0640（2017）01-0066-05

2015-11-15

2016-02-07

中國博士后科學基金資助項目（133798）

王尚龍（1990-），男，甘肅平涼人，碩士研究生。研究方向：虛擬現(xiàn)實及機械系統(tǒng)優(yōu)化設計。