考慮換船作業(yè)的長(zhǎng)江干線(xiàn)集裝箱船舶調(diào)度

王清斌，肖勤飛，李秀英，計(jì)明軍

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

0 引言

在長(zhǎng)江干線(xiàn)集裝箱運(yùn)輸過(guò)程中，船公司基本采取不定期船的運(yùn)輸方式.長(zhǎng)江干線(xiàn)的上游集裝箱任務(wù)以小批量居多，下游以批量較大任務(wù)為主，船舶的剩余箱位數(shù)和任務(wù)所需箱位數(shù)很難完全匹配，通常會(huì)產(chǎn)生剩余箱位數(shù)小于任務(wù)所需箱位數(shù)，以及剩余箱位數(shù)遠(yuǎn)大于任務(wù)所需箱位數(shù)兩種情況.無(wú)論哪種情況，增派船舶或繼續(xù)使用剩余箱位數(shù)過(guò)多的船舶，都會(huì)造成運(yùn)力浪費(fèi)和船公司運(yùn)營(yíng)成本增加.換船作業(yè)雖然會(huì)增加裝卸成本，但可以提高船舶利用率，降低船公司的運(yùn)營(yíng)成本.

集裝箱換船作業(yè)，是船公司在經(jīng)營(yíng)內(nèi)河集裝箱運(yùn)輸中經(jīng)常采取的作業(yè)方式.現(xiàn)實(shí)運(yùn)輸中，船公司對(duì)換船作業(yè)缺乏科學(xué)的決策支持，換船時(shí)間和地點(diǎn)選擇完全憑借經(jīng)驗(yàn)制定.事實(shí)上，合理的換船作業(yè)可以有效改善船公司的營(yíng)運(yùn)成本，提高船舶利用率，為船公司的決策提供新的方案支持.

船舶調(diào)度問(wèn)題一直是海運(yùn)領(lǐng)域的研究熱點(diǎn)，國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了多方面的深入研究[1-8].有學(xué)者研究了航速、潮汐等因素對(duì)船舶調(diào)度的影響，有學(xué)者著重于掛靠港選擇、運(yùn)輸任務(wù)指派和船舶選擇的組合優(yōu)化.然而，這些研究都未考慮船舶的運(yùn)營(yíng)成本，船公司在完成運(yùn)輸任務(wù)的同時(shí)，需要盡量減少投入運(yùn)力.因此，本文著重研究船舶換船作業(yè)對(duì)提高船舶實(shí)載率，減少運(yùn)力投入，降低船舶運(yùn)營(yíng)成本的影響.

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

針對(duì)長(zhǎng)江干線(xiàn)船舶剩余箱位數(shù)和任務(wù)所需箱位數(shù)很難完全匹配的情況，船公司考慮是否采取換船作業(yè)的方式，提高投入運(yùn)力的綜合利用率，降低總運(yùn)輸成本.在已知各航段的運(yùn)輸任務(wù)量和船公司可用船舶資源情況下，允許換船作業(yè)，以總運(yùn)輸成本最低為目標(biāo)，求解多港口、多船型不定期集裝箱船舶調(diào)度問(wèn)題.運(yùn)輸過(guò)程允許換船作業(yè)，一個(gè)運(yùn)輸任務(wù)從出發(fā)港到目的港可能不使用同一條船舶，這與經(jīng)典的VRP問(wèn)題不相同.

1.2 模型假設(shè)

(1)船舶航速、港口平均裝卸效率穩(wěn)定.

(2)船舶可以同時(shí)運(yùn)輸多個(gè)任務(wù)，同一任務(wù)的箱量不可拆分.

(3)單一箱型.

1.3 參數(shù)與變量

長(zhǎng)江干線(xiàn)各港口沿水道依次按順序排列，港口總數(shù)為H.考慮雙向船舶調(diào)度問(wèn)題，船舶在每個(gè)港口有兩種行駛方向，將方向不同的航段標(biāo)記為不同航段號(hào)，形成的航段總數(shù)為P=2H-2.對(duì)已知的運(yùn)輸任務(wù)a，按照跨越的航段，將其拆分為一個(gè)或多個(gè)子運(yùn)輸任務(wù).如圖1所示，5個(gè)港口的航道劃分成8個(gè)航段；運(yùn)輸任務(wù)1跨越3個(gè)航段，拆分成3個(gè)子運(yùn)輸任務(wù)，即航段2上的運(yùn)輸任務(wù)1，航段3上的運(yùn)輸任務(wù)1和航段4上的運(yùn)輸任務(wù)1.

圖1 考慮換船作業(yè)的船舶優(yōu)化調(diào)度問(wèn)題圖解Fig.1 Sample of container scheduling with transship operation

船舶運(yùn)營(yíng)的固定成本不易直接計(jì)算，將其分?jǐn)偟矫總€(gè)載箱箱位上，船舶運(yùn)輸成本包括空載箱位的運(yùn)輸成本和實(shí)載箱位的運(yùn)輸成本，其中，實(shí)載箱位的運(yùn)輸成本等于分?jǐn)偟墓潭ǔ杀炯由陷d運(yùn)集裝箱消耗的成本.考慮長(zhǎng)江干線(xiàn)運(yùn)輸實(shí)際情況，時(shí)間敏感度高的運(yùn)輸任務(wù)一般不選擇水路運(yùn)輸，故本文不過(guò)多考慮運(yùn)輸任務(wù)完成的時(shí)間約束問(wèn)題，只考慮等待時(shí)間對(duì)船舶調(diào)度的影響.

模型參數(shù)如下：

I——所有船舶集合，其元素為i，i∈{1 , 2,3,…,I}；

P——航段集合，其元素為p，p∈{0 ,1,2,…,P,P+1}，其中，0和P+1為虛擬航段，表示船舶任務(wù)開(kāi)始、結(jié)束；

A——運(yùn)輸任務(wù)的集合，其元素記為a；

Oa——運(yùn)輸任務(wù)a拆分成相鄰兩個(gè)子任務(wù)所在航段集合，如(p,q)∈Oa表示運(yùn)輸任務(wù)a相鄰兩個(gè)子運(yùn)輸任務(wù)所對(duì)應(yīng)的航段；

Oa′——運(yùn)輸任務(wù)a拆分成的所有子任務(wù)所在航段集合；

K——船舶實(shí)載次數(shù)集合，其元素為k，k∈{1 , 2,3,…,K}；

C——總運(yùn)輸成本，包括實(shí)載箱位航行成本、空載箱位航行成本、換船作業(yè)成本、港口使費(fèi)和等待成本；

e——單位集裝箱的換船作業(yè)成本；

ri——船i單位集裝箱箱位的實(shí)載航行成本；

si——船i單位集裝箱箱位的空載航行成本；

Qa——運(yùn)輸任務(wù)a的集裝箱總量；

μi——船i的最大載箱量；

wi——船i的港口使費(fèi)；

Ti——換船作業(yè)時(shí)等待船舶i的時(shí)間；

αi——船i的單位時(shí)間等待成本；

M——極大的正數(shù)；

zikpq——如果船i第k次實(shí)載過(guò)程中在相鄰航段p和q間?？?，則zikpq=1，否則為0.

決策變量：

Yikp——如果船i第k次實(shí)載過(guò)程中經(jīng)過(guò)航段p，則Yikp=1，否則為0；

xikap——如果船i第k次實(shí)載過(guò)程中運(yùn)送航段p上的運(yùn)輸任務(wù)a，則xikap=1，否則為0.

1.4 模型建立

式(1)為目標(biāo)函數(shù)，以總成本，即船舶實(shí)載箱位運(yùn)輸成本、空載箱位運(yùn)輸成本、換船成本、港口使費(fèi)及等待成本之和最小為目標(biāo)，式(2)為船舶等待時(shí)間產(chǎn)生成本的計(jì)算公式，式(3)和式(4)保證每個(gè)航段上的運(yùn)輸任務(wù)有且只有一艘船舶運(yùn)輸，式(5)保證船舶在港口的換船作業(yè)要求，式(6)保證船舶的裝載容量符合要求，式(7)保證航段的唯一性，式(8)～式(10)保證船舶航行的連續(xù)性，式(11)保證船舶實(shí)載量符合要求.

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

建立一個(gè)非線(xiàn)性混合整數(shù)規(guī)劃模型，算法與模型一致，將航段、船舶與任務(wù)進(jìn)行匹配，雖然可以通過(guò)線(xiàn)性化，使用CPLEX求解，但問(wèn)題求解規(guī)模較大，在短時(shí)間內(nèi)很難得到精確解.遺傳算法對(duì)求解此類(lèi)問(wèn)題具有較好效果，綜合模型和長(zhǎng)江干線(xiàn)特點(diǎn)，設(shè)計(jì)雙層編碼的遺傳算法求解，算法流程如圖2所示.

2.1 染色體編碼、解碼

染色體采用整數(shù)編碼，每個(gè)子運(yùn)輸任務(wù)使用的船舶是唯一的，故使用染色體上層表示子運(yùn)輸任務(wù)，染色體下層表示子運(yùn)輸任務(wù)使用的船舶.為縮小求解規(guī)模，加快算法求解速度，將具體航段信息與航次信息放入染色體解碼操作中.

如圖3所示，染色體表示3個(gè)運(yùn)輸任務(wù)由2艘船舶運(yùn)輸?shù)膬?yōu)化問(wèn)題.其解碼為010101、020101、020201、030202、030302.前兩位表示航段號(hào)、次兩位表示子運(yùn)輸任務(wù)號(hào)，最后兩位表示使用的船舶.

圖2 IGA算法流程圖Fig.2 Flow chart of IGA

圖3 染色體示意圖Fig.3 Sample of chromosome

在上述染色體編碼的基礎(chǔ)上，循環(huán)生成多條不同的染色體，得到初始種群.

2.2 選擇、交叉與變異

選擇操作采取常用的輪盤(pán)賭選擇法，據(jù)染色體的適應(yīng)度值計(jì)算每個(gè)染色體在子代中出現(xiàn)的概率，按照此概率隨機(jī)選擇個(gè)體構(gòu)成子代種群.

染色體上下兩層的編碼方式不同，故采取的交叉方式也不相同.上層染色體交叉需選取兩個(gè)交叉點(diǎn)，確定一個(gè)基因匹配段，先交換基因匹配段再調(diào)整匹配段之外的其余部分；下層染色體交叉采取單點(diǎn)交叉.上層交叉示意圖如圖4所示，選擇交叉位置為5的下層交叉示意圖如圖5所示.

圖4 上層染色體交叉示意圖Fig.4 Crossover of upper chromosome

圖5 下層染色體交叉示意圖Fig.5 Crossover of lower chromosome

變異操作采用下層染色體兩點(diǎn)變異方式.如染色體選擇下層變異位置為2和4，結(jié)果如圖6所示.

2.3 融合與基因修補(bǔ)

融合操作和基因修補(bǔ)是本文對(duì)遺傳算法的改進(jìn)之處，通過(guò)將未被選擇的染色體與交叉、變異后得到的染色體進(jìn)行重新融合，得到新的種群，擴(kuò)大了算法的搜索范圍，可大幅度提高解的精確度.

圖6 染色體變異示意圖Fig.6 Aberrance of chromosome

建模時(shí)采取分航段的方法，解空間龐大，為縮小解空間，采用基因修復(fù)方法，將裝卸量大于船舶容量的染色體作以下修復(fù)：

Step 1初始化參數(shù)，可用船舶總數(shù)為I，取交叉、變異、融合后的染色體p=1，將染色體按照航段號(hào)從小到大順序調(diào)整，并調(diào)整對(duì)應(yīng)的船舶位置，令m=1，n=1.

Step 2記錄第p個(gè)染色體第m位所對(duì)應(yīng)的航段，若在同航段上累計(jì)到位置m的任務(wù)數(shù)量大于位置n所對(duì)應(yīng)的船舶容量，則轉(zhuǎn)至Step 3；否則，轉(zhuǎn)至Step 4.

Step 3令位置n所對(duì)應(yīng)的數(shù)字取小于I的隨機(jī)數(shù)，轉(zhuǎn)至Step 2.

Step 4 令m=m+1，n=n+1，若m、n不大于染色體長(zhǎng)度的1/2，則轉(zhuǎn)至Step 2；否則，轉(zhuǎn)至Step 5.

Step 5 令p=p+1，m=1，n=1，若不大于種群規(guī)模，則轉(zhuǎn)至Step 2；否則，結(jié)束.

2.4 終止條件

計(jì)算終止條件為達(dá)到最大進(jìn)化迭代次數(shù)，輸出各代種群中最優(yōu)的染色體，轉(zhuǎn)化為運(yùn)輸任務(wù)的指派順序、港口的掛靠順序及使用的船舶.

3 數(shù)值實(shí)驗(yàn)與分析

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

以某經(jīng)營(yíng)長(zhǎng)江干線(xiàn)的集裝箱船公司為例，航線(xiàn)為長(zhǎng)江水域重慶港到洋山港，包括8個(gè)航段，如圖7所示.該公司在各港口可調(diào)用的船舶有5艘，船舶資源和相關(guān)成本參數(shù)如表1所示，各航段的距離如表2所示，運(yùn)輸任務(wù)量如表3所示.

圖7 長(zhǎng)江港口示意圖Fig.7 Sample of ports along Yangtze River

表 1 可調(diào)配船舶資源和相關(guān)成本參數(shù)Table 1 Available resource of ships and related cost parameters of ships

表2 各港口間的水路距離Table 2 Distance between ports (km)

根據(jù)以上參數(shù)，利用Matlab對(duì)模型求解，將種群規(guī)模設(shè)定為100，最大迭代次數(shù)為2 000.通過(guò)計(jì)算，得到最小運(yùn)輸成本為26.13萬(wàn)元，運(yùn)輸任務(wù)的指派情況如表4所示，各船舶的調(diào)度情況如表5所示.

表3 運(yùn)輸任務(wù)量Table 3 Freight volumes

從表4和表5可以得到具體調(diào)度方案.可以看出：因船舶剩余箱位數(shù)不能滿(mǎn)足需要，運(yùn)輸任務(wù)2、3在宜昌港換船，和任務(wù)5一起裝載到容量滿(mǎn)足的船舶4上；運(yùn)輸任務(wù)9因船舶剩余箱位數(shù)多，和任務(wù)4一起裝載至容量更合適的船舶3上.

3.2 方案有效性分析

在長(zhǎng)江干線(xiàn)船舶調(diào)度方案制定中，不考慮換船的調(diào)度方案如表6所示.

由表6可知，不考慮中途換船的調(diào)度方案總成本為31.60萬(wàn)元，通過(guò)對(duì)比，考慮換船作業(yè)的調(diào)度方案節(jié)省了5.47萬(wàn)元，降低了運(yùn)輸總成本.

表4 運(yùn)輸任務(wù)的分配Table 4 Freight assignment

表5 各船舶的調(diào)度情況Table 5 Ships scheduling

假設(shè)各航段運(yùn)量為Qp，運(yùn)距為dp，投入運(yùn)力為μp，則投入運(yùn)力綜合利用率η為

表 6 不考慮換船作業(yè)情況下各船舶的調(diào)度情況Table 6 Ships scheduling without transshipment

計(jì)算可得，換船作業(yè)調(diào)度方案與不換船作業(yè)調(diào)度方案的投入運(yùn)力綜合利用率分別為66.91%和61.07%，換船作業(yè)調(diào)度方案的投入運(yùn)力綜合利用率提升了5.84%.

考慮水路運(yùn)輸特點(diǎn)，客戶(hù)為節(jié)約運(yùn)輸成本，單個(gè)運(yùn)輸任務(wù)的運(yùn)輸量不會(huì)過(guò)小，船舶的容量在100～300 TEU.因此，選取50 TEU為界限，分析運(yùn)量在0～150 TEU的運(yùn)輸任務(wù)對(duì)調(diào)度方案結(jié)果的影響.將換船作業(yè)調(diào)度方案與不換船作業(yè)調(diào)度方案進(jìn)行對(duì)比，選取具有代表性的算例，結(jié)果如表7所示.

表 7 不同算例下的調(diào)度方案結(jié)果對(duì)比Table 7 Comparison of diffident scheduling plan with diffident parameters

從表7看出：運(yùn)輸量小于50 TEU時(shí)，船舶空間充足，靈活度高，換船作業(yè)的影響較小，不需要進(jìn)行換船作業(yè)；當(dāng)運(yùn)輸量大于50 TEU時(shí)，除了個(gè)別算例中任務(wù)數(shù)量很少不需換船作業(yè)外，換船調(diào)度方案使船舶的裝載量得到合理調(diào)整，降低運(yùn)輸總成本，投入運(yùn)力綜合利用率提高5%以上.

4 結(jié)論

允許換船作業(yè)是在作業(yè)優(yōu)化中考慮船舶運(yùn)營(yíng)成本，本文通過(guò)合理地處理分析運(yùn)營(yíng)成本，在運(yùn)輸需求已知的情況下，針對(duì)長(zhǎng)江干線(xiàn)直線(xiàn)型航道的特點(diǎn)，構(gòu)建長(zhǎng)江干線(xiàn)集裝箱運(yùn)輸多船型船舶調(diào)度非線(xiàn)性規(guī)劃模型，設(shè)計(jì)改進(jìn)的遺傳算法求解.研究表明，在考慮船舶運(yùn)營(yíng)成本的情況下，換船作業(yè)能夠提升投入運(yùn)力綜合利用率，為船公司降低運(yùn)營(yíng)成本提供了新途徑.

考慮到運(yùn)輸需求的動(dòng)態(tài)性，未來(lái)可以研究實(shí)時(shí)調(diào)度下的考慮換船作業(yè)的長(zhǎng)江干線(xiàn)集裝箱船舶調(diào)度問(wèn)題.