具有多種備選方案的露天礦統(tǒng)一運輸調(diào)度優(yōu)化①

田謙益

(閩南師范大學 計算機學院, 福建 漳州 363000)

具有多種備選方案的露天礦統(tǒng)一運輸調(diào)度優(yōu)化①

田謙益

(閩南師范大學 計算機學院, 福建 漳州 363000)

受客觀條件限制，使得露天礦統(tǒng)一運輸調(diào)度的優(yōu)化存在多個復(fù)雜約束，需要多種備選方案的問題.提出了一種新型優(yōu)化方法，該方法采用一種自適應(yīng)的懲罰函數(shù)方法來處理約束，然后運用多元優(yōu)化算法進行優(yōu)化.該自適應(yīng)懲罰函數(shù)參數(shù)少，簡單高效，對問題依賴小.多元優(yōu)化算法將搜索個體按其不同的功能組合成一個特殊的數(shù)據(jù)結(jié)構(gòu)，利用該結(jié)構(gòu)保存和共享尋優(yōu)過程信息，實現(xiàn)搜索過程記憶，能以較大概率找到最優(yōu)解，同時保留多個次優(yōu)解.以某露天鐵礦為工程應(yīng)用實例研究，將該方法與GA、PSO-w、DMS-PSO-HS幾種群智能算法的優(yōu)化結(jié)果進行比較驗證，結(jié)果表明本文提出的方法在露天礦統(tǒng)一運輸調(diào)度優(yōu)化中處理約束簡單、高效，能夠提供多種備選方案且最優(yōu)解精度更高.對露天礦統(tǒng)一運輸調(diào)度優(yōu)化問題進行多個備選方案的研究具有理論依據(jù)和實際意義，采用該方法進行具有多個備選方案的露天礦統(tǒng)一運輸調(diào)度優(yōu)化是可行有效的.

露天礦，懲罰函數(shù)，多元優(yōu)化算法，搜索元，過程記憶

露天礦通常存在多采掘點、多排卸點，從而形成物料流的多條通道.而露天礦的生產(chǎn)主要是大量物料的運移，運輸成本一般占整個露天礦生產(chǎn)成本的50%以上，是影響礦山經(jīng)濟效益的重要因素[1].國內(nèi)外露天礦運輸設(shè)備與物料的匹配情況主要分為3種類型：統(tǒng)一運輸、獨立運輸和組合運輸，其中統(tǒng)一運輸是指每臺卡車可以運輸任何物料、可以到任何裝載點裝車、到任意排卸點卸車, 實際上是把礦山車流規(guī)劃問題簡化為多個裝載點和多個卸載點之間的車流規(guī)劃問題, 這是目前應(yīng)用成果的主要體現(xiàn)[2].

近年來已有不少學者將遺傳算法、粒子群算法等群智能優(yōu)化算法用于露天礦運輸調(diào)度問題，取得了較好的結(jié)果[3-7].但這些方法都只能給出一個最優(yōu)方案，而在實際露天礦獨立運輸調(diào)度中，野外環(huán)境較為惡劣，容易出現(xiàn)塌方使道路中斷等類似事件，導(dǎo)致運輸線路需要調(diào)整，原有的最優(yōu)方案失效，從而增加運輸成本.此時若能啟用備選方案，就能適應(yīng)外界環(huán)境變化，快速調(diào)整運輸調(diào)度計劃，減少因臨時變化給生產(chǎn)帶來的損失.因此，如何根據(jù)外界環(huán)境變化從多個備選方案中選擇和確定礦石及巖石的合理調(diào)運方案，在滿足多個復(fù)雜約束的條件下，使得運輸成本在一定的運輸網(wǎng)絡(luò)中最小，是露天礦優(yōu)化設(shè)計中需要解決的重要問題之一.為實現(xiàn)這一目的，本文采用一種新型方法來解決露天礦獨立運輸調(diào)度的優(yōu)化問題.該方法采用一個參數(shù)少、效率高自適應(yīng)懲罰函數(shù)來處理復(fù)雜約束，然后運用多元優(yōu)化算法(multivariant optimization algorithm，MOA)進行優(yōu)化.

1 露天礦運輸調(diào)度模型

露天礦的生產(chǎn)主要是由電鏟車裝車、電動輪自卸卡車(以下簡稱卡車)運輸來完成.卡車一旦調(diào)用,則在1 個臺班內(nèi)不熄火.以節(jié)約生產(chǎn)成本為目的,統(tǒng)一運輸可歸結(jié)為一個總運輸成本最小的多變量帶復(fù)雜約束的線性規(guī)劃模型，模型見式(1)，表1給出了模型中的符號參數(shù)設(shè)定.

(1)

其中式(1)中，f(x) 為目標函數(shù)，表示一個臺班內(nèi)總運量的最小值；xij,xik為整數(shù)型決策變量，其中xij為從鏟點i運往卸礦點j的運輸車次，xik為從鏟點i運往卸巖點k的運輸車次.

2 多元優(yōu)化算法在露天礦獨立運輸調(diào)度中的優(yōu)化

表1露天礦運輸調(diào)度系統(tǒng)模型參數(shù)設(shè)定

符號含義i(i=1，…，l)臺班中的鏟裝點編號j(j=1，…，m)臺班中設(shè)置的卸礦點的編號k(k=1，…，n)臺班中設(shè)置的卸巖點的編號dij/dik為鏟裝點到卸礦/巖點的距離cij/cik單次鏟點到卸礦/巖點的滿載費用cji/cki單次卸點到卸礦/巖點的空載費用pi各鏟點的巖石量qi各鏟位的礦石量Mj臺班卸礦點的產(chǎn)量要求Mk臺班卸巖點的產(chǎn)量要求Qj各卸礦點的礦石品位要求T礦車滿載量ai鏟點礦石的平均品位am/ai為卸點要求品位上/下限t1裝車時間t2卸車時間t3一個臺班工作時間

2.1 多元優(yōu)化算法

圖1 MOA的數(shù)據(jù)結(jié)構(gòu)

經(jīng)典的群智能算法及其改進算法在解決不同問題時有著各自不同的優(yōu)勢，但都不同程度地存在著全局探索與局部開發(fā)相互制約，易陷入局部最優(yōu)的問題.究其原因主要是一些復(fù)雜問題的全局最優(yōu)解被大量的局部最優(yōu)解所包圍，具有較大欺騙性，而算法在尋優(yōu)過程中信息利用不充分，導(dǎo)致算法陷入局部最優(yōu).只有算法合理地處理全局探索和局部開發(fā)之間的關(guān)系，同時充分利用尋優(yōu)過程信息，才能找到全局最優(yōu)解[9].多元優(yōu)化算法采用一種新型的數(shù)據(jù)結(jié)構(gòu)存儲和充分利用尋優(yōu)過程信息，MOA中的進行搜索的個體為搜索元，搜索元按照不同的功能分為兩類，一類搜索元是全局搜索元(GlobalAtom，Ga)負責全局搜索，另一類搜索元是局部搜索元(LocalAtom，La)負責局部挖掘，全局搜索元以隊列的形式排列，局部搜索元以堆棧的形式排列，構(gòu)成一個特殊的數(shù)據(jù)結(jié)構(gòu)體.該結(jié)構(gòu)體如圖1所示，頂部是由全局搜索元構(gòu)成的隊列，每個全局搜索元下掛一個局部搜索元構(gòu)成的堆棧，每迭代一次，MOA對整個解空間進行全局搜索，找到具有開發(fā)潛力的區(qū)域；然后對各個有開發(fā)潛力的區(qū)域進行挖掘，找到該區(qū)域里的最優(yōu)解，排在堆棧頂端，成為全局最優(yōu)解，然后這些最優(yōu)解再進行比較，將最優(yōu)的全局最優(yōu)解排在隊列的最左端，這樣每次迭代結(jié)束時，當前的全局最優(yōu)解都出現(xiàn)在隊列的最前端，下掛與其對應(yīng)的多個局部最優(yōu)解，保留了尋優(yōu)過程信息.在整個迭代過程中，全局搜索和局部挖掘都同時存在，共享尋優(yōu)信息，使算法不易出現(xiàn)過早收斂，提高算法尋優(yōu)性能.

全局搜索元根據(jù)式(2)生成

(2)

式中d是問題的維度；maxi和mini分別為解空間第i維的上、下限；hi為一個介于mini到maxi之間均勻分布的隨機數(shù).局部搜索元根據(jù)式(3)生成

(3)

式中r為局部鄰域半徑,決定了局部鄰域的范圍；li,(i=1,…,d)為一個介于-1到1之間均勻分布的隨機數(shù).

2.2 多元優(yōu)化算法優(yōu)化露天礦獨立運輸調(diào)度模型

露天礦運輸調(diào)度問題可以歸結(jié)為一個帶復(fù)雜約束的線性規(guī)劃問題，復(fù)雜約束處理的好壞，直接影響到是否能找問題的全局最優(yōu)解.在處理復(fù)雜約束的方法中，有基于罰函數(shù)的方法、基于搜索可行解的方法等[ 10-11].本文采用一種新型的罰函數(shù)的方法來處理復(fù)雜約束，先構(gòu)造適應(yīng)度函數(shù)如

(4)

式中f(x)的是原問題的目標函數(shù)，φi(x)為第i個約束條件，且φi(x)≤0，K為懲罰函數(shù).懲罰函數(shù)的好壞，決定了能否在迭代過程中正確權(quán)衡目標函數(shù)與約束條件之間的關(guān)系.因此，本文構(gòu)造的懲罰函數(shù)如

圖2 用于露天礦運輸調(diào)度優(yōu)化的MOA算法流程圖

(5)

表2 相關(guān)參數(shù)表

式(5)是一個關(guān)于μ的指數(shù)衰減函數(shù)，迭代初期，由于可行解的個數(shù)較少，甚至沒有，則μ=0懲罰函數(shù)較大，也就是說懲罰力度較大，這時適應(yīng)度函數(shù)的目的在于找到可行解；隨著迭代次數(shù)的增加，可行解也逐漸增多，值也由0逐漸變大，懲罰力度變小，適應(yīng)度函數(shù)逐漸將目標轉(zhuǎn)向?qū)ふ夷繕撕瘮?shù)；當μ=1，意味著解空間里全是可行解，此時懲罰函數(shù)最小.

3 實例驗證

現(xiàn)有某露天鐵礦，具體參數(shù)見表2至表4，以總運量最小作為目標函數(shù)，建立該露天鐵礦的運輸調(diào)度模型.為驗證算法的有效性，將MOA算法與精英保留策略的遺傳算法(GA)[12]、自適應(yīng)慣性權(quán)重粒子群算法(PSO-w)[13]和動態(tài)多群和聲粒子群算法(DMS-PSO-HS)[14]進行比較，所有算法采用MATLAB2013a編程實現(xiàn).所有的種群大小為135，最大迭代次數(shù)為300次，其中MOA算法數(shù)據(jù)結(jié)構(gòu)為的上三角結(jié)構(gòu)，局部區(qū)域搜索半徑初始值設(shè)為2，隨迭代次數(shù)線性減小.算法隨機運行10次，所有實驗結(jié)果都是取10次的平均值.

表3 各鏟位礦石、巖石數(shù)量及礦石平均品位

表4 各鏟位與各卸點間的距離(km)

圖3 適應(yīng)度精度變化曲線圖

圖3為四種算法的優(yōu)化過程適應(yīng)度精度變化曲線圖, 其中MOA1-MOA3表示由MOA算法得出的備選方案1至備選方案3.按照圖1給出的MOA數(shù)據(jù)結(jié)構(gòu)形式，MOA算法最多可以有14個備選方案，但由于越往后，總運量會越來越大，所以圖中只給出了前3個備選方案和其他算法的最優(yōu)方案進行比較.從圖3可以看出GA、PSO-w和DMS-PSO-HS迭代次數(shù)在20次左右，適應(yīng)度值就開始收斂，而MOA迭代約150次才開始收斂，MOA較其他3種算法的收斂速度會慢一些，但MOA的收斂精度卻是最高的.

表5為尋優(yōu)結(jié)果對比表，從表5可以看出，算法收斂精度由高到低依次是：MOA、DMS-PSO-HS、MOA1、MOA2、GA、PSO-w、MOA3，MOA算法的最優(yōu)解收斂精度最高，，MOA算法的最優(yōu)解收斂精度最高，這和從圖3得到的結(jié)論是一致的，而且MOA算法得出的總運量也是最小的.此外MOA算法收斂速度和精度都優(yōu)于文獻[15]的結(jié)果.

表5 尋優(yōu)結(jié)果對比

4 結(jié)論

實驗結(jié)果表明，采用本文提出的方法進行露天礦統(tǒng)一運輸調(diào)度的優(yōu)化具有多重優(yōu)勢：(1) 自適應(yīng)的懲罰函數(shù)參數(shù)少，結(jié)構(gòu)簡單，對問題依賴小，適應(yīng)性強.(2) 能夠提供多種備選方案.由于MOA算法特殊的數(shù)據(jù)結(jié)構(gòu)特點，不僅能夠保留算法找到的最優(yōu)解，還能保留次優(yōu)解的信息，充分利用過程信息.在實施露天礦運輸調(diào)度時，如出現(xiàn)運輸車輛出故障等某些條件臨時發(fā)生變化又在可容忍范圍之內(nèi)時，可以考慮備選方案，以便能靈活、快速地調(diào)整運輸調(diào)度計劃，減少因臨時變化給生產(chǎn)帶來的損失.(3) 收斂穩(wěn)定.MOA算法特殊的數(shù)據(jù)結(jié)構(gòu)助于全局搜索和局部開發(fā)能力的平衡，而且在整個迭代過程中全局搜索和局部開發(fā)都同時存在，使得算法不至于過早收斂、跳出局部最優(yōu)解的能力更強.(4) 精度高.MOA算法最優(yōu)解的精度高于所選的其他幾種群智能優(yōu)化算法.雖然MOA算法的收斂速度不及其他幾種算法，但在實際工程應(yīng)用中，許多優(yōu)化問題屬于離線優(yōu)化，這就意味著速度是次要的，而精度是第一位的.

本文提出的方法對露天礦統(tǒng)一運輸調(diào)度優(yōu)化是可行高效的，同時對露天礦統(tǒng)一運輸調(diào)度優(yōu)化問題進行多個備選方案的研究具有理論依據(jù)和實際意義.

[1] 宋子嶺,白潤才,魏春啟.霍林河露天礦卡車調(diào)度決策方法及模型的研究[J].露天采煤技術(shù),2001 (1)：38-41.

[2] 孫效玉,張維國.滿足各種礦巖配車需求的露天礦車流規(guī)劃模型[J].東北大學學報：自然科學版,2012, 33(10): 1 487-1 491.

[3] Rahmanpour M., Osanloo M. A genetic algorithm for pit limit and blending optimization[C]. //23rd International Mining Congress and Exhibition of Turkey, IMCET 2013,Turkey, 2013.

[4] 李勇,胡乃聯(lián),李國清.基于改進粒子群算法的露天礦運輸調(diào)度優(yōu)化[J].中國礦業(yè),2013,22(4): 98-105.

[5] 胡乃聯(lián),李勇.李國清，等.用粒子群優(yōu)化算法編制露天礦生產(chǎn)作業(yè)計劃[J].北京科技大學學報,2013,35(4):537-543.

[6] V N Coelho a, M J F Souza a, I M Coelho, et al. Multi-objective approaches for the open-pit mining operational planning problem[J]. Electronic Notes in Discrete Mathemetics, 2012, 39: 233-242.

[7] Masoud Soleymani Shishvan a,c Javad Sattarvand. Long term production planning of open pit mines by ant colony optimization[J]. European Journal of Operational Research, 2015, 240: 825-836.

[8] Li Baolei, Shi Xinling, Gou Changxing, et al. Multivariant optimization algorithm for multimodal optimization [J]. Applied Mechanics and Materials, 2014, 483: 453-457.

[9] 李寶磊. 多元優(yōu)化過程記憶算法及動靜態(tài)條件下多模態(tài)尋優(yōu)研究[D].云南昆明，云南大學，2015.

[10] 王軍濤,尹國才,成岳鵬.智能算法在約束優(yōu)化問題中的應(yīng)用研究[J].北華航天工業(yè)學院學報,2013, 23(1):24-27.

[11] 甘敏,彭輝.一種新的自適應(yīng)懲罰函數(shù)算法求解約束優(yōu)化問題[J].信息與控制,2009,38(1):24-28.

[13] Shi Y, Eberhart R C. A modified particle swarm optimizer[C]. //Proceedings of IEEE World Congress on Computational Intelligence. NewYork, USA: IEEE, 1998.

[14] Zhao S Z, Suganthan P N, Pan Q K, et al. Dynamic multi-swarm particle swarm optimizer with harmony search[J]. Expert Systems with Applications, 2011, 38(4): 3 735-3 742.

[15] 霍曉宇,楊仕教,吳長振，等. 露天礦山運輸調(diào)度系統(tǒng)粒子群優(yōu)化[J]. 煤炭學報, 2012.37: 234-239.

VariousAlternativesforOptimizationofOpen-pit-mineIntegratedFleetHaulageDispatching

TIAN Qian-yi

(School of Computer Science, Minnan Normal University, Zhangzhou 363000，China)

By the condition limitation, the optimization of the open-pit-mine integrated fleet haulage dispatching has many complex constraints hard to deal with and yearns for various alternatives. A novel method of optimization that handles the complex constraints with an adaptive penalty function and optimizing with multivariant optimization algorithm is proposed. The adaptive penalty function is made up of simple and fewer parameters and is adaptable. The search individuals of multivariant optimization algorithm are constructed by a special data structure that is providing memory and information sharing according to different functions. Then the search individuals made full use of optimization process information, and implemented process memorise. At last the optimum could be found meanwhile various alternatives retention. A case study is performed by taking an open-pit iron mine as an engineering background. By comparing the optimization results of the algorithm with GA, PSO-w, DMS-PSO-HS, it was proved that the proposed method is simple and efficient to deal with the constraints, provides various alternatives and has advantages in the solutions’ quality for optimization open-pit-mine integrated fleet haulage dispatching. The various alternatives research of optimization open-pit-mine integrated fleet haulage dispatching has theory basis and practical significance. It is effective to optimize open-pit-mine integrated fleet haulage dispatching using the proposed method.

open-pit-mine，penalty function，multivariant optimization algorithm，search atom，process memorise

2017-05-28

福建省省屬高?？蒲袑ｍ楉椖?JK2016025)；福建省教育廳產(chǎn)學研項目(JAT160283)；福建省中青年教師教育科研項目(JAS151296)資助

田謙益，E-mail：qytian@126.com.

TP183; TD561

A

1672-6634(2017)03-0088-05