王正君 韓曉龍

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

0 引 言

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

圖1 港口物流流程圖

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

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

1 文獻(xiàn)綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1 按船舶到達(dá)時(shí)間順序?qū)Υ斑M(jìn)行編號(hào)，從1到n.

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

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

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

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

4 數(shù)據(jù)試驗(yàn)

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

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

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

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

表2 岸橋覆蓋范圍

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］秦 進(jìn)，繆立新，陳長(zhǎng)彬，等.時(shí)間窗限制下港口泊位優(yōu)化分配問(wèn)題模型［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)濟(jì)，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.