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

郝楊楊， 李軍軍， 黃有方

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

?

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

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

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

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

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

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

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

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

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

1問題描述與假設

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

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

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

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

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

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

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

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

7) 每條船都有一個最優(yōu)停靠偏好位置，偏離偏好泊位會增加在港時長；

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

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

2模型建立

2.1相關概念和符號

本模型的相關概念和符號如表1.

表1 相關概念和符號

續(xù)表1

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

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

(1)

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

1)懲罰成本f

泊位與岸橋集成調度的優(yōu)化目標包含兩方面：一是泊位的優(yōu)化，即停靠泊位應該盡可能的靠近偏好泊位，以減少集裝箱從岸橋到后方堆場的移動時間，提高岸橋作業(yè)效率，降低作業(yè)；二是服務時間的優(yōu)化，即船舶入港后應盡快靠泊作業(yè)，靠泊后盡可能在船公司規(guī)定的時間內(nèi)作業(yè)完畢并按時離港.針對這兩個目標建立了最小化總懲罰成本的多目標模型，旨在減少靠泊懲罰成本、靠泊等待時間、延遲離港時間.目標函數(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)

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

2)公平措施

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

表2 公平性設計

3鄰域搜索算法求解

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

表3 鄰域搜索算法過程

4算例實驗與分析

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

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

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

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

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

圖1 實驗1Fig.1 Experiment 1

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

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

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

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

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

圖2 實驗2Fig.2 Experiment 2

圖3 實驗3Fig.3 Experiment 3

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

圖4 實驗4Fig.4 Experiment 4

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

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

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

圖5 實驗5Fig.5 Experiment 5

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

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

圖6 實驗6Fig.6 Experiment 6

5結論

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

此外，本文還存在一些不足，如懲罰系數(shù)設置的合理性、權重分配的合理性等需要進一步研究.通過細致分析客戶對公平性滿意度的影響，調整各個公平性的權重值，探討公平性的權重體系設計對整個船舶靠泊服務公平性的影響是本文以后繼續(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]. 武漢理工大學學報， 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] 樂美龍， 劉秀玲. 基于泊位偏好與服務優(yōu)先級的泊位和岸橋分配[J]. 遼寧工程技術大學學報(自然科學版)， 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é)同調度優(yōu)化研究[J]. 武漢理工大學學報， 2011， 33(11):60-65．

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

[11] 勾 巖. 考慮船舶等待時間均衡的泊位岸橋聯(lián)合分配問題研究[D]. 大連：大連海事大學， 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.

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

1000-1190(2016)06-0860-07

TP18

A

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