集裝箱碼頭泊位、岸橋和集卡協(xié)同調(diào)度優(yōu)化

田 星，孟慶柱

（1.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063；2.天津東方海陸集裝箱碼頭有限公司，天津 300456）

1 引言

對集裝箱碼頭來說，泊位、岸橋和集卡是三種重要的基礎(chǔ)資源，泊位分配、岸橋配置和集卡調(diào)度對提高集裝箱碼頭的運作效率至關(guān)重要。泊位分配的目的是為了更好地利用有限的泊位資源，減少船舶在港產(chǎn)生的費用；岸橋是碼頭上比較昂貴的資源，岸橋調(diào)度指在滿足岸橋位置約束的條件下合理配置岸橋的數(shù)量，以減少岸橋的閑置時間，提高岸橋的利用率；集卡運輸集裝箱在岸橋和堆場之間移動，集卡數(shù)量過多，會造成空間有限的堆場的擁堵，同時增加集卡的閑置率，降低集卡的作業(yè)效率，而集卡數(shù)量不足，會造成集裝箱運輸?shù)难舆t，從而降低了岸橋的作業(yè)效率。這三種資源緊密相關(guān)、具有聯(lián)動關(guān)系，每種資源的調(diào)度都會對其它資源的調(diào)度產(chǎn)生影響。對港口來說，在原有硬件基礎(chǔ)設(shè)施上，單獨對其中某種資源進行調(diào)度優(yōu)化，并不能實現(xiàn)所有資源的最優(yōu)化利用，不能達到集裝箱碼頭整體物流作業(yè)效率的最優(yōu)化。同時考慮船舶泊位分配、岸橋配置和集卡調(diào)度這三個作業(yè)環(huán)節(jié)，協(xié)調(diào)好三個作業(yè)環(huán)節(jié)之間的關(guān)系，從整體上對三種資源進行協(xié)同調(diào)度，才能盡可能達到集裝箱碼頭整體物流作業(yè)效率的最優(yōu)化，從而提高港口的運營效率。

近年來，國內(nèi)外許多學(xué)者針對集裝箱碼頭一種資源的調(diào)度優(yōu)化問題展開了研究。在泊位調(diào)度方面，Imai[1]針對離散型泊位船舶動態(tài)實時靠泊問題，以船舶在港時間最小為目標(biāo)構(gòu)建了混合整數(shù)規(guī)劃模型，然后用啟發(fā)式算法進行求解；Lim[2]給出了泊位調(diào)度問題是NP完全問題的證明，并以泊位閑置率最低為目標(biāo)，把連續(xù)泊位調(diào)度問題轉(zhuǎn)化成二維裝箱問題進行研究；許歡[3]等以在港作業(yè)時間最短為目標(biāo)，將實際到港時間作為決策變量建立了泊位分配數(shù)學(xué)模型，并用實際算例進行了驗證。在岸橋調(diào)度方面，Daganzol[4]是最早開始進行研究的學(xué)者，他建立了混合整數(shù)規(guī)劃模型來合理配置每艘船的岸橋作業(yè)線；Kim和Park[5]在固定船舶裝卸量的前提下，以作業(yè)時間最小為目標(biāo)建立了混合整數(shù)規(guī)劃模型，運用貪婪隨機自適應(yīng)算法和分支定界方法進行求解；曾慶成[6]在Kim的模型基礎(chǔ)上進行了改進，運用改進的遺傳算法來優(yōu)化岸橋配置問題。在集卡調(diào)度方面，Bish[7]運用啟發(fā)式算法以船舶在港時間最小為目標(biāo)提出了集卡動態(tài)調(diào)度模型；Han[8]從平衡碼頭堆場資源的角度出發(fā)，運用啟發(fā)式算法對中轉(zhuǎn)型集卡調(diào)度問題進行了研究；曾慶成[9]借助Q學(xué)習(xí)算法對不同條件下的集卡調(diào)度問題進行求解，求得相關(guān)調(diào)度策略；李廣儒等針對面向整個港口的集卡作業(yè)問題，提出了一個動態(tài)蟻群算法來進行求解，使算法更加具有時效性[10]。

針對集裝箱碼頭多種資源的優(yōu)化調(diào)度問題，Bierwirth和Meisel[11]指出可以用三種方法來求解泊位、岸橋和集卡的調(diào)度問題，即順序法、反饋回路法和同步法，順序法和反饋回路法都需要建立兩個模型，實現(xiàn)分層調(diào)度，而同步法能夠?qū)崿F(xiàn)三種資源的協(xié)同調(diào)度，將兩個模型合并為一個模型進行求解；馮春煥[12]在泊位連續(xù)和裝卸混合作業(yè)的前提條件下，以船舶在港時間與集卡裝卸集裝箱運輸作業(yè)時間之和最小為目標(biāo)，構(gòu)建了一個三者協(xié)同調(diào)度的整數(shù)線性規(guī)劃模型，利用Lingo求解得到了船舶的最佳泊位、最優(yōu)岸橋分配數(shù)量以及基于運輸時間最短的集卡行駛路徑，并將結(jié)果與之前的三種資源單獨調(diào)度的研究相比較；單浩[13]以計劃期內(nèi)所有到港船舶的作業(yè)費用最少為目標(biāo)，建立了三者協(xié)同調(diào)度優(yōu)化的數(shù)學(xué)模型，然后運用遺傳算法進行求解，驗證了模型的有效性；ZJ.Gao和CJ.Wu等[14]不僅考慮了這三種資源，也將堆場龍門吊納入考慮范圍，以最小化船舶在港時間、岸橋作業(yè)時間、集卡運輸時間和堆場龍門吊的作業(yè)時間為目標(biāo)建立了一個數(shù)學(xué)模型，并設(shè)計了遺傳算法進行求解，具有一定的參考意義；A.Karam[15]在給出了泊位調(diào)度問題（BAP）與岸橋、集卡聯(lián)合調(diào)度問題兩個模型的基礎(chǔ)上，以最小化集裝箱處理成本為目標(biāo)，建立了一個三者協(xié)同調(diào)度的混合整數(shù)規(guī)劃數(shù)學(xué)模型，集裝箱處理成本包括三個方面：船舶?？课恢米罴巡次坏膽土P成本、船舶到港時間晚于預(yù)期到港時間的懲罰成本和船舶離港時間晚于最晚離港時間的懲罰成本；A.Karam和A.B.Eltawil[16]認(rèn)為集卡數(shù)量的多少對船舶整體作業(yè)時間有重大影響，他們在集卡數(shù)量有一定限制的條件下提出了一個協(xié)同調(diào)度的混合整數(shù)規(guī)劃模型，并對文中的排隊模型進行了驗證。以上針對泊位、岸橋和集卡協(xié)同調(diào)度的研究都是在一定前提條件之下進行的，具有一定的代表意義。本文通過對我國T集裝箱港口進行實地調(diào)研，建立了一個泊位、岸橋和集卡協(xié)同調(diào)度的數(shù)學(xué)模型，并利用該碼頭的實際數(shù)據(jù)，運用CPLEX進行求解驗證。

2 問題描述

在T港口的實際操作過程中，船舶到港后先在錨地臨時?？康却次唬@得泊位后進行靠泊操作，當(dāng)船舶?？客戤吅螅瑸樵摯渲玫陌稑蚝图ǘ家丫臀?，岸橋立即開始進行集裝箱卸載作業(yè)，將進口箱卸載到集卡上，由集卡運輸?shù)蕉褕龅闹付▍^(qū)域，然后集卡再空箱返回岸邊。本文的研究不能覆蓋碼頭所有作業(yè)時間內(nèi)的操作，以48h為一個研究周期，時間單位精確到分鐘，對一個周期內(nèi)船舶到港、?？恳约昂罄m(xù)的作業(yè)展開研究。

通過在T港口進行實地調(diào)研，從該港口提供的晝夜作業(yè)計劃表中提取真實數(shù)據(jù)進行分析，得到了該碼頭在日常作業(yè)中，船舶待卸載的集裝箱數(shù)量與分配的岸橋數(shù)量之間的關(guān)系，本文以均衡每艘船的作業(yè)時間為目的，設(shè)置了一個常數(shù)k，使得待卸載的集裝箱數(shù)量與常數(shù)k的比值即為每艘船舶分配的岸橋數(shù)量，將建立的數(shù)學(xué)模型轉(zhuǎn)化為整數(shù)線性規(guī)劃模型。在本文中，若船舶的實際離港時間早于最晚離港時間，則延誤時間為0，若實際離港時間晚于最晚離港時間，則延誤時間為實際離港時間與最晚離港時間的差值；船舶待裝卸的集裝箱總量除以每臺岸橋的作業(yè)效率即為船舶服務(wù)的岸橋總作業(yè)時間；由于每輛集卡每次只運輸一個集裝箱，船舶待卸載的集裝箱總量乘以集卡運輸往返時間即為船舶服務(wù)的集卡總作業(yè)時間；在實際操作過程中，岸橋的作業(yè)成本比集卡的作業(yè)成本高很多，為了減少總成本，應(yīng)該讓集卡等待岸橋，避免岸橋等待集卡情況的發(fā)生，對于任意船舶來說，每一臺岸橋的作業(yè)時間減去每一輛集卡的運輸時間即為平均每輛集卡等待岸橋的時間，那么，集卡等待岸橋的總時間為：每一臺岸橋的作業(yè)時間減去每一輛集卡的運輸時間再乘以每臺岸橋分配的集卡數(shù)量，再乘以為船舶服務(wù)的岸橋數(shù)量。

3 數(shù)學(xué)模型

3.1 模型假設(shè)

本文模型的建立基于如下假設(shè)條件：（1）碼頭岸線為連續(xù)型，不考慮任何物理條件對泊位的約束和限制；（2）船舶在港過程中可能產(chǎn)生的移泊都忽略不計；（3）所有到港船舶的到港時間和待卸載的集裝箱量是已知的；（4）只對進口箱即需要卸載的集裝箱進行研究；（5）岸橋為軌道式并處于同一軌道上，具有相同的移動速度；（6）所有岸橋具有相同的工作效率，其故障和休息時間忽略不計；（7）任意兩臺岸橋之間的作業(yè)不會對彼此產(chǎn)生干擾；（8）每臺岸橋配置的集卡數(shù)量相同且已知；（9）碼頭上可供使用的集卡數(shù)量充足；（10）每輛集卡每次只能運輸一個集裝箱；（11）集卡運輸不同集裝箱到不同堆場的往返時間相同且已知；（12）當(dāng)船舶上所有的進口箱卸載完畢后，為該船舶服務(wù)的岸橋和集卡才能離開去為另一艘船服務(wù)。

3.2 模型參數(shù)定義

為了方便模型的構(gòu)建，下面對建立模型所需的相關(guān)參數(shù)進行定義。

（1）集合符號定義：V={v1,v1,...,vk}，為船舶集合；Q={q1,q1,...,qn}，為岸橋集合；WB(t)為在t時刻，等待靠泊的船舶集合；BA(t)為在t時刻，在港的船舶集合。

（2）參數(shù)符號定義：T為研究周期；L為可用靠泊岸線的長度；Nq為碼頭可用岸橋總數(shù)；Nt為碼頭可用集卡總數(shù)；rq為岸橋q的單位作業(yè)效率；t為集卡運輸集裝箱一次的往返時間；nqv為船舶v分配的岸橋數(shù)量；ntq為岸橋q分配的集卡數(shù)量；lv為船舶v的長度；為船舶v的到港時間；為船舶v的最晚離港時間；NCv為船舶v待裝卸的集裝箱數(shù)量；為船舶v的在港單位作業(yè)時間成本；為船舶v等待泊位的單位作業(yè)時間成本；為船舶v延遲離港的單位作業(yè)時間成本；Cq為岸橋q的單位作業(yè)時間成本；Ct為集卡t的單位作業(yè)時間成本；為集卡t等待岸橋q的單位作業(yè)時間成本。

（3）直接變量定義：bv為船舶v的實際?？课恢茫籒hv為船舶v船首所對應(yīng)的岸橋的編號；為船舶v開始作業(yè)（靠泊完成）的時間；為船舶v的實際離港時間。

3.3 模型建立

本文將時間類優(yōu)化目標(biāo)轉(zhuǎn)化為作業(yè)成本優(yōu)化目標(biāo)，即以集裝箱碼頭整體物流作業(yè)總成本最小為優(yōu)化目標(biāo)來構(gòu)建數(shù)學(xué)模型，具體如下：

式（1）為目標(biāo)函數(shù)，目標(biāo)為整體物流作業(yè)總成本最小，具體包括6大主要成本：船舶在港時間成本、船舶等待靠泊的時間成本、岸橋作業(yè)的時間成本、集卡作業(yè)的時間成本、岸橋等待集卡的時間成本和船舶延誤成本。式（2）為將間接變量帶入式（1）后，得到的簡化目標(biāo)函數(shù)。

式（3）-（8）為約束條件：式（3）為對于任意時刻t，靠泊的船舶總長度小于等于碼頭岸線的總長度；式（4）為對于任意兩艘船v、v'，不能共用同一個泊位，即不允許出現(xiàn)重疊靠泊的現(xiàn)象；式（5）為對于任意時刻t，同一個岸橋q只能為同一艘船服務(wù)；式（6）為對于任意時刻t，為船舶v服務(wù)的岸橋數(shù)量不能大于碼頭的岸橋資源總數(shù)；式（7）為對于任意時刻t，為岸橋q服務(wù)的集卡數(shù)量不能大于碼頭的集卡資源總數(shù)；式（8）為對于任意船舶v，船舶完成靠泊后才能進行裝卸操作。

4 算例分析與求解

4.1 算例介紹

T港口的碼頭岸線為連續(xù)型，總長1 200m，研究周期為48h（2 880min），在一個周期內(nèi)共有15艘船在該碼頭進行卸船作業(yè)。該碼頭配有9臺岸橋，編號為1至9，每臺岸橋的作業(yè)效率為0.5箱/min，進行集裝箱運輸作業(yè)的集卡一共有44輛，集卡運輸集裝箱的往返時間為4min，每臺岸橋配置的集卡為4輛。各個作業(yè)環(huán)節(jié)的單位作業(yè)時間成本為：船舶等待泊位的單位作業(yè)時間成本為283元/min，船舶在港的單位作業(yè)時間成本為200元/min，船舶延遲離港的單位作業(yè)時間成本為250元/min，每臺岸橋的作業(yè)時間成本為40元/min，每輛集卡的作業(yè)時間成本為10元/min，集卡等待岸橋的單位作業(yè)時間成本為10元/min。

根據(jù)一個周期內(nèi)船舶到港的先后順序?qū)Υ斑M行1-15的編號，各船舶的長度、到港時間、最晚離港時間、待卸載的集裝箱數(shù)量等信息見表1。

表1 到港船舶的相關(guān)信息表

4.2 結(jié)果分析

利用ILOG CPLEX求解算例得到最優(yōu)解，即在該周期內(nèi)，到港船舶的泊位位置、開始作業(yè)時間、實際離港時間、分配的集卡數(shù)量以及分配的岸橋數(shù)量和編號，見表2。

表2 案例最優(yōu)分配方案

利用ILOG CPLEX求解顯示上述分配結(jié)果是最優(yōu)的，得出的該集裝箱碼頭的整體物流作業(yè)總成本最小值為1 845 926元。

本文選取的算例是T港口的碼頭在48h內(nèi)產(chǎn)生的真實數(shù)據(jù)，為了驗證本文模型的有效性，將本文求解得到的最優(yōu)解與實際操作過程進行比較。在實際操作過程中，到港船舶的相關(guān)信息見表3。

表3 實際操作過程中船舶相關(guān)信息

利用表1和表3中相關(guān)數(shù)據(jù)，根據(jù)式（2）求得實際操作過程中的整體物流作業(yè)總成本為：2 845 410元。該成本比本文求得的最優(yōu)成本大得多，可以得到以下結(jié)論：

（1）本文用ILOG CPLEX求解算例，并在較短時間內(nèi)得到了最優(yōu)解，證明了建立的整數(shù)線性規(guī)劃數(shù)學(xué)模型是有效的，表明精確算法也可以用來求解泊位、岸橋和集卡的協(xié)同調(diào)度問題；

（2）根據(jù)本文數(shù)學(xué)模型求得的總成本比實際操作過程的總成本減少了35%，如果將本文建立的模型運用在實際操作作業(yè)中，能有效降低碼頭作業(yè)成本，提高作業(yè)效率，具有一定的實際意義。

5 結(jié)論

在集裝箱碼頭上，單獨對泊位、岸橋和集卡中的某一種資源進行優(yōu)化調(diào)度，不能實現(xiàn)碼頭整體物流作業(yè)效率的最優(yōu)化，只有同時考慮三種資源的協(xié)同調(diào)度優(yōu)化，才能盡可能達到碼頭整體物流作業(yè)效率的最優(yōu)?；谏鲜鏊悸?，針對泊位、岸橋和集卡的協(xié)同調(diào)度優(yōu)化進行了研究，以整體物流作業(yè)成本最小為目標(biāo)，提出了協(xié)同調(diào)度的整數(shù)線性規(guī)劃數(shù)學(xué)模型，并以國內(nèi)某大型集裝箱港口T的真實數(shù)據(jù)為算例，運用商業(yè)軟件ILOG CPLEX進行求解，在可接受的時間內(nèi)求得了最優(yōu)解，并將求得的結(jié)果與實際操作過程進行對比，表明得到的最優(yōu)解在實際操作過程中是可行的，驗證了模型的有效性和準(zhǔn)確性。如果將本文建立的模型運用在T碼頭實際操作過程中，能夠有效降低碼頭作業(yè)成本，提高作業(yè)效率，具有一定的實際意義。

本文的研究還存在一些不足之處，后續(xù)的研究將從以下幾個方面展開：（1）本文選取的算例相對較小，將來考慮擴大算例的規(guī)模來驗證模型的有效性，比如考慮對一周、一月內(nèi)到港的船舶開展研究；（2）在擴大算例規(guī)模的條件下，如果運用本文的模型和算法求解較慢，考慮改進模型，或者運用一些啟發(fā)式算法來進行求解。

[參考文獻]

[1]Akio Imai,Etsuko Nishimura,Sryatos Papadimitriou.The dynamic berth allocation problem for a container port[J].Transportation Research Part B,2001,35:401-417.

[2]Lim A.The berth planning problem[J].Operations Research Letters,1998,22(2):105-110.

[3]許歡,劉偉,劉詩.低碳經(jīng)濟下的港口泊位分配模型及其算法實現(xiàn)[J].計算機工程與應(yīng)用,2014,(18):47-48.

[4]Daganzo C F.The crane Scheduling Problem[J].Transportation Research.1989,23(3):159-175.

[5]Kim K H,Park Y M.A crane scheduling method for port container terminals[J].European Journal of Operational Research,2003,156(3):752-768.

[6]曾慶成,高宇.集裝箱碼頭裝卸橋調(diào)度優(yōu)化模型與算法[J].計算機工程與應(yīng)用,2006,(32):217-219.

[7]Ebru K Bish,Thin-Yin Leong,Chung-Lun Li,et al.Analysis of a new vehicle scheduling and location problem[J].Naval Research Logistics,2001,48(5):363-385.

[8]Yongbin Han,Loo Hay Lee,Ek Peng Chew,et al.A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub.OR Spectrum,2008,30(4):697-720.

[9]曾慶成.集裝箱碼頭裝卸作業(yè)集成調(diào)度模型與方法[D].大連:大連海事大學(xué),2008.

[10]李廣儒,楊大奔,任大偉.集卡動態(tài)調(diào)度路徑優(yōu)化算法[J].交通運輸工程學(xué)報,2012,12(3):86-91.

[11]Bierwirth C.,Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research,2010,202(3):615-627.

[12]馮春煥.集裝箱碼頭泊位—岸橋—集卡調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2011.

[13]單浩.集裝箱碼頭泊位、岸橋和集卡協(xié)同調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2013.

[14]Guangfan Li,Chaohe Chen,Bifeng Jiang,et al.Research on the Optimization Model of Berth Allocation-Quay Crane Assignment-Truck Scheduling at Container Terminals[J].Applied Mechanics and Materials,2014,587-589:1 785-1 788.

[15]Ahmed Karam.Allocating berths,quay cranes and internal trucks in container terminals[A].the International Marine Transport&Logistics Conference(MARLOG 4)[C].2015.

[16]Ahmed Karam,Amr Eltawil.A new method for allocating berths,quay cranes and internal trucks in container terminals[A].5thIEEE International Conference on Logistics,Informatics and Service Science[C].2015.