魏永來，龍 偉，李炎炎，石小秋，嚴(yán)佳兵

(四川大學(xué) 制造科學(xué)與工程學(xué)院，成都 610065)

0 引言

隨著工業(yè)4.0和智能制造2025等國家重大戰(zhàn)略的提出，對生產(chǎn)制造領(lǐng)域的自動(dòng)化水平和智能化程度的要求將會(huì)越來越高；而現(xiàn)如今，生產(chǎn)制造的含義也不僅僅只限于工廠與車間，更是衍生到了大生產(chǎn)，大物流以及大數(shù)據(jù)融和于一體的智能制造系統(tǒng)。在此背景下，像工廠與車間之間這樣短時(shí)短距的局部物流是否能高效的運(yùn)作則顯得至關(guān)重要。自動(dòng)導(dǎo)引小車(Automated Guided Vehicle，AGV)作為一種靈活高效的小型運(yùn)輸設(shè)備，在制造系統(tǒng)、倉儲(chǔ)系統(tǒng)以及港口碼頭等領(lǐng)域得到了廣泛的應(yīng)用[1]。

AGV具有靈活性好、易于控制、智能化程度高等顯著特點(diǎn)，使用AGV進(jìn)行物料運(yùn)輸可以方便地重組系統(tǒng)，達(dá)到運(yùn)輸過程的柔性化；與傳統(tǒng)的人工或半人工的方式相比，減輕了勞動(dòng)強(qiáng)度，降低了危險(xiǎn)性，提高了生產(chǎn)效率[2]。近年來，關(guān)于作業(yè)車間的AGV調(diào)度問題也吸引了大量學(xué)者的關(guān)注，目前主要的求解算法有遺傳算法、粒子群算法、差分演化算法、禁忌搜索算法、模糊決策算法等[3-7]以及相關(guān)的組合或改進(jìn)優(yōu)化算法[8-9]。

蝙蝠算法(Bat Algorithm, BA)作為一種新興啟發(fā)式算法，具有結(jié)構(gòu)簡單、參數(shù)少、魯棒性強(qiáng)以及易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn)[10]，已被廣泛的應(yīng)用于函數(shù)優(yōu)化、模式識(shí)別和生產(chǎn)調(diào)度等領(lǐng)域。但是到目前為止，鮮有學(xué)者將蝙蝠算法應(yīng)用于AGV調(diào)度問題。同其他智能優(yōu)化算法一樣，基本蝙蝠算法存在易陷入局部最優(yōu)而導(dǎo)致早熟收斂問題，因此對基本蝙蝠算法進(jìn)行了改進(jìn)，提出了一種求解作業(yè)車間多AGV物料配送調(diào)度問題的混合禁忌蝙蝠算法(Hybrid Tabu Bat Algorithm，HTBA)。

1 AGV作業(yè)調(diào)度模型

1.1 調(diào)度問題的描述

本文研究的作業(yè)車間物料配送調(diào)度問題的實(shí)質(zhì)是在能夠保證準(zhǔn)時(shí)性、經(jīng)濟(jì)性以及行走總路程最短的前提下AGV數(shù)量的配置問題。可以具體描述為:在某作業(yè)車間的各個(gè)物料庫存放有加工生產(chǎn)所需的若干物料，根據(jù)特定的車間加工工藝流程，在給定的小車行走路徑、物料裝卸站點(diǎn)、加工工位、車間布局及小車行走規(guī)則以及相應(yīng)加工工位的需求時(shí)間和每個(gè)加工步驟所需的物料數(shù)量等一系列條件約束下，將各種加工物料用AGV搬運(yùn)到目標(biāo)工位以滿足生產(chǎn)的要求，求解完成上述車間物料配送調(diào)度要求的最佳AGV數(shù)量并給出相應(yīng)的調(diào)度時(shí)間表。在一個(gè)生產(chǎn)節(jié)拍內(nèi)，AGV從停靠站出發(fā)，在物料庫和工位之間不斷往復(fù)循環(huán)執(zhí)行配料任務(wù)，并在每次加工結(jié)束后將成品運(yùn)回倉庫儲(chǔ)存。具體的AGV作業(yè)過程如圖1所示。

圖1 AGV作業(yè)過程示意圖

1.2 模型分析

在一個(gè)作業(yè)車間小物流系統(tǒng)中，物料區(qū)和生產(chǎn)區(qū)的布局方式，AGV的行走方式以及物料運(yùn)輸?shù)碾y易程度，都會(huì)對調(diào)度問題的評(píng)價(jià)指標(biāo)產(chǎn)生重要影響。因此為了取得更好的 調(diào)度效果，通常把車間物料調(diào)度視為一個(gè)整體的系統(tǒng)來建立模型[11]。

基于以上分析，對本文研究的AGV物料配送系統(tǒng)，假設(shè)以下條件成立:

(1)車間物流系統(tǒng)中的各個(gè)物料庫和各個(gè)工位的位置都是確定的；

(2)生產(chǎn)過程中每一個(gè)工位加工所需的物料都由特定的物料庫進(jìn)行補(bǔ)給配送；

(3)生產(chǎn)指令的下達(dá)是任意的，即每一個(gè)AGV都可以接受該任務(wù)；

(4)在單位生產(chǎn)節(jié)拍內(nèi)，每個(gè)物料庫與每個(gè)工位之間只需配送一次；

(5)AGV每次的運(yùn)載量和AGV的運(yùn)行速度都限定在一定的范圍內(nèi)；

(6)AGV給每個(gè)工位的供料時(shí)間應(yīng)小于生產(chǎn)節(jié)拍，即在每一個(gè)產(chǎn)品加工完成之前必須完成該時(shí)段加工所需全部物料的供應(yīng)；

(7)AGV在行進(jìn)的過程中不會(huì)發(fā)生撒料和碰撞，且每輛AGV都只允許在供料通道上單向行駛；

(8)每輛AGV的配料初始位置都是確定的，當(dāng)AGV完成一個(gè)生產(chǎn)節(jié)拍內(nèi)所有配料任務(wù)后返回初始位置。

1.3 數(shù)學(xué)模型的建立

首先定義以下參數(shù)：

作業(yè)車間生產(chǎn)線上的生產(chǎn)節(jié)拍為G，物料庫的編號(hào)為m，共有M個(gè)物料庫；生產(chǎn)線工位編號(hào)為n，共有N個(gè)工位；AGV的編號(hào)為k，共有K輛小車；配送任務(wù)的編號(hào)為r，一個(gè)生產(chǎn)計(jì)劃周期內(nèi)總?cè)蝿?wù)數(shù)為R，即M個(gè)物料庫與N個(gè)工位之間存在配送關(guān)系的路徑總條數(shù)也為R。為了明確各個(gè)任務(wù)與物料配送路徑之間的對應(yīng)關(guān)系，建立一個(gè)任務(wù)資源庫，在任務(wù)資源庫中實(shí)現(xiàn)任務(wù)編號(hào)與對應(yīng)的AGV配送路徑之間的匹配；如任務(wù)1代表由1號(hào)物料庫向1號(hào)工位供料。

對于整個(gè)車間物流系統(tǒng)，分別用S、T和C表示一個(gè)生產(chǎn)計(jì)劃周期內(nèi)所有AGV的總行走路程、總運(yùn)輸時(shí)間和總配送成本。分別用矩陣α、矩陣β和矩陣χ表示AGV從特定配料區(qū)到指定工位之間的行走距離、運(yùn)輸時(shí)間和配送成本。矩陣Xkr表示編號(hào)為k的小車執(zhí)行第r次配送任務(wù)時(shí)配料區(qū)與工位之間的對應(yīng)關(guān)系[12]。即：

根據(jù)問題的描述建立的數(shù)學(xué)模型如下：

f(k)=min{S，T，C}

(1)

式中，k為決策變量；此模型的實(shí)質(zhì)是實(shí)現(xiàn)多個(gè)目標(biāo)的結(jié)果最優(yōu)化，下面分別對總行走路程S、總運(yùn)輸時(shí)間T和總配送成本C進(jìn)行說明。

1.3.1 總行走路程

1.3.2 總運(yùn)輸時(shí)間

這里的總配送時(shí)間，除了受式(3)～式(6)的約束外，還需要限定不同任務(wù)的作業(yè)順序以及作業(yè)時(shí)間。式(8)限定了當(dāng)物料庫m需要向多個(gè)對應(yīng)的工位輸送物料時(shí)的配送順序；式(9)表示編號(hào)為k的AGV完成第r個(gè)配料任務(wù)的時(shí)間等于第r-1個(gè)配料任務(wù)的完成時(shí)間、AGV在第r和r-1個(gè)任務(wù)之間的配送時(shí)間以及裝卸物料時(shí)間之和；式(10)限定了每輛AGV單位時(shí)間內(nèi)供料總時(shí)間應(yīng)小于生產(chǎn)節(jié)拍。其中：Tkr表示編號(hào)為k的AGV完成第r個(gè)配料任務(wù)的時(shí)間，Tr(r-1)表示AGV由第r-1個(gè)任務(wù)到第r個(gè)任務(wù)所消耗的時(shí)間，Ta為AGV的平均物料裝卸時(shí)間，對于每輛AGV，每執(zhí)行一次物料配送的任務(wù)，Ta只需計(jì)算一次。

1.3.3 總配送成本

(11)

s.t. 式(3)～式(6)

2 混合禁忌蝙蝠算法

基本蝙蝠算法是學(xué)者Yang根據(jù)自然界中蝙蝠所具備的回聲定位能力而提出的一種元啟發(fā)式算法[13]。針對作業(yè)車間多AGV物料配送的調(diào)度問題，本文在基本蝙蝠算法的基礎(chǔ)上，提出了一種混合禁忌蝙蝠算法，該算法能夠有效地避免算法早熟收斂、提高算法的全局搜索能力和精度，增強(qiáng)求解的穩(wěn)定性。

2.1 編碼與解碼

作業(yè)車間調(diào)度問題一般都是離散型組合優(yōu)化問題，而基本蝙蝠算法中每個(gè)個(gè)體位置均為連續(xù)值，因此運(yùn)用蝙蝠算法求解多AGV物料配送調(diào)度問題時(shí)，首先要明確解空間和問題空間之間的映射關(guān)系，即如何合理的設(shè)計(jì)算法的編碼與解碼方式使其能夠?qū)崿F(xiàn)隨機(jī)值與調(diào)度解之間的轉(zhuǎn)換。本文采用文獻(xiàn)[14]中的ROV規(guī)則來進(jìn)行蝙蝠個(gè)體位置向量與可行調(diào)度解之間的轉(zhuǎn)換。具體的轉(zhuǎn)換過程如圖2所示。

圖2 編碼轉(zhuǎn)換方案

本文采用基于任務(wù)的單層整數(shù)分段編碼策略，為每個(gè)任務(wù)提供2個(gè)編碼位，即編碼長度為2R。每個(gè)任務(wù)編碼序列中的第一位表示AGV編號(hào)，第二位表示AGV執(zhí)行配料任務(wù)的順序；如編碼序列113212...521中前兩位11表示編號(hào)為1的AGV第1次配料是完成任務(wù)1,32表示編號(hào)為3的AGV第2次配料是完成任務(wù)2，以此類推。

2.2 種群初始化

在算法的初期，需要對種群進(jìn)行初始化操作，由于編碼序列中每個(gè)編碼位的取值范圍不同，且整個(gè)編碼序列必須具有一定的實(shí)際意義，故采用如下的種群初始化方案：

步驟1 ：以工位數(shù)量N作為初始AGV數(shù)量，隨機(jī)生成R個(gè)1～N之間的整數(shù)作為各任務(wù)段第一個(gè)編碼位的值。

步驟2 ：若某幾個(gè)任務(wù)段的第一個(gè)編碼值相同，則進(jìn)行隨機(jī)排序作為第二個(gè)編碼位的值，否則記第二個(gè)編碼位的值為1。

步驟3：按從左至右的順序依次生成直至把所有的編碼位填充完整。

重復(fù)以上步驟若干次，即可得到一定規(guī)模的初始化蝙蝠種群。對于HTBA算法，種群初始化完成后，在搜索空間中，還需對蝙蝠個(gè)體的運(yùn)動(dòng)方式作出如下限定：

fk=fmin+(fmax-fmin)×rand

(12)

vk(t)=vk(t-1)+(xk(t-1)-x*)fk

(13)

xk(t)=xk(t-1)+vk(t)

(14)

xnew=xold+εAt

(15)

式(12)中，fk、fmin、fmax分別表示第k只蝙蝠個(gè)體在當(dāng)前時(shí)刻發(fā)出的聲波頻率以及聲波頻率的最小值和最大值；rand是0～1之間的隨機(jī)數(shù)，x*表示當(dāng)前范圍內(nèi)全局最優(yōu)解。式(13)、式(14)分別表示蝙蝠個(gè)體在t時(shí)刻速度與位置的更新過程。式(15)中，xold表示隨機(jī)選擇的一個(gè)最優(yōu)解，At表示當(dāng)前蝙蝠群體響度的平均值，ε表示在[-1,1]范圍內(nèi)的隨機(jī)數(shù)。

2.3 脈沖頻度和響度的更新

在蝙蝠個(gè)體的運(yùn)動(dòng)過程中，需要對每個(gè)個(gè)體的脈沖頻度和響度進(jìn)行更新，其中脈沖頻度會(huì)影響個(gè)體執(zhí)行局部搜索的概率，響度則影響著接受新解的概率。在初始時(shí)刻個(gè)體的脈沖響度較大，脈沖頻度較小；但隨著搜索過程的推進(jìn)，脈沖響度會(huì)逐漸減小，脈沖頻度逐漸增加，二者不斷更新變化使算法結(jié)果最優(yōu)化。本文采用如下的方法對個(gè)體的脈沖頻度Rk和響度Ak進(jìn)行更新。

Ak(t)=φAk(t-1)

(16)

Rk(t)=Rk(0)×{1-exp[-γ(t-1)]}

(17)

上述兩式中，φ、γ均為常量，且滿足0<φ<1，γ>0。

2.4 禁忌搜索與局部尋優(yōu)

2.4.1 禁忌表

為防止算法在搜索過程中出現(xiàn)循環(huán)，在基本的蝙蝠算法中，引入禁忌搜索算法中的禁忌表，使得蝙蝠個(gè)體在一段時(shí)間內(nèi)，不會(huì)重復(fù)地停留在同一個(gè)地方，使得算法更趨于全局的搜索。

在本文的HTBA中，通過每只蝙蝠個(gè)體的位置信息變化來決定是否將該蝙蝠加入禁忌表。當(dāng)蝙蝠個(gè)體在算法迭代過程中產(chǎn)生重復(fù)時(shí)，就會(huì)被納入禁忌表，成為被禁忌的對象，這些對象需要經(jīng)過一定的算法迭代次數(shù)才能從禁忌表中釋放出來，而迭代次數(shù)的多少通常由禁忌長度決定。如果禁忌長度越小，算法的計(jì)算時(shí)間就越短從而提高算法的效率；但是如果禁忌表的長度過小，又容易使算法陷入循環(huán)從而影響算法的性能，因此，選擇合適的禁忌長度至關(guān)重要[15]。在本文的算法中，設(shè)定禁忌表的長度為固定值。

2.4.2 藐視準(zhǔn)則

在算法迭代中，當(dāng)出現(xiàn)候選解全部被禁忌或者存在一個(gè)優(yōu)于當(dāng)前最優(yōu)狀態(tài)的禁忌候選解的情況時(shí)，此時(shí)藐視準(zhǔn)則將會(huì)使某些狀態(tài)解禁，以此來實(shí)現(xiàn)算法更高效的優(yōu)化性能。本文采用基于適應(yīng)度值的準(zhǔn)則：若存在某個(gè)禁忌候選解的適應(yīng)度值優(yōu)于當(dāng)前最優(yōu)狀態(tài)，則解禁此候選解為當(dāng)前解和新的當(dāng)前最優(yōu)狀態(tài)。

2.4.3 局部尋優(yōu)

針對AGV作業(yè)調(diào)度離散化的特點(diǎn)，在算法的局部尋優(yōu)過程中定義如下兩種用于鄰域搜索的擾動(dòng)操作[16]：

(1)元素插入。在蝙蝠個(gè)體位置編碼序列中，隨機(jī)選擇兩個(gè)對應(yīng)位置的元素，并將前一個(gè)元素插到后一個(gè)元素后面。

(2)元素交換。在蝙蝠個(gè)體位置編碼序列中，隨機(jī)選擇兩個(gè)對應(yīng)位置的元素，并交換二者的位置。

具體的局部尋優(yōu)過程如圖3所示。

圖3 局部尋優(yōu)流程圖

2.4.4 適應(yīng)度函數(shù)的選擇

算法中蝙蝠個(gè)體位置的優(yōu)劣由適應(yīng)度值函數(shù)衡量，而適應(yīng)度值函數(shù)通常由求解問題的目標(biāo)函數(shù)決定。本文所述調(diào)度模型的目標(biāo)函數(shù)是在實(shí)現(xiàn)AGV總行走路程S、總運(yùn)輸時(shí)間T和總配送成本C三者最優(yōu)化的前提下給出最佳的AGV數(shù)量配置。因此，將適應(yīng)度值函數(shù)設(shè)置為：

(18)

其中，k為AGV小車數(shù)，δ為比例因子,θ1、θ2、θ3分別為總行走路程、總運(yùn)輸時(shí)間和總配送成本的權(quán)重貢獻(xiàn)系數(shù)。

2.5 算法的實(shí)現(xiàn)步驟

HTBA算法的流程示意簡圖如圖4所示。

圖4 HTBA算法流程簡圖

其具體的實(shí)現(xiàn)步驟如下：

步驟1：種群初始化，設(shè)置算法相關(guān)參數(shù)。

步驟2：依次對每個(gè)蝙蝠個(gè)體進(jìn)行適應(yīng)度值評(píng)價(jià)，找出當(dāng)前最優(yōu)個(gè)體并判斷終止條件。

步驟3：設(shè)定禁忌表的長度并初始化禁忌表。

步驟4：按照2.2節(jié)中的公式更新蝙蝠個(gè)體的位置和速度。

步驟5：對于每個(gè)蝙蝠個(gè)體，若滿足rand>Rk，則采用局部尋優(yōu)策略對當(dāng)前最優(yōu)個(gè)體進(jìn)行局部搜索產(chǎn)生一個(gè)新解。

步驟6：評(píng)價(jià)產(chǎn)生的新解，若優(yōu)于當(dāng)前最優(yōu)解且滿足rand

步驟7：根據(jù)2.3節(jié)中的公式更新蝙蝠個(gè)體的Rk和Ak。

步驟8：更新當(dāng)前最優(yōu)個(gè)體位置，并判斷是否存在禁忌表中，若不是則更新禁忌表。

步驟9：終止條件檢查。若滿足，則解碼輸出最優(yōu)解；否則轉(zhuǎn)到步驟4。

步驟10：算法結(jié)束。

3 仿真實(shí)驗(yàn)與分析

采用Matlab編程語言對本文提出的混合禁忌蝙蝠算法進(jìn)行編程，程序的運(yùn)行環(huán)境為Win7系統(tǒng)下內(nèi)存為4GB的Intel(R)Core(TM) i3-4170 CPU 3.70GHz的PC機(jī)。

3.1 案例計(jì)算

算法相關(guān)參數(shù)設(shè)置如表1所示。

表1 HTBA算法參數(shù)

以解放軍某工廠的一作業(yè)車間生產(chǎn)線為例，驗(yàn)證算法的有效性。該生產(chǎn)線共有10個(gè)工位，增加一個(gè)0工位，用來表示AGV?？空镜奈恢?；加工物料分為四類，分別記為物料庫A、B、C、D，其中物料庫A對1、2、4、8號(hào)工位供料，物料庫B對2、3、6、7號(hào)工位供料，物料庫C對7、9、10號(hào)工位供料，物料庫D對4、5、8、9號(hào)工位供料。車間的生產(chǎn)節(jié)拍G為16min/臺(tái);AGV的平均裝卸物料時(shí)間Ta為1min。經(jīng)過測算，各物料庫與各個(gè)工位的距離，運(yùn)輸時(shí)間和配送成本，分別如表2～表4所示。

表2 各物料庫至各工位距離(單位：m)

表3 各物料庫至各工位運(yùn)輸時(shí)間(單位：min)

表4 各物料庫至各工位配送成本(單位：￥)

根據(jù)上述案例給出的原始數(shù)據(jù)，并結(jié)合AGV作業(yè)調(diào)度模型的相關(guān)約束條件，編程得到算法運(yùn)行后的調(diào)度結(jié)果如圖5、圖6所示。

圖5 最優(yōu)解甘特圖 圖6 最優(yōu)個(gè)體適應(yīng)度值變化曲線

由圖5可知，對于該作業(yè)車間，在滿足生產(chǎn)要求的前提下，至少需要6輛AGV進(jìn)行物料配送，求解出的最優(yōu)調(diào)度方案對每輛AGV的配送路徑和物料運(yùn)輸時(shí)間都進(jìn)行了合理的規(guī)劃。由圖6可知，算法在迭代到第48次時(shí)即達(dá)到最優(yōu)狀態(tài)。

3.2 算法對比分析

為了進(jìn)一步驗(yàn)證本文算法的優(yōu)越性，對上述案例，分別用基本蝙蝠算法、禁忌搜索算法和遺傳算法等在Matlab中進(jìn)行編程求解，得到的結(jié)果對比如表5所示。

表5 算法結(jié)果對比

由以上對比可知，相較于其它算法，本文提出的混合禁忌蝙蝠算法，對于結(jié)構(gòu)簡單的分布式作業(yè)車間的物料調(diào)度問題，具有很好的適配性，能夠得到較為理想的結(jié)果。

4 結(jié)論

本文提出了一種混合禁忌蝙蝠算法來求解在總行走路程、總運(yùn)輸時(shí)間、總配送成本等多目標(biāo)約束下的作業(yè)車間多AGV調(diào)度問題。此外，為了避免算法的早熟收斂，引入禁忌搜索和局部尋優(yōu)策略來提高算法尋優(yōu)能力。最后，通過對某實(shí)際生產(chǎn)加工作業(yè)車間進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明了本文的HTBA算法在解決作業(yè)車間多AGV物料配送調(diào)度問題中的可行性和高效性。同時(shí)，基于本文的研究結(jié)果，在今后可以將蝙蝠算法與其他一些智能優(yōu)化算法進(jìn)行結(jié)合，來求解其它類型或更加復(fù)雜的車間調(diào)度問題。