港口集裝箱碼頭泊位與岸橋的多階段協作調度仿真研究

馮小歐， 楊 瑾， 袁培燕

（1.鄭州旅游職業學院，鄭州 451464；2.河南師范大學計算機與信息工程學院，河南 新鄉 453007）

0 引言

隨著國際貿易的快速發展和大規模大噸位集裝箱貨柜船舶的發展趨勢，集裝箱碼頭的高效運營正面臨巨大的挑戰。集裝箱船舶及其裝卸設備也正在向著高速重負荷方向發展，這要求調度計劃和集裝箱碼頭作業不僅需要滿足船舶的裝卸工作任務要求，還要降低碼頭的作業代價和投資。集裝箱碼頭的主要作業空間涉及兩類主要資源：泊位和岸橋。泊位和岸橋是集裝箱碼頭的稀缺資源，泊位分配和岸橋調度對于提高集裝箱碼頭的運作效率至關重要。泊位分配是指為到港船舶安排靠泊位置和靠泊、離港時間，并最小化船舶在港時間。船舶等待靠泊時間最短、在港裝卸作業時間最短、靠泊成本最低以及客戶滿意度最高為當今泊位分配的主要研究目標。依據碼頭作業時泊位分布方式的不同，可分為離散型泊位和連續型泊位。根據文獻［1］中的表述，離散型泊位是將碼頭分割成一定數量的部分，每一部分即為一個泊位，在每一個時間點每一個泊位上只能停靠一艘船舶。而連續型泊位分布，碼頭沒有被分割，在滿足船舶長度的情況下船舶可停靠在碼頭邊界的任意位置。連續型泊位相對離散型泊位能更好地利用空間，但連續型泊位分配較復雜。岸橋是集裝箱碼頭重要的裝卸資源，岸橋調度所要解決的是在給船舶分配好泊位后，根據到港船舶集裝箱裝卸任務量以及船舶離港時間等約束為船舶分配可用的岸橋。岸橋價格昂貴，如何減少岸橋的閑置時間，提高岸橋的利用率是集裝箱碼頭取得競爭優勢的關鍵。

泊位與岸橋協調調度比單獨調度能更有效提高集裝箱碼頭的裝卸效率，減少船舶在港時間。圖1 給出了泊位與岸橋單獨調度和協調調度的作業流程。由于船舶停靠的泊位和泊位附近的岸橋工作狀態不同，導致船舶的服務時間不同。泊位決策影響岸橋分配決策，從而影響船舶在港時間。協調調度在泊位調度時不僅要考慮泊位空閑情況，也要考慮該泊位可用岸橋的狀態，計算停泊泊位岸橋的裝卸時間，選擇使船舶在港時間最短的泊位停靠。單獨調度則將兩個調度流程分開，先為船舶選擇最短泊位停靠等待時間，停靠后再分配可用岸橋，后者忽視了岸橋分配對船舶在港時間的影響，造成后續船舶的等待，具有一定的局限性。協調調度避免了單獨調度的局限性，可有效減少船舶總在港時間，并提高岸橋的裝卸效率。

1 泊位與岸橋調度方式

為解決泊位和岸橋兩類資源的調度，很多學者進行了研究。集裝箱碼頭的泊位和岸橋分配的單獨調度研究如文獻［1-4］。基于靜態調度和離散泊位調度的相關研究，文獻［5］中提出一種動態調度方法，建立一種混合整數規劃模型，其目標是最短化船舶的在港時間。文獻［6］中提出連續泊位概念，此時泊位被視為連續空間，以最大化泊位的利用率。此外還將泊位轉換為二維漸縮進行分析，結果表明，泊位調度是NPhard問題。為解決連續泊位分配，文獻［7］中將要求的離港時間和在非最優泊位上的額外處理代價的總附加代價設置為最優化目標，并通過模擬退火算法時進行求解。基于以上的工作，文獻［8］中通過分支界限法和自適應貪婪算法進行求解。文獻［9］中提出一種多重任務調度模型，目標則是最短化最近船舶的離港時間，并提出一種啟發式算法。類似內容還出現在文獻［10］中。

為提高資源利用率，文獻［11］中引入岸橋生產率到泊位和岸橋分配的協作調度。為最短化處理時間、等待時間和延時時間的總和，文獻［12］中提出一種混合遺傳算法對以上協作調度進行求解。由于碼頭工作的復雜性，連接泊位和岸橋分配的協作調度仍然缺乏有效的調度機制。文獻［13］中為最短化船舶在港時間，提出免疫遺傳算法的協作調度算法。文獻［14］中將協作調度的優化目標設為最小化船舶在港時間和岸橋移動次數，提出泊位分配子模型和岸橋分配子模型的耦合模型，并采取一種嵌套循環進行算法進行求解。基于連接泊位的可分割性，本文提出一種最優化調度模型，模型利用多階段啟發式調度算法和粒子群優化算法（Particle Swarn Optimization，PSO）可有效處理在集裝箱船舶動態調度中的協作調度。算法目標是決定船舶的泊位和泊位順序以及岸橋的使用數量，以最小化優于非最優泊位帶來的額外代價和停港延時的懲罰代價之和。

2 模型描述

船舶到港后的作業過程主要包括：船舶到港、分配靠泊位置（泊位）、分配岸橋、集裝箱裝卸以及船舶離港。為最短化船舶的總在港時間，碼頭管理者會根據到港船舶的相關信息以及碼頭裝卸的優化策略，將最優的靠泊位置以及可用的岸橋分配給船舶裝卸集裝箱。

由文獻［8］中可知，碼頭作業中，對于船舶而言有一個最優泊位，其裝卸工作代價是最小的，（如鄰近倉庫位置，此時運輸成本可以最小化）。對于泊位調度來說，船舶均想要優先選擇這些泊位，若這些泊位不可用才考慮在次最優位置進行泊位。裝卸作業時間取決于分配的岸橋數量。為確保船舶的離港時間和不必要的設備消耗，應該分理、正確配合岸橋數給船舶。因為岸橋數本身的限制，并不是所有船舶都能得到充足的岸橋數，盡量當船舶離港時，空閑岸橋需要重新分配給在港船舶，同時滿足船舶對于岸橋的最大持有數，以便降低船舶的停留停港時間和延期帶來的懲罰成本。

基于以上的分析，可通過離散化方法將連續泊位劃分為一組序列組成的多個泊位，如圖2 所示。船舶的最優泊位標識為分割后的序號，每個船舶可占用多個泊位段，但不能超過碼頭長度。同時，船舶的停靠位置可由船舶占用的泊位段進行標識。

模型相關符號說明

Q：岸橋數量集合｛1，2，…，q｝；

S：裝載集裝箱的船舶數量集合，S＝｛1，2，…，s｝；

L：泊位碼頭長度；

A：連續泊位分割量；

B：單個泊位的長度集｛1，2，…，L／A｝；

TEU：航線運輸的集裝箱標準箱；

M：岸橋效率，單位：TEU／h；

NCi：船舶i需要的最大岸橋數；

li：船舶i的長度；

Ci：港內船舶i的集裝箱總量；

tpi：船舶i要求的離港時間；

tai：船舶i的到達時間；

bpi：船舶i的最優泊位，以bi表示；

Nhi：船舶i最右邊的岸橋ID；

Nei：船舶i最左邊的岸橋ID；

rpi：船舶i的實際泊位；

tbi：船舶i的泊位時間；

tdi：船舶i的實際離港時間；

WB：等待泊位的船舶集；

BW：作業過程中的船舶集；

OTS：延期船舶集；

addCranei：船舶i按時完成任務需要的額外岸橋數；

headCranei：處于泊位rpi左邊的岸橋集；

endCranei：處于泊位rpi右邊的岸橋集；

Ni：船舶i按時完成任務需要的岸橋數；

CSj：如果岸橋j正在作業，則CSj＝1，否則CSj＝0；

BSl：如果泊位段l正在作業，則BCl＝1，否則BSl＝0；

QCi：船舶i工作的岸橋集；

LCi：船舶i工作時的泊位集；

TLi：船舶i的左邊集裝箱數量；

tfi：船舶i的估計作業時間；

tyi：船舶i的估計離港時間；

nci：船舶i工作時的岸橋數；

wi：船舶i在港口中的等待時間；

thi：船舶i的作業持續時間。

船舶的操作時間主要由集裝箱貨柜車的運輸時間和操作的岸橋數決定。船舶的停靠位置（泊位）可表示為運輸時間。岸橋數量主要取決于要求的離港時間。本文應用文獻［8］中提出的模型來求解這個調度問題。不同的是，兩階段的岸橋分配在泊位時進行了考慮。

式中：c1i為船舶在非最優泊位上的額外成本，cli為船舶i的單位額外成本；c2i（tdi-tpi）為船舶延期帶來的懲罰成本；c2i為船舶i的單位懲罰成本。

3 多階段協作調度

多階段協作調度包括船舶泊位分配和岸橋分配，岸橋分配又劃分為泊位時岸橋分配和離港后岸橋分配。

3.1 泊位分配算法

當船舶靠港時一般會選擇最優泊位，即：船舶抵達港口后，首先檢查最優泊位是否空閑，若空閑，則靠港泊位；若泊位已被占用，船舶選擇次最優泊位；如果所有泊位均無法使用，船舶將被推遲進港，等待在錨泊區域。對已經泊位的船舶，離其最近的岸橋按船舶離港時間、處理集裝箱數量和最大岸橋數量予以分配。泊位分配算法（Berth Allocation，BA）流程如圖3 所示。

3.2 岸橋調度算法

岸橋分配發生在船舶泊位和離港期間。考慮下一船舶到達對其的影響，如果下一到達船舶的最優泊位處于當前船舶的左邊，則其右邊的岸橋被優先分配給當前船舶。否則，左邊岸橋。岸橋分配分2 個階段。

（1）泊位時的岸橋分配算法。泊位階段，分配給船舶的岸橋主要考慮rpi和bpi+1。以bpi+1＞rpi為例，設置rpi為基線，考慮岸橋狀態和非交叉約束，添加處于基線左邊的岸橋到headCrane；其他添加到endCrane。根據船舶需求的岸橋數量，優先分配在headCrane 且與船舶最近的岸橋給船舶。如果headCranes的岸橋量不足，則選擇就近的岸橋加入工作組，且為船舶i工作的岸橋量不能超過NCi。泊位岸橋分配算法QA_B流程如圖4 所示。

圖4 泊位時岸橋分配算法

（2）離港后的岸橋分配算法。待船舶完成任務離開港口后，岸橋此時變成空閑資源。同時，可能有些船舶無法按時離港，所以這些空閑岸橋需要在這些逾期船舶中重新分配。不同于泊位時的分配，船舶離港后的岸橋分配需滿足最小化延時處罰代價的需求。離港岸橋分配算法QA_D流程如圖5 所示。

圖5 離港時岸橋分配算法

基于BA、QA_B和QA_D3 種算法，本文提出一種多階段協作式泊位與岸橋調度算法，步驟如下。

步驟1初始化船舶信息，包括：船舶到達時間、要求離港時間、優先泊位、集裝箱長度和數量，獲取港口泊位序列。

步驟2選取泊位序列中的泊位i。基于BA、QA_B和QA_D算法為船舶i分配泊位。時間窗口移至tai。

步驟3從BW中選取最早離港船舶j。如果tdj＞tai+1（i+1∈sequence），返回步驟2；否則，轉步驟4，且j ＝0。

步驟4選取當前離港船舶j，時間窗口移至tdj并釋放QCjand LCj。

步驟5檢查BW 中是否有船舶超時。如有，添加至OTS，k＝0；否則，轉步驟8。

步驟6選取OTS中的船舶k，基于QA_B和QA_D算法分配岸橋，并更新tyk。

步驟7檢查OTS中是否所有船舶已經處理或所有空閑岸橋已經分配給船舶。如是，轉步驟8，w＝0，否則，k＝k+1，轉步驟6。

步驟8選取WB 中的船舶w作為目標船舶，并基于BA算法為其分配泊位。

步驟9檢查WB中是否所有船舶已經處理。如不是，w＝w+1，轉步驟8，否則，轉步驟10。

步驟10如tdj+1＜tai+1，時間窗口移至tdj+1，j＝j+1，轉步驟4，否則轉步驟11。

步驟11如所有船舶完成作業，停止仿真并輸出結果，否則，i＝i+1，轉步驟2。

3.3 模型表示與調度框架

為便于求解調度方案，以粒子群算法PSO 對泊位和岸橋分配進行編、解碼。粒子群算法是一種受鳥群活動啟發的群體智能技術［16］，其核心是通過協作和粒子間的信息共享尋找最優或次優解。本文利用一種二維數組記錄粒子位置的基礎信息及其次序，見表1。第一維是粒子的位置信息，第二維表示數據的次序。PSO更新粒子的位置信息后，粒子次序同步進行計算更新。

表1 粒子位置的二維數組

根據xi的值，可以得到每個si的值。以縱向序列表示船舶的標識號ID，si的次序可映射為船舶的泊位次序。如表2 所示，數組表示10 個船舶的次序。通過以上的編碼方法，表2 中的服務序列可表示成表3。

表2 問題編碼

表3 服務序列解碼

基于以上分配算法和粒子群算法，設計了一種實現岸橋和泊位優化分配調度框架模型，如圖6 所示。模型主要包括調度算法、分析和優化等模塊，其中，調度算法模塊負責實現侯選調度計劃和輸出統計結果，分析模塊負責轉換編碼信息為可用信息并傳送到調度算法模塊，同時接收調度算法模塊的數據，優化模塊負責通過粒子群算法實現主要調度方案的產生，并更新粒子群和選擇優化結果。

圖6 泊位與岸橋多階段協作調度框架

個體初始化通過粒子群算法形成，并作為候選方案，見表2。解碼操作之后，通過調度算法模塊將每個個體解析為可用信息。分析模塊轉換解析數據至調度算法模塊以模擬集裝箱碼頭的作業過程。通過這個仿真框架，計算出侯選方案的結果，并將結果傳送到優化模塊，并從中選擇最優解。如運行滿足停止條件，就輸出最優解。否則，實施更新操作，更新個體信息進行下一次迭代。通過該模型，能實現協作式調度的仿真和最優化。

4 算例分析

基于文獻［8］，建立測試案例對算法進行驗證，采用Matlab R2009a平臺并結合圖6 所示的調度框架編寫算法仿真程序。設置碼頭長度為1500 m，在一次調度周期內，假設8 艘集裝箱船舶依次抵達港口，船舶的基本數據選取長江上游某大型港口的部分統計數據設計算例，見表4。對于船舶1 ～6 每小時懲罰代價和每米額外處理代價設為5000 ＄／h和400 ＄／m。船舶7～8 設為3000 ＄／h 和200 ＄／m。假設現有12 個岸橋部署在泊位附近，岸橋的生產率為40 TEU／h。泊位船舶間的安全距離設為30 m。測試中，選取先來先服務調度算法（First Come First Serve，FCFS）作為比較算法進行性能比較。

表4 船舶參數設置

FCFS算法中，船舶按時間優先級進行泊位。最早到達的船舶將優先進行泊位，其目標是最短化船舶的總等待時間。調度計劃見表5，其中，Tg為要求的離港時間與實際離港時間的差值，Pg為首選泊位與實際泊位的差值。船舶在港的總時間為86 h，總處理時間為86 h。所以船舶無須等待即可泊位。

表5 FCFS算法結果

本文算法中，船舶的泊位順序由粒子群算法決定，其結果見表6。可見，船舶在港時間總和為105 h，工作時間為85 h，等待時間為20 h。

表6 本文算法結果

算法比較見表7，表中，TI 為船舶總在港時間，TP為總處理時間，TW為總等待時間，D為懲罰代價，P為泊位附加代價。顯見，FCFS算法可以降低船舶的等待時間，但由于泊位不在最優（首選）位置，附加代價成為泊位代價的主要部分。通過協作調度優化可滿足大部分船舶對首選泊位的需求，并通過岸橋分配算法也能確保大部分船舶能按計劃完成處理任務。比較第1種算法，本文算法的目標代價顯然更加經濟。

表7 兩種算法比較

本文比較了2 種算法獲得最終解所需時間和得到相同解時所需時間，該時間也反映了算法本身的收斂性。如圖7 所示，當求解問題規模增大時，2 種算法求解最終解所需要的時間是遞增的，本文算法略高于FCFS算法，這是由于本文算法在每次迭代求解時均需對泊位分配和岸橋調度進行優化，以降低總代價，計算量大于FCFS算法。可見，若本文算法得到與FCFS相同的解即停止運算，該時間則略低于FCFS 得到相應解的求解時間。綜上，本文算法為最小化總體代價，其運行效率在調度規模增大時仍然是可以接受的。

圖7 3種算法求解效率

5 結語

為解決集裝箱碼頭連續泊位和岸橋的協作調度分配，提出一種結合啟發式算法和粒子群算法的優化模型。通過將碼頭劃分為多個倚靠單元，船舶的倚靠位置和岸橋可以表示成單元序列。在泊位階段，通過BA算法將單元序列分配給船舶。考慮到碼頭作業的多階段性，提出QA_B 和QA_D 算法進行岸橋分配。結果表明，盡管延時代價更高，且最終解的求解時間略長，但本文算法的的總代價低于FCFS 算法，這表明模型對于泊位和岸橋的協作調度分配是可行有效的。