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

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

0 引 言

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

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

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

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

1 巷道堆垛立體車庫概述

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

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

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

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

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

在存取車的整個過程中， 升降機、 旋轉(zhuǎn)臺都是確定的， 它們的運行時間也是確定的， 但堆垛機的運行時間卻不確定， 這主要是由于存取車時的車位不確定， 堆垛機空閑時的?？课恢貌淮_定， 堆垛機行進路線不確定等原因造成的。 因此， 存取車位的分配、 堆垛機運行路徑的規(guī)劃以及堆垛機空閑時的?？课恢玫仁橇Ⅲw車庫存取策略的主要研究內(nèi)容。

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

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

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

(1)

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

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

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

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

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

(2)

2.3 交叉存取策略

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

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

(3)

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

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

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

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

圖3 狼群等級層次的劃分

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

3.1.1 包圍獵物

灰狼從搜索區(qū)域內(nèi)發(fā)起攻擊， 將對獵物進行包圍狩獵[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為種群個體與獵物之間的距離；Xp為獵物的位置向量；X為灰狼的位置向量。

向量A,C的計算公式為

A=2a·r1-a，

(6)

C=2·r2，

(7)

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

(8)

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

3.1.2 狩獵

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

(9)

(10)

(11)

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

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

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

(12)

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

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

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

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

3.3 IGWO算法實現(xiàn)

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

3.3.1 編碼與解碼

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

表1 部分編碼序列

3.3.2 種群初始化

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

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

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

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

(13)

式中：ti表示各個策略下存取車所使用的總時間。

3.3.4 位置更新

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

個體2： 5 4 3 2 1 0 1 0 1 1

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

個體2： 3 1 5543210 1 001011

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

個體2： 3 1 5 4 2 0 1 0 1 1

3.3.5 局部尋優(yōu)

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

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

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

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

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

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

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

4 結(jié)果與分析

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

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

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

4.2 實驗結(jié)果與分析

為了驗證IGWO算法對車庫存取調(diào)度時間的影響， 將其與GWO以及文獻(xiàn)[4]中的改進遺傳算法(IGA)進行比較。 3種存取策略采用相同的存取次數(shù)。 該巷道堆垛式立體車庫共有31個車位， 假設(shè)在某時段有21輛車待存入， 10輛車待取出， 目標(biāo)函數(shù)為存取完全部車輛所需的總時間， 目標(biāo)函數(shù)值越小代表算法效果越好。 實驗環(huán)境為PC， 仿真軟件為MATLAB R2020b， PC主機為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 所示， 實驗結(jié)果表明IGWO算法比GWO和IGA算法效果好。 IGWO算法在第100次迭代后得到的最短存取總時間為832 s， GWO與IGA分別在迭代110次和140次后才逐漸收斂， 最終結(jié)果分別為1 043 s和1 263 s。 由此可見， 本文所提出的IGWO算法整體收斂速度較快， 收斂效果更好， 減少了顧客存取車的等待時間。 IGWO算法的最優(yōu)存取序列如表3 所示， 其中， 第1列的數(shù)字1和第32列的數(shù)字1為對應(yīng)元素， 表示對1號車位進行存車操作； 第22列的數(shù)字17和第53列的數(shù)字0為對應(yīng)元素， 表示對17號車位進行取車操作。 其他組數(shù)據(jù)依此類推。

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

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

4.2.2 取車優(yōu)先

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

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

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

4.2.3 交叉存取

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

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

圖7 交叉存取算法對比

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

表6 IGWO， GWO， GA算法的總存取時間

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

5 結(jié) 論

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