譚正華 宋港國 王李管 文 陽 李國泰

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

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

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

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

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

1.1 目標函數(shù)

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

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

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

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

1.2 約束條件

(1)卡車從裝載點運輸出去的總量不能超過裝載點的存儲量。

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

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

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

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

(6)卡車運行1 個周期的時間包括重車行駛時間,空車行駛時間,卡車在裝載點的裝載時間,在卸載點的卸載時間。超過道路的飽和度,卡車在裝載點或者卸載點會排隊等候。

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

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

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

2.1 多目標遺傳算法

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

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

對車流規(guī)劃數(shù)學模型的解算,采用的是NSGA-Ⅱ算法[17],這是一種基于參考點的多目標進化算法。

2.2 算法核心思想

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

2.2.1 歸一化

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

式中,St表示種群個體。

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

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

2.2.2 參考點的確定

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

2.2.3 關鍵層解的選擇策略

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

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

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

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

2.3 測試函數(shù)

采用常被用作檢測多目標進化算法搜索能力的多目標帶約束的測試函數(shù)驗證NSGA-Ⅲ算法的尋優(yōu)性,以保證案例應用時候的準確性和可行性。

目標函數(shù):

約束條件:

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實時調(diào)度準則

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

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

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

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

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

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

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

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

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

實時調(diào)度準則1和準則2,當?shù)V山系統(tǒng)穩(wěn)定時,實現(xiàn)車流規(guī)劃的目標任務?？ㄜ囃瓿伤幍缆飞系娜蝿站蜕暾堈{(diào)度,將卡車按照車流規(guī)劃和實時調(diào)度準則派往對應的道路上,并固定在這條道路上運輸,直到卡車申請調(diào)度。

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

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

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

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

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

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

4 案例應用

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

表1 裝載點與卸載點之間的距離Table 1 Distance between loading point and unloading point

表2 裝載點的存儲量和品位信息Table 2 Storage capacity and taste information of the loading point

表3 卸載點1 個班時的任務需求Table 3 Task requirements for one shift at the unloading point

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

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

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

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

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

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

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

表4 5 輛卡車各方案指標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

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

表7 道路當前的道路飽和度率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 號卡車調(diào)往Ⅲ/Ⅳ道路上,道路的飽和度率大于1,卡車一定會在Ⅲ/Ⅳ道路上的裝載點或者卸載點排隊,1 號卡車可以派往Ⅰ/Ⅲ道路和Ⅱ/Ⅰ道路,但不是最好的選擇,派往Ⅱ/Ⅱ道路上,道路飽和度率僅為1/4,道路的擁擠度最小,所以理應將卡車派往Ⅱ/Ⅱ道路上。

5 結(jié) 論

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

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

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

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

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

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