集裝箱港口岸邊資源泊位與岸橋協(xié)同優(yōu)化配置研究＊

王正君 韓曉龍

（上海海事大學(xué)物流研究中心 上海 200135）

0 引 言

集裝箱港口作為物流系統(tǒng)的一個重要節(jié)點，是聯(lián)接海陸運輸?shù)囊粋€樞紐.隨著經(jīng)濟的發(fā)展，集裝箱船舶不斷向大型化發(fā)展，同時港口的吞吐量也逐年遞增.而集裝箱港口建設(shè)投資巨大，一旦建成，很難對其進行改建.作為一個集裝箱港口，提高競爭力最有效的方式，就是提高對集裝箱運輸船舶的作業(yè)效率，在減少港口作業(yè)的成本的同時提高船公司對港口服務(wù)的滿意度.整個集裝箱港口的物流操作可以分為3部分：（1）岸邊操作；（2）場內(nèi)操作；（3）連接岸邊與堆場的水平運輸.一個集裝箱港口的物流過程見圖1.

圖1 港口物流流程圖

20世紀(jì)90年代以來，產(chǎn)生了大量有關(guān)集裝箱港口的優(yōu)化模型.本文研究了在連續(xù)泊位條件下，泊位與岸橋2種資源的協(xié)同優(yōu)化配置問題.本文的特點在于考慮了2個非常實際的問題：岸橋的工作范圍；岸橋在裝卸工作時在一定范圍內(nèi)進行調(diào)整.這些約束的加入使模型更接近實際情況.最后建立了一個混合整數(shù)規(guī)劃模型，并采用兩階段分解方法進行求解.第一階段不考慮岸橋的覆蓋范圍條件下，為船舶分配泊位與岸橋.然后第二階段再根據(jù)岸橋的覆蓋范圍對第一階段的岸橋分配進行調(diào)整，產(chǎn)生最終的岸橋工作時間表.

岸橋在裝卸過程中調(diào)整的意思是，在裝卸過程中，分配給船舶的岸橋數(shù)目的變化，或者是具體的某個岸橋作業(yè)的變化.在很多文章中是不考慮裝卸過程中岸橋的調(diào)整的.然而，在這種情況下岸橋的利用是比較低的，因為空閑的岸橋不能及時移動到需要它們的地方.還有一種情況是在裝卸過程中岸橋可以隨意的移動.這會導(dǎo)致太多的岸橋開始時間，同樣也會導(dǎo)致岸橋工作效率的低下.因此，從一個實際的角度出發(fā)，在一定范圍內(nèi)限制岸橋在裝卸作業(yè)中的調(diào)整更好.在本文中規(guī)定岸橋在工作中最多調(diào)整一次.

1 文獻綜述

集裝箱港口岸邊操作問題中主要涉及的資源為泊位資源和岸橋資源，目前國內(nèi)外學(xué)者已進行了一些研究，針對泊位和岸橋的研究大多數(shù)都將他們分開來處理.泊位分配一般是確定船舶在泊時間和在港口位置.劉志雄［1］針對離散泊位問題，以最小化所有船舶在港時間最短為目標(biāo)，在不考慮岸橋資源的影響下，建立了港口泊位調(diào)度問題的數(shù)學(xué)模型，并用粒子群算法對泊位調(diào)度問題進行優(yōu)化.秦進［2］提出了一個新的離散泊位分配模型，對船舶在港口的服務(wù)時間以及港口泊位的可用時間，都考慮了時間窗約束.在目標(biāo)函數(shù)中，還考慮到船舶的不同服務(wù)時間價值.然后用模擬退火算法對問題進行了計算與分析.此外相關(guān)的研究 還 有 Kim 和 Moon［3］，Imai［4］，Monaco 和Sammarra［5］等.

岸橋分配一般處理分配給一艘船的岸橋在船舶貝位上的工作序列.相關(guān)的研究有：Lim［6］對于集裝箱船舶沒有相互影響的條件下靜態(tài)的橋吊調(diào)度問題進行了研究，他們把到來的集裝箱船舶作為一個作業(yè)，橋吊分配給船舶作業(yè)完成之后都有一個收益，他們的目標(biāo)函數(shù)是使總的收益最大化.Lee Derhorng［7］研究了橋吊之間有相互影響的橋吊分配問題，對于橋吊分配模型，作者提出了一個混合整數(shù)規(guī)劃模型，因為這是一個NP－h(huán)ard問題，作者提出了利用遺傳算法對問題進行求解，計算結(jié)果顯示遺傳算法能夠有效的解決橋吊的分配問題.

一艘船在港口的?？繒r間直接取決于這艘船所分配的岸橋數(shù)量.分配的岸橋數(shù)越多，船舶的周轉(zhuǎn)時間一般也就越快.但將泊位分派和岸橋分開來研究得到的結(jié)果很可能是資源使用的局部最優(yōu)，而得不到全局最優(yōu).先前的研究，大多是將泊位資源與岸橋資源分開來研究的，對于將兩種資源協(xié)同優(yōu)化的研究比較少.相關(guān)方面的研究有：Han Xiaole［8］研究了泊位和橋吊的協(xié)同調(diào)度問題.研究了在不確定船舶的達到時刻和集裝箱的作業(yè)時間、泊位是離散條件下，具有不同優(yōu)先級的船舶動態(tài)到達，橋吊允許在作業(yè)完當(dāng)前船舶之后移動到其他的泊位對其他船舶進行作業(yè).作者提出了一個混合整數(shù)規(guī)劃模型，并用遺傳算法進行了求解.泊位被看做是離散的情況下，泊位的利用相對來說比較低，尤其是船舶的長度遠遠小于泊位的長度的時候.韓曉龍［9］研究了連續(xù)泊位下的泊位－橋吊分配問題，建立了泊位－橋吊配置模型，用啟發(fā)式回溯算法對模型求解，并用VB＋Access開發(fā)了泊位配置輔助系統(tǒng)（BAAS）.Park和Kim［10］將泊位看做是連續(xù)的，并提供了一個兩階段的解決方案.第一階段確定船舶靠泊位置和時間，同時確定在每個工作段分配給每艘船的岸橋數(shù).第二階段建立一個基于第一階段的詳細的岸橋時間表.但是文章中假設(shè)所有的岸橋都可以在整個泊位范圍內(nèi)工作.這在現(xiàn)實中一般是不可能的.即使不考慮岸橋自身的長度和相互之間的影響，岸橋自身工作能力也限制了它們的工作范圍.Zhang Canrong［11］在將連續(xù)泊位離散化的條件下，采用梯度優(yōu)化法，研究了泊位和岸橋資源的協(xié)同調(diào)度問題.

總的來說，目前對于港口岸邊資源的已有研究中，針對連續(xù)泊位且同時考慮岸橋資源的研究較少，且很少考慮安全作業(yè)間距、船舶離港時間、岸橋作業(yè)隨機性等實際因素.

2 第一階段：數(shù)學(xué)模型

在集裝箱港口中，出口箱進場時有一個通用的規(guī)則，即將同一條船的出口箱盡量放在碼頭前沿的某一個區(qū)域或連續(xù)的幾個區(qū)域內(nèi)，船舶?？繒r接近該區(qū)域，可以降低港口的作業(yè)成本，提高船舶的作業(yè)效率.因此每艘船在靠泊時都有一個自己的偏好位置.集裝箱船到港后，需要給其安排碼頭泊位給船舶進行裝卸作業(yè)，港口一般會提前1到2天得到確切的船舶靠岸時間.如果在安排船舶靠泊時，船舶到達，但沒有泊位資源可以用，船舶就必須要等待一段時間.這就會產(chǎn)生一個等待成本.本文模型的目標(biāo)就是使船舶盡可能的?？吭谄梦恢蒙?，最小化等待成本，同時盡可能減少船舶在港時間.

2.1 假設(shè)與標(biāo)記

在本文中的假設(shè)有：（1）模型中允許岸橋在裝卸工作時進行調(diào)整，但調(diào)整的次數(shù)是應(yīng)該受到限制的，為此，假設(shè)分配給同一艘船的岸橋在一段連續(xù)的時間內(nèi)，數(shù)目跟編號都不發(fā)生改變?yōu)橐粋€操作狀態(tài).操作狀態(tài)的改變，意味著岸橋進行了一次調(diào)整；（2）計劃被分為多個相等的時間段，時間段越多，輸出就越精確；（3）將連續(xù)泊位離散化，泊位被分為相等大小的?？课恢?，泊位越多，輸出越精確；（4）岸橋的開始工作后，不會被打斷，即岸橋的工作在時間上是連續(xù)的；（5）船舶在接受服務(wù)后，工作不會被打斷，且在工作過程中船舶不會發(fā)生移動；（6）不考慮靠離泊時間，即船舶到達后就立即接受服務(wù)，服務(wù)結(jié)束后立即離港.

模型中用到的標(biāo)記：m，n，c，z，q分別表示船舶、泊位、時間、狀態(tài)和岸橋的集合p表示最大操作狀態(tài)數(shù)，這里取2；ek為船舶k的預(yù)計到達時間；ak為船舶k的需要裝卸的作業(yè)量；hk為船舶k的長度；dk為船舶k的預(yù)計離開時間；sk為船舶k的偏好位置，即在才位置靠泊船舶裝卸成本最低；mik，mak分別為船舶k服務(wù)的最小跟最大岸橋數(shù)；C0k，C1k，C2k分別為偏離偏好位置的懲罰成本，單位等待時間成本，單位在港時間成本.

決策變量的定義以及相互間關(guān)系的數(shù)學(xué)表達式略.

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

對于一個靠泊計劃來說，船舶的靠泊位置、靠泊時間、離泊時間確定了之后，整個靠泊的時間表就可以確定.靠泊時間取決于船舶最早的操作狀態(tài)的開始時間，離泊時間等于靠泊時間＋船舶在港時間，而在港時間跟分配給船舶的岸橋數(shù)成反比關(guān)系.建立泊位與岸橋優(yōu)化配置模型如下.

目標(biāo)函數(shù)：

本文的目標(biāo)是最小化集裝箱處理成本的加權(quán)總和.目標(biāo)函數(shù)中包括偏離偏好位置的懲罰成本、延遲靠泊的懲罰成本及船舶在港時間成本.

與QC相關(guān)約束條件：

與泊位相關(guān)約束條件：

約束條件：（1）每個岸橋在一個時間段最多給1艘船工作；（2）滿足岸橋的總工作量與船舶總裝卸量相等；（3）分配給船舶的岸橋是連續(xù)的；（4）每個時間段每艘船舶最多有一個狀態(tài)；（5）船舶從開始服務(wù)到結(jié)束服務(wù)之前不會被打斷；（6）分配給每艘船的最大岸橋數(shù)約束；（7）一個狀態(tài)下岸橋工作不會被打斷；（8）實際到達時間與預(yù)計到達時間約束；（9）一個泊位在一個時間段內(nèi)最多被一艘船占用；（10）船舶所占泊位之和等于船長；（11）船舶在接受岸橋工作時，泊位是被占用的；（12）泊位使用是連續(xù)的；（13）泊位一旦被占用，船舶離開前不會被打斷.

3 第二階段：岸橋調(diào)整啟發(fā)式算法

根據(jù)第一階段得到的岸橋在不同時間、不同狀態(tài)下的工作情況，考慮到實際情況中岸橋覆蓋范圍的實際情況，以及在實際中，分配給船舶的岸橋是連續(xù)的，對岸橋的分配用啟發(fā)式算法進行調(diào)整.為方便計算，在這里定義，如果船舶在港期間有2個操作狀態(tài)，則按時間順序，最早的狀態(tài)為狀態(tài)1，接下來的為狀態(tài)2.具體的步驟如下.

步驟1 按船舶到達時間順序?qū)Υ斑M行編號，從1到n.

步驟2 判斷是否所有船都已經(jīng)分配了，分配了則結(jié)束，否則進入步驟3.

步驟3 按編號順序選擇船舶k（k從1到n）.

步驟4 根據(jù)岸橋覆蓋范圍以及工作情況，獲得船舶k狀態(tài)1下的可選岸橋解空間.（因為所選岸橋編號是連續(xù)的，因此根據(jù)第一階段已知的岸橋工作情況，最左邊的岸橋確定了，順序選擇相應(yīng)個數(shù)的岸橋就可以了.）從解空間中選擇一個解，然后將該解從解空間中剔除更新解空間.當(dāng)k＝1時，狀態(tài)1最終的解空間為0則無解，結(jié)束.當(dāng)k不等于1時，如果無解，則判斷船舶k－1是否有狀態(tài)2，并令k＝k－1，有狀態(tài)2時，進入步驟5；沒有狀態(tài)2，則計入步驟2.如果有解，則判斷船舶k是否有狀態(tài)2.如果船舶有狀態(tài)2，則進入步驟5，沒有狀態(tài)2，則令k＝k＋1回到步驟2.

步驟5 獲得船舶k在狀態(tài)2下可選岸橋的解空間.（解空間是在狀態(tài)1已知解空間的基礎(chǔ)上，在狀態(tài)1下船舶最左或者最右的岸橋加或者減相應(yīng)的岸橋數(shù)，并判斷是否在狀態(tài)2的時刻可以為船舶k工作，來獲得的.）從解空間中選擇一個解，然后將該解從解空間中剔除，更新解空間，令k＝k＋1，回到步驟2；如果無解，則回到步驟4.

通過上面的啟發(fā)式算法就可以根據(jù)岸橋的工作范圍，對岸橋的分配進行調(diào)整，進而得到確切的岸橋工作時間表.

4 數(shù)據(jù)試驗

以某集裝箱港口碼頭為例，碼頭岸線長度為365.72m（1 200ft），分為10個單位即10個泊位.一個時間段為2h，取12個時間段計算.船舶的長度換算成所長的泊位數(shù)，并將工作是的安全距離按船長的10%計算在內(nèi).碼頭設(shè)有7個岸橋，沒個岸橋都有自己的覆蓋范圍.為了便于計算船舶的裝卸作業(yè)量，按每個岸橋每小時能裝卸30個集裝箱，換算成一個岸橋單獨完成裝卸作業(yè)所需要時間，即如果ak＝10則表示該船要裝卸300個集裝箱.在港口操作中，船舶在港時間的長短對港口影響最大，其次是等待時間，最后是偏好位置的影響.因此C0k，C1k，C2k分別取100，500，1 000.具體與船舶，岸橋相關(guān)的信息見表1～2.

利用Lingo求解第一階段模型可以得到結(jié)果見表3.

考慮岸橋工作范圍，對分配的岸橋利用第二階段的啟發(fā)式算法進行調(diào)整，得到最終的結(jié)果見表4.

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

表2 岸橋覆蓋范圍

表3 第一階段模型計算結(jié)果

表4 岸橋調(diào)整后最終結(jié)果

通過算例，可以看到船舶2比預(yù)計達到時間晚靠泊，而第一階段模型中分配的岸橋在考慮了岸橋覆蓋范圍之后，岸橋的工作是無法覆蓋到船舶的，這導(dǎo)致了不可行解.而經(jīng)過第二階段啟發(fā)式算法的調(diào)整，最終確定岸橋的分配方案，而且岸橋的分配是連續(xù)的，在同一艘船舶的不同狀態(tài)間調(diào)整時也只是在原有狀態(tài)的基礎(chǔ)上加或者減一定的岸橋.更符合實際的碼頭操作.

5 結(jié)束語

研究了連續(xù)泊位下泊位岸橋協(xié)同調(diào)度的問題，以最小化偏好位置懲罰成本、等待時間成本與在港時間成本為目標(biāo).采用兩階段的分解算法，建立混合整數(shù)規(guī)劃模型進行求解.在考慮了岸橋覆蓋范圍之后，使問題更加現(xiàn)實.但這有可能會導(dǎo)致第一階段得出的結(jié)果后，在第二階段啟發(fā)式算法中無可行解.本文未能給出在第二階段無解的情況下，如何反饋給第一階段模型，并對第一階段模型的結(jié)果進行調(diào)整.這將是接下來要進行的研究的工作能容.

［1］劉志雄.港口泊位調(diào)度問題粒子群優(yōu)化研究［J］.物流工程與管理，2010，32（8）：101－103.

［2］秦 進，繆立新，陳長彬，等.時間窗限制下港口泊位優(yōu)化分配問題模型［J］.船海工程，2010，39（2）：142－145.

［3］KIM K H，MOON K C.Berth scheduling by simula－ted annealing ［J］.Transportation Research Part B，2003，37（6）：541－560.

［4］IMAI A，SUN X，NISHIMURA E，et al.Berth allocation in a container port：Using a continuous location space approach［J］.Transportation Research Part B，2005，39（3）：199－221.

［5］MONACO M F，SAMMARRA M.The berth allocation problem：A strong formulation solved by a Lagrangian approach ［J］. Transportation Science，2007，41（2）：265－280.

［6］LIM A，RODRIGUES B，XIAO F，et al.Crane scheduling with spatial constraints［J］.Naval Research Logistics，2004，51：386－406.

［7］LEE Derhorng，WANG Huiqiu，MIAO Lixin.Quay crane scheduling with non－interference constraints in port container terminals［J］.Transportation Research Part E 2008，44 ：124－135.

［8］HAN Xiaole，LU Zhiqiang，XI Lifeng.A prozctive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time［J］.European Journal of Operational Research 2010，207：1 327－1 340.

［9］韓曉龍.集裝箱港口裝卸作業(yè)資源配置研究［D］.上海：上海海事大學(xué)經(jīng)濟，2005.

［10］PARK Y M，KIM K H.A scheduling method for berth and quay cranes［J］.OR Spectrum，2003，25（1）：1－23.

［11］ZHANG Canrong，ZHENG Li，ZHANG Zhihai，et al.The allocation of berths and quay cranes by using a sub－gradient optimization technique［J］.Computers ＆Industrial Engineering ，2010，58：40－50.