港口集裝箱碼頭泊位與岸橋的多階段協(xié)作調(diào)度仿真研究

馮小歐， 楊 瑾， 袁培燕

（1.鄭州旅游職業(yè)學(xué)院，鄭州 451464；2.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007）

0 引言

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

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

1 泊位與岸橋調(diào)度方式

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

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

2 模型描述

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

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

基于以上的分析，可通過離散化方法將連續(xù)泊位劃分為一組序列組成的多個(gè)泊位，如圖2 所示。船舶的最優(yōu)泊位標(biāo)識(shí)為分割后的序號(hào)，每個(gè)船舶可占用多個(gè)泊位段，但不能超過碼頭長度。同時(shí)，船舶的停靠位置可由船舶占用的泊位段進(jìn)行標(biāo)識(shí)。

模型相關(guān)符號(hào)說明

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

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

L：泊位碼頭長度；

A：連續(xù)泊位分割量；

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

TEU：航線運(yùn)輸?shù)募b箱標(biāo)準(zhǔn)箱；

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

NCi：船舶i需要的最大岸橋數(shù)；

li：船舶i的長度；

Ci：港內(nèi)船舶i的集裝箱總量；

tpi：船舶i要求的離港時(shí)間；

tai：船舶i的到達(dá)時(shí)間；

bpi：船舶i的最優(yōu)泊位，以bi表示；

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

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

rpi：船舶i的實(shí)際泊位；

tbi：船舶i的泊位時(shí)間；

tdi：船舶i的實(shí)際離港時(shí)間；

WB：等待泊位的船舶集；

BW：作業(yè)過程中的船舶集；

OTS：延期船舶集；

addCranei：船舶i按時(shí)完成任務(wù)需要的額外岸橋數(shù)；

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

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

Ni：船舶i按時(shí)完成任務(wù)需要的岸橋數(shù)；

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

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

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

LCi：船舶i工作時(shí)的泊位集；

TLi：船舶i的左邊集裝箱數(shù)量；

tfi：船舶i的估計(jì)作業(yè)時(shí)間；

tyi：船舶i的估計(jì)離港時(shí)間；

nci：船舶i工作時(shí)的岸橋數(shù)；

wi：船舶i在港口中的等待時(shí)間；

thi：船舶i的作業(yè)持續(xù)時(shí)間。

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

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

3 多階段協(xié)作調(diào)度

多階段協(xié)作調(diào)度包括船舶泊位分配和岸橋分配，岸橋分配又劃分為泊位時(shí)岸橋分配和離港后岸橋分配。

3.1 泊位分配算法

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

3.2 岸橋調(diào)度算法

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

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

圖4 泊位時(shí)岸橋分配算法

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

圖5 離港時(shí)岸橋分配算法

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

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

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

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

步驟4選取當(dāng)前離港船舶j，時(shí)間窗口移至tdj并釋放QCjand LCj。

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

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

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

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

步驟9檢查WB中是否所有船舶已經(jīng)處理。如不是，w＝w+1，轉(zhuǎn)步驟8，否則，轉(zhuǎn)步驟10。

步驟10如tdj+1＜tai+1，時(shí)間窗口移至tdj+1，j＝j(luò)+1，轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟11。

步驟11如所有船舶完成作業(yè)，停止仿真并輸出結(jié)果，否則，i＝i+1，轉(zhuǎn)步驟2。

3.3 模型表示與調(diào)度框架

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

表1 粒子位置的二維數(shù)組

根據(jù)xi的值，可以得到每個(gè)si的值。以縱向序列表示船舶的標(biāo)識(shí)號(hào)ID，si的次序可映射為船舶的泊位次序。如表2 所示，數(shù)組表示10 個(gè)船舶的次序。通過以上的編碼方法，表2 中的服務(wù)序列可表示成表3。

表2 問題編碼

表3 服務(wù)序列解碼

基于以上分配算法和粒子群算法，設(shè)計(jì)了一種實(shí)現(xiàn)岸橋和泊位優(yōu)化分配調(diào)度框架模型，如圖6 所示。模型主要包括調(diào)度算法、分析和優(yōu)化等模塊，其中，調(diào)度算法模塊負(fù)責(zé)實(shí)現(xiàn)侯選調(diào)度計(jì)劃和輸出統(tǒng)計(jì)結(jié)果，分析模塊負(fù)責(zé)轉(zhuǎn)換編碼信息為可用信息并傳送到調(diào)度算法模塊，同時(shí)接收調(diào)度算法模塊的數(shù)據(jù)，優(yōu)化模塊負(fù)責(zé)通過粒子群算法實(shí)現(xiàn)主要調(diào)度方案的產(chǎn)生，并更新粒子群和選擇優(yōu)化結(jié)果。

圖6 泊位與岸橋多階段協(xié)作調(diào)度框架

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

4 算例分析

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

表4 船舶參數(shù)設(shè)置

FCFS算法中，船舶按時(shí)間優(yōu)先級進(jìn)行泊位。最早到達(dá)的船舶將優(yōu)先進(jìn)行泊位，其目標(biāo)是最短化船舶的總等待時(shí)間。調(diào)度計(jì)劃見表5，其中，Tg為要求的離港時(shí)間與實(shí)際離港時(shí)間的差值，Pg為首選泊位與實(shí)際泊位的差值。船舶在港的總時(shí)間為86 h，總處理時(shí)間為86 h。所以船舶無須等待即可泊位。

表5 FCFS算法結(jié)果

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

表6 本文算法結(jié)果

算法比較見表7，表中，TI 為船舶總在港時(shí)間，TP為總處理時(shí)間，TW為總等待時(shí)間，D為懲罰代價(jià)，P為泊位附加代價(jià)。顯見，F(xiàn)CFS算法可以降低船舶的等待時(shí)間，但由于泊位不在最優(yōu)（首選）位置，附加代價(jià)成為泊位代價(jià)的主要部分。通過協(xié)作調(diào)度優(yōu)化可滿足大部分船舶對首選泊位的需求，并通過岸橋分配算法也能確保大部分船舶能按計(jì)劃完成處理任務(wù)。比較第1種算法，本文算法的目標(biāo)代價(jià)顯然更加經(jīng)濟(jì)。

表7 兩種算法比較

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

圖7 3種算法求解效率

5 結(jié)語

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