孫宇博，胡 晶，劉 鑫

(1. 徐州工程學(xué)院管理工程學(xué)院，江蘇 徐州 221008；2. 中南大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410083)

1 引言

自進(jìn)入21世紀(jì)以來(lái)，地震等突發(fā)性災(zāi)害以及各類(lèi)重大事故頻發(fā)，海上突發(fā)重大事故更是頻頻發(fā)生[1]。我國(guó)的領(lǐng)海面積巨大，海岸線(xiàn)綿長(zhǎng)，靠海謀生的漁民不計(jì)其數(shù)，如何為海上應(yīng)急物流選取一條最佳的路徑通道，成為物流領(lǐng)域亟待解決的難題之一[2]。

汪貴慶[3]等人提出基于精英蟻群算法的交通最優(yōu)路徑研究。該方法首先基于Petri網(wǎng)絡(luò)，構(gòu)建精確的多因素交通路網(wǎng)模型；再利用精英蟻群算法對(duì)信息濃度進(jìn)行初始化引導(dǎo)，并采用相互約束的方式尋找兩條以上的路徑；最后通過(guò)對(duì)路徑信息素濃度的計(jì)算，尋找出最佳的路徑。該方法由于未能考慮物流配送過(guò)程中的約束條件，所以該方法選取的配送路徑配送時(shí)間較長(zhǎng)。樊相宇等人[4]提出基于道路堵塞及顧客時(shí)間要求的快件配送最優(yōu)路徑選擇。該設(shè)計(jì)方法首先對(duì)交通網(wǎng)絡(luò)的關(guān)鍵邊以及配送的網(wǎng)絡(luò)特征進(jìn)行計(jì)算；再根據(jù)時(shí)間要求，對(duì)不同的路徑進(jìn)行分析；并依據(jù)最短路徑上的各邊特點(diǎn)，對(duì)各邊對(duì)應(yīng)的路徑進(jìn)行計(jì)算，選取一組備用路徑；最后將符合時(shí)間要求的路徑作為運(yùn)輸?shù)淖罴崖窂剑瓿陕窂降倪x擇。該方法選取路徑的運(yùn)輸安全性能較低，且船艦疏散性能較差。除此之外，常用的路徑優(yōu)化方法還有基于有向圖規(guī)劃的船舶物流運(yùn)輸最優(yōu)路徑選取算法。依據(jù)有向規(guī)劃方法對(duì)物流運(yùn)輸時(shí)的路徑?jīng)_突分流點(diǎn)進(jìn)行確定；再依據(jù)深度優(yōu)先遍歷算法對(duì)分流點(diǎn)進(jìn)行計(jì)算，并逆序打印每一條路徑的計(jì)算結(jié)果，從中選取一條最優(yōu)路徑，以此完成物流的最佳路徑選取，該方法選取路徑的配送距離長(zhǎng)。

為解決上述路徑選取時(shí)存在的問(wèn)題，提出基于柵格GIS的海上應(yīng)急物流最優(yōu)路徑選取方法。

2 路徑優(yōu)化

首先基于柵格GIS技術(shù)對(duì)海上應(yīng)急物流在配送時(shí)存在的影響因素進(jìn)行分析。再利用智能優(yōu)化算法優(yōu)化配送路徑[5]。由于海上物流配送路徑錯(cuò)綜復(fù)雜，在運(yùn)輸中會(huì)產(chǎn)生大量的數(shù)據(jù)，對(duì)這些數(shù)據(jù)的處理效果會(huì)對(duì)物流運(yùn)輸路徑優(yōu)化效果產(chǎn)生影響[6]。然而現(xiàn)有方法不能對(duì)數(shù)據(jù)進(jìn)行有效處理，因此，本文采用柵格GIS技術(shù)對(duì)單格柵格數(shù)據(jù)與多格柵格數(shù)據(jù)同時(shí)進(jìn)行矢量化處理，根據(jù)數(shù)據(jù)處理結(jié)果再對(duì)海上應(yīng)急物流在配送時(shí)存在的影響因素進(jìn)行分析，可以提升路徑優(yōu)化效果。

2.1 挖掘約束條件

海上應(yīng)急物流在進(jìn)行配送時(shí)，船艦會(huì)將各個(gè)港口作為節(jié)點(diǎn)，執(zhí)行物流的配送任務(wù)。而在應(yīng)急物流的配送過(guò)程中，會(huì)受到各類(lèi)約束條件的影響，所以采用柵格GIS技術(shù)對(duì)應(yīng)急物流配送期間可能存在的約束條件進(jìn)行必要的特征點(diǎn)挖掘，成為配送的關(guān)鍵[7]。

在選取應(yīng)急物流配送路徑時(shí)，需要考慮時(shí)間約束問(wèn)題，過(guò)程如下所示

?d∈Dab，[T1+T2]≤Tab

(1)

式中，該次配送的局部最優(yōu)路徑為d，物流配送的出發(fā)點(diǎn)和終點(diǎn)分別為a和b，出發(fā)點(diǎn)與終點(diǎn)之間存在的全部路徑用Dab表示，物流規(guī)定的配送時(shí)間上限為T(mén)ab，而船艦在物流配送過(guò)程中的配送時(shí)間為T(mén)1，到達(dá)時(shí)間為T(mén)2。

其次，應(yīng)急物流在配送過(guò)程中要考慮中轉(zhuǎn)次數(shù)所帶來(lái)的影響，中轉(zhuǎn)次數(shù)約束條件如下式所示

(2)

由于船艦所航行的每一條航線(xiàn)都有船艦運(yùn)力，船艦在配送時(shí)不可超過(guò)極限運(yùn)力，因此，物流配送會(huì)受到航線(xiàn)運(yùn)力的約束，將此約束條件表示為

(3)

2.2 構(gòu)建路徑優(yōu)化模型

整合應(yīng)急物流在配送時(shí)產(chǎn)生的相關(guān)數(shù)據(jù)，如船艦裝載量、航線(xiàn)運(yùn)力等，將整合后的數(shù)據(jù)歸一到一個(gè)數(shù)據(jù)集中。設(shè)定數(shù)據(jù)集內(nèi)的數(shù)據(jù)量為N，數(shù)據(jù)集中每個(gè)數(shù)據(jù)個(gè)體的體積為UV。依據(jù)隨機(jī)生成理論生成物流配送航線(xiàn)；在此基礎(chǔ)上，繼續(xù)生成第二組路徑組合及航線(xiàn)，直至完成配送。匹配過(guò)程中，若無(wú)中轉(zhuǎn)港口，則將本次配送看作直達(dá)配送，以此構(gòu)建有m個(gè)解的路徑優(yōu)化模型[8]。

基于模型的特點(diǎn)以及獲取的約束條件，與目標(biāo)函數(shù)進(jìn)行結(jié)合，搭建配送的適應(yīng)度函數(shù)，過(guò)程如下式所示

(4)

式中，搭建的適應(yīng)度函數(shù)為S，模型中的目標(biāo)函數(shù)為M，函數(shù)中的懲罰系數(shù)為λ，且λ為無(wú)限大。

若構(gòu)建的函數(shù)不能滿(mǎn)足全部的約束條件，則獲取的配送路徑就為局部最優(yōu)而不是全局最優(yōu)，為了獲取全局最優(yōu)解，采用群智能優(yōu)化算法搜索局部混沌區(qū)域。

2.3 搜索局部混沌區(qū)域

路徑優(yōu)化后只能獲取路徑的局部最優(yōu)，而不是全局最優(yōu)。因此，基于改進(jìn)的群智能優(yōu)化算法，對(duì)備選的配送路徑進(jìn)行優(yōu)化處理。設(shè)置映射混沌序列為

φi+1=kφi·(1-φi)，i=1，2，…，q-1

(5)

式中，搜索的隨機(jī)參數(shù)為φi，搜索數(shù)量為q。

在更新完成整個(gè)群體的數(shù)據(jù)后，利用搜索策略對(duì)海上應(yīng)急物流配送路徑的局部混沌區(qū)域進(jìn)行搜索，過(guò)程如下式所示

Xm=(1-σ)X0+σ[r2+φm(r1-r2)]

(6)

式中，獲取的路徑搜索候選解為Xm，經(jīng)過(guò)高斯變異策略獲取的最優(yōu)解為X0，混沌序列中的元素表示為φm，最優(yōu)解空間中的上限與下限分別為r1和r2，搜索過(guò)程中控制收縮程度的參數(shù)為σ。

依據(jù)上述計(jì)算過(guò)程，對(duì)海上應(yīng)急物流的全局域混沌局部搜索，實(shí)現(xiàn)海上應(yīng)急物流的備選配送路徑優(yōu)化。

3 最優(yōu)路徑選取

利用灰色關(guān)聯(lián)系數(shù)對(duì)上述優(yōu)化的路徑進(jìn)行計(jì)算，從而實(shí)現(xiàn)海上應(yīng)急物流的最優(yōu)路徑選取[9]。

3.1 路徑評(píng)價(jià)指標(biāo)

首先，設(shè)定備選路徑有z個(gè)，評(píng)價(jià)指標(biāo)有o個(gè)，基于灰色理論構(gòu)建一個(gè)數(shù)學(xué)模型，過(guò)程如下式所示

R=W×η

(7)

式中，海上應(yīng)急物流的備選路徑綜合評(píng)價(jià)矩陣為R，且R={rz，z=1，2，…，n}，權(quán)重分配矩陣為W，且W={wo，o=1，2，…，m}，基于熵值法確定決策指標(biāo)權(quán)重為wo，η為關(guān)聯(lián)系數(shù)矩陣。

3.2 構(gòu)建評(píng)價(jià)指標(biāo)集

基于獲取的路徑評(píng)價(jià)指標(biāo)，對(duì)備選路徑進(jìn)行量化處理。經(jīng)過(guò)量化后，評(píng)價(jià)指標(biāo)會(huì)具備一致性特征，以此可對(duì)其進(jìn)行關(guān)聯(lián)系數(shù)的計(jì)算。將指標(biāo)分為“小且優(yōu)指標(biāo)”和“大且優(yōu)指標(biāo)”，并借助下式進(jìn)行求解

(8)

式中，備選路徑z的第o個(gè)指標(biāo)初始值為x′zo，而xzo為歸一化后的第z個(gè)路徑上的第o個(gè)指標(biāo)。最后基于上述處理過(guò)程，構(gòu)建規(guī)范的評(píng)價(jià)指標(biāo)集X={xzo}(n×m)。

3.3 最優(yōu)指標(biāo)集

整合備選路徑中不同指標(biāo)的最優(yōu)值，形成一個(gè)最優(yōu)指標(biāo)集，過(guò)程如下式所示

X0=(xo，o=1，2，…，m)

(9)

式中，獲取的最優(yōu)指標(biāo)集為X0。

3.4 計(jì)算指標(biāo)權(quán)重

通常情況下會(huì)根據(jù)層次分析法對(duì)指標(biāo)權(quán)重因子進(jìn)行確定，但是受主觀(guān)因素影響，評(píng)價(jià)結(jié)果不客觀(guān)，所以要利用客觀(guān)賦權(quán)法來(lái)計(jì)算評(píng)價(jià)指標(biāo)的權(quán)重。各個(gè)評(píng)價(jià)指標(biāo)的決策信息可用eo表示，表達(dá)過(guò)程如下所示

(10)

式中，eo為指標(biāo)決策信息，lnxzo為第z個(gè)備選路徑上第o個(gè)指標(biāo)的不確定值。而第o個(gè)指標(biāo)的評(píng)價(jià)數(shù)據(jù)的離散程度如下式所示

(11)

式中，獲取的指標(biāo)離散程度為Po，指標(biāo)的權(quán)重因子為Wo。

3.5 計(jì)算關(guān)聯(lián)度

基于上述計(jì)算結(jié)果，利用灰色系統(tǒng)理論中的灰色關(guān)聯(lián)分析法對(duì)海上應(yīng)急物流備選路徑的關(guān)聯(lián)程度進(jìn)行計(jì)算[10]。首先將獲取的最優(yōu)指標(biāo)集{x0(k)}={x0(1)，x02，…，x0(k)}作為參考數(shù)據(jù)列，并將各個(gè)指標(biāo)集{xo(k)}={xo(1)，xo(2)，…xo(k)}作為被比較數(shù)列，且(o=1，2，…，n)(k=1，2，…，m)。依據(jù)下式計(jì)算備選路徑中第z個(gè)路徑上第o個(gè)評(píng)價(jià)指標(biāo)的關(guān)聯(lián)系數(shù)δz(o)，過(guò)程如下式所示：

δz(o)=

(12)

3.6 綜合評(píng)價(jià)

最后對(duì)備選路徑的優(yōu)劣進(jìn)行排序，從而選擇出海上應(yīng)急物流的最優(yōu)路徑。選擇流程如圖1所示。

圖1 海上應(yīng)急物流的最優(yōu)路徑選擇流程

4 實(shí)驗(yàn)

為了驗(yàn)證所設(shè)計(jì)最優(yōu)路徑選擇方法的整體有效性，需要對(duì)此方法進(jìn)行測(cè)試。

4.1 實(shí)驗(yàn)結(jié)果及分析

分別采用基于柵格GIS的海上應(yīng)急物流最優(yōu)路徑選取方法(方法1)、基于精英蟻群算法的交通最優(yōu)路徑研究(方法2)、基于有向圖規(guī)劃的船舶物流運(yùn)輸最優(yōu)路徑選取算法(方法3)進(jìn)行測(cè)試；

1)隨機(jī)選定一塊海域，對(duì)方法1、方法2以及方法3的海上應(yīng)急物流配送時(shí)間進(jìn)行測(cè)試，測(cè)試結(jié)果如圖2所示。

圖2 三種方法的物流配送時(shí)間測(cè)試結(jié)果

依據(jù)圖2可知，方法1測(cè)試的海上應(yīng)急物流配送時(shí)間均在55小時(shí)至56小時(shí)之間。方法2經(jīng)過(guò)多次實(shí)驗(yàn)可知，海上應(yīng)急物流的配送時(shí)間在58小時(shí)至60小時(shí)之間。而方法3經(jīng)過(guò)多次測(cè)試后可知，海上應(yīng)急物流的配送時(shí)間在61小時(shí)至64小時(shí)之間。綜上所述，方法1所選取的最優(yōu)路徑在物流配送時(shí)的配送時(shí)間短。

2)對(duì)方法1、方法2以及方法3所選取的最優(yōu)路徑的運(yùn)輸距離進(jìn)行測(cè)試，測(cè)試結(jié)果如圖3所示。

圖3 三種方法所選路徑的運(yùn)輸距離測(cè)試結(jié)果

依據(jù)圖3可知，方法1所選路徑的海上應(yīng)急物流運(yùn)輸距離要低于方法2以及方法3。方法3在測(cè)試初期所選路徑的運(yùn)輸距離幾乎與方法1持平，但隨著實(shí)驗(yàn)次數(shù)的增多，方法3所檢測(cè)出的路徑運(yùn)輸距離均為三種方法中最長(zhǎng)的。這主要是因?yàn)榉椒?在物流配送前考慮了配送過(guò)程中可能出現(xiàn)的約束條件，所以方法1選取路徑的運(yùn)輸距離短。

3)對(duì)方法1、方法2以及方法3的船艦疏散性能進(jìn)行測(cè)試，測(cè)試結(jié)果如圖4所示。

圖4 三種方法的船艦疏散性能測(cè)試結(jié)果

依據(jù)圖4可知，方法1在100分鐘內(nèi)可以有效地對(duì)該路徑上的550艘船艦進(jìn)行疏散，而方法2只能疏散不超出350艘的船艦，方法3是三種方法中性能最差的，只能在100分鐘內(nèi)疏散不超過(guò)250艘船艦。綜上所述，方法1所選路徑的船艦疏散性能高。

4)對(duì)方法1備選路徑優(yōu)化前后的路徑運(yùn)輸安全性進(jìn)行測(cè)試，測(cè)試結(jié)果如表1所示。

表1 方法1路徑優(yōu)化前后運(yùn)輸安全性測(cè)試結(jié)果

依據(jù)表1可知，基于柵格GIS的海上應(yīng)急物流最優(yōu)路徑選取方法備選路徑在優(yōu)化前的運(yùn)輸安全性最高可達(dá)94.1%，而考慮約束條件的備選路徑運(yùn)輸安全性最高可達(dá)97.2%。綜上所述，經(jīng)過(guò)優(yōu)化后的備選路徑運(yùn)輸安全性能更好。

5 結(jié)束語(yǔ)

隨著近幾年我國(guó)發(fā)生的嚴(yán)重突發(fā)事件增多，對(duì)于海上應(yīng)急物流的選取變得更加嚴(yán)苛。針對(duì)應(yīng)急物流配送過(guò)程中路徑選擇方法中存在的問(wèn)題，提出基于柵格GIS的海上應(yīng)急物流最優(yōu)路徑選取方法。該方法首先利用柵格GIS技術(shù)與群智能優(yōu)化算法對(duì)備選路徑進(jìn)行優(yōu)化；再基于灰色關(guān)聯(lián)理論對(duì)備選路徑的灰色關(guān)聯(lián)度進(jìn)行計(jì)算，并依據(jù)計(jì)算結(jié)果選取最優(yōu)的路徑進(jìn)行配送。實(shí)驗(yàn)結(jié)果表明，該方法的最優(yōu)路徑配送時(shí)間、配送距離、船艦疏散性能以及輸送安全性均優(yōu)于傳統(tǒng)方法。