考慮潮汐影響的班輪多船型船舶調(diào)度

鄭紅星 王泉慧 任亞群

摘 要：針對(duì)班輪企業(yè)由于提前公布船期表，但受貨運(yùn)需求的波動(dòng)和潮汐的影響引起的多船型船舶調(diào)度問(wèn)題進(jìn)行研究。首先系統(tǒng)分析了一家班輪企業(yè)近洋運(yùn)輸航線結(jié)構(gòu);然后考慮大型船舶需乘潮進(jìn)出港口，以及適當(dāng)條件下允許租船的實(shí)際情況，兼顧班輪船期表的限制，構(gòu)建了以運(yùn)輸總成本最小為目標(biāo)的班輪多船型船舶調(diào)度非線性規(guī)劃模型;最后考慮模型的特點(diǎn)，設(shè)計(jì)了嵌入基因修復(fù)的改進(jìn)遺傳算法（IGA）用于模型求解。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的經(jīng)驗(yàn)調(diào)度方案相比，得到的船舶調(diào)度方案在船舶利用率上能提高25%～35%;中規(guī)模算例下與CPLEX相比，IGA的CPU處理時(shí)間平均降低77%;中、大規(guī)模算例下與蟻群算法相比，IGA計(jì)算的運(yùn)輸費(fèi)用平均降低15%。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提模型和算法的有效性，可為班輪企業(yè)船舶調(diào)度提供參考。

關(guān)鍵詞：班輪多船型船舶調(diào)度;船期表預(yù)知;非線性規(guī)劃;可變航速;潮汐

中圖分類號(hào)： U692.4+3

文獻(xiàn)標(biāo)志碼：A

Abstract： The multi-type liner scheduling problem in liner enterprises caused by the fluctuation of cargo demand and tide with line schedule announced in advance was studied. Firstly， the structure of near-sea transportation routes of a liner enterprise was systematically analyzed. Then， with the consideration of the real situations like large ships need to tide in and out of ports， ship renting is permitted under appropriate conditions， and the limits of a liner schedule， a nonlinear programming model of multi-type liner scheduling was built with the objective of minimizing the total transportation cost. Finally， in view of the characteristics of the model， an Improved Genetic Algorithm （IGA） embedded with gene repair was designed to solve the problem. Experimental results show that the proposed liner scheduling scheme can improve the ship utilization ratio by 25%-35% compared with the traditional experiential liner scheduling scheme， the CPU processing time of IGA is reduced by 32% on average compared with CPLEX in medium scale， and the transportation cost of IGA is reduced by 12% on average compared with ant colony algorithm in medium and large scales. All above demonstrates the validity of the proposed model and algorithm which can provide a reference for liner enterprises in liner scheduling.

Key words： multi-type liner scheduling; liner schedule prediction; nonlinear programming; variable speed; tide

0 引言

雖然班輪企業(yè)都會(huì)提前一個(gè)月左右公布船期表，但由于貨運(yùn)市場(chǎng)的起伏波動(dòng)，以及天氣和其他不確定因素的影響，使得每艘船舶的掛靠港口次序和每次運(yùn)營(yíng)的航線是不確定的。因此，為了盡可能保證貨物按原船期表進(jìn)行運(yùn)輸，并充分利用船隊(duì)資源，提高航運(yùn)企業(yè)的服務(wù)效率，需運(yùn)用科學(xué)合理的方法對(duì)船舶調(diào)度進(jìn)行優(yōu)化。

船舶調(diào)度問(wèn)題一直是相關(guān)各方研究的熱點(diǎn)問(wèn)題，是針對(duì)航運(yùn)企業(yè)經(jīng)營(yíng)的每艘船，指定具體的航行路線、掛靠港口、運(yùn)輸任務(wù)及其運(yùn)作時(shí)間表，通過(guò)合理的調(diào)度，高效利用船舶。船舶調(diào)度問(wèn)題主要分為不定期船舶調(diào)度和班輪船舶調(diào)度兩類。在不定期船舶調(diào)度方面，唐磊等[1]將船速對(duì)航次成本、航次時(shí)間的影響納入到研究中，提出了不定期船舶調(diào)度的非線性網(wǎng)絡(luò)規(guī)劃模型，用于解決航速可變的船舶選線與調(diào)度規(guī)劃問(wèn)題，設(shè)計(jì)了基于集合劃分方法的兩階段算法求解。錢燕等[2]針對(duì)不定期船舶調(diào)度中需求信息的動(dòng)態(tài)變化、船舶類型的多樣化以及船舶航線的不定性，以最小化航運(yùn)成本為目標(biāo)，建立了帶滾動(dòng)窗口的不定期多目標(biāo)船舶調(diào)度優(yōu)化模型，并制定了實(shí)時(shí)優(yōu)化策略以實(shí)現(xiàn)需求信息變化時(shí)能快速調(diào)整船舶調(diào)度航線。Lin等[3]研究了不定期船舶分艙運(yùn)輸和貨載轉(zhuǎn)讓的營(yíng)運(yùn)特點(diǎn)，建立船舶調(diào)度與貨運(yùn)分配組合優(yōu)化的模型，并用遺傳算法求解。

在班輪船舶調(diào)度方面，Agarwal等[4]將班輪運(yùn)輸中運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)與船舶調(diào)度、貨物路徑問(wèn)題進(jìn)行聯(lián)合優(yōu)化，以船隊(duì)在運(yùn)輸網(wǎng)絡(luò)上的利潤(rùn)最大為目標(biāo)，建立了混合整數(shù)規(guī)劃模型，并用貪婪算法、列生成算法等三種算法求解。壽涌毅等[5]應(yīng)用多目標(biāo)規(guī)劃方法研究了班輪運(yùn)輸?shù)拇罢{(diào)度問(wèn)題，追求變動(dòng)成本、航線運(yùn)載量缺口和班輪航次總絕對(duì)偏差的共同最小化。Li等[6]側(cè)重于實(shí)時(shí)船期計(jì)劃恢復(fù)問(wèn)題，并考慮了常規(guī)不確定性和突發(fā)不確定性，目標(biāo)是使延誤懲罰總數(shù)最小化，以最有效的方式恢復(fù)受影響的時(shí)間表。Meng等[7]進(jìn)行了班輪運(yùn)輸網(wǎng)絡(luò)中有多個(gè)港口、多艘船的時(shí)間表設(shè)計(jì)和集裝箱路線規(guī)劃設(shè)計(jì)。楊立乾[8]基于軸輻式網(wǎng)絡(luò)，在假定喂給港可被不同船舶多次掛靠的情況下，考慮船舶的運(yùn)載能力以及班輪船期表的影響，建立集裝箱支線運(yùn)輸多船型船舶調(diào)度模型，并利用粒子群算法求解。

但是以上班輪船舶調(diào)度均未考慮航速對(duì)船舶調(diào)度的影響。隨著研究問(wèn)題的深入，航速優(yōu)化逐步成為船舶調(diào)度的一個(gè)側(cè)重點(diǎn)，其中Qi等[9]考慮班輪時(shí)間表上不確定的港口時(shí)間和頻率要求，考慮到航速的影響，以預(yù)期的總油耗最低為目標(biāo)建立模型，制定了最佳船舶時(shí)間表。Lee等[10]使用一個(gè)動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)了一個(gè)帶有港口時(shí)間窗口的單船航線，每個(gè)港口只能被訪問(wèn)一次，將航速對(duì)航次時(shí)間的非線性影響納入到船舶調(diào)度中，建立了以集裝箱船舶運(yùn)營(yíng)成本最小的非線性混合整數(shù)規(guī)劃模型來(lái)設(shè)計(jì)船期表。

綜上，國(guó)內(nèi)外對(duì)船舶調(diào)度的現(xiàn)有文獻(xiàn)中，國(guó)外學(xué)者對(duì)于班輪船舶調(diào)度研究較多，而國(guó)內(nèi)學(xué)者對(duì)不定期船舶調(diào)度研究居多;文獻(xiàn)多以船舶運(yùn)營(yíng)總成本最小或者以利潤(rùn)最大為目標(biāo)制定船舶調(diào)度計(jì)劃，考慮航速變化對(duì)船舶調(diào)度的影響的文獻(xiàn)近年來(lái)逐漸增加;具體到班輪船舶調(diào)度，多以船期表的制定為主，罕有考慮船期表提前公布情況下，研究為保證貨物準(zhǔn)時(shí)從啟運(yùn)港裝卸并按時(shí)抵達(dá)目的港的船舶調(diào)度優(yōu)化;且少有考慮自營(yíng)船舶數(shù)目確定，適當(dāng)時(shí)機(jī)可租船的實(shí)際情況;而針對(duì)現(xiàn)實(shí)作業(yè)中某些港口大型船舶需乘潮進(jìn)/出港進(jìn)而影響整個(gè)航線上船舶運(yùn)輸時(shí)間的問(wèn)題目前幾乎沒(méi)有文獻(xiàn)涉及。

區(qū)別于已有文獻(xiàn)，本文針對(duì)船期表已提前公布的多條班輪航線，重點(diǎn)考慮船期表對(duì)船舶調(diào)度的約束，兼顧某些大型船舶需乘潮進(jìn)出港的現(xiàn)實(shí)，以及航速變化對(duì)運(yùn)輸時(shí)間的影響，并涵蓋可適時(shí)租船的情況，研究固定計(jì)劃期內(nèi)班輪船舶調(diào)度問(wèn)題，以確保有船按時(shí)來(lái)港裝卸貨物，使得計(jì)劃期內(nèi)船舶運(yùn)輸總成本最低。

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

1.1 問(wèn)題描述

針對(duì)一個(gè)已有班輪船隊(duì)，班輪公司在經(jīng)營(yíng)范圍內(nèi)對(duì)貨源、貨流進(jìn)行調(diào)查和預(yù)測(cè)，制定并公布未來(lái)一段時(shí)間的船期表。在該船期表使用過(guò)程中，受貨運(yùn)需求波動(dòng)及潮汐等其他不確定因素的影響，船舶可能無(wú)法按照預(yù)計(jì)時(shí)間到港裝卸貨物，給班輪企業(yè)和客戶帶來(lái)?yè)p失。由于客戶需要可靠的服務(wù)并期望準(zhǔn)時(shí)交貨，且企業(yè)要避免更高的運(yùn)輸成本受損，班輪企業(yè)需要根據(jù)具體貨運(yùn)需求調(diào)整航線上船舶的掛靠港、航速或租船，確保貨物能按時(shí)裝卸，以滿足航線上港口的貨運(yùn)需求，而且能使班輪企業(yè)獲得良好的經(jīng)濟(jì)效益。

問(wèn)題描述：預(yù)知固定計(jì)劃期內(nèi)各航線的貨運(yùn)流量和船期表，探討多個(gè)港口、多種船型的班輪船舶調(diào)度問(wèn)題，在保證貨物按時(shí)裝卸的前提下，以計(jì)劃期內(nèi)所有船舶運(yùn)輸成本最低制定船舶調(diào)度方案。區(qū)別于已有文獻(xiàn)，本文的側(cè)重點(diǎn)主要有以下幾個(gè)方面：

4 結(jié)語(yǔ)

本文在船期表預(yù)知的情況下，針對(duì)多條近洋航線考慮了船舶容量、數(shù)量、航速、班輪時(shí)間的限制以及大型船舶需乘潮進(jìn)出港口的情況，構(gòu)建了集裝箱運(yùn)輸多船型船舶調(diào)度非線性規(guī)劃模型，并設(shè)計(jì)了改進(jìn)的遺傳算法IGA求解。具體結(jié)論如下：

1）建立了考慮大型船舶需乘潮進(jìn)出港口的實(shí)際情況的多船型船舶調(diào)度模型，在船期表預(yù)知的前提下，考慮調(diào)節(jié)船速有助于保證船舶按時(shí)到港裝卸貨物;考慮適時(shí)租船保證貨量需求得到滿足。盡管航速提高和租船會(huì)帶來(lái)部分成本，但是與貨物運(yùn)輸延誤給班輪企業(yè)所帶來(lái)的損失相比甚微。

2）設(shè)計(jì)了改進(jìn)的遺傳算法IGA，對(duì)于不同層的染色體根據(jù)其實(shí)際特點(diǎn)采取了不同的編碼方式，融入了基因修復(fù)的思想，能為解決該類船舶調(diào)度問(wèn)題的算法提供新的設(shè)計(jì)思路。

3）本文所設(shè)計(jì)的模型與算法可以為班輪企業(yè)船舶調(diào)度提供決策支持，對(duì)于客戶滿意度要求較高的班輪企業(yè)有借鑒意義。

考慮到客戶需求的變化，未來(lái)可以研究需求變動(dòng)下的班輪船舶調(diào)度問(wèn)題。

參考文獻(xiàn)：

[1] 唐磊，謝新連，王成武.基于集合劃分的航速可變不定期船舶調(diào)度模型[J].上海交通大學(xué)學(xué)報(bào)，2013，47（6）：909-915.（TANG L， XIE X L， WANG C W. Model of tramp ship scheduling with variable speed based on set partition approach [J]. Journal of Shanghai Jiao Tong University， 2013， 47（6）： 909-915.）

[2] 錢燕，周良.基于遺傳算法的不定期船舶調(diào)度優(yōu)化模型研究 [J].計(jì)算機(jī)與數(shù)字工程，2014，42（4）：601-605. （QIAN Y， ZHOU L. Optimization model of tramp ship scheduling based on genetic algorithm [J]， Computer and Digital Engineering， 2014， 42（4）： 601-605.）

[3] LIN D-Y， LIU H-Y. Combined ship allocation， routing and freight assignment in tramp shipping [J]. Transportation Research Part E： Logistics and Transportation Review， 2010， 47（4）： 414-431.

[4] AGARWAL R， ERGUN O. Ship scheduling and network design for cargo routing in liner shipping [J]. Transportation Science， 2008， 42（2）： 175-196.

[5] 壽涌毅，賴昌濤，呂如福.班輪船舶調(diào)度多目標(biāo)優(yōu)化模型與蟻群算法[J].交通運(yùn)輸工程學(xué)報(bào)，2011，11（4）：84-88. （SHOU Y Y， LAI C T， LYU R F. Multi-objective optimization model and ant colony optimization of liner ship scheduling[J].Journal of Traffic and Transportation Engineering， 2011， 11（4）： 84-88.）

[6] LI C， QI X， SONG D. Real-time schedule recovery in liner shipping service with regular uncertainties and disruption events [J]. Transportation Research Part B： Methodological， 2016， 93： 762-788.

[7] MENG Q， WANG S. Schedule design and container routing in liner shipping [J]. Transportation Research Record， 2011， 2222（1）： 25-33.

[8] 楊立乾.基于軸輻式網(wǎng)絡(luò)的集裝箱支線運(yùn)輸多船型船舶調(diào)度模型[J].中國(guó)管理科學(xué)，2015，23（SI）：860-864. （YANG L Q. Scheduling model of feeder line multi-hull container ships based on hub-and-spoke network [J]. Chinese Jurnal of Management Science， 2015， 23（SI）： 860-864.）

[9] QI X， SONG D-P. Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times [J]. Transportation Research Part E： Logistics and Transportation Review， 2012， 48（4）： 863-880.

[10] LEE C-Y， MENG Q. Handbook of Ocean Container Transport Logistics： Making Global Supply Chains Effective [M]. Berlin： Springer， 2015： 279-373.

[11] 靳志宏，解玉真，李陽(yáng)，等.集裝箱支線運(yùn)輸船舶調(diào)度優(yōu)化問(wèn)題[J].中國(guó)航海，2008，31（4）：416-419. （JIN Z H， XIE Y Z， LI Y， et al. Scheduling optimization problems of feeder line container ships [J]. Navigation of China， 2011， 31（11）： 3075-3077.）

[12] 呂靖，毛鶴達(dá).硫排放控制區(qū)和碳排放限制下的班輪航線配船模型[J].大連海事大學(xué)學(xué)報(bào)，2017，43（1）：101-105. （LYU J， MAO H D. Fleet deployment for liner shipping under the restriction of SOx emission control areas and CO2 emission [J]. Journal of Dalian Maritime University， 2017， 43（1）： 101-105.）

[13] 杜劍，趙旭，王軍.內(nèi)支線集裝箱班輪航線優(yōu)化設(shè)計(jì)模型[J].交通運(yùn)輸系統(tǒng)工程與信息，2017，17（3）：178-191. （DU J， ZHAO X， WANG J. Container feeder liner shipping service optimal design model [J]. Journal of Transportation Systems Engineering and Information Technology， 2017， 17（3）：178-191.）

[14] DULEBENETS M A. The vessel scheduling problem in a liner shipping route with heterogeneous fleet [J]. International Journal of Civil Engineering， 2018， 16（1）： 19-32.