陳晶晶,方葉祥,王文鳳

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

0 引言

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

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

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

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

1 問題描述和建模

1.1 問題描述

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

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

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

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

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

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

1.2 模型建立

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

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

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

(1)

(2)

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

D=D1+Dnode

(3)

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

Dulm=D1+2RnL

(4)

(5)

(6)

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

(7)

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

(8)

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

(9)

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

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

(10)

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

進(jìn)而可計(jì)算出AGV勻速運(yùn)動(dòng)在直線路段的總能耗Eulm:

(11)

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

(12)

(13)

(14)

(15)

(16)

m0≤my≤m0+Q

(17)

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

2 問題求解

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

圖1 求解框架

2.1 NSGA-Ⅱ算法

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

2.1.1 編碼

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

圖2 編碼示例

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

2.1.2 解碼

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

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

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

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

2.2 模型可靠性分析

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

表2 結(jié)果對(duì)比

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

2.3 AGV沖突檢測及避撞算法

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

2.3.1 主動(dòng)避撞機(jī)制

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

圖3 時(shí)間窗右移流程

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

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

(18)

2.3.2 被動(dòng)避撞機(jī)制

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

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

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

3 案例研究

3.1 案例描述

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

圖5 車間拓?fù)鋱D

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

表4 貨架的搬運(yùn)量

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

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

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

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

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

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

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

表7 情形對(duì)比

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

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

圖7 初始AGV路徑時(shí)間窗

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

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

4 結(jié)束語

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

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

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