露天礦運輸問題的模擬退火優化

彭　程，薛偉寧，黃　軼

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

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

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

1　問題描述

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

(1)

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

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

(3)

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

(4)

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

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

2　運輸問題的排序優化表示

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

假設某廠有位于不同地區的2個分廠，生產相同品質的一種產品，每天的產量分別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。總產量和總需求量均為10 t/d，故該運輸問題是平衡的，可以表示為如下的線性規劃問題。

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中的按照產地為行，銷售地為列的表中，表中最后一行為各銷售地的總銷量，最后一列為各產地的總產量。將圖1中6個空白位置按行進行編號，表示為1～6，例如第一行第二列的空白位置編號為2，第二行第一列的空白位置編號為4，等等。

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

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

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

46325-

圖1　原始運輸量作業表

圖2　一步之后的運輸量作業表

圖3　二步之后的運輸量作業表

圖4六步之后的運輸量作業表

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

3　運輸問題的模擬退火優化

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

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

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

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

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

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

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

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

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

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

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

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

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

4　計算實例

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

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

表1　撫順西露天礦運輸問題數據表

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

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

5　結　語

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

[1]鞠興軍,李林,劉光偉.基于遺傳算法的神經網絡在露天礦卡車調度系統中的應用研究[J].露天采礦技術,2009,24(6):31-33.

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

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

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

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