0.引言

智能工廠是實現智能制造的關鍵環節。在智能工廠中，智能設備得到了廣泛的應用，AGV、智能機械手等智能搬運設備組成了智能生產物料系統。多搬運載體間的協同作業對智能工廠的正常運轉具有十分重要的意義。近年來，多搬運載體間的協同作業研宄成為物流領域的關注熱點，國內外學者針對協同問題開展了大量研究。
在搬運載體協同研宄方面，陳敏等[1]針對智能車間中多AGV的調度問題進行研宄，提出7個調度運行機制，通過運用PlantSimulation對進行仿真，驗證調度方案的合理性。賀長征等[2]針對柔性制造車間中AGV和加工設各的協同調度問題，建立雙資源優化數學模型，設計了“時間窗+Dijkstra+遺傳算法的混合算法進行求解，并采用了3種規則解決最優路徑規劃中的沖突問題。劉旭等[3]建立以AGV工作過程中行駛時間最短的數學優化模型，對遺傳算法的交叉變異算子改進，求解獲取多AGV協同調度的最佳方案。岳笑凸等研宄面向柔性制造系統中多自動牽引小車的協同調度問題，考慮小車的續航能力因素，以任務的最小完成時間和車輛數最少使用量為調度目標，采用混合遺傳一粒子群算法進行求解，并通過仿真驗證模型和算法有效性。AbdelmaguidTF等[5]研究加工設備和多AGV雙資源間的協同優化，以最大任務結束時間為優化目標，提出一種新的混合遺傳算法編碼方案進行求解，通過82組實驗算例，驗證模型和編碼方案的性能優劣性。

在路口避碰研究方面，胡杰杰[6]針對智能車間柔性物理，設計了集中式的AGV群控協調算法，賦予AGV任務優先級，解決節點處的沖突問題。肖萌[7]針對多AGV沖突問題以高優先級優先通過為原則，提出沖突判據方法和主軌道雙向并行避碰策略，通過仿真驗證和實現該方法。肖海寧等[8]研宄單向引導路的AGV系統，建立基于有向圖的AGV系統模型，基于此提出路徑鎖死的破解規則，通過PIantSimuIation仿真驗證其有效性。喬巖等[9]研宄在動態變動環境下，針對AGV臨時改變行進路線的清況，在交叉節點對AGV的優先級進行動態調整AGV通過路口順序，并以此更新AGV路線，以改進時間窗算法進行仿真實驗，證明方法的具備更好的魯棒性和高效率性。
目前的研究多為考慮單資源和雙資源的協同問題，在三資源協同作業方面研宄較少，在協同研宄中考慮搬運載體路口避碰的研宄也較少。本文考慮倉庫存取貨的堆垛機、工位間搬運物料的AGV和線邊裝卸物料的機械手三資源的協同作業中，同時設計多AGV在交叉路凵的可同時通行的避碰規則，優化整個作業車間的物流作業效率。

1.多載體協同作業優化模型

1.1問題描述及假設條件

1.1.1問題描述

針對智能工廠中多搬運載體的協同作業問題，以倉庫存取貨的堆垛機、工位間搬運物料的AGV和線邊裝卸物料的機械手為研究對象，研究堆垛機．AGV．線邊機械
手三個資源協同執行運輸任務的同時，考慮多AGV在交叉路口的避碰問題，建立以最大完工時間最小化的數學規劃模型，并建立成本懲罰函數作為輔助優化模型。車間物流作業流程如圖1所示，AGV n ，在倉庫前的物料交接點等待堆垛機將物料從立體倉庫搬運到AGV m 上，由AGV。選擇最優路徑（紅色路徑）將物料運輸到需求工位旁的交接點，由機械手進行卸載。

圖1 車間多搬運載體協作流程圖

1.1.2模型假設

根據智能車間的實際情況，為了便于模型求解分析以及考慮AGV交叉路口的碰撞情形，對問題進行合理的假設與簡化：
1）AGV在空載和負載的情況下均為勻速行駛；
2）不考慮AGV加速和減速過程；
3）搬運載體車況良好且均有額定容量；
4）AGV的任務執行過程為連續的，不存在中斷的情況；
5）AGV可同時接受多個任務，依次執行；
6）考慮AGV在路口的碰撞和堵塞情況；
7）堆垛機和機械手的操作時間和裝卸順序為己知；
8）各搬運載體間相互獨立，不存在約束情形；
9）小車在容量充足的情況下，可搬運多個物料或工件；
10）同類型搬運載體的工作能力指標相同。

1.2參變量定義

1.2.1參數設定

H：表示路徑節點的集合，h=1，2，···，H;I：表示任務的合集，i=1，2，···，L：表示堆垛機的集合，i=1，2，···，L；M：表示AGV的集合，m=1，2，•••,M;N：表示機械手的集合，n=1，2，···，N;S：表示路徑的集合．s=1，2，···，S:K：表示路口的合集，k=1，2，···，K:Ti：表示任務i的完工時間；T1：表示堆垛機執行完單個任務所需的平均時間；Tn：表示機械手執行完單個任務所需的平均時間；TLi：表示堆垛機I開始執行任務i的時刻；Eni：表示機械手n執行完任務i的時刻；Ti：表示機械手n開始執行任務i的時刻：Tilm：表示AGVm開始執行堆垛機1執行完的任務i的時刻；qms：表示AGV。行駛的距離；Vm：表示AGV。的行駛速度；t1mn：表示AGVm從堆垛機行駛至機械手n所需的時間；qms表示AGVm在交叉路口所處的相位；Qqms：表示AGm在交叉路口所處相位的集合。

1.2.2決策變量

tim：AGVm執行完任務i時刻；

1.3目標函數

為實現車間工作效率最大化和物料送達時間誤差最小，本文提出智能車間多搬運載體協同作業的兩個優化目標，構建完工時間和懲罰成本均最低的多目標優化函數。

1.3.1最短完工時間

minZ=max{Ti}     (1)
其中

式中，Ti表示任務i的完工時間，T1i表示堆垛機1開始執行任務i的時刻，Eni表示機械手n執行完任務i的時刻，整體優化目標為最大完工時間最小化。

1.3.2 最低懲罰成本

針對物料送達過程可能出現的提前送達、準時送達和延遲送達三種情況，本文對三種送達情況建立相應的成本懲罰函數，并作為第二個優化目標，如式(5)所示。
minC=min{f(tim)}     (5)
其中，考慮到物料運輸延遲送達對項目進度的影響損失比物料運輸提前送達對項目進度的影響損失更為嚴重，同時為增強資源配置過程中的柔性[10,11]，建立如圖2所示的曲線型軟時間窗成本懲罰函數。
假設最佳到達的時間窗為[ta,tb]，在此基礎上，可偏離得到可接受服務時間窗[t'a,t'b]，其中，t'a=ta-Δ1，t'b=tb+Δ2。若AGVm在[ta,tb]內將物料送達指定工位，懲罰成本為0；若AGVm在[t'a,t'b]或[tb,t'b]內將物料送達指定工位，只需承擔較少的懲罰成本；若AGVm在（0，t'a)或（t'b，∞ )內將物料送達指定工位，則需要承擔較多的懲罰成本。基于曲線型軟時間窗的成本懲罰函數如式（6）所示。

圖2 基于曲線型軟時間窗的懲罰成本函數

式（6）表示在曲線型軟時間窗的約束下，AGVm執行完任務i的時刻tim所對應的懲罰成本。如圖2所示，若AGVm在t'a時刻之前送達，單位時間所需承擔的懲罰成本為cp1，同時還需要承擔[t'a,ta]時間段所產生的懲罰成本；若AGVm在[t'a,ta]時間段內送達，單位時間所需承擔的懲罰成本為cp2；若AGVm在[ta,tb]時間段內送達，懲罰成本為0；若AGVm在[tb,t'b]時間段內送達，單位時間所需承擔的懲罰成本為cp3；若AGVm在t'b時刻以后送達，對應的單位時間所需承擔的懲罰成本為cp4，同時還需承擔[tb,t'b]時間段所產生的懲罰成本。
式中，α和β為提前送達和延遲送達的成本懲罰權重，分別取值為0.1和0.8[12]。

1.4約束條件

其中，式（7）表示任何時刻一臺堆垛機只能被分配一個任務；式（8）表示任意時刻同一任務只能被分配給一個加工工位；式（9）表示兩臺相位相沖突的AGV不能同時通過路口；式（10）表示每個任務在同一時刻只能由一臺AGV執行；式（(1)表示每個任務在任意時刻只能分配給一個堆垛機；式（12）表示機械手開始處理的時刻不得早于AGV將物料送達機械手所在交接點的時刻：式（13）表示任務被完成的時刻；式（14）表示只有在堆垛機將物料卸載在交接點后，AGV才能開始執行任務；式（巧）表示每臺AGV待執行的任務需依次排序執行：式（16）表示參數的非負限制。

2.AGV路口避碰規則

路口碰撞可分為相向沖突、路口沖突和節點占用沖突三種[13]。傳統路口避碰為題大多賦予AGV不同級別的優先級，按優先級高低依次通過，單次只能通過一輛AGV[13]。本文研宄中，為使AGV避碰環節更貼近實際，AGV在行駛過程中經過某交叉路口時，根據傳感器和RFID采集的數據，分析當前路口的通行情況和路口AGV行駛信息，通過檢測每輛AGV的行駛方向，判斷多輛AGV的是否可同時通行，并對相沖突的AGV進行優先級調整，使路口可同時通行多輛AGV，有效減少等待時間和碰撞情況的產生。

2.1 AGV沖突類型檢測

AGV行駛臨近交叉路口時，根據傳感器和RFID采集的數據，控制系統對AGV位置和時間狀態進行更新，檢測并分析在即將駛入的路口是否會發生沖突及其沖突類型。
檢測中參數定義如下：
1)λbm為表示AGVm到達節點h的時間；
2）εhm為表示AGVm在節點h的停留時間；
3）θ為表示沖突檢測時的安全時間間隔閾值；
4）Kmh為節點h的識別碼，且該節點在AGVm的規劃行駛路徑中；
5）Kmh-1<Kmh<Kmh+1為AGVm通過的節點順序。
沖突檢測模型如下：
1）相向沖突
若檢測過程中滿足以下關系式(17)、式(18)、式(19)，則AGV在路口將發生相向沖突。

2）路口沖突
若檢測過程中滿足以下關系式（20）和式（21），則AGV在下一路凵將發生路口沖突。

3）節點占用
若檢測過程中滿足以下關系式（22）和式（23），則AGV在下一路口將發生節點沖突。

2.2 路口沖突AGV的優先級動態調整

如圖3所示，AGVm行駛至交叉路口時，每輛AGVm均有gs、tl、tr三種行駛方向的可能性，分別代表直行、左轉、直行，在路口設置互容和不容兩種通行相位，處于互容相位的多輛AGV可在不碰撞的情況下同時通過，處于不容相位的多輛AGV不能同時通過路口，（假設路口的轉彎半徑可同時容納兩輛互容相位的AGV同時通過）。比如AGVtrm1則表示AGVm1在路口右轉，則與AGVtlm2、AGVtrm2、AGVtrm3、AGVgsm2、AGVtrm4、AGVgsm4是互容相位，可同時通過路口，與AGVgsm2、AGVtlm3、AGVtlm4是不容相位，不可同時通過路口，其通過路口順序需根據優先級調整確定。

圖3 AGV在路口的沖突相位圖

在交叉路口處于不容相位的AGV，為保證各AGV之間有明確的優先關系，通過賦予AGV優先級來確定通路口的先后順序，其依據是根據理論上AGV完成正在執行任務的剩余時間，值越小，則AGV優先級越大，不同的優先級以增幅A來確定，若是空載車輛，優先級則設為最低。
其中：

式中，rest（Ti)表示任務i的剩余完工時間；Number(k)表示當前路口排隊不容相位排隊通行的車輛數。

2.3 雙路囗路徑容量檢測

為減少雙路口之間路徑的堵塞現象，當AGV即將抵達雙路口路徑時，在檢測交叉路口沖突情況的同時，檢測雙路口之間路徑堵塞情況，評估當前是否可以進入該路徑而不造成堵塞，如圖4所示，評估標準為路徑剩余可容納的車輛數：
N(s)=F[ s ]-Y(s)       (25)

圖4 雙路口路徑容量檢測示意圖

式中，N（s）為路徑s的剩余可容納的車輛數；F（s）為路徑可容納車輛的額定容量，取值向下取整；Y(s)為路徑s中己進入的車輛數；ls為路徑s的長度；
lAGVm為AGVm的長度，θ為行車過程中的最小安全距離。
當N（s）＜1時，將禁止AGV通過交叉路口，等待直至有AGV從路徑駛出。

3 粒子群算法

PSO是Kennedy和Eberhart受鳥群群體運動的啟發于1995年提出的一種新的群智能優化算法[14]，通過粒子間的信息共享，協作完成尋優任務，具有記憶性強、效率
高和搜索速度快等特點，但易陷入局部最優，即局部尋優能力強，全局尋優能力弱[15]。本文對粒子群算法進行優化，采用動態慣性權重和引入遺傳算法中的自適應變異概率，避免算法后期陷入局部最優，提升算法的收斂能力和收斂精度，算法流程如圖5所示。

圖5優化自適應粒子群算法流程圖

3.1 PSO算式

設求解模型的維度為D維，有1個粒子，粒子群為L={p1,p2,…,pi,…,pl}速度表示為V={v1,v2,…,vi,…,vD}，位置表示為X={x1,x2,…,xi,…,xD}，pbesti表示粒子i經過的最佳位置，gbesti表示所有粒子經歷過的最佳位置。PSO算法的粒子i的第D維速度更新公式為式(27)，粒子i的第D維位置公式為式(28)：

式中，vkid表示粒子i進行第k次迭代時速度矢量的第D維分量；vkid表示粒子i進行第k次迭代時位置矢量的第D維分量；c1，c2表示學習因子加速度，其值為常數；r1，r2為取值范圍為[0,1]的兩個隨機參數；w表示慣性權重，取值非負，用來調節對解空間的搜素范圍。
慣性權重表示粒子i的先前速度對當前速度的影響。全局尋優能力與其值成正比，局部尋優能力與其值成反比；反之，粒子局部尋優能力強，全局尋優能力弱。即，值過大，則容易錯過最優解；值過小，則算法收斂速度慢或是容易陷入局部最優解。當問題空間較大時，為了在搜素速度和搜索精度之間達到平衡，故本文采用動態慣性權重式(29)，使算法在迭代初期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度，隨著迭代次數地增加，w不斷減小，進而使算法在初期有較強的全局收斂能力，而后期有較強的局部收斂能力。

式中，wmax表示最大慣性權重；wmin表示最小慣性權重；t表示當前迭代次數；tmax表示算法最大迭代次數。

3.2 自適應變異

在算法迭代初期，種群個體的差異性較大，為避免產生不良解，同時為使算法快速收斂，應以較小的概率進行變異。在迭代后期，種群個體多樣性逐漸降低，為避免算法陷入局部最優[14]，應以增大個體的變異率。

式中，Pmmin表示最小的變異概率，取值為0.01；Pmmax表示最大的變異概率，取值為0.1。t表示當前的迭代次數；tmax表示最大的迭代次數；Di表示粒子i到當前最優解的歐氏距離；Dmax表示種群中離當前最優解最遠的粒子i的最大歐氏距離。

4 算例分析

以電氣配件制造車間為例進行本文的實例驗證。該車間的電氣配件制造工序包括鉚接、壓線、點焊、攻牙、噴印、移印、預裝配、總裝配等。該廠裝配車間有一個原料倉庫，其中包括4個立體倉庫，3個堆垛機，車間有15個加工工位，編號1-15，車間呈S型分布，分布步長為5米，每個加工工位前有1臺線邊機械手，6臺激光引導式AGV。AGV負責原料和在制品的配送。該車間個搬運設備參數如表1所示，各工作站點間的車輛行駛時間如表2所示，0表示原料倉庫，各加工工位間的距離如表2所示。
本文以固定的搬運任務數和固定使用的AGV數分別進行實驗，并分別考慮在交叉路口避碰和不考慮避碰的兩種情況進行對照。算例1搬運任務為40，堆垛機數3，AGV數為3；算例2搬運任務為40，堆垛機數3，AGV數為6；算例3搬運任務為70，堆垛機數3，AGV數為3；算例4搬運任務為70，堆垛機數3，AGV數為6。

表1車門搬運設備實際參數表

表2 各工作站點間距離表

實驗結果如表3所示，搬運任務數相同時，AGV在交叉路口的耗時與AGV數量成正比，總完工時間與AGV數量成反比。AGV數量相同時，AGV在交叉路口的耗時和總完工時間均與搬運任務數成正比，即固定AGV的使用數量，搬運任務越多，AGV在交叉路口的耗時和總完工時間都隨之增加。
1）交叉路口考慮避碰
實驗結果如表4所示，考慮AGV在交叉路口的避碰情況，每個算例中AGV在路口的等待耗時均有不同程度的減少，隨著AGV數量或者搬運任務數量的增加，

表3 交叉路口不考慮避碰的實驗結果表

AGV在路口的碰撞可能性增加，使得AGV在路口的等待耗時減少效果較為明顯。
將在交叉路口不考慮避碰規則和考慮避碰規則兩種情況進行對比，如圖6和圖7所示，算例1-4在考慮避碰規則下，路口等待時間和總完工時間都有一定程度的減少，即在考慮交叉路口避碰的情況下，多設備協同作業的總完工時間、路口等待時間和作業效率都有所提高。

表4 交叉路口考慮避碰的實驗結果表

2）結果對比

圖6 兩種情況的交叉路口等待耗時圖

圖7 兩種情況的總完工時間圖

3）算法性能比較
通過算例2將本文的優化自適應PSO與傳統PSO進行比較，由圖8和表5可知，在迭代初期，算法趨于快速收斂，在25代左右尋得次優解。在迭代后期，基于自適應變異概率，其概率值增大，算法的搜索空間得以增大，在35代左右找到全局最優解。優化自適應PSO在解的變化和種群均值的變化都更為穩定且收斂速度更快。

表5 算法運算結果比較表

圖8 目標函數變化曲線圖

5 結語

本文針對智能工廠中多搬運載體的協同作業問題，建立以總任務完工時間最少為主決策目標和以懲罰成本最低為輔助決策目標的協同作業優化模型�？紤]AGV在交叉路口的避碰規則，AGV在檢測以互容和不容兩種相位判斷多輛AGV是否可以同時在交叉路口通行，針對處于不容相位的AGV，通過動態調整行車優先級規則，以最大程度上保證任務執行的準時性。協同作業模型采用優化PSO算法求解，為避免在迭代后期陷入局部最優，引入遺傳算法中的自適應變異，增強算法搜索解的維度空間。以電氣配件制造裝配車間為實例，以控制變量法對在交叉路口考慮避碰規則和不考慮避碰進行對比，結果表明在路口等待時間和總完工時間上，考慮避碰規則的結果都優于不考慮避碰的情況。將優化PSO算法和傳統PSO進行同模型同算例對比，結果表明在最優解、種群最優解均值和收斂次數上優化自適應PSO算法呈較為明顯優勢。

參考文獻：

[1] 陳敏,黎展滔,陳慶新,等.考慮有限物流運輸能力的智能車間AGV調度算法研究[J].工業工程,2019,22(4):49-57.
[2] 賀長征,宋豫川,雷琦,等.柔性作業車間多自動導引小車和機器的集成調度[J].中國機械工程,2019,30(4):438-447.
[3] 劉旭,樓佩煌,錢曉明,等.基于改進遺傳算法的物料配送多AGV調度優化[J].機械設計與制造工程,2015,44(3):16-21.
[4] 岳笑含,許曉健,王溪波.面向FMS基于改進的混合PSO-GA的多AGV調度算法研究[J].計算機科學,2018,45(S2):167-171.
[5] Abdelmaguid T F, Nassef A O, Kamal B A, et al. A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J].International journal of production research,2014,42(2):267-281.
[6] 胡杰杰.面向制造車間柔性物流的AGV群控系統研制[D].北京郵電大學,2019.
[7] 肖萌.基于混合遺傳算法的電力設備檢測柔性調度研究[D].武漢理工大學,2018.
[8] 肖海寧,樓佩煌.自動導引車系統避碰及環路死鎖控制方法[J].計算機集成制造系統,2015,21(05):1244-1252.
[9] 喬巖,錢曉明,樓佩煌.基于改進時間窗的AGVs避碰路徑規劃[J].計算機集成制造系統,2012,18(12):2683-2688.
[10] Belhaiza S, Hansen P, Laporte G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J].Computers & Operations Research,2014,52:269-281.
[11] Belhaiza S. A game theoretic approach for the real-life multiplecriterion vehicle routing problem with multiple time windows[J]. IEEE Systems Journal, 2016,12(2):1251-1262.
[12] Lau H Y K, Zhao Y. Integrated scheduling of handling equipment at automated container terminals[J].International journal of production economics, 2008,112(2):665-682.
[13] 李珍惜.基于激光導航AGV路徑規劃與避障算法的研究[D].西安科技大學,2019.
[14] Mousavi M, Yap H J, Musa S N, et al. Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PloS one,2017,12(3):e0169817.
[15] Ma Y, Xu J. A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows[J].Engineering Optimization,2015,47(6): 825-842文章來源于AGV吧