基于遺傳算法的卡車調(diào)度模型的研究

汪 洋，王山東

(1.安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243032；2.河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇南京 210098)

?

基于遺傳算法的卡車調(diào)度模型的研究

汪 洋1，王山東2

(1.安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243032；2.河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇南京 210098)

針對(duì)露天礦山的生產(chǎn)，建立合理的礦卡車調(diào)度方案是提升采掘和運(yùn)輸設(shè)備的效率、減少成本的有效途徑。通過(guò)對(duì)礦山生產(chǎn)中車輛調(diào)度的各參數(shù)進(jìn)行分析，本文建立起卡車運(yùn)輸損耗最少的多目標(biāo)函數(shù)和一系列關(guān)鍵因素作為約束條件的調(diào)度模型，并運(yùn)用遺傳算法求解，確定符合實(shí)際的調(diào)度方案以滿足生產(chǎn)需求。

露天礦山；卡車調(diào)度；多目標(biāo)函數(shù)；遺傳算法

露天礦山開采是通過(guò)對(duì)采掘設(shè)備和運(yùn)輸設(shè)備的實(shí)時(shí)調(diào)配來(lái)完成的。為了努力適應(yīng)我國(guó)礦山生產(chǎn)的新常態(tài)，實(shí)現(xiàn)降本增效、優(yōu)化產(chǎn)能，構(gòu)建合理的礦山卡車調(diào)度生產(chǎn)系統(tǒng)勢(shì)在必行。運(yùn)用合理的車輛分配與規(guī)劃和高效的車輛調(diào)度策略，能夠減少企業(yè)在卡車調(diào)度系統(tǒng)中產(chǎn)生的盲目性，最終將提高整個(gè)企業(yè)的經(jīng)濟(jì)效益[1]。結(jié)合遺傳算法和多目標(biāo)優(yōu)化方案制定出合理高效的調(diào)度方法來(lái)解決問(wèn)題，可以較好地提高系統(tǒng)的實(shí)際運(yùn)用價(jià)值。

1 根據(jù)實(shí)際生產(chǎn)情況建立卡車調(diào)度模型

露天礦卡車調(diào)度模型一般由目標(biāo)函數(shù)和一系列的約束條件構(gòu)成[2-3]。本文在完成生產(chǎn)任務(wù)條件下以卡車在一段時(shí)間內(nèi)運(yùn)輸費(fèi)用和車輛損耗費(fèi)用的總和達(dá)到最小為目標(biāo)，以采場(chǎng)電鏟的生產(chǎn)能力和卸料點(diǎn)的工作能力作為約束條件建立如下數(shù)學(xué)模型。

目標(biāo)函數(shù)：

約束條件：

(1)

(2)

(3)

R-ΔR≤Pm/Pr≤R+ΔR.

(4)

在目標(biāo)函數(shù)的公式中，C為某段時(shí)間范圍內(nèi)全部卡車的費(fèi)用之和；k、m、n分別為出動(dòng)的卡車總數(shù)量、實(shí)際工作的電鏟數(shù)量、卸點(diǎn)數(shù)量；Dij為第i個(gè)電鏟到第j個(gè)卸點(diǎn)的距離；Dji為第j個(gè)卸點(diǎn)到第i個(gè)電鏟的距離；Xsij為第s輛卡車由第i個(gè)電鏟到第j個(gè)卸點(diǎn)行駛的車數(shù)；Xsji為第s輛卡車由第j個(gè)卸點(diǎn)到第i個(gè)電鏟行駛的車數(shù)；

Cs1為第s輛車的重車單位長(zhǎng)度的運(yùn)輸費(fèi)用和設(shè)備損耗費(fèi)用；Cs2為第s輛車的空車單位長(zhǎng)度的運(yùn)輸費(fèi)用和損耗費(fèi)用；Ds為第s輛車的總運(yùn)行距離；Xs3為第s輛車單位長(zhǎng)度的維護(hù)費(fèi)用。

式(1)為卸點(diǎn)的卸貨能力約束，Cs為第s輛車的裝車重量；Ej為第j個(gè)卸點(diǎn)的卸貨能力。式(2)為電鏟的裝車約束，F(xiàn)i0為第i個(gè)電鏟的最低裝貨能力要求；Fi為第i個(gè)電鏟的裝貨能力。式(3)為單個(gè)電鏟的派車數(shù)量限制，V0為卡車運(yùn)行的平均速度；Tic為第i個(gè)電鏟的裝車時(shí)間。式(4)為開采礦石和巖石的比例約束，Pm為卡車運(yùn)送礦石的總重量；Pr為卡車運(yùn)送巖石的總重量；R為礦石和巖石的采剝比；ΔR為剝離產(chǎn)量的波動(dòng)量。

2 改進(jìn)的遺傳算法設(shè)計(jì)

遺傳算法GA(GeneticAlgorithm)是類似于生物進(jìn)化過(guò)程的優(yōu)化算法。它利用了生物界的自然選擇和群體基因遺傳機(jī)理，是具備隨機(jī)型和自適應(yīng)優(yōu)化的搜索算法，其計(jì)算過(guò)程模擬了進(jìn)化過(guò)程中的繁殖、交叉和突變現(xiàn)象，利用“適者生存”的進(jìn)化理論和遺傳學(xué)說(shuō)，引入隨機(jī)統(tǒng)計(jì)理論，使得適應(yīng)度高的優(yōu)良品種得以保留并加以組合，使之產(chǎn)生更優(yōu)良的個(gè)體[4-6]。其本質(zhì)是一種并行、高效的全局化搜索算法。

每個(gè)需要求得問(wèn)題的可能性解在遺傳算法里被視為一個(gè)個(gè)體，將其編碼成染色體，多個(gè)個(gè)體形成群體。根據(jù)設(shè)定的目標(biāo)函數(shù)對(duì)隨機(jī)產(chǎn)生的每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，計(jì)算相應(yīng)的適應(yīng)度值。根據(jù)適應(yīng)度值選擇個(gè)體實(shí)行復(fù)制、交叉和變異等操作，最終形成最適合環(huán)境的最優(yōu)解。算法流程圖如圖1所示。

圖1 遺傳算法流程圖

2.1 編碼及初始群體的產(chǎn)生

首先，產(chǎn)生初始化群體，并編碼。假設(shè)大小寫字母分別代表電鏟和卸料點(diǎn)。在一段時(shí)間內(nèi)，全部卡車的運(yùn)送線路稱為一條染色體，將一條染色體用矩陣的字符集合來(lái)表示。圖2表示某段時(shí)間內(nèi)4輛卡車的某個(gè)運(yùn)送方案，即1條染色體。根據(jù)電鏟和卸點(diǎn)是否處于正常工作情況，隨機(jī)產(chǎn)生初始線路即初始群體。

圖2 運(yùn)輸方案

2.2 計(jì)算群體的適應(yīng)度

調(diào)度系統(tǒng)模型設(shè)計(jì)的目標(biāo)函數(shù)是使運(yùn)輸費(fèi)用達(dá)到最小，所以在計(jì)算中取其倒數(shù)作為適應(yīng)度的值，即f=1/C，則運(yùn)輸費(fèi)用越低適應(yīng)度就越好。將經(jīng)過(guò)交叉和變異操作后適應(yīng)度最低的個(gè)體替換為計(jì)算后的染色體中適應(yīng)度最高的個(gè)體，適應(yīng)度最高的個(gè)體不參與運(yùn)算。

2.3 染色體交叉

假設(shè)種群規(guī)模是 Ns，交換概率為 Pc。傳統(tǒng)的交叉方法是將種群中相鄰的兩條染色體分為一組，每組產(chǎn)生一個(gè)(0,1)之間的隨機(jī)數(shù)αi，當(dāng)i為偶數(shù)時(shí)，i=1,2,..., Ns/2，當(dāng)i為奇數(shù)時(shí),i=1,2,…,(Ns-1)/2。當(dāng)Pc> αi時(shí)，將兩條染色體之間的第i行進(jìn)行交換。交換的位置由第2行到第i行最短子染色體的長(zhǎng)度之間隨機(jī)產(chǎn)生，從該位置開始到后面的部分進(jìn)行交換。

改進(jìn)后的方法首先將相鄰的兩條染色體分為一組，方法同上。再分別取兩條染色體第i行的每個(gè)基因，兩條染色體第i行較短的基因長(zhǎng)度為Nt，產(chǎn)生一個(gè)(0,1)之間的隨機(jī)數(shù)βi(i=1,…, Nt-1)，當(dāng)Pc>βi時(shí)先判斷每個(gè)對(duì)應(yīng)位置的基因是否都對(duì)應(yīng)為裝礦或者裝巖的電鏟，若類型相同，則進(jìn)行交換。再判斷Pc>βi+1是否成立，若成立則將兩條染色體第i位和第i+1位基因都進(jìn)行交換。當(dāng)計(jì)算到第Nt+1條等位基因時(shí)，將較長(zhǎng)的基因從第 Nt+1開始到結(jié)尾交換到較短的基因尾部。

假設(shè)在此時(shí)間段內(nèi)，裝礦作業(yè)的電鏟編號(hào)為A、B、C，裝巖作業(yè)的電鏟編號(hào)為D、E，礦石卸點(diǎn)編號(hào)為a、b，巖石卸點(diǎn)編號(hào)為c、d，實(shí)現(xiàn)過(guò)程如圖3所示。

圖3 染色體交叉過(guò)程

2.4 染色體變異

假設(shè)種群規(guī)模是Ns，隨機(jī)產(chǎn)生Ns個(gè)(0,1)分布的隨機(jī)數(shù)γi和變異概率Pm。當(dāng)γi

3 實(shí)例測(cè)試結(jié)果和分析

實(shí)驗(yàn)以安徽某露天鐵礦山在某個(gè)班次的生產(chǎn)時(shí)間段內(nèi)為例。其中電鏟編碼為A、B、C、D、E，卸點(diǎn)編碼為a、b、c、d。電鏟和卸點(diǎn)之間的相互距離如表1所示。標(biāo)定班次內(nèi)出動(dòng)的車數(shù)量為16，即種群規(guī)模為16，生產(chǎn)指揮系統(tǒng)給定的計(jì)劃為裝礦石25車，巖石15車，裝礦電鏟3臺(tái)，裝巖電鏟2臺(tái)，礦石和巖石卸點(diǎn)均為2個(gè)。假設(shè)交叉概率Pc=0.1，變異概率Pm=0.9，針對(duì)某個(gè)班次內(nèi)的生產(chǎn)情況，對(duì)群體進(jìn)行迭代求解。

表1 電鏟和卸點(diǎn)之間的距離信息km

ABCDEa2．01．82．12．31．7b2．11．92．22．41．8c2．62．42．52．82．2d2．82．62．73．02．5

注：以數(shù)值根據(jù)之前測(cè)試的數(shù)據(jù)為依據(jù)。

種群進(jìn)化過(guò)程如圖4所示。

圖4 種群進(jìn)化情況

測(cè)試結(jié)果表明，在種群經(jīng)過(guò)100次的迭代后，該種群的均值較為穩(wěn)定，結(jié)果收斂。最優(yōu)解的總費(fèi)用為8810元。

4 結(jié)語(yǔ)

本文將露天礦山卡車調(diào)度的研究轉(zhuǎn)變?yōu)榍蠼馐芏鄠€(gè)變量影響的最值問(wèn)題。討論的是調(diào)度模型在一個(gè)時(shí)間段內(nèi)的靜態(tài)方案，若其中的變量發(fā)生改變，再重新計(jì)算并考慮卡車等待時(shí)間最短的情況，則可以實(shí)現(xiàn)卡車的實(shí)時(shí)調(diào)度策略。遺傳算法為解決最值問(wèn)題提供了一種高效的解法，并根據(jù)生產(chǎn)情況的數(shù)據(jù)，結(jié)合遺傳算法的交叉、變異、最優(yōu)個(gè)體保存等方面在卡車調(diào)度問(wèn)題的特點(diǎn)進(jìn)行了測(cè)試，驗(yàn)證了方法的有效性。

[1]劉海娟.大型露天礦卡車實(shí)時(shí)調(diào)度系統(tǒng)的遺傳算法研究[D].阜新:遼寧工程技術(shù)大學(xué),2003.

[2]Miettinen.K.M.Nonlinear-Multiobjective-Optimization[M].Boston,London,Dordrecht:KluwerAcademicPublishers, 1999.

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

[4]楊令杰,李克民,王斌.露天礦卡車調(diào)度的理論與方法研究[J].露天采礦技術(shù),2006(4):12-14.

[5]解連江,邢軍,孫效玉.露天礦應(yīng)用汽車調(diào)度系統(tǒng)提高效率的預(yù)測(cè)方法[J].礦業(yè)工程,2004(3):13-16.

[6]孫效玉.露天礦卡車調(diào)度系統(tǒng)結(jié)構(gòu)及面向?qū)ο髮?shí)現(xiàn)方法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào):自然科學(xué)版,2006(1):17-20.

Research of Truck Dispatch Model Based on Genetic Algorithm

WANG Yang1, WANG Shan-dong2

(1.School of Computer Science and Technology, Anhui University of Technology, Maanshan Anhui 243032, China;2.School of Earth Sciences and Engineering, Hohai University, Nanjing Jiangsu 210098,China)

In the production of open pit mine, the establishment of reasonable mine truck dispatching scheme is an effective way to improve the efficiency and reduce the cost of mining and transportation equipment. Through analysis of various parameters of vehicle scheduling in mine production, this paper establishes a multi-objective function and a series of key factors as the constraint conditions of the vehicle scheduling model, and uses the genetic algorithm to solve the problem, and determines the actual scheduling scheme to meet the demand of production.

open pit mine; truck dispatch; multi-objective function; genetic algorithm

2015-06-08

汪 洋(1987- )，男，安徽馬鞍山人，安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，從事物聯(lián)網(wǎng)技術(shù)、計(jì)算機(jī)應(yīng)用研究。

TP393

A

2095-7602(2015)10-0038-04