考慮租箱返還限制的集裝箱船舶調(diào)度優(yōu)化①

張?zhí)煊?楊 碩 鄭紅星

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

0 引言

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

針對(duì)船舶調(diào)度的相關(guān)問題,國內(nèi)外學(xué)者進(jìn)行了大量的研究,根據(jù)研究的側(cè)重點(diǎn)不同,可以分為考慮時(shí)間窗的船舶調(diào)度問題、空箱調(diào)運(yùn)的船舶調(diào)度問題和租箱策略的船舶調(diào)度問題三方面。

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

在空箱調(diào)運(yùn)方面,文獻(xiàn)[4]研究了新的空箱調(diào)運(yùn)策略,即不確定目的港策略,以總調(diào)運(yùn)費(fèi)最小為目標(biāo)函數(shù)建立非線性規(guī)劃模型,并用Matlab 遺傳算法工具箱求解。文獻(xiàn)[5]研究了空箱調(diào)運(yùn)路徑和空箱重派的聯(lián)合優(yōu)化,以成本最低為目標(biāo)函數(shù)構(gòu)建網(wǎng)絡(luò)流模型并求解。文獻(xiàn)[6]研究了將空箱抽象成資源的空箱調(diào)運(yùn)問題,以費(fèi)用最低為目標(biāo)函數(shù)構(gòu)建混合整數(shù)模型,并用基于免疫的進(jìn)化算法進(jìn)行求解。文獻(xiàn)[7]研究了基于動(dòng)態(tài)規(guī)劃的空箱分配問題,以兩港口兩航線調(diào)運(yùn)系統(tǒng)建立動(dòng)態(tài)隨機(jī)模型,并利用模擬仿真驗(yàn)證其有效性。文獻(xiàn)[8]研究了結(jié)合庫存策略的空箱調(diào)運(yùn)問題,以成本最低為目標(biāo),基于罰函數(shù)建立庫存模型,并用啟發(fā)式算法進(jìn)行求解。

在租箱策略方面,文獻(xiàn)[9]研究了可折疊空箱的適用范圍的租箱問題,以成本流最小為目標(biāo)函數(shù)建立網(wǎng)絡(luò)流模型,用網(wǎng)絡(luò)單純形法計(jì)算。文獻(xiàn)[10]研究了考慮棄貨成本及租箱成本的空箱調(diào)運(yùn)問題,以運(yùn)輸系統(tǒng)總收益最大為目標(biāo)函數(shù)建立數(shù)學(xué)模型,并設(shè)計(jì)了遺傳算法與動(dòng)態(tài)規(guī)劃的組合算法進(jìn)行求解。文獻(xiàn)[11]研究了基于不同角度的租箱策略問題,建立數(shù)學(xué)優(yōu)化模型,并運(yùn)用數(shù)字仿真技術(shù)揭示策略運(yùn)用中的潛在規(guī)律。文獻(xiàn)[12]研究了新港口的租箱空箱分配問題,以總成本最低為目標(biāo)函數(shù)建立數(shù)學(xué)模型,并利用Matlab 結(jié)合模型特點(diǎn)進(jìn)行求解。

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

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

(2)設(shè)計(jì)了考慮待還租箱再次被利用的船舶實(shí)際航行線路的船舶調(diào)度方案。

1 問題描述

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

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

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

圖1 航線網(wǎng)絡(luò)圖

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

2.1 基本假設(shè)

為切合航運(yùn)企業(yè)運(yùn)營的實(shí)際情況,本文做出如下假設(shè)。

(1)所有船舶均可航行于航運(yùn)企業(yè)輻射的各類航線;在航運(yùn)企業(yè)的實(shí)際運(yùn)營過程中,為應(yīng)對(duì)實(shí)際的需求變動(dòng)或各種突發(fā)狀況一般僅定線不定船,航運(yùn)企業(yè)實(shí)際營運(yùn)的船舶需在該公司輻射的各類航線間跨航線調(diào)度。

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

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

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

2.2 符號(hào)說明

(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)參數(shù)

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

(3)決策變量

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

2.3 模型構(gòu)建

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

本文以整體航線網(wǎng)絡(luò)中所有集裝箱船舶運(yùn)輸過程中還箱成本最小為目標(biāo),因航線需重新整合,故集裝箱船舶運(yùn)輸及作業(yè)所產(chǎn)生的成本計(jì)入目標(biāo)函數(shù)中,從第一條船舶在始發(fā)港作業(yè)開始計(jì)費(fèi),至最后一條船舶在目的港停止作業(yè)為止。式(2)表示集裝箱船舶所裝卸的集裝箱數(shù)量不得多于個(gè)港口的集裝箱總數(shù),即維護(hù)集裝箱船舶的裝卸平衡;式(3)表示在各個(gè)港口中,待還租箱的總數(shù)保持平衡;式(4)表示在一次運(yùn)輸周期內(nèi),滿足所有待運(yùn)輸?shù)闹叵浼翱障涞目偭烤稍诒敬芜\(yùn)輸活動(dòng)中全部運(yùn)輸;式(5)表示所有集裝箱船舶的艙位數(shù)量應(yīng)容納待運(yùn)輸集裝箱的總數(shù);式(6)表示各港口的缺貨情況應(yīng)保證集裝箱船舶駛來或駛?cè)サ谋匾?式(7)表示待還租箱是否有必要承擔(dān)超期費(fèi)而選擇再次利用的約束;式(8)表示超期費(fèi)的計(jì)費(fèi)規(guī)則;式(9)～式(10)表示整個(gè)活動(dòng)過程運(yùn)行的邏輯約束;式(11)～式(12)表示船舶路徑選擇約束,若xijn＞0 說明船舶n從i港到過j港;式(13)表示待還租箱的路徑選擇約束,若fipn＞0 說明船舶n從i港裝過來自p港的集裝箱;若sipn＞0 說明船舶n從i港卸下來自p港的集裝箱;式(14)～式(15)表示待還租箱在各個(gè)港口裝卸數(shù)量限制的約束,即m船在i港裝的p港集裝箱數(shù)量要小于其他船舶在i港卸下的p港的集裝箱數(shù)量,m船在i港裝的j港集裝箱數(shù)量要小于其他船舶在i港卸下的j港的集裝箱數(shù)量與還箱量的和。

3 算法設(shè)計(jì)

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

圖2 算法流程圖

3.1 解的表示

依據(jù)船舶的裝卸貨物量對(duì)船舶進(jìn)行編號(hào),如表1,染色體表示船舶編號(hào)。

表1 染色體編碼示例

3.2 初始解的生成

基于模型中的約束,設(shè)計(jì)了如下的初始解生成策略。

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

步驟1計(jì)算染色體中包含優(yōu)先船舶的各艘船舶的進(jìn)港時(shí)間、重箱運(yùn)輸成本、空箱運(yùn)輸成本及航行時(shí)間。

步驟2對(duì)于每條航線,若優(yōu)先船舶的航行時(shí)間小于備選船舶的航行時(shí)間并進(jìn)港時(shí)間優(yōu)先,且成本小于緊前船舶,轉(zhuǎn)到步驟5;若優(yōu)先船舶航行時(shí)間大于備選船舶的航行時(shí)間,或成本大于備選船舶,轉(zhuǎn)到步驟3;若優(yōu)先船舶進(jìn)港時(shí)間晚于備選船舶進(jìn)港時(shí)間,且成本小于備選船舶,轉(zhuǎn)到步驟4。

步驟3將優(yōu)先船舶與緊前船舶的位置互換,轉(zhuǎn)到步驟2。

步驟4重新隨機(jī)生成染色體并轉(zhuǎn)到步驟1。

步驟5保留此層染色體。

3.3 適應(yīng)度函數(shù)的確定

本文模型的目標(biāo)函數(shù)為運(yùn)輸整體成本最小。目標(biāo)函數(shù)越小,解就越優(yōu)良,因此,本文的適應(yīng)度函數(shù)為:f(x)=Cmax-r(x),r(x) ＜Cmax,if:f(x)=0,r(x) ＞Cmax,其中r(x)為目標(biāo)函數(shù),Cmax為本代個(gè)體解得目標(biāo)函數(shù)的最大值。

3.4 選擇過程

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

步驟1計(jì)算個(gè)體的選擇概率,將其進(jìn)行從小到大的排列。

步驟2按照數(shù)組的排列順序?qū)⑵淅奂?第n個(gè)數(shù)變成前n項(xiàng)之和。

步驟3生成一個(gè)0～1 之間的隨機(jī)數(shù),計(jì)算其落到的區(qū)間。找到這個(gè)區(qū)間對(duì)應(yīng)的個(gè)體,重復(fù)多次,直到產(chǎn)生了一個(gè)數(shù)量相同的種群。

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

3.5 實(shí)數(shù)交叉與變異過程

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

步驟1生成一個(gè)0～1 的隨機(jī)數(shù),檢測該數(shù)是否小于交叉概率,若是轉(zhuǎn)到步驟2,否則轉(zhuǎn)到步驟3。

步驟2若該數(shù)小于變異概率,則轉(zhuǎn)到步驟5,否則轉(zhuǎn)到步驟4。

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

步驟4對(duì)此條染色體與相鄰的下一條染色體進(jìn)行實(shí)數(shù)交叉,將新生成的染色體保存至下一代。

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

3.7 基因修復(fù)算子

在交叉變異生成新個(gè)體時(shí),會(huì)出現(xiàn)某個(gè)場區(qū)的待裝載集裝箱的數(shù)量大于船舶容量的情況,采取以下步驟修復(fù)。

步驟1依次檢查個(gè)體,如果某個(gè)場區(qū)的待裝載集裝箱的數(shù)量大于船舶容量轉(zhuǎn)到步驟2,否則轉(zhuǎn)到步驟3。

步驟2在更多艙位的船舶中隨機(jī)選取一個(gè)基因與之交換位置。轉(zhuǎn)到步驟1。

步驟3輸出新個(gè)體,經(jīng)過基因修復(fù)的個(gè)體,要符合本算法的生成策略,對(duì)新個(gè)體依照3.1 節(jié)的方法來調(diào)整。

3.8 算法終止條件

終止條件為計(jì)算到預(yù)設(shè)的最大進(jìn)化迭代次數(shù)時(shí)停止,然后輸出各代種群中最優(yōu)的染色體,評(píng)價(jià)每個(gè)染色體的最終得分值,得出最大利潤。

4 算例實(shí)驗(yàn)

4.1 算例描述

以某內(nèi)貿(mào)航運(yùn)公司為例,該公司經(jīng)營的北-南航線的始發(fā)港為營口港,依據(jù)合同規(guī)定,該公司租借的集裝箱遵循何地借、何地還的規(guī)則。已知始發(fā)港為營口港,還箱點(diǎn)所在港口為廣州新港,航線示意圖如圖3 所示。

圖3 航線運(yùn)營網(wǎng)絡(luò)圖

假設(shè)各港口裝卸效率統(tǒng)一,為150 TEU/h,以及各港口待裝貨物全部上船,根據(jù)模型中船舶的約束,對(duì)船舶航線選擇進(jìn)行了計(jì)算。在保證貨物全部裝走的情況下,可優(yōu)化其船舶調(diào)度情況如表2～表10 所示。

表2 船舶編號(hào)與實(shí)際航線

表3 某內(nèi)貿(mào)船公司船期表

表3 續(xù)

表4 船舶容量與適用航速

表5 運(yùn)價(jià)表

表6 港口間距離

表7 各港口待運(yùn)貨物可裝箱量

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

表9 船舶調(diào)度情況

表10 航運(yùn)企業(yè)實(shí)際船舶調(diào)度成本

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

表11 考慮各港口待還租箱所乘船舶調(diào)度成本

圖4 最優(yōu)方案收斂圖

4.2 方案有效性驗(yàn)證

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

4.3 算法科學(xué)性驗(yàn)證

(1)算法有效性

現(xiàn)將本文數(shù)學(xué)模型用CPLEX 軟件求解,因本文數(shù)學(xué)模型均是線性,故可直接求解。CPLEX 運(yùn)行時(shí)間上限設(shè)置為4 h,再與MATHEURISITIC 計(jì)算結(jié)果進(jìn)行比較,各組對(duì)比結(jié)果見表12。

從表12 可以看出,單獨(dú)利用CPLEX 求解時(shí),用時(shí)較長,在求解大規(guī)模數(shù)據(jù)時(shí),短時(shí)間內(nèi)無解。而采用啟發(fā)式算法與CPLEX 相結(jié)合進(jìn)行求解,不單利用了改進(jìn)遺傳算法計(jì)算速度較快的優(yōu)點(diǎn),而且也利用了CPLEX 精確求解的優(yōu)點(diǎn),得到的最優(yōu)解的所有偏差值都控制在5%以內(nèi)。綜上,本文采用的算法可有效地在短時(shí)間內(nèi)解決問題。

表12 算例比較結(jié)果

(2)算法優(yōu)越性

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

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

表13 改進(jìn)遺傳算法和其他算法目標(biāo)函數(shù)值比較

表14 改進(jìn)遺傳算法和其他算法CPU 耗時(shí)比較

4.4 靈敏度分析

待還租箱的數(shù)量波動(dòng)會(huì)影響船舶航線的規(guī)劃,從而進(jìn)一步影響成本。從表15 中可以看出,待還租箱數(shù)量上的波動(dòng)對(duì)成本的影響中,前者較后者的成本增加趨勢顯著。在待還租箱逐漸增加的狀態(tài)下,選擇待還租箱再次被利用,可有效縮小成本。

表15 待還租箱數(shù)量變化靈敏度分析

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

圖5 還箱成本波動(dòng)圖

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

5 結(jié)論

本文以內(nèi)貿(mào)定期航線的航運(yùn)企業(yè)為研究對(duì)象,研究在航運(yùn)企業(yè)的實(shí)際運(yùn)營中,租箱返還影響的船舶調(diào)度問題。以運(yùn)輸成本最小為研究目標(biāo),著重考慮待還租箱的資源利用、船舶航線選擇問題,最終給出了各集裝箱船舶運(yùn)輸?shù)淖顑?yōu)路徑以及待還租箱的最優(yōu)搭載船舶方案,減少了船舶運(yùn)輸成本,表明通過船舶航線的整合以及待還租箱的合理利用可有效降低租箱次數(shù)及還箱成本。

結(jié)合問題特點(diǎn),構(gòu)建混合整數(shù)模型,并設(shè)計(jì)了改進(jìn)遺傳算法與CPLEX 集成進(jìn)行求解。為類似問題的解決提供了思路。

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