張新文

摘 要：針對(duì)露天“卡調(diào)”系統(tǒng)路線尋優(yōu)的非線性問題，利用模擬退火算法和遺傳算法相結(jié)合，彌補(bǔ)了傳統(tǒng)遺傳算法容易陷入局部極值的缺陷。仿真結(jié)果表明，改進(jìn)的遺傳算法在找到同樣最短距離的情況下，節(jié)省了7代的迭代次數(shù)，節(jié)省了路徑優(yōu)化時(shí)間，為該領(lǐng)域提供了一條新思路。

關(guān)鍵詞：卡車調(diào)度；遺傳算法；模擬退火算法；路徑優(yōu)化

DOI：10.16640/j.cnki.37-1222/t.2019.07.056

1 序言

露天“卡調(diào)”系統(tǒng)于20世紀(jì)中葉就被提出，隨著計(jì)算機(jī)技術(shù)的日益發(fā)展，國內(nèi)外各個(gè)高校及科研院所的學(xué)者將最先進(jìn)的技術(shù)及理論都集成到露天礦的生產(chǎn)調(diào)度過程中，通信方式也經(jīng)歷了由有線到無線的質(zhì)的飛躍，一改傳統(tǒng)通過人為調(diào)度方法，改善了卡車滯留、擁堵等事件的發(fā)生，提高了露天礦的整體生產(chǎn)效率，從而帶動(dòng)了經(jīng)濟(jì)增長點(diǎn)。

隨著卡車調(diào)度系統(tǒng)的發(fā)展，系統(tǒng)已經(jīng)由理論研究過渡到實(shí)際應(yīng)用，尤其是GPS技術(shù)的誕生，美國公司于1990年將該技術(shù)應(yīng)用于卡調(diào)系統(tǒng)中，感知了卡車速度，并使定位精度得到了大幅度提升；1990年到2000年期間，國內(nèi)如西安煤科院、撫順煤科院和中國礦業(yè)大學(xué)等高校及科研院所都涌入了該領(lǐng)域的研究，獲得了較多科研成果。21世紀(jì)初期，中國東方測控集團(tuán)也研發(fā)了卡調(diào)系統(tǒng)，將最先進(jìn)的定位技術(shù)和無線電技術(shù)等集成于系統(tǒng)，實(shí)現(xiàn)了全礦井生產(chǎn)、調(diào)度系統(tǒng)于一體，該套系統(tǒng)在鞍鋼礦業(yè)公司得到推廣與使用，提高了礦山的整體效率，經(jīng)濟(jì)效益突出?？ㄜ囌{(diào)度體統(tǒng)究其根本是非線性系統(tǒng)，隨著人工智能的發(fā)展，神經(jīng)網(wǎng)絡(luò)、粒子群、遺傳算法等最先進(jìn)的理論可以解決非線性問題，可以應(yīng)用在優(yōu)化調(diào)度方面。

2 應(yīng)用于卡調(diào)系統(tǒng)的遺傳退火算法

2.1 模擬退火算法

模擬退火算法（SA）早于1953年提出，該算法構(gòu)思來源于物理學(xué)的物體退火降溫過程。根據(jù)物理學(xué)原理，固體從加熱到冷卻的過程中，原子運(yùn)動(dòng)由劇烈變?yōu)榫徍停瑑?nèi)能也伴隨著溫度的降低而由升高變?yōu)榻档?，此時(shí)，固體內(nèi)部原子已發(fā)生重新排列，打破了原有平衡達(dá)到了一種新的穩(wěn)態(tài)，以上是模擬退火算法的物理學(xué)意義。退火算法與粒子群一般都適用于尋找全局最優(yōu)解，但是由于存在溫度初值和模擬退火V及溫度管控方面的問題，使其參數(shù)尋優(yōu)過程比較困難。

2.2 遺傳算法

該算法于20世紀(jì)70年代由美國教授提出來，算法主要來自于仿生進(jìn)化思想，即“適者生存”原則，是機(jī)器學(xué)習(xí)領(lǐng)域主要算法，適用于模型構(gòu)建，算法本身具有自組織、自學(xué)習(xí)能力。算法的具體實(shí)施流程是：第一步，種群隨機(jī)化形成，并選擇適合的循環(huán)次數(shù)及適應(yīng)函數(shù)；第二部：優(yōu)勝劣汰，保留強(qiáng)壯個(gè)體，舍棄不適類別；第三部，交叉選擇，迭代更強(qiáng)種類，并進(jìn)行變異化改進(jìn)；第四部：參數(shù)尋優(yōu)，找到全局最優(yōu)解。

2.3 應(yīng)用于卡調(diào)系統(tǒng)的遺傳退火算法

由于傳統(tǒng)遺傳算法在迭代后期容易陷入局部極值，而退火算法可以規(guī)避此類問題，因此綜合二者優(yōu)勢(shì)，找到全局最優(yōu)，具體原則如下：

SA-GA算法首先由退火算法提出最初群體，并通過種群進(jìn)化，形成更優(yōu)初始值，得到更高效率結(jié)果；利用模擬退火跳出局部最優(yōu)值，強(qiáng)化尋優(yōu)能力；在退火過程中，溫度降低，退火效率更快，具體流程如下：

3 算法效能分析

以某礦井為應(yīng)用示范，以選擇的某段行程為參考對(duì)象，在matlab里分別利用GA算法，SA-GA算法進(jìn)行模擬，群體初始粒子數(shù)為80，迭代次數(shù)為150，初始T選擇30℃，選取的每一點(diǎn)世界坐標(biāo)系如表1，表2所示，模擬效果如圖2、圖3所示。

4 總結(jié)

由圖2得到，SA在第42代得到最優(yōu)解，最短S為30.68km；由圖3得到，SA-GA算法在第35代找到全局最優(yōu)，最短S為31.9548km。因此，加入模擬退火算法后的遺傳算法在找到同樣最優(yōu)解的過程中節(jié)省了7代，這在露天礦卡車調(diào)度實(shí)際應(yīng)用中可以節(jié)省時(shí)間，提供了一條新思路。

參考文獻(xiàn)：

[1]劉浩洋.基于改進(jìn)蟻群算法的露天礦卡車優(yōu)化調(diào)度研究[D].西安：西安建筑科技大學(xué)，2013.

[2]高登來.露天礦卡車自動(dòng)化調(diào)度系統(tǒng)的考察[J].露天采煤技術(shù)，1999增刊：80-81.

[3]李軍才.Dispatch系統(tǒng)在我國大型露天礦山中的應(yīng)用[J].中國礦業(yè)，2000（09）：62-65.

[4]Ahangaran，Daryoush Kaveh，Yasrebi，Amir Bijan，Wetherelt，Andy.Real-time dispatching modeling for trucks with different capacities in open pit mines[J].Archives of Mining Sciences，2012（57）：39-52.

[5]王訓(xùn)斌，陸慧娟，陳五濤.帶時(shí)間窗動(dòng)態(tài)車輛路徑問題的改進(jìn)蟻群算法[J].工業(yè)控制計(jì)算機(jī)，2009，22（01）：41-43.

[6]周四根.特大型露天礦道路優(yōu)化設(shè)計(jì)研究[J].采礦技術(shù)，2014，5

（05）：13-14.