支線航運(yùn)網(wǎng)絡(luò)下集裝箱分配與船舶調(diào)度聯(lián)合優(yōu)化

孔靈睿, 計(jì)明軍, 孫以寧, 關(guān)云瀟, 郭興海

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院,遼寧大連 116026)

1 引 言

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

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

圖1 二級支線運(yùn)輸網(wǎng)絡(luò)Fig.1 The two-level feeder transportation network

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

圖2 三級支線運(yùn)輸網(wǎng)絡(luò)Fig.2 The three-level feeder transportation network

不同于傳統(tǒng)的支線運(yùn)輸網(wǎng)絡(luò),三級支線運(yùn)輸網(wǎng)絡(luò)不僅需要對支線集裝箱船舶調(diào)度方案進(jìn)行決策,還需同時考慮各貨源點(diǎn)的集裝箱到喂給港的分配方案.即貨源點(diǎn)的集裝箱并非提前分配至相應(yīng)的喂給港,而是同支線集裝箱船舶調(diào)度計(jì)劃進(jìn)行聯(lián)合優(yōu)化. 若一個貨源點(diǎn)的集裝箱通過不同的喂給港進(jìn)行運(yùn)輸,最優(yōu)的支線船舶調(diào)度方案可能會發(fā)生很大的變化,最小的運(yùn)輸成本也將隨之改變.通過構(gòu)建三級支線網(wǎng)絡(luò)并對其進(jìn)行聯(lián)合優(yōu)化研究,能夠?yàn)楹竭\(yùn)企業(yè)向供應(yīng)鏈終端整合提供思路,同時可以降低整體支線網(wǎng)絡(luò)的總運(yùn)輸成本.

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

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

基于上述考慮,本文將貨源點(diǎn)加入至傳統(tǒng)的支線運(yùn)輸網(wǎng)絡(luò)中,將傳統(tǒng)的二級支線運(yùn)輸網(wǎng)絡(luò)拓展成三級支線運(yùn)輸網(wǎng)絡(luò). 針對支線集裝箱船舶運(yùn)輸?shù)奶攸c(diǎn),考慮船舶容量、喂給港時間窗以及樞紐港運(yùn)輸班期等現(xiàn)實(shí)因素,分析貨源點(diǎn)集裝箱在喂給港的分配與支線船舶調(diào)度計(jì)劃之間的內(nèi)在聯(lián)系,對集裝箱分配方案以及支線集裝箱船舶調(diào)度計(jì)劃進(jìn)行聯(lián)合優(yōu)化,以期能夠降低整個三級支線運(yùn)輸網(wǎng)絡(luò)的總成本,為航運(yùn)企業(yè)的升級轉(zhuǎn)型提供有益借鑒.

2 問題描述與數(shù)學(xué)模型

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

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

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

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

2.1 模型假設(shè)

基于支線集裝箱船舶運(yùn)輸?shù)奶攸c(diǎn),提出如下假設(shè):

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

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

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

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

5)在調(diào)度的過程中需要保證每一個貨源點(diǎn)的運(yùn)輸需求都被滿足.

2.2 模型構(gòu)建

為了構(gòu)建數(shù)學(xué)模型,定義如表1 所示的參數(shù)和變量.

表1 參數(shù)與變量說明Table 1 Description of parameters and variables

基于表1 中的參數(shù)以及變量定義,集裝箱分配與多船型支線集裝箱船舶調(diào)度聯(lián)合優(yōu)化模型為

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

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

2.3 兩階段求解模型與算法

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

步驟1 集裝箱分配

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

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

該模型可直接使用線性求解器進(jìn)行求解.

步驟2 支線集裝箱船舶調(diào)度

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

3 基于列生成的整合優(yōu)化求解算法

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

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

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

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

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

在求得MP 模型的最優(yōu)解后,將0-1 整數(shù)變量約束加入至當(dāng)前的RMP 模型即可求得集分割模型的整數(shù)解. 本文所設(shè)計(jì)基于列生成的整合優(yōu)化求解算法的具體步驟總結(jié)如下:

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

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

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

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

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

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

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

3.2 集分割模型

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

表2 參數(shù)與變量說明Table 2 Description of parameters and variables

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

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

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

3.3 子問題模型

根據(jù)單純型法的原理,把檢驗(yàn)數(shù)小于0 的列代入至RMP 模型中迭代,能夠優(yōu)化當(dāng)前最優(yōu)解. 因此可將最小化檢驗(yàn)數(shù)的值作為子問題的目標(biāo)函數(shù),若子問題的目標(biāo)函數(shù)值小于零,則把所求得的方案轉(zhuǎn)化成列代入至RMP 模型中繼續(xù)求解,若子問題的目標(biāo)函數(shù)值大于等于0,則證明MP 模型已經(jīng)求得了最優(yōu).

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

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

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

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

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

3.4 ALNS 算法求解子問題

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

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

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

1)初始解

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

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

2)鄰域搜索動作

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

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

3)自適應(yīng)鄰域搜索規(guī)則

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

在選擇鄰域動作之前,還需要根據(jù)當(dāng)前進(jìn)行鄰域搜索的解的長度對四種鄰域動作當(dāng)前的權(quán)重值進(jìn)行臨時的設(shè)置.鄰域動作隨機(jī)插入和最優(yōu)插入的權(quán)重值依據(jù)式(41)進(jìn)行臨時設(shè)置;鄰域動作隨機(jī)移除和最優(yōu)移除的權(quán)重值依據(jù)式(42)進(jìn)行臨時設(shè)置,即

其中λ為0-1 之間的小數(shù),M為貨源點(diǎn)的數(shù)量,N為港口的數(shù)量,L表示當(dāng)前要進(jìn)行鄰域搜索的解的長度.

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

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

其中μ為0-1之間的小數(shù),φ是當(dāng)前進(jìn)行的鄰域搜索所得結(jié)果的評估值,具體表示為

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

4)不同船型的處理方法

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

5)算法停止規(guī)則

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

ALNS 算法的步驟如下所示:

步驟1 隨機(jī)生成10 個初始可行解;

步驟2 設(shè)置初始迭代次數(shù)iter←0;

步驟3 為所有的鄰域動作設(shè)置相同的初始權(quán)重;

步驟4 在10 個解中隨機(jī)選中一個解s;

步驟5 按照解s的長度對四種鄰域動作的權(quán)重值進(jìn)行臨時設(shè)置;

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

步驟7 若解s′的目標(biāo)函數(shù)值小于0,則將解s′加入至集合S中并對解s′進(jìn)行記錄,防止其被重復(fù)加入集合S;

步驟8 按照當(dāng)前所選擇的鄰域動作的搜索結(jié)果,對該鄰域動作的權(quán)重進(jìn)行更新;

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 算例描述

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

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

3) 在距離樞紐港一定半徑范圍內(nèi)隨機(jī)生成指定數(shù)量的貨源點(diǎn), 各貨源點(diǎn)的集裝箱運(yùn)輸需求在10 TEU～45 TEU 之間隨機(jī)生成.

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

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

4.2 實(shí)驗(yàn)結(jié)果與對比分析

為了更好的展示三級支線運(yùn)輸網(wǎng)絡(luò)中,貨源點(diǎn)集裝箱分配對于支線船舶運(yùn)輸路徑以及運(yùn)輸成本的影響,分別使用兩階段求解算法和整合優(yōu)化求解算法對10 個貨源點(diǎn)和10 個港口的算例進(jìn)行求解,求解結(jié)果如表3 所示.

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

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

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

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

此外,對Gurobi 和整合優(yōu)化算法的求解結(jié)果進(jìn)行對比分析可以發(fā)現(xiàn),對于Gurobi 可以在1 h 內(nèi)求得最優(yōu)解的算例,整合優(yōu)化算法的求解結(jié)果與Gurobi 的求解結(jié)果相差最多為1.78%,最少為0,平均相差0.81%;對于其他算例,整合優(yōu)化算法所求的成本均小于Gurobi 求解1 h 所得到的成本.

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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