考慮服務(wù)公平性的連續(xù)泊位-岸橋集成分配

郝楊楊， 李軍軍， 黃有方

(1.上海海事大學(xué) 物流研究中心， 上海 201306； 2.上海海事大學(xué) 商船學(xué)院， 上海 201306)

?

考慮服務(wù)公平性的連續(xù)泊位-岸橋集成分配

郝楊楊1*， 李軍軍2， 黃有方1

(1.上海海事大學(xué) 物流研究中心， 上海 201306； 2.上海海事大學(xué) 商船學(xué)院， 上海 201306)

泊位和岸橋是集裝箱碼頭非常最要的資源，合理的分派與調(diào)度可以有效地提高作業(yè)效率.目前泊位和岸橋的集成調(diào)度模型中大多以最小化船舶在港總時間或最小懲罰成本為目標(biāo)函數(shù)，忽略了碼頭對船舶服務(wù)的公平性.為此，通過擴展現(xiàn)有的連續(xù)泊位分配模型，兼顧船舶懲罰成本及船舶等待與岸橋分配的公平性，建立多目標(biāo)的連續(xù)泊位分配模型.設(shè)計一個三階式鄰域搜索算法， 該啟發(fā)式算法包括鄰域搜索安排船序列、停泊位置搜索和分配調(diào)整岸橋3個階段.實驗結(jié)果顯示，不同的鄰域策略取得的最優(yōu)解不同，通過設(shè)置最優(yōu)的鄰域策略可以獲取最優(yōu)的目標(biāo)函數(shù)值.實驗表明，該模型與算法可以在接受的時間內(nèi)取得最優(yōu)解，相關(guān)成果可以為碼頭對船舶服務(wù)的公平性研究提供理論依據(jù).

集裝箱碼頭； 連續(xù)泊位； 泊位-岸橋； 公平性； 鄰域搜索

作為集裝箱碼頭最重要的資源，泊位和岸橋的合理調(diào)度可以有效提高作業(yè)效率.實際作業(yè)中出于岸橋數(shù)量和岸橋成本限制，碼頭需要在最大限度的岸橋數(shù)量和有限泊位岸線下，進(jìn)行集成資源優(yōu)化配置來提高運行效率[1-2].

在泊位和岸橋的集成分配問題中，目標(biāo)函數(shù)通常是船舶總在港時間最小、總成本最小或是總等待時間最小.如Imai等[3-4]考慮到船舶服務(wù)的優(yōu)先級，建立了以船舶最小化在港時間為目標(biāo)的優(yōu)化模型，提出通過遺傳算法求解泊位分配問題.Frank Meisel等[5]采用岸橋的裝卸效率代表船舶的處理時間，研究了泊位和岸橋的聯(lián)合分配問題.梁承姬等[6]將船舶處理時間用岸橋裝卸的速度來表示，研究了泊位和岸橋整合分配問題.樂美龍等[7]研究了基于泊位偏好與服務(wù)優(yōu)先級的泊位和岸橋分配問題.將離散泊位連續(xù)化可以最大限度的提高泊位利用率，Kim等[8]構(gòu)建MIP模型研究連續(xù)泊位分配問題，并用模擬退火算法和LINDO進(jìn)行求解.韓曉龍等[9]建立了泊位分配的混合整數(shù)規(guī)劃模型以及橋吊調(diào)度的混合整數(shù)規(guī)劃模型，討論了連續(xù)泊位和岸橋的協(xié)同分配問題.

以上研究主要是從碼頭利益的角度考慮問題，最小化船舶在港總時間，提高碼頭資源利用率，卻忽略了碼頭對船舶服務(wù)的公平性.船舶服務(wù)的公平性最初體現(xiàn)在船舶的等待時間和停泊順序上，采用先到先服務(wù)(FCFS)的分配策略是最常見的研究領(lǐng)域.童珊[11]考慮到實際操作中碼頭裝卸效率同時影響著船舶在港時間和船舶的優(yōu)先權(quán)，建立了船舶優(yōu)先權(quán)的動態(tài)連續(xù)泊位分配模型.勾巖[12]研究港口服務(wù)的公平與效率，建立以船舶在港總時間和船舶等待時間方差最小為目標(biāo)的雙目標(biāo)優(yōu)化模型，并采用基于啟發(fā)式算法的多目標(biāo)遺傳算法NSGA-II對模型進(jìn)行求解，實現(xiàn)了公平與效率的統(tǒng)一.以上研究雖然通過對船舶延遲到達(dá)、延遲離港、偏離偏好泊位等情況的懲罰成本的分析，然而船舶服務(wù)的公平性中將等待靠泊作業(yè)的公平性和等待完成作業(yè)離開的公平、岸橋分配數(shù)量的公平等作為評估標(biāo)準(zhǔn)的研究卻很少.

本文通過擴展現(xiàn)有的連續(xù)泊位分配模型，考慮等待的公平性與岸橋分配的公平性，建立多目標(biāo)的連續(xù)泊位分配模型.為驗證公平性對船舶靠泊計劃的影響，設(shè)計一個三階式鄰域搜索算法， 該啟發(fā)式算法包括鄰域搜索安排船序列、停泊位置搜索和分配調(diào)整岸橋三個階段.通過鄰域生成策略和公平性的成本函數(shù)相結(jié)合來設(shè)計實驗方案，檢驗算法的有效性，分析等待時間對公平性的影響.

1問題描述與假設(shè)

通常船舶抵港后，碼頭調(diào)度員將根據(jù)相關(guān)信息和調(diào)度策略將泊位和岸橋分配給船舶.泊位-岸橋的優(yōu)化分配是指通過分配適當(dāng)?shù)牟次?、選擇合適的靠泊順序并配備合理的岸橋數(shù)量，使船舶在港時間較短，以提高船舶的利用率和客戶的滿意度，并降低碼頭的運營成本.對船公司而言，希望到港的船舶被分配到理想的偏好泊位、排隊等待靠泊的時間最小且處理時間延誤最??；對碼頭管理人員而言，希望計劃周期內(nèi)保持碼頭的集裝箱吞吐量能最大.

當(dāng)船舶靠泊時，占用泊位的長度取決于其船長，占用泊位的時間取決于岸橋裝卸處理的時間.本文考慮的連續(xù)泊位-岸橋分配問題，只要船舶滿足靠泊的岸線長度，船舶便可沿岸線靠泊，多只船可以同時靠泊接受服務(wù).本文通過對預(yù)期到達(dá)時間和裝卸服務(wù)需求量這兩個因素核算排序，綜合衡量船舶接受港口服務(wù)過程的公平性，包括順序公平、基于服務(wù)時間公平和資源配置公平.本文考慮船舶偏好泊位的影響以及船舶到港、離港延遲懲罰的約束，并結(jié)合船舶接受服務(wù)的公平性，建立的連續(xù)泊位和岸橋的集成分配模型將基于以下合理假設(shè)：

1) 每條船必須被服務(wù)且被服務(wù)一次，即不考慮移泊作業(yè)；

2) 船舶到港時間不能早于預(yù)計到達(dá)時間，只能等待靠泊，不能提前到港；

3) 處理時間取決于所在泊位、碼頭的岸橋數(shù)量，與船舶的距離、集裝箱運輸以及其他因素等無關(guān)；

4) 泊位資源視為連續(xù)線性的，被劃分為盡可能多且相等的微小停泊單元，多只船舶可以同時停靠；

5) 每條船舶設(shè)有同時作業(yè)的最大岸橋數(shù)和最小岸橋數(shù)，當(dāng)可用岸橋數(shù)量不小于最小岸橋數(shù)時才能開始作業(yè)，并且不能大于最大岸橋數(shù)；

6) 分散的閑置岸橋不能橫跨工作，岸橋只能在岸線固定的位置為靠泊的船進(jìn)行裝卸；

7) 每條船都有一個最優(yōu)?？科梦恢茫x偏好泊位會增加在港時長；

8) 假定泊位計劃在零時刻開始，船舶只有到港后才能進(jìn)行靠泊作業(yè)，正常情況下靠泊后即可開展裝卸作業(yè).

此外，船舶靠港作業(yè)過程中的靠泊時間和離泊時間對于不同船型差異不大，且相對整個在港時間很小，在此忽略不計.

2模型建立

2.1相關(guān)概念和符號

本模型的相關(guān)概念和符號如表1.

表1 相關(guān)概念和符號

續(xù)表1

2.2連續(xù)泊位岸橋集成分配模型

連續(xù)泊位岸橋集成分配模型為

(1)

目標(biāo)函數(shù)中f=f1+f2+f3，fmax和fmin用來作為函數(shù)的最大值和最小值，其中?max和?min作為評價公平性的最大和最小值.然后，懲罰成本和公平措施通過方程(1)合成一個獨立的目標(biāo)函數(shù)，此時w?+wf=1，w?≥0且wf≥0.

1)懲罰成本f

泊位與岸橋集成調(diào)度的優(yōu)化目標(biāo)包含兩方面：一是泊位的優(yōu)化，即停靠泊位應(yīng)該盡可能的靠近偏好泊位，以減少集裝箱從岸橋到后方堆場的移動時間，提高岸橋作業(yè)效率，降低作業(yè)；二是服務(wù)時間的優(yōu)化，即船舶入港后應(yīng)盡快靠泊作業(yè)，靠泊后盡可能在船公司規(guī)定的時間內(nèi)作業(yè)完畢并按時離港.針對這兩個目標(biāo)建立了最小化總懲罰成本的多目標(biāo)模型，旨在減少靠泊懲罰成本、靠泊等待時間、延遲離港時間.目標(biāo)函數(shù)通過(2)～(5)定義；而約束函數(shù)通過式(6)～(30)定義.

Minimize

(2)

(3)

(4)

(5)

s.t :

BLv≥Bv-Sv，?v，

(6)

BRv≥Sv-Bv，?v，

(7)

TLv≥Tv-ev，?v，

(8)

Tv≥ev，?v，

(9)

DLv≥Cv-dv，?v，

(10)

(11)

∑vXv，p，t≤1，?p，t，

(12)

∑vYv，t≤c-Dt，?t，

(13)

∑tYv，t≥av，?v，

(14)

Vv，t≤Yv，t，?v，t，

(15)

Yv，t≤M·Vv，t，?v，t，

(16)

(17)

Yv t≤uv，?v，t，

(18)

Vv t≤∑pXv，p，t，?v，t，

(19)

Vv t·M≥∑pXvpt，?v，t，

(20)

Uvp≤∑tXvpt，?v，p，

(21)

Uvp·M≥∑pXvpt，?v，p，

(22)

(23)

(24)

Vvt≤∑p，τ≤tZvpτ，?v，t，

(25)

∑p，tZvpt=1，?v.

(26)

?v，ρ≥2，ρ≤sps-bv:

(27)

(28)

(29)

(30)

其中,目標(biāo)函數(shù)式(2)為最小化懲罰成本函數(shù)，包括船舶停泊的泊位偏移偏好泊位的總成本、船舶延遲靠泊的總懲罰成本，船舶延遲離泊的總懲罰成本，分別通過 (3)～(5)定義.式(7)和(8)約束了船的停泊位置偏離偏好泊位的水平距離.函數(shù)(8)界定了船舶推遲停泊的時間差.式(9)約束了船舶到港后才能靠泊.式(10)約束了延遲離泊的時間差.函數(shù)式(11)約束了船舶離開時刻必須大于等于集裝箱作業(yè)完成時間.函數(shù)式(12)約束了每一個時空點只能被一條船占用，考慮了前期滾動調(diào)度中已被占用的時空點.函數(shù)式(13)表示的可供分配的岸橋數(shù)受總岸橋數(shù)限制，考慮了前期滾動調(diào)度結(jié)果中每個時刻已被占用的岸橋數(shù)目.函數(shù)式(14)約束了船的作業(yè)時間必須要大于等于總橋時.函數(shù)式(15)～(16)反映了作業(yè)的持續(xù)性，至少有一個岸橋為之服務(wù)，即船舶不能中途停止作業(yè).函數(shù)式(17)～(18)限制了可以給每條船分配的岸橋數(shù)受最大值和最小值限制.函數(shù)式(19)～(20)建立了Vk，j與Xk，i，j之間的關(guān)系.函數(shù)式(21)～(22)建立了Uk，i與Xk，i，j之間的關(guān)系.函數(shù)式(23)～(25)保證了船舶靠泊后占用時間和泊位上的連續(xù)性.式(26)保證了一條船只有一個參考點，即矩形的左下角.式(27)～(30)保證了矩形內(nèi)的網(wǎng)格取值為1，矩形外的網(wǎng)格取值為0.

2)公平措施

假設(shè)船舶是按預(yù)期到達(dá)時間進(jìn)行分類，所有船舶從1到svs，則v.船舶v的服務(wù)時間是由ψv=Cv-Tv，v∈sv計算取得.根據(jù)船舶抵港的順序，可以討論基本的順序公平性.在港口服務(wù)系統(tǒng)中船舶接受處理的順序由π所界定.根據(jù)EAT 和 EDT分別對船舶進(jìn)行πa和πd兩種時間的排序，以上兩種時間序列可以討論兩種標(biāo)準(zhǔn)化延遲公平性，即遲于EAT與遲于EDT.根據(jù)QC分配數(shù)量以及泊位是否為偏好泊位，討論資源配置的公平性，包括4種類型，具體分類見表2.最后，綜合討論以上公平性.

表2 公平性設(shè)計

3鄰域搜索算法求解

鄰域搜索算法的基本思想是在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來拓展搜索范圍，獲得局部最優(yōu)解，然后在基于此局部最優(yōu)解重新系統(tǒng)地改變鄰域結(jié)構(gòu)集拓展搜索范圍找到另一個局部最優(yōu)解的過程.由于鄰域搜索算法具有實用性、有效性、時效性及魯棒性的屬性特點，且可以在可容忍的時間內(nèi)求解NP-Hard問題，因此本文將采用鄰域搜索算法求解，實現(xiàn)局部范圍內(nèi)的集成分配優(yōu)化.該算法具體分為3個階段(表3):鄰域搜索進(jìn)行排序，生成靠泊位置，調(diào)整位置和分配岸橋.

表3 鄰域搜索算法過程

4算例實驗與分析

本文不考慮水深的影響，以寧波北侖港第二大港作為參考的生成測試數(shù)據(jù)集，根據(jù)以下條件隨機產(chǎn)生100艘船的算例數(shù)據(jù).

1)碼頭的長度是1 200m，分為120段的單位段10m.因此，sps=120;

2)岸邊總計有16個岸橋;

3)預(yù)計到達(dá)時間 EAT (ev)是均勻分布在一個星期內(nèi)，即168h.計劃周期設(shè)置為180h，分為180段的時間單位.因此，sts=180;

5)預(yù)期離港時間EDT(dv)由U(ev+10，ev+15)生成;

圖1 實驗1Fig.1 Experiment 1

實驗1顯示(圖1)，隨著迭代次數(shù)的不斷增加，目標(biāo)值不斷優(yōu)化.當(dāng)?shù)?747次時，目標(biāo)函數(shù)值降到最低為0.279，隨后迭代至3 000過程中，目標(biāo)函數(shù)值始終收斂于0.279.

實驗2在實驗1的基礎(chǔ)上，保持其他參數(shù)設(shè)置不變，修改鄰域調(diào)整次數(shù)md，取值從1、5、10直至100.

實驗2顯示(圖2)，隨著鄰域調(diào)整次數(shù)md在[1，100]范圍內(nèi)呈整數(shù)倍不斷增加，目標(biāo)函數(shù)值整體呈現(xiàn)不斷遞減的趨勢.當(dāng)鄰域調(diào)整次數(shù)為1時，目標(biāo)函數(shù)值最大為0.35；隨著鄰域調(diào)整次數(shù)的增加，目標(biāo)函數(shù)值不斷減小，最終減少至0.272.

實驗3在實驗1的基礎(chǔ)上，保持其他參數(shù)設(shè)置不變，修改鄰域結(jié)構(gòu)生成方式為插入方式和交換方式，比較插入方式與交換方式取得的目標(biāo)函數(shù)值.

實驗3顯示(圖3)，插入策略收斂較快，在355次迭代后目標(biāo)函數(shù)值收斂于0.277；而交換策略在迭代1 087次后目標(biāo)函數(shù)值收斂于0.273，可以取得更好的最優(yōu)解.

圖2 實驗2Fig.2 Experiment 2

圖3 實驗3Fig.3 Experiment 3

實驗4在實驗1的基礎(chǔ)上，保持其他參數(shù)設(shè)置不變，修改相鄰兩船位置的定位方式為絕對定位和相對定位方式，比較絕對定位與相對定位取得的目標(biāo)函數(shù)值.

圖4 實驗4Fig.4 Experiment 4

實驗4顯示(圖4)，相對定位取得的最優(yōu)解明顯好于絕對定位方式，絕對定位方式的最優(yōu)解為0.297，而相對定位的最優(yōu)解為0.279.

實驗5在實驗1的基礎(chǔ)上，保持其他參數(shù)設(shè)置不變，修改產(chǎn)生鄰域的范圍，取值從5、10、15至100，分為普通分布和正態(tài)分布.

實驗5顯示(圖5)，在選用范圍為10的普通分布情況下，可以取到最優(yōu)的目標(biāo)函數(shù)值0.271.

圖5 實驗5Fig.5 Experiment 5

實驗6在實驗1的基礎(chǔ)上，保持其他參數(shù)設(shè)置不變，根據(jù)上述實驗選擇較好的參數(shù)設(shè)置，修改鄰域調(diào)整次數(shù)md為100，調(diào)整鄰域結(jié)構(gòu)生成方式為交換方式，修改相鄰兩船位置的定位方式為相對定位方式，修改普通分布產(chǎn)生鄰域的范圍為10.

實驗6顯示(圖6)，當(dāng)選用較好的參數(shù)時，算法在93次迭代之后迅速收斂至最優(yōu)解0.237，收斂速度與最優(yōu)解都較實驗1有明顯改進(jìn).

圖6 實驗6Fig.6 Experiment 6

5結(jié)論

本文給出了基于服務(wù)公平性的連續(xù)泊位-岸橋集成分配模型，通過擴展現(xiàn)有的連續(xù)泊位分配模型，考慮船舶懲罰成本、船舶等待公平性與岸橋分配的公平性，建立了多目標(biāo)的分配模型，并設(shè)計了三階段的鄰域搜索算法.實驗結(jié)果顯示，不同的鄰域策略取得的最優(yōu)解不同，通過優(yōu)化鄰域策略可以獲取更優(yōu)的目標(biāo)函數(shù)值.實驗表明，該模型與算法可以在接受的時間內(nèi)取得最優(yōu)解，相關(guān)成果可以為碼頭對船舶服務(wù)的公平性研究提供理論依據(jù).

此外，本文還存在一些不足，如懲罰系數(shù)設(shè)置的合理性、權(quán)重分配的合理性等需要進(jìn)一步研究.通過細(xì)致分析客戶對公平性滿意度的影響，調(diào)整各個公平性的權(quán)重值，探討公平性的權(quán)重體系設(shè)計對整個船舶靠泊服務(wù)公平性的影響是本文以后繼續(xù)研究的方向.

[1] BARROS V H， COSTA T S， OLIVEIRA A C M， et al. Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[J]. Computers & Industrial Engineering， 2011， 60(4):606-613．

[2] 樂美龍，劉 菲. 基于Memetic算法的泊位和岸橋分配問題[J]. 武漢理工大學(xué)學(xué)報， 2011， 33(11):66-71．

[3] IMAI A， NISHIMURA E， PAPADIMITRIOU S. Berth allocation with service priority[J]. Transportation Research Part B Methodological， 2003， 37(5):437-457．

[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 Methodological， 2005， 39(3):199-221．

[5] MEISEL F， BIERWIRTH C. Integration of berth allocation and crane assignment to improve the resource utilization at a seaport container terminal[J]. Operations Research Proceedings， 2005， 26(4):105-110．

[6] LIANG C， HUANG Y， YANG Y. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J]. Computers & Industrial Engineering， 2009， 56(3):1021-1028．

[7] 樂美龍， 劉秀玲. 基于泊位偏好與服務(wù)優(yōu)先級的泊位和岸橋分配[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版)， 2013， 39(5):709-712.

[8] KIM K H， CHAN K. Berth scheduling by simulated annealing[J]. Transportation Research Part B Methodological， 2003， 37(2):541-560．

[9] 趙坤強， 韓曉龍， 梁承姬. 連續(xù)泊位下集裝箱港口泊位與橋吊協(xié)同調(diào)度優(yōu)化研究[J]. 武漢理工大學(xué)學(xué)報， 2011， 33(11):60-65．

[10] 童 珊. 基于船舶優(yōu)先權(quán)的集裝箱港口泊位分配問題[J]. 交通運輸工程與信息學(xué)報， 2012， 10(1):105-110．

[11] 勾 巖. 考慮船舶等待時間均衡的泊位岸橋聯(lián)合分配問題研究[D]. 大連：大連海事大學(xué)， 2015.

Integrated allocation of continuous berth and quay crane base on service fairness

HAO Yangyang1， LI Junjun2, HUANG Youfang1

(1.Logistics Research Center, Shanghai Maritime University, Shanghai 201306;2.Merchant Marine College, Shanghai Maritime University, Shanghai 201306)

Berth and quay are the most important resources in container ports, and optimal allocation and scheduling of them under stochastic environment are able to improve work efficiency. At present, most of the integrated scheduling models of berth and quay crane take minimization of the total time or penalty cost of the ship in the port as the objective function, ignoring the fairness of the ship's service. Therefore, the existing continuous berth allocation model is extended to the multi objective continuous berth allocation model based on ship’s penalty cost, fairness of the ship waiting and allocation of the berth and quay crane. A neighborhood search algorithm is designed, consisting of three stages: the sequence of the adjacent search, the search for the position of the berth and the allocation and adjustment of the quay crane. The results of the experiments show that the optimal solution is obtained by different neighborhood strategies, and the optimal value of the objective function is able to be generated by setting the optimal neighborhood strategies. The model and algorithm are found to possess optimal solution in an acceptable time, and the relevant results provide theory for research on ports for ships service fairness.

container terminal; continuous berth; berth-quay crane; fairness; neighborhood search

2016-05-22.

國家自然科學(xué)基金項目(71301101)；交通運輸部建設(shè)科技項目(2015328810160)；上海自然科學(xué)基金項目(15ZR1420200)；教育部人文社會科學(xué)基金項目(15YJC630059).

1000-1190(2016)06-0860-07

TP18

A

*E-mail: yyhao@shmtu.edu.cn．