隨機批量物料搬運的制造系統AGV配置優化

張惠煜，陳慶新，毛 寧

廣東工業大學 廣東省計算機集成制造重點實驗室，廣州 510006

定制型裝備制造企業生產系統屬于復雜的離散制造系統，具有隨機不確定性（訂單到達、工序工時以及返修等不確定因素）、生產周期長、拖期現象嚴重以及多品種大規模在制品等特點。由于生產車間物料搬運任務十分龐大，基于AGV（Automatic Guided Vehicle）的物料搬運系統（Material Handling System）成為生產車間至關重要的組成部分。AGV的數量對系統性能的優化具有顯著的影響，然而這類設備的價格昂貴，在制造系統中如何以最低的成本優化配置AGV 的類型及數量，以滿足系統產能及訂單交貨期的需求，是系統設計階段的關鍵問題[1-2]。本文考慮的AGV配置問題是一個具有雙重約束的隨機非線性整數規劃問題，然而這些約束（系統產能和訂單交貨期）無法用決策變量（AGV數量）的封閉形式表達。因此，建立一個有效的性能分析模型以獲得系統運行指標是求解AGV配置優化問題的基礎。

AGV 的數量配置問題是AGV 系統設計及控制的主要問題之一，目前求解的主要方法可以分為兩類：解析方法（基于數學理論建立數學模型進行求解計算）和仿真方法（基于仿真平臺建立仿真模型進行實驗計算）。由于所涉及問題的復雜性，解析方法只能獲得問題的近似解，基于經驗統計的仿真實驗可以應用于復雜系統獲得較為精確的結果，然而仿真實驗需要消耗大量的時間[3-4]。文獻[5]根據AGV行程需求是否已知將問題劃分為確定需求模型（行程需求已知）和隨機需求模型（需要估計AGV 的空載行程），并綜述不同的求解方法。對于隨機系統主要應用排隊理論進行求解，文獻[6]建立排隊模型計算AGV 的數量使AGV 的可用概率滿足工作站的需求，但這個模型在求解稀疏車流系統時往往高估了AGV的需求數量。文獻[7]根據G/G/c排隊模型計算AGV 在傳輸和請求之間的等待時間，以等待時間為約束設計算法優化AGV 數量，該模型不考慮批量處理的情況。文獻[8]基于閉排隊網分析系統穩態行為，并建立線性規劃模型估算AGV數量，然而閉排隊網模型是在系統總在制品數不變基礎上的。

本文研究的制造系統具有兩個特征：（1）隨機批量搬運，成批的物料運輸是一個批處理的過程，為減少AGV空車等待時間縮短生產周期，在AGV到達時若不能滿載也立即運往目的地，因此運輸的批量具有隨機性。（2）同等并行AGV，相同類型的AGV具有相同的性能參數（如額定速率、額定容量等），因此多臺同類型的AGV是同等的，且并行地在各個車間之間執行物料運輸任務。上述特征使得系統模型更為復雜，求解更為困難。

綜上所述，目前優化AGV 配置的規劃模型并未考慮隨機批量處理的問題，而針對具有隨機批量處理特征且緩沖區容量有限的排隊網性能分析方法也尚未見報道。因此，本文針對定制型生產方式，考慮具有隨機批量搬運和同等并行AGV的制造系統，基于Markov過程的排隊網絡理論建立系統的性能分析模型，進而求解以最小化AGV 投資成本為目標，具有系統產出率和生產周期雙重約束的AGV配置優化模型。

1 問題描述

如圖1所示，工件需要先后經過粗加工車間和精加工車間進行加工，AGV 在兩個車間的半成品緩存區之間并行地往返運輸工件。AGV具有四種狀態：裝載（含“饑餓等待”）→負載行程→卸載（含“阻塞等待”）→空載返程。（1）裝載時的饑餓等待：AGV 到達半成品緩沖區Buffer2 裝載工件時，若 Buffer2 不為空，則 AGV 即使不能滿載也立即運往半成品緩存區Buffer3；若Buffer2 為空，則AGV 需要等待直至有1 個工件在粗加工車間完工并進入Buffer2，這種狀態稱為“饑餓”（Starvation）。（2）卸載時的阻塞等待：AGV到達半成品緩存區Buffer3卸載工件時，若Buffer3 已滿而AGV 尚不能完全卸載，則AGV 需要等待直至全部工件卸載完成才能空車返回，這種狀態稱為“阻塞”（Blocking）。由于阻塞、饑餓等因素的影響降低了AGV的效率。

圖1 AGV物料搬運的制造系統

本文考慮以系統產出率和生產周期為約束的制造系統中AGV 配置的優化問題，其目標是優化AGV 數量，從而最小化AGV投資成本，同時滿足系統產能及訂單交貨期的要求。

定義參數如下：

i：AGV類型，i=1,2,…,n；

ui：第i類AGV的采購單價；

xi：第i類AGV配置的數量；

X：AGV數量配置向量，X={xi}；

Q：AGV投資成本；

Θ：系統平均產出率，即單位時間系統輸出完成品的平均數量；

Γ：系統平均生產周期，即每個工件在系統中停留的平均時間；

E{·}：隨機函數的數學期望；

ξ：隨機元。

該優化問題的數學模型如下：

式（1）表示優化目標，即求解AGV優化配置的向量X*，使得AGV 投資成本最小；式（2）表示平均產能約束，實際平均產出率不小于目標平均產出率Θmin；式（3）表示平均生產周期約束，實際平均生產周期不大于目標平均生產周期Γmax；式（4）表示X為非負整數型向量。由于E{Θ(X;ξ)}和E{Γ(X;ξ)}無法用明顯的數學函數式進行描述，無法應用傳統的非線性整數規劃方法求解。為此，針對問題的隨機性和非線性，本文提出一種基于排隊網求解系統性能指標的算法對該優化模型進行求解。

2 系統性能分析方法

目前針對物料搬運系統性能分析的模型已有大量的研究成果，采用的建模方法包括整數規劃模型、網絡流模型、排隊論模型和Markov模型等，但這些建模方法各有不足[9]。文獻[10]根據文獻[9]提出的擴展馬爾可夫鏈模型建立考慮多運輸AGV堵塞特性系統的排隊網絡模型，但其建立的均為閉環排隊網模型（即系統在制品數量為常數，系統無實時輸入流、輸出流），而且物料運輸過程中不考慮批量處理的問題。文獻[11]針對物料搬運系統建立有限緩沖區開排隊網模型，但未考慮批量搬運情形。針對具有有限緩沖區、隨機批量搬運的問題，文獻[12]考慮服務速率與批量大小相關的狀態相關排隊模型并提出一種Unifying Method 分析其性能指標，但均為針對單個隊列的模型，并不能直接應用于具有復雜拓撲結構、隊列之間存在耦合關聯的網絡系統。

人們所面臨的系統在制品數量為隨機變量且各緩沖區容量是有限的，因此采用有限緩沖區的開排隊網模型描述。有限緩沖區開排隊網模型在制造系統建模與分析中具有重要應用，與無限緩沖區的模型不同，堵塞和死鎖（Deadlock）的現象使得其不具有乘積形式的解（Product-Form Solution）[13]，因此求解難度更大。傳統的精確計算方法[13]雖然可以獲得精確解，但隨著系統規模的增大（如系統隊列數、緩存容量等）會導致狀態空間的“維數災”問題。為解決此問題，文獻[14]提出一種基于Markov過程的“狀態空間分解法”建立系統的性能分析模型，且仿真結果驗證了該方法近似結果的精確性和有效性。文獻[15]應用該分解方法以任務拒絕率為約束條件提出一種緩沖區容量配置的優化方法。

針對傳統制造系統的狀態空間分解法將整個系統按照節點（緩存區+工作中心）分解為若干個子系統，每個子系統是相對獨立的，并通過建立連續時間馬爾可夫鏈（Continuous-Time Markov Chain，CTMC）[16]模型建立子系統之間的耦合關聯。在每個子系統中，按CTMC模型分別建立描述子系統的狀態空間，并根據“生滅過程”理論分析狀態轉移規律，構建一系列的穩態平衡方程組，接著迭代求解獲得每種狀態的穩態概率，最后依據這些狀態概率值計算系統的性能指標值。與傳統的精確法對比，這在很大程度上降低了系統狀態空間的規模，因此該方法能夠求解較大規模的系統模型。基于傳統狀態空間分解法的思路，本文將其拓展，應用于含隨機批處理、同等并行AGV的制造系統建立性能分析模型。

2.1 排隊網絡模型

建立如圖2所示的有限緩沖區開排隊網模型，其中方框表示有限容量的緩存區，圓圈表示工作中心，弧線表示工件流，箭頭表示工件流向。

圖2 制造系統排隊網示意模型

該模型滿足以下假設條件：

工件到達系統的隨機過程為泊松過程，每個工件的到達是獨立的，平均到達速率為λ。

系統排隊模型為“混合制（損失、阻塞）”[17]：工件到達系統時若緩存區B1已滿，則工件被拒絕；否則進入B1，若工作站W1正在加工，則其加入隊列排隊。

每個工作站包含一臺加工設備，服務時間（含設備準備時間）服從負指數分布，W1和W4的平均加工速率分別為μ1和μ4，每個工件的加工時間是獨立的，且加工過程一旦開始就不可中斷。

緩沖區B1、B2和B4的容量是有限的，最大容量分別為N1、N2和N4。

系統服務規則為“先到先服務（FCFS）”。

系統阻塞機制為“服務后阻塞（BAS）”。

不同類型的AGV 具有不同的行駛速率，且到達B2或B4的間隔時間是獨立的，服從負指數分布，類型iAGV 的平均到達速率為Vi；AGV 行駛的平均速率為2dVi，其中d為軌道長度（即兩個車間之間的距離）。

不同類型的AGV 具有不同的裝載容量，第i類AGV的最大裝載容量為Ci。

AGV的調度規則如下：

每臺AGV 按照特定的軌道在B2或B4之間往返，即AGV之間相互獨立，沒有“堵車”現象發生。

AGV在B2裝載時服從FCFS規則，當AGV到達B2時，若B2中存在至少一個工件，AGV 裝載并立即前往B4，否則等待。

AGV在B4裝載時服從FCFS規則，若B4容量達到上限，則等待直至全部卸載并返回B2。

2.2 節點分解模型

AGV搬運批量的大小是與它的前緩存區(B2)中當前工件數有關的隨機變量。建立如圖3 所示的節點分解模型，節點1為不與AGV直接相關的節點，是傳統的“單個到達、單個離開”的模型；在B2后添加一個加工時間為0的虛擬工作站W2構成節點2，具有“單個到達、批量離開”的特征；將AGV的批處理過程視為加工速率為V的批量處理工作站V3，即節點3，具有“批量到達、批量離開”的特征；節點4 工件轉移的特征為“批量到達、單個離開”。

圖3 節點分解的排隊網模型

通過構造各個節點的狀態空間，從而建立狀態轉移平衡方程，并分析V3節點的狀態轉移建立節點2 和節點4之間的耦合關聯。

2.3 狀態轉移分析

文獻[18]證明對于k臺同等的（相同的運行速度、容量）AGV，可當量為一臺具有k倍運行速度的AGV進行分析。為簡化描述，以單臺AGV為例，建立節點3狀態空間如下：

其中，w3表示AGV運載的工件數量。b3表示AGV的狀態：b3=-1 為AGV處于“饑餓等待”狀態（此時w3=0）；b3=0 為 AGV 處于“空載返程”狀態（此時w3=0）；b3=1 為AGV 處于“負載行程”狀態（此時1 ≤w3≤C）；b3=2 為 AGV 處于“阻塞等待”狀態（此時 1 ≤w3≤C）。該節點狀態空間及狀態之間的轉移如圖4所示。

圖4 節點3的狀態轉移示意圖

根據系統的 Markov 性，當 AGV 到達B2時，B2中具有n個工件的概率均為P2(n),0 ≤n≤N2，而P2(n)是與AGV狀態無關的變量。因此，AGV從空載返程的狀態S3(0,0) 轉變為饑餓等待狀態S3(0,-1) 或者負載行程 狀態S3{(w3,1),1 ≤w3≤C} 的 概率 分 別為P3(0)load、P3(w3)load，其中：

因此AGV 狀態的轉移速率分別為VP3(0)load、VP3(w3)load。

當AGV 在B2處于饑餓等待狀態時，AGV 將轉變為負載行程狀態直至W1中加工完成的一個工件到達B2（有效到達率為，將在下一節分析），因此AGV 由狀態S3(0,-1)轉變為狀態S3(1,1)的轉移速率為。

當 AGV 到達B4時，AGV 能否卸貨取決于 AGV 當前裝載量w3和B4的當前剩余容量k。當k≥w3時，AGV 能完全卸載，因此由負載行程狀態S3{(w3,1),1 ≤w3≤C} 轉變為空載返程狀態S3(0,0) 的轉移速率為當k ＜w時，尚有w-k個工件未能33卸載，AGV 由狀態S3(w3,1) 轉變到阻塞等待狀態S3(w3-k,2)的速率為VPb4(w3)。其中Pb4(k)為B4當前剩余容量為k的概率。

當AGV 在B4處于阻塞等待狀態時，AGV 上有w3個工件尚未卸載，隨著在W4上完工的工件離開系統（有效加工速率為4），AGV 上未卸載工件逐漸減少直至全部卸載w3=0 并空載返回B2，即由狀態S3(w3,2)轉變為S3(0,0)的轉移速率為。

AGV的整個運行過程是一個“生滅過程”[16]，在每個循環中依次經歷四種狀態。系統穩態時，AGV 處于負載行程狀態或空載返程狀態的平均時間為T0=T1=V-1，處于饑餓等待狀態或阻塞等待狀態的平均等待時間為Ti=V-1×PS3(i)/PS3(0),i=-1,2，其中PS3(b3)為AGV處于各個狀態S3(w3,b3)的穩態概率。

AGV 在節點2 和節點4 裝載和卸載的過程可視為一個交錯更新過程[16]，且只在AGV 到達的更新時間點發生。對于AGV 單元前節點（節點2），AGV 由離開直至首次到達的間隔時間T2-2=T1+T2+T0內，經歷負載行程S3{(w3,1),1 ≤w3≤C}、卸載（阻塞等待）S3{(w3,2),1 ≤w3≤C}、空載返程S3(0,0)三個階段；對于AGV單元后節點（節點4），AGV由離開直至首次到達的間隔時間T4-4=T0+T-1+T2內，經歷空載返程S3(0,0)、裝載（饑餓等待）S3(0,-1)、負載行程S3{(w3,1),1 ≤w3≤C}三個階段。

根據系統Markov 過程的“生滅過程”理論，對每個狀態可列出對應的一個狀態轉移平衡方程，因此各節點可列出與其狀態總數一致的狀態轉移平衡方程組。以狀態S3(0,0)為例，輸入的狀態為S3(w3,1)和S3(1,2)，對應的轉移速率分別為輸出的速率為因此，根據輸入與輸出狀態轉移平衡可以建立如下方程組：

同理，節點3共有2(C+1)個狀態，針對其他狀態建立的轉移平衡方程組如下：

對于節點m=1,2,3,4，由其狀態轉移平衡方程組中未知變量（即各狀態穩態概率）PSm(wm,bm)的系數可構成大型稀疏矩陣πm,因此只要求解齊次線性方程組πm xm=0就可獲得各狀態的穩態概率值。本文應用Gauss-Seidel迭代法[13]迭代求解各節點方程組πm xm=0，由于節點間的耦合關聯，當前節點的轉移速率參數可由其關聯節點在上一次迭代的結果計算得出。在迭代過程收斂后，最終可獲得系統各狀態的穩態概率值PSm(wm,bm)，據此可計算系統性能指標值：平均產出率和生產周期。

3 AGV配置優化算法

優化問題是一個隨機非線性整數規劃問題，而且約束函數無法用一個封閉的數學方程式表達，因此在滿足預設系統產能（輸出率）和產品交貨期（生產周期）的情況下，采用嵌入排隊網模型的禁忌搜索算法優化AGV的配置方案，其算法流程圖如圖5所示。

步驟1初始化

采用二進制編碼，由變量松弛法獲取初值。

步驟2解空間搜索

圖5 禁忌搜索算法流程圖

步驟2.1采用隨機選擇兩個編碼的位轉變為相反值的擾動策略，產生新解。

步驟2.2調用排隊網模型求解系統性能指標值，判斷是否滿足約束條件，若滿足，則進入步驟2.3；否則返回步驟2.1。

步驟2.3通過擾動策略產生多個不同的解，并從中選擇最優的解，一旦該操作所得的解被選擇，禁止其執行動作的相關操作。

步驟2.4檢索是否破禁：當該被禁操作處于被禁準則，但其值所得的目標函數優于歷史最優解，則接受該動作執行破禁操作，并更新最優解記錄。

步驟3終止判斷

判斷是否滿足終止準則（最高擾動次數），若滿足，則當前解為最終解；否則返回步驟2.1。

4 算例分析

對于算例求解的操作系統環境為Microsoft Win10，硬件環境為CPU 3.30 GHz，4.00 GB RAM，對于解析算法的求解采用Matlab R2018a軟件平臺編程實現。

4.1 仿真實驗

如圖6 所示為在Tecnomatix Plant Simulation 8.2上建立的仿真模型示例。基于離散事件仿真理論，在大樣本的條件下，構造統計估計量（系統平均產出率和平均生產周期）并計算采集的數據樣本。仿真實驗每次運行1 000天（仿真時間），并在95%的置信度下進行50次獨立重復實驗，最終計算系統性能指標的均值。

4.2 實驗算例及結果分析

為驗證本文提出近似解法的有效性，并分析AGV配置參數對系統性能指標的影響及規律，本文設計實驗方案進行求解，并將結果與仿真實驗進行對比分析。

設計自變量（影響因素）如下：小車到達速率V；小車容量C；小車數量n。

設計因變量（實驗指標）如下：系統產出率Θ；系統生產周期Γ。

圍繞實驗目標問題，針對不同因素設計3組單因素實驗和1 組雙因素實驗，具體參數如表1 所示。各組實驗算例求解結果如表2 所示，其中“Δ/%”為近似結果相對仿真結果的偏差百分比。與仿真結果對比，本文改進的狀態空間分解法對于計算系統平均產出率的偏差率均在±3%內，計算系統平均生產周期的偏差率均在±6%內，并且每次計算所需的時間遠遠小于仿真所需耗時。因此，可以看出本文近似方法對于系統性能的分析和計算具有良好的適應性。

表1 實驗方案的系統參數

圖6 系統仿真模型示例

表2 算例求解結果

如圖7 所示為各組實驗中因變量隨自變量的變化規律曲線，由實驗結果可以看出：（A）單獨增加AGV 的運載速率，系統平均產出率略有提高，而系統平均生產周期則有明顯的縮短；（B）單獨增加AGV 的運載容量，系統平均產出率略有提高，而系統平均生產周期也有略微的縮短；（C）增加同等并行AGV 的數量，系統平均產出率略有提高，而系統平均生產周期則有明顯的縮短；（D）保持AGV的當量運載能力（=AGV運載速率×AGV運載容量）不變的情況下，隨著AGV運載速率的提高和AGV運載容量的降低，系統平均產出率有明顯的提高，而系統平均生產周期也有明顯的縮短。

圖7 因變量隨自變量變化規律

對于AGV 配置參數的單因素實驗（A）～（C），增加AGV 的運載速率或數量，則在制品運輸環節的服務速率增大，即在制品的運輸時間減少，因此系統產出率增大，而生產周期減少。增加AGV的運載容量，可能增加AGV 每次運輸的在制品數量，減少每個在制品的平均運輸時間，但是這也可能會提高AGV 在卸載在制品時“阻塞等待”的概率，因此運載容量的變化對系統性能的影響并不顯著。對于AGV運載速率和運載容量的雙因素實驗（D），當量運載能力不變時，提高AGV 速率并減少運載容量，增大了AGV 在運輸過程中保持滿載的概率，AGV 每次運輸的時間縮短，從而AGV 的實際運載能力會有提高，因此系統產出率得以提高，同時縮短了生產周期。

綜上所述，合理地配置AGV的數量等參數，可以有效地提高系統產出率并且縮短生產周期。

4.3 優化案例

以圖1所示的某裝備制造企業生產系統為例，為了在兩個車間之間配置AGV 執行物料運輸任務，需要確定AGV配置的最優方案。兩個車間的距離為d=100 m，如表3 所示，有三種類型的AGV 可供選擇。系統產能及訂單交貨期的約束為：系統產出率不低于Θmin=0.95個/min，而生產周期不超過Γmax=18 min。根據主生產計劃的任務投放速率為λ=1.0個/min，兩個車間的平均加工速率分別為μ1=1.1個/min 和μ4=1.2個/min。

表3 三類AGV的性能參數

根據嵌入排隊網模型的禁忌搜索算法求得算例優化的結果如表4 所示，其中標記“*”的方案為最優配置方案。由于問題規模較小，可以通過枚舉搜索的方法獲得全局最優解，即逐一增加每類AGV的數量，計算系統性能指標值并判斷是否滿足約束條件，最后從所有可行解中選擇成本最低的為最優解，求解過程的系統性能參數變化曲線如圖8 所示。由表4 和圖8 的結果可以看出，禁忌搜索算法獲得的最優解與枚舉搜索獲得的全局最優解一致，驗證了禁忌搜索方法的有效性。基于系統產出率和生產周期的約束，以最小化AGV 投資成本為目標，配置4臺類型II的AGV為該目標下的最優配置方案，以滿足系統產能及訂單交貨期的要求。另外，表4中與仿真結果的相對偏差率進一步驗證了改進狀態空間分解法的有效性及精確性。由此可以看出本文所提出的求解系統性能指標值及AGV配置優化算法的合理性及有效性，這種方法可以推廣到較大規模的系統分析及資源優化配置中。

表4 算例優化結果

圖8 優化過程中系統性能的變化曲線

5 結束語

本文建立了隨機非線性整數規劃模型，描述了智能車間物料搬運系統的AGV數量配置問題。針對具有隨機批量搬運的生產系統，建立有限緩沖區開排隊網模型，并拓展狀態空間分解法計算系統性能指標值，最后將其嵌入禁忌搜索算法，求解AGV配置優化問題。

通過算例求解及結果分析，與仿真結果對比，拓展的狀態空間分解法計算系統性能指標值具有較高的精確度，基于該方法求解性能指標值的優化算法可以獲得合理的AGV配置最優方案。因此這種方法可以應用于求解較大規模的系統資源優化配置問題。