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

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

0 引言

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

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

在考慮時(shí)間窗的船舶調(diào)度方面,文獻(xiàn)[1]研究了時(shí)間窗、航速影響的船舶調(diào)度問(wèn)題,建立了船舶成本、總服務(wù)成本最小和總利潤(rùn)最大的多階段模型,并利用仿真進(jìn)行求解。文獻(xiàn)[2]研究了受惡劣天氣影響的船舶調(diào)度問(wèn)題,以總成本最小為目標(biāo)函數(shù)建立模型,并設(shè)計(jì)了嵌入基因修復(fù)算子的改進(jìn)遺傳算法進(jìn)行求解。文獻(xiàn)[3]研究了基于船期表、航速及受泊時(shí)間窗的船舶調(diào)度問(wèn)題,以總成本最小為目標(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)問(wèn)題,以費(fèi)用最低為目標(biāo)函數(shù)構(gòu)建混合整數(shù)模型,并用基于免疫的進(jìn)化算法進(jìn)行求解。文獻(xiàn)[7]研究了基于動(dòng)態(tài)規(guī)劃的空箱分配問(wèn)題,以?xún)筛劭趦珊骄€調(diào)運(yùn)系統(tǒng)建立動(dòng)態(tài)隨機(jī)模型,并利用模擬仿真驗(yàn)證其有效性。文獻(xiàn)[8]研究了結(jié)合庫(kù)存策略的空箱調(diào)運(yùn)問(wèn)題,以成本最低為目標(biāo),基于罰函數(shù)建立庫(kù)存模型,并用啟發(fā)式算法進(jìn)行求解。

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

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

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

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

1 問(wèn)題描述

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

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

本文的問(wèn)題可描述為:針對(duì)某個(gè)航運(yùn)企業(yè)的航線輻射網(wǎng)絡(luò),在一個(gè)運(yùn)營(yíng)周期內(nèi)(從第一條船舶出發(fā)時(shí)刻開(kāi)始計(jì)時(shí),截止到整個(gè)航線網(wǎng)絡(luò)中最后一條船舶達(dá)到目的港的時(shí)刻為一個(gè)運(yùn)營(yíng)周期),已知各船舶進(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)化模型,研究考慮待還租箱再次被利用的條件下的租箱返還問(wèn)題,最終給出各條船舶所選航線以及各個(gè)待還租箱所搭載的船舶計(jì)劃方案。航線網(wǎng)絡(luò)圖如圖1 所示。

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

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

2.1 基本假設(shè)

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

(1)所有船舶均可航行于航運(yùn)企業(yè)輻射的各類(lèi)航線;在航運(yùn)企業(yè)的實(shí)際運(yùn)營(yíng)過(guò)程中,為應(yīng)對(duì)實(shí)際的需求變動(dòng)或各種突發(fā)狀況一般僅定線不定船,航運(yùn)企業(yè)實(shí)際營(yíng)運(yùn)的船舶需在該公司輻射的各類(lèi)航線間跨航線調(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),無(wú)其他費(fèi)用;在待還租箱返還過(guò)程中,可能還會(huì)產(chǎn)生折舊、清洗等費(fèi)用,但相對(duì)超期費(fèi)來(lái)說(shuō),這些費(fèi)用較低,可忽略。

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

2.2 符號(hào)說(shuō)明

(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港裝上來(lái)自j港的集裝箱箱量,i可以等于j;sijn:表示第n條船在i港卸下來(lái)自j港的集裝箱箱量;yijn:為0 -1 變量,表示船舶的航行路線信息,若第n條船從i港駛向j港,yijn=1,否則yijn=0。

2.3 模型構(gòu)建

集裝箱調(diào)運(yùn)過(guò)程中,為使成本最低,基于整體航線網(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)與新增利潤(rùn)之差;Σ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)輸過(guò)程中還箱成本最小為目標(biāo),因航線需重新整合,故集裝箱船舶運(yùn)輸及作業(yè)所產(chǎn)生的成本計(jì)入目標(biāo)函數(shù)中,從第一條船舶在始發(fā)港作業(yè)開(kāi)始計(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)保證集裝箱船舶駛來(lái)或駛?cè)サ谋匾?式(7)表示待還租箱是否有必要承擔(dān)超期費(fèi)而選擇再次利用的約束;式(8)表示超期費(fèi)的計(jì)費(fèi)規(guī)則;式(9)～式(10)表示整個(gè)活動(dòng)過(guò)程運(yùn)行的邏輯約束;式(11)～式(12)表示船舶路徑選擇約束,若xijn＞0 說(shuō)明船舶n從i港到過(guò)j港;式(13)表示待還租箱的路徑選擇約束,若fipn＞0 說(shuō)明船舶n從i港裝過(guò)來(lái)自p港的集裝箱;若sipn＞0 說(shuō)明船舶n從i港卸下來(lá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ù)中新增了利潤(rùn)與超期費(fèi)之差的多項(xiàng)式,并且新增多個(gè)約束條件,故本文模型更加復(fù)雜化?？紤]到本文計(jì)算量較大,依據(jù)模型的特點(diǎn),設(shè)計(jì)了改進(jìn)遺傳算法,建立了虛擬港口,即若待還租箱在某一港口被再次利用,則經(jīng)過(guò)這一虛擬港口,再多次進(jìn)行交叉變異,得到精確解。這一過(guò)程的具體執(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 選擇過(guò)程

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

步驟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ù)交叉與變異過(guò)程

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

步驟1生成一個(gè)0～1 的隨機(jī)數(shù),檢測(cè)該數(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è)場(chǎng)區(qū)的待裝載集裝箱的數(shù)量大于船舶容量的情況,采取以下步驟修復(fù)。

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

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

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

3.8 算法終止條件

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

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

4.1 算例描述

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

圖3 航線運(yùn)營(yíng)網(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)以租箱第一次上船開(kāi)始計(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)營(yíng)的過(guò)程中,采用待還租箱再次利用的措施,本周期航線網(wǎng)的運(yùn)營(yíng)成本為7 542 460.5 元。通過(guò)比較表10 和表11,可看出成本可降低19%,雖待還租箱再次利用會(huì)產(chǎn)生額外成本,但所增加的利潤(rùn)可完全覆蓋并超出額外成本。另一方面,從長(zhǎng)期運(yùn)營(yíng)的角度看,待還租箱的再次利用,可在一個(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é)果見(jiàn)表12。

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

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

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

為驗(yàn)證算法的優(yōu)越性,本文同時(shí)針對(duì)此問(wèn)題,分別用量子差分進(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 求解本文問(wèn)題時(shí)所得目標(biāo)函數(shù)值之差占目標(biāo)函數(shù)值的比例,表14 中QTIC、ATIC、MTIC分別表示MATHEURISIT 與QDE、ACO、MHA 求解本文問(wèn)題時(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ì)成本的影響中,前者較后者的成本增加趨勢(shì)顯著。在待還租箱逐漸增加的狀態(tài)下,選擇待還租箱再次被利用,可有效縮小成本。

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

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

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

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

5 結(jié)論

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

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

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