基于NSGA-Ⅲ和道路運(yùn)輸能力飽和度的露天礦卡車調(diào)度優(yōu)化方法

譚正華 宋港國(guó) 王李管 文 陽(yáng) 李國(guó)泰

(1.湘潭大學(xué)計(jì)算機(jī)學(xué)院,湖南 湘潭 411105;2.湘潭大學(xué)網(wǎng)絡(luò)空間安全學(xué)院,湖南 湘潭 411105;3.中南大學(xué)數(shù)字礦山研究中心,湖南 長(zhǎng)沙 410083)

礦業(yè)歷經(jīng)了機(jī)械化、自動(dòng)化時(shí)代,如今正步入智慧化時(shí)代[1-2],智能化和數(shù)字化是礦山發(fā)展的趨勢(shì),其中卡車調(diào)度的優(yōu)化是露天礦山智能化建設(shè)的研究熱點(diǎn)之一[3-5]。在露天礦的開(kāi)采過(guò)程中,卡車的運(yùn)輸費(fèi)用占了整個(gè)礦山生產(chǎn)成本的50%以上,卡車的非作業(yè)時(shí)間占了30%以上,合理高效地利用礦山設(shè)備不但可以減少對(duì)設(shè)備的損耗,也進(jìn)一步降低礦山的生產(chǎn)成本,有效提升企業(yè)的市場(chǎng)競(jìng)爭(zhēng)能力[6]。

國(guó)內(nèi)外對(duì)露天礦卡車調(diào)度方法研究的文獻(xiàn)較多,White J W 等[7-9]提出了兩階段法,該方法在LINGO上用數(shù)學(xué)方法求解線性規(guī)劃模型,用動(dòng)態(tài)規(guī)劃求解實(shí)時(shí)調(diào)度模型。20 世紀(jì)70 年代末,美國(guó)Modular 公司開(kāi)發(fā)的DISPATCH 調(diào)度系統(tǒng)就已經(jīng)應(yīng)用到實(shí)際的露天礦中。Souza 等[10]提出了混合式啟發(fā)算法,趙勇等[11]提出了基于流率飽和度的露天礦卡車調(diào)度,邢軍等[12]提出了基于產(chǎn)量完成飽和度的露天礦卡車調(diào)度。這些研究大多數(shù)基于礦山單個(gè)指標(biāo)建立單目標(biāo)車流規(guī)劃模型對(duì)卡車進(jìn)行調(diào)度,而企業(yè)通常需要解決涉及多個(gè)目標(biāo)的問(wèn)題,這些目標(biāo)往往相互沖突,需要尋求最優(yōu)的方案。

露天礦卡車調(diào)度已經(jīng)由單目標(biāo)問(wèn)題轉(zhuǎn)向多目標(biāo)問(wèn)題,多目標(biāo)加權(quán)成單目標(biāo)方法向多目標(biāo)進(jìn)化算法轉(zhuǎn)化,多目標(biāo)優(yōu)化是一種考慮多種指標(biāo)的尋優(yōu)策略,更符合于實(shí)際問(wèn)題的多種決策需求。在車流規(guī)劃上,本研究以露天礦卡車總運(yùn)輸量和卡車非作業(yè)時(shí)間最小為目標(biāo)函數(shù),構(gòu)建了露天礦卡車調(diào)度的車流規(guī)劃模型,并基于多目標(biāo)遺傳算法在MATLAB 軟件上求解。在實(shí)時(shí)調(diào)度上,本研究提出了一種基于道路運(yùn)輸能力飽和度的實(shí)時(shí)調(diào)度策略,并且和固定派車法組成綜合派車方案。

1 露天礦卡車調(diào)度多目標(biāo)優(yōu)化模型

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

露天礦卡車調(diào)度是一個(gè)復(fù)雜系統(tǒng)工程,實(shí)際問(wèn)題經(jīng)常涉及多個(gè)目標(biāo),這些目標(biāo)往往是復(fù)雜沖突的。綜合考慮礦山卡車調(diào)度的諸多因素,以卡車總運(yùn)輸量(t·km)最小,卡車非作業(yè)時(shí)間(h)最小為目標(biāo)構(gòu)建多目標(biāo)優(yōu)化調(diào)度模型[13-14]。

露天礦卡車調(diào)度模型概述如下:某露天礦實(shí)際開(kāi)采中,有m個(gè)裝載點(diǎn)Ai(i=1,2,…,m),有n個(gè)卸載點(diǎn)Bj(j=1,2,…,n),k輛卡車Cz(z=1,2,…,k),卸載點(diǎn)包括n1個(gè)破碎站和n2個(gè)渣場(chǎng);裝載點(diǎn)效率為T(mén)1(h/次),卸載點(diǎn)效率為T(mén)2(h/次);裝載點(diǎn)Ai到卸載點(diǎn)Bj的距離為dij(km)(i=1,2,…,m,j=1,2,…,n);卡車的容量為c(t);卡車滿載最大速度為V1(km/h),空載最大速度為V2(km/ h),卡車往返于裝載點(diǎn)與卸載點(diǎn)之間;礦山工作1 個(gè)班時(shí)為T(mén)(h);第i個(gè)裝載點(diǎn)礦石存儲(chǔ)量為Q1i(t),第i個(gè)裝載點(diǎn)巖石存儲(chǔ)量為Q2i(t),第i個(gè)裝載點(diǎn)礦石品位為Pi(%);第j個(gè)卸載點(diǎn)1 個(gè)班次產(chǎn)量的最低需求量為Q3j(t),第j個(gè)破碎站的品位要求上限為Q4j(%),第j個(gè)破碎站的品位值要求下限為Q5j(%);在裝載點(diǎn)i和卸載點(diǎn)j之間的道路上運(yùn)行1 趟的時(shí)間為T(mén)2ij(h);從i個(gè)裝載點(diǎn)到j(luò)個(gè)卸載點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)為Aij(輛);1 個(gè)班次中,每輛卡車在這條路線上最多可以運(yùn)行的次數(shù)為Bij;Xijz為第z輛卡車從第i個(gè)裝載點(diǎn)到第j個(gè)卸載點(diǎn)次數(shù)。

模型的每一個(gè)目標(biāo)函數(shù)由一個(gè)函數(shù)表示,所有的調(diào)度參數(shù)統(tǒng)稱為X,構(gòu)建的多目標(biāo)優(yōu)化目標(biāo)函數(shù)如下:

式中,F1(X)為總運(yùn)輸量;F2(X)為卡車非作業(yè)時(shí)間。

1.2 約束條件

(1)卡車從裝載點(diǎn)運(yùn)輸出去的總量不能超過(guò)裝載點(diǎn)的存儲(chǔ)量。

(2)產(chǎn)量不能低于卸載點(diǎn)的最低需求。

(3)1 個(gè)班次內(nèi),不能超過(guò)裝載點(diǎn)的最大裝車次數(shù)。

(4)1 個(gè)班次內(nèi),不能超過(guò)卸載點(diǎn)的最大卸車次數(shù)。

(5)滿足破碎站(裝載點(diǎn)包括破碎站和渣場(chǎng))的品位限制。

(6)卡車運(yùn)行1 個(gè)周期的時(shí)間包括重車行駛時(shí)間,空車行駛時(shí)間,卡車在裝載點(diǎn)的裝載時(shí)間,在卸載點(diǎn)的卸載時(shí)間。超過(guò)道路的飽和度,卡車在裝載點(diǎn)或者卸載點(diǎn)會(huì)排隊(duì)等候。

(7)不能超過(guò)卡車數(shù)量。

針對(duì)以上構(gòu)建的多目標(biāo)數(shù)學(xué)模型,本研究引入NSGA-Ⅲ算法進(jìn)行求解。

2 露天礦卡車調(diào)度多目標(biāo)遺傳算法

2.1 多目標(biāo)遺傳算法

1975 年由美國(guó)J.Holland 首次提出的遺傳算法(Genetic algorithm)[15]是一種隨機(jī)搜索方法,其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,不存在求導(dǎo)和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法,遺傳算法可以自動(dòng)獲取并引導(dǎo)優(yōu)化后的搜索空間,自適應(yīng)調(diào)整搜索方向,無(wú)需特定規(guī)則。

由式(1)可以看出來(lái):2 個(gè)目標(biāo)是沖突的,一個(gè)目標(biāo)變優(yōu),會(huì)導(dǎo)致另外一個(gè)目標(biāo)變差,如果降低總運(yùn)輸量,就會(huì)使得卡車的非作業(yè)時(shí)間增大,從而降低了設(shè)備的使用率。多目標(biāo)優(yōu)化問(wèn)題[16],目標(biāo)往往是沖突的,需要找到平衡的折中解,因此引入Pareto 最優(yōu)化理論。如果解x1在所有目標(biāo)函數(shù)上的效果都比x2好,則稱x1支配x2,如果在解集中,不存在任何一個(gè)解支配x2,則稱x2為非支配解。所有的非支配解在笛卡爾坐標(biāo)系下構(gòu)成一個(gè)Pareto 前沿面。

對(duì)車流規(guī)劃數(shù)學(xué)模型的解算,采用的是NSGA-Ⅱ算法[17],這是一種基于參考點(diǎn)的多目標(biāo)進(jìn)化算法。

2.2 算法核心思想

NSGA-Ⅲ是一種基于參考點(diǎn)的多目標(biāo)進(jìn)化算法,它與NSGA-ⅡⅠ[18]本質(zhì)的區(qū)別在選擇的機(jī)制上,本文不再贅述與NSGA-Ⅱ的相同的部分,只闡述優(yōu)化問(wèn)題求解過(guò)程中NSGA-Ⅲ的關(guān)鍵步驟。

2.2.1 歸一化

遍歷M個(gè)目標(biāo)函數(shù)在每個(gè)目標(biāo)維度i上的最小值,構(gòu)成最小數(shù)值集合,按照下式標(biāo)量化集合中的數(shù)值,可將目標(biāo)函數(shù)fi(x) 轉(zhuǎn)化為:

式中,St表示種群個(gè)體。

完成這一步后,接下來(lái)尋找極值點(diǎn),為歸一化做準(zhǔn)備,需要用到一個(gè)名為ASF的函數(shù),該函數(shù)定義如下:

接著遍歷每個(gè)目標(biāo)函數(shù),找到使得ASF數(shù)值最小的個(gè)體,這些個(gè)體就是Extreme Points,然后根據(jù)這些點(diǎn)的具體函數(shù)值,計(jì)算出對(duì)應(yīng)坐標(biāo)軸上的截距,截距的實(shí)際意義是每個(gè)坐標(biāo)點(diǎn)在對(duì)應(yīng)坐標(biāo)軸上的坐標(biāo)值,將其記錄為ai。得到ai和Zi的具體數(shù)值以后,計(jì)算歸一化的公式如下所示:

2.2.2 參考點(diǎn)的確定

歸一化后,NSGA-Ⅲ的參考點(diǎn)可在歸一化的超平面內(nèi)進(jìn)行:當(dāng)有M個(gè)目標(biāo)函數(shù)時(shí),則可以圍成M-1 個(gè)歸一化超平面,假定沿著每一個(gè)目標(biāo)函數(shù)所在軸進(jìn)行p等分的話,則參考點(diǎn)可以選擇H個(gè)。

2.2.3 關(guān)鍵層解的選擇策略

每個(gè)參考點(diǎn)可存在2 種情況,可能有一個(gè)或多個(gè)種群成員與它相關(guān),或者不需要任何種群成員與它關(guān)聯(lián)。

參考點(diǎn)設(shè)定之后,將已經(jīng)在種群中的每個(gè)解都關(guān)聯(lián)到一個(gè)參考點(diǎn),關(guān)聯(lián)之后,每個(gè)參考點(diǎn)j都會(huì)有1個(gè)與它關(guān)聯(lián)的解的數(shù)量ρj。然后對(duì)ρj分情況討論:① 如果這個(gè)參考點(diǎn)關(guān)聯(lián)的種群個(gè)體數(shù)量ρj為零,但在第N層級(jí)的種群中有個(gè)體被關(guān)聯(lián)到這個(gè)參考點(diǎn)向量,則從中尋找距離最小的點(diǎn),并將其從N中抽取,加入到被選擇的下一代種群中,設(shè)置ρj =ρj +1;② 如果在N中沒(méi)有個(gè)體被引用到該參考點(diǎn),則刪除該參考點(diǎn)向量,如果ρj ＞0,則從中選擇距離最近的參考點(diǎn)直到種群規(guī)模為N為止。

NSGA-Ⅲ流程圖如圖1所示。

圖1 NSGA-Ⅲ流程圖Fig.1 NSGA-Ⅲ flow chart

2.3 測(cè)試函數(shù)

采用常被用作檢測(cè)多目標(biāo)進(jìn)化算法搜索能力的多目標(biāo)帶約束的測(cè)試函數(shù)驗(yàn)證NSGA-Ⅲ算法的尋優(yōu)性,以保證案例應(yīng)用時(shí)候的準(zhǔn)確性和可行性。

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

約束條件:

種群數(shù)量設(shè)置成100,采用實(shí)數(shù)編碼,錦標(biāo)賽選擇,交叉算子設(shè)置為0.9,變異算子設(shè)置為0.01,迭代10 000 次,求解后優(yōu)化結(jié)果如圖2所示。Pareto 最優(yōu)解集提供了多組解可供選擇,并且分布均勻,具有良好的前沿面。

圖2 測(cè)試函數(shù)優(yōu)化結(jié)果Fig.2 Test function optimization results

3 道路運(yùn)輸能力飽和度和固定派車法的綜合實(shí)時(shí)調(diào)度策略

本文提出的道路運(yùn)輸能力飽和度和固定派車法[19-20]的實(shí)時(shí)調(diào)度由3 個(gè)基本參數(shù)和3 個(gè)準(zhǔn)則組成。

3.1 實(shí)時(shí)調(diào)度參數(shù)

在裝載點(diǎn)i與卸載點(diǎn)j之間的道路R上,Tij是卡車運(yùn)行一個(gè)周期的時(shí)間,包括重車和空車的行駛時(shí)間、裝載時(shí)間、卸載時(shí)間;t1ij為卸載點(diǎn)j卸載時(shí)間;t2ij為裝載點(diǎn)i裝載時(shí)間;Aij為道路R中的卡車數(shù)量。

卸載點(diǎn)j的卡車飽和度系數(shù):

表示因受限于卸載點(diǎn)的卸載能力,這條道路上最大的卡車數(shù)不能超過(guò)Kij,如果超過(guò),卡車一定會(huì)在卸載點(diǎn)排隊(duì)。

裝載點(diǎn)i的卡車飽和度系數(shù):

表示因受限于裝載點(diǎn)的裝載能力,這條道路上最大的卡車數(shù)不能超過(guò)Qij,如果超過(guò),卡車一定會(huì)在裝載點(diǎn)排隊(duì)。

道路R的飽和度率系數(shù)

道路R上,min{Kij,Qij} 表示道路飽和度;當(dāng)Mij大于1,卡車在裝載點(diǎn)或卸載點(diǎn)一定會(huì)發(fā)生排隊(duì)。

當(dāng)卡車申請(qǐng)調(diào)度,根據(jù)車流規(guī)劃,計(jì)算所有可以選擇的道路的Kij,Qij,Mij。有了以上參數(shù)的計(jì)算結(jié)果之后,根據(jù)調(diào)度準(zhǔn)則對(duì)當(dāng)前卡車進(jìn)行下一步安排。

3.2 實(shí)時(shí)調(diào)度準(zhǔn)則

卡車T在i號(hào)卸載點(diǎn)和j號(hào)卸載點(diǎn)間的道路R上,將按照以下3 條實(shí)時(shí)調(diào)度準(zhǔn)則對(duì)卡車進(jìn)行安排。

準(zhǔn)則1:將卡車T固定在道路R上運(yùn)輸,直到卡車申請(qǐng)調(diào)度。當(dāng)卡車申請(qǐng)調(diào)度,轉(zhuǎn)到準(zhǔn)則2。

準(zhǔn)則2:檢查卡車T在R上的任務(wù)是否完成,如果完成,說(shuō)明礦山系統(tǒng)正常,再檢查卡車T在其他可以正常工作的道路上的運(yùn)輸任務(wù)是否完成,如果在別的道路上還有任務(wù)沒(méi)有完成,基于道路飽和度將卡車T調(diào)往相應(yīng)的道路R'去;如果卡車T在道路R上的任務(wù)沒(méi)有完成,說(shuō)明道路R上某個(gè)環(huán)節(jié)出現(xiàn)了問(wèn)題,轉(zhuǎn)到準(zhǔn)則3。

準(zhǔn)則3: 處理礦山系統(tǒng)因?yàn)槿魏问乱驅(qū)е耰號(hào)卸載點(diǎn)和j號(hào)裝載點(diǎn)無(wú)法正常工作的情況[21]。檢查卡車T在其他可以正常工作的道路上的運(yùn)輸任務(wù)是否完成,如果完成,卡車T停止工作;如果沒(méi)有完成,則基于道路飽和度將卡車調(diào)往相應(yīng)的道路R'去,并固定在R'上,直到卡車T申請(qǐng)調(diào)度。礦山系統(tǒng)恢復(fù)正常后,卡車T需完成相應(yīng)的任務(wù)。

以道路飽和度率系數(shù)Mij作為道路選擇參數(shù),準(zhǔn)則2和準(zhǔn)則3 將卡車派往到派往后道路飽和度率系數(shù)最小的Mmin對(duì)應(yīng)的道路上。

調(diào)度完成后,更新各卡車的完成量。

實(shí)時(shí)調(diào)度流程如圖3所示。

圖3 實(shí)時(shí)調(diào)度流程圖Fig.3 Flow chart of real-time scheduling

3.3 實(shí)時(shí)調(diào)度模型實(shí)現(xiàn)的目標(biāo)

實(shí)時(shí)調(diào)度準(zhǔn)則1和準(zhǔn)則2,當(dāng)?shù)V山系統(tǒng)穩(wěn)定時(shí),實(shí)現(xiàn)車流規(guī)劃的目標(biāo)任務(wù)。卡車完成所處道路上的任務(wù)就申請(qǐng)調(diào)度,將卡車按照車流規(guī)劃和實(shí)時(shí)調(diào)度準(zhǔn)則派往對(duì)應(yīng)的道路上,并固定在這條道路上運(yùn)輸,直到卡車申請(qǐng)調(diào)度。

實(shí)時(shí)調(diào)度準(zhǔn)則3,對(duì)礦山系統(tǒng)不確定因素導(dǎo)致的特殊情況進(jìn)行調(diào)度處理。當(dāng)出現(xiàn)諸如裝載點(diǎn)卸載點(diǎn)臨時(shí)關(guān)閉,天氣原因或者車禍等等導(dǎo)致道路臨時(shí)封閉等一系列意外情況,卡車申請(qǐng)調(diào)度,對(duì)卡車進(jìn)行安排。

實(shí)時(shí)調(diào)度準(zhǔn)則在實(shí)現(xiàn)上述2 種目標(biāo)的時(shí)候,有以下幾個(gè)優(yōu)點(diǎn):卡車固定在某條道路,直到完成這條道路上的任務(wù)或者完成任務(wù)之前道路出現(xiàn)特殊情況,卡車才申請(qǐng)調(diào)度,這樣可以避免卡車頻繁的調(diào)動(dòng),節(jié)約礦山的成本和時(shí)間;不增加新的物理參數(shù),只以道路飽和度率系數(shù)作為基礎(chǔ);整個(gè)實(shí)時(shí)調(diào)度模型的目標(biāo)十分明確,盡最大可能保障卡車在裝載點(diǎn)和卸載點(diǎn)不排隊(duì)的同時(shí),完成車流規(guī)劃的目標(biāo)任務(wù)。

3.4 與其他實(shí)時(shí)調(diào)度模型比較

建立裝卸點(diǎn)路徑列表和卡車任務(wù)列表,分別存儲(chǔ)LP 需車路徑和申請(qǐng)調(diào)度的卡車,優(yōu)先級(jí)從列表自上而下依次遞減。根據(jù)LP 生產(chǎn)路徑下一次需要分配卡車到該路線上的預(yù)期時(shí)間,對(duì)LP 生產(chǎn)路徑排序,預(yù)期時(shí)間最短者為最需分配卡車的LP 的生產(chǎn)路徑,放在裝卸點(diǎn)路徑列表的第一行;根據(jù)卡車請(qǐng)求和即將申請(qǐng)調(diào)度的時(shí)間對(duì)卡車進(jìn)行排序,申請(qǐng)調(diào)度時(shí)間最近者位于列表的第一行。然后依據(jù)預(yù)測(cè)的礦石損失噸位,將卡車任務(wù)列表中的所有卡車和裝卸點(diǎn)路徑列表進(jìn)行匹配計(jì)算,將損失噸位最小者所對(duì)應(yīng)的卡車派往最需車路線上去。DP 調(diào)度的優(yōu)勢(shì)在于兼顧已經(jīng)申請(qǐng)調(diào)度和即將申請(qǐng)調(diào)度的卡車,從理論上而言,這是一種最佳配車方案,但在實(shí)際應(yīng)用中也存在問(wèn)題。動(dòng)態(tài)規(guī)劃調(diào)度算法是基于預(yù)測(cè)的,包括對(duì)需求時(shí)間和損失噸位的預(yù)測(cè),在實(shí)際應(yīng)用中預(yù)測(cè)的準(zhǔn)確性很難把握,如果預(yù)測(cè)的時(shí)間過(guò)長(zhǎng),對(duì)預(yù)測(cè)的準(zhǔn)確性很難把握,最大預(yù)測(cè)時(shí)間不能超過(guò)LP 最需車路徑中的最短運(yùn)行時(shí)間,如果預(yù)測(cè)的時(shí)間過(guò)短,則會(huì)造成每個(gè)時(shí)間段內(nèi)可以統(tǒng)籌考慮的卡車數(shù)量過(guò)少,優(yōu)化的實(shí)際意義不大;DP 調(diào)度不適合重車情形,需要單獨(dú)處理重車調(diào)度;單個(gè)經(jīng)濟(jì)指標(biāo)實(shí)現(xiàn)礦山卡車的分配。

Souza 等提出的混合式啟發(fā)算法,結(jié)合貪心隨機(jī)自適應(yīng)搜索程序和一般變量領(lǐng)域搜索,優(yōu)化了卡車調(diào)度中最少派車方案問(wèn)題,這個(gè)方法雖然采用了進(jìn)化算法增強(qiáng)了尋優(yōu)能力,但這是一單個(gè)經(jīng)濟(jì)指標(biāo)實(shí)現(xiàn)礦山卡車的分配。

基于流率飽和度的露天礦卡車調(diào)度和基于產(chǎn)量完成飽和度的露天礦卡車調(diào)度,同樣是單個(gè)經(jīng)濟(jì)指標(biāo)實(shí)現(xiàn)礦山卡車的分配,而且沒(méi)法預(yù)測(cè)到下一次調(diào)度對(duì)卡車排隊(duì)的影響,對(duì)于已經(jīng)排隊(duì)等候時(shí)間過(guò)長(zhǎng)的卡車,系統(tǒng)需做出預(yù)警警報(bào),并將卡車重新調(diào)度。

4 案例應(yīng)用

某露天礦礦區(qū)有5 個(gè)裝載點(diǎn),4 個(gè)卸載點(diǎn),運(yùn)量為100 t 的卡車10 輛,由北斗導(dǎo)航監(jiān)測(cè)系統(tǒng)測(cè)到各裝載點(diǎn)和卸載點(diǎn)之間的距離如表1所示,裝載點(diǎn)的存儲(chǔ)量和品位信息如表2所示,裝載點(diǎn)有3 個(gè)破碎站,1個(gè)班時(shí)的需求如表3所示。為了方便標(biāo)識(shí)裝載點(diǎn)、卸載點(diǎn)、道路、卡車,裝載點(diǎn)和卸載點(diǎn)依次用羅馬數(shù)字標(biāo)識(shí),卸載點(diǎn)i到裝載點(diǎn)j的道路用i/j標(biāo)識(shí),卡車依次用阿拉伯?dāng)?shù)字標(biāo)識(shí)。

表1 裝載點(diǎn)與卸載點(diǎn)之間的距離Table 1 Distance between loading point and unloading point

表2 裝載點(diǎn)的存儲(chǔ)量和品位信息Table 2 Storage capacity and taste information of the loading point

表3 卸載點(diǎn)1 個(gè)班時(shí)的任務(wù)需求Table 3 Task requirements for one shift at the unloading point

對(duì)于這樣一個(gè)礦山,決策變量定義為單輛卡車在每條道路上的車次,所以決策變量的個(gè)數(shù)為200 個(gè),約束條件個(gè)數(shù)50 個(gè),在MATLAB 平臺(tái)上編制NSGA-Ⅲ多目標(biāo)遺傳算法進(jìn)行優(yōu)化求解,其中種群數(shù)量設(shè)置為100,采用實(shí)數(shù)編碼,錦標(biāo)賽選擇,交叉算子設(shè)置為0.9,變異算子設(shè)置為0.01,得到優(yōu)化方案的Pareto最優(yōu)解集如圖4所示。

圖4 10 輛卡車場(chǎng)景下的露天礦實(shí)例優(yōu)化結(jié)果Fig.4 The optimization results of the open-pit mine example in the scene of 10 trucks

圖4 中,f1表示總運(yùn)輸量,f2表示卡車非作業(yè)時(shí)間。從圖4 可以看出,NSGA-Ⅲ求解得到了問(wèn)題的若干個(gè)理想解,解集構(gòu)成的Pareto 前沿面分布均勻,收斂性好,相比較單目標(biāo)優(yōu)化用數(shù)學(xué)的方法得到單個(gè)解,Pareto 最優(yōu)解集能給調(diào)度人員提供更多的選擇,調(diào)度工作人員可以根據(jù)礦山實(shí)際需求,合理地選擇派車方案進(jìn)行作業(yè),達(dá)到總運(yùn)輸量最小并且充分利用卡車的目的。本研究通過(guò)依次減少卡車數(shù)量,得到完成礦山既定任務(wù)所需最少卡車數(shù)量,并得出每輛卡車的車流規(guī)劃,如圖5～圖7所示。

圖5 6 輛卡車時(shí)的優(yōu)化結(jié)果Fig.5 Optimization results when there are 6 trucks

圖6 5 輛卡車時(shí)的優(yōu)化結(jié)果Fig.6 Optimization results when there are 5 trucks

圖7 4 輛卡車時(shí)的優(yōu)化結(jié)果Fig.7 Optimization results when there are 4 trucks

根據(jù)圖4～圖6,卡車數(shù)量從6 輛到4 輛,總運(yùn)輸量基本不變的情況下,卡車非作業(yè)時(shí)間快速減少,但在4 輛卡車時(shí),卡車非作業(yè)時(shí)間出現(xiàn)了負(fù)數(shù),說(shuō)明4輛卡車無(wú)法完成礦山的任務(wù),因此得出在當(dāng)前礦山情景下,最少5 輛卡車才能完成礦山的任務(wù)需求。以5輛卡車為例,各方案指標(biāo)如表4所示。

表4 5 輛卡車各方案指標(biāo)Table 4 Indicators of each program when there are 5 trucks

選擇Pareto 上一組解,車流規(guī)劃結(jié)果如表5所示。

表5 車流規(guī)劃結(jié)果Table 5 Traffic flow planning results

每條道路飽和度如表6所示。

表6 道路飽和度Table 6 Road saturation

某個(gè)時(shí)刻,1 號(hào)卡車在Ⅰ/Ⅱ道路上運(yùn)輸,2 號(hào)卡車和5 號(hào)卡車在Ⅱ/Ⅰ道路上運(yùn)輸,3 號(hào)卡車和4 號(hào)卡車在Ⅲ/Ⅳ道路上運(yùn)輸,當(dāng)1 號(hào)卡車申請(qǐng)調(diào)度,需對(duì)申請(qǐng)調(diào)度的1 號(hào)卡車下一步進(jìn)行安排。根據(jù)車流規(guī)劃給1 卡車分配的任務(wù),據(jù)系統(tǒng)監(jiān)測(cè),1 號(hào)卡車還在Ⅰ/Ⅲ,Ⅱ/Ⅰ,Ⅱ/Ⅱ,Ⅲ/Ⅳ這4 條道路上有任務(wù),并且這些路線都能正常作業(yè),這4條道路的飽和度率如表7所示。

表7 道路當(dāng)前的道路飽和度率Table 7 The current road saturation rate of the road

將卡車分別派往Ⅰ/Ⅲ,Ⅱ/Ⅰ,Ⅱ/Ⅱ,Ⅲ/Ⅳ這4條道路,4 條道路的飽和度率如表8所示。

表8 卡車派往后的道路飽和度率Table 8 Road saturation rate after trucks are dispatched

根據(jù)表8 可以發(fā)現(xiàn),如果將1 號(hào)卡車調(diào)往Ⅲ/Ⅳ道路上,道路的飽和度率大于1,卡車一定會(huì)在Ⅲ/Ⅳ道路上的裝載點(diǎn)或者卸載點(diǎn)排隊(duì),1 號(hào)卡車可以派往Ⅰ/Ⅲ道路和Ⅱ/Ⅰ道路,但不是最好的選擇,派往Ⅱ/Ⅱ道路上,道路飽和度率僅為1/4,道路的擁擠度最小,所以理應(yīng)將卡車派往Ⅱ/Ⅱ道路上。

5 結(jié) 論

基于多目標(biāo)進(jìn)化算法優(yōu)化理論,綜合考慮露天礦卡車調(diào)度各方面影響因素,以總運(yùn)輸量最少,卡車非作業(yè)時(shí)間最少,構(gòu)建2 個(gè)互斥的雙目標(biāo)優(yōu)化車流規(guī)劃數(shù)學(xué)模型。由于卡車排隊(duì)浪費(fèi)過(guò)多的時(shí)間以及卡車在行駛和停止?fàn)顟B(tài)下切換耗油較多,該模型考慮每條道路上裝載點(diǎn)和卸載點(diǎn)的飽和度,最大限度避免卡車在裝載點(diǎn)和卸載點(diǎn)排隊(duì)。經(jīng)NSGA-Ⅲ算法解算,可以得出最少派車數(shù)量,以及給已經(jīng)規(guī)劃好的路線分配派車任務(wù)。

基于道路飽和度率的調(diào)度策略,與固定派車法組成綜合實(shí)時(shí)調(diào)度模型,有如下幾個(gè)特點(diǎn):

(1)在礦山系統(tǒng)正常時(shí),完成車流規(guī)劃的同時(shí),盡可能減緩道路擁擠程度,避免調(diào)度卡車而引起裝載點(diǎn)或者卸載點(diǎn)排隊(duì),節(jié)省了礦山運(yùn)輸成本;避免了卡車司機(jī)隨意申請(qǐng)調(diào)度,浪費(fèi)太多時(shí)間在車流轉(zhuǎn)移上。

(2)在遇到特殊情況時(shí),該實(shí)數(shù)調(diào)度模型無(wú)需考慮何種特殊情況,只需考慮最終對(duì)裝載點(diǎn)和卸載點(diǎn)的影響。

(3)不增加新的物理參數(shù),只以道路飽和度率系數(shù)作為基礎(chǔ),與國(guó)外流行的動(dòng)態(tài)規(guī)劃模型相比,算法簡(jiǎn)潔合理,適應(yīng)性強(qiáng),適用面廣。

該方法也存在需要改進(jìn)的地方:實(shí)時(shí)調(diào)度階段,為了減緩道路擁擠度,將卡車派往最不擁擠的道路上去,可能會(huì)造成裝載點(diǎn)的鏟車啟動(dòng)工作一會(huì)又陷入長(zhǎng)時(shí)間等待,然后又啟動(dòng),又等待周而復(fù)始的過(guò)程中,導(dǎo)致鏟車效率不高。