支線航運網絡下集裝箱分配與船舶調度聯合優化

孔靈睿, 計明軍, 孫以寧, 關云瀟, 郭興海

(大連海事大學交通運輸工程學院,遼寧大連 116026)

1 引 言

在經濟全球化的影響下,海運貿易量不斷增長,集裝箱運輸行業在過去的數十年間呈快速、穩定的發展趨勢. 2018 年,全球集裝箱海運量已達到2.01 億TEU.集裝箱海運業的強勁發展,有力推動了集裝箱船舶的大型化. 目前,全球最大集裝箱船舶的運載能力已超過20 000 TEU.然而大型集裝箱船舶在為船公司帶來規模經濟效益的同時,其靠港的吃水要求也決定了大型集裝箱船舶只能掛靠在吃水較深的干線港. 而僅靠干線港之間的干線運輸難以滿足全方位的現代化運輸需求,國際集裝箱海運格局逐步由原來單一的港到港的運輸向著干線運輸和支線運輸相結合的方向衍化,形成了以樞紐港(干線港)為轉運中心的軸輻式航運網絡. 以樞紐港口為中心的軸輻式航運網絡,是海運一體化進程中出現的一種能夠適應全球海運系統的網絡形態[1],Msakni 等也通過實例驗證了應用軸輻式航運網絡的重要意義[2]. 在軸輻式航運網絡中,大船通常被用來服務于各大樞紐港之間的干線運輸以獲得規模經濟效益,小船則被用來完成支線運輸任務以滿足樞紐港所對應若干喂給港(支線港)的運輸需求[3]. 對于軸輻式航運網絡,需要明確樞紐港的位置、喂給港的掛靠方案以及樞紐港之間的班輪運輸航線和服務時間表.在此基礎上,如何規劃最優的支線集裝箱船舶調度方案,實現支線運輸成本的最小化,就成為了船公司日常需要考慮的重要問題.

支線集裝箱船舶運輸網絡同車輛路徑問題(vehicle routing problem,VRP)的網絡相似,均是包含一個配送中心(樞紐港)以及若干顧客點(喂給港)的二級運輸網絡,如圖1 虛框內部分所示.

圖1 二級支線運輸網絡Fig.1 The two-level feeder transportation network

從現代供應鏈和產業鏈的角度看, 海上集裝箱運輸僅是其中的一個環節, 只能滿足客戶的部分需求.2016 年起,以馬士基集團與法國達飛輪船為首的集裝箱航運巨頭試圖將供應鏈整合戰略應用到海洋運輸服務中. 盡管戰略執行有所不同,但均以加強海洋與內陸腹地的連接、接近海洋服務終端客戶為目標,以期深化企業與用戶合作,打造共贏、共存和良性發展的供應鏈生態圈. 為順應這一發展趨勢,本文將產生集裝箱運輸任務的貨源點加入至軸輻式航運網絡的支線運輸網絡中,構建三級支線運輸網絡,如圖2 所示.

圖2 三級支線運輸網絡Fig.2 The three-level feeder transportation network

不同于傳統的支線運輸網絡,三級支線運輸網絡不僅需要對支線集裝箱船舶調度方案進行決策,還需同時考慮各貨源點的集裝箱到喂給港的分配方案.即貨源點的集裝箱并非提前分配至相應的喂給港,而是同支線集裝箱船舶調度計劃進行聯合優化. 若一個貨源點的集裝箱通過不同的喂給港進行運輸,最優的支線船舶調度方案可能會發生很大的變化,最小的運輸成本也將隨之改變.通過構建三級支線網絡并對其進行聯合優化研究,能夠為航運企業向供應鏈終端整合提供思路,同時可以降低整體支線網絡的總運輸成本.

以往有關軸輻式航運網絡的研究主要集中在樞紐港之間的干線運輸上[4-7],有關支線船舶調度的研究較少. 關于支線船舶調度問題,Sambrocos 等[8]將其看作是車輛路徑問題(VRP)的一個擴展,認為支線船舶調度是從樞紐港出發,向喂給港運貨的具有容量約束的VRP;靳志宏等[9]同樣將VRP 理論應用到支線集裝箱船舶調度問題中,在現有研究的基礎上,加入對船舶容量約束與時間窗約束的考慮,構建了混合整數優化模型,并采用粒子群算法進行求解;Karlafti 等[10]考慮了更多的實際情況,研究了喂給港既有卸箱需求也有裝箱需求的情況下,樞紐港與眾多喂給港之間的支線集裝箱船舶調度問題,并采用混合遺傳算法進行求解;為探究船型的選擇對于支線集裝箱船舶運輸成本的影響,Ji 等[11]構建了多船型的支線集裝箱船舶調度優化模型,并設計改進遺傳算法進行求解;考慮船舶航速對于支線船舶調度方案的影響,Santini[12]等,計明軍等[13]研究了可變航速下的支線船舶調度問題.然而,以往的研究均是基于二級支線網絡,假定各喂給港的裝箱量已知,即各個貨源點的集裝箱已提前分配至相應的喂給港,再對支線集裝箱船舶調度方案進行優化. 缺乏對于供應鏈終端的貨源點的考慮,因此難以適應航運企業向供應鏈終端進行整合的發展趨勢,也無法使整體支線運輸網絡的總成本達到最小.

而對于車輛路徑問題, 也有學者將其拓展為三級運輸網絡. 其中與本研究最為相似的是考慮需求分配的車輛路徑問題(vehicle routing with demand allocation problem,VRDAP).該問題最早由Ghoniem 等[14]提出,應用于非營利性的食物配送方面,以最小化運輸距離為目標建立了混合整數規劃模型并設計了精確求解算法進行求解; Solak 等[15]以及Reihaneh 等[16]隨后也分別設計了更優的精確求解算法對VRDAP 進行求解. 本文研究的實質可以看成是VRDAP 在支線航運網絡的應用,但又與VRDAP 研究有著較大的區別:VRDAP 研究假設所有的車輛具有相同的運載能力,而本文的三級支線運輸網絡中包含兩種運載工具,集裝箱運輸船舶與集裝箱運輸車輛,且在實際運輸過程中存在著不同大小的支線集裝箱船舶,因此需要對船舶不同的運載能力進行考慮;VRDAP 研究僅考慮了配送問題,而支線集裝箱船舶運輸既需考慮卸船需求也需考慮裝船需求;VRDAP 研究沒有考慮任何時間上的約束,而相比于陸路運輸節點,集裝箱航運港口具有更為嚴格的時間要求,包含喂給港的作業時間窗以及樞紐港的運輸時刻表.從研究內容以及約束條件上看,本文的研究都更為復雜,更貼合支線集裝箱船舶運輸的實際情況.

基于上述考慮,本文將貨源點加入至傳統的支線運輸網絡中,將傳統的二級支線運輸網絡拓展成三級支線運輸網絡. 針對支線集裝箱船舶運輸的特點,考慮船舶容量、喂給港時間窗以及樞紐港運輸班期等現實因素,分析貨源點集裝箱在喂給港的分配與支線船舶調度計劃之間的內在聯系,對集裝箱分配方案以及支線集裝箱船舶調度計劃進行聯合優化,以期能夠降低整個三級支線運輸網絡的總成本,為航運企業的升級轉型提供有益借鑒.

2 問題描述與數學模型

如圖3 所示,本文研究的三級支線運輸網絡包括一個樞紐港、掛靠在該樞紐港下的喂給港以及若干產生集裝箱運輸任務的貨源點.通過對比圖3 中的兩個不同的運輸方案可知,若某一貨源點的集裝箱被分配至另一個不同的喂給港,那么最終的支線船舶調度方案可能會發生改變,運輸成本也會隨之發生變化.若提前確定好貨源點的集裝箱到喂給港的分配,并不能夠使得整個三級支線網絡的總成本達到最小. 因此需要對集裝箱分配以及支線船舶調度進行聯合優化,以最小化三級支線網絡的總運輸成本.

圖3 貨源點集裝箱在不同喂給港的分配對支線船舶調度方案的影響Fig.3 The impact of the container distribution among different feeder ports on the feeder routing plan

在本文所描述的網絡中,從樞紐港到每個喂給港的卸箱量已知,每個喂給港的裝箱量則是分配至該喂給港的集裝箱量的總和.若某一喂給港既沒有卸載集裝箱,也沒有任何一個貨源點的集裝箱被分配至該喂給港,則不需要任何一艘集裝箱船舶掛靠至該喂給港. 本文不但考慮船舶到達各喂給港的時間窗約束,也考慮所有貨源點的集裝箱必須在規定時間點之前送至樞紐港的班期約束. 此外,本文考慮多種船型的集裝箱船舶,不同類型的集裝箱船舶具有不同的容量、經濟航速與運輸費用.

本文需要解決的問題包括為每個貨源點的集裝箱選擇裝船的喂給港、為有集裝箱運輸需求的喂給港分配指定船舶并確定每艘船舶的運輸路線,以滿足運輸需求、船舶容量及時間窗限制,并使得船舶運輸與集裝箱分配(集裝箱從貨源點至喂給港的運輸成本)的總成本最小.

2.1 模型假設

基于支線集裝箱船舶運輸的特點,提出如下假設:

1)任意喂給港最多只能由一艘船舶掛靠;

2)所有的支線集裝箱船舶均從樞紐港出發,完成相應的裝卸任務后,最終返回樞紐港;

3)在喂給港卸下的集裝箱全部來自樞紐港,且在喂給港裝船的集裝箱只能運輸至樞紐港,即喂給港之間不存在集裝箱流量;

4)所有貨源點的集裝箱均不能被拆分,即某一貨源點的集裝箱必須全部運輸至同一喂給港;若同一位置的集裝箱允許被運往不同的喂給港,則被視為不同的貨源點;

5)在調度的過程中需要保證每一個貨源點的運輸需求都被滿足.

2.2 模型構建

為了構建數學模型,定義如表1 所示的參數和變量.

表1 參數與變量說明Table 1 Description of parameters and variables

基于表1 中的參數以及變量定義,集裝箱分配與多船型支線集裝箱船舶調度聯合優化模型為

其中式(1)中的目標函數表示最小化船舶運輸和集裝箱分配的總成本,即最小化三級支線網絡的總運輸成本;約束(2)定義了變量gi,若喂給港i有卸船集裝箱,或至少有一個貨源點被分配至喂給港i,則喂給港i有運輸需求,gi= 1,否則,gi= 0;約束(3)表示每個有運輸需求的喂給港有且僅有一艘集裝箱船舶掛靠,若某一喂給港沒有運輸需求,則該喂給港沒有集裝箱船進行掛靠;約束(4)規定所有集裝箱船舶均從樞紐港出發,其中若xkOO′=1,則表示船舶k沒有被實際投入使用,是一條虛擬航線;約束(5)可以保證運輸流的平衡,即駛入某一喂給港的集裝箱船舶必須從該喂給港駛出;約束(6)定義了船舶從一個港口到達下一個港口的時間,保證了船舶航行的連續性,且能夠消除子回路;約束(4)～約束(6)相結合可以保證每艘集裝箱船舶僅分配一條運輸航線,且最終均返回樞紐港;約束(7)定義了集裝箱船在樞紐港進行裝船作業的時間;約束(8)定義了集裝箱船舶在喂給港進行裝卸作業的時間;約束(9)保證船舶到達喂給港的時間滿足喂給港的時間窗要求;約束(10)保證船舶返回樞紐港的時間滿足船上所有集裝箱必須運至樞紐港的最晚時間要求;約束(11)定義了船舶在樞紐港的裝箱量;約束(12)保證喂給港的運輸需求全部被滿足(分配至某一喂給港的貨源點的集裝箱在該喂給港全部被裝船);約束(13)表示船舶的容量約束;約束(14)定義喂給港的裝箱量;約束(15)保證每一個貨源點均被分配至一個喂給港.

假設貨源點的數量為M, 包含樞紐港在內的港口的數量為N, 可以選擇的船型的數量為H. 對于一個喂給港來說,其緊前喂給港有N-1 種可能,其緊后喂給港的選擇也有N-1 種可能,可選的船型數量為H,那么該喂給港共可能生成H(N-1)2種方案;對于N-1 個喂給港,最多可產生H(N-1)3種方案;對于貨源點的分配共可能產生M(N-1)種方案,因此問題的復雜度最終可表示為MH(N-1)4. 隨著喂給港以及貨源點數量的增加,使用線性求解器對模型(1)進行直接求解會消耗大量的時間,因此在本文的第3節設計了求解算法對大規模問題進行求解.

2.3 兩階段求解模型與算法

為了驗證整合優化集裝箱分配與支線船舶調度的優勢與必要性, 在本節中介紹兩階段求解模型與算法(兩階段求解算法),用來作為第3 節中所提出的整合優化求解算法的對比基礎.基于本文所研究問題的特性,可以很容易的將問題拆分成第一階段的集裝箱分配問題以及第二階段的支線集裝箱船舶調度問題.兩階段求解算法描述如下:

步驟1 集裝箱分配

在第一步進行集裝箱的分配,目標是最小化總分配成本. 此外,為了能夠得到較好的最終解,在第一步分配集裝箱時也一定程度的考慮船舶運輸成本.由于此時船舶的具體行駛路徑是未知的,船舶運輸成本是通過計算船舶從樞紐港到各個有運輸需求的喂給港的總運輸成本來進行粗略的估計.因此第一階段的目標函數可以表示為最小化集裝箱分配成本與粗略估計的船舶運輸成本的加權平均成本,如式(16)中的目標函數所示(在集裝箱分配模型中,γ為0-1 之間的小數,表示集裝箱分配成本在目標函數中所占的比重;模型中涉及到的其他符號的表示同模型(1)).

其中約束(17)保證每個貨源點都被分配且僅分配至一個喂給港;約束(18)能夠保證得到相應的集裝箱分配方案后,在第二階段進行船舶調度的過程中不會超過船舶的容量約束;約束(19)定義了變量gi.

該模型可直接使用線性求解器進行求解.

步驟2 支線集裝箱船舶調度

當每個貨源點的集裝箱都被分配至相應的喂給港后,原問題就變成了已知集裝箱分配以及各個喂給港運輸需求的支線集裝箱船舶調度問題.兩階段算法第二階段的支線集裝箱船舶調度模型與模型(1)結構相同,不同點為在支線集裝箱船舶調度模型中,模型(1)中的變量gi和yci成為了已知參數,為兩階段算法中第一階段的求解結果.關于此階段模型的求解算法并非本文研究重點,采用以往研究中已提出的啟發式算法進行求解. 由于本文考慮的是多船型下的支線集裝箱船舶調度問題,因此參考文獻[11]中描述的遺傳算法對兩階段算法的第二階段進行求解.

3 基于列生成的整合優化求解算法

3.1 列生成求解算法原理及框架

列生成算法是求解大規模整數規劃問題的優化算法,其理論是由Danzig 等[17]提出的Dantzig-Wolfe 分解. 目前,該算法被用于對VRP 進行求解,并取得了很好的效果[18-19]. 考慮到本文所研究的問題為VRP 的一個變形與拓展,因此參考求解VRP 的列生成算法,基于本文所研究問題的特性,設計基于列生成的求解算法對問題進行求解.

應用列生成算法,首先是根據分解原理將模型(1)進行分解變型,生成與模型(1)等價的,擁有同樣最優解的集分割模型. 在集分割模型中,用單一加權約束代替了多面體集約束大大減少了約束的數目,但因這個多面體的頂點可能非常多,因此增加了約束矩陣的列數. 而這種多列的問題則可以采用列生成技術進行求解.

對于集分割模型, 首先將其線性松弛并將松弛后的集分割模型稱為主問題(master problem, MP)模型.若n代表MP 模型的變量數量,m表示MP 模型的約束數量,根據集分割模型的特點可知n遠遠大于m. 因此MP 模型的基本可行解的數量可表示為Cmn,即其可行域的頂點有Cmn個.當n很大時,即使m較小,總極點數量也十分的龐大.因此列生成算法的基本思想為:使用主問題模型所有列的部分子集構建受限主問題(restricted master problem,RMP)模型,并對RMP 模型進行求解,然后通過迭代向RMP 模型中加入能夠使得RMP 模型的目標函數值繼續降低的列(最小化問題),直至無法找到這樣的列時,即求得MP 模型的最優解. 實際上,在線性規劃的最優解里,基變量的數目永遠不會超過約束數目. 因此可以不用在求解時生成全部的列,只是在需要的時候才生成新的列添入至模型當中,這樣就可以使用較少的列獲得MP 模型的最優解,能夠大大加快求解的速度.

新加入列的原則是基于求解線性規劃的單純型法原理: 在列生成算法中,將RMP 模型中未加入的列默認為MP 模型的非基變量. 如在未加入的列中存在某一列s,其檢驗數小于0(最小化問題),那么列s的加入會使得RMP 模型的目標函數值進一步降低,因此需要將列s加入至RMP 模型中再次求解RMP 模型. 這個過程反復進行直至不存在檢驗數小于0 的列為止,則說明MP 問題已求得最優解. 由于MP 模型的列十分的多,不可能通過枚舉方法來找到可加入的列,因此要構造一個子問題(sub-problem,SP)模型,來獲得可加入的列并判斷MP 模型的最優性. 典型的,通過這種交互方法,只需要進行有限次迭代即可獲MP 模型的最優解.

在求得MP 模型的最優解后,將0-1 整數變量約束加入至當前的RMP 模型即可求得集分割模型的整數解. 本文所設計基于列生成的整合優化求解算法的具體步驟總結如下:

步驟1 構建集分割模型,并松弛其整數約束以構造MP 模型(見3.2 節);

步驟2 以兩階段算法最終求得的集裝箱分配以及船舶調度方案作為列生成算法的初始可行解(即初始列);

步驟3 用初始列構建RMP 模型(一條可行的船舶路徑及相應的集裝箱分配方案對應著RMP 模型的一列);

步驟4 構建能為RMP 模型生成新列,且能夠判斷MP 模型最優性的SP 模型(見3.3 節);

步驟5 用線性求解器Gurobi 求解RMP 模型,獲得當前RMP 模型的對偶變量值;

步驟6 將當前的對偶變量值代入SP 模型,求解SP 模型,如果沒有可添加的列(任何未加入列的加入均無法使RMP 模型獲得更小的目標函數), 則MP 模型已求得最優解, 轉入步驟7. 若存在可添加的列使得RMP 模型的目標函數值能夠進一步降低,則將相應列加入至RMP 模型中,轉入步驟5;

步驟7 向當前的RMP 模型中加入0-1 整數變量約束,求得集分割模型的整數解.

3.2 集分割模型

集分割模型的部分參數定義如表2 所示,其余參數同模型(1).

表2 參數與變量說明Table 2 Description of parameters and variables

其中模型(20)的目標函數表示最小化方案的總成本,與模型(1)的目標函數等價;式(21)表示每一個貨源點均被分配且僅被分配一次;式(22)表示若pi=0,則喂給港i最多被一條船舶路徑訪問,若pi ＞0,即有從樞紐港運輸至喂給港i的集裝箱,則該喂給港必須被訪問且僅被訪問一次.

至此, 模型(1)被轉化為與其等價的集分割模型. 模型(1)原本有大量的約束, 而集分割模型的約束僅為|C|+|Ω|個,與模型(1)相比大為減少. 在集分割模型中,每一個列都代表著一個可行的方案.

為應用列生成算法,首先將集分割模型進行線性松弛,將zr ∈{0,1}替換為0 ≤zr≤1,并稱線性松弛后的集分割模型為主問題模型(MP 模型).

3.3 子問題模型

根據單純型法的原理,把檢驗數小于0 的列代入至RMP 模型中迭代,能夠優化當前最優解. 因此可將最小化檢驗數的值作為子問題的目標函數,若子問題的目標函數值小于零,則把所求得的方案轉化成列代入至RMP 模型中繼續求解,若子問題的目標函數值大于等于0,則證明MP 模型已經求得了最優.

為了表示MP 模型某一列的檢驗數,用βc表示約束(21)所對應的對偶變量,用αi表示約束(22)所對應的對偶變量. 則MP 模型某一列的檢驗數可以表示為

為構建SP 模型,重新定義模型(1)中的一些參數,V表示當前所選船舶的速度,Q表示當前所選船舶的容量,fij表示當前所選船舶在i-j段的運輸成本.

xij為0-1 決策變量,表示船舶是否行駛i-j段;yci的表示同模型(1);ti表示船舶到達港i的時間;si表示船舶在港i的作業時間;ui表示船舶港離開港口i時的載箱量;qi表示船舶需要在港口i裝載的集裝箱總量.

其中模型(25)的目標函數表示最小化檢驗數的值;式(38)描述了變量xij和變量yci的關系:若當前船舶路徑不經過喂給港i, 則當前方案下任一貨源點都不能分配至喂給港i; 式(26)～式(37)的表示可參考式(4)～式(15),此處不再贅述. 區別為SP 模型僅生成一條船舶路徑及該路徑下的集裝箱分配方案,且不用保證每個有運輸需求的喂給港都被訪問,也不用保證每個貨源點均被分配,只是求得一條能夠使得目標函數最小的可行路徑以及相應路徑下的集裝箱分配方案.求解SP 模型,得到變量xij和變量yci的值之后,通過轉換即可到一個可行方案r,及相應的hri,mrc和lr的值.

對于SP 模型,即使集裝箱被提前分配好了,該問題可看作是一個TSP 問題,用線性求解器求解中大型規模算例仍然較為困難,因此在本文的3.4 節中設計了啟發式規則對SP 模型進行求解.

3.4 ALNS 算法求解子問題

子問題是具有容量和時間窗約束的基本最短路徑問題的一個擴展, 可以定義在一個有向圖G=(P ∪C,E ∪E′)上. 頂點集合由集合P和集合C構成,其中P是港口集合(P=Ω ∪O ∪O′),C為貨源點集合;邊集合包括集合E和集合E′,其中E={(i,j)|i ?=j ∈P},E′={(c,i)|c ∈C,i ∈Ω}. 根據子問題的目標函數,屬于集合E的邊的費用和屬于集合E′的邊的費用分別為

在每次求解主問題得到新的對偶變量值之后都需要對邊的費用進行更新. 對邊的重新定價,可能會產生負的費用值.Feilet 等[20]運用動態規劃算法對含負費用邊的最短路徑問題進行求解.若使用動態規劃算法求解子問題,在拓展標簽的過程中,設某港口有10 個可選擇的貨源點,其所能形成的集合為210個,那么當前港口可以拓展的標簽數量最多可達210. 盡管有很多標簽在拓展的過程中由于不可行或是被另一個標簽統治而刪去,可拓展標簽的數量仍然十分多.經實驗驗證發現通過動態規劃算法求解子問題的效率很低.因此本文設計啟發式規則對子問題進行求解.

本文基于自適應大規模鄰域搜索算法(adaptive large neighborhood search,ALNS)設計求解子問題的啟發式規則,算法的具體描述如下:

1)初始解

定義N為港口數量,M為貨源點數量,一個初始解可以表示為O,1,2,N+1,N+2,6,N+3,O′,其中O和O′分別表示樞紐港和虛擬樞紐港,1～N的數字分別表示喂給港的編號,N+1～N+M的數字分別表示第1 個到第M個貨源點,即小于等于N的編號為喂給港;大于N的編號為貨源點.

因此如上初始解所表示的船舶路徑為O-1-2-6-O′,其中貨源點1 和貨源點2 被分配至喂給港2,貨源點3 被分配至喂給港6.

2)鄰域搜索動作

針對初始解的生成規則和問題的特性,設計了四種鄰域動作:(a)隨機插入—隨機選擇解的一個位置插入一個0～M+N之間的與原解不重復的數值.(b)最優插入—評估所有插入位置以及所有可插入的不重復的數值,選擇一個最好的插入位置和相應最好的插入數值對原解進行更新. (c)隨機移除—隨機選擇解的一個位置并移除該位置的數值.(d)最優移除—評估所有可以移除的位置,選擇一個最優的移除位置并移除該位置的數值.

在進行鄰域動作時需要遵循以下規則:插入的數值必須與原解中的所有數值不重復;插入或移除的位置不能是解的最左邊或者解的最右邊(保證船舶必須從樞紐港出發并最終返回樞紐港).

3)自適應鄰域搜索規則

在算法最開始隨機生成10 個初始可行解,在進行鄰域搜索時,隨機在10 個解中選擇一個解進入鄰域搜索操作.在進行鄰域搜索之前,首先根據4 種鄰域動作的權重值(算法初始時,四種鄰域動作的權重值相同,在迭代的過程中需要根據解的好壞進行更新),運用輪盤賭機制選擇一個鄰域動作,再對所選定的解進行該鄰域動作下的鄰域搜索.當每次通過鄰域搜索得到新解比當前解更優時,則用新解替代當前解;若新解比當前解差,則以一定的概率接受新解成為當前解. 設置能夠使子問題目標函數值為負的解的集合為S,若新解的目標函數值小于0,則將該解加入到集合S當中,并對該解進行記錄,禁止加入重復的解到集合S.

在選擇鄰域動作之前,還需要根據當前進行鄰域搜索的解的長度對四種鄰域動作當前的權重值進行臨時的設置.鄰域動作隨機插入和最優插入的權重值依據式(41)進行臨時設置;鄰域動作隨機移除和最優移除的權重值依據式(42)進行臨時設置,即

其中λ為0-1 之間的小數,M為貨源點的數量,N為港口的數量,L表示當前要進行鄰域搜索的解的長度.

根據式(41)和式(42)對鄰域動作的權重進行臨時的設置,可以使得在原有權重的基礎上,長度越長的解越可能進行移除操作,長度越短的解則越可能進行插入操作.在選擇完某一個鄰域動作后,還需要對四種鄰域動作臨時設置的權重值進行還原.

此外,在完成一次鄰域動作搜索后,需要依據所得新解的好壞,按照式(43)對當前所選鄰域動作的權重值進行更新,即

其中μ為0-1之間的小數,φ是當前進行的鄰域搜索所得結果的評估值,具體表示為

其中ω1＞ω2＞ω3＞ω4＞0

4)不同船型的處理方法

每次判斷生成的新解是否可行時,均按照最大船型的參數進行計算.但在得到一個可行解后,計算其成本以及SP 模型目標函數之前,需要判斷是否可以在保證解可行的形況下,更換更小的船型,若可以的話則按照當前可更換的最小船型計算相應參數的值.

5)算法停止規則

ALNS 算法迭代10 000 次停止.若集合S為非空,則將S中所有解轉化成列加入到RMP 模型中. 求解RMP 模型,得到新的對偶變量值后,再進行ALNS 算法;若S為空則可看作當前MP 模型中不存在檢驗數為負的列,可以判斷MP 模型已經求得了最優解(近優解).

ALNS 算法的步驟如下所示:

步驟1 隨機生成10 個初始可行解;

步驟2 設置初始迭代次數iter←0;

步驟3 為所有的鄰域動作設置相同的初始權重;

步驟4 在10 個解中隨機選中一個解s;

步驟5 按照解s的長度對四種鄰域動作的權重值進行臨時設置;

步驟6 采用輪盤賭機制選擇一個鄰域動作,對解s進行該鄰域動作下的鄰域搜索,生成一個新解s′,并對臨時設置的權重值進行還原. 若解s′優于解s,則用s′替換s,若解s′比解s差,則以一定概率接受s′;

步驟7 若解s′的目標函數值小于0,則將解s′加入至集合S中并對解s′進行記錄,防止其被重復加入集合S;

步驟8 按照當前所選擇的鄰域動作的搜索結果,對該鄰域動作的權重進行更新;

步驟9 iter←iter+1. 如果iter ≤10 000,則轉至步驟4,否則轉至步驟10;

步驟10 輸出集合S,算法終止.

4 實驗結果與分析

本文基于珠江三角洲地區,選取一個樞紐港、若干喂給港以及若干貨源點構成三級支線運輸網絡. 設計不同規模的算例,分別運用線性求解器Gurobi、兩階段求解算法、整合優化求解算法進行求解,以驗證模型的準確性、算法的求解效率以及本文的研究意義.實驗的計算機參數配置為Intel(R)Core(TM)I5-8265U,1.80 GHz,8 GB RAM.算法在Visual Studio 2017 C++中實現編碼,所使用的Gurobi 版本為8.1.0.

4.1 算例描述

1)設置包括樞紐港在內的港口數量|P| 為10,15,20,25,30;貨源點數量|C|為10 到80 不等. 對于不同的(|P|,|C|)組合,共計生成45 個算例.

2)選取三種類型的支線集裝箱船舶,分別為100 TEU,150 TEU,200 TEU.

3) 在距離樞紐港一定半徑范圍內隨機生成指定數量的貨源點, 各貨源點的集裝箱運輸需求在10 TEU～45 TEU 之間隨機生成.

4)各喂給港的卸箱量設置:0.2 的概率為0 TEU;0.8 的概率在15 TEU～55 TEU 之間隨機生成.

5)各港口的效率、時間窗限制以及各貨源點集裝箱最晚運至樞紐港的期限在一定范圍內隨機生成.

4.2 實驗結果與對比分析

為了更好的展示三級支線運輸網絡中,貨源點集裝箱分配對于支線船舶運輸路徑以及運輸成本的影響,分別使用兩階段求解算法和整合優化求解算法對10 個貨源點和10 個港口的算例進行求解,求解結果如表3 所示.

表3 兩階段求解算法vs.整合優化求解算法Table 3 Two-phase algorithm vs. integrated optimization algorithm

在兩階段算法的求解結果中,貨源點的集裝箱實現了最優分配,得到了最小的集裝箱分配成本1 050 元.在最優的集裝箱分配方案下,需要使用2 艘100 TEU 的集裝箱船舶和1 艘150 TEU 的集裝箱船舶實現最優的船舶調度,相應的支線船舶運輸成本為32 450 元,最終的總運輸成本為35 500 元;在整合優化求解的結果中,貨源點1 被分配至喂給港5,貨源點4 和貨源點6 被分配至喂給港9,均沒有進行最優的分配,集裝箱分配成本增加至1 080 元. 然而在該集裝箱分配方案下,僅需要3 艘100 TEU 的集裝箱船舶即可實現支線船舶的最優調度,船舶運輸成本大大降低. 整合優化算法求得的總運輸成本比兩階段求解算法求得的總運輸成本降低19.37%,初步驗證了構建三級支線運輸網絡以及進行整合優化的意義.

為了進一步驗證算法的有效性和本文的研究意義,分別運用3 種求解方法對45 個不同規模的算例進行求解,求解結果如表4 所示. “*”表示Gurobi 運行1 h 沒有得到最優解,相應數值為Gurobi 運行1 h 得到的滿意解;“—”表示Gurobi 運行1 h 沒有得到可行解;Gap1 為整合優化算法求解結果與Gurobi 計算結果的對比情況;Gap2 為整合優化算法求解結果與兩階段算法求解結果的對比情況.

表4 中結果顯示, 使用線性求解器Gurobi 求解模型(1)時, 只有算例1、算例2、算例3、算例10 和算例19 在1 h 內求得了最優解,其余算例均無法在1 h 內求得最優解或可行解.而對于所有的算例,整合優化求解算法均能在12 min 內求得最優解(近優解),平均求解時間為469.29 s.

此外,對Gurobi 和整合優化算法的求解結果進行對比分析可以發現,對于Gurobi 可以在1 h 內求得最優解的算例,整合優化算法的求解結果與Gurobi 的求解結果相差最多為1.78%,最少為0,平均相差0.81%;對于其他算例,整合優化算法所求的成本均小于Gurobi 求解1 h 所得到的成本.

圖4 為表4 中Gap1 值的柱狀圖,進一步展示了除了4 個算例之外,整合優化算法的求解結果均優于或等于Gurobi 的求解結果,成本最多可降低22.47%,平均降低7.44%. 因此,通過對比Gurobi 以及整合優化算法的求解結果,驗證了整合優化算法的求解效率.

圖4 Gap1 柱狀圖Fig.4 The bargraph of Gap1

表4 三種求解方法下不同規模算例的求解結果Table.4 Computational results of three types of methods for different size of instances

此外,對比觀察表4 中整合優化算法的求解結果與兩階段算法的求解結果可知,對于所有的算例,整合優化算法的求解結果均要優于兩階段算法的求解結果.在45 個算例中,既存在集裝箱分配發生變化后可以將大船換成小船使總成本降低的情況,也存在集裝箱分配發生變化后,集裝箱船舶的行駛路線發生改變而使總成本降低的情況.

圖5 為表4 中Gap2 值的柱狀圖,由圖5 可知,整合優化集裝箱分配與支線船舶調度最多可使成本降低40%以上,平均成本降低值為26.67%,充分驗證了整合優化求解的必要性以及本文的研究意義.

圖5 Gap2 柱狀圖Fig.5 The bargraph of Gap2

為證明使用多船型集裝箱船舶對于本文所研究問題的優勢,選取表4 中算例28～36 共9 個算例,運用整合優化求解算法,分別對多船型、僅100 TEU 船型、僅150 TEU 船型、僅200 TEU 船型4 種情況進行求解,求解結果如圖6 所示.

由圖6 可知,對于所有算例,使用多船型的調度方案均比單一船型要好,且差別較為明顯,因此驗證了使用多船型集裝箱船舶進行集裝箱分配與支線船舶調度聯合優化的必要性.

圖6 多船型調度與單一船型調度成本對比Fig.6 The difference between the cost for the scheduling of single-type containership and multi-type containership

5 結束語

為順應航運企業向供應鏈終端整合的發展趨勢,同時考慮到貨源點集裝箱分配方案對于支線集裝箱船舶調度成本的影響,本文將有集裝箱運輸需求的貨源點加入傳統的支線船舶運輸網絡進行研究,構建了三級支線運輸網絡. 以運輸總成本最小化為目標,建立了集裝箱分配與集裝箱船舶調度聯合優化模型,并分別采用兩階段求解算法以及基于列生成原理的整合優化算法對問題進行求解. 實驗結果表明,整合優化求解算法相對于線性求解器Gurobi 更具優勢,由此驗證了整合優化算法的有效性;對比兩階段算法與整合優化算法的求解結果,整合優化算法能夠得到更低的支線網絡運輸總成本,驗證了整合優化的重要性.

本研究可為集裝箱船舶運輸企業向供應鏈終端延伸服務的愿望和計劃提供建議,促使其與產生集裝箱運輸需求的客戶方進行合作,提前預知運輸需求,獲得能夠使支線運輸總成本最低的集裝箱分配計劃與船舶調度方案,從而進一步加強航運企業同內陸腹地的連接.將集裝箱運至樞紐港進行后續的干線運輸有明確的時間要求,因此本文的研究主要側重于三級支線網絡的集運過程.而對于網絡末端的配送問題,則具有更強的不確定性,需要考慮喂給港的堆場容量、外集卡的提箱時間、堆場的堆存成本等諸多因素.在未來的研究中,擬在此研究基礎上,對三級支線網絡疏運過程中的協同優化問題開展進一步討論.