考慮能耗的多AGV系統(tǒng)無沖突路徑規(guī)劃*

陳晶晶,方葉祥,王文鳳

(南京工業(yè)大學(xué)經(jīng)濟與管理學(xué)院,南京 211816)

0 引言

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

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

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

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

1 問題描述和建模

1.1 問題描述

本文采用拓撲圖表達倉儲車間環(huán)境,而倉儲車間內(nèi)路線并不是完全相通的,會有部分區(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數(shù)量集合,每臺AGV起始點在同一位置,且各自有不同的目標(biāo)節(jié)點。多AGV執(zhí)行任務(wù)時互為彼此的動態(tài)障礙物并且會產(chǎn)生能耗,問如何規(guī)劃出全局無沖突多AGV系統(tǒng)搬運路徑,以使得總時間最短,并且AGV總能耗最小,建模過程服從如下假設(shè)。

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

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

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

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

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

1.2 模型建立

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

表1 模型參數(shù)和決策變量定義表

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

(1)

(2)

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

D=D1+Dnode

(3)

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

Dulm=D1+2RnL

(4)

(5)

(6)

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

(7)

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

(8)

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

(9)

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

即可計算出AGV勻速轉(zhuǎn)彎的總耗能Eutm:

(10)

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

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

(11)

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

(12)

(13)

(14)

(15)

(16)

m0≤my≤m0+Q

(17)

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

2 問題求解

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

圖1 求解框架

2.1 NSGA-Ⅱ算法

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

2.1.1 編碼

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

圖2 編碼示例

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

2.1.2 解碼

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

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

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

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

2.2 模型可靠性分析

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

表2 結(jié)果對比

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

2.3 AGV沖突檢測及避撞算法

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

2.3.1 主動避撞機制

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

圖3 時間窗右移流程

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

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

(18)

2.3.2 被動避撞機制

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

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

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

3 案例研究

3.1 案例描述

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

圖5 車間拓撲圖

表3 AGV技術(shù)參數(shù)

表4 貨架的搬運量

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

首先利用NSGA-Ⅱ算法求解數(shù)學(xué)模型,關(guān)鍵參數(shù)設(shè)置如表5所示。

表5 關(guān)鍵參數(shù)設(shè)置

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

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

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

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

表7 情形對比

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

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

圖7 初始AGV路徑時間窗

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

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

4 結(jié)束語

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

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

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