陳晶晶,方葉祥,王文鳳

(南京工業(yè)大學經濟與管理學院,南京 211816)

0 引言

自動引導車在貨物運輸時能夠有效的提高搬運效率、降低生產成本,是具有敏捷性、自動化等優(yōu)點的運輸工具[1],現(xiàn)如今節(jié)能減排已成為全球制造業(yè)實現(xiàn)可持續(xù)發(fā)展的共識[2]。制造型企業(yè)車間開始推行自動化改進,引入AGV進行貨物運輸,因此為AGV規(guī)劃出一條無沖突且節(jié)能的路徑,既可以提高AGV系統(tǒng)的整體運行效率也可以達到節(jié)能減排的效果。

AGV的路徑優(yōu)化已經成為國內外于倉儲車間中的主要研究問題之一[3],為了規(guī)劃出無沖突的路徑。楊潔等[4]對倉儲分揀庫區(qū)進行數學建模,采用兩個沖突解決方式不同的模型為分揀庫區(qū)多AGV規(guī)劃出無碰撞路徑。于會群等[5]以AGV完成任務的空載時間與AGV的空置率為優(yōu)化目標,改進Q-Learning算法生成多AGV無沖突路徑,最終完成多AGV路徑優(yōu)化。王然等[6]通過構建獎懲矩陣的形式,提出一種在線學習的Q-Learning算法,實現(xiàn)多AGV的無沖突路徑規(guī)劃。泰應鵬等[7]提出以時間窗為基礎的多AGV路徑規(guī)劃方法,對路徑沖突進行偵測,通過路徑變換、策略等待等方式解決。劉維民[8]為解決多AGV運行路徑利用率不均衡造成的碰撞問題,而提出基于時間窗的路徑算法,最后為多AGV系統(tǒng)規(guī)劃處一條利用率均衡且無沖突的路徑;張中偉等[9]通過時間窗檢測沖突類型,對多AGV系統(tǒng)規(guī)劃出無沖突路徑,將等待時間、行駛距離、任務緊急程度等作為量化動態(tài)優(yōu)先級策略。

針對車間AGV節(jié)能減排問題,郭亞銘等[10]以最短運輸距離和最小化能耗為目標優(yōu)化制造車間單AGV節(jié)能路徑規(guī)劃;李俊蘭等[11]針對AGV多任務運輸以運輸距離和能耗作為優(yōu)化目標,對AGV多運輸任務時合理安排順序和規(guī)劃運輸路徑能夠提升AGV能效;吳立輝等[12]建立節(jié)能路徑模型,優(yōu)化目標為最小能耗和搬運距離,提出改進Dijkstra算法和NSGA-Ⅱ算法集成的多載具AGV節(jié)能路徑規(guī)劃。WANG等[13]在研究AGV調度問題時,根據車間實際復雜度考慮對AGV能耗的影響,合理安排AGV的運輸路徑;宋栓軍等[14]在時間窗的基礎上,建立受負載和時間控制的能耗計算方法,以系統(tǒng)能耗最低為目標構建AGV沖突消解模型,該方法可以減少系統(tǒng)內的AGV的充電次數,提高多AGV系統(tǒng)的工作效率。

上述文獻主要研究了多AGV無沖突路徑規(guī)劃及考慮單AGV能源消耗的路徑規(guī)劃,然而現(xiàn)階段針對多AGV系統(tǒng)規(guī)劃無沖突路徑時考慮能耗指標、實現(xiàn)綠色節(jié)能路徑的較少,并在倉儲車間多AGV進行物流運輸領域開展節(jié)能減排路徑規(guī)劃的研究總體而言仍較為匱乏。針對現(xiàn)有多AGV能耗優(yōu)化無沖突路徑存在的問題,本文以倉儲車間環(huán)境下多AGV為研究對象,提出兩階段優(yōu)化方法。第一階段建立多目標節(jié)能優(yōu)化第模型,利用算例分析驗證模型的可靠性;第二階段對初始路徑進行沖突檢測及解決。最后以案例研究驗證了模型的有效性。

1 問題描述和建模

1.1 問題描述

本文采用拓撲圖表達倉儲車間環(huán)境,而倉儲車間內路線并不是完全相通的,會有部分區(qū)域禁止通行。引入三維變量定義部分連通無向圖為G=(W,A,B),其中W={0,1,2,…,n+1}為貨架和路徑交叉等具有特殊意義的節(jié)點集合,A={(i,j):i,j∈W,i≠j}是車間過道邊的集合,用dij表示邊之間的距離。B=min(i,j)表示尋找兩個節(jié)點間的最短距離。K={1,2,…,k}為AGV數量集合,每臺AGV起始點在同一位置,且各自有不同的目標節(jié)點。多AGV執(zhí)行任務時互為彼此的動態(tài)障礙物并且會產生能耗,問如何規(guī)劃出全局無沖突多AGV系統(tǒng)搬運路徑,以使得總時間最短,并且AGV總能耗最小,建模過程服從如下假設。

(1)本文針對單行雙向潛伏式AGV;

(2)AGV以勻速直線和勻速轉彎兩種速度行駛;

(3)每臺AGV的運輸的載重量、體積不會超過其額定載荷;

(4)AGV裝卸物料的時間包含在搬運時間以內;

(5)AGV不考慮AGV任務途中充電情況,且能連續(xù)工作無障礙。

1.2 模型建立

建立模型,定義參數和決策變量如表1所示。

表1 模型參數和決策變量定義表

(1)搬運時間。分析AGV搬運時間,首先要確定AGV的行走距離D。AGV行走距離D主要包括運輸遍歷節(jié)點間的距離D1和節(jié)點區(qū)域行駛距離Dnode,其中:

(1)

(2)

式中:nL表示直行通過節(jié)點數目,nT表示轉彎通過節(jié)點數目,即:

D=D1+Dnode

(3)

小車在運輸過程中速度保持不變,AGV勻速直線行駛的總距離Dulm和勻速轉彎行駛的總距離Dutm分別為:

Dulm=D1+2RnL

(4)

(5)

(6)

則AGV完成所有搬運任務的總搬運時間表示為:

(7)

(2)能耗。為降低分析AGV能耗難度,本文主要從AGV的運動角度進行切入,將搬運過程總能耗分解為待機能耗、勻速直線運動能耗Eulm和勻速轉彎運動耗能Eutm。Pso為AGV的待機運動功率,故AGV系統(tǒng)搬運過程最小總能耗表示為:

(8)

AGV做勻速直線運動時加速度為零,勻速轉彎時,車輛與地面的靜摩擦力完全提供向心力。設AGV勻速運動共有u個階段,其中勻速轉彎通過的節(jié)點有nT個,故勻速直線階段有u-nT個。因此,第y個勻速運動的驅動力。

(9)

式中:my表示第y個勻速運動階段AGV和貨物的總質量,kg;Cr為滾動摩擦系數。

即可計算出AGV勻速轉彎的總耗能Eutm:

(10)

式中:η表示行走驅動電機功率因數,θ表示AGV的轉向角度,R1、R2、R3、R4表示AGV四個車輪的轉彎半徑。

進而可計算出AGV勻速運動在直線路段的總能耗Eulm:

(11)

現(xiàn)以最小搬運時間和能耗為優(yōu)化目標,可建立數學模型:

(12)

(13)

(14)

(15)

(16)

m0≤my≤m0+Q

(17)

約束式(12)～式(13)表示變量的定義;約束式(14)～式(15)表示每個節(jié)點都能被訪問一下;約束式(16)表示每個任務節(jié)點只能由一輛AGV運輸;約束式(17)表示AGV運輸重量不能超過其最大載重。

2 問題求解

本文多AGV節(jié)能無沖突路徑規(guī)劃問題,提出兩階段優(yōu)化方法,如圖1所示。第一階段建立多目標數學模型,根據NSGA-Ⅱ算法求解出初始節(jié)能路徑;第二階段對路徑沖突進行檢測與解決,得出最優(yōu)路徑。

圖1 求解框架

2.1 NSGA-Ⅱ算法

在選擇、交叉、變異等算法上采用傳統(tǒng)NSGA-Ⅱ算法[16],鑒于本問題設計路徑和能耗兩類,本文重點介紹編碼和解碼算法,其余不作贅述。

2.1.1 編碼

針對n個搬運任務的場景,路徑規(guī)劃核心是對n個搬運任務搬運能耗最少的最短搬運路徑的選擇。采用實數編碼方式,將n個搬運任務隨機排列在染色體上,染色體上基因總數與搬運任務相對應,且每一個基因在染色體上只表達一次。例如:3輛AGV,10個搬運任務的實數編碼如圖2所示。

圖2 編碼示例

則3輛車的搬運任務分別表示為:0-2-5-8-0,0-4-7-10-1-0,0-3-7-9-0。

2.1.2 解碼

步驟1:根據染色體編碼獲得搬運任務基因位信息,按照滿足搬運重量條件約束下,分配到各輛AGV;

步驟2:若v輛AGV搬運重量小于等于極限重量,則染色體內第i個搬運任務分配到該AGV;若v輛AGV搬運重量大于極限重量,則染色體內第i個搬運任務分配到第v+1輛AGV;

步驟3:獲得各AGV的搬運路徑及路段間的距離,分析AGV行駛過程中的運輸載重量及拐彎次數,計算直線和拐彎行駛的能耗,通過式(8)求得能耗值、式(7)求得時間;

步驟4:重復步驟1～步驟3,直至解碼完成。

2.2 模型可靠性分析

為驗證1.2節(jié)中提出的多目標模型的可靠性,以文獻[15]中的算例為例。應用本文模型,采取NSGA-Ⅱ算法求解得出初始節(jié)能路徑,本文計算結果與文獻[15]計算結果對比如表2所示。

表2 結果對比

由表2可知,本文模型的計算結果與文獻[15]的結果一致度較高,因此驗證了本文提出多目標節(jié)能模型的可靠性。

2.3 AGV沖突檢測及避撞算法

依據NSGA-Ⅱ算法求解出的初始節(jié)能路徑,判斷多AGV系統(tǒng)同時運行時可能發(fā)生的沖突[17],常見沖突類型:相向沖突、節(jié)點沖突和占位沖突。本文主要采用時間窗[9]的思想進行判斷AGV沖突類型并通過避撞機制解決沖突。

2.3.1 主動避撞機制

(1)時間窗右移方法。時間窗右移是處理沖突常見的策略,當某個路段出現(xiàn)AGV沖突,采用時間窗右移時,所有受影響的路段時間窗都需要推遲一段時間,流程如圖3所示。

圖3 時間窗右移流程

圖4 基于時間窗的動態(tài)優(yōu)先級的任務分配算法

(2)動態(tài)優(yōu)先級策略。動態(tài)優(yōu)先級策略考慮的因素有等待時間、距離以及負載程度,主要原因如下:①當AGV發(fā)生沖突時,若等待時間過長,設置高優(yōu)先級可以減少過長的等待時間,同時可以避免因長時間等待而引發(fā)新的占位沖突;②考慮AGV路徑距離,當AGV到任務節(jié)點的剩余路徑較長時,設置高優(yōu)先級優(yōu)先執(zhí)行任務,可有效減少等待浪費的時間,從而縮短運輸時間;③實時考慮AGV行駛時的載重情況,當AGV到目標點的負載較大,需提高AGV優(yōu)級才能使其盡早完成運輸任務。優(yōu)先級數學模型:

(18)

2.3.2 被動避撞機制

多AGV系統(tǒng)的實際運行中,會出現(xiàn)一些不可預見的因素影響車輛的運行,例如:AGV突發(fā)故障、貨物掉落等。當遇這些情況時,采取被動避撞機制對AGV進行路徑二次規(guī)劃。具體步驟如下:

步驟1:根據AGV上傳的位置路段設為不可通行區(qū)域,同時為后續(xù)要經過此路段的車輛重新規(guī)劃路線,得出新的初始路徑;

步驟2:根據求解出的初始路徑,建立各路段時間窗,再次采取時間窗與動態(tài)優(yōu)先級結合的主動避撞機制檢測沖突并調整至全局無沖突路徑。

3 案例研究

3.1 案例描述

為驗證本文提出優(yōu)化方法的有效性,本文采用某太陽能光伏組件制造企業(yè)的一個硅片倉儲車間數據進行實驗。所建立車間拓撲地圖如圖5所示(0為揀貨區(qū),01,02為AGV?？奎c,1,2,…,20為貨架),轉彎半徑R為0.8 m。車間選用6輛額定功率為80 W的其技術參數如表3所示,車間各貨架的搬運量如表4所示。

圖5 車間拓撲圖

表3 AGV技術參數

表4 貨架的搬運量

3.2 優(yōu)化方法的有效性分析

首先利用NSGA-Ⅱ算法求解數學模型,關鍵參數設置如表5所示。

表5 關鍵參數設置

求解模型得出Pareto解對應的優(yōu)化目標值如圖6所示。

圖6 初始節(jié)能Pareto集

為對比能耗優(yōu)化效果,本文選擇Pareto解集中對應能耗最低的解進行分析,如表6所示。

分兩種情形驗證模型節(jié)能效果的有效性:情形1下AGV執(zhí)行運輸任務的順序可優(yōu)化調整,僅關注搬運時間T。情形2下AGV執(zhí)行運輸任務的順序可優(yōu)化調整,綜合考慮搬運時間T和總能耗Etotal。求解結果如表7所示。

表7 情形對比

兩種情形都得到了最短搬運時間,而情形2與情形1相比,能耗降低11.84%。因為情形2綜合考慮搬運時間和能耗兩個優(yōu)化目標,在AGV執(zhí)行運輸任務時,加入考慮AGV的能源消耗,得出既能保證搬運效率又能有效降低AGV能耗的搬運路徑。

針對多AGV系統(tǒng)進行運輸任務時容易發(fā)生沖突問題,根據不同沖突類型進行消除。經第一階段路徑規(guī)劃模型計算得出各AGV的初始節(jié)能路徑安排如表5所示,得出初始AGV路徑時間窗如圖7所示,進而第二階段沖突檢測及避撞算法,采用動態(tài)優(yōu)先級策略,結合圖3沖突消減流程處理AGV沖突。節(jié)點沖突判斷的時間閾值δ取2.67 s,α=β=γ=1/3。

圖7 初始AGV路徑時間窗

圖8 動態(tài)優(yōu)先級策略消減沖突后的AGV路徑時間窗

多AGV系統(tǒng)在完成運輸任務時易出現(xiàn)沖突問題,故在對模型所得的初始路徑進行碰撞調整,由圖所知AGV2、AGV4、AGV6執(zhí)行運輸任務的時間未受到優(yōu)先級策略的影響,盡管AGV1、AGV3、AGV6在執(zhí)行運輸任務的時間有所增加,但是AGV系統(tǒng)總的運輸時間并沒有發(fā)生變化?？芍趧討B(tài)優(yōu)先級的策略有效避免了沖突問題,既能做到降低路徑上車輛堵塞又能做到提高系統(tǒng)的運行效率。

4 結束語

針對部分連通車間多AGV系統(tǒng)動態(tài)無沖突節(jié)能路徑規(guī)劃問題,提出兩階段優(yōu)化方法進行求解,首先建立以搬運時間和能耗為優(yōu)化目標的多AGV節(jié)能路徑規(guī)劃模型,求解出初始節(jié)能路徑。然后利用時間窗檢測沖突類型,構建動態(tài)優(yōu)先級策略進行主動避撞機制。當出現(xiàn)突發(fā)情況時,通過被動避撞機制對AGV進行重調度,以規(guī)劃出全局多AGV無沖突路徑?；诎咐芯勘砻?

(1)采用NSGA-Ⅱ算法求解模型,分兩種情形進行分析對比,發(fā)現(xiàn)在綜合考慮搬運時間和能耗的情形下,能夠保證搬運時間最短的基礎上,同時能耗能夠降低11.84%,驗證模型的有效性。

(2)分析出AGV系統(tǒng)運輸過程中的沖突類型,采用動態(tài)優(yōu)先級策略解決沖突問題可縮短任務完成時間,解決車輛堵塞,該方法靈活簡單。在未來工作中可以加入考慮AGV電量情況、充電類型進行規(guī)劃,獲取均衡的沖突解決節(jié)能路徑。