基于改進(jìn)灰狼優(yōu)化算法的立體車庫(kù)調(diào)度優(yōu)化

陳 敏， 陳 曄， 許民宗， 郭曉宇

(中北大學(xué) 電氣與控制工程學(xué)院， 山西 太原 030051)

0 引 言

由于巷道堆垛式立體車庫(kù)車位多， 出入口少， 導(dǎo)致用戶存取車等待時(shí)間較長(zhǎng)， 降低了存取車的效率。 因此， 以存取車調(diào)度時(shí)間為模型對(duì)這類立體車庫(kù)利用優(yōu)化算法優(yōu)化調(diào)度， 以提高車庫(kù)運(yùn)行效率， 減少存取車的等待時(shí)間具有重大意義[1]。

國(guó)內(nèi)學(xué)者對(duì)立體車庫(kù)存取車調(diào)度的研究已取得顯著的成果， 使用的算法主要有遺傳算法(GA)、 模擬退火算法(SA)、 粒子群算法(PSO)等。 魏麗[1]應(yīng)用改進(jìn)遺傳算法并利用MATLAB遺傳算法工具箱對(duì)巷道堆垛立體車庫(kù)存取調(diào)度時(shí)間和能耗進(jìn)行建模仿真， 得到了時(shí)間最優(yōu)迭代曲線和最優(yōu)操作序列， 最后將結(jié)果與隨機(jī)分配策略的結(jié)果進(jìn)行比較， 驗(yàn)證了改進(jìn)遺傳算法在提高車輛存取效率上的有效性。 陳桂蘭等[2-3]使用改進(jìn)粒子群算法對(duì)立體車庫(kù)存取策略的時(shí)間模型進(jìn)行仿真優(yōu)化， 在粒子群算法的基礎(chǔ)上引入了遺傳算法和模擬退火算法， 提高了算法的全局搜索能力且避免其陷入局部最優(yōu)解， 與傳統(tǒng)的遺傳算法相比， 改進(jìn)后的算法存取效率提高了24.5%～36.0%。 李劍鋒等[4]使用改進(jìn)遺傳算法對(duì)巷道堆垛立體車庫(kù)的存取調(diào)度進(jìn)行優(yōu)化， 以總存取時(shí)間為模型建立了目標(biāo)函數(shù)， 經(jīng)過仿真試驗(yàn)后得到較小的存取車總時(shí)間以及存取車優(yōu)化序列。 YIN等[5]引入學(xué)習(xí)強(qiáng)化算子和卡爾曼濾波對(duì)灰狼算法進(jìn)行改進(jìn)， 使用6個(gè)測(cè)試函數(shù)驗(yàn)證了改進(jìn)后算法的尋優(yōu)性能， 最后將其用于解決流水車間調(diào)度中的節(jié)能問題。 LI等[6]以滿意度作為優(yōu)化目標(biāo)建立數(shù)學(xué)模型， 使用改進(jìn)遺傳算法得到了最優(yōu)調(diào)度結(jié)果， 并將其與以客戶等待時(shí)間為目標(biāo)的優(yōu)化結(jié)果相比較， 證明了滿意度作為優(yōu)化目標(biāo)的有效性。

以上研究在對(duì)自動(dòng)化立體車庫(kù)進(jìn)行調(diào)度優(yōu)化時(shí)， 都只是對(duì)之前的算法進(jìn)行改進(jìn)， 沒有再引入新的方法和思路對(duì)存取車調(diào)度進(jìn)行研究。 灰狼優(yōu)化算法是Mrijalili提出的一種智能優(yōu)化算法， 具有原理簡(jiǎn)單、 易于實(shí)現(xiàn)、 需調(diào)整的參數(shù)少、 求解精度高、 收斂速度快、 在函數(shù)優(yōu)化問題中優(yōu)于其他智能算法等優(yōu)點(diǎn)[7-8]。 雖已有學(xué)者使用此算法對(duì)流水車間的調(diào)度進(jìn)行研究， 得到了較好的驗(yàn)證結(jié)果， 但目前灰狼優(yōu)化算法在立體車庫(kù)存取車調(diào)度的研究中鮮有應(yīng)用。

本文使用改進(jìn)的灰狼優(yōu)化算法對(duì)車庫(kù)調(diào)度問題進(jìn)行研究。 根據(jù)立體車庫(kù)車輛調(diào)度的特點(diǎn)， 使用遺傳算法、 鄰域搜索操作對(duì)灰狼算法進(jìn)行改進(jìn)： 引入遺傳算法的交叉操作改進(jìn)灰狼算法的位置更新公式； 為了解決灰狼算法易陷入局部最優(yōu)解的缺點(diǎn)， 引入鄰域策略對(duì)更新后種群中的領(lǐng)頭狼進(jìn)行局部搜索操作， 以獲得更優(yōu)的灰狼個(gè)體， 從而整體上帶動(dòng)種群向更優(yōu)的方向更新。 研究結(jié)果與文獻(xiàn)[4]中所使用的改進(jìn)遺傳算法作比較， 驗(yàn)證了算法在降低存取車時(shí)間上的有效性。

1 巷道堆垛立體車庫(kù)概述

巷道堆垛式立體車庫(kù)由旋轉(zhuǎn)平臺(tái)、 升降機(jī)、 堆垛機(jī)等組成。 本文的研究對(duì)象為單巷道兩區(qū)車庫(kù)， 每區(qū)有4層4列16個(gè)車位， 兩區(qū)共有32個(gè)停車位。 1區(qū)的1層1列為轉(zhuǎn)換層， 其結(jié)構(gòu)如圖1 所示。 該類車庫(kù)的優(yōu)勢(shì)是利用堆垛機(jī)同時(shí)進(jìn)行水平和垂直運(yùn)動(dòng)使車輛到達(dá)指定位置， 再由搬運(yùn)器進(jìn)行存取操作[9]， 極大地節(jié)省了存取車時(shí)間。 其車位平面分布如圖2 所示。

圖1 巷道堆垛式立體車庫(kù)三維結(jié)構(gòu)圖

(a) 車庫(kù)1區(qū)坐標(biāo)

2 存取策略優(yōu)化及建模

巷道堆垛式立體車庫(kù)在接收到存車操作指令時(shí)， 升降機(jī)將待存車輛垂直運(yùn)送到轉(zhuǎn)換層， 由堆垛機(jī)將車輛運(yùn)送到目的地； 當(dāng)接收到取車操作指令時(shí)， 待取車輛通過堆垛機(jī)運(yùn)送到轉(zhuǎn)換層， 然后由升降機(jī)將車輛輸送到出入口進(jìn)行旋轉(zhuǎn)等待出庫(kù)。

在存取車的整個(gè)過程中， 升降機(jī)、 旋轉(zhuǎn)臺(tái)都是確定的， 它們的運(yùn)行時(shí)間也是確定的， 但堆垛機(jī)的運(yùn)行時(shí)間卻不確定， 這主要是由于存取車時(shí)的車位不確定， 堆垛機(jī)空閑時(shí)的?？课恢貌淮_定， 堆垛機(jī)行進(jìn)路線不確定等原因造成的。 因此， 存取車位的分配、 堆垛機(jī)運(yùn)行路徑的規(guī)劃以及堆垛機(jī)空閑時(shí)的停靠位置等是立體車庫(kù)存取策略的主要研究?jī)?nèi)容。

立體車庫(kù)存取策略主要包括存車優(yōu)先策略、 取車優(yōu)先策略、 交叉存取策略。 為了對(duì)比這3種策略下的調(diào)度時(shí)間， 本文對(duì)每一種策略都安排相同的出入庫(kù)次數(shù)。

2.1 存車優(yōu)先策略

將存取車任務(wù)進(jìn)行分組， 先進(jìn)行存車操作。 堆垛機(jī)完成存車操作后回到轉(zhuǎn)換層待命， 當(dāng)有下一次的存車任務(wù)到來時(shí)可以直接進(jìn)行存車操作[10]。 這種存車策略適應(yīng)于某一存入車輛較多時(shí)的時(shí)間段。 存車優(yōu)先策略的數(shù)學(xué)模型為

(1)

式中： (a0,b0) 為轉(zhuǎn)換層坐標(biāo)； (a1,b1)為堆垛機(jī)執(zhí)行上一步操作時(shí)的位置； (a2,b2)為堆垛機(jī)所要到達(dá)的目的地；t1為升降機(jī)運(yùn)行一次所需的時(shí)間；t2為堆垛機(jī)在相鄰兩層間運(yùn)行所需的時(shí)間；t3為堆垛機(jī)在相鄰兩列間運(yùn)行所需的時(shí)間；t4為旋轉(zhuǎn)臺(tái)旋轉(zhuǎn)一次所需的時(shí)間；n1為待存車數(shù)目；n2為待取車數(shù)目。

2.2 取車優(yōu)先策略

當(dāng)有存取操作時(shí)先進(jìn)行取車操作， 每次完成取車操作后堆垛機(jī)都回到原取車地等待， 當(dāng)下一次取車任務(wù)到來時(shí)堆垛機(jī)從原取車地直接到達(dá)待取車地。 完成存車操作后， 堆垛機(jī)在原地待命[10]。 這種存取策略適用于某一集中取車的時(shí)間段。 取車優(yōu)先策略的數(shù)學(xué)模型為

2max{t2|a2-a0|,t3|b2-b0|}+t4)+

max{t2|a2-a0|,t3|b2-b0|})。

(2)

2.3 交叉存取策略

在某一時(shí)間段內(nèi)既進(jìn)行存車操作也進(jìn)行取車操作， 存取車操作交叉進(jìn)行， 堆垛機(jī)完成取車操作后待在轉(zhuǎn)換層等待進(jìn)行下一步的存車操作， 存車操作結(jié)束后堆垛機(jī)原地待命。 這種存取策略適用于普通的存取車時(shí)間段。 交叉存取策略的數(shù)學(xué)模型為

max{t2|a2-a0|,t3|b2-b0|}+t4+t1),

(3)

由太原某大廈調(diào)研數(shù)據(jù)可知， 堆垛機(jī)在相鄰兩層之間的運(yùn)行時(shí)間為10 s， 在相鄰兩列間的運(yùn)行時(shí)間為 5 s， 升降機(jī)升降一次所需時(shí)間為10 s， 旋轉(zhuǎn)臺(tái)進(jìn)行一次旋轉(zhuǎn)操作所需時(shí)間為5 s。 轉(zhuǎn)換層的坐標(biāo)為(1,1)。

3 改進(jìn)灰狼優(yōu)化算法

3.1 灰狼優(yōu)化算法

灰狼優(yōu)化算法(GWO)是以自然界中狼群的狩獵以及生活習(xí)性為基礎(chǔ)的一種群智能優(yōu)化算法[11]。 狼群有嚴(yán)格的等級(jí)制度， 每支狼群都可以分成4個(gè)等級(jí)層次， 如圖3 所示。

圖3 狼群等級(jí)層次的劃分

在GWO算法中， 由領(lǐng)頭狼(α,β,δ)引導(dǎo)搜索， 而ω作為候選狼跟隨前面的領(lǐng)頭狼[12]。

3.1.1 包圍獵物

灰狼從搜索區(qū)域內(nèi)發(fā)起攻擊， 將對(duì)獵物進(jìn)行包圍狩獵[8，13]， 包圍行為的數(shù)學(xué)描述為

D=|C·Xp(k)-X(k)|,

(4)

X(k+1)=Xp(k)-A·D,

(5)

式中：k為當(dāng)前迭代次數(shù)；A和C均為協(xié)同系數(shù)向量；D為種群個(gè)體與獵物之間的距離；Xp為獵物的位置向量；X為灰狼的位置向量。

向量A,C的計(jì)算公式為

A=2a·r1-a，

(6)

C=2·r2，

(7)

其中，a在迭代過程中從2線性減少到0， 即

(8)

式中：r1,r2為[0,1]之間的隨機(jī)向量；K為最大迭代次數(shù)。

3.1.2 狩獵

在整個(gè)狩獵的過程中都由頭狼進(jìn)行引導(dǎo)，β和δ狼有時(shí)也會(huì)進(jìn)行狩獵。 灰狼個(gè)體的下一個(gè)位置是根據(jù)領(lǐng)頭狼的位置來搜索和更新的[14]， 位置更新公式為

(9)

(10)

(11)

3.2 改進(jìn)灰狼優(yōu)化算法

1) 交叉操作式位置更新策略

立體車庫(kù)存取車調(diào)度是一個(gè)離散優(yōu)化問題， 而GWO優(yōu)化的問題都是連續(xù)的， 顯然使用式(9)～式(11)進(jìn)行灰狼個(gè)體的更新是行不通的。 所以， 本文引入GA算法中的交叉操作對(duì)GWO算法中的位置更新策略進(jìn)行改進(jìn)。 以相同的概率選擇α，β，δ狼與當(dāng)前灰狼個(gè)體隨機(jī)進(jìn)行交叉操作， 位置更新公式為

(12)

式中： cross表示兩個(gè)個(gè)體進(jìn)行交叉操作；r為[0,1]之間的隨機(jī)數(shù)。

2) 鄰域搜索局部尋優(yōu)策略

領(lǐng)域搜索的主旨是對(duì)得到的某個(gè)局部解使用鄰域操作對(duì)其周圍個(gè)體進(jìn)行搜索來獲得最終解， 已被廣泛應(yīng)用于解決組合優(yōu)化問題。 主要的鄰域操作有交換操作、 插入操作、 逆轉(zhuǎn)操作等。

在灰狼尋優(yōu)過程中， 為了使領(lǐng)頭狼帶領(lǐng)種群向更優(yōu)的位置更新， 本文引入鄰域搜索對(duì)領(lǐng)頭狼(α,β,δ)分別進(jìn)行搜索操作， 以避免整支狼群進(jìn)入局部最優(yōu)狀態(tài)。 為了進(jìn)一步擴(kuò)大搜索范圍， 搜索到更多的解， 在獲得鄰域集合之前先對(duì)領(lǐng)頭狼進(jìn)行相同鄰域操作的擾動(dòng)操作得到“擾動(dòng)解”， 然后使用該鄰域操作獲得這個(gè)“擾動(dòng)解”的鄰域集合， 在增加種群多樣性的同時(shí)利于算法跳出局部最優(yōu)。 根據(jù)立體車庫(kù)調(diào)度的特點(diǎn)， 本文選擇逆轉(zhuǎn)操作， 主要理論及操作步驟詳見文獻(xiàn)[15]。

3.3 IGWO算法實(shí)現(xiàn)

使用IGWO算法解決立體車庫(kù)的調(diào)度問題主要包括參數(shù)設(shè)定、 編碼與解碼、 初始種群的生成、 目標(biāo)函數(shù)的確立、 種群個(gè)體位置更新和局部尋優(yōu)。

3.3.1 編碼與解碼

本文采用2段混合編碼方式進(jìn)行編碼操作， 結(jié)合車庫(kù)存取車調(diào)度優(yōu)化的實(shí)際情況， 其主要包含車位位置和存取操作兩部分。 若總共有m輛車待存取， 其中有n1個(gè)為存車操作，n2個(gè)為取車操作，n1+n2=m， 則灰狼個(gè)體的總長(zhǎng)度為2m。 前m個(gè)元素由實(shí)數(shù)組成， 表示待存取車位位置； 后m個(gè)元素由二進(jìn)制(0,1)組成， 表示存取操作， 0代表取車操作， 1代表存車操作。 將車位位置與存取車操作進(jìn)行一一對(duì)應(yīng)， 部分編碼如表1 所示。

表1 部分編碼序列

3.3.2 種群初始化

對(duì)灰狼初始種群采用隨機(jī)方法生成， 灰狼個(gè)體的前m個(gè)元素由1～m個(gè)整數(shù)隨機(jī)排列組成， 后m個(gè)元素由n1個(gè)1和(m-n1)個(gè)0隨機(jī)排列組成， 個(gè)體總長(zhǎng)度為2m。

3.3.3 目標(biāo)函數(shù)

本文的目標(biāo)是求調(diào)度總時(shí)間的最小值。 所以， 目標(biāo)函數(shù)Ft表示為

Ft=ti,i=c,q,j,

(13)

式中：ti表示各個(gè)策略下存取車所使用的總時(shí)間。

3.3.4 位置更新

在進(jìn)行個(gè)體位置更新時(shí)， 灰狼個(gè)體與α,β,δ狼的交叉概率皆為1/3。 隨機(jī)選擇兩個(gè)灰狼個(gè)體上的部分片段進(jìn)行交叉操作， 并將交叉后個(gè)體上重復(fù)的元素刪除。 如：

個(gè)體2： 5 4 3 2 1 0 1 0 1 1

若交叉片段為2～4， 將車位位置與存取車操作整體進(jìn)行對(duì)應(yīng)交換， 則將個(gè)體1和個(gè)體2上位置2～4的整數(shù)編碼元素及其對(duì)應(yīng)的3個(gè)0 1編碼元素進(jìn)行交叉操作， 即將2個(gè)個(gè)體的交叉片段相互交叉放置在另一個(gè)個(gè)體前端， 如：

個(gè)體2： 3 1 5543210 1 001011

最后將交叉后的個(gè)體中重復(fù)的元素刪除， 更新后的個(gè)體1和個(gè)體2， 如：

個(gè)體2： 3 1 5 4 2 0 1 0 1 1

3.3.5 局部尋優(yōu)

對(duì)上一步完成位置更新后種群中的α,β,δ狼實(shí)行局部尋優(yōu)操作， 主要包括獲得“擾動(dòng)解”以及“擾動(dòng)解”的鄰域集合。

假設(shè)位置更新后個(gè)體α的編碼為

1) 擾動(dòng)操作為逆轉(zhuǎn)位置3～5上的元素， 所得“擾動(dòng)解”為

2) 引入逆轉(zhuǎn)操作獲得“擾動(dòng)解”的鄰域集合， 如逆轉(zhuǎn)片段為2～4， 則

3.4 IGWO算法立體車庫(kù)調(diào)度流程

IGWO算法求解立體車庫(kù)調(diào)度問題的流程如圖4 所示。

圖4 IGWO求解車庫(kù)調(diào)度流程圖

4 結(jié)果與分析

4.1 改進(jìn)灰狼優(yōu)化算法參數(shù)設(shè)置

按照第2節(jié)中立體車庫(kù)的存取調(diào)度時(shí)間模型， 并對(duì)第3節(jié)的改進(jìn)灰狼算法進(jìn)行設(shè)計(jì)， 可得出IGWO算法的部分參數(shù)， 如表2 所示。

表2 IGWO算法部分參數(shù)

4.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證IGWO算法對(duì)車庫(kù)存取調(diào)度時(shí)間的影響， 將其與GWO以及文獻(xiàn)[4]中的改進(jìn)遺傳算法(IGA)進(jìn)行比較。 3種存取策略采用相同的存取次數(shù)。 該巷道堆垛式立體車庫(kù)共有31個(gè)車位， 假設(shè)在某時(shí)段有21輛車待存入， 10輛車待取出， 目標(biāo)函數(shù)為存取完全部車輛所需的總時(shí)間， 目標(biāo)函數(shù)值越小代表算法效果越好。 實(shí)驗(yàn)環(huán)境為PC， 仿真軟件為MATLAB R2020b， PC主機(jī)為Intel(R) Core(TM) i7-8700， 主頻為 3.20 GHz， 內(nèi)存為16 GB， 操作系統(tǒng)為Windows 10。

4.2.1 存車優(yōu)先

存車優(yōu)先仿真結(jié)果如圖5 所示， 實(shí)驗(yàn)結(jié)果表明IGWO算法比GWO和IGA算法效果好。 IGWO算法在第100次迭代后得到的最短存取總時(shí)間為832 s， GWO與IGA分別在迭代110次和140次后才逐漸收斂， 最終結(jié)果分別為1 043 s和1 263 s。 由此可見， 本文所提出的IGWO算法整體收斂速度較快， 收斂效果更好， 減少了顧客存取車的等待時(shí)間。 IGWO算法的最優(yōu)存取序列如表3 所示， 其中， 第1列的數(shù)字1和第32列的數(shù)字1為對(duì)應(yīng)元素， 表示對(duì)1號(hào)車位進(jìn)行存車操作； 第22列的數(shù)字17和第53列的數(shù)字0為對(duì)應(yīng)元素， 表示對(duì)17號(hào)車位進(jìn)行取車操作。 其他組數(shù)據(jù)依此類推。

圖5 存車優(yōu)先算法對(duì)比

表3 存車優(yōu)先策略存取車序列

4.2.2 取車優(yōu)先

取車優(yōu)先仿真結(jié)果如圖6 所示， 使用IGWO算法得到的最短存取總時(shí)間為724 s。 最優(yōu)存取序列如表4 所示， 按此存取序列在取車優(yōu)先策略下進(jìn)行存取操作可使總存取操作時(shí)間最短。

表4 取車優(yōu)先策略存取車序列

圖6 取車優(yōu)先算法對(duì)比

4.2.3 交叉存取

交叉存取仿真結(jié)果如圖7 所示， IGWO算法最終得到的最短存取總時(shí)間為540 s， 與IGA算法相比總存取時(shí)間減少了198 s， 與GWO算法相比減少了109 s。 最優(yōu)存取序列如表5 所示。

表5 交叉存取策略存取車序列

圖7 交叉存取算法對(duì)比

表6 為IGWO算法、 GWO算法、 IGA算法在運(yùn)行10次后總存取時(shí)間的平均值， 表7 為IGWO與其余兩種算法總時(shí)間平均值的對(duì)比結(jié)果。 由表6、 表7 可知， 本文提出的IGWO算法在存取車調(diào)度時(shí)間上比GWO算法減少了18.8%～19.6%， 比IGA算法減少了31.1%～33.7%； 在3種存取策略中交叉存取策略所用的總時(shí)間最短， 在存取車數(shù)目相同時(shí)可優(yōu)先選擇交叉存取策略。

表6 IGWO， GWO， GA算法的總存取時(shí)間

表7 IGWO與GWO， IGA算法的對(duì)比結(jié)果

5 結(jié) 論

本文使用IGWO算法對(duì)巷道堆垛式立體車庫(kù)的存取調(diào)度進(jìn)行了優(yōu)化， 并通過仿真試驗(yàn)在存車優(yōu)先、 取車優(yōu)先、 交叉存取3種存取策略下與GWO算法、 IGA算法進(jìn)行了比較。 從實(shí)驗(yàn)結(jié)果可以看出， IGWO算法比GWO算法的總存取時(shí)間減少了18.8%～19.6%， 比IGA算法的總存取時(shí)間較少了31.1%～33.7%。 本文所提出的IGWO算法提高了存取車效率以及車庫(kù)效益， 為研究立體車庫(kù)調(diào)度問題提供了新思路。