露天煤礦車輛的不確定調度模型與優化求解

薛雪，孫偉，劉曉文

（中國礦業大學 信電學院，江蘇 徐州，221008）

露天煤礦車輛的不確定調度模型與優化求解

薛雪，孫偉，劉曉文

（中國礦業大學 信電學院，江蘇 徐州，221008）

以內蒙古一露天煤礦為研究對象，對露天礦車輛調度過程中的關鍵時間參數進行統計分析，確定其隨機性，建立車輛調度的不確定模型。在對不確定調度模型優化分析的過程中，訓練神經網絡逼近函數，對于粒子群算法容易陷入局部收斂的缺陷，結合模擬退火算法的局部搜索技術，得到模擬退火算法和粒子群算法相結合的混合智能算法。計算實驗結果證明該算法的有效性和優越性。

不確定調度；車輛調度；粒子群算法；模擬退火算法；混合智能算法

車輛調度問題（VRP）是廣泛應用于交通運輸、物流配送等領域的一類組合優化問題，而在車輛實際的服務過程中，總會遇到這樣或那樣的不確定信息，必須根據一定的準則對已安排好的車輛路徑進行及時調整更新。在這種情況下，確定型VRP的理論和方法不再具有處理這些問題的能力，需要研究一整套新的與確定型VRP相對應的不確定信息VRP理論和方法。目前對于不確定車輛調度的研究主要集中在隨機VRP和模糊VRP方面，基本上都是采用啟發式算法進行求解。如陸琳等[1]運用一種新型的混合粒子群算法，康喜兵等[2]應用禁忌搜索算法，陳寶文等[3]運用蟻群算法、宋遠清等[4]應用遺傳算法求解隨機需求車輛路徑問題。張楊等[5]對隨機旅行時間車輛路徑問題進行了研究；婁山佐[6]針對多庫房隨機車輛路徑問題，設計一個自適應交叉熵法解決子系統隨機VRP；駱正山等[7]應用一種基于模糊可能性的混合遺傳算法求解模糊需求VRP；甘勤濤等[8]運用禁忌搜索算法求解模糊需求VRP；Zheng等[9]運用一種混合智能算法求解車輛模糊旅行時間FVRP問題；張建勇等[10]]對模糊預約時間FVRP問題進行了研究。而對于露天煤礦車輛調度問題，目前主要還是通過建立具有嚴格約束的數學模型，采用精確的求解算法來解決。但是，由于露天煤礦車輛調度模型的復雜性，很多計算參數很難確定，模型的建立和求解的結果有時不能符合實際需求，這就給不確定優化提供了空間[11?13]。目前，對于露天煤礦車輛調度的不確定優化研究較少，因此，研究露天煤礦車輛調度不確定優化有很重要的理論意義。在此，本文作者以內蒙古一露天煤礦為例，對車輛調度過程中的關鍵時間參數進行統計分析，確定其隨機性，在確定型模型的基礎上，建立車輛的不確定調度模型——隨機期望值模型。對于該模型的求解，通過訓練神經網絡逼近不確定函數，并且針對粒子群算法容易陷入局部收斂的缺陷，結合模擬退火算法的局部搜索策略，經過仿真證明這種混合智能算法提高了全局收斂性，得到了較滿意的結果。

1 問題的提出

以內蒙古某一露天煤礦達產時期運輸系統為例[13]，對車輛調度系統建立模型并求解。該礦主要開采中、上兩層煤，設計能力為100萬t/a，采用國產4.6 m3斗容的單斗挖掘機和蘇制42 t貝拉斯汽車。該礦有8個鏟位，包括6個裝巖點、2個裝煤點；3個卸點，包括2個排土場、1個煤轉站。剝離電鏟6臺，采煤電鏟2臺，電鏟容量4.6 m3，現有容量為42 t的卡車51臺，班出動率0.55。卸煤時間1.5 min，卸巖時間1.0 min。露天礦生產實行三班制，每班8 h，除去吃飯、休息和換班的時間，班純工作時間為6 h。剝離電鏟1個班內的最大產量為960 m3，采煤電鏟1個班次內的最大產量為1 290 t，剝采比：4.6 m3/t。

采用完成生產任務的條件下，出動卡車數最少為目標函數的車流規劃模型[13]。將確定車輛調度模型描述如下：

式中：Nt為實動卡車臺數；Tij為從卸載點i到裝載點j路徑上的空運時間；Lij為從卸載點i到裝載點j路徑上的裝載時間；Qij為從卸載點i到裝載點j路徑上的等裝時間；Xij為從卸載點i到裝載點j路徑上的空車流量，單位為車/min；m和n分別為卸載點數和裝載點數。約束條件如下。

式中：Rj為第j個電鏟最大生產能力；Di為第i個卸礦點最大卸載速率，單位為車/min；?V為允許的剝離產量波動量，單位為m3/min；Po為卡車載礦容量，單位為t；Pw為卡車載巖容量，單位為m3；Sr為生產剝采比，單位為m3/t；m1和n1分別為卸載巖石點數和裝載巖石點數。

約束條件中，式（2）和式（3）是車流連續性約束，保證各裝（卸）載點的流入與流出車流量相等；式（4）是電鏟采裝能力約束，保證采掘速率不超過其最大生產能力；式（5）是卸礦點處理能力約束，保證卸載速率不超過最大處理能力；式（6）是生產剝采比約束，用于平衡生產；式（7）是非負約束。

2 露天煤礦車輛調度不確定模型的建立

2.1 露天煤礦車輛調度不確定信息統計分析

露天煤礦生產系統龐大且復雜，運輸環節也包含很多方面，實際上，運輸中存在許多不確定因素，如道路運行時間、裝載點產量、卸載點產量、剝采比等。露天礦車輛調度中有3個關鍵的時間參數，即道路運行時間、電鏟裝車時間和卸點卸車時間。掌握準確的道路運行時間、電鏟裝車時間和卸點卸車時間，是車輛調度中車流規劃的基礎。王強等[14]對這3個主要時間參數的概率分布進行了分析，分析結果為：道路運行時間符合正態分布；電鏟裝車時間的分布相對復雜，符合對數正態分布、對數邏輯分布、逆高斯分布；卸點卸車時間比較穩定，可近似看作1個常數。

本文對卸點卸車時間不進行進一步分析，直接使用歷史經驗數據，而對道路運行時間和電鏟裝車時間進行數據采集，并對數據進行分布擬合，求得其分布函數。

2.1.1 裝車時間隨機性統計

電鏟裝車時間是指從卡車進入裝車區域開始到電鏟裝載完畢卡車離開裝車區域為止所需時間。其中，裝車時間包括電鏟裝車時間和待裝時間，當然也包括調車時間，在這種意義上說，統計裝車時間，更符合現場數據需求，也更方便。

露天煤礦中有采煤電鏟和剝離電鏟，采煤和剝離工作有所區別，并且由于煤礦和巖石的塊度以及松散度不同，所以電鏟裝載煤礦和巖石的時間就有所差別，其裝車時間是不同的。該礦有2臺采煤電鏟，6臺剝離電鏟，本文對兩種電鏟裝車時間數據分開采集，并分開進行處理。在現場，分別對剝離電鏟的裝車時間和采煤電鏟的裝車時間，進行1個班次內的統計，對統計數據處理以后，各取出100個數據，剝離電鏟的裝車時間（min）為：6.58，7.28，7.71，6.76，9.70，8.17，7.56，8.00，6.68，8.16，6.73，8.49，7.25，7.81，7.26，6.51，6.88，7.00，8.51，9.10，7.90，8.37，8.43，7.97，7.67，6.55，7.85，6.00，6.71，7.37，6.06，9.29，8.15，7.81，7.52，7.56，6.22，7.73，7.00，7.28，7.14，6.24，6.19，6.77，6.45，7.00，7.32，8.42，7.26，7.08，7.34，6.48，6.20，6.96，6.33，7.32，6.63，7.15，6.85，7.78，7.32，7.26，5.84，7.08，7.44，6.48，8.31，7.15，7.36，6.04，7.10，6.80，8.10，8.10，6.26，7.41，8.69，6.67，6.56，6.83，10.15，7.87，6.98，5.50，6.73，7.52，5.80，6.70，6.41，6.96，9.40，8.25，6.21，6.88，7.92，7.10，7.24，7.73，7.77，6.50。

對裝車時間數據只用對數邏輯分布、逆高斯分布和對數正態分布進行擬合，擬合結果如圖1所示。由于對數正態分布曲線和逆高斯擬合曲線基本一致，所以在圖中看來是重合的。通過擬合發現：剝離電鏟裝車時間服從對數正態分布或逆高斯分布。經計算，該分布的均值（期望）為7.28，方差為0.872，為方便描述，用LN（7.28, 0.872）表示該分布。

接著，對采煤電鏟裝車時間數據也進行如上分布擬合，同樣取100個數據，由于篇幅有限，所取數據在此沒有列出。擬合結果顯示，采煤電鏟裝車時間服從期望為8.75、方差為1.062的對數正態分布，即LN（8.75,1.062）。

2.1.2 道路運行時間隨機性統計

圖1 剝離電鏟裝車時間分布擬合Fig.1 Distribution fitting of loading time of stripper shovel

鑒于數據量比較大，重車運行時間的統計結果沒有列出，直接把數據放在MATLAB中進行擬合，對其他每個重車運行時間都進行同樣處理，求出分布參數，如表1所示。

表1 重車運行時間Table 1 Travel time of laden trucks min

2.2 露天煤礦車輛調度不確定模型

作為不確定優化的一種類型，根據不同的決策準則，隨機規劃可分為期望值、機會約束規劃和相關機會規劃這3種基本模型[15]。由于露天煤礦車輛調度該模型中，隨機參數只存在于目標函數中，所以，采用隨機期望值模型。

對于優化問題中出現的不確定變量，相應地都有該變量的數學期望的概念。基于此，建模方法是在期望約束成立下極大化這些不確定目標函數的數學期望即期望值模型，其一般形式如下：

其中：x為決策向量；ξ為隨機變量；f（x,ξ）表示目標函數；gi（x,ξ）表示隨機約束函數；E表示期望值算子。

在實際的露天煤礦車輛調度建模過程中，根據式（8）的一般期望值模型，結合式（1）的確定型模型，目標函數仍采用班車輛出動最少的模型，可以得到不確定模型——隨機期望值約束模型如下：

在目標函數中，E為期望算子，Xij和Yji為決策變量，Tij和Dji為確定性參數，Lij和Tji為隨機時間參數變量。由于目標函數中含有不確定變量，所以，將出動車輛的期望值最小作為目標函數。

由于約束條件均不包含不確定變量，所以，約束條件不變，見式（2）～（7）。另外，規定巖石卸載時間為1.0 min，卸煤的時間為1.5 min。

把2.1節求得的參數的概率分布代入，得到具體的不確定模型如下：

其中：X為空車流量；Y為重車流量；L1為剝離電鏟的裝車時間；L2為采煤電鏟的裝車時間；T為相應的重車運行時間。

3 露天煤礦車輛調度不確定模型的求解

近年來，粒子群算法在車輛調度方面得到了廣泛的應用。因此，對于所建立的露天煤礦車輛的不確定調度模型，首先訓練神經網絡逼近不確定函數，接著采用粒子群算法進行優化，并且針對粒子群算法容易陷入局部最優的缺陷，結合模擬退火算法局部搜索策略，提出一種混合智能策略。

3.1 策略思想

粒子群算法因其計算簡單、參數設置少和良好的算法收斂性，已被廣泛應用于各個領域。但是，在應用過程中，人們發現粒子群算法也具有隨機搜索算法比較普遍的缺點，主要有：

（1） 粒子群算法容易陷入局部極值點中，導致得不到全局最優解。造成這種現象的原因有2個：一是待優化函數許多是多峰函數，形狀復雜，而粒子群優化算法并不能從理論上嚴格證明收斂于任何類型函數的全局極值點，因此，對于復雜的應用模型，有時可能難以得到滿意的結果；二是由于算法的參數設計或者粒子數的選擇不當，使得在計算過程中，粒子的多樣性迅速消失，造成算法“早熟”，從而導致算法不能收斂到全局極值點。

（2） 粒子群優化算法的收斂速度比較慢。原因是粒子群優化算法并沒有很充分的利用計算過程中得到的信息，在每次迭代時，只是利用了個體最優和全局最優，因此，不能在一定的時間內達到相應的精度[16?17]。

粒子群算法中粒子通過跟蹤2個極值來更新自己，算法結構運行簡單，不需調整太大參數且不需要梯度信息，早期收斂速度快，但后期受隨機振蕩現象的影響，使其在全局最優值附近需要較長的搜索時間，收斂速度慢，極易陷于局部極小值，精度降低，易發散，調整學習因子和慣性因子也無法完全避免。因此，將粒子群算法與模擬退火算法融合在一起，以克服局部收斂的缺陷。

SA算法的最主要特征就是具有跳出局部極值點區域的能力，能尋找到全局最優或近似最優，而與初始點的選擇無關。模擬退火算法由于其固有的密集計算特性，存在運行時間長和計算內存大等問題，這是大數據庫求解的主要瓶頸。模擬退火算法的并行實現技術能大幅度地提高其性能，從本質上減少計算時間。

3.2 算法流程

步驟1通過隨機模擬為不確定函數產生輸入輸出數據（即訓練樣本）。

將式（10）中模型的車流量依次轉化為x1,x2, …,xn（n為路徑總數）。根據隨機變量qi（這里表示時間參數）的分布，應用隨機模擬技術為不確定函數

產生N個輸入輸出數據（xl,yl），每次均模擬T1代。

步驟2根據產生的訓練樣本訓練神經網絡以逼近不確定函數。

步驟3初始化包含popsize個個體的粒子種群，初始化個體最優pbest、全局最優gbest和最優適應度。設置包括最大迭代次數gen、慣性權重w、加速常數c1和c2等在內的各參數。初始化退火模擬算法的參數：搜索步長η，退溫系數λ，初始溫度，最大搜索步數L。

步驟4通過訓練好的神經網絡計算每個粒子的目標值，并根據目標值計算每個粒子的適應度。

步驟5對約束條件進行處理，并根據處理原則更新每個粒子的最優和全局最優，記錄歷史最優值，更新最優位置。

步驟6對群體最佳位置應用基于SA的局部搜索策略。

步驟7更新各粒子的速度和位置。

步驟8重復步驟4～7，直到達到迭代結束條件為止。

步驟9找到最好的粒子作為最優解，求出最優目標。

3.3 基于模擬退火的局部搜索

為避免PSO算法早熟收斂，結合SA的局部搜索技術，對第k代種群的最優位置gbestk進行更新，以幫助種群跳出局部最最小。

局部搜索的算法流程如下。

步驟1令m=1，gbest’=gbestk

步驟2采用下式產生1個新解：

其中：η為搜索步長；N（0,1）為服從均值為0、方差為1的高斯分布的隨機數；Xmax和Xmin分別為變量的上、下界。

步驟3計算pa。

（1） 若x′可行，gbest′不可行，則pa=1；

（2） 若x′不可行，gbest′可行，則pa=0；

（3） 若x′和gbest′均可行，則

步驟4隨機產生0到1之間均勻分布的隨機數rand（ ），若pa≥rand（ ），則gbest′=x′。

步驟5令m=m+1。若m＞L（其中L是事先設定的最大局部搜索步數），則輸出gbest′作為種群的最優位置，否則返回步驟2。

在算法中，f是目標值，也是適應度函數；viol是約束違反量函數；另外，初始溫度按如下經驗公式確定：

其中：fmax和fmin分別為初始種群中粒子的最大目標值和最小目標值。另外，算法采用指數退溫，即T（k+1）=λ·T（k）。

3.4 仿真結果

參數選取如下。

（1） 隨機模擬3 000代，產生2 000個訓練樣本，神經網絡訓練中網絡結構為38-20-1：輸入神經元38個，隱含神經元20個，輸出1個。

（2） 粒子群參數：粒子種群規模為200，迭代次數為300次，學習因子c1=c2=2.05，慣性權重w采用線性遞減法，wmax=0.9，wmin=0.4。

（3） 模擬退火參數：搜索步長η=0.005，局部最大搜索步數L=40，退溫指數λ=0.94。

經過20次的獨立仿真，取最好的優化結果，其迭代曲線如圖2（a）所示。

最優的車流數據如下：

20次目標值的平均值為28.085 5，即最少出動卡車28臺。

為了便于比較，直接應用粒子群算法，參數設置與前相同，經過仿真調試，重新進行20次仿真，求得目標值為34.794 7，迭代曲線如圖2（b）所示。

圖2 迭代曲線圖Fig.2 Relationship between fitness values and generation

通過對上述典型算例的仿真研究，可對混合優化策略得到如下結論：

（1） 從圖2（b）可看出：粒子群算法收斂速度較快，但是最終結果并不是最優解，而是陷入了局部最優，得到的結果并不是全局最優值。

（2） 從圖2（a）可看出：基于退火?粒子群的混合智能算法比粒子群算法性能優越，使用退火?粒子群算法得到了全局最優解，求得的目標值28.085 5比34.794 7要小得多，并且收斂速度也不比基于粒子群算法的混合智能算法的收斂速度低。

4 結論

（1） 通過對露天煤礦車輛調度中不確定因素的分析，將不確定優化理論引入到露天煤礦車輛調度中，綜合運用車輛的不確定調度理論，得到了露天礦車輛的不確定數學模型，能夠更好地反映現實問題，得到的調度方案更具有彈性。

（2） 在不確定車輛調度模型的優化求解過程中，訓練神經網絡進行函數逼近，并且將模擬退火算法的局部搜索技術融入到粒子群算法中，形成的混合智能算法優勢互補，提高了算法的收斂速度和全局收斂性，為粒子群算法開辟了新的應用領域，也為不確定優化問題的求解提供了新的方法。

[1] 陸琳, 譚清美. 一類隨機需求VRP的混合粒子群算法研究[J].系統工程與電子技術, 2006, 28（2）： 244?247.

LU Lin, TAN Qing-mei. Hybrid particle swarm optimization algorithm for stochastic vehicle routing problem[J]. Systems Engineering and Electronics, 2006, 28（2）： 244?247.

[2] 康喜兵, 甘勤濤. 隨機需求車輛路徑問題的禁忌搜索算法研究[J]. 科學技術與工程, 2006, 6（13）： 1882?1884.

KANG Xi-bing, GAN Qin-tao. Research on the tabu search for vehicle routing problem in the case of stochastic demand[J]. Science Technology and Engineering, 2006, 6（13）： 1882?1884.

[3] 陳寶文, 宋申民, 陳興林. 隨機需求車輛路徑問題及其啟發式算法[J]. 計算機工程與設計, 2007, 28（1）： 138?142.

CHEN Bao-wen, SONG Shen-min, CHEN Xing-lin. Vehicle routing problem with stochastic demands and its modify ant colony system[J]. Computer Engineering and Design, 2007, 28（1）： 138?142.

[4] 宋遠清, 李永生, 梁慎清, 等. 需求隨機車輛調度問題的遺傳算法研究[J]. 計算機技術與發展, 2009, 19（2）： 230?233.

SONG Yuan-qing, LI Yong-sheng, LIANG Shen-qing, et al. Study of genetic algorithm for vehicle routing problem with stochastic demands[J]. Computer Technology and Development, 2009, 19（2）： 230?233.

[5] 張楊, 黃慶, 卜祥智. 隨機旅行時間局內車輛路徑問題的模型及其算法[J]. 管理工程學報, 2006, 20（3）： 82?85.

ZHANG Yang, HUANG Qing, BU Xiang-zhi. Model and algorithm for on-line vehicle routing problem with stochastic travel time[J]. Journal of Industrial Engineering and Engineering Management, 2006, 20（3）： 82?85.

[6] 婁山佐. 一種解決多庫房隨機車輛路徑問題方法[J]. 系統仿真學報, 2009, 19（4）： 879?882.

LOU Shan-zuo. Method for solving multi-depot stochastic vehicle routing problems[J]. Journal of System Simulation, 2009, 19（2）： 230?233.

[7] 駱正山, 王小完. 基于模糊條件下車輛路徑問題的研究[J].微電子學與計算機, 2005, 22（3）： 181?184.

LUO Zheng-shan, WANG Xiao-wan. Study of the vehicle routing problem basing fuzzy station[J]. Microelectronics, 2005, 22（3）： 181?184.

[8] 甘勤濤, 陽平華, 童鐘靈. 模糊需求車輛路徑問題的禁忌搜索算法研究[J]. 長春理工大學學報, 2006, 29（1）： 84?86.

GAN Qin-tao, YANG Ping-hua, TONG Zhong-ling. Research on the tabu search for vehicle routing problem in the case of fuzzy demand[J]. Journal of Changchun University of Science and Technology, 2006, 29（1）： 84?86.

[9] ZHENG Yong-shuang, LIU Bao-ding. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J]. Applied Mathematics and Computation, 2006, 176（2）： 673?683.

[10] 張建勇, 李軍, 郭耀煌. 具有模糊預約時間的VRP混合遺傳算法[J]. 管理科學學報, 2005,8（3）： 64?71.

ZHANG Jian-yong, LI Jun, GUO Yao-huang. Hybrid genetic algorithm to vehicle routing problem with fuzzy due-time[J]. Journal of Management Sciences in China, 2005, 8（3）： 64?71.

[11] 張幼蒂. 卡車?電鏟優化調度理論及應用[R]. 徐州： 中國礦業大學采礦工程系, 1993： 22?78.

ZHANG You-di. Theory and application on truck optimization dispatching[R]. Xuzhou： China University of Mining and Technology. Department of Mining Engineering, 1993： 22?78.

[12] 張幼蒂, 蘇婧, 李曙光. 計算機控制卡車實時調度的系統研究[J]. 中國礦業大學學報, 1995, 24（2）： 1?6.

ZHANG You-di, SU Jing, LI Shu-guang. Systematic study on computer-controlled truck real-time dispatching[J]. Journal of China University of Mining and Technology, 1995, 24（2）： 1?6.

[13] 蘇婧. 計算機控制卡車調度系統的理論與應用研究[D]. 徐州：中國礦業大學采礦工程系, 1995： 25?55.

SU Jing. Theory and systematic study on computer-controlled truck dispatching[D]. Xuzhou： China University of Mining and Technology. Department of Mining Engineering, 1995： 25?55.

[14] 王強, 張瑩, 陳沖, 等. 露天礦卡車調度關鍵時間參數的概率分布[J]. 煤炭學報, 2006, 31（6）： 761?764.

WANG Qiang, ZHANG Ying, CHEN Chong, et al. Probability distribution of key time parameters in open-pit mine truck dispatching[J]. Journal of China Coal Society, 2006, 31（6）： 761?764.

[15] 彭錦, 劉寶碇. 不確定規劃的研究現狀及其發展前景[J]. 運籌與管理, 2004, 11（2）： 1?10.

PENG Jin, LIU Bao-ding. Uncertain programming： Current status and future prospects[J]. Operations Research and Management Science, 2004, 11（2）： 1?10.

[16] 高鷹, 謝勝利. 基于模擬退火的粒子群優化算法[J]. 計算機工程與應用, 2004, 40（1）： 47?50.

GAO Ying, XIE Sheng-li. Particle swarm optimization algorithms based on simulated annealing[J]. Computer Engineering and Applications, 2004, 40（1）： 47?50.

[17] 王凌, 劉波. 微粒群優化與調度算法[M]. 北京： 清華大學出版社, 2008： 62?69. WANG Ling, LIU Bo. Particle swarm optimization and scheduling algorithms[M]. Beijing： Tsinghua University Press, 2008： 62?69.

（編輯 楊幼平）

Uncertain scheduling model and optimization of vehicle in open mine

XUE Xue, SUN Wei, LIU Xiao-wen
（School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221008, China）

Taking an open mine in Inner Mongolia as the research object, the randomness of the key time parameters in vehicle scheduling was determined through statistical analysis, and the uncertain model of vehicle scheduling was given. Neural network was trained to approximate function. Because the particle swarm algorithm was likely to fall into local convergence, combining the local search method of the simulated annealing algorithm, a hybrid intelligent algorithm which consisted of the simulated annealing algorithm and the particle swarm optimization was proposed to solve the uncertain model. The results show that the high performance and effectiveness of the proposed method is improved through the computational results.

uncertain scheduling; vehicle scheduling; particle swarm optimization; simulated annealing optimization; hybrid optimization algorithm

TP391.9

A

1672?7207（2011）05?1354?07

2010?08?20；

2010?11?29

國家高技術研究發展計劃（“863”計劃）項目（2007AA06Z114）；中國礦業大學青年科研基金資助項目（0C080250）

薛雪（1980?），女，江蘇徐州人，講師，從事生產調度、智能調度的研究；電話：13512565965；E-mail： cumtxx@126.com