曾強(qiáng)，陳永鋒，袁瑞甫，趙水晶

(1.河南理工大學(xué)工商管理學(xué)院能源經(jīng)濟(jì)研究中心，河南焦作 454000；2.河南理工大學(xué)能源科學(xué)與工程學(xué)院，河南焦作 454000)

0 前言

設(shè)施布局是指在給定的空間與約束條件下，將生產(chǎn)所需的設(shè)施進(jìn)行合理組合和安排，以便經(jīng)濟(jì)高效地為企業(yè)的生產(chǎn)運(yùn)作活動(dòng)服務(wù)[1]。現(xiàn)有研究表明，合理的設(shè)施布局可以有效降低10%～30%物料搬運(yùn)成本、加快物料處理效率、減少在制品數(shù)量、縮短產(chǎn)品生產(chǎn)周期[2-3]。因此，開展制造業(yè)設(shè)施布局優(yōu)化研究具有重要意義。

多行設(shè)施布局具有節(jié)約生產(chǎn)空間、物料傳輸柔性高、搬運(yùn)設(shè)備利用率高等優(yōu)點(diǎn)[4]，因此引起了國內(nèi)外學(xué)者的廣泛關(guān)注和研究。多行設(shè)施布局中分布有橫向通道和縱向通道(統(tǒng)稱為通道)，設(shè)施間的物料流動(dòng)均沿通道運(yùn)行。目前針對通道數(shù)量、位置均不確定及設(shè)施縱橫比可柔性變化情況的研究較少。董舒豪等[5-6]先后針對縱向通道數(shù)量已知但位置不確定和縱向通道數(shù)量及位置均不確定的兩個(gè)問題進(jìn)行了研究，但均是基于設(shè)施長寬固定和橫向通道位置及數(shù)量已知的前提。李玉蘭、李波[7]構(gòu)建了帶有搬運(yùn)設(shè)備空載成本的優(yōu)化模型，但設(shè)施間物料搬運(yùn)距離采用曼哈頓距離，并沒有考慮物流通道，使得布局方案有可能無法滿足實(shí)際需求。此外，通道數(shù)量和位置不僅直接影響設(shè)施間的物料搬運(yùn)距離，而且對布局面積有一定影響。通道數(shù)量過少會(huì)增加設(shè)施間的物料搬運(yùn)距離，通道數(shù)量過多則會(huì)直接增加占地面積成本，因此在布局過程中需要綜合考慮通道的數(shù)量和位置。

多行設(shè)施布局是一個(gè)NP-hard問題，故啟發(fā)式算法是求解該類問題的常用方法[8]。目前已在多行設(shè)施布局問題中應(yīng)用的啟發(fā)式算法有遺傳算法[7，9-10]、粒子群優(yōu)化算法[11-12]、蛙跳算法[13]、模擬退火算法[14]、珊瑚礁算法[15]等。其中，遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法。在遺傳算法中，編碼方式、交叉算子、變異算子在很大程度上決定了種群的遺傳進(jìn)化方向及遺傳進(jìn)化的效率，因此這三者的設(shè)計(jì)至關(guān)重要[16]。CHENG等[9]結(jié)合切片結(jié)構(gòu)編碼方式采用遺傳算法對設(shè)施布局問題進(jìn)行仿真實(shí)驗(yàn)，證明了遺傳算法能夠有效解決該類問題。HASDA等[10]對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，提出交換算子和旋轉(zhuǎn)算子，降低了搜索空間，提高了算法性能。李玉蘭、李波[7]采用單親遺傳方式和單點(diǎn)交換的交叉算子對小規(guī)模設(shè)施布局問題進(jìn)行求解，指出了單點(diǎn)交換的交叉算子搜索性能更好。因此，編碼方式、交叉算子、變異算子的設(shè)計(jì)是遺傳算法能否有效求解設(shè)施布局類問題的關(guān)鍵。

綜合考慮多行設(shè)施布局過程中通道數(shù)量、位置均不確定及設(shè)施縱橫比在滿足最大縱橫比約束的情況下對物料搬運(yùn)成本和整體布局面積的影響，建立以物流成本、搬運(yùn)設(shè)備空載成本及占地面積成本的加權(quán)平均值最小化為優(yōu)化目標(biāo)的布局優(yōu)化模型，設(shè)計(jì)一種基于柔性隔間結(jié)構(gòu)(Flexible Bay Structure，F(xiàn)BS)編碼的改進(jìn)自適應(yīng)遺傳算法(Improved Adaptive Genetic Algorithm，IAGA)，對該模型進(jìn)行求解。

1 數(shù)學(xué)模型構(gòu)建

1.1 問題描述

在有限的區(qū)域內(nèi)分行布置n個(gè)設(shè)施，每相鄰兩行設(shè)施之間存在一條橫向通道，中間行(除第一行和最后一行)中的每行至少存在一個(gè)縱向通道。假設(shè)如下：(1)所有設(shè)施均可看作規(guī)則的矩形；(2)所有設(shè)施面積和最大縱橫比均為已知的固定值；(3)所有設(shè)施的物料搬運(yùn)點(diǎn)均位于設(shè)施的中心點(diǎn)；(4)通道寬度為已知的固定值，且通道位置和數(shù)量可變；(5)設(shè)施布局方向已知。在以上假設(shè)條件下，為車間生產(chǎn)提供一個(gè)以物流成本、搬運(yùn)設(shè)備空載成本及占地面積成本的加權(quán)平均值最小的設(shè)施布局方案。

1.2 變量定義

為方便描述布局優(yōu)化模型，定義了如表1所示的變量。

表1 變量定義

1.3 優(yōu)化模型

1.3.1 優(yōu)化目標(biāo)

以物流成本、搬運(yùn)設(shè)備空載成本及占地面積成本的加權(quán)平均值最小化為優(yōu)化目標(biāo)，建立的目標(biāo)函數(shù)如式(1)所示：

minc=w1×op1+w2×op2+w3×op3

(1)

(1)物流成本的量化

物流成本是指各個(gè)設(shè)施間的物流量、單位物流成本及搬運(yùn)距離三者的乘積之和，按式(2)進(jìn)行量化。

(2)

其中：設(shè)施間搬運(yùn)距離采用文獻(xiàn)[6]提出的3種方式(同行搬運(yùn)、鄰行搬運(yùn)及跨行搬運(yùn))進(jìn)行度量，如圖1所示。

圖1 三種搬運(yùn)方式示意

假設(shè)從設(shè)施i搬運(yùn)物料至設(shè)施j，則同行搬運(yùn)距離和鄰行搬運(yùn)距離分別按式(3)和式(4)計(jì)算：

dij=|xi-xj|+|yi-y′i|+|yj-y′j|

(3)

d′ij=|xi-xj|+|yi-yj|

(4)

其中：y′i表示距離設(shè)施i最近的橫向通道中心點(diǎn)的縱坐標(biāo)。

跨行搬運(yùn)可能存在多條路徑如圖1(c)所示，在搬運(yùn)過程中需選擇最短路徑。采用鄰接圖對可行路徑進(jìn)行表示。以設(shè)施i、設(shè)施j及兩設(shè)施所在行之間的縱向通道的中心點(diǎn)作為節(jié)點(diǎn)，鄰行之間的節(jié)點(diǎn)是可達(dá)的，其權(quán)重為兩節(jié)點(diǎn)間的距離，跨行節(jié)點(diǎn)為不可達(dá)，其權(quán)重為無窮大，記為∞。圖1(c)的鄰接圖和可達(dá)矩陣如圖2所示。采用floyd算法[17]求解最短路徑。

圖2 跨行搬運(yùn)方式的鄰接圖與可達(dá)矩陣

(2)搬運(yùn)設(shè)備空載成本的量化

(5)

(6)

(7)

(3)占地面積成本的量化

設(shè)施布局占地面積是指當(dāng)前布局下的最小包絡(luò)矩形的面積，按式(8)進(jìn)行量化：

op3=λ2×l′×w′

(8)

其中，l′和w′分別按式(9)和式(10)計(jì)算：

(9)

(10)

1.3.2 約束條件

模型的約束條件如式(11)—(17)所示：

(11)

(12)

(13)

(14)

s+v=1

(15)

s，v∈[0，1]

(16)

(17)

其中：i，j∈[1，2，…，n]；k∈[1，2，…，r]；ΔS為松弛變量。式(11)表示所有設(shè)施尺寸滿足最大縱橫比和面積約束；式(12)(13)表示所有設(shè)施均不超出規(guī)定的布置區(qū)域；式(14)—(16)表示任意設(shè)施間不發(fā)生干涉；式(17)表示第一行和最后一行不存在縱向通道，中間行至少存在一個(gè)縱向通道。

2 改進(jìn)自適應(yīng)遺傳算法設(shè)計(jì)

2.1 IAGA算法流程

圖3 IAGA算法流程

2.2 FBS編碼及解碼

柔性隔間結(jié)構(gòu)(FBS)編碼是由前、中、后三段構(gòu)成，前段是長度為n的設(shè)施編號(hào)排列，中段是長度為n的隔間結(jié)構(gòu)，后段是不定長度的縱向通道位置信息。根據(jù)布局編碼信息從左到右、從上到下依次放置設(shè)施，解碼過程如圖4所示，其中縱向通道位置(3，0)和(4，1)分別表示在位置3前插入縱向通道和位置4后加入通道。每行設(shè)施的長(平行于x軸的邊長)和寬(平行于y軸的邊長)分別按照式(18)和式(19)計(jì)算：

(18)

圖4 布局編碼及解碼示意

(19)

(20)

(21)

a1，a2，…，ank∈ψk

(22)

2.3 適應(yīng)度函數(shù)

個(gè)體適應(yīng)度按式(23)計(jì)算：

f(x)=1/(φ×op1+op2+op3)

(23)

其中：φ為懲罰系數(shù)，若當(dāng)前解同時(shí)滿足約束式(12)和約束式(13)，則φ=1，否則φ>1。

2.4 自適應(yīng)交叉操作

基本遺傳算法在種群進(jìn)化過程中往往采用固定的交叉概率和單一的交叉算子。較高的交叉概率在種群進(jìn)化前期能夠快速篩除較差的個(gè)體，但在種群進(jìn)化后期，個(gè)體適應(yīng)度趨于平均值，全局的搜索需求降低，較高的交叉概率則容易破壞適應(yīng)度較高的個(gè)體且單一的交叉算子難以兼顧全局搜索能力和局部搜索能力，導(dǎo)致在求解多峰值優(yōu)化問題時(shí)易早熟。因此，采用自適應(yīng)交叉概率方式[19-20]，動(dòng)態(tài)調(diào)整交叉概率pc，適應(yīng)度越高的個(gè)體發(fā)生交叉的概率越低，反之亦然。自適應(yīng)交叉概率pc按式(24)取值：

pc=

(24)

針對適應(yīng)度較低的個(gè)體和適應(yīng)度較高的個(gè)體分別設(shè)計(jì)了雙點(diǎn)交叉算子和單親單點(diǎn)交換算子。雙點(diǎn)交叉算子可以對個(gè)體進(jìn)行較大范圍擾動(dòng)，保證了種群進(jìn)化過程中的個(gè)體多樣性，提高算法全局搜索能力，如圖5所示；單親單點(diǎn)交換算子可以對個(gè)體進(jìn)行小范圍擾動(dòng)，不易破壞個(gè)體結(jié)構(gòu)，提高算法局部搜索能力，如圖6所示。在種群進(jìn)化過程中，以概率ps選擇雙點(diǎn)交叉算子，以1-ps概率選擇單親單點(diǎn)交叉算子。文中ps取值與pc相同。

圖5 雙點(diǎn)交叉示意

圖6 單親單點(diǎn)交換示意

2.5 變異操作

分別針對設(shè)施編號(hào)排列和FBS編碼設(shè)計(jì)了兩種變異策略，在種群進(jìn)化過程中以等概率隨機(jī)選擇一種變異策略進(jìn)行變異操作。

FBS編碼變異：隨機(jī)選擇需變異個(gè)體FBS編碼中的任意一個(gè)基因值進(jìn)行取反操作(原值為0則置為1，原值為1則置為0)。

設(shè)施編號(hào)排列變異：隨機(jī)選擇需變異個(gè)體設(shè)施編號(hào)排列中的任意兩個(gè)設(shè)施編號(hào)進(jìn)行置換。

2.6 通道的更新

通道更新目的是確定當(dāng)前個(gè)體的通道位置和數(shù)量。通道的更新步驟如下：

步驟1，依次為中間行的每一行隨機(jī)生成一個(gè)縱向通道，并作為初始解x0。

步驟2，若不滿足約束式(13)，且krow>1，則隨機(jī)刪除當(dāng)前布局的一條橫向通道，跳轉(zhuǎn)到步驟1，否則執(zhí)行下一步。

步驟3，若不滿足約束式(13)，且krow≤1，則重新生成布局編碼，跳轉(zhuǎn)到步驟1，否則執(zhí)行下一步。

步驟4，設(shè)置循環(huán)計(jì)數(shù)器初值t=1。

步驟5，隨機(jī)選擇中間行中的任意一行，以同等概率選擇以下3種方式之一獲得新解xnew。

方式一：為該行隨機(jī)添加新的縱向通道。

方式三：隨機(jī)選擇當(dāng)前行的一個(gè)縱向通道重新生成其位置。

步驟6，若xnew不滿足約束式(13)或f(xnew)

步驟7，若t

3 案例分析

將上述IAGA算法采用Java語言實(shí)現(xiàn)。為了驗(yàn)證文中所提方法的有效性，引用文獻(xiàn)[6]中的案例進(jìn)行分析。該案例中共有18個(gè)設(shè)施需要布置在長64 m、寬41 m的區(qū)域內(nèi)，通道寬度為3 m。各個(gè)設(shè)施面積及最大縱橫比如表2所示。所有設(shè)施間的單位距離搬運(yùn)成本均取值為1元/(t·m)。設(shè)施間的物流量如表3所示，未列出的設(shè)施間物流量為0。

表2 設(shè)施面積和最大縱橫比

表3 設(shè)施間物流量 單位：t Tab.3 Logistics volume between facilities Unit：t

式(1)中權(quán)重系數(shù)由專家打分法得出，分別為w1=0.5，w2=0.25，w3=0.25，取空載系數(shù)λ1=0.7、單位面積成本系數(shù)λ2=2。取種群大小m=80，進(jìn)化代數(shù)ngen=1 000，交叉概率參數(shù)p′c=0.8、最大交叉概率pmax=1，最小交叉概率pmin=0.5，變異概率pm=0.1，懲罰系數(shù)φ=2。

在一臺(tái)配置為Intel(R)Core(TM)i5-10210U CPU@1.60 GHz 2.11 GH及8.0 GB內(nèi)存的計(jì)算機(jī)上獨(dú)立運(yùn)行IAGA算法20次，將所得到的最優(yōu)解與原文獻(xiàn)[6]中隨機(jī)密鑰蝙蝠算法(Random-Key Bat Algorithm，RKBA)獨(dú)立運(yùn)行20次的最優(yōu)解進(jìn)行比較，結(jié)果如表4所示。RKBA算法最優(yōu)布局如圖7所示，IAGA算法最優(yōu)布局如圖8所示。

圖7 RKBA最優(yōu)設(shè)施布局

圖8 IAGA最優(yōu)設(shè)施布局

表4 IAGA與RKBA運(yùn)行結(jié)果

從表4可知：IAGA算法所得最優(yōu)解優(yōu)于RKBA算法，節(jié)約占地面積315.37 m2。表明IAGA算法能夠有效求解帶有最大縱橫比約束的橫向和縱向通道數(shù)量和位置均不確定的多行設(shè)施布局模型。

僅采用單親單點(diǎn)交換算子的基本遺傳算法(GAO)、僅采用雙點(diǎn)交叉算子的基本遺傳算法(GAT)及IAGA算法分別獨(dú)立運(yùn)行20次的對比結(jié)果如表5所示，3種算法對應(yīng)的進(jìn)化圖和20次運(yùn)行結(jié)果對比分別如圖9和圖10所示。

圖9 三種算法的最優(yōu)進(jìn)化圖

圖10 三種算法獨(dú)立運(yùn)行20次結(jié)果對比

表5 三種算法運(yùn)行20次結(jié)果對比 單位：元

從圖9、圖10和表5可知：GAO算法運(yùn)行穩(wěn)定性最差，表明該算法全局搜索能力較差，容易陷入局部最優(yōu)；GAT算法收斂速度和求解質(zhì)量最差，種群進(jìn)化后期乏力，表明該算法局部搜索能力較差；IAGA算法運(yùn)行結(jié)果最為穩(wěn)定且最優(yōu)解對應(yīng)的總目標(biāo)成本最低，收斂速度較快，搜索能力較強(qiáng)，表明該算法在求解文中所提的布局優(yōu)化模型上表現(xiàn)出更好的性能。

4 結(jié)束語

針對橫向和縱向通道位置和數(shù)量均不確定的多行設(shè)施布局問題，提出一種基于IAGA的多行設(shè)施布局優(yōu)化方法。通過研究得出如下結(jié)論：

(1)構(gòu)建的通道位置和數(shù)量均不確定的多行設(shè)施布局優(yōu)化模型，考慮了設(shè)施最大縱橫比約束，該模型以物流成本、搬運(yùn)設(shè)備空載成本及占地面積成本的加權(quán)平均值最小化為優(yōu)化目標(biāo)，能較好地反映實(shí)際需求。

(2)設(shè)計(jì)的基于FBS編碼的改進(jìn)自適應(yīng)遺傳算法，能有效求解通道位置和數(shù)量均不確定的多行設(shè)施布局優(yōu)化模型。算法中設(shè)計(jì)的FBS編碼方式能夠有效表示設(shè)施的位置信息，更容易生成適應(yīng)度較高的個(gè)體。針對基本遺傳算法對于多峰值問題求解時(shí)容易早熟現(xiàn)象，設(shè)計(jì)了自適應(yīng)交叉概率、自適應(yīng)選擇雙點(diǎn)交叉算子和單親單點(diǎn)交換算子、針對隔間結(jié)構(gòu)和設(shè)施編號(hào)排列的基本位變異算子，提高了算法性能。