基于IAGA的多行設(shè)施布局優(yōu)化方法

曾強，陳永鋒，袁瑞甫，趙水晶

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

0 前言

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

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

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

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

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

1.1 問題描述

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

1.2 變量定義

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

表1 變量定義

1.3 優(yōu)化模型

1.3.1 優(yōu)化目標

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

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

(1)

(1)物流成本的量化

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

(2)

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

圖1 三種搬運方式示意

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

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

(3)

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

(4)

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

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

圖2 跨行搬運方式的鄰接圖與可達矩陣

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

(5)

(6)

(7)

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

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

op3=λ2×l′×w′

(8)

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

(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)表示第一行和最后一行不存在縱向通道，中間行至少存在一個縱向通道。

2 改進自適應遺傳算法設(shè)計

2.1 IAGA算法流程

圖3 IAGA算法流程

2.2 FBS編碼及解碼

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

(18)

圖4 布局編碼及解碼示意

(19)

(20)

(21)

a1，a2，…，ank∈ψk

(22)

2.3 適應度函數(shù)

個體適應度按式(23)計算：

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

(23)

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

2.4 自適應交叉操作

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

pc=

(24)

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

圖5 雙點交叉示意

圖6 單親單點交換示意

2.5 變異操作

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

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

設(shè)施編號排列變異：隨機選擇需變異個體設(shè)施編號排列中的任意兩個設(shè)施編號進行置換。

2.6 通道的更新

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

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

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

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

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

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

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

方式三：隨機選擇當前行的一個縱向通道重新生成其位置。

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

步驟7，若t

3 案例分析

將上述IAGA算法采用Java語言實現(xiàn)。為了驗證文中所提方法的有效性，引用文獻[6]中的案例進行分析。該案例中共有18個設(shè)施需要布置在長64 m、寬41 m的區(qū)域內(nèi)，通道寬度為3 m。各個設(shè)施面積及最大縱橫比如表2所示。所有設(shè)施間的單位距離搬運成本均取值為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，進化代數(shù)ngen=1 000，交叉概率參數(shù)p′c=0.8、最大交叉概率pmax=1，最小交叉概率pmin=0.5，變異概率pm=0.1，懲罰系數(shù)φ=2。

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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