露天礦運(yùn)輸問(wèn)題的模擬退火優(yōu)化

彭　程，薛偉寧，黃　軼

(1.華北科技學(xué)院信息與控制技術(shù)研究所，河北 三河 065201；2.安全監(jiān)測(cè)監(jiān)控技術(shù)國(guó)家安全生產(chǎn)監(jiān)督管理總局安全生產(chǎn)重點(diǎn)實(shí)驗(yàn)室，河北 三河 065201)

隨著能源價(jià)格的變化，運(yùn)輸優(yōu)化成為露天礦企業(yè)降低生產(chǎn)成本、提升競(jìng)爭(zhēng)力的重要手段。運(yùn)輸問(wèn)題是一類(lèi)特殊的線(xiàn)性規(guī)劃問(wèn)題，可以利用單純形法或內(nèi)點(diǎn)法等傳統(tǒng)的線(xiàn)性規(guī)劃算法求解。近年來(lái)智能優(yōu)化領(lǐng)域的研究取得了很大進(jìn)展，學(xué)者將智能優(yōu)化算法用于求解露天礦運(yùn)輸問(wèn)題。例如文獻(xiàn)[1]～[3]分別采用遺傳算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)、雙目標(biāo)粒子群優(yōu)化算法和混合差分進(jìn)化-生物地理優(yōu)化算法進(jìn)行了露天礦運(yùn)輸問(wèn)題的優(yōu)化計(jì)算。與單純形法等傳統(tǒng)的線(xiàn)性規(guī)劃問(wèn)題解法相比，智能優(yōu)化算法的性能還有差距，但是這類(lèi)算法的優(yōu)勢(shì)在于易于理解和實(shí)現(xiàn)，并且可以進(jìn)一步推廣到更復(fù)雜的運(yùn)輸優(yōu)化問(wèn)題中[4]。與文獻(xiàn)[1]～[3]直接對(duì)運(yùn)輸量進(jìn)行優(yōu)化的思路不同，文獻(xiàn)[4]利用運(yùn)輸問(wèn)題的特點(diǎn)，將運(yùn)輸問(wèn)題表示為生成可行解的排序優(yōu)化問(wèn)題，并利用遺傳算法求解排序優(yōu)化問(wèn)題，取得了較好的效果，但是遺傳算法在交叉操作的過(guò)程中會(huì)生成不合理的解，需要進(jìn)一步調(diào)整。

模擬退火算法[5]能夠以一定的概率接受變差的解，具有跳出局部極小點(diǎn)的能力，是一類(lèi)重要的全局優(yōu)化算法，已被用于解決旅行商[5]、振動(dòng)系統(tǒng)頻域辨識(shí)[6]以及超分辨率圖像重建[7]等各類(lèi)問(wèn)題。用其求解旅行商問(wèn)題等排序優(yōu)化問(wèn)題時(shí)，不需要進(jìn)行解的進(jìn)一步調(diào)整。為此，本文采用了文獻(xiàn)[4]的將運(yùn)輸問(wèn)題轉(zhuǎn)化為等價(jià)的排序優(yōu)化問(wèn)題，并使用智能優(yōu)化算法求解的思路，實(shí)現(xiàn)了模擬退火算法進(jìn)行露天礦運(yùn)輸?shù)膬?yōu)化計(jì)算，并與文獻(xiàn)中報(bào)道的結(jié)果進(jìn)行了對(duì)比。

1　問(wèn)題描述

假設(shè)露天礦有I個(gè)裝載點(diǎn)，分別表示為L(zhǎng)i(i= 1，2，…，I)，裝載點(diǎn)Li所在采區(qū)的開(kāi)采能力為Pi，m3；J個(gè)卸載點(diǎn)，分別表示為Uj(j=1，2，…，J)，卸載點(diǎn)Uj的受礦能力為Qj，m3。則為了降低運(yùn)輸成本，露天礦運(yùn)輸問(wèn)題的目標(biāo)函數(shù)定義為式(1)。

(1)

式中，Cij和xij分別為從裝載點(diǎn)Li到卸載點(diǎn)Uj的單位運(yùn)費(fèi)和運(yùn)輸量,Cij單位為元/m3,xij單位為m3。

假設(shè)裝載點(diǎn)所在礦區(qū)生產(chǎn)的礦石需全部運(yùn)出，卸載點(diǎn)接收的礦石量不大于其受礦能力，運(yùn)輸問(wèn)題還需要滿(mǎn)足等式約束(式(2))和不等式約束(式(3))?？紤]到實(shí)際的運(yùn)輸過(guò)程中運(yùn)輸量xij不能為負(fù)，故運(yùn)輸問(wèn)題還需滿(mǎn)足邊界約束，見(jiàn)式(4)。

(3)

xij≥0,i=1,2,…,I,j=1,2,…,J

(4)

綜上，本文研究的露天礦運(yùn)輸問(wèn)題可以表示為式(1)～(4)定義的約束優(yōu)化問(wèn)題。

由裝載點(diǎn)LI+1到各卸載點(diǎn)的運(yùn)輸量分別為xI+1,1、xI+1,2、…、xI+1,J，運(yùn)費(fèi)均為0，元/m3，則式(1)～(4)定義的非平衡運(yùn)輸問(wèn)題等價(jià)于式(5)定義的平衡運(yùn)輸問(wèn)題。

2　運(yùn)輸問(wèn)題的排序優(yōu)化表示

在運(yùn)輸問(wèn)題中使用智能優(yōu)化算法的通常做法是直接對(duì)運(yùn)輸量xij進(jìn)行優(yōu)化，但這樣處理存在著難以滿(mǎn)足約束條件，尤其是等式約束條件，進(jìn)而陷入局部極小點(diǎn)的困難。運(yùn)輸問(wèn)題的一類(lèi)經(jīng)典解法是表上作業(yè)法[8]，它有不同的實(shí)現(xiàn)形式，如最小元素法，伏格爾法等。當(dāng)運(yùn)輸問(wèn)題自變量的數(shù)量較多時(shí)，表上作業(yè)不太方便。文獻(xiàn)[4]借鑒表上作業(yè)法的思想，提出了將運(yùn)輸問(wèn)題轉(zhuǎn)化為排序優(yōu)化問(wèn)題的思路，使得運(yùn)輸問(wèn)題的約束條件可以直接得到滿(mǎn)足。本文也使用了這一思路處理露天礦運(yùn)輸問(wèn)題。下面以一個(gè)簡(jiǎn)單的運(yùn)輸問(wèn)題為例，說(shuō)明排序操作的過(guò)程。詳細(xì)的原理可以參考文獻(xiàn)[4]和文獻(xiàn)[8]。

假設(shè)某廠(chǎng)有位于不同地區(qū)的2個(gè)分廠(chǎng)，生產(chǎn)相同品質(zhì)的一種產(chǎn)品，每天的產(chǎn)量分別4 t和6 t；銷(xiāo)往3座城市，3座城市每天銷(xiāo)量分別為3 t、2 t和5 t；從1分廠(chǎng)到3座城市的單位運(yùn)費(fèi)分別為200元/t、500元/t和100元/t，從2分廠(chǎng)到3座城市的運(yùn)費(fèi)分別為300元/t、200元/t和300元/t。總產(chǎn)量和總需求量均為10 t/d，故該運(yùn)輸問(wèn)題是平衡的，可以表示為如下的線(xiàn)性規(guī)劃問(wèn)題。

minf(x)=200x11+500x12+100x13+

300x21+200x22+300x23

s.t.x11+x21=3,x12+x22=2,

x13+x23=5,x11+x12+x13=4,

x21+x22+x23=6

為了生成可行解，需要將運(yùn)輸量放入圖1中的按照產(chǎn)地為行，銷(xiāo)售地為列的表中，表中最后一行為各銷(xiāo)售地的總銷(xiāo)量，最后一列為各產(chǎn)地的總產(chǎn)量。將圖1中6個(gè)空白位置按行進(jìn)行編號(hào)，表示為1～6，例如第一行第二列的空白位置編號(hào)為2，第二行第一列的空白位置編號(hào)為4，等等。

假設(shè)首先在圖1中編號(hào)為3的空白位置，即第一行第三列放入一個(gè)運(yùn)輸量，考慮到1分廠(chǎng)產(chǎn)量為4 t，城市3的銷(xiāo)量為5 t，故運(yùn)輸量取其中較小的值，即4 t；同時(shí)將第一行和第三列允許的運(yùn)輸量各自減去放入位置3中的4 t，即圖1變?yōu)閳D2。

同理，假設(shè)第二次在圖2中編號(hào)為2的空白位置，即第一行第二列放入一個(gè)運(yùn)輸量，其取值為所在行和列允許的運(yùn)輸量的較小值，即0t；同時(shí)將第一行和第二列允許的運(yùn)輸量各自減去放入位置2的0t，即圖2變?yōu)閳D3。

假設(shè)之后按照6、4、5、1的順序依次修正運(yùn)輸量作業(yè)表，得到圖4，圖中最后一行和最后一列均為0，即此時(shí)得到了優(yōu)化問(wèn)題的一個(gè)滿(mǎn)足約束條件的解。

46325-

圖1　原始運(yùn)輸量作業(yè)表

圖2　一步之后的運(yùn)輸量作業(yè)表

圖3　二步之后的運(yùn)輸量作業(yè)表

圖4六步之后的運(yùn)輸量作業(yè)表

實(shí)際上圖4中的運(yùn)輸量為該運(yùn)輸問(wèn)題的最優(yōu)解，對(duì)應(yīng)的最優(yōu)運(yùn)費(fèi)為2 000元。它可以由上述的作業(yè)順序S=[3,2,6,4,5,1]生成。作業(yè)順序不同，最終得到的運(yùn)輸量不同，但是都能夠滿(mǎn)足約束條件。平衡運(yùn)輸問(wèn)題的解可以通過(guò)找到最優(yōu)作業(yè)順序的方式得到。

3　運(yùn)輸問(wèn)題的模擬退火優(yōu)化

對(duì)于小規(guī)模問(wèn)題，表上作業(yè)法是有效的，但是自變量數(shù)目較多時(shí)，表上作業(yè)不太方便?？紤]到模擬退火算法是解決排序優(yōu)化問(wèn)題，例如旅行商問(wèn)題的有效方法，本文實(shí)現(xiàn)了模擬退火算法進(jìn)行作業(yè)順序的優(yōu)化。

模擬退火算法主要包括生成及接受/拋棄新解和降溫兩類(lèi)操作。

1) 生成及接受/拋棄新解操作。對(duì)每個(gè)特定的溫度，在已有解的基礎(chǔ)上按照某種方式生成一個(gè)新解，若新解優(yōu)于已有解，則接受該新解。若新解劣于已有解，則按照一定概率接受新解，接受概率與當(dāng)前所處溫度有關(guān)，溫度越高，接受的概率越大。在當(dāng)前溫度下執(zhí)行若干次生成新解、接受/拋棄新解的操作，以達(dá)到在該溫度下的平衡。

2) 降溫操作。從一個(gè)足夠高的溫度出發(fā)，按照某種規(guī)律進(jìn)行降溫。

不同的模擬退火算法的主要區(qū)別在于生成新解的方式以及降溫方式不同。本文采用幾何降溫方式。

作業(yè)順序優(yōu)化是一類(lèi)排序優(yōu)化問(wèn)題，假設(shè)已有一個(gè)作業(yè)順序S0，生成新的作業(yè)順序的一種方法是在S0中任選兩個(gè)位置，交換兩位置的內(nèi)容，其他位置的內(nèi)容保持不變。例如對(duì)上述運(yùn)輸問(wèn)題而言，假設(shè)原有的作業(yè)順序?yàn)镾0=[1,3,2,5,4,6]，隨機(jī)產(chǎn)生的位置為2和4，則交換位置2和位置4的內(nèi)容，可以生成一個(gè)新的作業(yè)順序S1=[1,5,2,3,4,6]。

綜上，求解露天礦運(yùn)輸問(wèn)題的模擬退火算法的步驟，如下所示。

1) 步驟一，增加虛擬裝載點(diǎn)，將式(1)～(4)定義的非平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為式(5)定義的平衡運(yùn)輸問(wèn)題。

2) 步驟二，設(shè)定模擬退火算法參數(shù)，包括初始溫度T0、終止溫度T2、降溫系數(shù)α、每個(gè)溫度下生成新解的最大次數(shù)N。

3) 步驟三，隨機(jī)生成一個(gè)作業(yè)順序S0，計(jì)算對(duì)應(yīng)的可行解x0以及對(duì)應(yīng)的運(yùn)費(fèi)f(x0)。令當(dāng)前溫度T1=T0，已生成新解數(shù)目n=0。令最優(yōu)解xb=x0，最優(yōu)目標(biāo)函數(shù)fb=f(x0)。

4) 步驟四，在已有的作業(yè)順序S0中任意找到兩個(gè)位置，交換其內(nèi)容，其他位置保持不變，生成新的作業(yè)順序S1；計(jì)算對(duì)應(yīng)的可行解x1以及對(duì)應(yīng)的運(yùn)費(fèi)f(x1)。若f(x1)p2，則接受新的作業(yè)順序S1和新解x1，即令S0=S1、x0=x1、f(x0)=f(x1)。

5) 步驟五，令當(dāng)前溫度T1下已生成新解的次數(shù)n=n+1。若n

6) 步驟六，按幾何方式進(jìn)行降溫，即令溫度T1=αT1。若T1>T2，令已生成新解數(shù)目n=0，返回步驟四；否則輸出最優(yōu)解xb及其對(duì)應(yīng)的最優(yōu)運(yùn)費(fèi)fb。

4　計(jì)算實(shí)例

為了驗(yàn)證模擬退火算法求解露天礦運(yùn)輸問(wèn)題的效果，考慮文獻(xiàn)[1]、文獻(xiàn)[2]研究過(guò)的撫順西露天礦運(yùn)輸問(wèn)題，該礦有9個(gè)裝載點(diǎn)、5個(gè)卸載點(diǎn)，各裝載點(diǎn)所在采區(qū)的開(kāi)采能力、卸載點(diǎn)的受礦能力、從各裝載點(diǎn)到各卸載點(diǎn)的單位運(yùn)費(fèi)數(shù)據(jù)見(jiàn)表1。經(jīng)計(jì)算，總受礦能力比總開(kāi)采能力大150萬(wàn)m3，故該運(yùn)輸問(wèn)題是非平衡的，需要引入第10個(gè)虛擬的裝載點(diǎn)，其對(duì)應(yīng)的開(kāi)采能力為150萬(wàn)m3，到各卸載點(diǎn)的運(yùn)費(fèi)均為0元/m3。該露天礦運(yùn)輸問(wèn)題可以表示為一個(gè)十行五列的運(yùn)輸量作業(yè)表上的排序優(yōu)化問(wèn)題。

模擬退火算法的參數(shù)：初始溫度T0=1 000 ℃、終止溫度T2=1 ℃、降溫系數(shù)α= 0.999、每個(gè)溫度下生成新解的最大次數(shù)N=3。模擬退火算法求出的最優(yōu)解見(jiàn)表2，對(duì)應(yīng)的最優(yōu)運(yùn)費(fèi)為41 224萬(wàn)元。表2同時(shí)給出了文獻(xiàn)[1]、文獻(xiàn)[2]求出的最優(yōu)解，對(duì)應(yīng)的最優(yōu)運(yùn)費(fèi)分別為41 717萬(wàn)元和44 090萬(wàn)元。借助于Matlab軟件提供的線(xiàn)性規(guī)劃求解器linprog得到的最優(yōu)運(yùn)費(fèi)為41 224萬(wàn)元，對(duì)比可知模擬退火算法得到了該運(yùn)輸問(wèn)題的全局最優(yōu)解。

表1　撫順西露天礦運(yùn)輸問(wèn)題數(shù)據(jù)表

表2　不同算法得到的撫順西露天礦運(yùn)輸問(wèn)題的最優(yōu)解

為了考察上述參數(shù)對(duì)本文實(shí)現(xiàn)的模擬退火算法性能的影響，重復(fù)進(jìn)行100次優(yōu)化計(jì)算，100組最優(yōu)解中，有99組為41 224萬(wàn)元，1組為41 232萬(wàn)元，這表明優(yōu)化計(jì)算中使用的算法參數(shù)是合理的，能夠使模擬退火算法具有較好的可重復(fù)性。

5　結(jié)　語(yǔ)

本文借鑒了文獻(xiàn)中將運(yùn)輸問(wèn)題轉(zhuǎn)化為排序優(yōu)化問(wèn)題的思路，利用模擬退火算法求解露天礦運(yùn)輸問(wèn)題。實(shí)現(xiàn)的模擬退火算法在生成新解時(shí)只需進(jìn)行簡(jiǎn)單的位置交換操作，具有易于理解和實(shí)現(xiàn)的優(yōu)點(diǎn)。計(jì)算結(jié)果表明，通過(guò)合理設(shè)置參數(shù)，模擬退火算法可以得到運(yùn)輸問(wèn)題的全局最優(yōu)解，是求解露天礦運(yùn)輸問(wèn)題的一種有效算法。

[1]鞠興軍,李林,劉光偉.基于遺傳算法的神經(jīng)網(wǎng)絡(luò)在露天礦卡車(chē)調(diào)度系統(tǒng)中的應(yīng)用研究[J].露天采礦技術(shù),2009,24(6):31-33.

[2]李勇,胡乃聯(lián),李國(guó)清.基于改進(jìn)粒子群算法的露天礦運(yùn)輸調(diào)度優(yōu)化[J].中國(guó)礦業(yè),2013,22(4):98-101,105.

[3]王桃,江松,盧才武.露天礦運(yùn)輸調(diào)度優(yōu)化的生物地理學(xué)改進(jìn)算法[J].金屬礦山,2016(9):161-164.

[4]VIGNAUX G A,MICHALEWICZ Z.A genetic algorithm for the linear transportation problem[J].IEEE Transactions on Systems,Man and Cybernetics,1991,21(2):445-452.

[5]KIRKPATRICK S,GELATT C D,VECCHI M P Jr.Optimization by simulated annealing[J].Science,1983,220:671-680.

[6]彭程,王永.振動(dòng)系統(tǒng)穩(wěn)定模型的頻域辨識(shí)[J].振動(dòng)與沖擊,2010,29(3):118-120.

[7]任宏德.基于模擬退火算法優(yōu)化的超分辨率圖像重建[J].激光雜志,2016,37(2):38-41.

[8]夏偉懷,符卓.運(yùn)籌學(xué)[M].長(zhǎng)沙:中南大學(xué)出版社,2011:75-86.