鄭紅星 王泉慧 任亞群

摘 要：針對班輪企業(yè)由于提前公布船期表，但受貨運(yùn)需求的波動和潮汐的影響引起的多船型船舶調(diào)度問題進(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è)計了嵌入基因修復(fù)的改進(jìn)遺傳算法（IGA）用于模型求解。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的經(jīng)驗(yàn)調(diào)度方案相比，得到的船舶調(diào)度方案在船舶利用率上能提高25%～35%;中規(guī)模算例下與CPLEX相比，IGA的CPU處理時間平均降低77%;中、大規(guī)模算例下與蟻群算法相比，IGA計算的運(yùn)輸費(fèi)用平均降低15%。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提模型和算法的有效性，可為班輪企業(yè)船舶調(diào)度提供參考。

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

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

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

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

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

4 結(jié)語

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

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

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

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

考慮到客戶需求的變化，未來可以研究需求變動下的班輪船舶調(diào)度問題。

參考文獻(xiàn)：

[1] 唐磊，謝新連，王成武.基于集合劃分的航速可變不定期船舶調(diào)度模型[J].上海交通大學(xué)學(xué)報，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ī)與數(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é)報，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].中國管理科學(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ùn)輸船舶調(diào)度優(yōu)化問題[J].中國航海，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é)報，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].交通運(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.