基于NSGA-Ⅲ和道路運輸能力飽和度的露天礦卡車調度優化方法

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

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

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

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

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

1 露天礦卡車調度多目標優化模型

1.1 目標函數

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

露天礦卡車調度模型概述如下:某露天礦實際開采中,有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 個班次產量的最低需求量為Q3j(t),第j個破碎站的品位要求上限為Q4j(%),第j個破碎站的品位值要求下限為Q5j(%);在裝載點i和卸載點j之間的道路上運行1 趟的時間為T2ij(h);從i個裝載點到j個卸載點最多能同時運行的卡車數為Aij(輛);1 個班次中,每輛卡車在這條路線上最多可以運行的次數為Bij;Xijz為第z輛卡車從第i個裝載點到第j個卸載點次數。

模型的每一個目標函數由一個函數表示,所有的調度參數統稱為X,構建的多目標優化目標函數如下:

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

1.2 約束條件

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

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

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

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

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

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

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

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

2 露天礦卡車調度多目標遺傳算法

2.1 多目標遺傳算法

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

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

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

2.2 算法核心思想

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

2.2.1 歸一化

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

式中,St表示種群個體。

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

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

2.2.2 參考點的確定

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

2.2.3 關鍵層解的選擇策略

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

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

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

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

2.3 測試函數

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

目標函數:

約束條件:

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

圖2 測試函數優化結果Fig.2 Test function optimization results

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

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

3.1 實時調度參數

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

卸載點j的卡車飽和度系數:

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

裝載點i的卡車飽和度系數:

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

道路R的飽和度率系數

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

當卡車申請調度,根據車流規劃,計算所有可以選擇的道路的Kij,Qij,Mij。有了以上參數的計算結果之后,根據調度準則對當前卡車進行下一步安排。

3.2 實時調度準則

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

準則1:將卡車T固定在道路R上運輸,直到卡車申請調度。當卡車申請調度,轉到準則2。

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

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

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

調度完成后,更新各卡車的完成量。

實時調度流程如圖3所示。

圖3 實時調度流程圖Fig.3 Flow chart of real-time scheduling

3.3 實時調度模型實現的目標

實時調度準則1和準則2,當礦山系統穩定時,實現車流規劃的目標任務。卡車完成所處道路上的任務就申請調度,將卡車按照車流規劃和實時調度準則派往對應的道路上,并固定在這條道路上運輸,直到卡車申請調度。

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

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

3.4 與其他實時調度模型比較

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

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

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

4 案例應用

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

表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

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

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

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

圖5 6 輛卡車時的優化結果Fig.5 Optimization results when there are 6 trucks

圖6 5 輛卡車時的優化結果Fig.6 Optimization results when there are 5 trucks

圖7 4 輛卡車時的優化結果Fig.7 Optimization results when there are 4 trucks

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

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

選擇Pareto 上一組解,車流規劃結果如表5所示。

表5 車流規劃結果Table 5 Traffic flow planning results

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

表6 道路飽和度Table 6 Road saturation

某個時刻,1 號卡車在Ⅰ/Ⅱ道路上運輸,2 號卡車和5 號卡車在Ⅱ/Ⅰ道路上運輸,3 號卡車和4 號卡車在Ⅲ/Ⅳ道路上運輸,當1 號卡車申請調度,需對申請調度的1 號卡車下一步進行安排。根據車流規劃給1 卡車分配的任務,據系統監測,1 號卡車還在Ⅰ/Ⅲ,Ⅱ/Ⅰ,Ⅱ/Ⅱ,Ⅲ/Ⅳ這4 條道路上有任務,并且這些路線都能正常作業,這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

根據表8 可以發現,如果將1 號卡車調往Ⅲ/Ⅳ道路上,道路的飽和度率大于1,卡車一定會在Ⅲ/Ⅳ道路上的裝載點或者卸載點排隊,1 號卡車可以派往Ⅰ/Ⅲ道路和Ⅱ/Ⅰ道路,但不是最好的選擇,派往Ⅱ/Ⅱ道路上,道路飽和度率僅為1/4,道路的擁擠度最小,所以理應將卡車派往Ⅱ/Ⅱ道路上。

5 結 論

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

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

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

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

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

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