權(quán)利要求

1.基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，包括如下步驟：

步驟1，根據(jù)露天礦實(shí)際生產(chǎn)調(diào)度建立主要指標(biāo)體系；

步驟2，以運(yùn)輸成本最小、運(yùn)輸距離最短以及等待時(shí)間最小為目標(biāo)，構(gòu)建金屬露天礦多目標(biāo)調(diào)度模型；

步驟3，對(duì)NSGA-Ⅲ算法進(jìn)行改進(jìn)，得到基于距離支配關(guān)系的NSGA-Ⅲ算法；

步驟4，采用改進(jìn)的算法對(duì)金屬露天礦多目標(biāo)調(diào)度模型進(jìn)行求解。

2.根據(jù)權(quán)利要求1所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述步驟1中，首先獲取露天礦的運(yùn)輸路網(wǎng)數(shù)據(jù)，包括各路段的距離及通行能力；其次，通過(guò)調(diào)取以往的實(shí)際生產(chǎn)數(shù)據(jù)獲取礦山實(shí)際生產(chǎn)中裝、卸載點(diǎn)的產(chǎn)量要求，實(shí)際的裝、卸載所耗費(fèi)的時(shí)間，最后，通過(guò)對(duì)原始的實(shí)際數(shù)據(jù)進(jìn)行分析，得出空載狀態(tài)及重載狀態(tài)下的單位成本，以及日常維護(hù)的費(fèi)用。

3.根據(jù)權(quán)利要求1所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述金屬露天礦多目標(biāo)調(diào)度模型如下：

F(X)＝Minimize(f1(X),f2(X),f3(X))

其中：

minf1(X)表示運(yùn)輸成本最小化，minf2(X)表示運(yùn)輸距離最小化，minf3(X)表示等待時(shí)間最小化，h表示回路個(gè)數(shù)，r＝1,2...,h，xrij表示回路r中從裝載點(diǎn)i到卸載點(diǎn)j的重載運(yùn)輸次數(shù)，dij表示裝載點(diǎn)i到卸載點(diǎn)j的距離，C1表示卡車(chē)重載運(yùn)行狀態(tài)下單位成本，yrji表示回路r中從卸載點(diǎn)j到裝載點(diǎn)i的重載運(yùn)輸次數(shù)，C2表示卡車(chē)空載運(yùn)行狀態(tài)下單位成本，Kr表示第r個(gè)回路上卡車(chē)數(shù)量，T0表示班次時(shí)間，C3表示班次時(shí)間內(nèi)卡車(chē)維修費(fèi)用，Tz表示裝載時(shí)間。

4.根據(jù)權(quán)利要求3所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述金屬露天礦多目標(biāo)調(diào)度模型還包括如下約束條件：

其中，約束條件(4)表示出礦點(diǎn)最小生產(chǎn)任務(wù)要求；約束條件(5)表示出礦點(diǎn)最大生產(chǎn)能力；約束條件(6)表示受礦點(diǎn)最小任務(wù)量要求；約束條件(7)表示受礦點(diǎn)最大生產(chǎn)能力；約束條件(8)表示卸載點(diǎn)礦石品位應(yīng)該在允許范圍內(nèi)；約束條件(9)表示卡車(chē)數(shù)量限制；約束(10)表示在同一回路內(nèi)保證車(chē)輛不擁堵的約束；

m表示裝載點(diǎn)數(shù)目，i＝1,2,...,m，C表示卡車(chē)裝載量，pi表示第i個(gè)裝載點(diǎn)最小任務(wù)量，qi表示第i個(gè)裝載點(diǎn)最大產(chǎn)出量，n表示卸載點(diǎn)數(shù)目，j＝1,2,...,n，gj表示第j個(gè)卸載點(diǎn)最小任務(wù)量，fj表示第j個(gè)卸載點(diǎn)最大承載力，Gi表示第i個(gè)裝載點(diǎn)出礦品位，K表示卡車(chē)數(shù)量，ej表示第j個(gè)卸載點(diǎn)的品位需求，表示卸載點(diǎn)允許的品位波動(dòng)偏差。

5.根據(jù)權(quán)利要求1或3或4所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述對(duì)NSGA-Ⅲ算法進(jìn)行改進(jìn)的方法如下：

在原始NSGA-Ⅲ算法中引入均勻分布的參考點(diǎn)，然后將參考點(diǎn)與原點(diǎn)連接形成參考線，計(jì)算所有個(gè)體到參考線的垂直距離，將個(gè)體與垂直距離最小的參考點(diǎn)關(guān)聯(lián)；通過(guò)快速Pareto非支配排序形成非支配等級(jí)，然后按照由低到高的順序加入歸檔集，在歸檔集種群規(guī)模大于N時(shí)，利用小生境選擇技術(shù)使歸檔集種群規(guī)模為N，改進(jìn)后使用距離支配關(guān)系對(duì)種群進(jìn)行非支配排序，劃分非支配層級(jí)。

6.根據(jù)權(quán)利要求5所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述距離支配關(guān)系是指，如果解X1距離支配解X2，即X1X2，則滿(mǎn)足下列條件：

其中是個(gè)體X1到理想點(diǎn)的歐氏距離，是個(gè)體X2到理想點(diǎn)的歐氏距離，將歐氏距離作為適應(yīng)度值來(lái)選擇更優(yōu)的解，表示兩個(gè)候選解的目標(biāo)值之間的夾角，即是每個(gè)候選解的所屬小生境的大小。

7.根據(jù)權(quán)利要求5所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述設(shè)置為第(|P|/2)個(gè)最小夾角，以保證解集P中非支配解的比值總是在0.5，即，在非支配排序過(guò)程中，使得一半的種群處于非支配層級(jí)。

8.根據(jù)權(quán)利要求5所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，采用基于距離支配關(guān)系的NSGA-Ⅲ算法對(duì)多目標(biāo)調(diào)度模型進(jìn)行求解，具體求解過(guò)程如下：

Step 1確定種群規(guī)模，產(chǎn)生初始父代種群，每一個(gè)種群對(duì)應(yīng)一條運(yùn)行路徑；

Step 2將父代群進(jìn)行交叉、變異的遺傳操作形成新的子代種群；

Step 3將父代種群與子代種群合并；

Step 4按照所述多目標(biāo)調(diào)度模型，計(jì)算合并后種群中所有個(gè)體的目標(biāo)值；

Step 5根據(jù)種群中每個(gè)個(gè)體的目標(biāo)值按照距離支配關(guān)系進(jìn)行非支配排序；

Step 6按照非支配層級(jí)由低到高的順序加入歸檔集，到達(dá)臨界層時(shí)采用小生境選擇技術(shù)使歸檔集種群規(guī)模與初始種群規(guī)模一致；

Step 7判斷是否滿(mǎn)足設(shè)定的迭代次數(shù)這一終止條件，是則結(jié)束算法輸出結(jié)果，否則轉(zhuǎn)Step 2。

9.根據(jù)權(quán)利要求8所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述Step 5中，使用距離支配關(guān)系將種群個(gè)體按照目標(biāo)值進(jìn)行非支配排序，過(guò)程如下：

(1)根據(jù)目標(biāo)函數(shù)f1(X)，f2(X)和f3(X)計(jì)算每個(gè)種群個(gè)體目標(biāo)函數(shù)值，在初始化種群中，每一條運(yùn)行的路徑對(duì)應(yīng)為算法中的一個(gè)個(gè)體；

(2)分別比較每一維目標(biāo)函數(shù)值，選取每一維目標(biāo)函數(shù)值的最小值作為理想點(diǎn)；

(3)計(jì)算種群中每個(gè)個(gè)體與其他個(gè)體之間的最小夾角，從而得出小生境大小并根據(jù)距離支配關(guān)系劃分非支配層級(jí)。

10.根據(jù)權(quán)利要求8所述基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，其特征在于，所述根據(jù)距離支配關(guān)系劃分非支配層級(jí)的方法是：

如果解X1與解X2之間的夾角小于小生境大小，則僅比較兩個(gè)解到理想點(diǎn)之間的距離來(lái)判斷非支配關(guān)系；如果兩個(gè)解之間的夾角大于小生境的大小，則考慮能否在一定區(qū)間內(nèi)保留到理想點(diǎn)較遠(yuǎn)的個(gè)體，進(jìn)而保證種群多樣性。

說(shuō)明書(shū)

技術(shù)領(lǐng)域

本發(fā)明屬于礦業(yè)系統(tǒng)工程及礦山優(yōu)化技術(shù)領(lǐng)域，涉及露天礦車(chē)輛的智能調(diào)配，特別涉及一種基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法。

背景技術(shù)

露天礦生產(chǎn)是集采掘、運(yùn)輸調(diào)度、破碎處理等一系列活動(dòng)的大型生產(chǎn)系統(tǒng)，其中運(yùn)輸調(diào)度是整個(gè)生產(chǎn)系統(tǒng)的關(guān)鍵環(huán)節(jié)。礦車(chē)運(yùn)輸調(diào)度是一個(gè)涉及任務(wù)產(chǎn)量、生產(chǎn)能力、質(zhì)量、設(shè)備利用率和資源問(wèn)題的多目標(biāo)系統(tǒng)，露天礦運(yùn)輸成本占露天礦生產(chǎn)成本的50-60％。根據(jù)實(shí)際生產(chǎn)需求建立優(yōu)化調(diào)度模型，能有效降低企業(yè)的生產(chǎn)運(yùn)營(yíng)成本。從國(guó)內(nèi)外來(lái)看，目前露天礦卡車(chē)運(yùn)輸調(diào)度的實(shí)際生產(chǎn)中，首先在優(yōu)化規(guī)模上大多以小規(guī)模優(yōu)化模擬實(shí)際生產(chǎn)，其次原有的單目標(biāo)及多目標(biāo)等露天礦調(diào)度優(yōu)化模型，大多僅求解出從裝載點(diǎn)在卸載點(diǎn)之間的次數(shù)，無(wú)法有效滿(mǎn)足目前露天礦運(yùn)輸調(diào)度的實(shí)際需求。

發(fā)明內(nèi)容

為了克服上述現(xiàn)有技術(shù)的缺點(diǎn)，本發(fā)明的目的在于提供一種基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，根據(jù)露天礦實(shí)際生產(chǎn)調(diào)度建立了主要的指標(biāo)體，然后以運(yùn)輸成本最小和運(yùn)輸距離最短以及等待時(shí)間最小為目標(biāo)，構(gòu)建金屬露天礦多目標(biāo)調(diào)度模型，再對(duì)基本的NSGA-Ⅲ算法進(jìn)行改進(jìn)，最后采用改進(jìn)的算法對(duì)金屬露天礦多目標(biāo)調(diào)度模型進(jìn)行求解，最終可滿(mǎn)足目前露天礦運(yùn)輸調(diào)度的實(shí)際需求。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案是：

一種基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，包括如下步驟：

步驟1，根據(jù)露天礦實(shí)際生產(chǎn)調(diào)度建立主要指標(biāo)體系；

步驟2，以運(yùn)輸成本最小、運(yùn)輸距離最短以及等待時(shí)間最小為目標(biāo)，構(gòu)建金屬露天礦多目標(biāo)調(diào)度模型；

步驟3，對(duì)NSGA-Ⅲ算法進(jìn)行改進(jìn)，得到基于距離支配關(guān)系的NSGA-Ⅲ算法；

步驟4，采用改進(jìn)的算法對(duì)金屬露天礦多目標(biāo)調(diào)度模型進(jìn)行求解。

與現(xiàn)有技術(shù)相比，本發(fā)明在現(xiàn)有單目標(biāo)調(diào)度優(yōu)化模型的基礎(chǔ)上，引入運(yùn)輸距離與等待時(shí)間最小兩個(gè)目標(biāo)，同時(shí)考慮了礦區(qū)道路的實(shí)際通行能力，構(gòu)建露天礦的金屬露天礦多目標(biāo)調(diào)度優(yōu)化模型。在早期研究中，優(yōu)化調(diào)度主要采用線性規(guī)劃、整數(shù)規(guī)劃以及動(dòng)態(tài)規(guī)劃來(lái)優(yōu)化調(diào)度問(wèn)題。但是由露天礦調(diào)度換進(jìn)復(fù)雜、需求多樣，往往不能得到實(shí)際有效的結(jié)果，本發(fā)明提出的基于距離優(yōu)勢(shì)關(guān)系的NSGA-Ⅲ算法原理簡(jiǎn)單、容易實(shí)現(xiàn)，在求解過(guò)程中能有效保證解的多樣性，并能夠快速求解出滿(mǎn)足要求的解集。

本發(fā)明針對(duì)礦區(qū)的實(shí)際生產(chǎn)需求，建立了完善的運(yùn)輸路徑及運(yùn)輸車(chē)次模型，并能求出可行的解，降低運(yùn)輸成本有著重要的意義。

附圖說(shuō)明

圖1是本發(fā)明中采用基于距離優(yōu)勢(shì)關(guān)系的NSGA-Ⅲ算法求解模型的流程圖。

圖2是本發(fā)明中的基于距離優(yōu)勢(shì)關(guān)系的示意圖，能保證一定區(qū)域內(nèi)相對(duì)收斂性較差但是多樣性較好的解參與進(jìn)化。

具體實(shí)施方式

下面結(jié)合附圖和實(shí)施例詳細(xì)說(shuō)明本發(fā)明的實(shí)施方式。

本發(fā)明為一種基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法，能夠有效減少卡車(chē)調(diào)度過(guò)程中的運(yùn)輸距離和運(yùn)輸次數(shù)，進(jìn)而顯著降低企業(yè)的運(yùn)輸成本，并且在有效保證礦石品位的前提下能提高礦山的生產(chǎn)能力，顯著提升礦山企業(yè)的經(jīng)濟(jì)效益，并且在模型構(gòu)建過(guò)程中做出了路徑規(guī)劃和車(chē)流分配工作。

如圖1所示，其主要包括如下步驟：

步驟1，根據(jù)露天礦實(shí)際生產(chǎn)調(diào)度建立主要指標(biāo)體系，包括運(yùn)輸路網(wǎng)數(shù)據(jù)、生產(chǎn)指標(biāo)要求、運(yùn)算能力數(shù)據(jù)、成本等。

通過(guò)對(duì)露天礦的實(shí)際調(diào)研測(cè)度，首先獲取露天礦的運(yùn)輸路網(wǎng)數(shù)據(jù)，包括各路段的距離及通行能力；其次，通過(guò)調(diào)取以往的實(shí)際生產(chǎn)數(shù)據(jù)獲取礦山實(shí)際生產(chǎn)中裝、卸載點(diǎn)的產(chǎn)量要求，實(shí)際的裝、卸載所耗費(fèi)的時(shí)間。最后，通過(guò)對(duì)原始的實(shí)際數(shù)據(jù)進(jìn)行分析，得出空載狀態(tài)及重載狀態(tài)下的單位成本，以及日常維護(hù)的費(fèi)用。

步驟2，根據(jù)礦山實(shí)際生產(chǎn)要求和指標(biāo)，以運(yùn)輸成本最小、運(yùn)輸距離最短以及等待時(shí)間最小為目標(biāo)，構(gòu)建金屬露天礦多目標(biāo)調(diào)度模型如下：

F(X)＝Minimize(f1(X)，f2(X)，f3(X))

其中：

式中，目標(biāo)函數(shù)(1)min f1(X)表示運(yùn)輸成本最小化；目標(biāo)函數(shù)(2)min f2(X)表示運(yùn)輸距離最小化；目標(biāo)函數(shù)(3)min f3(X)表示等待時(shí)間最小化；h表示回路個(gè)數(shù)，r＝1，2…，h，xrij表示回路r中從裝載點(diǎn)i到卸載點(diǎn)j的重載運(yùn)輸次數(shù)，dij表示裝載點(diǎn)i到卸載點(diǎn)j的距離，C1表示卡車(chē)重載運(yùn)行狀態(tài)下單位成本，yrji表示回路r中從卸載點(diǎn)j到裝載點(diǎn)i的重載運(yùn)輸次數(shù)，C2表示卡車(chē)空載運(yùn)行狀態(tài)下單位成本，Kr表示第r個(gè)回路上卡車(chē)數(shù)量，T0表示班次時(shí)間，C3表示班次時(shí)間內(nèi)卡車(chē)維修費(fèi)用，Tz表示裝載時(shí)間。

約束條件如下：

其中，約束條件(4)表示出礦點(diǎn)最小生產(chǎn)任務(wù)要求；約束條件(5)表示出礦點(diǎn)最大生產(chǎn)能力；約束條件(6)表示受礦點(diǎn)最小任務(wù)量要求；約束條件(7)表示受礦點(diǎn)最大生產(chǎn)能力；約束條件(8)表示卸載點(diǎn)礦石品位應(yīng)該在允許范圍內(nèi)；約束條件(9)表示卡車(chē)數(shù)量限制；約束(10)表示在同一回路內(nèi)保證車(chē)輛不擁堵的約束。

m表示裝載點(diǎn)數(shù)目，i＝1，2，...，m，C表示卡車(chē)裝載量，pi表示第i個(gè)裝載點(diǎn)最小任務(wù)量，qi表示第i個(gè)裝載點(diǎn)最大產(chǎn)出量，n表示卸載點(diǎn)數(shù)目，j＝1，2，...，n，gj表示第j個(gè)卸載點(diǎn)最小任務(wù)量，fj表示第j個(gè)卸載點(diǎn)最大承載力，Gi表示第i個(gè)裝載點(diǎn)出礦品位，K表示卡車(chē)數(shù)量，ej表示第j個(gè)卸載點(diǎn)的品位需求，表示卸載點(diǎn)允許的品位波動(dòng)偏差。

步驟3，對(duì)NSGA-III算法進(jìn)行改進(jìn)，得到基于距離支配關(guān)系的NSGA-III算法，改進(jìn)的方法如下：

參考圖2，在原始NSGA-III算法中引入均勻分布的參考點(diǎn)，然后將參考點(diǎn)與原點(diǎn)連接形成參考線，計(jì)算所有個(gè)體到參考線的垂直距離，將個(gè)體與垂直距離最小的參考點(diǎn)關(guān)聯(lián)；算法保留了隨機(jī)生成初始種群以后通過(guò)進(jìn)化形成子代加入父代的協(xié)同進(jìn)化的精英保留策略，通過(guò)快速Pareto非支配排序形成非支配等級(jí)，然后按照由低到高的順序加入歸檔集，在歸檔集種群規(guī)模大于N時(shí)，利用小生境選擇技術(shù)使歸檔集種群規(guī)模為N，改進(jìn)后使用距離支配關(guān)系對(duì)種群進(jìn)行非支配排序，劃分非支配層級(jí)。

在原始的NSGA-III算法中，由于Pareto支配的限制，導(dǎo)致僅能從臨界層選擇過(guò)程中保留多樣性較好的解，且這些解不一定作為相對(duì)較優(yōu)的解保留到下一代種群中，因此提出一種距離支配關(guān)系提升解的多樣性。距離支配關(guān)系結(jié)合小生境技術(shù)，不僅考慮到解的收斂性，同樣使解的多樣性得到了增強(qiáng)。具體來(lái)說(shuō)，如果解X1距離支配解X2，即X1X2，則滿(mǎn)足下列條件：

其中是個(gè)體X1到理想點(diǎn)的歐氏距離，是個(gè)體X2到理想點(diǎn)的歐氏距離，將歐氏距離作為適應(yīng)度值來(lái)選擇更優(yōu)的解，表示兩個(gè)候選解X1、X2的目標(biāo)值之間的夾角，即是每個(gè)候選解的所屬小生境的大小。

在基于支配的算法中，通常采用精英保留策略，也就是在生成父代種群后會(huì)通過(guò)遺傳變異生成子代種群，父代與子代共同進(jìn)行環(huán)境選擇。因此，本發(fā)明的目標(biāo)就是在非支配排序過(guò)程中，使得一半的種群處于非支配層級(jí)。為了保證解集P中非支配解的比值總是在0.5，被設(shè)置為第(|P|/2)個(gè)最小夾角。

使用距離支配關(guān)系將種群個(gè)體按照目標(biāo)值進(jìn)行非支配排序的過(guò)程如下：

(1)根據(jù)目標(biāo)函數(shù)f1(X)，f2(X)和f3(X)計(jì)算每個(gè)種群個(gè)體目標(biāo)函數(shù)值，在初始化種群中，每一條運(yùn)行的路徑對(duì)應(yīng)為算法中的一個(gè)個(gè)體；

(2)分別比較每一維目標(biāo)函數(shù)值，選取每一維目標(biāo)函數(shù)值的最小值作為理想點(diǎn)；

(3)計(jì)算種群中每個(gè)個(gè)體與其他個(gè)體之間的最小夾角，從而得出小生境大小并根據(jù)距離支配關(guān)系劃分非支配層級(jí)。

(4)如果解X1與解X2之間的夾角小于小生境大小，則僅比較兩個(gè)解到理想點(diǎn)之間的距離來(lái)判斷非支配關(guān)系；如果兩個(gè)解之間的夾角大于小生境的大小，則考慮能否在一定區(qū)間內(nèi)保留到理想點(diǎn)較遠(yuǎn)的個(gè)體，進(jìn)而保證種群多樣性。

步驟4，采用改進(jìn)的算法對(duì)金屬露天礦多目標(biāo)調(diào)度模型進(jìn)行求解，具體求解過(guò)程如下：

Step 1確定種群規(guī)模，產(chǎn)生初始父代種群，每一個(gè)種群對(duì)應(yīng)一條運(yùn)行路徑；

Step 2將父代群進(jìn)行交叉、變異的遺傳操作形成新的子代種群；

Step 3將父代種群與子代種群合并；

Step 4按照上述的多目標(biāo)調(diào)度模型，計(jì)算合并后種群中所有個(gè)體的目標(biāo)值；

Step 5根據(jù)種群中每個(gè)個(gè)體的目標(biāo)值按照距離支配關(guān)系進(jìn)行非支配排序；

Step 6按照非支配層級(jí)由低到高的順序加入歸檔集，到達(dá)臨界層時(shí)采用小生境選擇技術(shù)使歸檔集種群規(guī)模與初始種群規(guī)模一致；

Step 7判斷是否滿(mǎn)足設(shè)定的迭代次數(shù)這一終止條件，是則結(jié)束算法輸出結(jié)果，否則轉(zhuǎn)Step 2。

全文PDF

基于高維多目標(biāo)進(jìn)化算法的露天礦卡車(chē)多目標(biāo)調(diào)度優(yōu)化方法.pdf