復式航道港口拖輪配置仿真優化

鄭紅星，徐海棟，曹紅雷

(大連海事大學 交通運輸管理學院，遼寧 大連 116026)

復式航道港口拖輪配置仿真優化

鄭紅星，徐海棟，曹紅雷

(大連海事大學 交通運輸管理學院，遼寧 大連 116026)

為更好地指導復式航道港口拖輪資源的配置，構建了拖輪作業仿真模型。基于復式航道的特點，給出了基于Arena的仿真模型，并嵌入了以拖輪耗油總成本最小為目標的作業調度優化模型；給出了嵌入啟發式規則的遺傳算法用于求解該模型；并通過多次仿真實驗，兼顧拖輪的作業耗油總成本和閑置率，篩選出當前的最優配置方案；通過拖輪閑置率隨船舶類型和數量變化的仿真分析，并結合未來船舶大型化的趨勢，給出了未來的拖輪最佳配置方案。

航道工程；復式航道；拖輪配置；遺傳算法；拖輪閑置率

0 引 言

一般情況下，船舶在港口的進出港作業需要拖輪協助，拖輪的配置是影響港口作業效率和客戶滿意度的重要因素。拖輪的合理配置與港口航道模式、拖輪作業調度緊密相關，對拖輪資源進行合理調度，可以提高拖輪作業效率，降低作業成本，是提高港口競爭力的重要途徑，也是港口作業的研究熱點；而隨著船舶大型化的發展，復式航道在港口中越來越普遍，復式航道兼具單向航道與雙向航道的特點，因此研究復式航道更有意義。

近年來，國內外學者對相關問題進行了細致的研究，主要從以下3個方面評述。

在航道模式的研究方面，黃泰坤等[1]通過對比雙向航道及復式航道下天津港運營情況，探討了港口服務水平、錨地等待時間、航道等待時間等因素隨著船流密度變化的趨勢；唐國磊等[2]研究了航道尺度對泊位有效利用率的影響，構建了相應的仿真模型，并進行了系統分析。姬利娜[3]針對城市路網中存在畸形交叉口的客觀事實，在分析畸形交叉口帶來的交通問題的基礎上，提出了畸形交叉口交通改善的基本思路和方法，可為船舶航道交通流研究提供借鑒；王江濤[4]基于非集計離散選擇模型理論，結合通道內各種運輸方式特性，給出了在運用 MNL 模型預測通道客運分擔率時特性變量的選取原則,對航道通過率研究有一定指導意義。

在拖輪配置方面，陸海波[5]對影響拖輪總體配置的生產要素進行了全面的統計和分析，使港口拖輪配置規模和結構日趨合理，為港口的拖輪配置提供了相關借鑒；劉志雄[6]通過分析港口拖輪作業的過程及特點，通過仿真計算得到船舶的平均等待時間、最大排隊隊長及各種拖輪的利用率等參數，為決策者合理配置拖輪提供了科學依據。

在拖輪調度方面，WANG Su等[7]結合現有調度規則構建了拖輪調度問題的混合整數規劃模型，通過數值實驗證明了所構建模型的效用，并分析了拖輪的配置數量對到港船舶在港時間造成的影響；王巍等[8]和HE Tao等[9]分別針對多停泊基地和不同作業模式下的拖輪調度，以最大完工時間和總作業油耗最小為目標，建立了拖輪調度多目標優化模型，計算結果表明不同作業模式對拖輪調度結果會產生較大影響；WANG Su等[10]在集裝箱終端拖輪調度問題研究的基礎上，以最少船舶周轉時間為目標，提出互相信任策略的蟻群算法，進一步提高了船舶進出港的效率；徐奇等[11-12]考慮了多階段共用平行機特征的拖輪作業模式優化問題，建立了考慮兩階段與切換時間的調度優化模型，設計了啟發式規則與模擬退火結合的求解算法，并運用Arena軟件對拖輪助泊作業系統進行仿真實現；YU Wenhui[13]對港口拖輪的優化及仿真進行研究，采用啟發式算法求解最優解，并進行了驗證實驗；LIN Jiahong等[14]通過Arena軟件對虎門港的港口資源進行分析，提出以總成本和港口生產能力為指標的改進方案。

綜上，現有研究大多側重不同類型航道的通過能力，少有研究航道同其他港口作業資源集成的文獻；大多數學者主要采用統計和預測的方法來研究拖輪的配置，鮮有兼顧航道類型和拖輪調度的文獻；大多數文獻主要考慮作業成本、等待時間等因素，建立調度優化模型并設計啟發式算法求解，罕有將拖輪調度和配置融為一體的研究。因此，筆者在現有研究基礎上，將拖輪配置和調度優化問題集成，并兼顧復式航道的特點，建立相應的仿真優化模型，分析不同配置方案的各項關鍵指標，得出合理的配置方案。

1 問題描述

在多數復式航道的港口中，中間主航道用來通行大型船舶，且分時段單向通航，兩側副航道通行中小型船舶，且分進出單向通航。

船舶從到達到離開港口，主要有以下3個拖輪作業過程。① 進港：船舶需要輪拖拽進入泊位進行相關裝卸作業；② 移泊：船舶需要拖輪的協助在不同泊位之間移動以便于貨物的裝卸；③ 出港：船舶裝卸完畢后需要拖輪協助離開泊位進入航道完成出港作業。

問題描述為：在復式航道的港口中，根據船舶到達的種類和數量，如何確定配置拖輪的類型及數量，在能夠滿足調度需要的條件下使拖輪作業成本最小。

2 優化模型

一般情況下，船舶在抵港前24 h會通知港方，港方以24 h為一個作業周期來安排拖輪作業，以作業周期內拖輪耗油總成本最低為目標，構建拖輪作業調度模型。

2.1 假設條件

1) 假設有內外兩個拖輪基地；

2) 只考慮船舶進港靠泊和離泊出港兩個階段的拖輪作業任務；

3) 進港船舶按照到達先后順序排列，出港船舶按照預計離港時間(EDT)先后順序排列；

4) 船舶通過航道的時間一定，且拖輪空駛的速度遠大于牽引作業的速度。

2.2 符號定義

2.2.1 參 數

I為所有船舶的集合，I={1，2，…，m}；J為拖輪類型的集合，J={1，2，…，n}；P為每種拖輪編號的集合，P={1，2，…，s}；W為所有作業時段的集合，W={1，2，…，12}；SNS為所有拖輪數量；Sij為第i條船所需第j種拖輪的數量；TATi為第i條船的到達時刻；TLOTi為船舶i裝卸作業所需時長；TTUi為最晚裝卸時間；TEDTi為第i條船預計離港時間；TH為第i條船船舶進(出)港在航道上的航行時間；Tk為拖輪空駛通過航道的時間；TS為兩只船舶在航道上航行所需預留的安全間隔時長；T0為一個作業時段的長度；C1為拖輪單次作業耗油成本；C2為拖輪空駛耗油成本；C0j為第j種類型拖輪耗油系數。

2.2.2 決策變量

TITi為第i條船開始進港的時刻，TOTi為第i條船開始出港的時刻。

2.2.3 過程變量

2.3 模型建立

2.3.1 目標函數

2.3.2 約束條件

(1)

p∈P

(2)

(3)

(4)

TOTi+1=max{TOTi+TH+Tk,TEDTi};i∈I,

(5)

(6)

(w-1)T0≤TITi

(7)

(w-1)T0≤TOTi

(8)

(w-1)T0

(9)

(w-1)T0

(10)

p∈P

(11)

(12)

TITi+TH+TLOTi≤TLTi;i∈I

(13)

TITi+TH+TLOTi≥TATi;i∈I

(14)

TOTi≥TEDTi;i∈I

(15)

其中：式(1)表示為船舶服務的拖輪數量必須滿足該船需求；式(2)表示一條船舶只能由同一種類型拖輪進行作業；式(3)～(4)表示船舶進港時間限制；式(5)～(6)表示船舶出港時間限制；式(7)～(8)表示主航道船舶必須在進港時段入港、出港時段出港；式(9)～(10)表示主航道船舶必須在進港時段結束前完成進港作業、在出港時段結束前完成進港作業；式(11)～(12)分別表示在內、外拖輪基地的拖輪數量小于拖輪總數量；式(13)～(14)表示船舶在港作業的時間不得早于到達時間且不能超過限制時間；式(15)表示船舶實際離港時間不得早于預計離港時間。

2.4 求 解

拖輪調度是NP-hard問題，基于模型特點，設計了嵌入啟發式規則的遺傳算法。

2.4.1 多維實數編碼

筆者采用多維實數編碼方式進行問題求解。每條船只能由1種類型且最多不超過2艘拖輪共同作業，則所需染色體共分為3層，見圖1。

圖1 染色體編碼示意Fig.1 Chromosome coding schemes

按照已知的階段順序編碼，從左到右依次對應各階段所需接受拖輪服務的船舶。第1行表示服務該船的拖輪類型。第2，3行表示服務該船的拖輪的編號。染色體的長度由所需進、出港作業的船舶數量決定。

2.4.2 初始種群生成

在初始種群生成時，采用了首艘拖輪可用的啟發式規則生成種子染色體，加快最優解的搜索速度，提高算法效率，該染色體滿足船舶拖輪類型、數量的匹配要求以及時間約束，主要步驟如下：

Step1：當船舶根據預定順序準備進(出)港作業時，首先判斷當前時段是進港時段還是出港時段；其次，判斷船舶類型，大船在進港時段通過主航道進港，在出港時段通過主航道出港，否則需要等相應作業時段才能進行進(出)港作業，中小船可以隨時通過副航道進(出)港。

Step2：根據船舶進港規則完成判斷后，需完成船舶拖輪匹配任務，首先，更新已有的拖輪信息；其次，按照拖輪的編號判斷該拖輪基地第一種類型的拖輪跟船舶是否匹配，如果能夠匹配，判斷該種類型的拖輪數量是否足夠，如果條件都滿足，則完成匹配過程；如果不滿足，則按序轉到下一種型號拖輪繼續匹配，直到找到滿足條件的拖輪。

Step3：如果該拖輪基地所有種類的拖輪都不滿足船舶進(出)港的要求，則要考慮其他拖輪基地拖輪空駛的情況，需要按照第二步的順序判斷空駛的拖輪基地的拖輪的種類、數量是否滿足調度要求。如果滿足，則拖輪空駛；否則，船舶等待。

2.4.3 適應度函數與選擇規則

采用輪盤賭進行個體的選擇，設f(x)為目標函數，則F(x)=1/f(x)。

2.4.4 交叉與變異

考慮交叉操作的實際意義，把染色體的3層同點同時進行交叉，在變異操作時，賦予每一層不同的變異范圍；同時在交叉變異之后增加染色體的修復過程如下：

Step1：對于i=1∶n，若第2行染色體CTT(i)=0時，重新生成CTT(i)，轉到Step2；

Step2：判斷生成染色體的拖輪數量是否與拖輪船舶數量匹配，若匹配轉到Step3，否則，轉到Step4；

Step3：判斷第2行染色體與第3行染色體拖輪編號有沒有重復，若重復，重新生成第3行染色體，否則，轉到Step5；

Step4：將不匹配的染色體選出，重新生成，轉到Step2；

Step5：染色體修復完畢。

終止條件

當迭代次數達到預先設置代數時，算法終止。

3 仿真模型

筆者基于離散事件仿真原理，以7 d為仿真周期，仿真周期內每24 h做一次拖輪調度，以min為仿真步長，通過Arena軟件建立相應的仿真模型，主要仿真流程如下。

首先，讀取數據模塊獲取本次仿真的拖輪配置信息，并讀取每天抵港船舶的相關信息、及基于調度優化模型給出的每天拖輪調度方案；其次，船舶拖輪匹配模塊基于讀取的數據，實時給抵港船舶分配拖輪和作業時段；第三，航道行駛模塊用于仿真船舶基于設定的復式航道通行規則進出港，拖輪牽引船舶通過相應航道的作業過程；第四，拖輪釋放模塊用于仿真拖輪牽引船舶完成相應的進出港任務后，拖輪釋放的過程。各模塊示意如圖2～5。限于篇幅，在船舶拖輪匹配模塊中，只截取該模塊中大型拖輪判斷部分。

圖2 數據讀取模塊示意Fig.2 Data reading module

圖4 航道通航模塊示意Fig.4 Navigation module

圖5 拖輪釋放模塊示意Fig.5 Tugboat release module

4 算例實驗

4.1 算例描述

某港擁有一條復式航道，其中主航道只允許大型船舶通航，每2 h為一個時段交替進行進、出港作業，在主航道兩側各有一條副航道，設有內、外兩個拖輪基地，并配有大、中、小這3類拖輪，到港船舶遵守該港的實際船期表，船舶在拖輪的輔助作業下通過主副航道所需時間分別為0.6、0.4 h，兩船之間的安全間隔時間為0.25 h，拖輪空駛通過航道的時間為0.15 h。小、中、大型拖輪單次作業費用為1 000、1 300、1 600元，空駛費用均為300元，不同船型與作業所需拖輪數量匹配情況如表1，周期內船舶進、出港作業順序安排情況已知。

表1 船型與拖輪匹配情況Table 1 Matching condition of ship type and tugboat

注：“—”表示不能匹配。

4.2 算例分析

筆者采用MATLAB編寫的遺傳算法程序，在I7-5700HQ CPU@2.70 GHz 64位的電腦上運行。為了測試遺傳算法效率，筆者選取了不同規模的數據進行實驗，算法程序運行效率良好且穩定。

通過優化算法計算研究周期內各種不同拖輪配置的耗油總成本，計算結果見表2。

表2 不同拖輪配置每天作業成本Table 2 Daily operation cost of different tugboat configuration

從表2中可看出：在船舶進出港作業中，配置6艘拖輪，拖輪作業總成本最小，如果只考慮港口作業成本，優先配置6艘拖輪。如果綜合考慮拖輪作業成本與港口作業的忙閑程度，需要考慮各種配置下拖輪的閑置率。將優化算法生成的各種配置下最優的拖輪配置方案和拖輪的調度方案輸入到已經建立的仿真模型中，通過仿真模型調用優化算法生成的最優解來計算各種拖輪配置下不同類型拖輪的閑置率，每種配置下各類型拖輪閑置率見表3。

表3 不同拖輪配置下各類型拖輪閑置率統計Table 3 Various tugboat idle rate with different tugboat configuration

由表3可知：從配置拖輪類型來看，小型拖輪的閑置率最高，大中型拖輪閑置率基本相同，表明小型拖輪數量充足，大中型拖輪需求基本相同；從配置拖輪數量來看，隨著拖輪數量的增加，拖輪的閑置率呈現上升趨勢，并且當配置6艘拖輪時，各種類型的拖輪閑置率較其他配置低，說明配備6艘拖輪大多數時候拖輪工作狀態較為忙碌，并且在實際仿真過程中，存在因拖輪數量不足引起的船舶在港等待造成延誤的情況，所以如果綜合考慮拖輪作業成本及港口作業忙閑程度，可考慮增加一艘拖輪。

4.3 拖輪閑置率影響參數分析

4.3.1 船舶數量變化

考慮貨物季節性和周期性變化引起船舶進出港數量變化，在成本最低的2/2/2配置下，周期內平均每天進出港船舶的數量分別增加和減少16%、33%，進行靈敏度分析，得出各種類型拖輪的閑置率的情況，見表4。

由表4可知，隨著船舶抵港數量的增加，各類型拖輪的閑置率都呈下降趨勢，可是在船舶數量增加的過程中，某種特定類型的拖輪閑置率變化不明顯，由于特定時刻拖輪數量不足，部分船舶在港口等待，當前仿真周期內沒有完成進出港作業，所以閑置率變化不明顯。從拖輪類型來看，中型拖輪的閑置率最低，考慮到進出港作業量的變化，可以考慮增加一艘中型拖輪。

表4 拖輪閑置率隨船舶數量變化情況Table 4 Tugboat idle rate changing with ship number

4.3.2 船舶類型變化

考慮未來船舶大型化趨勢，在成本最低的2/2/2配置下，繼續將進出港大型船舶的數量分別增加20%，40%，60%，根據計算得出數據分別繪制各種配置下的拖輪閑置率隨大型船舶數量變化的折線圖，如圖6。

圖6 拖輪閑置率變化情況
Fig.6 Variation of tugboat idle rate

由圖6可看出：隨著大型船舶數量的增加，大中型拖輪的閑置率下降，小型拖輪的閑置率反而上升，這是由于大型船舶不能由小型拖輪完成作業任務；中型拖輪的閑置率最低，波動性也較大，并且隨著大型船舶數量的增加，中型拖輪閑置率趨于相同，這是因為大型船舶作業主要使用中型拖輪，引起中型拖輪數量不足。由文中算例可知：每艘大型船舶使用中型拖輪比使用大型拖輪費用低600元，故從未來船舶大型化的角度，增加一艘中型拖輪，能夠更好地滿足需求。

綜上，從船舶數量變化以及船舶大型化的角度，兼顧拖輪的作業耗油總成本和閑置率兩項指標，并考慮港口作業的忙閑程度，優先增加一艘中型拖輪。

5 結 語

筆者從經濟效益的角度對復式航道港口拖輪配置問題進行研究，建立了嵌入拖輪調度優化方案的仿真模型，刻畫了復式航道下，拖輪配置同抵港船舶的種類、數量和拖輪作業調度方案的關聯關系，為相關問題提供了一個有效的解決思路。未來研究可以考慮航道跟泊位聯合調度問題。

[1] 黃泰坤，王元戰，李紹武，等.海港復式航道通過能力動態系統仿真[J].大連海事大學學報，2015，41(1)：20-26.

HUANG Taikun，WANG Yuanzhan，LI Shaowu，et al.Dynamic system simulation on throughput capacity of compound channel of sea port[J].JournalofDalianMaritimeUniversity，2015，41(1)：20-26.

[2] 唐國磊，王文淵，郭子堅，等.航道尺度對集裝箱碼頭泊位有效利用率的影響[J].哈爾濱工程大學學報，2016，37(1)：127-131.

TANG Guolei，WANG Wenyuan，GUO Zijian，et al.Impact analysis of channel dimensions on the effective utilization ratio of container terminal berths[J].JournalofHarbinEngineeringUniversity，2016，37(1)：127-131.

[3] 姬利娜，張金偉，亢鳳林.城市道路畸形交叉口的交通改善方法[J].重慶交通大學學報(自然科學版)，2012，31(6)：1185-1188.

JI Lina，ZHANG Jinwei，KANG Fenglin.Traffic improvement method of deformed intersection in urban road[J].JournalofChongqingJiaotongUniversity(NaturalScience)， 2012，31(6)：1185-1188.

[4] 王江濤，馬駟.預測通道客運分擔率的MNL模型特性變量選取[J].重慶交通大學學報(自然科學版)，2010，29(6)：947-950.

WANG Jiangtao，MA Si.MNL model characteristic variables selection on forecasting corridor mode split[J].JournalofChongqingJiaotongUniversity(NaturalScience)， 2010，29(6)：947-950.

[5] 陸海波.寧波港拖輪船隊優化配置研究[D].上海：上海海事大學，2007.

LU Haibo.StudyonOptimalAllocationofTugboatFleetinNingboHarbor[D].Shanghai：Shanghai Maritime University，2007.

[6] 劉志雄，王少梅.港口拖輪作業的計算機仿真研究[J].系統仿真學報，2004，16(1)：45-47.

LIU Zhixiong，WANG Shaomei.The computer simulation study of port tugboat operation[J].JournalofSystemSimulation，2004，16(1)：45-47.

[7] WANG Su，KAKU I，CHEN Guoyue，et al.Research on the modeling of tugboat assignment problem in container terminal[J].AdvancedMaterialsResearch，2012，433/440：1957-1961.

[8] 王巍，趙宏，李強.面向多停泊基地的港口拖輪調度優化研究[J].計算機工程與應用，2013，49(13)：8-12.

WANG Wei，ZHAO Hong，LI Qiang.Multi-objectives optimization for port tugboat scheduling considering multi-anchorage bases[J].ComputerEngineeringandApplication，2013，49 (13)：8-12.

[9] HE Tao，YE Wenwen.Research of tugboat operation scheduling problem based on hybrid evolutionary strategy[C]//2010 2ndInternationalConferenceonInformationScience&Engineering.U S A：IEEE，2010：1438-1441.

[10] WANG Su，ZHENG Kai，ZHENG Jun，et al.An improved discrete particle swarm optimization for tugboat scheduling problem in container terminal[J].InternationalConferenceonInformationManagement，2011，34(7)：573-579.

[11] 徐奇，李娜，靳志宏.考慮多階段共用平行機特征的拖輪作業模式優化[J].運籌與管理，2014，23(5)：178-186.

XU Qi，LI Na，JIN Zhihong.Optimization on tugboat operation mode considering characteristics of the multi-stage common parallel machines[J].OperationsResearchandManagementScience，2014，23(5)：178-186.

[12] XU Q，SHAO Q Q，JIN Z H.Optimization on tugboat operation scheduling based upon the hybrid flow shop arrangement[J].SystemEngineeringTheoryandPractice，2014，34(2)：485-493.

[13] YU Wenhui.Heuristic algorithm for simulation and optimization system of port tugboats allocation[C]//2011InternationalConferenceonInternetComputingandInformationServices.U.S.A：IEEE，2011：306-309.

[14] LIN Jiahong，GAO Benhe，ZHANG Canrong.Simulation-based investment planning for human port[J].SimulationModelingPracticeandTheory，2014，40(1)：161-175.

(責任編輯：劉 韜)

Simulation Optimization of Compound Channel Port Tugboat Configuration

ZHENG Hongxing，XU Haidong，CAO Honglei

(Transportation Management College，Dalian Maritime University，Dalian 116026，Liaoning，P.R.China)

In order to better guide the compound channel tugboat configuration，a tugboat operation simulation model was put forward.Firstly，based on the characteristics of compound channel，the Arena simulation model was proposed，which embedded operation scheduling optimization model，with the aim of minimizing the total tugboat fuel consumption cost.Secondly，the embedded heuristic rules genetic algorithm was designed to solve the proposed model.Thirdly，through various simulation tests，the present optimal configuration scheme was selected，considering total tugboat fuel cost and tugboat idle rate.Then，through the simulation analysis on the tugboat idle rate changing with ship types and ship numbers as well as the combination with large scale trend of ship in the future，the future optimal tugboat configuration scheme was given.

waterway engineering；compound channel；tugboat configuration；genetic algorithm；tugboat idle rate

10.3969/j.issn.1674-0696.2017.08.18

2016-05-02；

2016-09-16

國家自然科學基金項目(71473024)

鄭紅星(1971—)，男，河北遷安人，副教授，博士，主要從事物流系統及仿真方面的研究。E-mail：zhredstar@dlmu.edu.cn。

徐海棟(1991—)，男，山東濰坊人，碩士研究生，主要從事物流系統及仿真方面的研究。E-mail：1835351671@qq.com。

U692.4

A

1674-0696(2017)08-102-08