面向多搬運任務的柔性制造車間多載具AGV節能路徑規劃

摘要：自動導引搬運車（automated guided vehicle，AGV）能夠靈活、準確、高效地進行物料搬運，被廣泛應用于柔性制造車間。多載具AGV能同時搬運多個工件，具有較強的搬運靈活性，其路徑規劃問題的復雜性和多約束性更強，求解難度更大。針對柔性制造車間多載具AGV節能路徑規劃問題，首先建立了以能耗和搬運距離為優化目標的AGV節能路徑規劃模型；然后，提出了一種改進Dijkstra算法和非支配排序遺傳算法（non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ）集成的多載具AGV節能路徑規劃方法；最后通過案例驗證了模型的節能效果和求解方法的有效性。

關鍵詞：多載具AGV；節能路徑規劃；改進Dijkstra算法；非支配排序遺傳算法

中圖分類號：TP23文獻標志碼：A

文章編號：1001-3695（2023）01-009-0057-06

doi：10.19734/j.issn.1001-3695.2022.06.0296

Energy-efficient path planning for single multi-load AGV executing

multiple transport tasks in flexible manufacturing workshop

Wu Lihui1，2，Hu Wenbo1，Zhou Xiu1，Zhang Zhongwei1

（1.School of Mechanical amp; Electrical Engineering，Henan University of Technology，Zhengzhou 450001，China；2.School of Mechanical Engineering，Shanghai Institute of Technology，Shanghai 201418，China）

Abstract：AGV can execute material handling flexibly，accurately，and efficiently，and have been widely applied in flexible manufacturing workshops.A multi-load AGV can transport multiple workpieces at the same time and owns strong handling flexibility.When performing multiple transport tasks，the solution to the path planning problem is more difficult due to the increa-sing complexity and constraints.Aiming at the energy-efficient path planning problem for a multi-load AGV in a flexible manufacturing workshop，this paper established an AGV energy-efficient path planning model with energy consumption and transport distance as the optimization objectives.Furthermore，this paper proposed a model solution method integrating the modified Dijkstra algorithm and the non-dominated sorting genetic algorithm-Ⅱ（NSGA-Ⅱ）.Finally，the case study verifies the energy-saving effect of the model and the validity of the solution method.

Key words：multi-load AGV；energy-efficient path planning；modified Dijkstra algorithm；non-dominated sorting genetic algorithm-Ⅱ

0引言

柔性制造是智能制造的重要內容之一，是制造業未來發展的驅動力。在柔性制造車間中，自動導引搬運車（AGV）憑借高度自動化、靈活改變搬運路徑、安全性好等優勢得到了廣泛的應用，是實現車間智能物流的關鍵設備之一［1］。在柔性制造車間應用的AGV中，多載具AGV能夠同時搬運多個工件，有助于縮小制造車間AGV數量規模，提高AGV利用率［2］。隨著我國“碳達峰、碳中和”戰略的提出，如何響應國家節能減排號召、減少制造生產過程能耗，已成為制造行業普遍關注的問題［3］。相應地，對柔性制造車間內的AGV進行節能路徑規劃，已被證明是降低車間生產過程能耗的有效方法之一［4］，逐漸獲得制造企業與學術界的關注。

近年來，對于AGV路徑規劃的研究主要采用圖論法［5］、啟發式規則［6，7］、元啟發式算法［8，9］等。其中戴敏等人［10］以單載具AGV能耗和搬運時間為優化目標建立了節能路徑規劃模型，提出了一種改進分布估計算法對模型進行求解。張中偉等人［11］研究柔性制造車間單載具AGV的能耗優化問題，建立以搬運距離和能耗為目標的節能優化模型，提出了粒子群優化算法進行求解。Lian等人［12］通過研究多輛單載AGV的完成效率和能耗，建立了兩輪差動驅動移動機器人的運動模型，提出了一種改進的啟發式路徑規劃算法進行求解。Yu等人［13］為了節約AGV運輸目標時的時間和減少能量損失，采用離散布谷鳥算法求解多目標點的路徑規劃問題。然而，上述節能路徑規劃研究對象主要為單載具AGV，缺乏多載具AGV物料搬運場景下的路徑規劃研究。單載具AGV多任務路徑規劃問題的本質為搬運任務排序優化問題，亦為NP-hard［14］。與之相比較，多載具AGV可同時搬運多個工件，AGV裝/卸與搬運工件順序明顯具有更強的柔性，導致多載具AGV路徑規劃問題的解空間更大更復雜，求解難度更大。

在多載具AGV路徑規劃研究方面，Tao等人［15］建立了以最短搬運時間為目標函數的數學模型，提出了一種改進的粒子群優化算法來獲得最優路徑。Shan等人［16］建立了總行駛路徑最短的數學模型，提出了時間窗改進算法和路徑沖突協方差相結合的路徑規劃方法。李軍軍等人［17］分析了多載具AGV路段沖突、節點沖突問題，以搬運時間為目標建立了多載具AGV路徑規劃模型，并提出了一種誘導蟻群粒子群算法用于模型求解。Du等人［18］利用混合遺傳粒子群優化算法建立了路徑規劃問題的數學模型來求解該問題，并提出了基于時間優先級的粒子迭代機制，使進化更具方向性，加快了算法的收斂速度。然而，上述多載具AGV路徑規劃研究的優化目標主要集中于搬運距離和時間兩方面，未充分考慮柔性制造車間的節能降耗需求。

因此，本文以柔性制造車間中的單臺多載具AGV為研究對象，針對其在多搬運任務場景下的路徑規劃問題，以搬運能耗和距離為優化目標，建立多載具AGV節能路徑規劃模型（energy-efficient path planning for multi-load AGVs，EPPMA），進而提出改進Dijkstra算法和NSGA-Ⅱ集成（integration of modified Dijkstra algorithm and NSGA-II，IMDAN）的路徑規劃方法。

1問題描述與建模

1.1問題描述與建模假設

柔性制造車間加工工件具有多品種、小批量的特點，導致車間中物料搬運過程具有以下特點：a）物料搬運任務分散；b）各搬運任務的目標設備各不相同；c）部分搬運任務之間裝、卸位置具有較高關聯性［19］。因此，物料搬運過程中可充分利用上述特點，對各物料搬運任務的裝、卸載順序進行優化調整，以降低多載AGV在搬運過程中的能耗，并縮短AGV的行駛路徑。

為對柔性制造車間中多載具AGV節能路徑規劃問題進行建模，采用拓撲圖法［5］對車間的物料搬運環境進行描述。將柔性制造車間中工件裝/卸載位置、物料搬運路徑交叉位置、轉向位置抽象為節點，各節點間的連接導軌抽象為帶權重的邊，則柔性制造車間的物料搬運環境可抽象為無向圖G=（V，E），V={1，2，…，q}表示節點集合，E={（i，j）：i，j∈V，i≠j}表示邊集合，且任意兩相鄰節點i、j的邊（i，j）的權重可用其路徑距離dij表示。以某柔性制造車間為例，建立其拓撲圖如圖1所示。

根據柔性制造車間環境及多載具AGV實際運行情況，多載具AGV節能路徑規劃建模過程基于以下假設：a）車間中所有軌道均為單行雙向；b）AGV進行加速運動時加速度恒定，進行勻速直行和勻速轉彎運動時速度恒定且不相同，在減速過程中通過自身機械制動減速，不考慮減速時的能耗；c）AGV裝/卸載時間為固定值，不因工件種類存在差異；d）初始時刻，搬運任務同時下達且AGV空載可用。

1.2模型表示

對于EPPMA問題，定義多載具AGV最大荷載工件量為Lmax，需要搬運的任務數量為n，第k項搬運任務的裝貨點和卸貨點編號分別定義為Pk和Ck，k=1，2，…，n，Pk，Ck∈V，且Pk≠Ck；定義多載具AGV最大負載時，AGV與工件的總質量記為mmax；定義AGV的初始位置為s（s∈V）；定義AGV完成n個搬運任務情況下，其遍歷的搬運路徑有序節點組合為S。考慮到初始時刻AGV處于初始位置s，且AGV完成單次搬運任務需經過裝貨和卸貨兩個階段，則AGV完成n個搬運任務的過程可分為2n個搬運階段（即n個裝貨階段和n個卸貨階段），且單個搬運階段的搬運路徑起始/目標節點為裝貨點或卸貨點（首次搬運起始點為s）。定義第l個搬運階段l=1，…，2n，AGV遍歷的搬運路徑有序節點集合為Sl，Sl∈S，起始和目標節點分別為（vsl，vel），vsl，vel∈V，第l個搬運階段AGV的載量為Ll，AGV與工件的質量為ml。

1）搬運距離模型定義整數決策變量yijl為第l個搬運階段AGV經過邊（i，j）的狀態信息：

yijl=1AGV按路徑Sl行駛時經過邊（i，j）

0其他

則AGV完成n個搬運任務的總搬運距離D表示為

D=∑2nl=1∑qi=1∑qj=1dijyijl（1）

2）能耗模型能耗是功率在時間域上的積分，進行能耗分析需要確定時間邊界。設定AGV到達第k個搬運任務裝貨、卸貨點的時間分別為TPk和TCk，TCk＞TPk≥0，則AGV完成n個搬運任務的總完成時間Ttotal可表示為

Ttotal=max{TCk}k=1，2，…，n（2）

進而，以Ttotal為時間邊界分析搬運能耗，根據多載具AGV的物料搬運過程的運動特性，從其不同運動狀態角度進行能耗分析，將搬運過程總能耗分解為加速運動能耗Eam（單位為J）、勻速直行運動能耗Elm、轉彎路段能耗Etm、待機運動能耗和減速能耗。Pso為AGV待機所需功率。根據建模假設b），AGV減速時驅動電機的功率會迅速降低至0，因此減速能耗為0。進而，AGV搬運過程總能耗Etotal表示為

Etotal=PsoTtotal+Eam+Etm+Elm（3）

其中：加速運動能耗E am如式（4）所示。

Eam=∑2nl=1Elam=∑2nl=1{∑rlu=1{Flam×［vu0tuam+12aam（tuam）2］}η}（4）

其中：Elam表示Flam第l個搬運階段加速運動時的驅動力，單位N；根據物理運動學分析可以得出在第l個搬運階段存在的加速運動階段總數rl；vu0表示第u個（1≤u≤rl）加速運動階段的初始速度，單位為m/s；aam表示AGV加速運動的加速度，單位m/s2；tuam表示第u個加速階段時間，單位s；η表示行走驅動電機功率因數。轉彎路段能耗Etm如式（5）所示。

Etm=∑2nl=1Eltm=

∑2nl=1nld×ml×g×f4×（R1+R2+R3+R4）×π2η（5）

其中：Eltm表示第l個搬運階段的轉彎能耗；nld表示相應的轉向節點個數；R1、R2、R3、R4表示常見的四輪AGV四個車輪的轉彎半徑，單位為m；f為AGV與車間地面間的動摩擦系數。

勻速直行運動能耗Elm如式（6）所示。

Elm=∑2nl=1Ellm=∑2nl=1Fllm×Dlη（6）

其中：Ellm表示第l個搬運階段的勻速直行運動能耗；Fllm 表示第l個搬運階段AGV勻速直線行駛的驅動力；Dl表示第l搬運階段AGV勻速直線行駛的距離，單位為m。其中時間邊界和具體的能耗建模信息參考文獻［11］。

3）總體目標模型多載具AGV節能路徑規劃模型的優化目標為

minimize［D］

minimize［Etotal ］（7）

約束條件：

∑i∈Slyijl=1l=1，…，2nj：j∈Sl（8）

∑j∈Slyijl=1l=1，…，2ni：i∈Sl（9）

l=1，…，2n；vel=vsl+1（10）

l=2，…，2n，ifvsl=Ck∨vel=Ck

l*=2，…，l-1，vsl*=Pk∨vel*=Pk（11）

l=2，…，2n，ifvsl=Pk∨vel=Pk，

l*=l+1，…，2n，vsl*=Ck∨vel*=Ck（12）

Ll≤Lmaxl=1，…，2n（13）

ml≤mmaxl=1，…，2n（14）

其中：式（8）（9）表示在第l個搬運階段，任意邊（i，j）只能被訪問一次；式（10）表示當前搬運階段的結束節點為下一個搬運階段的起始節點；式（11）表示當前階段若存在某項任務的卸貨點，則之前某階段必定存在該項任務的裝貨點；式（12）表示當前階段若存在某項任務裝貨點，則之后某個階段必定存在該項任務的卸貨點；式（13）表示任意階段AGV荷載工件的數量不得超出其最大荷載工件量；式（14）表示任意階段AGV滿載重量不超出其負荷能力。

2IMDAN路徑規劃方法

EPPMA模型求解問題本質上是一個多目標優化問題。由于NSGA-Ⅱ方法具有運行速度快、解集收斂性好的特點［20］，Dijkstra算法具有快速獲得無向圖中兩點間最短距離的優點［21］，所以本文設計集成Dijkstra和NSGA-Ⅱ算法的IMDAN路徑規劃方法求解EPPMA模型，其方法框架與具體流程如圖2所示。

IMDAN模型求解包括兩個階段：

a）兩搬運任務節點間搬運距離最優路徑獲取。根據n個搬運任務的裝貨點和卸貨點、AGV初始位置點等已知信息分析獲得2n+1個任務節點集合；從集合中任意選取兩任務節點，基于柔性制造車間無向圖網絡，采用改進Dijkstra算法［22］獲得該兩任務節點間搬運距離最短路徑方案集合（若最短路徑有多條，則同時將其定為最優路徑方案）；遍歷2n+1個任務節點集合中的所有可能兩節點組合，以獲得各節點間最優路徑方案，形成節點間AGV最優搬運路徑表。

b）物料搬運取、卸貨任務排序優化。基于任務節點間AGV最優搬運路徑表設計NSGA-Ⅱ算法，優化AGV搬運n個搬運任務過程中的裝貨與卸貨順序，從而獲得實現能耗和搬運距離同時優化的AGV路徑規劃方案。模型求解的重心在于第2階段，下面重點介紹階段2所用NSGA-Ⅱ算法的設計。

2.1NSGA-Ⅱ算法設計

2.1.1編碼

基于階段1提供的輸入信息，IMDAN節能路徑方案的確定取決于yijl、vsl、和vel三個決策變量的值，因此個體的編碼需要反映它們的信息。針對n個搬運任務的場景，多載具AGV需要取/卸貨的總次數為2n，其路徑規劃的核心是對2n個裝/卸貨節點進行排序和2n個搬運階段搬運能耗最少的最短搬運路徑的選擇。因此采用兩段實數編碼的方式，第一段染色體的基因長度為2n，將n個搬運任務的裝貨點和卸貨點序號隨機排列在對應的2n個基因位上，第二段染色體的基因長度同樣為2n，第二段染色體2n個基因從左到右依次表示各搬運階段選擇的最優搬運路徑。個體編碼示例如圖3所示。

然而，在初始化種群個體時只進行前述操作可能產生非法個體，具體體現在：對于第一段染色體，某任務的裝貨點基因位置在相應卸貨點基因之前，或AGV在某段搬運路徑的載量超出了AGV容量限制；對于第二段染色體，基因位上的基因值大于對應的最優搬運路徑的總個數。為此，在種群初始化個體編碼時，針對非法個體的染色體進行基因調整設計，具體過程如圖4所示。

2.1.2解碼

個體解碼主要是根據染色體基因編碼體現的各任務裝貨點和卸貨點排列順序信息，獲得該染色體對應搬運方案的搬運距離D和總能耗Etotal目標值，進而評判不同種群個體間的優劣關系。具體解碼步驟如下：

a）將AGV初始位置節點作為起始節點，第一段染色體首基因位作為目標節點，同時根據第二段染色體的首基因位查詢AGV起始節點和目標節點間AGV最優搬運路徑表，獲得AGV選擇的搬運路徑及對應的搬運距離；通過分析AGV搬運過程中的轉彎次數，計算其加速、勻速和轉彎的能耗，并根據式（3）求得能耗值。

b）從左到右依次將第一段染色體兩相鄰基因位分別作為起始節點和目標節點，根據第二段染色體相對應的基因位信息，查詢節點間AGV最優搬運路徑表，獲得AGV的具體搬運路徑和搬運距離。當起始節點為某項任務的裝貨點時，則在后續搬運階段，AGV的總重量需加上此項任務的工件重量，若目標節點為卸貨點，則AGV的總重量減去此工件的重量。此外，通過式（3）求得能耗值。

c）通過累加方式得出多載具AGV執行該任務序列的搬運總距離D和搬運總能耗Etotal，重復步驟b），直至兩段染色體末基因位為止。

d）重復步驟a）～c），直至所有染色體都解碼完成。

2.1.3交叉操作

交叉操作是為了增加種群個體的多樣性。在交叉操作時，設計了兩種交叉算子，以執行三個搬運任務的單臺多載具AGV為例，各搬運任務的裝、卸貨節點分別是（6，9）、（18，16）、（24，21），則此時交叉算子操作示例如圖5所示。

若兩父代個體的第一段染色體基因不同，對父代個體第一段染色體基因進行交叉操作，具體過程為：從父代個體中隨機選取兩個不同基因位x1和x2，1≤x1，x2≤2n；將父代個體B上［x1，x2］位置的基因復制到父代個體A的首端，將父代個體A上［x1，x2］位置的基因復制到父代個體B的首端；從左到右依次訪問A和B兩父代個體基因，將重復出現的基因刪除，從而形成新的子代個體A1和B1。若兩父代個體的第一段染色體基因位相同，對父代染色體第二段染色體基因進行雙點交叉操作。對于情形2，交叉操作之后需要對染色體上的基因進行合法性調整，具體過程如圖4所示。

針對變異操作，采用對兩段染色體進行逆轉操作的方法［23］，在第一段和第二段染色體中分別任選兩個不同的基因位，然后將兩基因位之間的基因值以逆向排序插入到原位置中。變異操作之后需要對染色體上基因進行合法性調整，具體過程如圖4所示。染色體選擇操作采用二元錦標賽選擇策略［24］；快速非支配排序和擁擠度計算等關鍵過程可參考文獻［24］，此處不再贅述。

3案例研究

為驗證本文提出的EPPMA模型與IMDAN方法的有效性，采用某企業柔性制造車間數據進行案例研究，該車間拓撲圖如圖6所示。車間路口轉彎半徑均為0.85 m。該車間采用一臺具有3個裝載工位的AGV進行工件搬運，該AGV采用四輪驅動方式，各車輪采用額定功率為60 W的伺服電機作為驅動源。車間現有六項常見搬運任務，AGV初始位置在節點8，各搬運任務的裝/卸貨點及對應工件的質量信息如表1所示，其技術參數可參考文獻［11］。IMDAN方法在Intel CoreTM i5-7300HQ CPU，8 GB RAM，Windows 10 的PC上采用MATLAB編程實現，該方法關鍵參數設置為：種群規模為50，最大迭代次數為500，交叉概率為0.9，變異概率為0.1。

3.1模型節能效果有效性驗證

為驗證EPPMA模型節能效果，分三種情形進行討論：情形1中AGV執行搬運任務的裝卸點順序可優化調整，綜合考慮D和Etotal，采用IMDAN方法求解；情形2僅關注目標D，采用與IMDAN方法相同步驟進行求解，僅在染色體解碼過程中采用單目標進行；情形3中AGV滿載后再執行卸貨任務，綜合考慮D和Etotal，采用IMDAN方法求解。

三種情形下分別運行算法10次，將情形2得到的最優解與情形1得到的Pareto解集中對應的最短搬運距離的解進行對比，實驗結果如表2所示。情形1和3兩種情形得到的Pareto解集如圖7所示。對比兩種情形下的能耗優化效果，選擇對應最低搬運能耗的Pareto解進行分析，結果如表3所示。

由表2可知，情形1和2雖然都能獲得最短搬運距離，但在能耗目標上，情形1比情形2降低了2.4%。其主要原因為情形1綜合權衡了搬運距離與能耗兩個優化目標，當多載具AGV執行多項搬運任務時，選擇裝貨點和卸貨點的執行順序時同時兼顧搬運距離和能耗兩個目標，能夠在搬運距離最優的同時，進一步降低AGV搬運能耗。由表3可知，情形1與3相比，能耗降低了21%，距離縮短了16.1%。其主要原因為AGV執行搬運任務裝卸節點順序的改變使得搬運階段總能耗和總距離都得到優化。因此在柔性制造車間中多載具AGV搬運過程中考慮能耗作用明顯，本文EPPMA模型是有意義、有效的。

3.2IMDAN方法的有效性驗證

IMDAN方法的有效性驗證主要通過以下兩個對比實驗進行。

a）實驗1。將IMDAN方法與面向多目標的單載具AGV路徑規劃方法，即多目標粒子群算法（multi-objective particle swarm optimization，MOPSO）［11］和基于分解的多目標進化算法（multi-objective evolutionary algorithm based on decomposition，MOEA/D）［25］進行對比。MOPSO方法已被證明為實現單載具AGV路徑規劃過程搬運總能耗與距離目標優化的有效方法［11］。MOEA/D方法被廣泛應用于多目標優化問題，并能有效對面向多目標的單載具AGV路徑規劃問題進行求解［25］。

b）實驗2。將IMDAN方法與最新的多載具AGV路徑規劃方法，即改進自適應遺傳算法（improved adaptive genetic algorithm，IAGA）［26］和混合遺傳粒子群優化算法（genetic particle swarm optimization algorithm，GA-PSO）［18］進行比較。IAGA與GA-PSO方法已被驗證能夠用于多載具AGV路徑規劃問題求解，并能有效減小AGV總距離或總搬運時間等目標［18，26］。

1）實驗1采用MOPSO和MOEA/D方法求解本企業案例，兩種方法均在同一PC上使用MATLAB語言編程實現，并采用與IMDAN相同的編碼方式。MOPSO算法參數設置為：種群規模50、最大迭代次數500、認知加速度系數2、社會加速度系數2、慣性權重下界0、慣性權重上界1。MOEA/D算法參數設置為：種群規模50、權重向量個數100、最大迭代次數500、鄰域個數15。兩種算法分別運行10次，得到的Pareto最優解與IMDAN方法的最優解進行對比，結果如圖8所示。圖8表明：IMDAN方法搜索得到的Pareto前沿相較于MOEA/D和MOPSO方法的Pareto前沿更靠左下位置，即IMDAN方法得到的最優解質量優于MOEA/D和MOPSO方法。

在此基礎上，對IMDAN與MOPSO、MOEA/D方法的平均計算時間進行比較（表4）。結果表明，IMDAN、MOPSO、MOEA/D方法的平均計算時間分別為16.3 s、47.5 s、112.5 s，IMDAN方法的平均計算時間明顯低于MOPSO和MOEA/D方法。

因此，針對面向搬運距離與能耗目標的柔性制造車間多任務物料搬運問題，本文采用的IMDAN方法優于基于MOPSO和MOEA/D的單載具AGV路徑規劃方法。

2）實驗2采用IAGA和GA-PSO求解本企業案例，同樣地，兩種方法均在同一PC上使用MATLAB語言編程實現，且關鍵參數設置與IMDAN方法相同。兩種方法分別運行20次，在求解獲得最短距離的基礎上，選擇能耗最優方案，并將其與基于IMDAN得到的Pareto解集中搬運距離最短的最優解進行對比，如表5所示。結果表明，在搬運距離方面，三種方法均能求得最短搬運距離198 m；在能耗方面，IMDAN相較于IAGA、GA-PSO的總能耗值分別降低了4.2%、1.9%。因此，IMDAN在搬運距離與能耗多目標優化方面，優于IAGA、GA-PSO。

3.3結論分析

從以上模型節能效果實驗與IMDAN方法有效性實驗分析，可獲得以下結論：

a）本文EPPMA模型是有意義、有效的，即在多載具AGV路徑規劃過程中縮短搬運距離的同時，充分考慮能耗目標因素，有利于降低AGV搬運總能耗。在半導體芯片制造、芯片封裝、機械制造等行業，大規模柔性制造車間廣泛存在，其自動化物料搬運過程大量采用多載具AGV，單臺AGV的節能效果在整個車間范圍內累積，將為車間物料搬運環節帶來可觀的節能效果。

b）在搬運距離與能耗目標方面，IMDAN方法優于現有基于MOPSO和MOEA/D的單載具AGV路徑規劃多目標方法，且IMDAN方法優于現有基于IAGA、GA-PSO的多載具AGV路徑規劃方法。因此，本文設計的IMDAN方法是有效的。

對IMDAN能實現搬運距離與總能耗多目標優化的原因進行分析：a）本文方法從多搬運任務分解的角度，將多載具AGV的搬運過程以裝、卸載為節點分解為多個階段，采用改進Dijkstra算法獲得任意兩裝卸節點間的最短搬運距離路徑集合，實現了兩節點間的搬運距離最短；b）基于NSGA-Ⅱ算法較強的全局優化能力，設計該方法對多載具AGV的裝卸任務節點進行優化排序，在實現總搬運距離最短的基礎上，降低了多載具AGV搬運的總能耗。

4結束語

針對柔性制造車間多載具AGV節能路徑規劃問題，以搬運距離和能耗為目標建立了面向多項搬運任務的多載具AGV節能路徑規劃模型，提出了一種基于改進Dijkstra算法和非支配排序遺傳算法集成的多載具AGV多目標路徑規劃方法。基于某柔性制造車間數據進行案例分析表明：a）采用IMDAN方法求解EPPMA模型，對三種不同情形進行比較，在綜合考慮搬運距離和能耗的情形下且能夠保證搬運距離最短的基礎上，能耗相較于其他情形分別降低了2.4%和21%，驗證了模型節能效果有效性；b）IMDAN與基于MOPSO、MOEA/D的單載具AGV路徑規劃方法及基于IAGA、GA-PSO的多載具AGV路徑規劃方法進行比較，結果表明IMDAN在搬運距離和總能耗方面具有更優的綜合性能，驗證了該方法的有效性。該方法的節能效果對于柔性制造車間物料搬運過程具有重要意義，如半導體芯片制造、芯片封裝、機械制造等行業的大規模柔性制造車間中的多載具AGV使用規模較大、長加工工序及大規模在制品等特性，導致多載具AGV高頻率使用，從規模效應和累積效應考慮，本文IMDAN具有很大的節能潛力。另外考慮沖突的多臺多負載AGV的節能路徑規劃問題是進一步研究的方向。

參考文獻：

［1］孫毛毛，匡兵.基于時間窗的AGV動態避碰路徑規劃方法［J］.計算機應用研究，2022，39（1）：54-58.（Sun Maomao，Kuang Bing.Path planning method for AGV dynamic collision avoidance based on time window［J］.Application Research of Computers，2022，39（1）：54-58.）

［2］武星，翟晶晶，樓佩煌，等.考慮任務行程時間的多載量自動導引車系統防死鎖任務調度［J］.中國機械工程，2021，32（23）：2840-2849.（Wu Xing，Zhai Jingjing，Lou Peihuang，et al.Deadlock-free task scheduling with task traveling time for a multi-load AGV system［J］.China Mechanical Engineering，2021，32（23）：2840-2849.）

［3］包哲人，徐華.面向能耗機制的多目標柔性作業車間調度［J］.計算機應用研究，2017，34（12）：3617-3622.（Bao Zheren，Xu Hua.Multi-objective flexible Job-Shop scheduling based on energy-consumption mechanism［J］.Application Research of Computers，2017，34（12）：3617-3622.）

［4］郭興海，計明軍，劉雙福.融合多目標與能耗控制的無人倉庫內AGV路徑規劃［J］.計算機集成制造系統，2020，26（5）：1268-1276.（Guo Xinghai，Ji Mingjun，Liu Shuangfu.Multi-objective and energy consumption control of AGV routing planning in unmanned warehouse［J］.Computer Integrated Manufacturing Systems，2020，26（5）：1268-1276.）

［5］牛雅倩，余芳，劉靜雯，等.基于動態平衡策略的自動化碼頭多AGV路徑優化算法研究［J］.計算機應用研究，2022，39（2）：385-390.（Niu Yaqian，Yu Fang，Liu Jingwen，et al.Research on optimal algorithm of multi-AGV paths for automated terminals based on dynamic balance strategy［J］.Application Research of Computers，2022，39（2）：385-390.）

［6］Ho Y C，Liu Haocheng，Yih Y.A multiple-attribute method for concurrently solving the pickup-dispatching problem and the load-selection problem of multiple-load AGVs［J］.Journal of Manufacturing Systems，2012，31（3）：288-300.

［7］Ho Y C，Liu Haocheng.The performance of load-selection rules and pickup-dispatching rules for multiple-load AGVs［J］.Journal of Manufacturing Systems，2009，28（1）：1-10.

［8］牛秦玉，李博.基于模擬退火遺傳算法的全向AGV路徑規劃［J/OL］.計算機集成制造系統.（2022-05-17）［2022-06-01］.http：//www.cims-journal.cn/CN/abstract/abstract7484.shtml.（Niu Qinyu，Li Bo.Omnidirectional AGV path planning based on annealing genetic algorithm［J/OL］.Computer Integrated Manufacturing Systems.（2022-05-17）［2022-06-01］.http：//www.cims-journal.cn/CN/abstract/ abstract7484.shtml.）

［9］張碩，錢曉明，樓佩煌，等.基于改進粒子群算法的大規模自動導引車系統路徑規劃優化［J］.計算機集成制造系統，2020，26（9）：2484-2496.（Zhang Shuo，Qian Xiaoming，Lou Peihuang，et al.Path planning optimization of large scale AGV system based on improved particle swarm optimization algorithm［J］.Computer Integrated Manufacturing Systems，2020，26（9）：2484-2496.）

［10］戴敏，張玉偉，曾勵.綠色作業車間機器與AGV的集成調度研究［J］.南京航空航天大學學報，2020，52（3）：468-477.（Dai Min，Zhang Yuwei，Zeng Li.Integrated scheduling of machines and AGVs in green Job-Shop［J］.Journal of Nanjing University of Aeronautics amp; Astronautics，2020，52（3）：468-477.）

［11］張中偉，李俊蘭，吳立輝，等.考慮能耗的制造車間單AGV路徑規劃研究［J］.制造技術與機床，2021（3）：118-122.（Zhang Zhongwei，Li Junlan，Wu Lihui，et al.Single AGV path planning considering energy consumption in the manufacturing workshop［J］.Manufactu-ring Technology amp; Machine Tool，2021（3）：118-122.）

［12］Lian Yindong，Zhang Langwen，Xie Wei，et al.An improved heuristic path planning algorithm for minimizing energy consumption in distri-buted multi-AGV systems［C］//Proc of International Symposium on Autonomous Systems.2020：70-75.

［13］Yu Jianjun，Wang Yang，Ruan Xiaogang，et al.AGV multi-objective path planning method based on improved cuckoo algorithm［C］//Proc of the 4th Advanced Information Technology，Electronic and Automation Control Conference.2019：556-561.

［14］黃海松，任竹鵬，魏建安.改進狼群算法求解旅行商問題［J］.計算機應用研究，2019，36（12）：3644-3646，3656.（Huang Haisong，Ren Zhupeng，Wei Jian’an.Improved wolf group algorithm for solving traveling salesman problem［J］.Application Research of Compu-ters，2019，36（12）：3644-3646，3656.）

［15］Tao Qiuyun，Sang Hongyan，Guo Hengwei，et al.Improved particle swarm optimization algorithm for AGV path planning［J］.IEEE Access，2021，9：33522-33531.

［16］Shan Hongying，Wang Chuang，Zou Cungang，et al.Research on pull-type multi-AGV system dynamic path optimization based on time window［J］.Proceedings of the Institution of Mechanical Engineers Part D：Journal of Automobile Engineering，2021，235（7）：1944-1955.

［17］李軍軍，許波桅，楊勇生，等.多自動導引車路徑規劃的誘導蟻群粒子群算法［J］.計算機集成制造系統，2017，23（12）：2758-2767.（Li Junjun，Xu Bowei，Yang Yongsheng，et al.Guided ant co-lony particle swarm optimization algorithm for path planning of AGVs［J］.Computer Integrated Manufacturing Systems，2017，23（12）：2758-2767.）

［18］Du Lizhen，Ke Shanfu，Wang Zhen，et al.Research on multi-load AGV path planning of weaving workshop based on time priority［J］.Mathematical Biosciences and Engineering，2019，16（4）：2277-2292.

［19］王真，王晨曦，王宇豪，等.車間多載自動導引車綠色物流調度［J］.重慶大學學報，2020，43（1）：44-52.（Wang Zhen，Wang Chenxi，Wang Yuhao，et al.On multi-load AGV green logistics sche-duling in knitting workshop［J］.Journal of Chongqing University，2020，43（1）：44-52.）

［20］Deb K，Pratap A，Agarwal S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-Ⅱ［J］.IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

［21］孫寧，吳偉豪，趙風財，等.基于增強型Dijkstra算法的無信號燈交叉路口智能車輛調度研究［J］.計算機應用研究，2022，39（1）：188-193.（Sun Ning，Wu Weihao，Zhao Fengcai，et al.Vehicle scheduling at unsignalized intersections based on enhanced Dijkstra algorithm［J］.Application Research of Computers，2022，39（1）：188-193.）

［22］Zhang Zhongwei，Wu Lihui，Zhang Wenqiang，et al.Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop［J］.Computers amp; Industrial Engineering，2021，158：107397.

［23］陳輔斌，李忠學，楊喜娟.基于改進NSGA2算法的多目標柔性作業車間調度［J］.工業工程，2018，21（2）：55-61.（Chen Fubing，Li Zhongxue，Yang Xijuan.Multi-objective flexible Job-Shop scheduling based on improved NSGA2 algorithm［J］.Industrial Engineering Journal，2018，21（2）：55-61.）

［24］顏陸紅，郭文普，徐東輝，等.基于NSGA-Ⅱ算法的機動通信系統站址規劃方法［J］.計算機應用研究，2022，39（1）：226-230，235.（Yan Luhong，Guo Wenpu，Xu Donghui，et al.Base station location planning method of mobile communication system based on NSGA-Ⅱ［J］.Application Research of Computers，2022，39（1）：226-230，235.）

［25］Zhang Qingfu，Li Hui.MOEA/D：a multiobjective evolutionary algorithm based on decomposition［J］.IEEE Trans on Evolutionary Computation，2007，11（6）：712-731.

［26］劉暢，張承瑞，孫玉璽.改進自適應遺傳算法在多載AGV調度的應用研究［J］.小型微型計算機系統，2021，42（11）：2241-2245.（Liu Chang，Zhang Chengrui，Sun Yuxi.Research on application of improved adaptive genetic algorithm in multi-load AGV scheduling［J］.Journal of Chinese Computer Systems，2021，42（11）：2241-2245.）

收稿日期：2022-06-07；修回日期：2022-08-05基金項目：國家自然科學基金資助項目（U1704156）；河南省科技攻關計劃項目（212102210357）

作者簡介：吳立輝（1981-），男，湖南邵陽人，教授，博導，博士，主要研究方向為復雜制造系統調度；胡文博（1996-），男，河南周口人，碩士研究生，主要研究方向為柔性制造車間AGV調度；周秀（1999-），女，湖南懷化人，碩士研究生，主要研究方向為柔性制造車間AGV調度；張中偉（1987-），男（通信作者），河南正陽人，副教授，碩導，博士，主要研究方向為可持續制造、智能制造（zzw_man@haut.edu.cn）.