基于隨機(jī)秘鑰蝙蝠算法的多行設(shè)施布局設(shè)計(jì)

董舒豪 徐志剛 秦開仲 常艷茹 蘇開遠(yuǎn) 朱建峰

1.山東大學(xué)機(jī)械工程學(xué)院，濟(jì)南，2500612.山東大學(xué)深圳研究院，深圳，518057

0 引言

設(shè)施布局問題是指在給定的空間與約束條件下，將生產(chǎn)系統(tǒng)的各種資源進(jìn)行合理的組織與分配，以使設(shè)計(jì)目標(biāo)集達(dá)到最優(yōu)[1]。設(shè)施布局對制造企業(yè)的物料搬運(yùn)、在制品庫存、交貨期、生產(chǎn)效率、工作空間、環(huán)境等方面均具有重要的影響，關(guān)系到企業(yè)能否高效率、低成本運(yùn)營[2-3]。

多行設(shè)施布局作為一種常見的設(shè)施布局形式，具有節(jié)約生產(chǎn)空間、物料傳輸柔性高、搬運(yùn)設(shè)備利用率與容錯能力高的優(yōu)點(diǎn)，適用于零部件種類多、工藝復(fù)雜的情況[4]。多行設(shè)施布局形式的生產(chǎn)系統(tǒng)中通常分布有橫向與縱向交錯的通道，橫向通道兩邊的行中分布有設(shè)施，縱向通道分布于行內(nèi)，橫縱交錯的通道可以保證搬運(yùn)設(shè)備沿著通道在同一行、行與行的設(shè)施之間合理地進(jìn)行物料搬運(yùn)，因此通道數(shù)量和位置的設(shè)計(jì)直接關(guān)系到多行設(shè)施布局方案的有效性。但目前諸多研究中，通常較少考慮通道對多行設(shè)施布局中物料搬運(yùn)的影響，而是以歐氏距離(直線距離)或曼哈頓距離(矩形距離)表示設(shè)施間物料搬運(yùn)的距離，這就可能造成最終的布局方案不能滿足設(shè)計(jì)要求[5]。LEE等[6]和PAUL等[7]分析了考慮通道的多行設(shè)施布局問題中搬運(yùn)距離的計(jì)算方法，但其中通道的位置和數(shù)量均為固定。本文第一作者等[5]研究了考慮行內(nèi)縱向通道位置不確定情況下的多行設(shè)施布局，但假定行內(nèi)縱向通道的數(shù)量為已知。行內(nèi)縱向通道數(shù)量和位置均為不確定的多行設(shè)施布局問題的研究還未見報(bào)道。例如，在實(shí)際多行設(shè)施布局形式的車間中，通常需要在中間行內(nèi)設(shè)計(jì)一定數(shù)量、合理位置的縱向通道，使搬運(yùn)設(shè)備在各行之間合理地執(zhí)行物料搬運(yùn)任務(wù)，若縱向通道的數(shù)量太少或位置不合理，則可能導(dǎo)致車間內(nèi)物料搬運(yùn)的距離增加；若縱向通道數(shù)量過多，則可能會導(dǎo)致布局空間不足，因此，在設(shè)計(jì)過程中需要對車間內(nèi)縱向通道的數(shù)量、位置進(jìn)行綜合考量。

多行設(shè)施布局問題屬于NP-hard問題，故智能優(yōu)化算法成為求解該問題的常用手段[8]，如遺傳算法(genetic algorithm, GA)[2,6]、粒子群優(yōu)化(particle swarm optimization, PSO)算法[1,7]、蛙跳算法[9]、模擬退火算法[8,10]、蟻群算法[8]、螢火蟲算法[11]等。YANG[12]提出的蝙蝠算法(bat algorithm, BA)融合了GA算法、PSO算法與和聲搜索算法的優(yōu)點(diǎn)，最初是針對連續(xù)性優(yōu)化問題而開發(fā)的，并在連續(xù)性優(yōu)化問題測試中展現(xiàn)出較好的性能。LATIFI等[13]將BA算法[12]應(yīng)用于具有連續(xù)性質(zhì)的開放式設(shè)施布局問題中，以設(shè)施橫縱坐標(biāo)進(jìn)行編碼。此外，很少有離散性質(zhì)的設(shè)施布局問題(如單行設(shè)施布局、多行設(shè)施布局等)運(yùn)用BA算法，原因是BA算法中的頻率、速度、位置等更新公式均是為連續(xù)性問題而設(shè)計(jì)的[14]。在其他離散問題領(lǐng)域的研究中，通常摒棄了BA算法中的頻率、速度、位置等連續(xù)型更新公式，而采用其他離散型的更新算子，如2-exchange算子[15]、交叉算子[14,16]、交換和插入算子[14,17]、2-opt算子[15,17]等，這樣處理并未較好地遵循BA算法本身的思想，且在離散化過程中會提高算法的復(fù)雜性[18]。為了發(fā)揮BA算法在求解連續(xù)性優(yōu)化問題中的優(yōu)勢，克服其在多行設(shè)施布局問題中應(yīng)用的難點(diǎn)，在不引入離散型更新算子的前提下，可以借鑒KANG等[18]的研究成果：將隨機(jī)秘鑰(浮點(diǎn)數(shù))編碼的思想應(yīng)用于布谷鳥搜索算法(cuckoo search, CS)中，解決同是離散性質(zhì)的閉環(huán)設(shè)施布局問題，該方法通過隨機(jī)秘鑰在連續(xù)空間上的更新映射為布局解的變化，使CS算法中的萊維飛行得以實(shí)現(xiàn)。

本文綜合考慮多行設(shè)施布局問題中行內(nèi)縱向通道數(shù)量和位置均為不確定的情況，建立該問題的數(shù)學(xué)模型。鑒于BA算法在連續(xù)性優(yōu)化問題中表現(xiàn)出的優(yōu)勢，本文采用BA算法進(jìn)行模型求解，為了使其得以應(yīng)用于離散性質(zhì)的多行設(shè)施布局問題中，采用隨機(jī)秘鑰編碼思想，提出一種基于映射規(guī)則的隨機(jī)秘鑰蝙蝠算法(random-key bat algorithm, RKBA)，通過定義算法中蝙蝠位置向設(shè)施布局組合解的映射規(guī)則和映射步驟，使算法能夠在連續(xù)空間上執(zhí)行，并在離散空間上映射出碼長不同的解(布局方案)，以實(shí)現(xiàn)BA算法在多行設(shè)施布局問題中的應(yīng)用，從而設(shè)計(jì)出切實(shí)有效的布局方案。

1 問題的描述與建模

1.1 問題描述

本文所研究的多行設(shè)施布局形式如圖1所示，具體描述如下：從布局區(qū)域的左側(cè)邊界開始，將一系列寬度相等、長度不等的矩形作業(yè)單元分配到若干個具有相同高度(即作業(yè)單元的寬度)的行中，行與行之間分布有橫向通道，中間行內(nèi)分布有縱向通道，以使設(shè)計(jì)目標(biāo)集達(dá)到最優(yōu)。該提布局方式常見于餐廳、工位較多的辦公室、行與直線通道整齊排布的車間等場景中，本文以車間作為研究對象。圖1中，wh表示橫向通道的寬度，wv表示縱向通道的寬度，wf表示行的高度，即每個作業(yè)單元的寬度。

圖1 多行設(shè)施布局的形式

本文所研究的多行設(shè)施布局問題還有以下前提條件：①每個作業(yè)單元的長和寬均為已知的固定值；②作業(yè)單元的物料搬運(yùn)點(diǎn)均位于其中心點(diǎn)；③所有作業(yè)單元與通道所占面積之和小于矩形布局區(qū)域的總面積；④橫向通道與縱向通道的寬度已知，橫向通道的數(shù)量已知、位置已定，縱向通道位于中間行內(nèi)，每一中間行內(nèi)縱向通道的數(shù)量和位置均不確定。

1.2 多目標(biāo)函數(shù)

1.2.1最小化物流強(qiáng)度

最小化物流強(qiáng)度即要求作業(yè)單元間物流量與物料搬運(yùn)距離乘積之和最小，目標(biāo)函數(shù)如下：

(1)

其中，n為作業(yè)單元的數(shù)量；fij為作業(yè)單元i至作業(yè)單元j的物流量；dij為搬運(yùn)設(shè)備沿通道從作業(yè)單元i向作業(yè)單元j行進(jìn)的距離。為準(zhǔn)確求得其值，歸納出多行設(shè)施布局中物料搬運(yùn)的基本類型，如圖2所示。

(a)同行搬運(yùn) (b)鄰行搬運(yùn)

圖2a中，同行搬運(yùn)的距離計(jì)算公式為

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

(2)

其中，xi、yi分別為作業(yè)單元i中心點(diǎn)的橫坐標(biāo)、縱坐標(biāo)；y′為作業(yè)單元i和j臨近的同一橫向通道y方向上的中心坐標(biāo)。圖2b中，臨行搬運(yùn)的距離即為曼哈頓距離：

dij=|xi-xj|+|yi-yj|

(3)

(4)

則可以確定圖2c和圖2d所需繪制的節(jié)點(diǎn)數(shù)量分別為4和7。以圖2d為例，節(jié)點(diǎn)①和⑦為兩作業(yè)單元i和j的中心點(diǎn)，節(jié)點(diǎn)②和③為第二行中縱向通道的中心點(diǎn)，節(jié)點(diǎn)④、⑤和⑥為第三行中縱向通道的中心點(diǎn)，進(jìn)而可以生成圖3所示的鄰接圖與鄰接矩陣。鄰接圖上具有可達(dá)關(guān)系的節(jié)點(diǎn)之間的距離即為節(jié)點(diǎn)之間的曼哈頓距離，無可達(dá)關(guān)系的節(jié)點(diǎn)之間的距離記為∞。

圖3 鄰接圖與鄰接矩陣

對于上述跨行搬運(yùn)，在所生成的鄰接圖和鄰接矩陣的基礎(chǔ)上，本文采用Dijkstra算法求解兩作業(yè)單元間物料搬運(yùn)的最短搬運(yùn)距離dij，其具體求解步驟見文獻(xiàn)[5]。

1.2.2最小化搬運(yùn)設(shè)備空載運(yùn)行強(qiáng)度

搬運(yùn)設(shè)備的空載運(yùn)行與前述物料搬運(yùn)是相互獨(dú)立的，以圖4說明搬運(yùn)設(shè)備的空載運(yùn)行。當(dāng)作業(yè)單元i到作業(yè)單元j有物料搬運(yùn)請求時(shí)，搬運(yùn)設(shè)備可能停靠在某一不確定的作業(yè)單元l處，接到搬運(yùn)任務(wù)后空載運(yùn)行至作業(yè)單元i；或者搬運(yùn)設(shè)備正在搬運(yùn)作業(yè)單元k至作業(yè)單元l的物料，搬運(yùn)完成后再由作業(yè)單元l空載出發(fā)至作業(yè)單元i，然后才能完成作業(yè)單元i到作業(yè)單元j的物料搬運(yùn)。

圖4 搬運(yùn)設(shè)備的空載運(yùn)行

考慮到各種工件在不同工序的加工批量、加工時(shí)間具有不確定性，所以搬運(yùn)設(shè)備的位置狀態(tài)也可能具有不確定性。設(shè)搬運(yùn)設(shè)備為完成作業(yè)單元i到作業(yè)單元j的物料搬運(yùn)而需從某一不確定作業(yè)單元l處空載出發(fā)至作業(yè)單元i的概率為Pl，根據(jù)文獻(xiàn)[19]，Pl可表示為

(5)

由式(5)可知，當(dāng)其他作業(yè)單元至作業(yè)單元l有較大的物流量時(shí)，搬運(yùn)設(shè)備從作業(yè)單元l處空載出發(fā)的概率就較大。進(jìn)而，搬運(yùn)設(shè)備為完成作業(yè)單元i至作業(yè)單元j的物料搬運(yùn)所需要空載運(yùn)行距離的期望值可表示為

(6)

綜上，搬運(yùn)設(shè)備空載運(yùn)行強(qiáng)度的目標(biāo)函數(shù)可表示為

(7)

式中，c為物料搬運(yùn)設(shè)備的空載系數(shù)，即物料搬運(yùn)設(shè)備空載運(yùn)行時(shí)與載有物料運(yùn)行時(shí)單位距離運(yùn)行成本的比率，本文取其為油耗比。

1.2.3最大化相互關(guān)系

作業(yè)單元之間的相互關(guān)系通常與搬運(yùn)距離無關(guān)，而與作業(yè)單元之間的歐氏距離有關(guān)，其目標(biāo)函數(shù)可以表示為

(8)

1.3 數(shù)學(xué)模型

對式(1)、式(7)和式(8)中的fij和rij進(jìn)行標(biāo)準(zhǔn)化處理[20]，消除量綱差異：

(9)

(10)

引入權(quán)重系數(shù)w1、w2、w3，將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，構(gòu)建以下數(shù)學(xué)模型(約束條件為中間行中縱向通道的數(shù)量約束，其余約束條件詳見文獻(xiàn)[5]，也可通過掃描本文篇首處OSID碼獲得)：

(11)

其中，nk為第k行中的縱向通道數(shù)量，nkmax和nkmin分別表示第k行中縱向通道數(shù)量的最大值和最小值。

2 隨機(jī)秘鑰蝙蝠算法設(shè)計(jì)

2.1 蝙蝠速度和位置的隨機(jī)秘鑰編碼

圖5 蝙蝠速度與位置的隨機(jī)秘鑰編碼

2.2 蝙蝠位置向布局解的映射

蝙蝠位置用隨機(jī)秘鑰(浮點(diǎn)數(shù))組成的隨機(jī)秘鑰串表示，而多行設(shè)施布局的解通常表示為整數(shù)碼串，因此，需要建立蝙蝠位置與布局解之間的映射關(guān)系。本文將蝙蝠位置向解的映射分為以下三步：①作業(yè)單元與縱向通道數(shù)量隨機(jī)秘鑰的映射；②邊界約束的修正；③縱向通道位置隨機(jī)秘鑰的映射。假設(shè)有10個作業(yè)單元需要布置在四行內(nèi)，中間兩行內(nèi)縱向通道的數(shù)量要求為n2max=n3max=2，n2min=n3min=1，該布局中蝙蝠位置向多行設(shè)施布局組合解映射過程的一個實(shí)例見圖6，該映射方法根據(jù)蝙蝠位置的不同，可能得出不同長度的解。

2.2.1作業(yè)單元與縱向通道數(shù)量隨機(jī)秘鑰的映射

(a)作業(yè)單元與縱向通道數(shù)量隨機(jī)秘鑰的映射

(12)

?,k,κ∈Nk∈[2,m-1]

2.2.2邊界約束的修正

(1)判斷第m行中是否存在某一作業(yè)單元的長度小于lmax，若是，則執(zhí)行步驟(3)，否則執(zhí)行步驟(2)。

(2)隨機(jī)產(chǎn)生一個新的蝙蝠位置，替代當(dāng)前蝙蝠位置，并執(zhí)行2.2.1節(jié)的映射操作，然后判斷是否滿足邊界約束，若是，則跳出修正操作，否則執(zhí)行步驟(1)。

(13)

式中，rrand∈(0,1)。

(4)若最后一行中的作業(yè)單元總長度小于或等于布局區(qū)域的總長度L，則跳出修正操作，否則繼續(xù)執(zhí)行步驟(1)，直到滿足布局邊界約束為止。

2.2.3縱向通道位置隨機(jī)秘鑰的映射

(14)

2.3 全局搜索

(15)

(16)

(17)

式中，fmin、fmax分別為蝙蝠頻率的最小值和最大值；β為[0,1]上的隨機(jī)數(shù)；x*為當(dāng)前種群中的最優(yōu)蝙蝠位置。

圖7 蝙蝠位置的全局更新

2.4 局部搜索

x′*=x*+εA(t)

(18)

圖8 蝙蝠位置的局部更新

2.5 音量和脈沖發(fā)生率的更新

(19)

(20)

2.6 本文所提RKBA算法的執(zhí)行流程

對于本文所需求解的最小化問題，設(shè)xbest為歷史最優(yōu)位置，記F(x)為蝙蝠位置x所映射出的解的目標(biāo)函數(shù)值，則本文所提RKBA算法的流程如下：

(2)完成Xt到解的映射，計(jì)算Xt所映射出的解集的目標(biāo)值，選出Xt中的最優(yōu)位置，記為x*。

(3)將x*與歷史最優(yōu)位置xbest進(jìn)行對比，若F(x*)

(4)如果滿足算法終止規(guī)則，則輸出xbest所映射出的解，否則繼續(xù)執(zhí)行下一步。

(5)t+ +，根據(jù)式(15)～式(17)對Xt中的蝙蝠位置進(jìn)行全局更新。

(8)選出Zt中的最優(yōu)位置作為x*，并繼續(xù)執(zhí)行步驟(3)。

以上步驟(6)引入Zt代替Xt執(zhí)行局部搜索的目的是避免步驟(7)執(zhí)行過程中遺失潛在的全局最優(yōu)蝙蝠位置。本文所提RKBA的執(zhí)行流程如圖9所示。

圖9 本文所提RKBA的流程圖

3 實(shí)例求解測試

3.1 基礎(chǔ)數(shù)據(jù)

以國內(nèi)某農(nóng)機(jī)設(shè)備的生產(chǎn)車間為實(shí)例，該車間長64 m，寬41 m，現(xiàn)有18個作業(yè)單元擬分配到車間內(nèi)的四行空置區(qū)域中，行的寬度與作業(yè)單元的寬度均為8 m，橫向通道與縱向通道的寬度均為3 m，其中中間兩行內(nèi)要求具有1～2條縱向通道，即n2max=n3max=2，n2min=n3min=1，使得物料搬運(yùn)順利進(jìn)行。作業(yè)單元的長度信息見表1。

表1 作業(yè)單元長度

作業(yè)單元之間的物流量與相互關(guān)系見表2和表3，其中未列出的作業(yè)單元之間的物流量和相互關(guān)系為0。此外，表2中作業(yè)單元之間區(qū)分從至關(guān)系，即當(dāng)作業(yè)單元i和j之間物流量不為0時(shí)，通常有fij≠fji(i≠j)；表3中作業(yè)單元之間不區(qū)分從至關(guān)系，即rij=rji(i≠j)。

表2 作業(yè)單元間物流量

表3 作業(yè)單元間相互關(guān)系

3.2 實(shí)例求解與算法分析

圖10 各算法最優(yōu)結(jié)果的進(jìn)化曲線

從圖10可以看出，相對于其他幾種算法，本文所提出的RKBA算法具有更快的收斂速度，且所得解的質(zhì)量更高。所有測試結(jié)果中目標(biāo)函數(shù)最優(yōu)值為RKBA算法得到的0.5325，對應(yīng)的布局解與布局方案如圖11所示。

圖11 最優(yōu)解及其對應(yīng)布局方案

記錄5種算法分別獨(dú)立測試20次后最優(yōu)目標(biāo)值的最佳值、最差值、平均值及算法的平均運(yùn)行時(shí)間，各性能指標(biāo)的對比見表4。此外，記錄5種算法分別獨(dú)立測試20次的平均最優(yōu)目標(biāo)值進(jìn)化曲線，如圖12所示。

表4 算法性能的對比

圖12 各算法平均最優(yōu)目標(biāo)值進(jìn)化曲線

根據(jù)表4與圖12的測試結(jié)果，對算法進(jìn)行對比分析。首先可以看出GA算法的尋優(yōu)效果較差，原因可能是GA算法的局部尋優(yōu)能力較差，雖然種群多樣性較好，但局部搜索能力弱、搜索深度不夠，導(dǎo)致其出現(xiàn)“早熟”。PSO和tsPSO兩種算法在整體尋優(yōu)質(zhì)量上相差不大，但tsPSO算法比PSO算法的運(yùn)行時(shí)間略短，也說明tsPSO算法較PSO算法具有一些優(yōu)勢，但對比CS算法與RKBA算法，PSO算法和tsPSO算法的求解質(zhì)量相對較差，原因可能是：雖然PSO算法、tsPSO算法采用慣性權(quán)重來平衡全局搜索和局部搜索，但它們在搜索過程中沒有圍繞種群最優(yōu)粒子位置進(jìn)行小步長的局部搜索，導(dǎo)致它們的搜索結(jié)果不理想，而CS算法中的“拋棄”操作與RKBA算法中的局部搜索均是圍繞種群最優(yōu)個體執(zhí)行的小步長深度搜索，所以具有較好的尋優(yōu)效果。CS算法的求解質(zhì)量較高，也說明該算法中的萊維飛行具有較好的尋優(yōu)效果，使算法具有較好的局部深度搜索能力，但CS算法的搜索時(shí)間比其他幾種算法都要長。RKBA算法在求解質(zhì)量、尋優(yōu)時(shí)間、收斂速度上均表現(xiàn)出了較好的性能，從求解質(zhì)量來看，RKBA算法的求解質(zhì)量遠(yuǎn)高于GA算法、PSO算法與tsPSO算法的求解質(zhì)量，相對于CS算法也具有一定的優(yōu)勢；從尋優(yōu)時(shí)間來看，RKBA算法的求解時(shí)間最短，且遠(yuǎn)遠(yuǎn)領(lǐng)先于CS算法；從收斂速度來看，相對于GA算法、PSO算法與tsPSO算法，RKBA算法的收斂速度明顯更快，與CS算法相比，在迭代前期，RKBA算法與CS算法均具有較快的收斂速度，但在搜索至約200代之后，RKBA算法的收斂性能要優(yōu)于CS算法。綜上所述，RKBA算法在求解本文多行設(shè)施布局問題中具有較好的尋優(yōu)效果，可以更加快速、高效地生成可行的多行設(shè)施布局方案。

4 結(jié)論

(1)本文建立了行內(nèi)縱向通道數(shù)量和位置具有不確定性的多行設(shè)施布局優(yōu)化模型。該模型以最小化物流強(qiáng)度、最小化搬運(yùn)設(shè)備空載運(yùn)行強(qiáng)度和最大化作業(yè)單元相互關(guān)系作為設(shè)計(jì)目標(biāo)，并給出了搬運(yùn)設(shè)備沿通道進(jìn)行物料搬運(yùn)的距離計(jì)算方法。

(2)提出了一種基于映射規(guī)則的隨機(jī)秘鑰蝙蝠算法。在不引入其他離散型更新算子的前提下，將蝙蝠算法中的蝙蝠速度和位置用隨機(jī)秘鑰表示，根據(jù)所建立的多行設(shè)施布局優(yōu)化模型定義了蝙蝠位置向解的映射規(guī)則和映射步驟，使算法可以在連續(xù)空間上執(zhí)行，并在組合空間上映射出碼長不同的布局方案。映射方法的建立使所提出算法既能發(fā)揮蝙蝠算法在求解連續(xù)性優(yōu)化問題中的優(yōu)勢，又能解決本文所研究的離散性質(zhì)的設(shè)施布局問題。通過一個實(shí)例，將隨機(jī)秘鑰蝙蝠算法與其他算法進(jìn)行了求解對比，生成了有效的多行設(shè)施布局方案，并證明了所提出算法的有效性。

設(shè)施布局是一類復(fù)雜的實(shí)際問題，目前該領(lǐng)域仍存在許多實(shí)際因素未被深入挖掘。今后可考慮設(shè)計(jì)過程中的實(shí)際因素，如物料裝卸點(diǎn)問題、障礙物問題(墻壁、立柱、固定設(shè)備等)，使問題更符合實(shí)際，模型更加完善。