不確定性航線配船數(shù)學(xué)模型建模方法

蘇紹娟，王麗錚，王呈方

（武漢理工大學(xué) 交通學(xué)院，武漢430063）

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

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

1 數(shù)學(xué)模型

在若干港口之間長期從事大宗貨物運(yùn)輸?shù)亩ň€運(yùn)輸船隊(duì)，其船舶運(yùn)行組織具有很強(qiáng)的規(guī)律性和相對的穩(wěn)定性。我國沿海的石油、礦石、煤炭等大宗工業(yè)物資的運(yùn)輸就屬于這種情況?？茖W(xué)的配置船舶會(huì)帶來巨大的效益。

1.1 目標(biāo)函數(shù)

以總利潤最大化為目標(biāo)函數(shù)：即收入減去營運(yùn)費(fèi)用再減去閑置費(fèi)用的最大值［1］。

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

DWi——船舶的載重噸；

ij——i船在j航線上的年航行次數(shù)；

Yj——j航線的運(yùn)價(jià)；

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

RJ——燃油單價(jià)；

——船價(jià)；

α——與收入有關(guān)的成本占收入的比例；

α1——與船價(jià)相關(guān)的成本占船價(jià)的比例；

α2——船舶的閑置費(fèi)占船價(jià)的百分比。

1.2 約束條件

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

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

3）變量非負(fù)性約束

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

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

——i型船舶在j航線上營運(yùn)時(shí)的單船年運(yùn)量；

——j航線上貨運(yùn)需求量；

Ai——船隊(duì)中擁有的j型船數(shù)量；

K——船型總數(shù)；

G——航線總數(shù)。

需要說明的是ij是模糊量，Yj和是隨機(jī)變量，所以A P～ij是同時(shí)含有模糊和隨機(jī)的不確定量。即目標(biāo)函數(shù)是含有模糊和隨機(jī)的不確定量。由于航次數(shù)是三角模糊量，所以船舶的年貨運(yùn)量同樣是模糊數(shù)，約束實(shí)質(zhì)上是模糊約束。

2 粒子群算法的改進(jìn)

粒子群算法是繼蟻群算法之后又一群體智能算法，在粒子群算法中，每個(gè)粒子根據(jù)自己的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來調(diào)整自己的飛行速度和方向從而尋找問題的最優(yōu)解。它是一種隨機(jī)搜索算法，而且是從多個(gè)初始點(diǎn)開始進(jìn)行搜索的，比較容易快速地接近或達(dá)到最優(yōu)解。

2.1 混沌算法

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

將混沌變量zik映射到優(yōu)化變量取值區(qū)間成為xi，n+1：

二次載波的數(shù)學(xué)模型為：

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

x＊——第一階段搜索到的最優(yōu)解；

zt——時(shí)變參數(shù)。

這樣就可以實(shí)現(xiàn)在次優(yōu)值的雙側(cè)鄰域內(nèi)通過逐步縮小混沌變量遍歷的區(qū)域范圍進(jìn)行混沌細(xì)搜索，從而找到全局最優(yōu)值。

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

2.2 粒子群算法的改進(jìn)

本文對標(biāo)準(zhǔn)粒子群算法進(jìn)行了以下改進(jìn)［2-7］。

1）初始化。

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

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

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

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

式中：c3——非負(fù)常數(shù)；

r3——［0，1］之間的隨機(jī)數(shù)；

l——在粒子群中隨機(jī)選取的某個(gè)粒子。

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

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

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

為了定量描述粒子群的狀態(tài)，給出群體適應(yīng)度方差的定義。

設(shè)粒子群的粒子數(shù)目為n，fi為第i個(gè)粒子的適應(yīng)度，favg為粒子群目前的平均適應(yīng)度，σ2為粒子群的群體適應(yīng)度方差，則σ2可以定義為：

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

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

如果出現(xiàn)早熟現(xiàn)象，以目前得到的pg＝（pg1，pg2，…，pgn）作為二次載波的當(dāng)前最優(yōu)解，在局部區(qū)域進(jìn)行混沌優(yōu)化，從而引導(dǎo)粒子快速跳出局部最優(yōu)，加快收斂速度。

2.3 改進(jìn)PSO的計(jì)算流程

1）采用混沌系列初始化粒子的位置及相關(guān)參數(shù)，使用模糊隨機(jī)模擬技術(shù)檢驗(yàn)其可行性。

2）使用模糊隨機(jī)模擬技術(shù)［8］計(jì)算每個(gè)粒子的最優(yōu)位置pi＝（pi1，pi2，…，pin）為當(dāng)前粒子所在的位置，并計(jì)算其對應(yīng)的適應(yīng)度pbest，并計(jì)算全局最優(yōu)位置為pg＝（pg1，pg2，…，pgn）當(dāng)前群體中具有最優(yōu)適應(yīng)度的粒子的位置，gbest為該粒子的適應(yīng)度。

3）判斷算法收斂準(zhǔn)則（根據(jù)實(shí)際問題來確定）是否滿足，如果滿足，轉(zhuǎn)向9）；否則執(zhí)行4）。

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

5）判斷算法收斂準(zhǔn)則是否滿足，如果滿足，執(zhí)行9）。

6）根據(jù)式（11）與（12）計(jì)算群體適應(yīng)度方差σ2，并判斷是否成立，若成立則轉(zhuǎn)向7）進(jìn)行混沌搜索；否則轉(zhuǎn)向4）。

7）設(shè)置混沌搜索的最優(yōu)解向量z＝pg，zbest＝gbest。

8）根據(jù)式（6）、（7）產(chǎn)生混沌變量，進(jìn)行混沌搜索，得最優(yōu)解向量x及對應(yīng)的適應(yīng)值xbest，令pg＝x，gbest＝xbest轉(zhuǎn)3）。

9）輸出pg＝（pg1，pg2，…，pgn）及gbest，算法運(yùn)行結(jié)束。

3 航線配船實(shí)例及結(jié)果分析

某沿海礦石運(yùn)輸公司現(xiàn)有2.5萬噸級、3.5萬噸級和4.5萬噸級船舶分別為1艘、2艘和3艘。收集了72個(gè)干散貨船價(jià)格并將其轉(zhuǎn)換為4萬噸級的干散貨船船價(jià)，采用概率統(tǒng)計(jì)的方法進(jìn)行隨機(jī)模擬，得出4萬噸級船的船價(jià)為符合對數(shù)正態(tài)分布的隨機(jī)數(shù)，概率密度為：

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

通過對沿海干散貨運(yùn)輸?shù)恼{(diào)研及單船經(jīng)濟(jì)指標(biāo)計(jì)算，得出航次數(shù)、運(yùn)價(jià)、各航線上的運(yùn)量等見表1。

表1 航次數(shù)、運(yùn)價(jià)、各航線上的運(yùn)量

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

圖1 兩種方法計(jì)算結(jié)果比較

可見改進(jìn)后迭代156次即可達(dá)到最優(yōu)，而標(biāo)準(zhǔn)PSO迭代500次還未達(dá)到最優(yōu)，可見改進(jìn)后PSO的有效性。

4 結(jié)束語

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

［1］張德洪，顧家駿.運(yùn)輸船舶船型技術(shù)經(jīng)濟(jì)論證方法［M］.北京：人民交通出版社，1989.

［2］呂振肅，侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法［J］.電子學(xué)報(bào)，2004，32（3）：416-420.

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

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

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

［6］趙 強(qiáng).改進(jìn)的混沌優(yōu)化方法及其應(yīng)用［J］.自動(dòng)化與儀器儀表，2006（3）：90-92.

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

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

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