考慮惡劣天氣的班輪多階段重調(diào)度方法

王永航，張?zhí)煊睿嵓t星

（大連海事大學(xué)交通運輸工程學(xué)院，遼寧大連 116026）

0 引言

隨著班輪運輸市場競爭的日益激烈，通過降低班輪運輸?shù)某杀厩冶３忠欢ǖ姆?wù)水平來提高企業(yè)競爭力，是航運企業(yè)持續(xù)關(guān)注的問題之一?？紤]到海運中天氣的變化無常，各種惡劣天氣使得很多營運船舶被迫改變原計劃或及時作出各種應(yīng)急對策，又需兼顧班輪公司提前公布的船期和相關(guān)的掛靠港口等因素，研究惡劣天氣影響下船舶的調(diào)度問題是航運公司提升企業(yè)競爭力的關(guān)鍵之一，也是當(dāng)前相關(guān)各方研究的熱點問題。

針對班輪船舶調(diào)度問題，國內(nèi)外很多學(xué)者都對其進行了較為深入細(xì)致的研究，Tierney 等［1］研究了班輪船舶如何準(zhǔn)時到達(dá)指定服務(wù)水平的問題，考慮了時間窗、船舶速度等約束，建立了以船舶成本和總服務(wù)成本最小、總利潤最大多目標(biāo)的三階段數(shù)學(xué)模型，利用模擬仿真進行求解。鄭紅星等［2-3］分別研究了班輪進出港受貨運需求波動和潮汐影響的問題和不定期船舶受泊位可用時間窗和在港可裝可卸的實際情況影響的問題，共同考慮了船期表、航速、船舶大小等約束，構(gòu)建了以運輸總成本最小為目標(biāo)的班輪多船型船舶調(diào)度非線性規(guī)劃模型，設(shè)計了嵌入基因修復(fù)的改進遺傳算法求解。邢江波等［4］研究了針對應(yīng)急情況下班輪集裝箱流的恢復(fù)問題，考慮了調(diào)整航速、縮短在港時間、交換港口掛靠順序和取消港口掛靠的策略，建立了以航運成本最小為目標(biāo)的混合整數(shù)非線性模型，采用精確算法和啟發(fā)式算法分別對模型進行求解。杜劍等［5-6］研究了內(nèi)支線集裝箱班輪航線運營中裝卸箱量、裝卸效率、航行時間及等泊時間皆具有不確定性問題，考慮了掛靠航線的甩箱率與適配船型、準(zhǔn)班率與承諾到港時間的約束，建立了以周期內(nèi)航運成本最低為目標(biāo)的非線性模型，將模擬仿真引入模型與算法進行求解。Wang 等［7］研究了集裝箱班輪的轉(zhuǎn)船與定線、需求不確定性問題與船舶航速優(yōu)化等問題，建立了以總運營成本最小為目標(biāo)的集裝箱班輪船隊調(diào)度模型分析問題。Karsten 等［8］研究了班輪運輸網(wǎng)絡(luò)設(shè)計問題，考慮了船舶之間的協(xié)調(diào)和貨物流動的過境時間限制約束，建立了以港口停靠最大利潤為目標(biāo)的非線性模型，設(shè)計了大鄰域搜索改進啟發(fā)式算法進行求解。Li等［9］研究了班輪運輸實時調(diào)度恢復(fù)策略不確定性和正在出現(xiàn)的中斷事件可能會推遲船只的計劃時間表問題，明確區(qū)分班輪運輸中的兩種不確定性，并提出了相對應(yīng)的策略。Wang 等［10］研究了集裝箱班輪公司的航線會受航運需求及季節(jié)性轉(zhuǎn)變影響的問題，考慮到每條航線應(yīng)該取消或插入某個港口的調(diào)整策略，建立了以總航運成本最小為目標(biāo)的混合整數(shù)線性規(guī)劃模型，設(shè)計了兩階段法啟發(fā)式算法進行求解。Ozcan 等［11］研究了減少班輪運輸在中轉(zhuǎn)過程中的延誤問題，考慮了船舶的停留時間和中轉(zhuǎn)時間等約束，建立了以遵守靠泊時間窗為目標(biāo)的數(shù)學(xué)模型，設(shè)計了新的有效不等式和Benders 分解算法進行求解。Koza 等［12］研究了將服務(wù)調(diào)度整合到班輪運輸網(wǎng)絡(luò)設(shè)計問題，考慮了航行速度優(yōu)化和貨物運輸時間限制等約束，建立以班輪運輸總運輸成本為目標(biāo)函數(shù)的數(shù)學(xué)模型，設(shè)計了高級線性的列生成數(shù)學(xué)方法進行求解。

綜上所述，在現(xiàn)有研究關(guān)于不定期船舶調(diào)度和班輪船舶調(diào)度中，國內(nèi)外大多數(shù)學(xué)者都以航運總成本為目標(biāo)，考慮了貨物時間窗、航速、船舶在港時間及中轉(zhuǎn)時間等約束，并設(shè)計了啟發(fā)式算法來求解；但是考慮惡劣天氣影響導(dǎo)致封港的調(diào)度極少，在實際情況中班輪公司遇到此情況往往會在其他港口等待或者用下一班次進行運輸，因此在實際工作中惡劣天氣導(dǎo)致的封港對班輪的影響巨大，包括準(zhǔn)班率、艙位變動、航線變動導(dǎo)致的成本增加，以及客戶的滿意度，乃至下一班次的計劃等，為此需在提前預(yù)知天氣信息的前提下及時對營運船舶做出合理的調(diào)度方案。

區(qū)別于已有研究，本文從整個航運網(wǎng)絡(luò)的視角出發(fā)，在班輪公司船期表已定的情況下，重點考慮惡劣天氣導(dǎo)致封港對班輪運輸?shù)挠绊?，為確保整個計劃期內(nèi)已訂艙的貨物能按期抵達(dá)目的港，最終給出部分航段運輸計劃的動態(tài)調(diào)整方案和部分船舶掛靠港口的最佳次序。

1 問題描述與解決策略

1.1 問題描述

某班輪公司在固定計劃期內(nèi)，根據(jù)I個港口之間的裝卸貨物量和V艘不同類型的船舶，規(guī)劃了L條航線；而在實際運營過程中，船舶掛靠的港口因受惡劣天氣影響未能按提前公布的船期表運輸貨物，由此給班輪公司和客戶帶來了極大的損失。為了減少由于惡劣天氣影響帶來的損失和避免給下一班次造成影響，班輪公司要在同一班次的固定計劃期內(nèi)解決問題，可通過航運大數(shù)據(jù)提前3～4 天獲知惡劣天氣所影響的港口，即能準(zhǔn)確得知將要掛靠下一港口能否掛靠的情況，確定將被影響港口所在的航線，再通過航運大數(shù)據(jù)定位此時的船舶坐標(biāo)、船舶艙位情況和航行速度等信息；班輪公司在固定計劃期初始執(zhí)行既定的船舶調(diào)度計劃，以設(shè)計的多階段重調(diào)度機制向前滾動收集惡劣天氣信息，直到此班輪公司有船執(zhí)行該航運網(wǎng)絡(luò)上最長航線的末段航運任務(wù)時結(jié)束。

設(shè)計的多階段重調(diào)度機制如下：從計劃期初始，調(diào)度時間開始向前滾動，班輪公司實時收集惡劣天氣信息，當(dāng)收到惡劣天氣信息后，分析這些惡劣天氣是否影響該公司正在執(zhí)行航運任務(wù)船舶的下一個目的港，若不影響則繼續(xù)滾動直到三天后截止，為一個再調(diào)度時段，并以該時刻為下一個再調(diào)度時段的起始，在調(diào)度時以該時刻受影響航線上營運船舶坐標(biāo)的下一個不受惡劣天氣影響目的港口為調(diào)度起點，針對所影響航線中未掛靠的港口進行船舶調(diào)度；若影響則直接終止?jié)L動，采用多階段重調(diào)度機制，且以此時的船舶坐標(biāo)為起點立刻進行船舶調(diào)度，并以該時刻為下一個再調(diào)度時段的起始。然后繼續(xù)以此機制向前滾動，示意圖如圖1所示。

圖1 多階段重調(diào)度機制安排Fig.1 Arrangement of multi-stage rescheduling mechanism

本文問題可描述為：針對某一航運網(wǎng)絡(luò)上的某一家班輪公司，在固定計劃期內(nèi)，已知船舶數(shù)量、船舶容量、船舶經(jīng)濟航速及最大航速、港口數(shù)量及港口間距離和提前公布的船期表，以及航運網(wǎng)絡(luò)上該班輪公司所有運營船舶的實時坐標(biāo)、艙位情況和航行速度等信息，以設(shè)計的多階段重調(diào)度機制收集天氣信息，在獲知某些港口遭遇惡劣天氣沖擊的時段后，為確保已訂艙貨物的船期，以固定計劃期內(nèi)所有船舶的總航運成本最小為優(yōu)化目標(biāo)，通過多階段重調(diào)度機制給出班輪船舶的最佳調(diào)度方案。

1.2 解決策略

考慮班輪航線的特點和惡劣天氣的隨機性，班輪公司一般采用以下策略對船舶進行多階段重調(diào)度：

1）貨物中轉(zhuǎn)策略。由于惡劣天氣的影響致使某一港口在一段時間內(nèi)不能掛靠，或一批貨物的目的港遭受惡劣天氣影響，為不影響其他貨物的班期，可采取貨物中轉(zhuǎn)方案，即選取距離較近的港口為貨物中轉(zhuǎn)港，通過租船或跨航線調(diào)船將該港貨物運至中轉(zhuǎn)港。

2）租船直運策略。由于惡劣天氣影響某一港口，可采用租船直運的方式，即租船將該港口的貨物直運到目的港口。

3）跨航線調(diào)船策略。船舶在預(yù)設(shè)航線上裝載貨物完成，但處于未滿載狀態(tài)且可滿足其他港口的貨運需求，可離開原來設(shè)定的航線并轉(zhuǎn)至該港口裝載貨。

4）反掛策略。即在時間窗允許的情況下，跨過被惡劣天氣影響的港口，先掛靠后一港口再返回被惡劣天氣影響的港口進行掛靠。

此外，船舶一般采用經(jīng)濟航速航行，有時為了滿足貨物的班期，可采用最大航速航行，但需支付較高的額外航運費用。

通常出現(xiàn)惡劣天氣等應(yīng)急情況，可能需要上述多種解決策略的組合才能確保已訂艙貨物按期抵達(dá)目的港，本文就是以上述所有策略為基礎(chǔ)，兼顧航速的調(diào)整，最終得出惡劣天氣影響下的船舶最佳調(diào)度方案。

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

2.1 模型假設(shè)

1）針對掛靠的港口面臨惡劣天氣不能掛靠，且這些異常天氣情況可在掛靠下一目的港前3天，通過航運大數(shù)據(jù)已知；

2）初始港已知，且不考慮從終止港返回；

3）貨物到達(dá)港口的時間窗必須滿足；

4）各個港口間都可進行租船運輸；

5）兩港之間船舶行駛的速度不變（一直為最大航速或一直為經(jīng)濟航速）。

2.2 參量

I為港口集合；V為船舶集合；[ETi，STi]為i港的貨物時間窗；[ETBi，STBi]為i港被惡劣天氣影響的時間窗；dij為i港和j港距離（海里）；Cij為單位貨量的i和j港間的租船成本（元/集裝箱）；Fi為i港的港口使用費（元）；FRi為中轉(zhuǎn)港口使用費；為v船的經(jīng)濟航速（海里/時）；為v船的最大航速（海里/小時）為v船經(jīng)濟航速的單位運輸成本（元/海里）為v船最大航速的單位運輸成本（元/海里）；Mv為v船的容量（箱）；為在已知惡劣天氣時刻，v船已裝載的容量（箱）；Oij為i港和j港使用租船運輸?shù)呢浳飻?shù)量（箱）；OiR為i港和樞紐港使用租船運輸?shù)呢浳飻?shù)量（箱）；Lvij為v船舶在i港裝載j港的貨物數(shù)量（箱）為v船到達(dá)i港的時刻為v船到達(dá)第一個港的時刻為v船離開i港的時刻。

決策變量：

2.3 模型構(gòu)建

式（1）航運最小成本包括運輸成本、租船成本、港口使用費和中轉(zhuǎn)港口使用費；式（2）保證掛靠路徑的連續(xù)性；式（3）表示在v船已裝載的容量不得超過額定裝載量；式（4）表示船舶的連續(xù)裝載量不得超過額定裝載量；式（5）表示船舶裝載的貨物數(shù)量和租船運輸?shù)呢浳飻?shù)量總和滿足兩港的貨流需求；式（6）表示v船只能掛靠無惡劣天氣影響的港口；式（7）表示使用租船從i港至中轉(zhuǎn)港口Ri裝載貨物量總和滿足兩港的貨流需求；式（8）表示若船舶在i港裝載j港的貨物數(shù)大于船舶剩余裝載量，則采用租船直運策略將i、j港之間的貨物進行調(diào)運；式（9）表示由于兩港貨物需求的變化量，若自有大型船舶容量遠(yuǎn)大于港間貨物需求，采用貨物中轉(zhuǎn)港策略；式（10）表示船舶在i、k、j港裝載的貨物數(shù)總和滿足兩港的貨流需求的變化量，且滿足船舶剩余裝載量，采用跨航線調(diào)船策略；式（11）和（12）表示船舶的抵港時間需滿足港口的時間窗要求；式（13）表示船舶掛靠第一個港口從0 時刻開始計算；式（14）表示到達(dá)j港的時刻要大于從i港出發(fā)的時刻；式（15）和（16）表示船舶到達(dá)各港口的時刻不能在惡劣天氣時間窗內(nèi)。

3 求解方法

由于本文構(gòu)建的數(shù)學(xué)模型是非線性模型，且約束條件較多，為此，針對問題特點設(shè)計了嵌入基因修復(fù)算子的改進遺傳算法（Improved Genetic Algorithm，IGA）進行求解，算法步驟如下所述。

3.1 染色體編碼

由于本文涉及船舶掛靠港口的次序、船舶從一個港口到下一港口的航速、自有船舶或租船在各個港口實際裝載的貨物量，故采用三層編碼。其中，第一層代表的是掛靠港口的次序，用編號為0，1，…進行實數(shù)編碼，且不能重復(fù)；第二層代表的是航速，由于在本文中只有經(jīng)濟航速和最大航速兩種，故采用0-1 二進制編碼，0 為低速，1 為高速；第三層代表的是實際裝載的貨物量，其中實際裝載的貨物量都為整數(shù)，故采用實數(shù)編碼；第四層代表的是天氣狀況，由于本文只考慮良好天氣和惡劣天氣，故采用二進制編碼，0 為良好天氣，1 為惡劣天氣。例如掛靠港口次序為10的染色體具體編碼如表1所示。

表1 染色體編碼Tab.1 Chromosome coding

3.2 初始種群初步優(yōu)化策略

步驟1 根據(jù)3.1節(jié)的編碼規(guī)則隨機生成初始種群。

步驟2 將初始種群中所有個體采用如下操作進行初步優(yōu)化：隨機選擇一個個體對應(yīng)染色體中兩個不同的掛靠港口，相互交換即改變船舶掛靠港口順序，若同時滿足式（6）、（13）、（14）且能改善目標(biāo)函數(shù)則執(zhí)行此操作；否則不執(zhí)行，并將其全部轉(zhuǎn)入步驟3。

步驟3 在初步優(yōu)化后的所有個體中隨機選取兩個個體形成一組，選取一組個體組合。

步驟3.1 對于被選中的組合進行如下操作：對其兩條染色體中同一位置的掛靠港口進行交換，若同時滿足式（6）、（13）、（14）且能改善目標(biāo)函數(shù)則執(zhí)行此操作；否則不執(zhí)行。

步驟3.2 若已經(jīng)選擇完所有初步優(yōu)化的個體，則結(jié)束此策略；否則選擇下一組個體組合，轉(zhuǎn)入步驟3.1。

3.3 適應(yīng)度評價

在適應(yīng)度評價方面，將適應(yīng)度值函數(shù)與目標(biāo)函數(shù)進行轉(zhuǎn)化，本文優(yōu)化目標(biāo)為航運成本最小，顯然要使目標(biāo)函數(shù)值越小，染色體個體的適應(yīng)度越大，如式（17）所示：

3.4 最優(yōu)保存策略

對于個體的選擇，一般采用輪盤賭法，但往往會陷入局部最優(yōu)，本文為避免此缺點，采用最優(yōu)保存策略。

步驟1 選擇父代種群中適應(yīng)度最大即航運成本最小的個體，保存其不進行交叉、變異。

步驟2 將剩余父代種群進行交叉、變異生成子代種群。

步驟3 選擇子代種群中最差個體和步驟1 中個體的適應(yīng)度值比較，若前者小于后者，則進行替換；否則，不進行替換。

3.5 交叉變異

在進行交叉變異時，由于本文采用三層編碼且第一、三層和第二層的編碼方式不同，故每層采用的交叉、變異的方式不同。

其中，第一層和第三層采用兩點交叉的方式。例如第一層進行兩點交叉，設(shè)有父代染色體X1和染色體X2，首先選取第四個基因節(jié)點和第七個基因節(jié)點為交叉點，然后將這兩個交叉點之間的基因相互調(diào)換，其中3-9、4-7、5-8、6-1 代表著基因之間的映射關(guān)系，再依次對調(diào)兩交叉點外的基因，且保證互調(diào)后的基因沒有重復(fù)，最終得到子代染色體和染色體如圖2所示。

圖2 第一層染色體交叉示意圖Fig.2 Schematic diagram of first layer of chromosome crossing

第二層編碼中采用單點交叉的方式，例如設(shè)有父代染色體X3和染色體X4，進行交叉時先選取第六個基因節(jié)點，讓兩個染色體的第六個基因節(jié)點互換，從而生成兩個新的子代染色體和染色體如圖3所示。

圖3 第二層染色體交叉示意圖Fig.3 Schematic diagram of second layer of chromosome crossing

三層染色體的變異操作都采用逆轉(zhuǎn)變異，即在某條染色體中隨機挑選兩個逆轉(zhuǎn)點，然后將兩個逆轉(zhuǎn)點間的基因值以逆轉(zhuǎn)概率Pi逆向排序。以第一層為例，設(shè)有染色體X5，從中選取第六個基因和第十個基因為逆轉(zhuǎn)點，然后將這兩個逆轉(zhuǎn)點之間的基因逆向排序，最終得到變異染色體X′5，如圖4所示。

圖4 第一層染色體變異示意圖Fig.4 Schematic diagram of first layer of chromosome variation

由于天氣狀況已知，所以第四層編碼不采取交叉、變異操作。

3.6 基因修復(fù)算子

在形成新個體產(chǎn)生后，可能會產(chǎn)生不可行解，有如下情況。

情況1 染色體變異可能會將港口基因變異成被惡劣天氣影響港口的基因，船舶掛靠的港口一定是無惡劣天氣影響的港口，因此將不滿足約束個體，按以下步驟進行修復(fù)：

步驟1 檢查個體的第一層編碼，若有港口被惡劣天氣影響的基因，則轉(zhuǎn)到步驟2；否則轉(zhuǎn)到步驟3。

步驟2 將此基因刪掉，隨機在此位置插入無惡劣天氣影響的港口基因。

步驟3 輸出新個體。

情況2 在船舶滿載的條件下，則調(diào)度該船舶無意義，需將不滿足約束個體按以下步驟進行修復(fù)：

步驟1 重點檢查該個體的第三層編碼，若有船舶滿載，則轉(zhuǎn)到步驟2；否則轉(zhuǎn)到步驟3。

步驟2 將此條染色體刪掉，重新生成新的染色體，并轉(zhuǎn)回步驟1。

步驟3 輸出新個體。

此過程在交叉變異后執(zhí)行，形成新種群，否則返回初始種群。

3.7 終止條件

終止條件為預(yù)設(shè)的最大迭代次數(shù)時停止，輸出適應(yīng)度最高的染色體，并將給出其掛靠港的順序、兩港之間的航速選擇情況以及裝卸貨情況。

3.8 算法求解流程

步驟1 染色體編碼并生成初始種群。

步驟2 根據(jù)初始種群初步優(yōu)化策略進行首次優(yōu)化。

步驟3 計算適應(yīng)度，并采用最優(yōu)保留策略選擇個體。

步驟4 對染色體進行交叉、變異，形成新種群。

步驟5 將新生成的種群進行基因修復(fù)。

步驟6 判斷是否滿足最大迭代次數(shù)，若滿足則算法結(jié)束；否則返回步驟3。

4 算例分析

4.1 算例描述

為檢驗算法的效果，結(jié)合國內(nèi)某班輪公司所經(jīng)營的近洋航線為例。某班輪企業(yè)有5 艘船舶（船舶參數(shù)已知），10 個港口（各港口的貨運需求量已知），根據(jù)各港口的貨運需求量已制定了以15 天為周期的船期表。在營運過程中，各港口由于天氣變化因素導(dǎo)致的封航影響船舶掛靠港口。針對此情況，以確保除被惡劣天氣影響不能掛靠的港口外到達(dá)其他各港口貨運時間窗不變的前提下，達(dá)到固定計劃期內(nèi)所有船舶總航運成本最小的船舶調(diào)度。船舶參數(shù)如表2 所示，其中1 海里/時=1.852 km/h，各港口的數(shù)據(jù)如表3～5 所示，TEU（Twentyfeet Equivalent Unit）是以長度為20 英尺（1 英尺=0.3 m）的集裝箱為國際計量單位。

表2 船舶相關(guān)參數(shù)Tab.2 Related parameters of ships

表3 港間距離 單位：海里Tab.3 Distances between ports unit：mile

表4 港口使用費Tab.4 Usage fee of port

表5 貨運量及時間窗Tab.5 Freight volumes and time windows

航運企業(yè)根據(jù)經(jīng)驗將五艘船掛靠在各個港口，并給出掛靠港口順序，如表6所示。

表6 掛靠港口順序情況Tab.6 Order of reaching ports

4.2 算例優(yōu)化方案

本案例在運營過程中，設(shè)置滾動時段長度為3 天，通過模擬航運大數(shù)據(jù)獲取實時天氣情況已知，設(shè)置惡劣天氣時間窗為兩天，并隨機選取港口東京港口在［7，8］時間窗內(nèi)有惡劣天氣影響，所以C、D、E 船舶在此期間掛靠東京的港口時會受影響。使用Matlab 編程軟件進行計算求解，設(shè)定初始種群規(guī)模100，當(dāng)?shù)螖?shù)達(dá)到500 時終止，船舶在港間的調(diào)度情況如表7所示。

表7 船舶港間調(diào)度情況Tab.7 Ship scheduling between ports

由于惡劣天氣影響和時間窗約束，東京港口的貨物采用了租船直運策略，船舶直達(dá)神戶目的港口，并以神戶港口為貨物中轉(zhuǎn)港，C、D、E 都為跨航線調(diào)船策略。同時由于貨物關(guān)系影響，船D 和E 分別在神戶港口和東京港口停留等待貨物，并經(jīng)過5 次實驗取平均值得到最小船舶調(diào)度成本為3 439 689元，而傳統(tǒng)辦法進行等待的成本為4 154 237 元，由此可知多階段調(diào)度機制較傳統(tǒng)辦法節(jié)約了714 548元。

由于惡劣天氣進行變動，再次通過航運大數(shù)據(jù)獲取實時天氣情況已知，隨機選取大連港口在［12，13］時間窗內(nèi)有惡劣天氣影響導(dǎo)致封航，C 號船舶在此期間掛靠大連港口時會受影響，再次采用本文模型和算法進行多階段重調(diào)度，采用Matlab 編程軟件進行計算求解，設(shè)定初始種群規(guī)模100，當(dāng)?shù)螖?shù)達(dá)到500 時終止，在Intel Core i5 2450M 2.5 GHz 的處理器，4 GB 內(nèi)存的CPU 上進行求解，船舶在港間的最優(yōu)動態(tài)調(diào)度方案如表8所示。

由于惡劣天氣影響和時間窗約束，C 號船舶對大連港口的貨物采用了反掛策略，調(diào)換原來方案的掛靠順序，先掛靠青島港口再返回去掛靠大連港口，避免了惡劣天氣對大連港口的影響；多行駛了223 海里，并得到最小船舶調(diào)度成本為3 491 549 元，比之前調(diào)度成本多了51 860 元；在保證貨物時間窗的情況下，此調(diào)度成本是可接受的。

4.3 方案有效性

通過對照表7和表8以及對應(yīng)貨物時間窗的對比，其船舶到達(dá)港口的貨物時間窗均滿足要求，未造成貨物運輸延誤；且該方案的調(diào)度成本較小，將C、D和E號船舶都進行調(diào)度，避免了惡劣天氣影響港口時間導(dǎo)致封航無法進行運輸?shù)膯栴}，隨后利用租船通過航次直運的方案和中轉(zhuǎn)港的方案，更好地滿足了所有固定船舶的航線運輸，并且相較于傳統(tǒng)等待辦法節(jié)約了422 662 元，節(jié)約了總成本的15.1%，大大節(jié)約了航運總成本。

表8 船舶港間再調(diào)度情況Tab.8 Ship rescheduling between ports

為驗證方案的有效性，進行了大、中、小三種規(guī)模的算例實驗，每組算例結(jié)果經(jīng)過5 次實驗取平均值，并與傳統(tǒng)等待方案進行對比，偏差均在15%以上，大大節(jié)約了航運總成本，其具體內(nèi)容如表9所示。

表9 多階段重調(diào)度方案和傳統(tǒng)等待方案比較Tab.9 Comparison of multi-stage rescheduling scheme and traditional waiting scheme

4.4 算法性能分析

4.4.1 有效性分析

本文采用Cplex求解驗證算法有效性，但目標(biāo)函數(shù)及部分約束為非線性，需要將其進行線性轉(zhuǎn)化，具體如下：

1）在目標(biāo)函數(shù)中，運輸成本一項為非線性，需將δvij×yvij部分進行轉(zhuǎn)化，令μvij=δvij×yvij，其中：

2）式（14）為非線性約束，并進行如下轉(zhuǎn)化：

將所有公式線性化處理后，用Cplex 求解，最終將兩種方法根據(jù)港口數(shù)和船舶從小規(guī)模到大規(guī)模進行比較，其結(jié)果如表10所示。

經(jīng)比較可知，Cplex 只在小規(guī)模計算中用時較短，改進遺傳算法在相對較大的規(guī)模中優(yōu)勢較為明顯，計算速度遠(yuǎn)快于Cplex的計算速度；在比較目標(biāo)值偏差時，所有偏差值均在5%以內(nèi)。因此，本文的改進遺傳算法適用于求解較大規(guī)模的船舶調(diào)度問題。

表10 改進遺傳算法和Cplex比較Tab.10 Comparison of improved genetic algorithm and Cplex

4.4.2 優(yōu)越性分析

為驗證算法的優(yōu)越性，本文同時針對此問題，用蟻群優(yōu)化（Ant Colony Optimization，ACO）算法參數(shù)設(shè)定最大迭代次數(shù)500，種群規(guī)模為200；禁忌搜索（Tabu Search，TS）算法［13］參數(shù)設(shè)定最大迭代次數(shù)為500，最優(yōu)值連續(xù)不變次數(shù)為100，鄰域規(guī)模為100，短禁忌表長度為25，長禁忌表長度為50；量子差分進化（Quantum Differential Evolution，QDE）算法［14-15］參數(shù)設(shè)定最大迭代次數(shù)為500，種群規(guī)模為200，收縮因子為0.9，量子交叉為0.3。分別進行求解，最終將四種算法根據(jù)港口數(shù)和船舶從小規(guī)模到大規(guī)模進行比較，其結(jié)果如表11～12所示。

其中，表11中AGAP、TGAP、QGAP分別表示IGA與ACO、TS、QDE 求解本文問題時所得目標(biāo)函數(shù)值之差占IGA 所獲目標(biāo)函數(shù)值的比例，表12 中GAP1、GAP2、GAP3 分別表示IGA與ACO、TS、QDE 求解本文問題時CPU 耗時之差占IGA 求解時CPU 耗時的比例。經(jīng)比較可知，蟻群優(yōu)化（ACO）算法和禁忌搜索（TS）算法在計算中用時較短，但在比較目標(biāo)值偏差時，所有偏差值均在10%以上；改進遺傳算法在計算時間和目標(biāo)值上均優(yōu)于量子差分進化（QDE）算法。通過比較可知，改進遺傳算法能在有效時間內(nèi)降低成本，驗證了本文的改進遺傳算法的優(yōu)越性。

表11 改進遺傳算法和其他算法的目標(biāo)函數(shù)值比較Tab.11 Comparison of objective function value between improved genetic algorithm and other algorithms

表12 改進遺傳算法和其他算法的CPU耗時比較Tab.12 Comparison of CPU time cost between improved genetic algorithm and other algorithms

4.5 靈敏度分析

通過對問題的分析，發(fā)現(xiàn)惡劣天氣影響港口的數(shù)量和時間窗對目標(biāo)函數(shù)的影響較大，因此針對以上兩個方面進行靈敏度分析。

在實際情況中，港口被惡劣天氣影響會根據(jù)港間的位置關(guān)系所決定，以臺風(fēng)為例，會按一定路徑影響所經(jīng)過的港口，同時影響太多港口則無法調(diào)度，且此種情況極少出現(xiàn)。因此在惡劣天氣影響的時間窗為固定的基礎(chǔ)上，設(shè)定港口被惡劣天氣影響的數(shù)量為一至三個，步長為一個港口。在不同規(guī)模下進行三次實驗，結(jié)果取平均值，其結(jié)果如表13所示。

表13 惡劣天氣影響港口數(shù)量的靈敏性分析（總航運成本） 單位：元Tab.13 Sensitivity analysis of number of ports affected by severe weather（total shipping cost） unit：yuan

由結(jié)果可知，惡劣天氣影響港口的數(shù)目越多，總航運成本越高。且當(dāng)港口數(shù)和船數(shù)處于小規(guī)模時，總航運成本隨惡劣天氣影響港口數(shù)目的增加而更明顯；當(dāng)港口數(shù)和船數(shù)處于大規(guī)模時，總航運成本隨惡劣天氣影響港口數(shù)目的增加而更細(xì)微。

為了分析惡劣天氣影響港口時間窗對目標(biāo)函數(shù)的影響，以實際情況可知，重大惡劣天氣最多影響港口封港三天，因此在惡劣天氣影響的港口個數(shù)為固定的基礎(chǔ)上，設(shè)定惡劣天氣影響港口時間窗為一至三天，步長為一天。在不同規(guī)模下進行三次實驗，結(jié)果取平均值，其結(jié)果如表14所示。

表14 惡劣天氣影響港口時間窗的靈敏性分析（總航運成本） 單位：元Tab.14 Sensitivity analysis of severe weather affecting port time windows（total shipping cost） unit：yuan

由結(jié)果可知，惡劣天氣影響港口的時間窗對總航運成本影響波動較大，影響天數(shù)越長其總航運成本越高。

通過對比兩次實驗結(jié)果可以發(fā)現(xiàn)，不論是受惡劣天氣影響港口的數(shù)目還是受惡劣天氣影響港口的時間窗，都對目標(biāo)函數(shù)產(chǎn)生了極大的影響。

5 結(jié)語

本文研究了惡劣天氣影響下班輪公司船舶的調(diào)度優(yōu)化問題，以固定計劃期內(nèi)區(qū)域航運網(wǎng)絡(luò)上該班輪公司所有營運船舶為研究對象，在滿足提前公布船期表的前提下，設(shè)計了多階段重調(diào)度機制，考慮了航速變化和船舶容量等約束，構(gòu)建了以總航運成本最小為優(yōu)化目標(biāo)的非線性模型，設(shè)計了多層編碼的改進遺傳算法且融入了基因修復(fù)算子進行求解，可給出最佳的多階段重調(diào)度方案。結(jié)果表明，通過對部分航段的運輸計劃靈活采用多階段重調(diào)度機制并結(jié)合中轉(zhuǎn)、租船直運、跨航線調(diào)船和反掛等策略，可有效地降低惡劣天氣的影響，能為班輪公司因惡劣天氣原因的實際應(yīng)急調(diào)度提供參考。

后續(xù)研究可以對惡劣天氣數(shù)據(jù)進行收集、整理并通過航運大數(shù)據(jù)預(yù)測全年的惡劣天氣情況，為班輪公司提前做好全年的航線配船規(guī)劃、部分短期航線的開辟計劃和租船計劃等。