應(yīng)對樞紐失效的軸輻式網(wǎng)絡(luò)樞紐備份

胡晶晶，黃有方

(上海海事大學(xué)經(jīng)濟(jì)管理學(xué)院，上海201306)

(*通信作者電子郵箱yhuang@shmtu.edu.cn)

0 引言

軸輻式網(wǎng)絡(luò)物流系統(tǒng)中，軸輻式網(wǎng)絡(luò)樞紐點(diǎn)存在失效風(fēng)險(xiǎn)，失效后的恢復(fù)策略包括樞紐設(shè)施和通道的重新修復(fù)和備份。維護(hù)軸輻式網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn)需要考慮投入成本及一些不確定因素，如:翁克瑞［1］研究帶固定軸線成本的軸輻式網(wǎng)絡(luò)，強(qiáng)調(diào)合并運(yùn)輸?shù)墓潭ㄝS線成本，用拉格朗日算法求解;Yang等［2］考慮金融和服務(wù)的不確定性，提出了一種模糊雙目標(biāo)軸輻式網(wǎng)絡(luò)設(shè)計(jì)問題，用兩階段法求解;Yang等［3］針對交通成本和時(shí)間的混合不確定性，提出了綜合的軸輻式網(wǎng)絡(luò)規(guī)劃和優(yōu)化問題。有學(xué)者考慮軸輻式網(wǎng)絡(luò)中樞紐失效的風(fēng)險(xiǎn)進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)可靠性研究，如:Zhalechian等［4］在運(yùn)營和破壞風(fēng)險(xiǎn)的基礎(chǔ)上設(shè)計(jì)一個(gè)具有彈性的軸輻式樞紐網(wǎng)絡(luò)，考慮了三個(gè)主要的彈性維度，包括主動(dòng)能力、反應(yīng)能力和設(shè)計(jì)質(zhì)量;An等［5］針對樞紐和反應(yīng)中斷管理的失敗可能會給軸輻式網(wǎng)絡(luò)帶來恢復(fù)成本的問題，提出了可靠的軸輻式網(wǎng)絡(luò)設(shè)計(jì)模型，在此模型中考慮了備用中心和備選路線的選擇，以主動(dòng)地處理樞紐中斷問題。

軸輻式網(wǎng)絡(luò)中的失效和恢復(fù)主要研究樞紐功能的變化失效和備份策略。Mohammadi等［6］建立混合隨機(jī)規(guī)劃模型研究不確定情況下軸輻式網(wǎng)絡(luò)中持續(xù)的樞紐點(diǎn)位置的確定，并使用蟻群算法對大規(guī)模的實(shí)際數(shù)據(jù)進(jìn)行計(jì)算驗(yàn)證;楊珺等［7］提出了考慮延遲懲罰并面向整個(gè)軸輻式網(wǎng)絡(luò)的節(jié)點(diǎn)完全中斷問題，建立節(jié)點(diǎn)中斷的上、下界模型;劉舒佶［8］提出軸輻式網(wǎng)絡(luò)樞紐功能性中斷問題和模型，并通過數(shù)據(jù)測試比較遺傳算法和禁忌搜索算法的優(yōu)劣;Mohammadi等［9］考慮了樞紐的全部或者部分失效，設(shè)計(jì)基于樞紐位置問題的可靠軸輻式物流網(wǎng)絡(luò)。以上文獻(xiàn)的作者研究整個(gè)軸輻式網(wǎng)絡(luò)的可靠性，但沒有重點(diǎn)突出樞紐失效的應(yīng)對方式。

進(jìn)行精確計(jì)算的數(shù)學(xué)求解器和遺傳算法在求解軸輻式網(wǎng)絡(luò)問題方面都有所應(yīng)用。Azizi等［10］研究軸輻式網(wǎng)絡(luò)樞紐失效的影響，分別采用數(shù)學(xué)求解器CPLEX和遺傳算法求解，比較分析了單個(gè)備份樞紐和多個(gè)備份樞紐策略。Kratica等［11］使用兩段編碼法和適當(dāng)?shù)哪繕?biāo)函數(shù)，運(yùn)用兩種遺傳算法進(jìn)化方法研究美國貨運(yùn)航空軸輻式網(wǎng)絡(luò)。王雅琪等［12］利用遺傳算法研究非線性規(guī)模經(jīng)濟(jì)效應(yīng)下軸輻式網(wǎng)絡(luò)樞紐選址問題。軸輻式網(wǎng)絡(luò)研究用到的方法還有博弈論，Sasaki等［13］競爭環(huán)境下的斯塔伯格模型軸輻式網(wǎng)絡(luò)樞紐選址，設(shè)計(jì)了大型多樞紐軸輻式交通網(wǎng)絡(luò)。將軸輻式網(wǎng)絡(luò)的研究和車輛調(diào)度相結(jié)合，呂婷等［14］建立了軸輻式網(wǎng)絡(luò)下的車輛調(diào)度模型，設(shè)計(jì)了基于啟發(fā)式調(diào)度規(guī)則的節(jié)約算法進(jìn)行求解。魏素豪等［15］構(gòu)建了基于單分配、多樞紐、混合式網(wǎng)絡(luò)結(jié)構(gòu)特征的軸輻式公共交通網(wǎng)絡(luò)優(yōu)化模型，用模擬退火算法求解。

本文從提高軸輻式物流網(wǎng)絡(luò)的安全穩(wěn)定性角度，針對軸輻輻式網(wǎng)絡(luò)中樞紐失效可能阻斷正常的貨流，預(yù)先為每個(gè)樞紐選擇備份樞紐點(diǎn)，研究經(jīng)過備份樞紐后流量的流經(jīng)路線和流量大小的變化，求解不同成本權(quán)重下，初始軸輻式網(wǎng)絡(luò)成本和備份樞紐構(gòu)建成本的變化及對軸輻式網(wǎng)絡(luò)結(jié)構(gòu)的影響。

1 問題描述

初始軸輻式網(wǎng)絡(luò)中紐點(diǎn)若失效轉(zhuǎn)化為節(jié)點(diǎn)，其余樞紐點(diǎn)負(fù)荷增大，需要新的樞紐點(diǎn)來替代原樞紐點(diǎn)。并非樞紐失效之后才進(jìn)行備份樞紐點(diǎn)的選擇，而是給正常的樞紐點(diǎn)選擇備份樞紐點(diǎn)。問題研究每個(gè)樞紐點(diǎn)的備份樞紐點(diǎn)的選擇，分析影響備份樞紐的因素，不同備份樞紐的選擇對總成本的影響，由備份樞紐和輻節(jié)點(diǎn)構(gòu)成新的軸輻式網(wǎng)絡(luò)的合理性。目標(biāo)函數(shù)包括失效前的網(wǎng)絡(luò)構(gòu)建成本和應(yīng)對失效的備份成本，并賦予權(quán)重α。分析目標(biāo)函數(shù)中兩部分投入成本的重要性占比權(quán)重α設(shè)置對軸輻式網(wǎng)絡(luò)結(jié)構(gòu)的影響。

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

由于整個(gè)數(shù)學(xué)規(guī)劃的約束較多，將應(yīng)對樞紐失效的樞紐備份模型分成兩部分闡述，分別是初始軸輻式網(wǎng)絡(luò)基本模型和樞紐備份擴(kuò)展模型。

2.1 初始軸輻式網(wǎng)絡(luò)基本模型

初始軸輻式網(wǎng)絡(luò)構(gòu)建基本模型設(shè)計(jì)有兩個(gè)決策變量，決定樞紐選址的0/1變量xij和表示經(jīng)過樞紐點(diǎn)的貨物OD(Origin to Destination)流的yikl，變量和參數(shù)設(shè)置如表1所示。當(dāng)貨流的起始點(diǎn)與目的點(diǎn)同屬于一個(gè)樞紐點(diǎn)時(shí)，不考慮樞紐點(diǎn)之間的規(guī)模運(yùn)輸。

目標(biāo)函數(shù)f1權(quán)重為α，如式(1)所示，總成本包括有四個(gè)部分，分別為:樞紐點(diǎn)的建設(shè)成本(式(2));貨物由起始點(diǎn)運(yùn)到樞紐點(diǎn)過程中的收集成本(式(3));由樞紐點(diǎn)運(yùn)至目的節(jié)點(diǎn)的配送成本(式(4));干線運(yùn)輸成本(式(5));式(6)為節(jié)點(diǎn)分配關(guān)系約束，表示每一個(gè)節(jié)點(diǎn)只能作為樞紐節(jié)點(diǎn)或是樞紐點(diǎn)的輻節(jié)點(diǎn)，不能獨(dú)立存在;式(7)表示只有當(dāng)xkk為1時(shí)，即選擇節(jié)點(diǎn)k作為樞紐節(jié)點(diǎn)，才能夠?qū)⑵渌?jié)點(diǎn)分配至節(jié)點(diǎn)k，否則節(jié)點(diǎn)k不能擁有輻節(jié)點(diǎn);式(8)為節(jié)點(diǎn)i的貨物流量平衡約束;式(9)為輔助約束，用以確保模型在節(jié)點(diǎn)距離不嚴(yán)格符合三角行不等式時(shí)仍然可以使用;式(10)、(11)為約束變量屬性。

表1 初始軸輻式網(wǎng)絡(luò)變量和參數(shù)Tab.1 Variables and parameters of initial hub and spoke network

2.2 樞紐備份擴(kuò)展模型

樞紐備份擴(kuò)展模型引入了新的變量和約束，用以表達(dá)樞紐備份思想，在原有的樞紐之間選擇合適的備份樞紐，目標(biāo)函數(shù)求樞紐備份成本。這部分模型是非線性的。

1)目標(biāo)函數(shù)。當(dāng)軸輻式網(wǎng)絡(luò)由備份樞紐點(diǎn)重新構(gòu)成時(shí)，新的成本產(chǎn)生且區(qū)別于正常情況下的成本，這部分成本的權(quán)重為1－α。式(12)目標(biāo)函數(shù)f2由三部分構(gòu)成。式(13)表示節(jié)點(diǎn)i經(jīng)過原樞紐點(diǎn)k的貨物由備份樞紐b替代，距離參數(shù)也從節(jié)點(diǎn)i到k變?yōu)楣?jié)點(diǎn)i到b，計(jì)算在選擇了備份樞紐b后的收集成本。式(14)表示經(jīng)過備份樞紐b的分配成本。式(15)表示干線之間的流量運(yùn)輸由樞紐k的備份樞紐l進(jìn)行，這一部分計(jì)算的是選擇一個(gè)備份樞紐后的干線運(yùn)輸成本。因?yàn)樵趂1中已經(jīng)計(jì)算了樞紐選址時(shí)產(chǎn)生的樞紐建設(shè)成本，備份樞紐是在已有的樞紐中選擇的，因此不重復(fù)計(jì)算樞紐建設(shè)成本。這一部分的成本f2主要計(jì)算備份樞紐構(gòu)建的新的軸輻式網(wǎng)絡(luò)的物流成本，是資源投入用于防范樞紐失效后軸輻式網(wǎng)絡(luò)失效的備份成本。

2)變量和約束。表2為擴(kuò)展模型的新增變量的設(shè)置。式(16)、(17)表示當(dāng)一個(gè)點(diǎn)是樞紐點(diǎn)時(shí)才可以被選為備份樞紐，研究的備份樞紐選擇策略是從已有的樞紐中選擇備份樞紐，當(dāng)然，備份樞紐也可以從節(jié)點(diǎn)中選擇，可以使原來的節(jié)點(diǎn)升級為樞紐點(diǎn)再選為備份樞紐，這里只從樞紐點(diǎn)中選擇備份樞紐。式(18)表示每個(gè)樞紐點(diǎn)都有一個(gè)備份樞紐點(diǎn)，單個(gè)樞紐失效單個(gè)樞紐備份。式(19)表示當(dāng)樞紐點(diǎn)k選為樞紐點(diǎn)a的備份樞紐點(diǎn)時(shí)，原來經(jīng)過樞紐a和樞紐l之間的流量重新經(jīng)過樞紐k和樞紐l。

表2 擴(kuò)展模型變量Tab.2 Variables of extended model

3)非線性部分的線性化。模型中的計(jì)算涉及到原樞紐點(diǎn)和備份樞紐點(diǎn)，具有一定的復(fù)雜性，數(shù)學(xué)規(guī)劃是非線性的，用變量替代的方法進(jìn)行線性化。在式(20)、(21)中，把xik·zkb原來的樞紐選址決策變量xik和備份樞紐選擇變量zkb的乘積用變量 hikb表示，hikb=xik·zkb，hikb≥ xik+zkb－ 1，其中 hikb=1表示節(jié)點(diǎn)i分配給樞紐點(diǎn)k，且樞紐點(diǎn)b選為樞紐點(diǎn)k的備用樞紐點(diǎn)。在式(22)至(24)中，zak·yial用變量viakl表示，并給出了線性化的變量代換過程。整數(shù)viakl=zak·yakl，viakl≥yial+(zak－1)M，viakl表示由節(jié)點(diǎn)i到樞紐點(diǎn)a的流量重新經(jīng)過樞紐點(diǎn)k和備份樞紐l。用變量代換的方法增加了模型中的變量，將目標(biāo)函數(shù)中的非線性乘積關(guān)系轉(zhuǎn)化成有實(shí)際意義的具體變量，使非線性規(guī)劃轉(zhuǎn)化為線性規(guī)劃。

擴(kuò)展模型如下:

線性化如下:

總成本F式(25)由f1和f2構(gòu)成，并分別賦予權(quán)重:

備份是為了預(yù)防樞紐失效或中斷風(fēng)險(xiǎn)導(dǎo)致的軸輻式網(wǎng)絡(luò)的失效。備份樞紐也會產(chǎn)生一定成本，合理的備份樞紐的設(shè)置可以和正常情況下的軸輻式網(wǎng)絡(luò)成本進(jìn)行平衡使總成本最低。

3 實(shí)驗(yàn)算例與分析

模型分別使用數(shù)學(xué)求解器CPLEX和遺傳算法求解:

1)將擴(kuò)展模型非線性部分線性化，線性化后和軸輻式網(wǎng)絡(luò)初始模型一起構(gòu)成了該問題的混合整數(shù)線性規(guī)劃;Matlab調(diào)用CPLEX求解這個(gè)混合整數(shù)線性規(guī)劃模型。

2)原模型遺傳算法求解。

3.1 模型線性化之后的 CPLEX求解

1)軸輻式網(wǎng)絡(luò)基本參數(shù)和權(quán)重敏感性分析。

CPLEX計(jì)算規(guī)模為16個(gè)設(shè)施點(diǎn)，目標(biāo)函數(shù)F中成本f1賦予的權(quán)重為α，備份樞紐選擇成本f2的權(quán)重為1－α。設(shè)置基本參數(shù)Cc、Cd、Ct，α為A、B、C、D四組不同的值依次如表3，對于每一組基本參數(shù)，設(shè)置權(quán)重 α 的變化取值為(0.1，0.3，0.5，0.7，0.9)。由于軸輻式網(wǎng)絡(luò)結(jié)構(gòu)還受到流量影響，在算例中固定流量矩陣wij。如表3，每一組樞紐點(diǎn)都會得到相同數(shù)量的備用樞紐點(diǎn)，備用樞紐點(diǎn)從原樞紐點(diǎn)中選擇。有些樞紐點(diǎn)是重復(fù)選為備用樞紐點(diǎn)的。權(quán)重α的值依次遞增，初始成本f1、樞紐備份下的成本f2和總成本F都在改變。隨著權(quán)重的增加，樞紐點(diǎn)的數(shù)量在減少。因?yàn)闄?quán)重的增加使f1所占的總成本的比例增加，f1的值是不斷升高的，樞紐的選址在初始軸輻式網(wǎng)絡(luò)中計(jì)算得到，因此當(dāng)原軸輻式網(wǎng)絡(luò)的成本f1增大時(shí)，樞紐的數(shù)量會不斷減少以使總成本得到優(yōu)化。

如圖1選取B、C參數(shù)繪制縱坐標(biāo)成本f1、f2，F(xiàn)隨橫坐標(biāo)權(quán)重α的變化趨勢。由圖1可知，原樞紐成本f1增加，備份成本f2減少，總成本F先增加，后有小幅降低但仍高于起始點(diǎn);α決定了f1、f2在成本投入所占的比重。備份成本主要由備份樞紐點(diǎn)構(gòu)成的軸輻式網(wǎng)絡(luò)成本。不同的軸輻式網(wǎng)絡(luò)結(jié)構(gòu)下選擇備份樞紐后網(wǎng)絡(luò)結(jié)構(gòu)變化的復(fù)雜程度也是不一樣的。圖2中分別給出了不同參數(shù)設(shè)置下8個(gè)樞紐點(diǎn)、6個(gè)樞紐點(diǎn)、4個(gè)樞紐點(diǎn)的備份策略和軸輻式網(wǎng)絡(luò)結(jié)構(gòu)的改變。備份樞紐點(diǎn)一旦選定，它和輻節(jié)點(diǎn)的關(guān)系也重新得到了調(diào)整。設(shè)置的樞紐點(diǎn)較多時(shí)，有較少的輻節(jié)點(diǎn)需要被重新分配到備用樞紐點(diǎn);當(dāng)設(shè)置的樞紐點(diǎn)個(gè)數(shù)較少時(shí)，備份樞紐點(diǎn)更易于選取。

在圖2(a) 中，第1、2、7、8、14 這五個(gè)樞紐點(diǎn)相距較近，第10、11、12這三個(gè)樞紐距離較近，它們選擇備份樞紐也是在各自的聚集區(qū)域內(nèi)選擇。如1的備份樞紐是14，2的備份樞紐是8，7的備份樞紐是1，8的備份樞紐是2。

2)樞紐點(diǎn)容量敏感性分析。

考慮樞紐容量對備份樞紐影響時(shí)的目標(biāo)函數(shù)和樞紐容量設(shè)置如下:

1)中基本參數(shù)和權(quán)重敏感性分析中分析了不同的收集成本、分配成本和轉(zhuǎn)運(yùn)成本系數(shù)以及權(quán)重對樞紐分配和備用樞紐選擇的影響，保持1)中基本參數(shù)不變，進(jìn)一步觀察樞紐容量是否影響備份樞紐的選擇，在目標(biāo)函數(shù)中加入?yún)?shù)樞紐容量v，算例結(jié)果顯示樞紐容量也會影響到軸輻式網(wǎng)絡(luò)結(jié)構(gòu)，改變樞紐容量的大小對軸輻式網(wǎng)絡(luò)結(jié)構(gòu)和備份樞紐點(diǎn)的選擇也有一定的影響。為了降低節(jié)點(diǎn)間距離對樞紐選址的影響，體現(xiàn)樞紐容量參數(shù)的敏感性，改變坐標(biāo)系，使各個(gè)節(jié)點(diǎn)的分布更加均勻。

表3 不同參數(shù)下備份樞紐的選擇Tab.3 Selection of backup hubs under different parameters

圖1 B、C兩組參數(shù)下成本f1、f2、F隨權(quán)重α的變化Fig.1 Change of cost f1，f2and F with the weight of α under two groups of parameters of B and C

如表4所示，保持權(quán)重 α 為 0.1不變，Cc=0.1、Cd=0.7、Ct=0.6分別比較無容量限制和樞紐容量為v時(shí)的樞紐選址和備用樞紐選擇策略，加入樞紐容量限制后，樞紐個(gè)數(shù)明顯減少，同時(shí)備份樞紐也發(fā)生了變化。

在應(yīng)急情況下，若是樞紐的容量足夠大，樞紐間的轉(zhuǎn)運(yùn)相似于樞紐之間的備份選擇策略，網(wǎng)絡(luò)結(jié)構(gòu)也不需要作較大的調(diào)整。

圖2 不同參數(shù)設(shè)置下的備份樞紐選擇Fig.2 Backup hub selection under different parameter settings

表4 樞紐容量對備份樞紐的影響Tab.4 Influence of hub capacity on backup hubs

3.2 樞紐備份遺傳算法求解

1)算法設(shè)計(jì)。

軸輻式網(wǎng)絡(luò)樞紐備份為非線性問題，利用遺傳算法計(jì)算大規(guī)模軸輻式網(wǎng)絡(luò)的樞紐選址和備份，體現(xiàn)了遺傳算法全局優(yōu)化、計(jì)算效率高的優(yōu)勢。使用樞紐選址數(shù)據(jù)集(http://people.brunel.ac.uk/～ mastjjb/jeb/info.html)用 Matlab 遺傳算法工具箱求解。遺傳算法基本設(shè)置:種群規(guī)模20;染色體基因數(shù)200;交叉概率0.7;變異概率0.4;執(zhí)行代數(shù)200。有兩個(gè)主要決策變量:軸輻式網(wǎng)絡(luò)的樞紐點(diǎn)和相應(yīng)的備份樞紐點(diǎn)。編碼為0、1，給出一組染色體為樞紐選址的初始解。解碼為1的點(diǎn)為樞紐點(diǎn)，在對備份樞紐的操作中，重新分配所有的原樞紐節(jié)點(diǎn)給備份樞紐點(diǎn)。

適應(yīng)度函數(shù)根據(jù)目標(biāo)函數(shù)α(ff+fc+fd+ft)+(1－α)(pc+pd+pt)進(jìn)行評估，計(jì)算中令不變的固定成本ff為零。目標(biāo)函數(shù)求解最小總成本，在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)綜合考慮樞紐選址和備份樞紐選址對總成本的影響，調(diào)整α值觀察變化。

在遺傳操作中，選擇操作采用輪盤賭法，選擇距離最近的節(jié)點(diǎn)。交叉方法為單點(diǎn)交叉如圖3。變異方法為單點(diǎn)變異，交換樞紐點(diǎn)基因位置。

圖3 單點(diǎn)交叉Fig.3 Single point cross

2)遺傳算法結(jié)果。

Matlab繪制遺傳算法進(jìn)化過程如圖4所示，α為0.5，樞紐點(diǎn)個(gè)數(shù)為16，停止迭代時(shí)最大適應(yīng)度值和平均適應(yīng)度值變化不大、趨于穩(wěn)定，適應(yīng)度值中最優(yōu)值收斂于1.26609E+08，平均值收斂于1.28755E+08。由圖4(d)得到初始樞紐選址圖形，初始樞紐對應(yīng)的備份樞紐也計(jì)算得出，如表5所示。

圖4 遺傳算法進(jìn)化過程Fig.4 Evolutionary process of genetic algorithm

遺傳算法得到的軸輻式網(wǎng)絡(luò)樞紐點(diǎn)和對應(yīng)的備份樞紐點(diǎn)及成本變化情況如表5所示。

遺傳算法計(jì)算規(guī)模為200個(gè)點(diǎn)，實(shí)驗(yàn)中6、9、16個(gè)樞紐選址和樞紐備份求解時(shí)間均低于CPLEX的計(jì)算時(shí)間。隨著α值增加，雖然f2在總成本的比例變小，f1比例增大，由于f1中的固定成本ff設(shè)置為零，f1增加的速率小于f2減小的速率，所以當(dāng)f2減少時(shí)，總成本減少。同時(shí)，選址的樞紐位置之間也越來越遠(yuǎn)。綜上，適應(yīng)度函數(shù)中樞紐備份成本f2對總成本F和樞紐點(diǎn)位置的影響是敏感的。

4 結(jié)語

本文建立混合整數(shù)非線性規(guī)劃模型，探討軸輻式網(wǎng)絡(luò)樞紐備份策略，分別用遺傳算法求解原模型，用CPLEX求解線性化的模型，得出了軸輻式網(wǎng)絡(luò)樞紐備份問題的優(yōu)化解，并分析影響軸輻式網(wǎng)絡(luò)樞紐選址和樞紐備份的影響因素，以優(yōu)化軸輻式網(wǎng)絡(luò)構(gòu)建成本和備份成本。

表5 遺傳算法求解結(jié)果Tab.5 Solution result of genetic algorithm

提高物流系統(tǒng)的可靠性，需要有效的網(wǎng)絡(luò)系統(tǒng)管理策略，如樞紐點(diǎn)備份。備份樞紐的研究在應(yīng)急物流中的災(zāi)民疏散區(qū)選址、帳篷募集地設(shè)置、零擔(dān)物流中的備用倉庫選址都有實(shí)際的應(yīng)用意義。接下來的研究可以從多個(gè)樞紐失效、多個(gè)備份樞紐方面進(jìn)行，其中樞紐失效對樞紐通道的影響和恢復(fù)也值得進(jìn)一步探討。