考慮租箱返還限制的集裝箱船舶調度優化①

張天宇 楊 碩 鄭紅星

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

0 引言

隨著航運市場的競爭加劇,提高競爭力越來越引起航運企業的重視,而日常的船舶調度是提高該類企業競爭力的有效手段之一;就經營班輪航線的航運企業而言,考慮到期租箱返還的船舶調度優化,不僅可以降低企業運營成本,還可部分緩解企業輻射網絡中的缺箱和艙位過剩等問題,船舶調度已經引起了越來越多企業的重點關注。

針對船舶調度的相關問題,國內外學者進行了大量的研究,根據研究的側重點不同,可以分為考慮時間窗的船舶調度問題、空箱調運的船舶調度問題和租箱策略的船舶調度問題三方面。

在考慮時間窗的船舶調度方面,文獻[1]研究了時間窗、航速影響的船舶調度問題,建立了船舶成本、總服務成本最小和總利潤最大的多階段模型,并利用仿真進行求解。文獻[2]研究了受惡劣天氣影響的船舶調度問題,以總成本最小為目標函數建立模型,并設計了嵌入基因修復算子的改進遺傳算法進行求解。文獻[3]研究了基于船期表、航速及受泊時間窗的船舶調度問題,以總成本最小為目標函數建立非線性數學模型,并用嵌入基因修復的改進遺傳算法進行求解。

在空箱調運方面,文獻[4]研究了新的空箱調運策略,即不確定目的港策略,以總調運費最小為目標函數建立非線性規劃模型,并用Matlab 遺傳算法工具箱求解。文獻[5]研究了空箱調運路徑和空箱重派的聯合優化,以成本最低為目標函數構建網絡流模型并求解。文獻[6]研究了將空箱抽象成資源的空箱調運問題,以費用最低為目標函數構建混合整數模型,并用基于免疫的進化算法進行求解。文獻[7]研究了基于動態規劃的空箱分配問題,以兩港口兩航線調運系統建立動態隨機模型,并利用模擬仿真驗證其有效性。文獻[8]研究了結合庫存策略的空箱調運問題,以成本最低為目標,基于罰函數建立庫存模型,并用啟發式算法進行求解。

在租箱策略方面,文獻[9]研究了可折疊空箱的適用范圍的租箱問題,以成本流最小為目標函數建立網絡流模型,用網絡單純形法計算。文獻[10]研究了考慮棄貨成本及租箱成本的空箱調運問題,以運輸系統總收益最大為目標函數建立數學模型,并設計了遺傳算法與動態規劃的組合算法進行求解。文獻[11]研究了基于不同角度的租箱策略問題,建立數學優化模型,并運用數字仿真技術揭示策略運用中的潛在規律。文獻[12]研究了新港口的租箱空箱分配問題,以總成本最低為目標函數建立數學模型,并利用Matlab 結合模型特點進行求解。

綜上所述,針對考慮時間窗的船舶調度問題的研究,大多以總成本最低為目標,罕有考慮利用船舶調度提高收益而覆蓋新增成本的問題;在空箱調運問題的研究中,大多文獻以收益最高為目標進行空重艙位分配,但無法在短周期之內改善航運企業空箱分布不均勻的狀況;在租箱策略方面,上述文獻以租箱成本最低為目標,進行租箱策略選擇,但鮮有考慮租箱返還問題的文獻。租箱返還問題涉及到時間窗、租箱策略、空箱調運等問題。因此,本文重點考慮租箱的還箱成本控制問題,兼顧空箱調運過程中的船舶調度問題及待還租箱所搭載的船舶方案設計。本文與已有文獻不同之處主要有以下兩點。

(1)考慮了待還租箱放棄直接歸還,選擇再次被利用,利用與否取決于收益與所產生的超期費之差。

(2)設計了考慮待還租箱再次被利用的船舶實際航行線路的船舶調度方案。

1 問題描述

隨著航運企業的快速發展,租箱策略愈發被廣泛應用。在所租空箱的還箱過程中,會造成艙位資源和高利潤航線資源的浪費,因此宏觀調度各集裝箱船舶以及各個待還租箱的運輸方案可成為減少此類成本的重要手段,即再次利用待還租箱資源,將空轉重,創造更多利潤以減少還箱成本。

本文中,班輪公司的輻射點已知,租箱公司所要求的還箱點固定。首先,班輪公司可根據船舶艙位數量及各港口需要運輸的集裝箱數量自由選擇航線;其次,依據待還租箱的還箱路徑及到期時間判斷租箱是否可以再次被利用;最后,待還租箱可視不同港口的缺箱情況搭載不同的船舶到達缺箱點,由空轉重或者由重轉空。

本文的問題可描述為:針對某個航運企業的航線輻射網絡,在一個運營周期內(從第一條船舶出發時刻開始計時,截止到整個航線網絡中最后一條船舶達到目的港的時刻為一個運營周期),已知各船舶進出港時間、港口之間距離、重箱運輸量及運費、空箱運輸量及運費、待還租箱還箱期限、超期費收費標準、還箱點等相關信息后,以單個周期所有船舶的運輸成本最小為目標,建立協同優化模型,研究考慮待還租箱再次被利用的條件下的租箱返還問題,最終給出各條船舶所選航線以及各個待還租箱所搭載的船舶計劃方案。航線網絡圖如圖1 所示。

圖1 航線網絡圖

2 數學模型

2.1 基本假設

為切合航運企業運營的實際情況,本文做出如下假設。

(1)所有船舶均可航行于航運企業輻射的各類航線;在航運企業的實際運營過程中,為應對實際的需求變動或各種突發狀況一般僅定線不定船,航運企業實際營運的船舶需在該公司輻射的各類航線間跨航線調度。

(2)假設船舶到港等待時間和船舶裝卸作業時間已知;在船舶抵港之前,大多數會將該船的預計抵達時間段并連同實際配載信息發送給港口,且港口一般都已提前制定了船舶排隊規則和泊位作業計劃。

(3)假設待還租箱超期返還只會產生超期費,無其他費用;在待還租箱返還過程中,可能還會產生折舊、清洗等費用,但相對超期費來說,這些費用較低,可忽略。

(4)假設在一個航運周期運營過程中,不考慮再次租賃集裝箱;一般來說,航運企業的租箱計劃和還箱計劃分開,租箱業務屬于箱管部門,還箱業務屬于航線部分。

2.2 符號說明

(1)集合

N:船舶集合,n=(1,2,…,N)∈N;M:集裝箱集合,m=(1,2,…,M)∈M;P:掛靠港集合,i,j=(1,2,…,I,J)∈P;T:目的港集合,k=(1,2,…,K)∈T。

(2)參數

Ri:i港所需歸還的集裝箱箱量,Ri＞0;Li:i港的缺箱量,Li＞0;Cij:表示從i港到j港的貨運量,Cij＞0;Sn:船舶n的容量,Sn＞0;tij:從i港到j港的航行時間,tij＞0;Di:i港的待還租箱的還箱期限,Di為整數;hin:第n條船到i港的載貨量(包含空箱),hin＞0;ri:i港的重箱量,Ri:i港的還箱數量,Ri＞0;tin:第n條船航行至i港的時間,tin＞0;din:第n條船所裝i港的租箱的超期天數,din＞0;tin:第n條船航行至i港的時間,tin＞0;Cm:第m個箱子的運輸成本,Cm＞0;RDm:第m個箱子的產生的超期費,RDm≥0;CRm:第m個重箱產生的收益,CRm＞0;CLi:船舶在i港的裝卸成本,CLi＞0;CSm:第m個箱子在停泊時產生的平均成本,CSm＞0;CSijn:第n條船從i港到j港的運輸成本,CSijn＞0。

(3)決策變量

xijn:表示第n條船從i港到j港的載貨量;fijn:表示第n條船在i港裝上來自j港的集裝箱箱量,i可以等于j;sijn:表示第n條船在i港卸下來自j港的集裝箱箱量;yijn:為0 -1 變量,表示船舶的航行路線信息,若第n條船從i港駛向j港,yijn=1,否則yijn=0。

2.3 模型構建

集裝箱調運過程中,為使成本最低,基于整體航線網絡,各集裝箱船舶根據船舶特點選擇不同航線、不同掛靠港口,因而會產生互不相同的各項成本,其中ΣmΣnΣijCm +ΣmΣijRDm -ΣmΣijCRm表示因待還租箱的由空轉重或者由重轉空所產生的超期費與新增利潤之差;ΣmΣnΣijCm × fijn表示集裝箱運輸成本;ΣnΣijCSijn × yijn表 示 集裝箱船舶 的 航行成 本;ΣmΣnΣijCSm × yijn表示船舶停泊所產生的成本;ΣmΣnΣijCLi ×(fijn+sijn) 表示船舶在港的裝卸成本。

本文以整體航線網絡中所有集裝箱船舶運輸過程中還箱成本最小為目標,因航線需重新整合,故集裝箱船舶運輸及作業所產生的成本計入目標函數中,從第一條船舶在始發港作業開始計費,至最后一條船舶在目的港停止作業為止。式(2)表示集裝箱船舶所裝卸的集裝箱數量不得多于個港口的集裝箱總數,即維護集裝箱船舶的裝卸平衡;式(3)表示在各個港口中,待還租箱的總數保持平衡;式(4)表示在一次運輸周期內,滿足所有待運輸的重箱及空箱的總量均可在本次運輸活動中全部運輸;式(5)表示所有集裝箱船舶的艙位數量應容納待運輸集裝箱的總數;式(6)表示各港口的缺貨情況應保證集裝箱船舶駛來或駛去的必要性;式(7)表示待還租箱是否有必要承擔超期費而選擇再次利用的約束;式(8)表示超期費的計費規則;式(9)～式(10)表示整個活動過程運行的邏輯約束;式(11)～式(12)表示船舶路徑選擇約束,若xijn＞0 說明船舶n從i港到過j港;式(13)表示待還租箱的路徑選擇約束,若fipn＞0 說明船舶n從i港裝過來自p港的集裝箱;若sipn＞0 說明船舶n從i港卸下來自p港的集裝箱;式(14)～式(15)表示待還租箱在各個港口裝卸數量限制的約束,即m船在i港裝的p港集裝箱數量要小于其他船舶在i港卸下的p港的集裝箱數量,m船在i港裝的j港集裝箱數量要小于其他船舶在i港卸下的j港的集裝箱數量與還箱量的和。

3 算法設計

由于本文重點考慮了待還租箱再次利用的影響因素,因此,目標函數中新增了利潤與超期費之差的多項式,并且新增多個約束條件,故本文模型更加復雜化。考慮到本文計算量較大,依據模型的特點,設計了改進遺傳算法,建立了虛擬港口,即若待還租箱在某一港口被再次利用,則經過這一虛擬港口,再多次進行交叉變異,得到精確解。這一過程的具體執行流程圖如圖2 所示,設計了基于混合整數規劃的啟發式算法(MATHEURISTIC),即將啟發式算法與混合整數規劃方法(mixed-integer programming,MIP)集成進行模型求解。

圖2 算法流程圖

3.1 解的表示

依據船舶的裝卸貨物量對船舶進行編號,如表1,染色體表示船舶編號。

表1 染色體編碼示例

3.2 初始解的生成

基于模型中的約束,設計了如下的初始解生成策略。

初始化參數,生成染色體第一行。具體步驟如下。

步驟1計算染色體中包含優先船舶的各艘船舶的進港時間、重箱運輸成本、空箱運輸成本及航行時間。

步驟2對于每條航線,若優先船舶的航行時間小于備選船舶的航行時間并進港時間優先,且成本小于緊前船舶,轉到步驟5;若優先船舶航行時間大于備選船舶的航行時間,或成本大于備選船舶,轉到步驟3;若優先船舶進港時間晚于備選船舶進港時間,且成本小于備選船舶,轉到步驟4。

步驟3將優先船舶與緊前船舶的位置互換,轉到步驟2。

步驟4重新隨機生成染色體并轉到步驟1。

步驟5保留此層染色體。

3.3 適應度函數的確定

本文模型的目標函數為運輸整體成本最小。目標函數越小,解就越優良,因此,本文的適應度函數為:f(x)=Cmax-r(x),r(x) ＜Cmax,if:f(x)=0,r(x) ＞Cmax,其中r(x)為目標函數,Cmax為本代個體解得目標函數的最大值。

3.4 選擇過程

選擇是為了選出優秀的個體組成一個新的群體,本文采用輪盤賭選擇優秀個體,每個個體i被選中的概率為,具體的選擇過程如下。

步驟1計算個體的選擇概率,將其進行從小到大的排列。

步驟2按照數組的排列順序將其累加,第n個數變成前n項之和。

步驟3生成一個0～1 之間的隨機數,計算其落到的區間。找到這個區間對應的個體,重復多次,直到產生了一個數量相同的種群。

步驟4按照交叉概率對新種群進行交叉操作,每一個個體與下一個個體概率交叉,直至所有個體遍歷完畢。

3.5 實數交叉與變異過程

本文設計了實數交叉算子,即將種群中的第1個染色體m1和第a個染色體ma在j位進行交叉,從而生成新個體,即,其中n為[0,1]區間的隨機數,具體交叉變異過程如下。

步驟1生成一個0～1 的隨機數,檢測該數是否小于交叉概率,若是轉到步驟2,否則轉到步驟3。

步驟2若該數小于變異概率,則轉到步驟5,否則轉到步驟4。

步驟3保持這條染色體不變,保留到下一代。

步驟4對此條染色體與相鄰的下一條染色體進行實數交叉,將新生成的染色體保存至下一代。

步驟5對此條染色體進行變異操作,具體操作步驟為:任選一條裝有待還租箱的船舶,將其隨機分配到其他符合船舶容量的運輸航線上。

3.7 基因修復算子

在交叉變異生成新個體時,會出現某個場區的待裝載集裝箱的數量大于船舶容量的情況,采取以下步驟修復。

步驟1依次檢查個體,如果某個場區的待裝載集裝箱的數量大于船舶容量轉到步驟2,否則轉到步驟3。

步驟2在更多艙位的船舶中隨機選取一個基因與之交換位置。轉到步驟1。

步驟3輸出新個體,經過基因修復的個體,要符合本算法的生成策略,對新個體依照3.1 節的方法來調整。

3.8 算法終止條件

終止條件為計算到預設的最大進化迭代次數時停止,然后輸出各代種群中最優的染色體,評價每個染色體的最終得分值,得出最大利潤。

4 算例實驗

4.1 算例描述

以某內貿航運公司為例,該公司經營的北-南航線的始發港為營口港,依據合同規定,該公司租借的集裝箱遵循何地借、何地還的規則。已知始發港為營口港,還箱點所在港口為廣州新港,航線示意圖如圖3 所示。

圖3 航線運營網絡圖

假設各港口裝卸效率統一,為150 TEU/h,以及各港口待裝貨物全部上船,根據模型中船舶的約束,對船舶航線選擇進行了計算。在保證貨物全部裝走的情況下,可優化其船舶調度情況如表2～表10 所示。

表2 船舶編號與實際航線

表3 某內貿船公司船期表

表3 續

表4 船舶容量與適用航速

表5 運價表

表6 港口間距離

表7 各港口待運貨物可裝箱量

表8 各港口待還租箱數量及還箱截止期限

表9 船舶調度情況

表10 航運企業實際船舶調度成本

因各個港口空箱需求量不同,故本文著重考慮待還租箱再次利用,以減少還箱成本。因此,假設待還租箱運到用箱港口之后,需等下一個周期的船裝走,所以超期天數應以租箱第一次上船開始計時,截止到租箱到達還箱點的時間與待還租箱返還期限之差。假設每個集裝箱運輸成本為60 元/d,各港口停泊及裝卸單位成本統一。采用啟發式算法與MIP方法集成進行模型求解。各港口待還租箱路徑如表11所示,最優方案收斂圖如圖4。

表11 考慮各港口待還租箱所乘船舶調度成本

圖4 最優方案收斂圖

4.2 方案有效性驗證

在船舶實際運營的過程中,采用待還租箱再次利用的措施,本周期航線網的運營成本為7 542 460.5 元。通過比較表10 和表11,可看出成本可降低19%,雖待還租箱再次利用會產生額外成本,但所增加的利潤可完全覆蓋并超出額外成本。另一方面,從長期運營的角度看,待還租箱的再次利用,可在一個或幾個周期內減少租箱次數,可有效降低租箱成本,從而驗證了本文方案的有效性。

4.3 算法科學性驗證

(1)算法有效性

現將本文數學模型用CPLEX 軟件求解,因本文數學模型均是線性,故可直接求解。CPLEX 運行時間上限設置為4 h,再與MATHEURISITIC 計算結果進行比較,各組對比結果見表12。

從表12 可以看出,單獨利用CPLEX 求解時,用時較長,在求解大規模數據時,短時間內無解。而采用啟發式算法與CPLEX 相結合進行求解,不單利用了改進遺傳算法計算速度較快的優點,而且也利用了CPLEX 精確求解的優點,得到的最優解的所有偏差值都控制在5%以內。綜上,本文采用的算法可有效地在短時間內解決問題。

表12 算例比較結果

(2)算法優越性

為驗證算法的優越性,本文同時針對此問題,分別用量子差分進化算法(quantum differential evolution,QDE)[13-14]、蟻群算法(ant colony optimization,ACO)、元遺傳算法(meta-heuristic algorithm,MHA)[15]進行求解并與本文算法進行比較。QDE參數設定最大迭代次數500,種群規模為200,收縮因子為0.8,量子交叉為0.2;ACO 參數設定最大迭代次數500,種群規模為200;MHA 參數設定最大迭代次數為500,種群規模為200。算法比較結果如表13所示。

其中表13 中QTIC、ATIC、MTIC 分別表示MATHEURISIT 與QDE、ACO、MHA 求解本文問題時所得目標函數值之差占目標函數值的比例,表14 中QTIC、ATIC、MTIC分別表示MATHEURISIT 與QDE、ACO、MHA 求解本文問題時CPU 耗時之差占MATHEURISIT 求解時CPU 耗時的比例。經比較可知,蟻群算法(ACO)和元遺傳算法(MHA)計算時間短,但目標函數值相差較大;量子差分進化算法(QDE)計算時間及結果與MATHEURISIT 相近,但速度慢,且結果有偏差,因此,本文算法存在優越性。

表13 改進遺傳算法和其他算法目標函數值比較

表14 改進遺傳算法和其他算法CPU 耗時比較

4.4 靈敏度分析

待還租箱的數量波動會影響船舶航線的規劃,從而進一步影響成本。從表15 中可以看出,待還租箱數量上的波動對成本的影響中,前者較后者的成本增加趨勢顯著。在待還租箱逐漸增加的狀態下,選擇待還租箱再次被利用,可有效縮小成本。

表15 待還租箱數量變化靈敏度分析

因集裝箱超期費是探究租箱是否可以再次利用的關鍵成本因素,而待還租箱利用率是探究待還集裝箱是否可以再次利用的關鍵利潤因素,為了進一步探究待還租箱在返還過程中再次被利用的可行性,本文針對以上兩個變量進行了敏感性分析,結果如圖5 所示。

圖5 還箱成本波動圖

通過對比以上兩組數據可以看出,超期費率的變化對成本的波動情況影響較小,而待還租箱再次利用所創造的收益隨著利用率的增加變化趨勢明顯。故可在本文的約束條件下,選擇待還租箱再次被利用,盡管會產生更多的超期費,但利用此類箱所產生的利潤可將其完全覆蓋,并縮小其余成本,這也驗證了本文研究的有效性。

5 結論

本文以內貿定期航線的航運企業為研究對象,研究在航運企業的實際運營中,租箱返還影響的船舶調度問題。以運輸成本最小為研究目標,著重考慮待還租箱的資源利用、船舶航線選擇問題,最終給出了各集裝箱船舶運輸的最優路徑以及待還租箱的最優搭載船舶方案,減少了船舶運輸成本,表明通過船舶航線的整合以及待還租箱的合理利用可有效降低租箱次數及還箱成本。

結合問題特點,構建混合整數模型,并設計了改進遺傳算法與CPLEX 集成進行求解。為類似問題的解決提供了思路。

通過敏感性分析發現,待還租箱數量的波動對船舶運營成本的影響較大,但經過本文優化后的運輸方案,可適當降低成本。再次利用率的變動對還箱成本有顯著影響,但超期費率的變動影響不大,因此,將待還租箱由空轉重或者由重轉空所產生的利潤與需支付的超期費之差會越來越大,這既可有效減輕直接還箱帶來的成本負擔,也可減少租箱次數。本研究為航運企業的實際調度決策起輔助支持作用,對于企業的集裝箱管理有很強的借鑒意義。