窮舉-混沌蟻群算法環(huán)形穿梭車模型研究

劉緒川，王 龍，梅英杰，張孟建

（1.中科芯集成電路有限公司，無錫214072；2 哈爾濱工業(yè)大學(xué) 儀器科學(xué)與工程學(xué)院，哈爾濱150001；3.貴州大學(xué) 電氣工程學(xué)院，貴陽550025）

近年來，自動化物流系統(tǒng)[1-2]日益廣泛地應(yīng)用于煙草、機電、醫(yī)藥、食品、軍隊等領(lǐng)域，相關(guān)物流裝備趨于多元化，其水平和技術(shù)性能不斷提高。自動化倉庫作為物流系統(tǒng)中一個重要的組成部分，其不僅具有傳統(tǒng)倉庫的存儲功能，還具有揀選、盤點、理貨等功能，而且其設(shè)備自身及物料存取操作都能自動進行，這大大提高了倉儲效率，同時節(jié)省勞動力，受到了廣泛的關(guān)注。立體倉庫系統(tǒng)在食品、醫(yī)藥、煙草、玻纖、家具等行業(yè)應(yīng)用日漸廣泛，以立體倉庫系統(tǒng)為核心的相關(guān)物流設(shè)備愈加多元化，技術(shù)水平和性能也得到不斷提高。

穿梭車又稱為軌道式自動導(dǎo)引車RGV[4-6]，是集多種高新技術(shù)于一體的自動搬運設(shè)備，因行駛和輸送速度快、靈活性好、自動化程度高而被廣泛應(yīng)用。經(jīng)過長期的發(fā)展，環(huán)形RGV 系統(tǒng)代替了多臺直行RGV 系統(tǒng)或者大量的普通輸送設(shè)備，實現(xiàn)物料運送目的地的自由變動，提高了輸送的效率和靈活性。環(huán)形RGV 系統(tǒng)其最主要的應(yīng)用是作為連接立體倉庫入庫作業(yè)區(qū)站臺、出庫作業(yè)區(qū)站臺和立體倉庫站臺的紐帶，起搬運物料的作用，是立體倉庫系統(tǒng)主要且重要的子系統(tǒng)。由于環(huán)形RGV 系統(tǒng)采用封閉的環(huán)形軌道，RGV 單向環(huán)軌繞圈行駛，相鄰兩車之間存在防止碰撞的安全距離，針對不同項目系統(tǒng)的軌道數(shù)據(jù) （直道長度、彎道長度和轉(zhuǎn)彎半徑等）、RGV 運行參數(shù)（直道行駛速度、彎道行駛速度和加速度等）、裝卸載站臺數(shù)量及位置分布、物流的需求量等參數(shù)的不同，RGV 的數(shù)量有著很大的差異[3，7-8]。

穿梭車在整個工作系統(tǒng)中，其效率受到出進貨口停留時間、車身長度、穿梭車數(shù)、運行速度等影響。若穿梭車過多，會造成擁堵，甚至?xí)到y(tǒng)癱瘓，大大降低了工作運行效率。若穿梭車較少，雖然不會造成系統(tǒng)擁堵，但是會使得貨物運輸時間較長，貨物運輸?shù)男式档?。因此合理的穿梭車調(diào)度，在合適的運行速度下，減少擁堵時間，會使得整個工作系統(tǒng)效率提高。

1 模型假設(shè)

假設(shè)1：為方便貨物的搬運，假設(shè)每側(cè)的進、出貨口均勻分布在軌道的直線上。

假設(shè)2：假設(shè)每輛穿梭車每次只能運送1 件貨物。

假設(shè)3：假設(shè)穿梭車裝、卸貨物的時間相同，分別為tL、tU，一個周期為T s。

假設(shè)4：假設(shè)穿梭車的貨運軌道為單軌道設(shè)計，穿梭車不能超車，只能進行停車和前進。

假設(shè)5：假設(shè)穿梭車在環(huán)形軌道上逆時針勻速運行，其速度為v。

假設(shè)6：假設(shè)每側(cè)的進、出貨口均勻地分布在軌道的起點中線兩側(cè)，其間隔為3 m。

A 側(cè)進貨口待進的貨物量為200 件，B 側(cè)總的待進貨數(shù)量為322 件。從B 側(cè)進貨、A 側(cè)出貨時，所對應(yīng)的進貨口和出貨口之間的距離，其值如表1所示。

表1 B 側(cè)進貨A 側(cè)出貨對應(yīng)的進貨口距離（考慮車長，m）Tab.1 Distance of the receiving port corresponding to the B-side purchasing and A-side shipping（considering the vehicle length，m）

表2 所示為一些主要符號含義。

表2 符號說明Tab.2 Symbol description

2 模型建立

考慮系統(tǒng)的運行效率，使得穿梭車運送貨物能夠得到高效運行，在穿梭車數(shù)量合適情況下，盡可能保證不擁堵，提高系統(tǒng)效率。

2.1 模型1

基于以上對問題的分析和理解，建立單個穿梭車的裝、卸貨物和運行的耗時模型，其公式如下：

式中：T1為小車在環(huán)形軌道上運行的時間；T2為小車裝、卸貨物所需的時間；T3為運行過程中等待的時間。

式中：S 為小車完成1 次裝、卸貨物在環(huán)形軌道上所通過的路程；v 為小車的行駛速度。

此外，小車裝、卸貨物所需的時間為

式中：tL為小車裝貨所需要的時間；tU為小車卸貨所需要的時間；n 為裝卸貨物的次數(shù)。

2.2 模型2

本文為了清楚地描述穿梭車的數(shù)量變化對系統(tǒng)的擁堵次數(shù)、完成工作量所需要的時間之間的關(guān)系。采用最小二乘多項式擬合，建立n 次多項式模型：

2.3 起點中線規(guī)則

為了方便后續(xù)算法分析，穿梭車軌道L=100 m，穿梭車運行速度v=1.5 m/s，裝卸貨一個周期T=10 s，軌道上出貨口7 個，進貨口6 個，考慮實際穿梭車車長約1.3 m，進出貨口寬度1 m。設(shè)計環(huán)形軌道如圖1 所示。

圖1 考慮車長的環(huán)形軌道示意圖Fig.1 Schematic diagram of circular track considering vehicle length

3 模型設(shè)計分析

3.1 窮舉式算法

窮舉式算法在小車數(shù)量少的情況下，可以比較精確地得到最優(yōu)調(diào)度，所占用的資源也不多，其在本文的流程是：在滿足約束的情況下，保證排隊最少的情況下，小車行駛的最短距離即可當做目標最短時間。當A、B 側(cè)均有貨物時，小車優(yōu)先載運B 側(cè)的貨物，并從最遠的進貨口進行裝貨，到達A 側(cè)卸貨時，以最遠的出貨口為優(yōu)先出貨口；當B 側(cè)的有貨進貨口數(shù)目少于小車數(shù)量時，小車開始對A 側(cè)的進貨口進行載運，由于A 側(cè)的貨物有固定的出貨口，本文選擇dA1k和dA2k（dAjk表示A 側(cè)進貨口j 中的第k 個貨物在B 側(cè)的目標出貨口）中貨號口更大的進行載運。假設(shè)系統(tǒng)中N 量穿梭車Ci（i 表示從0～N），每輛車到進貨口的距離為dQjCi，則組成的矩陣為

當有t 個任務(wù)時，每一輛穿梭車到對應(yīng)的進貨口都有對應(yīng)的距離，通過這些值可以窮舉出穿梭車的行徑組合有種；對于這些組合可以選取矩陣中不同列和不同行對應(yīng)的距離之和最短的數(shù)值，因為小車排隊最少，所以該值即可當做最優(yōu)解。

3.2 基于混沌蟻群算法的穿梭車處理貨物的調(diào)度規(guī)劃

由于蟻群算法[9-10]在進行穿梭車調(diào)度時存在操作時間長、收斂效率低、易陷入局部最優(yōu)等缺陷。而混沌理論利用混沌運動特有的內(nèi)在遍歷性、規(guī)律性和隨機性可以在一定范圍內(nèi)不重復(fù)地遍尋所有狀態(tài)，跳出局部最優(yōu)解，具有良好的計算精度和全局尋優(yōu)能力。因此將混沌理論加入到基本蟻群算法中可有效改善基本蟻群算法的弊端，得到較優(yōu)的算法，從而規(guī)劃出全局最優(yōu)。因此我們建立了混沌蟻群算法模型。

混沌蟻群算法的穿梭車規(guī)劃算法流程如圖2所示。

3.3 基于蒙特卡洛的出貨口選擇算法

根據(jù)問題背景可以得到，此環(huán)形穿梭車系統(tǒng)共有兩側(cè)，分別為A、B 側(cè)，兩側(cè)均有進貨口，亦有出貨口。B 側(cè)的進、出口數(shù)量相等，均為4 個，將進貨口的編號 設(shè)為I，其中I＝1，2，3，4； 出貨口設(shè) 為J，J＝1，2，3，4。

而對應(yīng)的A 側(cè)出貨只有3 個，因此，針對B側(cè)作為進貨口時，其出貨口位于A 側(cè)，但是出貨口的選擇是隨機的，基于這一特點，本文設(shè)計了基于蒙特卡洛的出貨口選擇算法，該算法的核心為代碼如下：

3.4 算法分析

步驟1使用蒙特卡洛的出貨口選擇算法計算出B 側(cè)作為進貨口的情況下，單輛穿梭車完成對應(yīng)進貨口的工作任務(wù)所需要的時間；B 側(cè)4 個進貨口分別完成工作量所需時間。

步驟2由于A 側(cè)的進貨口有待貨出口時，每個進貨口均指定了B 對應(yīng)的出貨口。因此，在計算完成貨物量所需要的時間前，應(yīng)根據(jù)起點中線規(guī)則（考慮車長）計算出進貨口和出貨口之間的距離，如圖3 所示。

圖3 A 側(cè)進貨口與B 側(cè)各出貨口之間的距離Fig.3 Distance between A-side inlet and B-side outlet

步驟3根據(jù)穿梭車運動規(guī)則和各進、出貨口之間距離關(guān)系，使用蒙特卡洛方法進行模擬，分別取N＝1，3，6，7，9 進行計算，模擬了4 組結(jié)果，所得結(jié)果如圖4 所示。

圖4 穿梭車數(shù)量與完成工作的耗時關(guān)系圖Fig.4 Relationship between the number of shuttle cars and the time taken to complete the work

從圖4 中可以明顯地看出，完成一定數(shù)量的工作量的情況下，即系統(tǒng)能夠接受的范圍內(nèi)，完工的時間與穿梭車的數(shù)量成反比。

步驟4對環(huán)形穿梭車系統(tǒng)效率，我們考慮穿梭車的擁堵時間以及在單位時間內(nèi)系統(tǒng)最大貨物吞吐量來評價系統(tǒng)效率。在N≤5 時，用窮舉式算法求取穿梭車擁堵時間、貨物處理總耗時以及單位時間內(nèi)系統(tǒng)最大貨物吞吐量。在N＞5 時，用混沌蟻群算法找到最優(yōu)穿梭車擁堵時間、貨物處理總耗時以及單位時間內(nèi)系統(tǒng)最大貨物吞吐量。其擬合結(jié)果如圖5 所示。

圖5 擬合結(jié)果Fig.5 Fitting results

結(jié)果表明系統(tǒng)的擁堵次數(shù)和擁堵時間會隨小車數(shù)目增加而明顯增加；系統(tǒng)的總完工時間在與穿梭車數(shù)目之間是一個先減少后增加的關(guān)系，系統(tǒng)在單位時間內(nèi)的最大貨物吞吐量與穿梭車之間是一個先增加后減少的關(guān)系，可以得知穿梭車后期的擁堵會造成系統(tǒng)運行效率的降低。故為保證穿梭車系統(tǒng)的效率，需要選擇合適的小車數(shù)目。

4 結(jié)語

根據(jù)本文建立的模型和使用的算法，不同數(shù)量的穿梭車情況下，對單位時間貨物吞吐量、處理貨物的耗時情況、擁堵時間以及擁堵次數(shù)進行分析，找到最合適的小車數(shù)，保證系統(tǒng)的效率。本模型可用于工廠環(huán)形穿梭車系統(tǒng)的構(gòu)建，實際運用中對參數(shù)的優(yōu)化存在一定的實際價值，對自動化物流系統(tǒng)有重要意義。