基于改進禁忌搜索算法的立體車庫搬運器路徑優化建模與仿真

趙劍英, 李建國,2*, 薛千樹

(1.蘭州交通大學自動化與電氣工程學院, 蘭州 730070; 2.四電BIM工程與智能應用鐵路行業重點實驗室, 蘭州 730070)

平面移動式立體車庫采用與立體倉庫類似的原理和結構,入/出庫過程需要依靠搬運器轉運車輛,研究搬運器作業路徑與層列組合及顧客到達率關系,有助于提高車庫運行效率。

左為恒等[1]以排隊論為理論基礎,分析立體車庫車輛排隊過程,根據車輛到達率的變化,采用一種將堆垛機的數量和運行速度綜合考慮的調度方式,來降低立體車庫的運行能耗;Ly等[2]以最小化運行時間為優化目標,討論了自動導引搬運器系統(automated guided vehicle system,AGVS)在倉庫運營中的存儲分配策略和路徑規劃;Dong等[3]將四向穿梭車式密集倉儲系統(shuttle based storage and retrieval system,SBS/RS)建模為離散馬爾可夫鏈,推導出各策略組合下的往返分配,并進一步建立了單命令和雙命令操作的預期旅行時間模型;Wang等[4]提出了一種將禁忌搜索和遺傳算法相結合的混合算法來優化理論操作時間;改善算法的局部搜索能力的同時也不會損失多樣性;Yu等[5]在對自動存取系統 (automated storage and retrieval system,AS/RS)輸入輸出分析的基礎上,提出了一種混合禁忌搜索算法來解決存儲分配問題;文獻[6-7]分析了自動化導引搬運器(automated guided vehicle, AGV)運行環境,通過改進禁忌搜索算法優化全局搜索能力和收斂速度。文獻[8-10]對立體車庫和倉庫在建設過程中的層列組合方式[8],建設成本[9-10]進行分析研究;文獻[11-14]通過遺傳算法[11]、改進遺傳算法[12-13]以及粒子群算法[14]對立體車庫的調度設備運行路徑進行優化;許倫輝等[15]提出AGV動態路徑優化的時間窗模型,以此避免AGV路徑沖突;藺一帥等[16]提出了智能倉儲協同優化框架的求解算法,分析了貨位與路徑優化之間關系。然而,車庫中層列組合的分布影響搬運器運行環境,諸多文獻對自動化立體車庫路徑優化策略進行了不同深度的研究,但是綜合考慮車庫布局及顧客因素的路徑優化方案研究較少。

在建立多條件約束的平面移動式立體車庫搬運器最短服務時間調度模型基礎上,考慮層列組合及顧客到達率影響因素,提出一種改進禁忌搜索算法,在初始解效率最優庫位布局下進一步優化搬運器作業路徑,以實例車庫顧客泊車歷史數據進行可行性驗證,為提高立體車庫運行效率提供參考。

1 平面移動式立體車庫模型

平面移動式立體車庫可以根據場地和高度的不同進行參數的設計,其主體部分包括升降機(lift)、有軌導引搬運器(rail guided vehicle,RGV)、鋼構框架、載車板、入/出庫口(input/output point,I/O)、電氣控制系統等,其實體模型如圖1所示,以I/O口所在層為分界線分為地上部分和地下部分。

研究對象屬于AS/RS系統,其中RGV不僅可以水平移動還可以利用升降機進行跨層移動,入/出庫口用于車輛的進出,RGV用于與泊位實現入/出庫交換及車輛水平搬運。升降機(lift)主要用于對RGV及車輛進行跨層搬運。通過建立三維坐標系來描述RGV的運行場景,其中x軸表示RGV的水平移動方向,其值表示RGV所在位置的列坐標,y軸用來區分車位所在層,z軸表示RGV的垂直移動方向,其值表示RGV所在位置層坐標。

圖1 平面移動式立體車庫實體模型Fig.1 Solid model of flat mobile stereo garage

2 數學模型建立

2.1 配置條件

為表述方便,結合實際運行情況,以下為所研究平面移動式立體車庫的配置條件。

(1) 車庫車位分配策略為隨機就近分配,即入庫過程中為到達車輛選擇一個離到達位置最近的空車位。

(2) 空閑RGV待命位遵循原地待命策略,即在未收到新的入/出庫任務指令前,RGV停在最后一次入/出庫任務的結束位置處。

(3) 車庫中RGV、入/出庫口及升降機的占用均遵循先到先服務規則。

(4) 忽略RGV、升降機的啟動、制動時間及RGV進、出升降機時間。

(5) 同一時刻一個任務僅能調用一個RGV或一部升降機。

(6) 同一時刻車庫中的一個路徑節點僅被一個RGV占用,若同一時間同一節點發生多個RGV的沖突,則規定先收到指令的RGV先動作,其他進行等待直至其之前所有RGV完成操作。

2.2 基于服務時間最短的RGV調度模型

對于需要跨層搬運的入/出庫任務,RGV的運行過程包括水平方向與垂直方向,其中,垂直方向需升降機配合,當升降機處于繁忙或者與當前任務不在同層時,就會增加作業的服務時間。根據RGV不同運行階段場景及水平、垂直方向的運行時間分析,建立RGV完成入/出庫服務所消耗時間最短的調度模型,其目標函數為

(1)

(2)

(3)

ts,h,l,occupy=ts,m,h,l,waite+ts,m,h,l,actual

(4)

式中:ts,m,h表示編號為m的RGV在任務h的S運行階段的運行時間;S=1,表示RGV空載運行階段;S=2,表示RGV負載運行階段;ts,m,h,l,1(2)表示編號為m的RGV在任務h的S運行階段自待命位置運行至升降機l所在位置(自升降機l所在位置運行至泊車位置)的運行時間;yh,s,m、zh,s,m為決策變量;ts,m,h,l,occupy表示編號為m的RGV在任務h的S運行階段占用升降機l的運行時間;ts,m,h,l,waite表示編號為m的RGV在任務h的S運行階段等待升降機l的時間;ts,m,h,l,actual表示編號為m的RGV在任務h的S運行階段中升降機l的實際運行時間。

2.3 約束條件

考慮設備配置及安全問題,設置以下約束條件。

(1)RGV進入一段路徑的起始時間和離開該路徑的結束時間。

(2)每一個顧客任務只能使用一輛RGV。

(3)任務數不超過RGV配置總數。

(4)RGV運行最小安全距離。

計算公式為

(5)

(6)

(7)

(8)

(9)

2.4 改進禁忌搜索算法

禁忌搜索算法(tabu search,TS)基本原理為采用鄰近域選優方法,并通過禁忌表記錄狀態變化,當出現被禁解優于當前最好解時,引入藐視準則,最終通過迭代實現路徑尋優。

在2.2節基礎上,針對禁忌搜索算法隨機生成的初始解容易導致算法陷入局部最優解以及算法收斂速度較慢問題,對其進行改進,以求解立體車庫周期最短路徑問題。定義立體車庫單位工作周期RGV路徑轉移過程為:RGV從待命位置前往I/O口或泊車位置進行當前任務作業,完成當前任務后前往下一任務起始位置。根據立體車庫層列布局,建立C×F矩陣,初始禁忌長度為0,改進方法如下。

(1)以RGV服務時間調度模型構造初始路徑Sij的目標函數,將約束條件轉化為目標函數的懲罰項,將不符合約束條件的解懲罰,從而生成符合約束條件且服務時間最短的初始解。

(2)鄰域結構定義為部分節點(不滿足條件約束)與鄰近節點互換產生新的鄰近域N(Sij,n)。

改進后算法流程如圖2所示。

假設任務Oij初始路徑Sij上的第n個節點Sij,n處不滿足條件約束,主要表現為RGV間無法滿足最小安全距離,及路徑節點時間窗約束。針對該節點鄰近域N(Sij,n)生成候選解Sreg。以式(1)作為評價函數,若Sreg>Sij,則更新最優值,反之,若Sreg

圖2 改進禁忌搜索算法流程圖Fig.2 Flowchart of the improved forbidden search algorithm

N(Sij,n)={N|N=Sij,n+μ*Dm,l}

(10)

Dm,l∈{-1,+1}

(11)

式中:μ為單位步長,其值小于RGV最大前瞻節點數;Dm,l為方向決策變量,由于RGV在軌道雙向運行,即定義正方向交換為Dm,l=-1,反方向交換為Dm,l=+1。

2.5 立體車庫運行效率指標

以RGV平均服務時間、RGV平均利用率、RGV平均能耗作為運行效率評價指標。

(1) RGV平均服務時間Ts:由服務顧客總數與RGV服務總時間決定,其值越小說明車庫的運行效率越高。計算公式為

(12)

式(12)中:Tij為任務Oij自開始服務至服務結束所用時間;N為入庫車輛的總數;N′為出庫車輛的總數。

(2) RGV平均利用率Tρ:表示車庫1 d中RGV的平均繁忙程度,相同規模車庫,服務相同的顧客數量,則RGV平均利用率數值小表明入/出庫效率越高,對車庫運營者越有利,計算公式為

(13)

式(13)中:T′ij為RGV執行任務Oij空載運行階段時間;T″ij為RGV執行任務Oij負載運行階段時間;To為RGV執行1次存取所需時間,h為任務Oij的編號;Dij為RGV執行待命任務耗時;Tz為車庫1 d中運行總時間,m=1,2,…,M,M∈N+為RGV的編號。

(3) RGV平均能耗TQ:由各RGV運行能耗之和與服務總任務數及RGV總數量有關,表示每個RGV單個任務所消耗能耗,相同數量任務數及RGV總數的情形下,其數值越小表明其調度策略越優,計算公式為

(14)

式(14)中:P1、P2為RGV空載運行牽引功率和負載運行牽引功率。

3 仿真實驗與分析

實驗工程參數:RGV水平移動速度為1 m/s;升降機垂直升降速度為0.6 m/s;升降機數量L=2;

RGV數量M=3;入/出庫口數量為3個且并列排布,車位總列數記為C,車庫層高記為F;庫位高度為2.5 m,寬度為2 m,RGV入/出庫搬運時間為10 s且車輛到達進入、離開車廳總時間固定為30 s。

3.1 層、列組合影響分析

為研究立體車庫層列組合對算法初始解的影響,對不同層、列布局(C×F)的車庫模型進行仿真。考慮到車庫設備安全性與結構可靠性,以及占地面積,設置車庫層數所屬區間[4, 8],列數所屬區間[10, 26],保證庫位數量保持基本一致為依據,得出如表1所示層、列不同組合。

表1 層、列不同情況組合Table 1 Different combinations of layers and columns

依據RGV服務時間最短原則,對上述9種層列組合進行仿真,圖3為不同層列組合庫位下的RGV平均服務時間及RGV平均利用率反映情況。

觀察結果發現,當車庫層數由4→8,列數由26→10變化過程中,RGV平均服務時間先減小后增大,而RGV利用率變化為先增加后減小。分析層數與列數之比發現,層與列之比約在1/10→4/10的變化過程中運行效率指標逐步向好變化,在4/10→6/10時又逐步變差,這是由于升降機位于車庫巷道兩端,跨層作業RGV運行至目標位置距離即為RGV待命位置距配合側升降機位置與目標層升降機側位置距目標位置的距離之和,顯然,若將車庫以列一分為二,當1/2的總列數小于總層數時,可以認為此時影響RGV作業時間的主要因素為升降機,若升降機的使用頻率增加,則增加了等待升降機所用時間。以此推斷,立體車庫中層列比靠近1/2的層列組合方案,有利于RGV路徑優化策略。

當層列組合變化為6×16時RGV平均服務時間達到最小,這是由于隨著顧客到達率的增加,I/O所在層所容納車輛數逐漸飽和,當I/O所在層車輛飽和后跨層搬運車輛一方面受升降機狀態的影響,另一方面受兩RGV運行路徑沖突的影響,當車庫列即圖1中總層數x值小,列總層數y值大時,車輛在同一層的存取過程中,所受路徑沖突的影響變大即此時RGV平均服務時間開始增大。

綜上分析,當層數為6,列數為16時RGV最短服務時間調度模型生成的初始解效率指標最優。

圖3 層列組合方案效率指標仿真Fig.3 Simulation of efficiency metrics for layer column combination scheme

3.2 到達率影響分析

顧客到達率影響RGV路徑規劃的復雜度,主要表現為不同到達率下RGV利用率及單個RGV單位時間內作業目標位置數量不同,導致平均服務時間不同,為了驗證顧客到達率因素對所提算法影響,分別取顧客到達率λ=12,λ=20,λ=40,λ=60 veh/h情形下分兩組進行實驗,第一組為對照組,無路徑優化策略;第二組為本文設計策略組,分析對比結果如表2所示。

根據表2可以看出,當顧客到達率λ=12、20 veh/h時,RGV平均利用率均小于50%,較無優化策略組平均服務時間分別減小8.59%、10.29%;當顧客到達率λ=40、60 veh/h時,RGV平均利用率大于50%,較無優化策略組平均服務時間減小2.92%、1.50%。高利用率下,即隨著系統繁忙度增加,兩組實驗下RGV運行效率指標趨于相等,可以認為在RGV平均利用率小于50%的情形下本文所提RGV路徑優化算法表現更優。

表2 不同到達率下RGV運行效率指標Table 2 Operational efficiency index of RGV with different arrival rates

3.3 綜合效率評估

以6×16庫位布局建立矩陣地圖,取3.2節中λ=12 veh/h顧客到達率水平下某時間段一臺RGV位置轉移過程。在該顧客到達過程仿真開始之前,設置庫位狀態如圖4所示,黑色標記庫位表示占用狀態,白色標記庫位表示空閑狀態,RGV分配遵循就近分配原則。

根據以上庫位狀態信息及RGV位置信息,采用傳統禁忌搜索算法與本文改進禁忌搜索算法進行實驗。如圖5所示為兩種算法下路徑長度變化曲線,可以看出,二者初始優化效果相似,但改進禁忌搜索算法收斂速度更快,且最終得到可行性路徑長度更短。由此可見,改進禁忌搜索算法在更短的迭代過程下對路徑分配的優化效果更佳,適合本文模型的求解。

3.4 實例驗證

隨機抽取西安某商業立體車庫2017年7月連續一周顧客泊車歷史數據,在就近車位分配原則下以6層16列庫位布局進行可行性驗證,繪制RGV運行效率指標,如圖6所示,RGV平均服務時間為101.08 s,RGV平均運行能耗為289.54 kJ。

圖5 迭代過程路徑長度變化曲線Fig.5 Path length change curve during iterations

圖6 立體車庫運行效率指標Fig.6 Operational efficiency indicators of cubic garage

可以看出,RGV服務時間及運行能耗大部分沿平均值分布且平均服務時間小于120 s,符合3.2節表2中RGV平均利用率小于50%的情形下仿真結果,說明所提路徑優化算法在實際工程中有較強可行性。

4 結論

本文建立了以實際車庫入/出庫作業過程為基礎的RGV當前任務最小服務時間目標函數,提出一種帶有多條件約束的RGV服務時間最短調度模型,利用改進禁忌搜索算法對RGV作業路徑進行優化,仿真不同層列組合及不同到達率下RGV效率指標,得出如下主要結論。

(1)6×16層列組合庫位布局下初始解效率指標趨于最優。

(2)當顧客到達率較小時,即RGV平均利用率小于50%的情形下,算法更有利于車庫效率的提高。

(3)綜合考慮層列組合及到達率因素,改進后算法收斂速度更快,路徑搜索速度顯著提升。

(4)以連續一周顧客泊車歷史數據進行驗證,證明了所提路徑優化算法在實際工程中有較強可行性。

本研究對車庫綜合場景下的效率表現情況均進行了相關實驗及結果分析,所提路徑優化算法為提高立體車庫運行效率提供參考。在本研究基礎上,未來將對RGV路徑沖突對策進行進一步研究。