基于果蝇优化算法的备件柜布局优化*

王尚龙，王崴，2，瞿珏，刘明

（1.空军工程大学防空反导学院，西安710051；2.西安交通大学机械制造系统工程国家重点实验室，西安710049）

基于果蝇优化算法的备件柜布局优化*

王尚龙1，王崴1，2，瞿珏1，刘明1

（1.空军工程大学防空反导学院，西安710051；2.西安交通大学机械制造系统工程国家重点实验室，西安710049）

备件车是保障维护其他装备正常运行的车辆，其备件柜的布局是否优化决定备件的更换速率，甚至影响整个系统的工作效率。针对备件柜的布局进行了深入研究，并通过计算实现了备件柜的布局分布。在备件柜的布局优化过程中运用了剩余矩形匹配的布局策略，并结合备件柜的布局特点对该算法进行了相应改进，使其更好地运用在本研究的布局问题中。同时运用果蝇优化算法来确定剩余矩形匹配权重的计算，在布局过程中将传统的布局策略和智能算法相结合以达到优化的目的。

备件车，布局优化，剩余矩形匹配算法，果蝇算法

0 引言

通用备件车是一种新型通用的备件器材装载平台，可完成武器装备的机械备件、液压件及电子元件的储存和运输，可实现备件的计算机管理，可作为部队（仓库）周转器材的储运平台，是地空导弹武器系统的直接支援车辆，在军事装备中有重要的作用。通用备件车主要由军用越野汽车底盘、备件舱、备件柜、工作台、备件管理系统、配电系统、空气调节系统、驻车自取力发电与控制系统等组成。其中备件舱是该备件车功能实现的核心部件，用来装载其他操作设备和各种备件。因此，备件舱中的备件布局优化问题显得尤为重要，备件布局的优化决定了整个系统的效率，同时给操作人员也带来了便利。所有的备件都是装载在不同类型的备件柜中，各备件柜的优化与否决定了舱的空间利用率，同时备件柜的优化是备件得以优化的保障。该问题可描述为在一定体积的空间中如何实现备件柜的布局，使备件柜在整个舱中所占空间较小，提高备件舱的空间利用率，提升备件车的运用价值。

备件柜的总体结构是三维模型，而在布局的过程中只考虑备件柜正前方的矩形即可，因此，该布局问题实则属于二维布局问题。二维布局问题的研究取得了一定的成就，提出了许多算法。如：通过寻找矩形在空间中的可行域来确定待布矩形的位置［1］；提出以站角和凹陷程度为启发性规则的启发性算法［2］；在布局过程中采用最下最左原则［3］等。同时也已经将智能算法融入到了布局优化求解中，如：遗传算法在下料模型的使用［4］、约束问题中的粒子群算法［5-6］、各种改进的智能算法［7-8］以及其他布局算法［9］。

1 果蝇优化算法

果蝇优化算法是由Wen-TsaoPan提出的基于果蝇觅食行为推出的寻求全局优化的方法［10］。果蝇的嗅觉特别灵敏，能够感觉到40 km以外的食物源和气味，并向产生该气味的方向靠拢，同时向其他同伴靠拢，最后利用视觉发现食物和同伴聚集的位置。其基本步骤如下：

①随机初始果蝇群体位置：

②赋予个体利用嗅觉搜寻食物的随机方向和距离：

③估计与原点的距离（Dist），以求出该果蝇个体位置的味道浓度（S）（距离的倒数）：

④将味道浓度判定值（S）代入味道浓度判定函数以求出该果蝇个体位置的味道浓度（Smelli）：

⑤找出此果蝇群体中味道浓度最高的果蝇（求极大值）：

⑥保留最佳味道浓度值与x、y坐标，群体会向该位置飞去，形成新的群聚位置：

⑦迭代寻优，重复以上步骤，并判断味道浓度是否优于前一次迭代味道浓度，若是则执行（6）。

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

根据本问题的特点，本文运用了剩余矩形匹配的算法来求解备件柜的优化［11］。剩余矩形匹配算法在二维布局和下料中都取得了有效的运用，该方法的基本思想是在一个固定面积的矩形中，通过每个待布物依次与所剩矩形空间之间的匹配来选择待布物在所有剩余矩形中的具体位置，在匹配的过程中强调了面积和边的两者共同组合匹配的原则，通过选择匹配度最高的面积，确定待布矩形的布局位置。基本步骤如下：

①将要布入的小矩形块按照面积大小依次进行排序，并依次记为Ri（i=1，2，…n）；

②以大矩形的整个面积为第1个剩余矩形，且该剩余面积只有一个，只需将第1个要布入的小矩形块R1根据约束要求放入该大矩形中，规定其放入的位置为小矩形的左下角的顶点和大矩形的左下角的顶点重合；

③由于在大矩形中已经布入了一个小矩形的缘故，在剩余的空间中就会产生两个矩形面积。对剩余区域矩形的划分方法不同，将会产生两种不同的矩形面积，分别如图1所示，依次来分析所有可能出现的剩余矩形。

设第1个矩形R1的长为a，宽为b，整个大矩形的左下角顶点的坐标为（x0，y0），右上角的顶点坐标为（x1，y1），以两个顶点的坐标来表示矩形，从而可定义其剩余矩形分别为：

④根据剩余矩形面积匹配的准则，将第2 个要放入的矩形块R2依次放入4 个剩余矩形中，根据如下公式计算出最大值：

然后根据计算结果，选取4个矩形中匹配度最高的那个剩余矩形作为第2个矩形R2的布局位置；

⑤第2个布入的规则依旧是该矩形块的左下角的顶点与所选择的剩余矩形的顶点重合；

⑥继续划分剩余矩形，当布入的矩形为n时，其相应的剩余矩形就为n+1，依次按照上述方法将所有矩形布入大矩形中为止。

以上是传统剩余矩形的匹配算法，在该算法中开始选择的矩形会对后续矩形的选择造成影响，即后面的矩形选择会受到前面矩形的约束。而本文在此基础上进行改进，每次对剩余矩形划分的时候不受前面矩形的影响，重新对所有矩形进行划分，以选择出适合当前矩形的剩余区域。如图1为例进行说明，如果在布入第1个矩形R1的过程中选取了图中的剩余矩形r，传统剩余矩形算法在之后的选择中不能选择图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区域无法布入R3，因此，不予考虑。比较上式的结果，r6的匹配度最高。从而可得，按传统的算法可能会错过一些匹配度更高的矩形区域，本文在运用剩余矩形算法的过程中，会根据要布入矩形的大小重新划分矩形区域，使其在计算过程中找到匹配度更高的矩形区域。

3 备件柜的布局优化

3.1 问题描述

通用备件车的备件舱用来存放备件和其他设备，因此，备件柜的优化将决定其他设备的存放和整舱的规划。备件舱的整体尺寸为（长×宽×高）：6 000 mm×2 000 mm×2 400 mm。要布入该备件舱的备件柜从结构上划分有：便携式备件箱、大抽屉、小抽屉，其各自的数量分别为28，8，36。便携式备件箱虽有方便携带的挂钩，但整体结构依旧是长方体。根据需要每种类型的备件柜又有不同的尺寸大小，备件柜尺寸和类型的不同给布局增加了一定的难度。各备件柜的具体类型和尺寸如下页表1所示。

该问题需要把这些不同尺寸的备件柜布入整个备件舱中，使其所占空间最小。由于整个备件舱要方便操作人员工作以及通行，因此，将备件柜分别布在备件舱的两侧，中间留出相应的通道。根据此要求可以进行以下操作，把备件柜均匀地分成两组，在计算的过程中只考虑备件舱一侧的备件柜布局即可，另一侧可按相同的结果进行布局。结合备件要方便取存的特点，备件柜必须不能相互干涉，且各备件柜的口全部靠向里侧以方便工作人员操作。从而，该问题转化为将其中的36个矩形布在一个大小为2 400 mm×6 000 mm的矩形中，使其所占面积较小。

表1 便携式备件箱及抽屉规格

3.2 布局优化

3.2.1 布局约束和要求

结合具体情况，制定该问题的布局约束和具体要求：

①必须将36个不同型号的备件柜全部布在备件舱的一侧；

②各备件柜之间不能相互重叠；

③每个备件柜布入的形式只有一种，即小矩形块的长边必须要和大矩形的长边平行且柜子的底部向下；

④为使备件柜占的空间小，规定布局的过程中各备件柜必须填满该矩形宽边方向的空间，使其在矩形的长边方向所占的空间尽可能少。

3.2.2 布局结果

由图5计算结果可以得出m=0.160 7，当取得最大值时对应的果蝇的坐标为x=2.192 5，y=1.126 9，据此可以算得=0.4。

由图6计算结果可以得出m=0.984 7，当取得最大值时对应的果蝇的坐标为x=2.376 5，y=4.66，据此可以算得=0.2。

由图7计算结果可以得出m=0.257 2，当取得最大值时对应的果蝇的坐标为x=3.893 1，y=2.942 4，据此可以算得=0.2。

在图8中，由于大矩形的长较长，只取了其中的一部分，其余矩形及大矩形的宽均按比例所取。在实际操作中，可按该方案分别对备件舱的两侧进行布局。

4 结论

本文针对通用备件车中备件柜的布局优化问题，提出了改进的剩余矩形匹配算法的布局策略。在剩余矩形匹配算法中利用了果蝇优化算法，通过该算法算得面积匹配度。最后通过计算匹配度最高的矩形区域，将各备件柜布在备件舱中，从而使得备件舱的空间利用比较合理。

本文探讨了规则的备件柜布局问题，下一步将会研究非规则的备件布局，以及如何实现将备件布在已布的备件柜中，将是今后深入研究探讨的问题。

［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］陈勇，王玫.采用遗传算法的矩形件优化下料模型［J］.现代制造工程，2009，31（1）：63-66.

［5］周驰，高亮.基于粒子群优化算法的约束布局优化［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］潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估［J］.太原理工大学学报（社会科学版），2011，29（4）：1-5．

［11］曾凤华.剩余矩形匹配算法在矩形件排样中的应用［J］.机电工程技术，2006，35（3）：64-65．

［11］吴坤，康建设，杨东.果蝇算法优化的相关向量机在电子装备中的应用［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-），男，甘肃平凉人，硕士研究生。研究方向：虚拟现实及机械系统优化设计。