不確定性航線配船數學模型建模方法

蘇紹娟，王麗錚，王呈方

（武漢理工大學 交通學院，武漢430063）

航線配船主要是解決多船型在多條航線上的合理配置問題，目的在于充分利用現有的條件和資源，以最少的投入，換取最大的效益。由于在航運市場中存在很多不確定的因素，所以建立不確定性的航線配船模型符合實際情況。

粒子群優化算法（PSO）是一種新興的群智能優化算法，相對遺傳算法、模擬退火等算法而言，PSO更簡單有效，并已得到眾多學者的重視和研究，許多實際應用非常成功。但它同許多智能方法一樣存在早熟問題。在航體配船，由于存在隨機、模糊現象，使問題更加復雜，計算量非常大，所以提高計算速度很重要。根據不確定航線配船數學模型的特點及粒子群算法本身的特征，本文對粒子群算法進行了相應的改進。

1 數學模型

在若干港口之間長期從事大宗貨物運輸的定線運輸船隊，其船舶運行組織具有很強的規律性和相對的穩定性。我國沿海的石油、礦石、煤炭等大宗工業物資的運輸就屬于這種情況。科學的配置船舶會帶來巨大的效益。

1.1 目標函數

以總利潤最大化為目標函數：即收入減去營運費用再減去閑置費用的最大值［1］。

式中：Aij——i型船在j航線上的單船年利潤；

DWi——船舶的載重噸；

ij——i船在j航線上的年航行次數；

Yj——j航線的運價；

DHYij——i船在j航線上的單航次耗油量；

RJ——燃油單價；

——船價；

α——與收入有關的成本占收入的比例；

α1——與船價相關的成本占船價的比例；

α2——船舶的閑置費占船價的百分比。

1.2 約束條件

1）船舶在該航線上的運量不能大于貨運需求量，即

2）保證各航線上的某型船數量與該船的閑置量之和與船隊中擁有的這種船的數量Ait相等。

3）變量非負性約束

式中：xij——決策變量，在j航線上配置的i型船數量；

pi——決策變量，i型船的閑置量；

——i型船舶在j航線上營運時的單船年運量；

——j航線上貨運需求量；

Ai——船隊中擁有的j型船數量；

K——船型總數；

G——航線總數。

需要說明的是ij是模糊量，Yj和是隨機變量，所以A P～ij是同時含有模糊和隨機的不確定量。即目標函數是含有模糊和隨機的不確定量。由于航次數是三角模糊量，所以船舶的年貨運量同樣是模糊數，約束實質上是模糊約束。

2 粒子群算法的改進

粒子群算法是繼蟻群算法之后又一群體智能算法，在粒子群算法中，每個粒子根據自己的飛行經驗和同伴的飛行經驗來調整自己的飛行速度和方向從而尋找問題的最優解。它是一種隨機搜索算法，而且是從多個初始點開始進行搜索的，比較容易快速地接近或達到最優解。

2.1 混沌算法

混沌變量產生的方法有多種，選用較為廣泛的Logistic映射，即：

將混沌變量zik映射到優化變量取值區間成為xi，n+1：

二次載波的數學模型為：

式中：λ——時變參數zt的衰減因子，λ?1，通常取λ∈［0.95，0.999］；

x＊——第一階段搜索到的最優解；

zt——時變參數。

這樣就可以實現在次優值的雙側鄰域內通過逐步縮小混沌變量遍歷的區域范圍進行混沌細搜索，從而找到全局最優值。

對于時變參數zt的初始值的選擇問題，模仿模擬退火算法初始退火溫度的思路來確定，即先按混沌尋優方法的第一階段搜索N個可行解，并記錄這N個可行解中所對應的目標函數值的最大最小值fmax和fmin，選擇參數P（0＜P＜1），于是按下式確定zt的初始值z0：z0＝

2.2 粒子群算法的改進

本文對標準粒子群算法進行了以下改進［2-7］。

1）初始化。

采用混沌系列初始化粒子的位置，既不改變粒子群優化算法初始化時所具有的隨機性本質，又利用混沌提高了種群的多樣性和粒子搜索的遍歷性。根據公式（6）和 （7）取足夠多的混沌序列點數，選擇性能較好的N個可行解組成初始群體。

2）加入約束因子的PSO模型。

1999年Clerc對算法的數學研究證明，采用約束因子（constriction factor）控制速度的權重，能夠保證算法的收斂且可以有效搜索不同的區域，從而得到高質量的解。

3）加入“第三個”極值，即在從第k代向第k+1代飛行的過程中，粒子除追隨個體極值pbest和全局極值gbest外，還追隨從粒子群中隨機選取的某個粒子的個體極值nbest進行速度更新。則粒子群數學模型為：

式中：c3——非負常數；

r3——［0，1］之間的隨機數；

l——在粒子群中隨機選取的某個粒子。

為保證收斂性，c1+c2+c3＞4。

在粒子的速度迭代公式中增加nbestt后，由pbest，gbest，nbest三者共同向下一代提供信息，粒子獲得的信息量增大，從而可能更快的找到優化解。同時類似于GA中的變異操作，提供擾動信息，增加了粒子的多樣性，從而可使粒子跳出局部最優區域，使算法搜索未知的空間，避免算法過早收斂。nbest只起補充作用，因此C3的取值通常較小，一般為0.1～0.5。

4）粒子群優化算法在運行過程中，如果某粒子發現了一個當前最優位置 ，其它粒子將迅速向其靠攏。如果該最優位置是局部最優點，粒子群就無法在解空間內重新搜索，因此，算法陷入局部最優，出現了所謂的早熟收斂現象。實驗證明，粒子群優化算法無論是早熟收斂還是全局收斂，粒子群中的粒子都會出現“聚集”現象。要么所有粒子聚集在某一特定位置，要么聚集在某幾個特定位置，這主要取決于問題本身的特性以及適應度函數的選擇。

為了定量描述粒子群的狀態，給出群體適應度方差的定義。

設粒子群的粒子數目為n，fi為第i個粒子的適應度，favg為粒子群目前的平均適應度，σ2為粒子群的群體適應度方差，則σ2可以定義為：

其中f為歸一化定標因子，其作用是限制σ2的大小，取值如下：

式（11）表明，群體適應度方差σ2反映的是粒子群中所有粒子的“聚集”程度。σ2越小，則粒子群的“聚集”程度就越大，若此時算法不滿足結束條件，而“聚集”將使群體失去多樣性陷入了早熟狀態，故當σ2＜C（C為一給定常數）時，進行早熟處理。

如果出現早熟現象，以目前得到的pg＝（pg1，pg2，…，pgn）作為二次載波的當前最優解，在局部區域進行混沌優化，從而引導粒子快速跳出局部最優，加快收斂速度。

2.3 改進PSO的計算流程

1）采用混沌系列初始化粒子的位置及相關參數，使用模糊隨機模擬技術檢驗其可行性。

2）使用模糊隨機模擬技術［8］計算每個粒子的最優位置pi＝（pi1，pi2，…，pin）為當前粒子所在的位置，并計算其對應的適應度pbest，并計算全局最優位置為pg＝（pg1，pg2，…，pgn）當前群體中具有最優適應度的粒子的位置，gbest為該粒子的適應度。

3）判斷算法收斂準則（根據實際問題來確定）是否滿足，如果滿足，轉向9）；否則執行4）。

4）對于粒子群中的所有粒子，執行如下操作：（1）根據式（9）和式（10）更新粒子的位置與速度并計算出其適應度；（2）如果粒子i的適應度優于它對應的pbest，則pi＝（pi1，pi2，…，pin）設置為第i個粒子的新位置，并更新pbest；（3）如果群體中具有最優適應度的粒子的適應度優于gbest，則將pg＝（pg1，pg2，…，pgn）設置為該粒子的位置，并更新gbest。

5）判斷算法收斂準則是否滿足，如果滿足，執行9）。

6）根據式（11）與（12）計算群體適應度方差σ2，并判斷是否成立，若成立則轉向7）進行混沌搜索；否則轉向4）。

7）設置混沌搜索的最優解向量z＝pg，zbest＝gbest。

8）根據式（6）、（7）產生混沌變量，進行混沌搜索，得最優解向量x及對應的適應值xbest，令pg＝x，gbest＝xbest轉3）。

9）輸出pg＝（pg1，pg2，…，pgn）及gbest，算法運行結束。

3 航線配船實例及結果分析

某沿海礦石運輸公司現有2.5萬噸級、3.5萬噸級和4.5萬噸級船舶分別為1艘、2艘和3艘。收集了72個干散貨船價格并將其轉換為4萬噸級的干散貨船船價，采用概率統計的方法進行隨機模擬，得出4萬噸級船的船價為符合對數正態分布的隨機數，概率密度為：

由參考文獻［9］可知其他噸位的船價概率密度大致為：

通過對沿海干散貨運輸的調研及單船經濟指標計算，得出航次數、運價、各航線上的運量等見表1。

表1 航次數、運價、各航線上的運量

采用本文提出的粒子群算法來求解仿真實例，令c1＝2.8，c2＝1.3，c3＝0.3，種群規模 N＝30，最大迭代次數為500次，約束因子λ＝0.729，混沌初始化100個可行解，混沌搜索500次。運行結果及目標函數收斂曲線見圖1。

圖1 兩種方法計算結果比較

可見改進后迭代156次即可達到最優，而標準PSO迭代500次還未達到最優，可見改進后PSO的有效性。

4 結束語

由于航線配船涉及的資金投入產出額很大，合理地對船舶進行組織優化對航運企業來說意義重大。本文提出的改進的PSO，在原模型的基礎上，加入“第三個”極值，增加粒子獲得的信息量增大，同時采用約束因子控制速度的權重，并將混沌理論引入到PSO中，不但可以找到優良的初始種群，也避免了早熟現象的出現，能夠保證算法的收斂且可以有效搜索不同的區域，從而得到高質量的解，實例也證明了該方法的有效性。

［1］張德洪，顧家駿.運輸船舶船型技術經濟論證方法［M］.北京：人民交通出版社，1989.

［2］呂振肅，侯志榮.自適應變異的粒子群優化算法［J］.電子學報，2004，32（3）：416-420.

［3］趙志剛，蘇一丹.帶自變異算子的粒子群優化算法［J］.計算機工程與應用，2006，13：45-47.

［4］劉華鎣，林玉娥，張君施.基于混沌搜索解決早熟收斂的混合粒子群算法［J］.計算機工程與應用，2006，13：77-79.

［5］劉洪波，王秀坤，譚國真.粒子群優化算法的收斂性分析及其混沌改進算法［J］.控制與決策，2006（6）：636-640.

［6］趙 強.改進的混沌優化方法及其應用［J］.自動化與儀器儀表，2006（3）：90-92.

［7］高海昌，馮博琴，侯 蕓，朱 利.自適應變異的混合粒子群優化策略及其應用［J］.西安交通大學學報，2006，6（40）：663～666.

［8］劉寶碇，趙瑞清，王 綱.不確定規劃及應用［M］.北京：清華大學出版社，2003.

［9］劉祖源，施金龍，毛筱菲.船舶貿易與經營［M］.北京：人民交通出版社，1999.