帶時間窗約束的AGV集配貨綠色路徑規劃問題研究＊

鄭曉軍 高 峰 高 佳 郭星澤

（大連交通大學機械工程學院工業工程系，遼寧 大連 116028）

作為柔性制造車間內物料運輸系統的重要載具之一，AGV通常要在規定的服務時間窗內對車間不同工序的工位執行集配貨的物流運輸任務，因此AGV的工作效率直接影響車間的整體運營效率。隨著國務院《關于加快建立健全綠色低碳循環發展經濟體系的指導意見》的發布，節能減排已成為我國制造業現階段的主要發展目標。而如何對AGV行駛路徑進行合理規劃以降低其運輸能耗是亟待解決的首要問題。

因此，本文以柔性制造車間為研究背景，在集配貨綠色車輛路徑規劃問題（the green vehicle routing problem with pick-up and delivery，GVRPPD）的基礎上，綜合考慮車間的整體運營效率以及節能減排的發展目標，將GVRPPDTW（GVRPPD with time windows）作為本研究的重點。

目前針對集配貨車輛路徑規劃問題的研究大都以配送費用最小及配送滿意度最大[1?2]作為組合優化目標：Zou W Q等[3]以最大化配送滿意度與最小化配送成本作為優化目標建立AGV路徑規劃模型，并設計了一種多目標進化算法進行求解。劉雪梅等[4]以物料配送成本最低以及物料到達工位的滿意度最高為優化目標建立數學模型，并利用NSGA-Ⅱ算法對模型進行求解。而目前對GVRPPD的研究大都集中在城際物流中，將燃油費用[5]與碳排放量[6]作為優化目標。為實現車間物流運輸和節能減排協同發展[7]，學者們針對柔性制造車間內的GVRPPD問題進行深入研究，主要分為兩個研究方面：一方面是以AGV的運動狀態和路徑平滑度[8]作為研究對象：Gao J等[9]從AGV的車身結構與運動狀態對AGV能耗特性進行分析，將行駛距離和運輸總能耗作為優化目標，建立了針對異構AGV車隊的節能路徑規劃模型；郭興海等[10]以行駛路徑最短與路徑平滑度最大為優化目標，設計了一種以改進QPSO算法與Bezier曲線相結合的兩階段全局路徑規劃方法。另一方面，在柔性制造車間的物流運輸過程中，AGV能耗與車身負載重量成正比例關系[11]。因此，考慮集配貨過程AGV車身負載量[12]的變化成為另一研究重點：周炳海等[13]針對混流裝配線中AGV先集貨后配貨的過程將AGV的總重量及行駛時間作為組合優化目標，并提出了一種改進的多目標引力搜索算法對問題進行求解。Wang H F等[14]將AGV運輸過程中的車身負載量與AGV行駛速度作為優化目標建立AGV行駛能耗模型，并通過加權指數的方式對配送費用與能耗兩優化目標之間進行評估與權衡。

上述學者對集配貨車輛路徑規劃問題作出了拓展性的研究，且均對柔性制造車間內的GVRPPDTW問題的研究有一定的啟發與幫助，本文在當今學者研究的基礎上，構建一種以AGV集配貨過程能耗與時間偏離能耗之和最小化為優化目標的GVRPDPTW模型。并針對所研究問題特性，利用變鄰域搜索算法對遺傳算法局部搜索能力較弱的劣勢進行彌合[15]，設計了一種包含5種鄰域結構的改進變鄰域搜索的混合遺傳算法，最后通過對數值實驗進行對比分析，驗證本文模型及算法的可行性與有效性。

1 問題描述

根據生產作業排程安排與工件加工工藝的要求，車間通常需要多道工序間的配合來共同完成對工件的加工。某柔性制造車間對一同種類型的工件進行加工，AGV在其內部執行物料運輸任務，車間內部含有n個工位點，此工件的加工需要兩道工序配合完成，將兩道工序分別定義為p1和p2，工序之間存在加工順序優先級的約束，即p1>p2，且每道工序對應的工位均為并行工位。為了保證車間內整體運營效率，要求AGV不能在超過規定時間窗口的最晚時間對工位點進行集配貨操作，車間內每個運輸周期完成后，AGV將返回充電站進行充電。

為了有效說明所研究的問題作出如下基本假設：

（1）假設車間內部平穩生產，不會出現停機、故障和AGV碰撞等現象發生。

（2）各工位的服務時間窗、二維地理坐標、集配貨量已知。

（3）充電站內部存有多臺同質AGV，其裝載量一致且已知。

（4）AGV執行運輸任務時從充電站出發，完成對應運輸任務后，最終返回至充電站。

（5）AGV行駛速度恒定，其行駛能耗只與車身負載質量與行駛距離有關。

2 模型建立

2.1 符號及變量定義

將AGV運輸網絡抽象為一個無向圖G=(V,A)，其中 V={0}∪{V0}，其中節點0點為AGV的充電站，V0={1,2,···,n}表示工位點集合；A表示連接各個節點的所有邊的集合，A={(i,j)|i,j∈V}。

本文所需變量定義如下：

k為AGV集合K={1,2,3,···,m}中的任意一輛車，m為最大車輛數；Uijk為第k輛AGV從工位點i行駛工位點j到配貨量，(?i,j∈V0,i≠j)；Vijk為第k輛AGV從工位點i行駛工位點j到集貨量，(?i,j∈V0,i≠j)；ETi為 工位點i的時間窗下限；LTi為 工位點i的時間窗上限；Ti為AGV到達工位點i的 時間；dij為AGV從工位點i到工位點j的行駛距離；xijk為決策變量，若第k輛AGV從工位點i直接到達工位點j，則xijk=1，否則為0。

本文所需常量定義如下：

Q為AGV的最大車身負載量；Q0為AGV的自身重量；Pt為 AGV待機功率；g為重力加速度；Cr為滾動系數。

2.2 目標函數與約束條件

根據問題描述，建立以柔性制造車間AGV運輸過程總能耗最小為優化目標的GVRPDPTW模型。模型的總能耗分別由集配過程能耗與時間偏離能耗兩部分組成。

（1）集配過程能耗

為了在充分說明AGV在工位點之間集配貨過程的能耗情況，本文以Briand C[16]所提AGV能耗計算方式為建模基礎，并根據所提問題特性，現將集配過程能耗Ep定義如式（1）。

（2）時間偏離能耗

由于AGV車身所配置的電池容量有限，過長的待機時間不僅會造成AGV執行車間內部的裝載任務時的準時率下降，還有可能導致AGV電池電量過度消耗而無法支持剩余任務的完成。

基于上述分析，為保證對AGV運輸過程中能耗問題考慮的全面性，本文定義時間偏離能耗Et如式（2）所示。

上述公式中，式（4）確保派出的AGV數不超過AGV的總數；式（5）確保每個工位點只被一輛AGV訪問，且只被訪問一次；式（6）為消除子回路約束；式（7）表示AGV從充電站出發后又返回充電站；式（8）確保AGV運輸路線的任一節點的車身負載重量均不超過車身最大負載量，并保證AGV先駛至p1所在工位點進行集貨操作后，駛至p2所在的工位點配貨；式（9）～（10）確保AGV從充電站出發并完成所對應的運輸任務后返回充電站時，車身負載為0；式（11）表示AGV對工位點i服務的時間不能超過i點的時間窗上限。

3 混合遺傳算法設計

針對柔性制造車間內帶時間窗的AGV集配貨綠色路徑規劃問題，所設計的改進變鄰域搜索的混合遺傳算法流程圖如圖1所示，其中Gen為當前迭代次數；GenMax為 預設最大迭代次數；Iter與IterMax為變鄰域搜索當前次數與總次數。

圖1 混合遺傳算法流程圖

3.1 編解碼設計

常見的染色體編碼方式有二進制編碼、整數編碼、矩陣編碼等。本文根據GVRPPDTW問題特性，采用整數編碼的方式對其進行編碼操作。針對該柔性制造車間染色體基因總數為n+m。工位點編號為{1,2,···,n?1,n}，AGV小車的編號為{n+1,n+2,···,n+m}，通過向前插入AGV編號使染色體的基因組成多個基因片段，每個基因片段表示集配貨任務中的一條路徑。

例如：當n=10，m=3時，待服務的工位編號集合為 {1,2,3,4,5,6,7,8,9,10}，AGV編號為 {11,12,13}，則一個可行的染色體為{2,5,4,12,1,6,7,11,9,6,10,8,3,13}，具體編解碼操作如圖2所示。

圖2 解碼示意圖

3.2 根據集配特性產生初始種群

本文根據集配貨問題的特性將初始種群以工位的優先級選擇順序和隨機遍歷相結合的方式生成初始路徑，并對每條路徑進行時間偏離優化進而生成初始種群。具體步驟如下：

Step 1：根據車間工位點的編號，分別確定集貨點和配貨點集合I1、I2。

Step 2：遍歷所有工位點，分別從I1、I2中隨機選擇滿足AGV車身最大負載量的集貨點和配貨點組成一條初始路徑。

Step 3：判斷集合剩余工位點的貨物量是否大于AGV最大車身負載重量，若剩余貨物量大于車身負載量則回到Step2，否則收集剩余集合工位點生成最后一條路徑。

Step 4：對生成的初始路徑在滿足集配貨問題約束的前提下，根據工位的左時間窗對所有路徑進行時間偏離優化，生成初始種群。

3.3 適應度函數

為提高算法求解效率與尋優質量，本文根據所提問題特性，引入懲罰策略對路徑進行約束。因此染色體個體Su的適應度函數f(Su)定義如式（12）所示：

其中：α和β表示一個極大數值；li表示若第u個染色體路徑存在違反容量約束的路徑則lu=1否則lu=0；wu表示若第u個染色體路徑存在違反時間約束的路徑則wu=1，否則wu=0。

3.4 交叉算子

為產生不同的AGV集配貨任務分配方案，本文通過OX交叉算子來擴大解空間的搜索范圍。如圖3所示，首先針對執行交叉操作的兩個染色體的交叉位置進行隨機選擇，進而確定交叉片段，以子代2的生成為例：將父代1中序列4-5-6-7-8作為子代2的第一段，將父代2篩去點位4、5、6、7和8后的序列作為子代2的第二段，同理生成子代1。

圖3 染色體交叉操作

3.5 自適應變異算子

為維持種群多樣性，防止算法陷入局部最優解，本文在傳統的單點變異方式基礎上采用一種自適應變異方式對算法全局進行擾動，如式（13）所示。通過染色體的適應度值進行變異概率的自適應確定，減少優秀染色體被變異操作破壞的可能性，從而提高尋優計算效率，加快算法收斂速度。

式中：fmax為迭代過程中種群的最大適應度值；favg為種群平均適應度值；f為當前染色體適應度值，k1、k2為常數且k1、k2∈(0～1)。

3.6 變鄰域搜索算法

考慮到遺傳算法在求解過程易陷入局部最優解，為了進一步改善解的質量，本文引入變鄰域搜索算法對種群中部分最優染色體進行局部搜索操作。并針對本文問題模型特點，設計了基于5種鄰域結構的搜索機制，旨在保證算法局部搜索能力的前提下，增加鄰域結構的多樣性。

（1）基于逆序反轉的搜索策略

在染色體內部隨機挑選兩個基因位置，將兩者之間的全部基因進行逆序反轉操作。如圖4a所示。

圖4 鄰域結構示意圖

（2）不同路徑間的搜索策略

①2-2交換：隨機選擇兩條路徑，在路徑1和路徑2中分別隨機選取兩個工位點進行互換操作。如圖4b所示。

②2-0插入：隨機選擇兩條路徑，在路徑1中隨機選取兩個工位點依次插入到路徑2中。如圖4c所示。

（3）同一路徑內的搜索策略

①1-1交換：對于同一條路徑，隨機選擇兩個工位點進行位置互換。如圖4d所示。

②1-0插入：對于同一條路徑，隨機選擇一個工位點將其插入此路徑內的任一位置。如圖4e所示。

因本文設計的鄰域結構較多，每次循環需遍歷所有鄰域結構。而在算法迭代的不同時期，種群所需的擾動強度不同，為提升算法求解速率，本文采取一種自適應的搜索次數策略。在算法迭代初期采用較低的迭代次數，以此來加快種群收斂；在迭代后期增加搜索次數，對染色體進行深度搜索。具體公式如式（14）所示。

式中:NSnum表 示第gen代染色體的變鄰域搜索次數；ρ1表 示變鄰域搜索的最小次數；ρ2表示自適應搜索次數；MAXgen表示算法預設的最大迭代次數；?」表示向下取整。

變鄰域搜索操作步驟如下：

Step 1：初始化參數，并根據式（14）自適應確定最大搜索次數IterMax。

Step 3：隨機選擇兩條路徑，對路徑1和路徑2分別進行2-2交換以及2-0插入的搜索操作，得到滿足≥f(Su)的新解。

Step 4：遍歷所有AGV的運輸路徑，針對路徑內部進行1-1交換和1-0插入。得到滿足≥f(Su)的新解。

Step 5：判斷是否達到自適應搜索次數的最大值，若Iter>IterMax則重新編碼生成優化后的染色體，否則回到Step2。

4 仿真實驗

本節實驗共分為兩組，第一組實驗采用Solomon的標準算例庫進行數值實驗，并與已知國際最優解進行數據對比，驗證本文設計算法的可行性；第二組實驗以某工廠柔性制造車間實際生產過程中某一時段的生產數據作為實驗案例，通過與GA和VNS算法所求結果進行實驗對比，驗證本文算法有效性。

所有仿真實驗均在加速頻率為2.6 GHz的Inter i5-9400處理器、運行內存為16 GB的Windows10PC平臺進行，其中程序編譯和運行環境為MATLAB R2018b。算法的實驗參數設置如下：種群規模P=100、迭代次數GenMax=300、交叉概率Pc=0.9、自適應變異式中k1=0.05,k2=0.1、自適應變鄰域搜索次數式中 ρ1=20,ρ1=100，模型中的g=9.8N/kg，Cr=0.71。

4.1 算法可行性驗證分析

柔性制造車間內部的GVRPPDTW問題為經典VRP的延伸問題，為了驗證本文算法的可行性，本文測試數據選自Solomon標準測試數據集[17]。該數據集共分為6大類，即C1、C2、R1、R2、RC1、RC2，其中C類與R類分別表示客戶點分布為密集和隨機；RC類則介于兩者之間，1和2作為時間窗緊密和寬松的表達形式。

為保證數值實驗的全面性與完整性，本文分別針對客戶點規模、客戶地理位置分布情況選取部分算例進行實驗,并對每個算例重復計算10次，取10次結果中的最優值，計算結果如表1-3所示。

表1 客戶規模為25的算例求解結果

表2 客戶規模為50的算例求解結果

表3 客戶規模為100的算例求解結果

由表中數據分析可知，客戶數量為25的小規模算例相較于國際最優算例的平均偏差為0.27%；客戶數量為50的中規模算例平均偏差為0.41%；客戶數量為100的大規模算例平均偏差為1.27%；從上述求解結果來看，本文算法與已知國際最優解偏差較小，對于不同規模的算例均能求得近似滿意解。因此，本文算法的可行性得以驗證。

4.2 算法有效性驗證分析

以某工廠柔性制造車間為背景，所建立的車間拓撲地圖如圖5所示，共由包括AGV充電站在內的27個節點，32條邊組成。其中編號0為AGV充電站，編號1～13與14～26分別表示集貨工位點與配貨工位點。本文通過截取實際生產過程中某一時段的生產數據來構造本次實驗案例，如表4所示。

表4 工位點信息

圖5 車間拓撲地圖

車間內共有5輛AGV，本次實驗所需AGV具體參數如表5所示。

表5 AGV參數

為了驗證本文算法求解的有效性，在本文設計的案例條件下與GA，VNS算法的計算結果進行實驗分析。3種算法實驗條件及參數相同，每種算法重復計算10次，取計算結果中的最優值，如表6所示。

表6 各算法運行結果比較

根據實驗所得數據，本文所設計的算法在集配過程能耗與時間偏離能耗方面，較GA優化了3.9%與67.7%，較VNS算法優化了0.7%與37.4%，在AGV運輸總能耗方面能夠分別降低7.1%與1.6%。這是因為本文將兩種算法優勢互補與改進，優化了總運輸路線中AGV對工位點的服務順序，從而使AGV運輸過程的能耗與行駛距離得到平衡，并且本文所設計的算法所求解的行駛路線能夠將AGV對更多工位的服務時間控制在其對應的時間窗口內，因此在優化AGV運輸過程總能耗問題中，本文所設計的算法求解質量更高，且針對實際生產案例也表現出良好的尋優能力，使得本文算法的有效性得以驗證。

5 結語

本文針對柔性制造車間背景下帶時間窗約束的AGV集配貨綠色路徑規劃問題進行了研究，得出結論如下：

（1）以最小化AGV集配過程能耗及時間偏離能耗作為組合優化目標，構建AGV綠色車輛路徑規劃模型，能夠相對客觀全面地反映柔性制造車間內部AGV運輸總能耗的情況。

（2）設計了一種改進變鄰域搜索的混合遺傳算法用于求解本文所研究的問題，并針對問題特性設計了5種鄰域結構的搜索機制；首先通過Solomon算例驗證本文所設計算法的可行性，然后與GA和VNS算法進行實驗仿真，最終的實驗結果表明，本文所設計的算法在求解質量上均優于GA和VNS算法。

本文研究的帶時間窗約束的AGV集配貨綠色路徑規劃問題柔性制造車間運輸能耗問題，為了進一步實現車間節能減排的發展目標，后續，將針對節能視角下的加工資源和運輸資源集成調度問題進行深入研究，并對求解算法作出進一步優化。