董舒豪 徐志剛 秦開仲 常艷茹 蘇開遠 朱建峰

1.山東大學機械工程學院，濟南，2500612.山東大學深圳研究院，深圳，518057

0 引言

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

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

多行設施布局問題屬于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)點，最初是針對連續(xù)性優(yōu)化問題而開發(fā)的，并在連續(xù)性優(yōu)化問題測試中展現出較好的性能。LATIFI等[13]將BA算法[12]應用于具有連續(xù)性質的開放式設施布局問題中，以設施橫縱坐標進行編碼。此外，很少有離散性質的設施布局問題(如單行設施布局、多行設施布局等)運用BA算法，原因是BA算法中的頻率、速度、位置等更新公式均是為連續(xù)性問題而設計的[14]。在其他離散問題領域的研究中，通常摒棄了BA算法中的頻率、速度、位置等連續(xù)型更新公式，而采用其他離散型的更新算子，如2-exchange算子[15]、交叉算子[14,16]、交換和插入算子[14,17]、2-opt算子[15,17]等，這樣處理并未較好地遵循BA算法本身的思想，且在離散化過程中會提高算法的復雜性[18]。為了發(fā)揮BA算法在求解連續(xù)性優(yōu)化問題中的優(yōu)勢，克服其在多行設施布局問題中應用的難點，在不引入離散型更新算子的前提下，可以借鑒KANG等[18]的研究成果：將隨機秘鑰(浮點數)編碼的思想應用于布谷鳥搜索算法(cuckoo search, CS)中，解決同是離散性質的閉環(huán)設施布局問題，該方法通過隨機秘鑰在連續(xù)空間上的更新映射為布局解的變化，使CS算法中的萊維飛行得以實現。

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

1 問題的描述與建模

1.1 問題描述

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

圖1 多行設施布局的形式

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

1.2 多目標函數

1.2.1最小化物流強度

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

(1)

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

(a)同行搬運 (b)鄰行搬運

圖2a中，同行搬運的距離計算公式為

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

(2)

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

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

(3)

(4)

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

圖3 鄰接圖與鄰接矩陣

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

1.2.2最小化搬運設備空載運行強度

搬運設備的空載運行與前述物料搬運是相互獨立的，以圖4說明搬運設備的空載運行。當作業(yè)單元i到作業(yè)單元j有物料搬運請求時，搬運設備可能?？吭谀骋徊淮_定的作業(yè)單元l處，接到搬運任務后空載運行至作業(yè)單元i；或者搬運設備正在搬運作業(yè)單元k至作業(yè)單元l的物料，搬運完成后再由作業(yè)單元l空載出發(fā)至作業(yè)單元i，然后才能完成作業(yè)單元i到作業(yè)單元j的物料搬運。

圖4 搬運設備的空載運行

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

(5)

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

(6)

綜上，搬運設備空載運行強度的目標函數可表示為

(7)

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

1.2.3最大化相互關系

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

(8)

1.3 數學模型

對式(1)、式(7)和式(8)中的fij和rij進行標準化處理[20]，消除量綱差異：

(9)

(10)

引入權重系數w1、w2、w3，將多目標函數轉化為單目標函數，構建以下數學模型(約束條件為中間行中縱向通道的數量約束，其余約束條件詳見文獻[5]，也可通過掃描本文篇首處OSID碼獲得)：

(11)

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

2 隨機秘鑰蝙蝠算法設計

2.1 蝙蝠速度和位置的隨機秘鑰編碼

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

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

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

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

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

(12)

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

2.2.2邊界約束的修正

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

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

(13)

式中，rrand∈(0,1)。

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

2.2.3縱向通道位置隨機秘鑰的映射

(14)

2.3 全局搜索

(15)

(16)

(17)

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

圖7 蝙蝠位置的全局更新

2.4 局部搜索

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

(18)

圖8 蝙蝠位置的局部更新

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

(19)

(20)

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

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

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

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

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

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

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

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

圖9 本文所提RKBA的流程圖

3 實例求解測試

3.1 基礎數據

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

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

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

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

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

3.2 實例求解與算法分析

圖10 各算法最優(yōu)結果的進化曲線

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

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

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

表4 算法性能的對比

圖12 各算法平均最優(yōu)目標值進化曲線

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

4 結論

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

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

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