基于閉合排隊網(wǎng)絡(luò)擴展求和算法的露天礦車鏟協(xié)同優(yōu)化研究

趙加征 李 寧，2 葉海旺，2 王李管 王其洲，2 雷 濤，2

（1.武漢理工大學資源與環(huán)境工程學院，湖北武漢430070；2.礦物資源加工與環(huán)境湖北省重點實驗室，湖北武漢430070；3.中南大學資源與安全工程學院，湖南長沙410083）

露天開采具有基建時間短、生產(chǎn)能力大、開采成本低、作業(yè)安全性高等優(yōu)點，在現(xiàn)代礦業(yè)開發(fā)利用過程中得到了廣泛應用［1］。由于汽車運輸具有調(diào)度方便、適應范圍廣等優(yōu)點，是目前露天開采的主要運輸方式。據(jù)統(tǒng)計［2］，露天開采運輸作業(yè)成本約占礦石開采總生產(chǎn)成本的60%，極大影響著礦山企業(yè)的經(jīng)濟效益。因此，在滿足礦山生產(chǎn)能力的條件下，有效減少運輸車輛的等待時間，確定車鏟最優(yōu)配比，提高汽車運輸效率，對于提升礦山經(jīng)濟效益具有重要意義。

排隊論是研究服務(wù)過程中排隊現(xiàn)象的一種數(shù)學理論，也稱為隨機服務(wù)系統(tǒng)理論［3］。排隊理論能夠從系統(tǒng)整體角度描述作業(yè)過程，在很多領(lǐng)域得到了應用［4-9］。近年來，大量學者利用排隊理論研究并分析了露天礦運輸作業(yè)過程的排隊現(xiàn)象。高景俊等［10］應用排隊論中的有限隊列模型優(yōu)化了排巖系統(tǒng)的工藝流程，結(jié)合生產(chǎn)實際情況來控制車鏟合理調(diào)配。俞雄志［11］采用排隊理論確定車鏟比，并比較了不同車鏟配比之間經(jīng)濟效益的差異性。Ercelebi 等［12］采用閉式排隊網(wǎng)絡(luò)理論對卡車進行了分配，基于線性規(guī)劃實現(xiàn)了汽車的運行調(diào)度，并分析了運輸作業(yè)中卡車數(shù)量與最優(yōu)調(diào)度策略對成本的影響。Ta 等［13］為確定裝載機組的最少卡車數(shù)量，以吞吐量及礦石品位為約束，基于有限源隊列理論，建立了油砂露天礦排隊模型，跟據(jù)裝載機閑置概率與卡車數(shù)量之間的關(guān)系，建立了卡車分配模型來解決實際問題。

上述研究大多假設(shè)作業(yè)時間服從負指數(shù)函數(shù)分布，采裝過程僅考慮單臺裝載設(shè)備。然而實際生產(chǎn)中只有卸礦作業(yè)時間服從負指數(shù)函數(shù)分布［14-15］，裝車時間基于負指數(shù)函數(shù)分布的假設(shè)可能會導致計算結(jié)果與實際情況產(chǎn)生較大差異［16］，不同排隊模型也會影響卡車等待時間［17］。礦山在同一工作平臺一般具有多個裝載點，運輸汽車數(shù)量需根據(jù)作業(yè)計劃進行選擇。為研究多鏟車、作業(yè)時間服從一般函數(shù)分布的情形，引入閉合排隊網(wǎng)絡(luò)擴展求和算法計算礦山生產(chǎn)處于穩(wěn)定狀態(tài)時各系統(tǒng)的運行指標。

1 閉合排隊網(wǎng)絡(luò)擴展求和算法

求和算法（Summation Algorithm，SUM）是一種分析計算服務(wù)時間呈負指數(shù)函數(shù)分布排隊網(wǎng)絡(luò)的近似算法，在此基礎(chǔ)上改進得到的擴展求和算法（Extended SUM，ESUM），可以有效解決服務(wù)時間為一般函數(shù)分布的排隊網(wǎng)絡(luò)問題［18］。

1.1 ESUM計算原理

假設(shè)某閉合排隊網(wǎng)絡(luò)中有N個服務(wù)點，第i個服務(wù)點（1 ≤i≤N）有mi個相同的服務(wù)臺，此閉合排隊網(wǎng)絡(luò)中顧客總數(shù)為K。閉合排隊網(wǎng)絡(luò)處于穩(wěn)定時，有如下關(guān)系成立：①各服務(wù)點的平均排隊長度與該服務(wù)點流量有關(guān)；②各服務(wù)點內(nèi)平均排隊長度之和與閉合網(wǎng)絡(luò)內(nèi)顧客總數(shù)相同。

第一類關(guān)系可表述為

SUM將服務(wù)點分為4類，如表1所示。

注：m表示該服務(wù)點共有m個服務(wù)臺；∞表示該服務(wù)點存在無數(shù)個服務(wù)臺。

根據(jù)上述分類，有下式成立：

式中，m i為第i個結(jié)點處包含的相同服務(wù)臺數(shù)量；ρi為第i個服務(wù)點的服務(wù)強度；Pmi為表 1 中 Type1 型系統(tǒng)中全部服務(wù)臺都被占用的概率。

第二類關(guān)系可表述為

式（1）、式（3）構(gòu)成了SUM算法的基礎(chǔ)。

在ESUM 中，Type1 的服務(wù)時間函數(shù)分布由負指數(shù)分布擴展到一般分布，引入系數(shù)ai對式（2）進行修正：

對于 M/G/1-FCFS 和 M/G/m-FCFS 型服務(wù)點，平均排隊長度分別為

ESUM算法的迭代步驟為：

（1）以λ1= 0 為流量下限，λμ= min{μi,mi} 為流量上限。對于-/G/∞型服務(wù)點，mi=K。

（3）若g(λ)＞K，令λμ=λ，若g(λ)＜K，令λ1=λ，重復步驟（2）；若(K-ε)≤g(λ)≤(K+ε)（ε是一個很小的數(shù)，表示計算精度），則停止計算。利用滿足要求的流量λ，便可分析閉合網(wǎng)絡(luò)中各服務(wù)點的運行指標。

1.2 改進ESUM算法

1.2.1 誤差分析

礦山在實際生產(chǎn)過程中由于閉合網(wǎng)絡(luò)中總卡車數(shù)量為定值，不存在無容量約束的情形，即最大排隊長度應為卡車總數(shù)，而ESUM 算法是基于無限容量等待過程得到閉合排隊網(wǎng)絡(luò)的近似公式，無容量約束下可能會出現(xiàn)排隊長度大于卡車總數(shù)的情形。利用Matlab 軟件對文獻［19］中卡車總數(shù)為5 輛時的流量進行隨機模擬，模擬時間為500 min，在無容量限制情況下采裝過程排隊長度隨時間的變化關(guān)系如圖1 所示。由圖1可以看出，卡車在采裝系統(tǒng)中長度最高為8 輛，且有多次超過卡車實際總數(shù)5 輛。在無容量約束時，鏟車處的排隊長度會變大，導致閉合排隊網(wǎng)絡(luò)整體流量λ變小，導致直接應用式（5）、式（6）計算會產(chǎn)生較大誤差。因此，采用有限容量的等待過程對ESUM算法進行改進，更符合礦山實際情況。

1.2.2 算法改進

礦山閉合網(wǎng)絡(luò)模型中，卡車總數(shù)不變，當所有卡車都在同一服務(wù)點時，將后續(xù)卡車看作損失，沒有加入排隊過程，等待制排隊模型變?yōu)榛旌现婆抨犇Ｐ?，利用此時的系統(tǒng)排隊長度改進式（5）、式（6）確定模型表達式，即：

式中，bi為修正系數(shù)。

服務(wù)點多服務(wù)臺與單服務(wù)臺的差異，僅僅表現(xiàn)為卡車被鏟車服務(wù)的隨機性不同。鑒于多服務(wù)臺情形的公式［3］過于復雜，因此本研究選用單服務(wù)臺的情形進行近似分析。單服務(wù)臺混合制排隊模型M/M/1/N 和單服務(wù)臺等待制排隊模型M/M/1 的系統(tǒng)排隊長度公式分別為

式中，N為排隊容量；ρ為服務(wù)強度。

由式（9）、式（10）可得：

當ρ取值分別為 0．4, 0．5,0．6,0．7 時，h隨卡車數(shù)量的變化情況如圖2所示。

由圖2 可知：隨著卡車數(shù)量逐漸增大，M/M/1 模型和M/M/1/N 模型的比值越來越接近1，即當卡車數(shù)量無限大時，兩種模型無差異。在ESUM 算法中，閉合網(wǎng)絡(luò)中流量大小與卡車總數(shù)成正比，且ρi=λiμi，由此定義bi：①bi為ρi的函數(shù)，且當ρi= 0時，bi= 0；當ρi= 1 時，bi= 1；②bi為單調(diào)遞增函數(shù)，且增長率逐漸減小。為簡化公式，選常用函數(shù)，取。

1.2.3 方法驗證

利用改進ESUM 算法對某礦山生產(chǎn)過程的隨機模擬實例［20］進行分析，假設(shè)該露天礦山有1 臺電鏟，若干輛卡車，卸載場地有1 個卸礦車位，可供1 輛卡車進行卸車作業(yè)。計算機模擬基礎(chǔ)數(shù)據(jù)為：裝載時間服從正態(tài)分布，其均值為1.32 min，方差為0.072 9；重車運行時間服從定長分布，其均值為4 min；卸車服務(wù)時間服從負指數(shù)分布，均值為0.74 min；空車運行時間為定長3.67 min；每輛卡車裝載量均值為22.5 t；每班工作時間為6 h。

針對卡車總數(shù)K= 5,6,…,11 的情形，分別采用改進的ESUM 算法對上述實例的閉合網(wǎng)絡(luò)進行分析計算，并與原始算法的計算結(jié)果對比，如表2 所示。改進后的班生產(chǎn)能力與計算機模擬得到的生產(chǎn)能力差異在3%以內(nèi)，精度相較之前明顯提高。卡車總數(shù)在11 輛時的誤差較大，主要是由于修正函數(shù)bi后期與函數(shù)h不完全符合，不過隨著后期卡車數(shù)量增多，出現(xiàn)排隊現(xiàn)象越明顯，對于車鏟協(xié)同不利，在實際優(yōu)化時不會考慮此類數(shù)據(jù)，因此利用改進的ESUM 算法進行車鏟協(xié)同優(yōu)化具有可行性。

2 工程應用

2.1 礦山閉合排隊網(wǎng)絡(luò)模型

某年產(chǎn)280萬t的露天石灰石礦山為滿足生產(chǎn)需求，每天需連續(xù)工作兩班共計16 h，平均班產(chǎn)量4 667 t。礦山現(xiàn)有單斗挖掘機3臺，運輸卡車12輛，其中11輛常用。礦山運輸路徑中段有一段單車道，并且卸礦前需要稱重。實際生產(chǎn)中，在采裝過程中極易排隊等待現(xiàn)象。因此，有必要對車鏟協(xié)同進行優(yōu)化，減少卡車在采裝過程中的等待時間，提高卡車利用效率。

依據(jù)閉合排隊網(wǎng)絡(luò)理論，將該礦山作業(yè)過程抽象為采裝、重車運行、單車道、稱重、卸礦、空車運行等系統(tǒng)，如圖3所示。

2.2 排隊網(wǎng)絡(luò)分析

（1）采裝系統(tǒng)。采裝過程中，3 臺單斗挖掘機在同一工作平臺進行工作，卡車到達后可以自由選擇空閑的挖掘機，當3 臺挖掘機都被占用時，后來的卡車排列成一隊等待。以人工計時方式對裝車時間進行統(tǒng)計并利用Matlab 軟件進行數(shù)據(jù)分析，結(jié)果顯示，未通過K-S 檢驗，即裝車時間不符合負指數(shù)分布；數(shù)據(jù)通過J-B正態(tài)分布擬合檢驗，裝車時間經(jīng)驗分布函數(shù)如圖4所示，置信度為95%。由圖4可以看出，數(shù)據(jù)基本符合正態(tài)分布，因此，本研究將采裝過程視為3個服務(wù)臺的M/G/3 型排隊系統(tǒng)，裝車時間均值為7.298 4 min，標準差為1.404 2 min。

（2）重車運行系統(tǒng)。將礦山公路視為無限個服務(wù)臺，即卡車在公路行駛時無需等待。為簡化排隊模型，將兩段重車運行合成一段完整的運行路徑，重車運行時間符合均值為2.6 min 的定長分布，此系統(tǒng)屬M/G/∞型。

（3）單車道系統(tǒng)。在行駛路徑中間部分的單車道，只允許單向通過。車輛在啟動加速階段時所用時間較長，在平穩(wěn)路段運行時可以認為是勻速運動。該部分可以雙向通行，此系統(tǒng)的流量應為2λ，通行時間為定值0.5 min，屬于M/G/1型排隊系統(tǒng)。

（4）稱重系統(tǒng)。卡車經(jīng)過重車運行后，在卸礦前需先進行稱重。礦山目前有1臺地磅，稱重過程耗時均值為0.5 min，據(jù)以往經(jīng)驗［15］，稱重時間服從負指數(shù)分布，此系統(tǒng)屬于M/M/1型。

（5）卸礦系統(tǒng)。該礦山目前只有1 個卸礦點，可允許2 輛卡車同時進行卸礦作業(yè)，即系統(tǒng)內(nèi)有2 個服務(wù)臺，卸礦時間服從均值為2 min 的負指數(shù)分布，此系統(tǒng)屬于M/M/2型。

（6）空車運行系統(tǒng)。與重車運行類似，可以將該系統(tǒng)視為含有無數(shù)個服務(wù)臺的服務(wù)點，服務(wù)時間定長分布的M/G/∞型排隊系統(tǒng)?？哲囘\行時間均值為2 min，其中不包括在單車道的運行時間。

卡車在此礦山閉合網(wǎng)絡(luò)模型中循環(huán)經(jīng)過6 級服務(wù)系統(tǒng)，根據(jù)各系統(tǒng)排隊類型，選用相應公式，即可求解出閉合網(wǎng)絡(luò)處于穩(wěn)態(tài)時各服務(wù)點的運行指標。

2.3 改進ESUM模型計算結(jié)果

2.3.1 閉合排隊網(wǎng)絡(luò)各節(jié)點分析

用改進ESUM 算法求解該礦山閉合排隊網(wǎng)絡(luò)模型中K= 4,5,…,14 的近似解，計算精度取ε= 0．001，結(jié)果如表3所示。

當K為 6～14 時，增加的 8 輛卡車有 7 輛在采裝系統(tǒng)中，說明這些卡車以排隊等待的形式加入到網(wǎng)絡(luò)中。隨著卡車數(shù)量增加，λ值明顯變大，不過其增長率逐漸減小。由圖5 可知：λ值會趨近于采裝過程極限服務(wù)能力，即采裝過程容易成為限制整個閉合排隊網(wǎng)絡(luò)流量增加的節(jié)點，因此需要對采裝過程的排隊指標進行精確分析。

2.3.2 采裝過程分析

假設(shè)卡車以恒定到達率到達采裝點，卡車裝載量均值為30 t，計算每班生產(chǎn)能力并依據(jù)Little公式［3］計算各到達率對應的平均逗留時間，結(jié)果如表4 所示。當卡車數(shù)量為4、5時，卡車在采裝系統(tǒng)平均逗留時間較少，但此時該系統(tǒng)中的平均卡車數(shù)小于3 輛，即單斗挖掘機可能會存在空閑時間過長的情況?？ㄜ嚳倲?shù)為6 時，單斗挖掘機在平均意義上無空閑，卡車逗留時間也較短，同時滿足平均班產(chǎn)量目標，此時車鏟協(xié)同效果較優(yōu)?？紤]到實際生產(chǎn)過程存在其他未考慮的因素，因此卡車總數(shù)為7輛比較適宜?？ㄜ嚁?shù)量從原先的11 輛減少至7 輛時，卡車在采裝過程的逗留時間縮短了42.24%，班生產(chǎn)能力只減少了7.86%。

2.4 隨機模擬驗證

利用Matlab軟件模擬采裝系統(tǒng)的排隊過程，以驗證采用改進ESUM 算法確定卡車數(shù)量的合理性，當兩者在采裝系統(tǒng)的數(shù)量一致或相差不大時，可以認為改進ESUM 算法有效。模擬過程需要進行有效性檢驗，一般情況下排隊過程達到穩(wěn)定時的排隊指標可以通過理論推導得到，但M/G/m/N排隊模型用數(shù)學推導異常困難，M/M/m模型與M/G/m模型的仿真模擬差異只是生成服務(wù)時間隨機數(shù)的函數(shù)不同，可以轉(zhuǎn)化成為M/M/m/N 排隊模型進行驗證［21］。本研究根據(jù)實例［3］分析該隨機模擬的準確性。

設(shè)計算機有5 個終端，用機時間服從負指數(shù)分布，為15 min；顧客到達符合泊松流，平均0.2 個/min；5 個終端全被使用時，后續(xù)顧客只能前往別處。根據(jù)排隊論公式計算上述示例，系統(tǒng)平均排隊長度為2.669 7個，平均逗留時間為15 min。采用上述模擬方法模擬多次發(fā)現(xiàn)，系統(tǒng)平均排隊長度為2.76 個，平均逗留時間為15.59 min，可以證明該模擬有效。

運用上述模擬方法對改進ESUM 算法的計算結(jié)果進行驗證，當卡車總數(shù)為6 輛時，分別模擬10 次采裝過程，模擬時間均為500 min，結(jié)果如表5所示，某次排隊長度隨時間的變化特征如圖6 所示。10 次隨機模擬中采裝系統(tǒng)平均排隊長度的平均值為3.204 8，改進ESUM 算法的計算值為3.383 9，可以認為由改進ESUM算法計算得到的卡車數(shù)量較準確。由圖6可以直觀看出，卡車數(shù)量保持在3輛時次數(shù)較多。

3 結(jié) 論

根據(jù)實際情況建立了某露天礦生產(chǎn)的閉合排隊網(wǎng)絡(luò)模型，將該礦山流程簡化為采裝、重車運行、單車道、稱重、卸礦和空車運行等系統(tǒng)節(jié)點，研究得到如下結(jié)論：

（1）引入閉合排隊網(wǎng)絡(luò)擴展求和算法，計算穩(wěn)態(tài)時該礦山各系統(tǒng)節(jié)點的運行指標，得到采裝過程是制約該礦山生產(chǎn)的瓶頸環(huán)節(jié)。

（2）以卡車等待時間少并滿足平均班產(chǎn)量為目標，確定該礦山合理的卡車數(shù)量為7 輛，卡車在采裝過程中的逗留時間較未優(yōu)化前縮短了42.24%。

（3）利用仿真模擬驗證了閉合排隊網(wǎng)絡(luò)擴展求和算法在該礦山應用的可行性，結(jié)果表明，采用此方法進行車鏟協(xié)同優(yōu)化簡單有效。