基于服務損失函數的集裝箱碼頭泊位—岸橋聯合調度優化

王智靈，劉桂云,劉明濤

（寧波大學海運學院，寧波 315211）

發展戰略與項目管理

基于服務損失函數的集裝箱碼頭泊位—岸橋聯合調度優化

王智靈，劉桂云*,劉明濤

（寧波大學海運學院，寧波 315211）

面對不確定環境、多樣性和差異化服務需求，集裝箱碼頭亟需改進和優化調度方法，提高碼頭作業效率和客戶滿意度。針對集裝箱碼頭泊位與岸橋的資源分配問題，通過添加緩沖時間來吸收不確定因素對調度計劃產生的影響，引入多元服務質量損失函數建立以偏離最優靠泊位置、岸橋移動損失及在港時間損失為目標的優化模型，利用改進的遺傳算法對模型進行求解，并通過試驗算例證明了模型及算法的有效性。

不確定環境；服務損失；泊位與岸橋；客戶滿意度；遺傳算法

集裝箱港口間的競爭日益激烈，要在競爭中取得優勢，必須使港口的物流作業系統化、合理化，為船舶的裝卸提供一個良好的物流作業平臺，最有效途徑是優化港口資源的分配與調度。泊位和岸橋是集裝箱碼頭稀缺與瓶頸資源，其協同作業效能決定了碼頭的整體作業能力。因此，合理的安排泊位與岸橋，制定有效的作業調度計劃能夠提高集裝箱碼頭的作業效率和服務質量，增加客戶滿意度，同時降低碼頭的運營成本，提升競爭力。

集裝箱碼頭運作過程中存在許多不確定因素與難以預料的突發事件，使得作業不能正常運作，例如船舶到港時間的變動、岸橋操作時間的不確定等因素。因此不確定環境下的泊位與岸橋聯合調度問題的研究更加接近實際情況。Lu[1]等針對連續、動態不確定性泊位的調度問題，設計了前饋調度方案并改進反饋方案，利用啟發式算法進行了求解。陳秋雙等[2]針對不確定環境下集裝箱碼頭的擾動管理問題對作業過程中的不確定因素分類，運用隨機變量、模糊集等進行數學描述，闡述魯棒調度模型的建立和求解技術。Han等[3]考慮船舶到港時間的不確定性，建立了離散型的泊位與岸橋聯合調度模型，通過遺傳算法和抽樣仿真求解得出魯棒性的調度計劃。楊春霞[4]針對固定靠泊和柔性靠泊兩種靠泊方式，以最小化船舶在港時間和碼頭生產成本為目標，設計了一種基于可變調度深度改進型的混合重調度策略。孫彬等[5]提出一種在不確定環境下基于魯棒反應式策略的離散型泊位和岸橋調度方法，設計了一種基于CNP協商機制的岸橋實時調度模型，提高系統的抗干擾能力。桂小婭[6]考慮船舶到達時間的不確定性，建立了確定條件和不確定性條件下的前攝-反映兩階段調度模型，運用雙層循環迭代算法進行求解。粱承姬等[7]針對船舶到港時間和裝卸作業時間隨機問題，建立了以船舶在港總時間、偏離偏好泊位的懲罰時間及延緩時間之和最小為目標的混合整數規劃模型，提出一種啟發式靠泊的改進遺傳算法進行求解。

企業在生產、經營過程中，產品的質量問題給企業帶來大量的損失，目前關于質量損失的研究集中在加工制造業中零件質量的有形損失。艾延廷等[8]針對軸承組建裝配問題，以裝配質量損失最小為目標，建立了基于信噪比的多元裝配質量損失模型，采用遺傳算法進行求解?？锓襕9]等基于質量損失函數構建了加工過程的產品特性與任務載荷要求、過程特性與生產能力的關系模型，定量評估加工過程中各種隨機因素對可靠性的影響。Yadav等[10]綜合考慮了質量損失問題、全壽命周期等問題，構建多目標優化的復雜質量損失函數模型。彭和平等[11]將多重相關質量損失函數應用于公差設計中以降低生產成本。

按照Aytug[12]中的分類，現有的不確定性調度方式包括完全反應調度、前饋—反饋調度和魯棒性調度。完全反應調度在計劃中不考慮隨機性，隨著執行過程采用調派規則進行實時調度。前饋—反饋調度是指在已有調度方案基礎上，當不確定性發生時，對方案進行調整的方式。魯棒性調度在制定計劃時考慮不確定性，以求最小化主要不確定因素對實際運行結果帶來的影響。在魯棒性調度中，通過添加緩沖時間來吸收不確定性的方法運用十分廣泛，但對于在不確定條件下的泊位與岸橋聯合調度問題，通過添加緩沖時間方式的魯棒性調度研究很少。

在碼頭作業中，最常見的兩種不確定因素是船舶到達時間和岸橋的操作時間。因此本文從這兩種不確定因素出發，通過添加緩沖時間吸收不確定因素，建立基于客戶滿意度的不確定環境下泊位與岸橋聯合調度模型，增強調度方案的魯棒性。引入多元服務質量損失函數作為目標函數來度量碼頭服務質量的損失，具體的服務損失包括船舶在港時間的損失、偏離最佳靠泊位置的損失以及岸橋移動損失，建立在保障船舶總體滿意度條件下，碼頭服務損失最小的調度模型并采用改進的遺傳算法進行求解，使調度結果更優。

1 多元服務質量損失函數

在衡量客戶滿意度水平時，引入田口質量損失函數。田口玄一[13]將質量損失定義為產品產出后對社會的損失，包括直接損失和間接損失。質量特性值偏離目標值越大，造成的損失就越大。為了定量描述產品質量損失，田口提出了“質量損失函數”的概念，并以信噪比來衡量設計參數的穩健程度。田口質量損失函數用一個二次損失函數來估計當產品質量特性值偏離目標值時的產品質量損失。令L（Y）為由質量指標Y偏離目標值而引起的經濟損失，m為顧客目標值。若L（Y）在Y=m存在二階導數，則L（Y）在Y=m附近按泰勒級數展開，可以近似地表示為

式中:Y=m時損失最小且為零，即L（m） = L′（m） = 0，損失函數可以表示為

式中:K為質量損失系數，其中K = L"（m）/2!，不依賴Y的常數。

由于二次質量損失函數式（2）中的質量損失系數K是由服務質量特性所造成的經濟損失所決定，然而確定該經濟損失是非常困難的，田口選擇一個使質量損失函數對所采用的單位不敏感的質量損失系數，令并提出了無量綱的標準化質量損失函數

式中:TU、TL分別為產品質量特征的公差上下限。

標準化的質量損失函數是無量綱，所以質量損失函數可以相加求和。集裝箱碼頭客戶服務損失具有田口損失函數的特性，故多元服務質量損失函數可表示為

2 問題描述

在集裝箱碼頭的實際運作中，多種不確定因素會影響船舶泊位與岸橋調度，主要表現在船舶到達時間和岸橋裝卸作業的不確定性等。針對不同特點的不確定性的描述，最常用的方法有兩種：一種是不確定性參數服從概率分布，即通過分析運營數據統計出參數所服從的概率分布，通常情況下采用隨機變量描述調度系統的不確定性，如各作業任務執行時間的不確定性和任務到達時間的不確定性。另一種是不確定性參數處于某一區間，即通過統計分析運營數據，整理出參數所處的某個區間，用區間表示參數的不確定性。本文綜合這兩種方法處理泊位與岸橋調度中的不確定性。假設船舶的實際到港時間服從以計劃到港時間為均值的均勻分布，即為船舶到港時間的變動范圍。同時，裝卸作業時間Bi也是服從岸橋平均作業時間為均值的均勻分布。

為了增加調度計劃的魯棒性，通過添加緩沖時間的方法吸收不確定性因素帶來的影響，根據船舶到港時間的變動范圍來確定緩沖時間的最大值，即φmax= 2α，α為船舶到港時間的標準差，由船舶到港時間的變動范圍ΔCi得出。φ存在兩種情況，φ > 0表示船舶延遲到港，即實際到港時間在[Ci,Ci+ΔCi]范圍內，則給船舶添加的緩沖時間為正數，φ < 0表示船舶提前到港，即實際到港時間在期望到港時間范圍內，則添加的緩沖時間為負數。如果緩沖時間添加的足夠大，那么能夠吸收的不確定性也就比較大，計劃的魯棒性就更強，調度計劃的魯棒性可以用緩沖時間的大小來體現，因此在目標函數中加入了最大化緩沖時間。

考慮動態、連續泊位下的調度問題，泊位是連續岸線，能夠有效利用泊位資源。引入靠泊損失，如果偏離最優靠泊位置就會增加作業成本。引入岸橋移動損失，岸橋可在船舶間進行移動裝卸，提高裝卸利用率，但頻繁的移動會增加過多岸橋移動成本?？蛻舻臐M意度用在港時間損失來衡量，即所有在港船舶在期望時間內離港，損失越小，客戶的滿意度越高。

3 調度模型

3.1 模型假設

為了更好的建立模型，根據問題的特性和現實約束，提出以下假設：

（1）連續泊位各處均符合船舶靠泊的水深條件；（2）船舶到港后才進行靠泊服務，船舶靠泊和離港操作時間不計；（3）遵循一次靠泊原則且每艘船舶都有自己的最優靠泊位置；（4）岸橋均位于同一軌道上，從左至右依次編號；（5）岸橋移動不能交叉跨越，兩臺岸橋之間存在安全距離；（6）岸橋的移動時間忽略不計；（7）某一時刻，岸線上所有船舶的貝位從左至右依次編號；（8）每艘船舶都有最小和最大岸橋數的限制。

3.2 符號定義

3.2.1 集合與參數

V={1,...,n}，計劃期到港船舶集合，用i和j代表不同的船舶編號；Q={1,...,q}，碼頭可用岸橋集合，q為岸橋號，k為岸橋數；T={1,...,t}計劃期時間段集合，t為時間段號；Ωi為船舶i的任務量，i∈V；L為碼頭岸線總長度；li為船舶i的長度，包括前后的安全距離，i∈V；pbi為船舶i的最優靠泊位置，i∈V；Ci為船舶i的計劃到港時間，i∈V；Ai為船舶i的實際到港時間，服從以計劃到港時間為均值的均勻分布，i∈V；Bi為船舶i單個岸橋的處理時間，服從以平均處理時間為均值的均勻分布，i∈V；Di為船舶i的期望離港時間，i∈V；rimin和rimax為船舶i所需最小和最大岸橋數，i∈V；v為單個岸橋單位時間的作業效率；λ1，λ2，λ3分別為在港時間損失、偏離最優靠泊位置損失、岸橋移動損失的權重。

3.2.2 決策變量

bi為船舶i靠泊位置；bli為船舶i向左偏離最優靠泊位置的偏離差；bri為船舶i向右偏離最優靠泊位置的偏離差；Si為船舶i的開始服務時間；ei為船舶i結束服務的離港時間；xij∈(0,1)，若船舶i在空間上完全停靠在船舶j之前則為1，否則為0；Qit為t時刻分配給船舶i的岸橋數量；yitq∈(0,1)，若船舶i在t時間內被岸橋q服務則為1，否則為0；changeit為船舶i在t時刻相對于t-1時刻岸橋數目增加的數量；ji為船舶i的延緩時間；σ∈(0,1)，若船舶i有k個岸橋服務且延緩時間為t則為1，否則為0；busyit：判斷船舶i在t時刻是否處于作業狀態；di∈(0,1)，若船舶i的離港時間大于期望離港時間則為1，否則為0。

3.3 目標函數

建立如下基于服務損失函數的調度模型，其目標函數為

目標函數（5）第一部分，表示顧客的在港時間服務損失，期望離港時間、實際到港時間為船舶在港時間服務質量特征偏差的上下限；第二部分，表示船舶偏離最優靠泊位置的服務損失，考慮到是連續泊位取1/2岸線長度作為靠泊服務質量特征的偏差；第三部分，岸橋的移動損失，每艘船的裝卸岸橋有最大最小數量限制，可作為岸橋移動服務質量特征偏差的上下限；第四部分表示添加的延緩時間的絕對值最大。

3.4 約束條件

式（6）邊界約束，所有船舶都必須靠泊在碼頭岸線范圍內

式（7）和式（8）確保沒有兩艘船舶在同一地點同一時刻被服務

式（9）表示船舶到港后才能進行作業

式（10）確保所有船舶的任務量都能得到滿足

式（11）表示任意時間段內分配給所有船舶的總數滿足碼頭可用岸橋總數

式（12）表示岸橋只有滿足此要求才可開始作業

式（13）定義每艘船任務處理時間

式（14）表示每一岸橋在同一時刻只能為一艘船舶服務

式（15）表示某時刻服務于同一船舶的岸橋數量

式（16）限制分配給同一船舶的岸橋是連續的且不能跨越

式（17）表示船舶在任意時間段內分配到的岸橋數目必須符合碼頭剩余可用岸橋數量的限制

式（18）定義某一時刻到下一時刻岸橋數量的增加數量

式（19）保證以岸橋作業結束時間為船舶的實際離港時間

式（20）表示延緩時間內船舶的岸橋數不變

式（21）保證船舶任務量能夠滿足且延緩時間內該船舶還占用泊位和岸橋資源

式（22）和（23）定義決策變量

式（24）定義0-1變量

4 算法求解

4.1 個體編碼設計

采用自然數編碼方式，染色體的每一列代表服務船舶的相關信息，染色體編碼如表1所示。以第二排為例，船舶2的?？课恢脼?50，分配的岸橋數量為3，添加的緩沖時間為0。

4.2 種群初始化

根據集裝箱船舶的到港總數V，采用隨機生成1到V間的隨機整數。對于連續泊位的問題，泊位是一條連續的岸線，因此設定船舶在岸線上靠泊的位置為船舶的最左端。船舶靠泊位置部分的染色體在[0,L]范圍內隨機產生。根據各船舶所需的岸橋數目的需求，分配的岸橋數量即岸橋部分的染色體在[rimin,rimax]之間隨機產生。添加的緩沖時間部分的染色體雖然也是隨機產生，但是受到船舶實際到港時間的約束。船舶實際到港時間服從以計劃到港時間為均值的均勻分布，即船舶在[Ci-ΔCi, Ci+ΔCi]時間段內隨機到達，船舶有可能提前或者延遲到港。因此緩沖部分染色體的生成步驟為：判斷船舶i的到港時間Ai與計劃到港時間Ci的關系，若Ai≥Ci，則在[0, φi]隨機產生；若Ai≤Ci，則在[-φi,0]隨機產生。

4.3 適應度函數

根據目標函數是最小化問題，采用如下公式計算種群中的個體適應度值

式中：c為大于0的數。由于目標函數始終為正值，所以取c=0。通過這個適應度函數可以看出服務損失Q（xi）越小，適應度值f(xi)越大，在選擇操作中被選中的概率就越大。

表1 染色體編碼說明Tab.1 Chromosome representation

4.4 遺傳操作

采用錦標賽法對個體進行選擇操作。關于交叉和變異，本文采用算數交叉的方式和逆轉變異的方法。改進遺傳算法中采用自適應交叉概率Pc和變異概率Pm，當種群個體適應度趨于一致或局部最優解時，交叉和變異概率增加以跳出局部最優解；當群體適用度比較分散時。交叉和變異概率減少以利于優良個體的生存。自適應的交叉和變異的表達式為

式中：Pc1,Pc2,Pm1,Pm2分別為預先定義的參數；f為進行交叉的兩個個體中較大的適應度值；f’為變異個體的適應度值；favg為每代種群平均適應度值；fmin為每代種群最小適應度值。

5 算例分析

根據某碼頭的統計數據設計算例，評價模型和算法的有效性。具體的數據為：碼頭岸線長度為1 500 m，配有13臺岸橋，單個岸橋平均作業效率為30 TEU/（臺.時）。計劃時間周期為24 h，計劃期內到港船舶總數為6艘。船舶具體信息見表2。

表2 船舶參數數據Tab.2 Data of the ships

為了保證碼頭作業的安全性，將船舶前后的安全距離取15 m，則船舶li的長度就包含了船長和安全距離。船舶的實際到港時間，服從以計劃到港時間為均值的均勻分布，即到港時間服從[Ci-2.5,Ci+2.5]分布，通過計算得出相應的標岸橋的作業時間Bi服從以平均作業時間10.5小時為均值的均勻分布，即[6,15]分布。船舶實際信息如表3所示。

表3 船舶實際信息Tab.3 Actual information of the ships

在進行遺傳操作時，選擇Pc1=0.7,Pc2=0.3，Pm1=0.1,Pm2=0.07，根據改進的遺傳算法計算后輸出數據，計算的優化過程如圖1所示，調度的結果如表4所示。

圖1 算法進化收斂圖Fig.1 Convergence of the algorithm

表4 泊位-岸橋調度結果Tab.4 Results of berth and quay-crane scheduling

6 結 論

集裝箱碼頭的調度過程中存在諸多不確定因素，本文研究了在不確定環境下連續泊位與岸橋的聯合調度問題，引入了多元服務質量損失函數建立優化模型，并采用改進的遺傳算法對模型進行了求解。為驗證模型的正確性，結合集裝箱碼頭的統計數據進行了算例分析，得到了當到港船舶為6艘時的調度計劃，在合理的時間內得了出了滿意的解，使船舶在港總服務損失最小，進而提高客戶滿意度。計算結果表明，在目標函數中加入最大化的緩沖時間可以吸收作業中的不確定性，使方案更加可行、符合實際。

除此之外，在集裝箱碼頭調度中，還應考慮到集卡、場橋及堆場集成調度等問題，在不確定因素的影響下合理地利用碼頭的各類資源，充分考慮各環節間的聯系，制定合理的聯合調度優化策略，這也是下一步的研究方向。

參考文獻：

[1] Lu Z, LEE L H, CHEW E P. A decision model for berth allocation under uncertainty [J]. European Journal Research,2011,212（1）：54-68.

[2] 陳秋雙,杜玉泉,徐亞.不確定環境下集裝箱碼頭的擾動管理[J].物流技術.2010,2（Z1）：1-5. CHENG Q S, DU Y Q, XU Y. Disturbance Management of Container Ports under Uncertain Circumstances [J]. Logistics Technology, 2010, 2(Z1):1-5.

[3] Han X, Lu Z, X L, A .procative approach foe simulataneous berth and quay crane scheduling problem with stochasic arrival and handling time. European Journal of Operational Research [J]. 2010,207：1 327-1 340.

[4] 楊春霞.不確定環境下的集裝箱碼頭泊位-岸橋調度優化研究[D].大連:大連海事大學,2011.

[5] 孫彬,孫俊清,陳秋雙.基于魯棒反應式策略的泊位和岸橋聯合調度[J].系統工程理論與實踐，201（4）：1 076-1 083. SUN B, SUN J Q, CHEN Q S. Integrated scheduling for berth and quay cranes based on robust and reactive policy [J]. Systems Engineering-Theory & Practice, 2013, 33(4):1 076-1 083.

[6] 桂小婭.不確定性條件下集裝箱碼頭泊位與岸橋集成調度計劃建模與優化[D].上海:上海交通大學，2013.

[7] 粱承姬,吳宇.不確定環境下集裝箱碼頭泊位與岸橋聯合調度[J].計算機工程與應用，2015（11）:1-9. LIANG C J, WU Y. Simultaneous berth and quay crane scheduling under uncertainty environments in container terminals [J]. Computer Engineering and Applications, 2015（11）:1-9. CNKI網絡優先出版：2015-11-04, http://www.cnki.net/kcms/detail/11.2127.TP.20151104.1600.002.html

[8] 艾延廷,田晶,高紅池.基于多元質量損失與遺傳算法的裝配質量優化技術研究[J].中國機械程，2012,23（10）：1 161-1 164. AI Y T, TIAN J, GAO H C. Study on Assembly Quality Optimization Techniques Based on Multivariate Quality Loss and Genetic Algorithm [J]. China Mechanical Engineering, 2012, 23(10):1 161-1 164.

[9] 匡芬,戴偉,陳亮，等.基于質量損失的加工過程可靠性評估方法研究和應用[J]. 計算機集成制造統,2015,21（6）：1 571-1 574. KUANG F, DAI W, CHEN L, et al. Assessment method and applications for reliability manufacturing process based on quality loss [J]. Computer Integrated Manufacturing Systems, 2015,21(6):1 571-1 574.

[10] Yadav O P, Bhamare S, Rathore A. Reliability-based robust design optimization: a multi-objective framework using hybrid quality loss function [J]. Quality and Reliability Engineering International, 2010, 26（1）: 27-41.

[11] 彭和平,蔣向前,徐振高，等.基于多重相關特征質量損失函數的公差優化設計[J].中國機械工程,2008,19(5):590-530. PENG H P, JIANG X Q, XU Z G, et al. Optimal Tolerance Design Based on the Quality Loss Function with Multi-correlated Characteristics [J].China Mechanical Engineering, 2008,19(5):590-530.

[12] Aytug H, Lawley M A, McKay K， et al. Ececuting proudution schhdules in the face of uncertainties: A review and some future directions[J]. European Journal of Operational Research，2005,161：86-110.

[13] 田口玄一[日].魏錫祿,王和福譯.質量工程學概論[M]. 北京:中國對外翻譯出版公司,1985.

Optimization of berth and quay-crane integrated scheduling in container terminal based on service loss function

WANG Zhi-ling, LIU Gui-yun＊, LIU Ming-tao
(Faculty of Maritime and Transportation, Ningbo University, Ningbo 315211, China)

With the emergence of the uncertain environment, diversity and difference services, it needs to make an optimization of berth quay-crane integrated scheduling methods in container terminal to improve the efficiency and customer satisfaction. According to the resource allocation problem of berth and quay-crane in container terminal, by adding a buffer time to absorb the impact of uncertain factors on scheduling, based on the multiple service quality loss function, an optimization model was established aiming at the deviation of the optimum berth loss, move loss of quay-crane and ship time loss in port. Moreover, the improved genetic algorithm was used to solve the model, and the validity of the model and algorithm was proved by experiments.

uncertain environment; service loss; berth and quay-crane; customer satisfaction; genetic algorithm

U 651

A

1005-8443(2017)03-0313-07

2016-11-08；

2017-03-20

寧波市自然基金項目（2016A610074）；浙江省軟科學項目（2015C25039）；寧波港口經濟圈文化創新團隊

王智靈（1991-），女，陜西寶雞人，碩士研究生，主要從事港口及物流管理方面的研究。

*通信作者：劉桂云（1972-）, 女, 滿族, 遼寧鞍山人, 博士，教授, 主要從事港口和物流管理方面工作。E-mail: liuguiyun@nbu.edu.cn

Biography:WANG Zhi-ling（1991-）, female, master student.