船舶進出港協(xié)調調度研究

許長彬 金群昊 余海瑞 任海英

摘 要：船舶滯港、壓港問題是制約港口服務的瓶頸所在，船舶進出港調度是解決港口擁堵的有效方法，其核心就是泊位和航道資源的優(yōu)化配置。迄今，在船舶進出港調度方法研究上已取得一定成果，其主要涉及調度過程的優(yōu)化模型和算法研究。本文在分析和對比國內外相關研究成果的基礎上，主要針對協(xié)調航道和泊位的船舶進出港調度優(yōu)化問題，論述了研究背景、研究意義和研究現狀。

關鍵詞：船舶;協(xié)調調度;建模;優(yōu)化;綜述

錨地、航道和泊位構成了港口資源的基本要素，其中航道和泊位資源的優(yōu)化配置與港口服務水平的提升息息相關。隨著海運運量的不斷上升以及船舶向大型化、高速化的方向發(fā)展，加之港口調度方案的不合理，從而出現了大量的船舶壓港、滯港現象。

解決港口擁堵問題可以從增加港口規(guī)模和優(yōu)化船舶調度方案入手。增加港口規(guī)模的方法包括擴建泊位和拓寬航道等，但需要大量的資金，而且周期長。優(yōu)化船舶進出港調度方案是最為有效的措施。目前，關于港口船舶調度的研究側重于航道調度和泊位分配的單一方面，而對二者的協(xié)調調度研究較少。

船舶進出港協(xié)調調度研究主要集中在提高船舶進出航道的效率和泊位資源調度優(yōu)化方面，為復雜的組合優(yōu)化問題。在滿足航行實際和現有資源（航道、拖輪、引航員、泊位、操作人員等其他關鍵資源）等相關約束條件下，通過確定各船舶的進出港時間、進出港次序，使船舶總等待時間和總調度時間等指標達到最優(yōu)或較優(yōu)，實現調度過程優(yōu)化對縮短航次周期、提高船舶準點率、降低船舶運營成本和港口資源消耗，提高經濟效益和市場競爭力等方面有重要作用。

本文對船舶協(xié)調調度及相關領域調度的模型和算法進行了綜述，剖析現有模型與算法，并對未來的研究方向進行了展望。

1港口船舶調度研究

1.1傳統(tǒng)的VTS調度方法：

傳統(tǒng)的船舶進出港調度以先到先服務（FCFS）的模式為基礎。對于進港船舶，一般情況下，需要提前24小時向目的港（或掛靠港）的VTS中心發(fā)送進出港計劃，如果航程不足24小時，應該在駛離上一港前報告。在抵達報告線時發(fā)送抵港報告，VTS中心根據船舶屬性、航道狀況和泊位狀況審核該船的調度安排，符合進港條件，會安排船舶進入航道并進行靠泊作業(yè);如果沒有通過審核或者沒有調度安排，一般會被安排到錨地等待。船方會安排代理向碼頭企業(yè)申請調度，向引航站申請引航。碼頭企業(yè)安排調度，并向中心申請審核，審核通過后通知船舶，船舶在規(guī)定時間內完成靠離泊作業(yè)。船舶完成轉卸貨作業(yè)后，向中心申請離港。如果符合出港條件，船舶在拖輪和引航員的協(xié)助下離港;若與其他船舶沖突，中心一般會讓船舶在碼頭等候，直到符合條件才會安排船舶出港。船舶出報告線后，發(fā)送離港報告，在該港口的進出港作業(yè)完畢。對于雙向通航的港口，VTS中心還會考慮到船舶屬性（噸位、船長和裝載貨物類型等）確定是單向通航還是雙向通航。

目前船舶調度主要仍憑人工經驗完成，缺乏定量化決策模型和有效的調度計劃衡量指標，而且調度目標單一，缺乏平衡多目標的能力，嚴重制約了港口的運作效率和船舶調度效率 的提高，因此迫切需要研究港口船舶調度的優(yōu)化方法。

1.2近年來對船舶進出港調度方案的研究進展

對于單向航道。徐國裕等[1-2]對單向航道進出港船舶的順序安排進行了研究。對船載AIS 提供的與單向水道船舶通行有關的信息數據進行分析，提煉出影響船舶調度順序的主因素和子因素， 賦予相關的權重值，得出以船舶權重為準的排序模式。宋巖[3]認為船舶調度過程是一個離散的、動態(tài)的隨機過程，把處理多目標條件下調度計劃優(yōu)化作為重點，以船舶總在港時間和泊位利用率為目標建立模型，并用遺傳算法求解，在求解過程中通過對多目標進行權重偏好變換，轉化為單目標的優(yōu)化問題。陳卓歐[4]注意到航道內船舶追越和加減速的情況，以船舶追越次數和加減速次數衡量航道通航風險，以船舶等待時間和單位時間船舶通過數量衡量通航效率，建立相應模型。Lin等[5]針對單向航道的船舶調度問題，優(yōu)先考慮等待時間長和優(yōu)先級高的船舶，提出以調整后總的船舶等待時間最小的調度模型，保證船舶調度過程的公平性。

在雙向航道研究方面，林俊[6]分析了雙向通航港口調度機理，考慮到通航模式影響因素，依據單雙向通航轉換特性建立模式轉換約束，考慮船舶在港作業(yè)的連續(xù)性，建立了連續(xù)性約束，通過空間到時間的轉換，以調度開始時刻為切入點建立了安全性約束。設計雙向通航調度多目標遺傳算法，算法設計了三層染色體編碼解碼方法，加入等待時間期望評價的適應度函數，精英保留策略，基于序值和擁擠距離的并列選擇算子，部分映射交叉算子，兩點變異算子以及染色體修復算子。鄭娟[7]重點關注了雙向通航港口Y型航道的船舶交通組織狀況，運用離散事件系統(tǒng)仿真的方法，建立了船舶航行作業(yè)系統(tǒng)仿真模型，針對不同通航歷時、不同潮差、不同規(guī)模的港區(qū)進行了仿真試驗，得出航道交匯水域船舶不同交通組織規(guī)則對航道通過能力、船舶平均等待時間、船舶等待延時均值的影響規(guī)律，并選取船舶速度、船舶安全間距、航道交匯水域通航歷時三個船舶航行參數進行敏感性分析。

以上相關的船舶調度只針對單一的航道進行，而港口船舶調度是一個連續(xù)的、多因素影響的過程，應該協(xié)調航道與泊位資源，解決船舶在港作業(yè)時航道、泊位使用沖突。

王金濤[8]受空中交通流調度領域協(xié)同決策的思想的啟發(fā)，建立了協(xié)同港方和船方利益的多目標函數。Zhang等[9]對調度的開始階段建立初始化模型，進出港交通流方向切換的流量轉換模型，建立時隙分配模型實現了對同向連續(xù)船舶的控制。相較于一般的船舶進出港調度，協(xié)調調度模型覆蓋了調度過程的更多方面。協(xié)調調度模型加入了進港船舶泊位停靠先后次序算子、泊位狀態(tài)算子和泊位沖突消解算子，同時考慮到由于泊位的先后次序需要增加的安全時間間隔。林俊[5]在雙向航道調度模型的研究中，考慮到雙向航道單向通航和雙向通航條件轉換的特點，設計了單向通航、雙向通航模式相互轉換的約束條件以及雙向通航時正橫間距安全約束。

在算法設計方面，遺傳算法比傳統(tǒng)的優(yōu)化算法具有良好的并行計算能力，有較好的擴容性和魯棒性，在多目標優(yōu)化方面得到廣泛利用。王金濤[7]、張新宇等[10]根據解空間的目標函數設計了適應度函數，針對遺傳算法的特點，將解空間的初始化約束條件轉化為適應度函數的懲罰項，時隙分配和流量轉換融入到編碼解碼方法中，然后設計基于染色體序值和擁擠距離的選擇算子和精英策略，并設計動態(tài)多點交叉算子、對稱基因位變異算子、隨機修復策略。林俊[5]考慮到雙向航道的特點，設計了三層染色體的編解碼方法，為了照顧模型的公平性，在適應度函數設計中加入了等待時間期望評價。遺傳算法存在容易陷人局部最優(yōu)及后期收斂較慢的問題，為了解決這個問題，張新宇等[11]采用多種群遺傳算法并加入退火機制，憑借其前期搜索空間大、退火溫度高、適應度值的變化范圍廣的特點，保證了算法不會陷人局部最優(yōu)的情況;算法前期隨著溫度不斷下降，搜索空間會急劇縮小，算法后期可發(fā)揮遺傳算法局部搜索的能力，進而保證了最終結果收斂到最優(yōu)解的區(qū)間。除了遺傳算法之外，Chen等[12]嘗試了基于粒子位置的離散粒子群算法（DPSO）求解調度序列，DPSO較GA有著搜索速度快、效率高和算法簡單的優(yōu)點，但是容易陷入局部最優(yōu)。

船舶進出港協(xié)調調度模型和求解算法的研究還不完善，其他相關領域的學者在多目標優(yōu)化建模、求解方面已取得一定成果。

2運河船舶排閘算法研究（多目標優(yōu)化）

我國內河諸多重要通航樞紐建有船閘，隨著通航樞紐擁堵狀況的不斷惡化，水路交通研究領域的學者對于船舶排閘問題給予了充分關注。胡適軍等[13]把船舶排閘問題看做組合優(yōu)化中的二維填充問題，綜合了快速排閘算法和寬度優(yōu)先排閘算法，利用快速排閘算法對遺傳算法進行改造，提出了遺傳優(yōu)化排閘算法。建立了船閘調度模型、船舶交通流量模型、閘室排擋模型，并且以閘室利用率和船舶待閘時間為評價指標來評價算法對提高船閘運行效率的作用。劉云峰等[14]分析了三峽永久船閘的編排問題，將其概括為一個NP-完全的多目標規(guī)劃問題，以搜索最優(yōu)閘室組合的二叉樹為基礎，設計出DPS算法。王小平等[15]將三峽葛洲壩看做一個有機的整體，建立了兩壩聯合調度的數學模型，設計了基于簡化的串聯排隊系統(tǒng)的船舶編排算法。肖恒輝等[16]從現場調度的角度出發(fā)，提出了閘外編排的概念，以排擋圖為依據，采用長度優(yōu)先、先大后小的排擋策略，建立了閘外編排的數學模型，并根據模型的目標函數和約束生成了相應的閘外編排算法。

以上關于運河船舶過閘調度的研究都是多目標多約束的NP-Hard問題，排閘問題的建模過程和算法求解過程，以及聯合調度思想，為港口船舶協(xié)調調度提供了啟發(fā)和參考。

3海峽（運河）船舶調度

在海峽船舶調度方面，伊斯坦布爾海峽是連通地中海和黑海的交通要道，交通流密度很大，交通情況復雜。為了提高南向船舶和北向船舶的通過效率，?zgecan等[17]提出了船舶調度算法，算法的基本理論是優(yōu)先調度等待時間長的船舶，同時給大型危險品船以較高的優(yōu)先級，采用多種排隊方法的比較分析出通過狹水道的最佳方案。把這種方法的運用擴展到雙向航道單向通航調度優(yōu)化的算法之中。在運河調度優(yōu)化方面，甘勇等[18]為了解決三峽-葛洲壩聯合調度下船舶過閘優(yōu)先級的問題，提出了船舶流排序算法模型，基于船舶相關的靜態(tài)屬性和動態(tài)屬性，運用模糊綜合評價法計算出靜態(tài)權重，根據不滿意問題的數學描述和排隊論，得出計算動態(tài)權重的指數函數，最后根據權重值得高低確定編排的原則。

4空中交通領域飛機進離場優(yōu)化問題研究

與本文相關的空中交通領域關于飛機進離場優(yōu)化研究較多，陳世林等[19]針對機場交通擁擠的問題，基于協(xié)同決策（CDM）理論，提出了進離場流量轉換的協(xié)同決策模型和算法，并采用動態(tài)規(guī)劃法求解。協(xié)同決策思想于上世紀末由美國聯邦航空局提出，提高了交通流量管理（TFM）效率。隨后協(xié)同決策被應用于地面等待中，在地面等待的研究中時隙分配問題被深入研究，徐肖豪等[20]論述了時隙分配的概念、屬性、模型和求解算法，以此為基礎總結出時隙分配的關鍵問題及模型和算法研究，指出了時隙分配問題的研究方向。嚴俊等[21]對航班波運行模式下的地面等待策略，提出了時隙交換策略。借鑒上述協(xié)同決策、流量轉換、時隙分配等思想，可用來分析港口船舶調度優(yōu)化問題。

5生產過程調度問題模型和算法研究

生產過程調度是自動化、工業(yè)工程和管理工程等領域的重點研究方向。對于具有大規(guī)模、帶復雜約束、不確定等綜合復雜性的實際生產調度問題，傳統(tǒng)的調度模型和優(yōu)化算法已難以建立相關調度模型和取得理想的調度結果。針對上述問題，劉民等[22]采用基于數據的調度過程建模方法，提出了精確模型和特征模型相結合的建模方法?；谟唵巍C器、計劃等歷史數據、實時數據和仿真數據。采用數據挖掘和預測方法提出了基于數據的調度模型。Li等[23]針對柔性制造系統(tǒng)， 基于生產過程調度相關歷史數據和仿真數據提取少量數據對，并采用整體模糊化和數據趨勢預測方法生成大量用于獲取啟發(fā)式調度規(guī)則選擇策略的訓練數據對，應用ANFIS或BP神經網絡進行調度規(guī)則的挖掘.

隨著AIS等技術的不斷發(fā)展和應用，港口部門已積累了與調度相關的大量歷史數據，并可采集到與調度相關的大量實時數據，這些數據反映出大量實際調度環(huán)境特點及調度知識。借鑒生產過程調度領域基于數據的建模方法和數據處理方法，有助于改進傳統(tǒng)的船舶調度建模方法和優(yōu)化算法。

6總結

船舶進出港調度是水路交通領域的重點研究方向。為了促進基于協(xié)調調度的船舶進出港優(yōu)化方法研究進一步發(fā)展，本文在對傳統(tǒng)調度方法介紹的基礎上，重點介紹了船舶進出港協(xié)調調度及相關領域的建模和求解方法。同時，目前的船舶調度問題建模方法在進行建模時對實際復雜環(huán)境的進行了簡化，并且附加了較多的約束條件，如不考慮引航員和拖輪的調度、航道水深已滿足進出港要求、港口錨地容量無限大、船舶港內航行速度用平均速度代替等。所以，單純的采用傳統(tǒng)建模方法所建立的模型與實際情況有一定的差距。因此，如何解決傳統(tǒng)方法的弊端是研究的一大趨勢。

參考文獻：

[1]徐國裕，劉人杰，吳兆麟.單向水道船舶進出港排序權重分析[C]// 2008-2009年船舶通信導航論文集.

[2]徐國裕，郭涂城，吳兆麟.單向水道船舶進出港最佳排序模式[J].大連海事大學學報， 2008， 34（4）：150-153.

[3]宋巖，黃磊，胡偉.遺傳算法在港口船舶調度領域中的應用[J].中國水運月刊， 2009， 9（9）：76-77.

[4]陳卓歐.天津港進港主航道船舶交通組織調度建模研究[J].中國海事， 2015（5）：46-49.

[5]Lin J， Zhang X Y， Yin Y， et al. Optimization of Ship Scheduling Based on One-Way Fairway[J]. Lecture Notes in Computer Science， 2014， 8631：3-2014.

[6]林俊.雙向通航情況下港口船舶調度優(yōu)化[D].大連海事大學，2015.

[7]鄭娟.航道交匯水域船舶交通組織的影響分析[D].大連理工大學， 2011.

[8]Zhang X， Lin J， Guo Z， et al. Vessel transportation scheduling optimization based on channel–berth coordination[J]. Ocean Engineering， 2016， 112：145-152.

[9]張新宇，郭子堅，王金濤，等.基于航道與泊位資源協(xié)調調度的船舶交通優(yōu)化[J].中國航海， 2015， 38（3）：33-36.

[10]張新宇，林俊，郭子堅，等.基于模擬退火多種群遺傳算法的港口船舶調度優(yōu)化[J].中國航海， 2016， 39（1）：26-30.

[11] Chen X， Zhang X Y， Liu T S， Lin J， et al. The Vessel Schedule Optimization Based on Particle Swarm Optimization Algorithm[C].

[12]胡適軍，周春輝，文元橋，等. 船舶排閘的遺傳算法設計與仿真[J].中國航海， 2015， 38（2）：38-42.

[13]劉云峰，齊歡. DFS算法在三峽永久船閘優(yōu)化編排中的應用[J].計算機工程， 2002， 28（8）：224-226.

[14]王小平，齊歡，肖恒輝，等. 基于串聯排隊網絡的三峽-葛洲壩水利樞紐聯合調度模型[J].交通運輸工程學報， 2006， 6（3）：82-86.

[15]肖恒輝，齊歡，王小平，等. 船舶調度閘外編排算法[J].交通運輸工程學報， 2007， 7（1）：26-29.

[16]?zgecan S. Ulus?u， ?zba? B， Alt?ok T， et al. Transit Vessel Scheduling in the Strait of Istanbul[J]. Journal of Navigation， 2009， 62（1）：59-77.

[17]甘勇，齊歡，肖恒輝. 三峽-葛洲壩聯合調度下的船舶調度優(yōu)先級算法[J].交通信息與安全， 2006， 24（6）：128-131.

[18]陳世林，胡明華，張洪海. 基于進離場容量轉換的協(xié)同決策系統(tǒng)[J].系統(tǒng)管理學報， 2008， 17（5）：586-590.

[19]徐肖豪，王飛.地面等待策略中的時隙分配模型與算法研究[J].航空學報， 2010， 31（10）：1993-2003.

[20]嚴俊，吳桐水，高強，等.航空公司合作博弈下的時隙交換模型[J].交通運輸工程學報， 2012， 12（5）.

[21]劉民.國家973計劃項目課題 “復雜生產制造過程實時智能優(yōu)化調度理論與算法研究” 總結報告， 清華大學， 2008.

[22]Li D C， Wu C S， Tsai T I， et al. Using mega-fuzzification and data trend estimation in small data set learning for early FMS scheduling knowledge[J]. Computers & Operations Research， 2006， 33（6）：1857-1869.