李俊蘭 張中偉 吳立輝 武照云

(河南工業(yè)大學(xué)機電工程學(xué)院，河南 鄭州 450001)

智能制造已成為全球制造業(yè)發(fā)展的重要趨勢，在“工業(yè)4.0”智能制造框架內(nèi)，智能物流被認(rèn)為是實現(xiàn)智能制造的核心與關(guān)鍵[1]，而自動導(dǎo)引運輸車(automated guided vehicle，AGV)則是實現(xiàn)智能物流的重要物料運輸設(shè)備。隨著全球應(yīng)對氣候變化壓力的持續(xù)增大，制造業(yè)節(jié)能減排意識不斷提高。物料運輸系統(tǒng)是車間制造系統(tǒng)的重要組成部分，其能耗是車間生產(chǎn)能耗中不可忽視的部分。然而，車間節(jié)能生產(chǎn)研究長期聚焦在機床，以AGV為代表的物料運輸設(shè)備較少被關(guān)注[2]。因此，研究AGV運輸過程的能耗優(yōu)化問題，對于車間節(jié)能生產(chǎn)具有重要的現(xiàn)實意義。

能耗建模是能耗優(yōu)化的基礎(chǔ)技術(shù)。圍繞AGV能耗建模，目前主要從車輛運動角度進(jìn)行能量分解，考慮一些實際應(yīng)用環(huán)境因素，如車輛結(jié)構(gòu)特性，電池充放電效率等，基于物理運動學(xué)理論進(jìn)行研究[3-5]。這些工作為量化評估和預(yù)測AGV運輸能耗提供了指導(dǎo)。進(jìn)而，一些學(xué)者開展了AGV能耗優(yōu)化研究，例如：王晨曦[6]研究了作業(yè)車間AGV綠色物流調(diào)度問題，建立了以AGV能耗和調(diào)度時間為目標(biāo)的AGV物流調(diào)度優(yōu)化模型，并提出了一種改進(jìn)遺傳粒子群算法進(jìn)行求解；筆者研究團(tuán)隊建立了以運輸距離和能耗為優(yōu)化目標(biāo)的節(jié)能單負(fù)載AGV路徑規(guī)劃模型，分別提出了兩階段求解方法和基于粒子群優(yōu)化算法(particle swarm optimization，PSO)的求解方法[5-7]。然而，目前AGV能耗優(yōu)化研究非常有限，總結(jié)可得出結(jié)論：①節(jié)能路徑規(guī)劃是提升AGV使用能效的一種可行方法，能耗可作為AGV路徑規(guī)劃的獨立優(yōu)化目標(biāo)；②當(dāng)AGV執(zhí)行多項運輸任務(wù)時，任務(wù)的執(zhí)行順序會影響節(jié)能效果，但當(dāng)前研究主要面向單負(fù)載AGV和單項運輸任務(wù)，缺乏有效的面向多運輸任務(wù)的節(jié)能AGV路徑規(guī)劃(energy-efficient AGV path planning，EAPP)理論和方法指導(dǎo)。

針對現(xiàn)有AGV能耗優(yōu)化研究存在的問題和不足，本文以離散制造車間環(huán)境下的單負(fù)載AGV為研究對象，進(jìn)行面向多運輸任務(wù)的EAPP研究，建立了以運輸距離和能耗為優(yōu)化目標(biāo)的EAPP模型，進(jìn)而提出一種兩階段求解方法，并通過案例研究驗證了模型的節(jié)能有效性。

1 問題描述與建模

1.1 模型假設(shè)

面向多運輸任務(wù)的EAPP研究用拓?fù)涞貓D表示車間環(huán)境，將AGV運輸網(wǎng)絡(luò)抽象為一個無向圖G=(V,A)，其中V={1,2,…，n}是車輛裝/卸貨、道路交叉位置等具有特殊意義的節(jié)點集合，A={(i,j):i,j∈V,i≠j}是節(jié)點之間路徑的邊集合，且邊(i,j)的權(quán)重用直接連接節(jié)點i和j的路段距離dij表示。在筆者研究團(tuán)隊前期AGV運輸過程能耗建模研究假設(shè)的基礎(chǔ)上[7]，本研究增加以下與運輸任務(wù)相關(guān)的假設(shè)條件：

(1)所有運輸任務(wù)零時刻下達(dá)，且AGV可用。一旦AGV開始執(zhí)行運輸任務(wù)，不能中斷或者取消。

(2)AGV初始不在任意運輸任務(wù)的起始節(jié)點，執(zhí)行各運輸任務(wù)時不允許后退或形成回路。當(dāng)執(zhí)行完最后一項運輸任務(wù)，AGV停在其目標(biāo)節(jié)點。

1.2 模型表示

對于零時刻下達(dá)的m項運輸任務(wù)，各任務(wù)k(k=1,2,…,m)的取貨起始節(jié)點Pk和運輸目標(biāo)節(jié)點Ck事先給出，Pk,Ck∈V，且Pk≠Ck。定義決策變量xkq表示運輸任務(wù)k和q(q=1,2,…,m，且k≠q)的執(zhí)行順序：

設(shè)AGV空載質(zhì)量為m0，最大載重量為Q?；谘芯考僭O(shè)，AGV執(zhí)行完全部運輸任務(wù)，交替出現(xiàn)的空載和負(fù)載運輸階段總數(shù)為2m。AGV在各運輸階段的行駛路徑可用其遍歷過的有序節(jié)點組成的集合Sl表示，l=1,2,…,2m，Sl?V，且2≤|Sl|≤n。當(dāng)l=1,2,…,m時，Sl表示AGV在與運輸任務(wù)序號相對應(yīng)的負(fù)載運輸階段行駛路徑；當(dāng)l=m+1,m+2,…,2m時，Sl表示AGV在第l-m個空載運輸階段行駛路徑。給定Sl時，基于研究假設(shè)和物理動力學(xué)理論可確定AGV到達(dá)各運輸任務(wù)k起始節(jié)點、目標(biāo)節(jié)點的時間TPk和TCk。進(jìn)而，以全部運輸任務(wù)的總完成時間Ttotal作為分析AGV能耗的時間邊界，其可表示為：

Ttotal=max{TCk},k=1,2,…,m

(1)

分析AGV總運輸Etotal需要先計算各運輸階段的AGV能耗，然后累加求和。時間邊界以及AGV運輸過程能耗的分析計算方法可參考文獻(xiàn)[7]。此外，定義整數(shù)決策變量yijl來反映各運輸階段AGV行駛經(jīng)過的邊信息：

AGV總運輸節(jié)點間距離D則可表示為：

(2)

EAPP模型優(yōu)化目標(biāo)可表示為：

(3)

約束為：

m0≤Mk≤m0+Q,?k

(4)

TPq-TCk+H(1-xkq)≥0,?k,q

(5)

TPk-TCq+Hxkq≥0,?k,q

(6)

(7)

(8)

(9)

約束條件式(4)中Mk為AGV執(zhí)行運輸任務(wù)k時的車輛和貨物總重，該式表示AGV在任一負(fù)載運輸階段的載荷不應(yīng)超過其載重極限。式(5)和(6)表示任意兩個負(fù)載運輸階段不允許時間重疊，其中H是一正極大數(shù)，從而可以確定運輸任務(wù)執(zhí)行順序。式(7)和(8)分別表示在各運輸階段規(guī)劃路徑Sl中包含的每個節(jié)點只能被訪問一次和只能通過一條邊離開。式(9)用來約束AGV在各運輸階段不允許后退和環(huán)路行駛。

2 模型求解

AGV在各空載/負(fù)載運輸階段的可行規(guī)劃路徑Sl往往不唯一，各運輸階段路徑規(guī)劃最優(yōu)難以保證整體路徑規(guī)劃效果最優(yōu)。為此，提出一種兩階段方法求解EAPP模型，其流程如圖1所示。

在第1階段，借鑒現(xiàn)有研究成果，例如利用PSO[7]搜索AGV在車間任意兩個不同節(jié)點間空載行駛時的最佳節(jié)能路徑，記錄對應(yīng)的Pareto解集。由于各運輸任務(wù)初始節(jié)點、目標(biāo)節(jié)點和工件質(zhì)量等信息已知，針對每項運輸任務(wù)對應(yīng)的負(fù)載運輸階段，同法搜索AGV最優(yōu)節(jié)能運輸路徑，并記錄對應(yīng)的Pareto解集。這些記錄信息作為第2階段利用非支配排序遺傳算法(non-dominated sorting genetic algorithm-II，NSGA-II)解決運輸任務(wù)優(yōu)化排序以及局部運輸階段最優(yōu)運輸路徑的組合優(yōu)化問題，進(jìn)而獲得完成全部運輸任務(wù)的最優(yōu)運輸路徑的基礎(chǔ)信息。在第2階段，研究重點關(guān)注反映問題可行解的種群個體編碼方案和遺傳算子設(shè)計。

(1)個體編碼

個體編碼應(yīng)能夠反映影響優(yōu)化目標(biāo)的決策變量xkq和yijl的信息，設(shè)計了一種分段編碼的個體編碼方案，其示例如圖2所示。

個體染色體長度統(tǒng)一為3m，采用實數(shù)編碼，全部運輸任務(wù)序號隨機分布在前m個基因上；中間m個基因從左到右，按運輸任務(wù)序號由小到大的順序依次記錄與各運輸任務(wù)對應(yīng)的負(fù)載運輸階段選擇的最優(yōu)運輸路徑；最后m個基因從左向右，按空載運輸階段順序依次記錄各空載運輸階段選擇的最佳行駛路徑。

(2)遺傳算子

選擇算子沿用標(biāo)準(zhǔn)NSGA-II中的錦標(biāo)賽選擇策略[8]，構(gòu)建容量是種群規(guī)模一半的配對池，后續(xù)交叉、變異操作以從配對池中隨機選擇的個體為父代。

設(shè)計了兩種交叉算子，示例如圖3所示。若兩父代個體前m個基因相同，則對它們的后2m個基因進(jìn)行雙點交叉操作；否則先雙點交叉前m個基因，并進(jìn)行合法性校驗：依次比對交叉后的子代和父代個體的前m個基因，然后將父代剩余基因按順序依次替換子代多余基因。進(jìn)而，子代個體根據(jù)交叉后的前m個基因，為各空載運輸階段重新選擇最優(yōu)路徑，更新最后m個基因。

針對變異操作，設(shè)計了3種使用幾率均等的變異算子：①在前m個基因中任選兩個不同的基因位，交換其基因值，進(jìn)而為各空載運輸階段重新選擇最優(yōu)行駛路徑，更新最后m個基因；②保持前m個基因不變，隨機選擇一項運輸任務(wù)，從其對應(yīng)的最優(yōu)運輸路徑Pareto解集中隨機挑選一個不同于當(dāng)前選擇的解，進(jìn)而更新相應(yīng)基因位的值；③保持前m個基因不變，隨機選擇一個空載運輸階段，從其對應(yīng)的最優(yōu)行駛路徑Pareto解集中隨機挑選一個不同于當(dāng)前選擇的解，并更新相應(yīng)基因位的值。

NSGA-II中非支配排序、擁擠度計算等關(guān)鍵算法過程可參考文獻(xiàn)[8]，在此不再贅述。

3 案例研究

結(jié)合某航空制造企業(yè)的一個制造車間[7]進(jìn)行案例研究，該車間運輸網(wǎng)絡(luò)拓?fù)涞貓D如圖4所示。

車間現(xiàn)有表1所示的5項常見運輸任務(wù)。AGV初始?？吭诠?jié)點44，其技術(shù)參數(shù)可參考文獻(xiàn)[7]。兩階段EAPP模型求解方法在Intel core(TM)i7-8700 3.20GHz CPU，24GB RAM，Windows 10的PC用Matlab語言實現(xiàn)，階段1利用PSO[7]搜索AGV執(zhí)行各運輸任務(wù)的最優(yōu)節(jié)能路徑(如表2所示)和在車間任意兩個不同節(jié)點間空載行駛的最優(yōu)節(jié)能路徑；階段2使用NSGA-II時的關(guān)鍵參數(shù)設(shè)置如表3所示。

表2 AGV執(zhí)行各運輸任務(wù)的最優(yōu)節(jié)能路徑

表3 NSGA-II參數(shù)設(shè)置

為驗證應(yīng)用EAPP模型的節(jié)能效果，分兩種情形討論。情形1與車間現(xiàn)行計劃一致，AGV按照任務(wù)序號依次執(zhí)行運輸任務(wù)；情形2下AGV執(zhí)行運輸任務(wù)的順序可優(yōu)化調(diào)整。兩種情形下求解模型得到的Pareto解對應(yīng)的優(yōu)化目標(biāo)值如圖5所示。

為對比能耗優(yōu)化效果，在兩種情形下分別隨機選擇一個對應(yīng)最低運輸能耗的Pareto解進(jìn)行分析，如圖6所示。情形2與情形1相比，Etotal降低了15.2%，D縮短了14.5%。然而，兩種情形下負(fù)載運輸階段的總能耗和總節(jié)點間距離相等，說明負(fù)載運輸階段優(yōu)化效果相同。情形2下總體優(yōu)化效果之所以更優(yōu)是因為運輸任務(wù)執(zhí)行順序的改變使空載運輸階段總能耗和總節(jié)點間距離得以優(yōu)化。

此外，進(jìn)一步驗證所提EAPP模型求解方法的有效性。階段1所用PSO的有效性已在文獻(xiàn)[7]中進(jìn)行了論證，故本文針對階段2使用的NSGA-II，將其與求解多目標(biāo)優(yōu)化問題常用的多目標(biāo)粒子群優(yōu)化算法(multi-objective PSO，MOPSO)[9]進(jìn)行對比。

借鑒目前利用PSO解決車間調(diào)度以及最短路徑搜索問題常用的粒子編碼方案[10]，將每個粒子表示為(X1,X2,…,X3m,V1,V2,…,V3m)的形式：前3m個元素標(biāo)記粒子位置信息，取值分別為[0, 1]內(nèi)的隨機數(shù)；后3m個元素記錄粒子在搜索空間各維的速度信息，其取值范圍為[-1, 1]。由于問題可行解是通過粒子空間位置表達(dá)的，對任一粒子，其位置信息的前m個元素用于確定運輸任務(wù)執(zhí)行順序：首先將前m個元素的值按照從大到小排列，然后將各元素的值替換為其粒子編碼的位置序號，從而得到運輸任務(wù)執(zhí)行順序。粒子位置信息的中間m個元素從左到右，依次與運輸任務(wù)編號1～m相對應(yīng)，視為確定AGV在各負(fù)載運輸階段選擇哪條優(yōu)化路徑的概率。類似地，粒子位置信息中的最后m個元素從左到右，依次與運輸作業(yè)任務(wù)執(zhí)行順序決定的各空載運輸階段相對應(yīng)，視為確定AGV在各空載運輸階段選擇哪條優(yōu)化路徑的概率。在各負(fù)載/空載運輸階段，可能存在多條最優(yōu)運輸路徑，這些路徑被選中的概率相等，具體選擇哪條根據(jù)輪盤賭法確定。

針對本案例，MOPSO關(guān)鍵參數(shù)設(shè)置如表4所示。

表4 MOPSO參數(shù)設(shè)置

基于階段1提供的基礎(chǔ)信息，將NSGA-II和MOPSO分別運行5次，發(fā)現(xiàn)兩算法得到的Pareto前沿相同，如圖5b所示。解碼對應(yīng)最低運輸能耗的Pareto解，發(fā)現(xiàn)運輸任務(wù)的最優(yōu)執(zhí)行順序為“2→5→1→3→4”和“1→5→2→3→4”。然而，NSGA-II的平均運行時間(18.816 s)小于MOPSO的(40.675 s)。因此，階段2所用NSGA-II在同時解決運輸任務(wù)優(yōu)化排序和各空載/負(fù)載運輸階段最優(yōu)運輸路徑選擇方面是有效的。

4 結(jié)語

針對車間節(jié)能生產(chǎn)需求，以單臺單負(fù)載AGV為研究對象，建立了面向多運輸任務(wù)，以運輸距離和能耗為優(yōu)化目標(biāo)的EAPP模型，并提出了一種兩階段模型求解方法。案例研究驗證了模型的有效性，當(dāng)AGV執(zhí)行多項運輸任務(wù)時，合理安排運輸任務(wù)執(zhí)行順序和規(guī)劃運輸路徑能夠提升AGV使用能效。后續(xù)將對多負(fù)載AGV進(jìn)行節(jié)能路徑規(guī)劃研究。