彭　程，薛偉寧，黃　軼

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

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

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

1　問題描述

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

(1)

式中，Cij和xij分別為從裝載點Li到卸載點Uj的單位運費和運輸量,Cij單位為元/m3,xij單位為m3。

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

(3)

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

(4)

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

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

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

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

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

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

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

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

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

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

46325-

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

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

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

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

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

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

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

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

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

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

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

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

綜上，求解露天礦運輸問題的模擬退火算法的步驟，如下所示。

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

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

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

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

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

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

4　計算實例

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

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

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

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

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

5　結(jié)　語

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

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

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

[3]王桃,江松,盧才武.露天礦運輸調(diào)度優(yōu)化的生物地理學改進算法[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]彭程,王永.振動系統(tǒng)穩(wěn)定模型的頻域辨識[J].振動與沖擊,2010,29(3):118-120.

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

[8]夏偉懷,符卓.運籌學[M].長沙:中南大學出版社,2011:75-86.