基于懲罰函數的集裝箱碼頭連續泊位-岸橋聯合調度

劉桂云， 陳珊珊， 張小莉， 劉明濤

(寧波大學 海運學院， 浙江 寧波 315211)

基于懲罰函數的集裝箱碼頭連續泊位-岸橋聯合調度

劉桂云， 陳珊珊， 張小莉， 劉明濤

(寧波大學 海運學院， 浙江 寧波 315211)

為對連續泊位與岸橋聯合調度問題進行求解，從碼頭運營者的角度出發，以最小化懲罰為優化目標建立數學模型，設計一種嵌套式遺傳算法。在客戶滿意率最大的情況下，求得船舶的靠、離泊時間和位置及最優裝卸序列。通過進行數值模擬案例分析，驗證該優化方法可在提高客戶滿意率的同時，縮短船舶在港時間，對集裝箱碼頭生產運作實踐具有一定的參考價值。

交通運輸經濟學； 集裝箱碼頭； 泊位與岸橋； 聯合調度； 遺傳算法； 懲罰函數

Abstract: An optimization method of unified scheduling for continuous berth and quay-crane is formulated to minimize the punishment from the terminal operators' perspective, and a nested genetic algorithm is designed to solve this problem. The time of docking and departure, berthing and the best loading/unloading sequence of ships are solved for the highest customer satisfaction rate. The optimization method is verified with a representative case, which indicates that the method can improve the degree of customer satisfaction as well as decrease the birthing time of ships. The method can be a reference of some kind for the actual production of the container terminal.

Keywords: traffic transport economics; container terminal; berth and quay-crane; unified scheduling; genetic algorithm; penalty function

研究集裝箱碼頭生產調度問題對提高碼頭服務能力和運營效率，進而提升全球物流效率具有重要意義。泊位與岸橋調度是集裝箱碼頭調度的核心內容，國內外很多學者都對此進行過研究，提出了具有實踐指導意義的優化方法。一些成熟的理論研究己應用于碼頭實際生產作業中。

LI等[1]以最小化船舶在港時間為目標，將泊位與岸橋分配作為一個并行調度問題建模求解；GUAN等[2]在此基礎上建立以最小化權重任務的完成時間為目標的調度模型。韓俊等[3]和靳志宏等[4]研究泊位與岸橋聯合調度問題，假設服務于一艘船舶的所有岸橋必須同時結束，運用免疫遺傳算法求解模型。AK等[5]引入禁忌搜索法，研究以最小在港時間和避免船舶延遲離港的懲罰費用為目標的泊位與岸橋聯合調度模型。LIANG等[6]以最小化所有岸橋工作時間、等待時間和延遲時間為目標函數建立泊位與岸橋聯合調度模型，并采用遺傳算法求解，得出靠泊位置、時間和岸橋分配數量。BIRGER等[7]考慮岸橋作業時間超長的懲罰、偏離最佳靠泊位置的懲罰和岸橋移動的懲罰，引入滾動時間窗和船舶優先級研究聯合調度問題。樂美龍等[8]建立連續泊位與岸橋分配模型，并運用Memetic求解算法。 YANG等[9]提出一種解決多用戶集裝箱碼頭泊位與岸橋分配問題的有效方法，根據泊位與岸橋的交互關系建立泊位與岸橋耦合模型，并設計改進遺傳算法。桂小婭等[10]以最小化船舶在港時間為目標建立連續泊位和岸橋聯合調度模型，并提出一種雙層循環迭代求解算法。

此外，還有一些學者對岸橋裝卸調度進行研究。趙坤強等[11]分別研究分配泊位和岸橋數量模型及岸橋裝卸調度模型。余劉海等[12]在計劃周期內研究泊位分配與岸橋在任務間的動態調度，建立基于任務的連續泊位與岸橋協調調度模型。YAVUZ等[13]等研究泊位分配、岸橋分配(數量)和岸橋裝卸調度問題，設計一種能求解大規模問題的算法。楊華龍等[14]建立以最小化船舶在港時間和最大化岸橋利用率為目標的連續泊位與岸橋聯合調度模型。呂賽賽等[15]依據作業量確定船舶的優先權，建立基于船舶優先權的泊位與岸橋耦合優化模型。

已有研究主要針對的是岸橋數量分配，對具體岸橋在任務間調度的研究較少，而在實際生產調度中，只有合理安排特定岸橋的作業順序才能保障裝卸效率；同時，已有研究大多以最小化在港時間為目標建立數學模型，考慮因素較為單一，無法滿足客戶多方面的需求。對此，引入懲罰函數，從提高客戶滿意度的角度建立泊位與岸橋聯合調度模型。具體懲罰包括對超出客戶最佳離港時間的懲罰、對偏離最佳靠泊位置的懲罰和對岸橋移動的懲罰。

1 問題描述

1.1問題假設

研究泊位與岸橋聯合調度問題時，不僅要考慮靠泊時間和位置的最優，還要考慮岸橋對裝卸時間的影響及岸橋能在多艘船舶間動態調度。根據問題的特性和現實約束，為便于分析，提出以下假設： 連續泊位各處均符合船舶靠泊水深條件；船舶靠泊和離港操作時間不計； 岸橋位于同一軌道，從左至右依次編號，兩臺岸橋之間存在安全距離，假定為一個貝位； 岸橋水平移動時間忽略不計； 由于船方要求和船舶大小的限制，每艘船舶都有最小和最大岸橋數限制； 船舶停泊期間不會移動； 每艘船舶都有其最優靠泊位置； 某一時刻，岸線上所有船舶的貝位從左至右依次編號。

1.2符號定義

為詳細描述連續泊位與岸橋聯合調度的過程，對相應符號進行定義。

1.2.1集合符號

V={1,2,…,v}為等待靠泊的船舶；Q={1,2,…,k}為岸線可用的岸橋，并從岸線左端開始依次編號，岸橋總數為|Q|；T={0,1,…,t}為計劃期時間，是以1 h為單位的離散時間；L={0,1,…,l}為海岸線長度，是以100 m為單位的離散距離；Ωi={1,2,…,n}為船舶i上的所有任務。

1.2.2參數符號

1.2.3決策變量

2 調度模型

2.1目標函數

建立目標函數最小化懲罰值，分為3個部分： 第1部分涉及船舶最佳離港延遲懲罰系數，每艘船舶都有其最佳離港時間，船舶作業時間可看成在港時間； 第2部分涉及船舶靠泊位置和船舶偏離最優靠泊位置的懲罰，每艘船舶都有其最優靠泊位置，在最優位置對應的出口堆場區和進口堆場區集卡運輸成本最小，一旦偏移將導致集卡運輸距離增加； 第3部分是對每艘船舶分配的岸橋數量增加的懲罰。由于岸橋的移動會增加岸橋的移動成本，因此限定岸橋在船舶之間大范圍移動，設置一艘船舶岸橋數量增加的懲罰。具體表達為

(1)

2.2約束條件

約束條件表達為

(2)

(3)

(4)

Si≥Ci

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

i=j,k1≠k2

(13)

i≠j,k1≠k2,n1≠n2

(14)

(15)

changeit≥Qit-Qit-1

(16)

pli=pbl(i)-dli+dri

(17)

pli+l(i)≤L

(18)

pli+l(i)-L(1-yij)≤plj

(19)

busyit+busyjt≤1+yij+yji

(20)

(21)

式(2)～式(21)中：?i,j∈V;?k∈Q;?t∈T;?n∈Ωi;?k1,k2∈Q;?n1,n2∈Qi。式(2)定義岸橋在第K期的位置(岸線方向)；式(3)定義岸橋在第K期開始空閑的時刻；式(4)定義岸橋服務單個任務所需要的時間；式(5)確保船舶作業開始時間在到達之后；式(6)定義船舶作業的結束時間；式(7)為碼頭岸橋總數量的約束；式(8)表示岸橋只有在滿足上述要求時才可開始作業；式(9)表示一個岸橋在某一時刻只能為一項任務服務；式(10)定義任務的開始時間；式(11)定義任務的結束時間；式(12)表示一個岸橋只能為一艘船舶服務；式(13)和式(14)限制岸橋不可跨越作業；式(15)定義某時刻服務于同一船舶的岸橋數量；式(16)定義某一時刻到下一時刻岸橋數量的增加量；式(17)通過左偏差和右偏差定義岸橋靠泊位置；式(18)確保所有的船舶在岸線內靠泊；式(19)和式(20)確保沒有兩艘船舶在同一地點、同一時刻被服務。

3 求解算法

由于模型涉及的決策變量較多，這里將其求解過程分為泊位分配和岸橋分配與調度2個部分，用一種嵌套式循環算法求解。

1) 內循環1用于求解泊位分配問題，運用遺傳算法迭代循環求解泊位調度最優值。

2) 內循環2用于求解岸橋分配與調度問題，運用遺傳算法迭代循環求最優值。

3) 外循環算法主要用于傳遞2個內循環之間的參數，實現2個問題的銜接；此外，還可通過2個內循環的迭代和反饋不斷改進泊位與岸橋聯合調度解的質量和計劃的性能。

嵌套式循環算法流程見圖1，設計思路如下。

圖1 嵌套式循環算法流程

1) 初始化：k=1。

2) 根據每艘船舶的裝載量和卸載量，按一定的作業效率設定每艘船舶作業需要的時間。

3) 根據設定的作業時間，運用遺傳算法求解泊位計劃，獲得每艘船舶的靠泊時間和位置。

4) 根據獲得的泊位計劃，把內循環1中的結果參數傳遞到內循環2中，運用遺傳算法求解岸橋分配與調度，獲得岸橋作業順序。

5) 判斷步驟“4)”獲得的岸橋調度結果是否正確、合理，若“是”，進入步驟“6)”，否則重新設定初始船舶作業時間，重復步驟“3)”。

6) 判斷外循環的迭代次數是否滿足設定次數G，若“是”，進入步驟“7)”，否則根據當前的岸橋分配與調度結果更新船舶作業時間，重復步驟“3)”。

7) 當迭代次數滿足要求時，退出循環，輸出最終解。

步驟“2)”中設定初始船舶作業時間時，令每艘船舶的作業時間=船舶總作業量/岸橋平均作業效率。步驟“5)”中重新設定初始船舶作業時間時，令每艘船舶的作業時間=船舶總作業量/岸橋平均作業效率×(0.9～1.1)。步驟“6)”中在更新船舶作業時間的過程中， 船舶作業時間=∑每一貝位作業時間=∑(單循環次數×岸橋單循環效率+雙循環次數×岸橋雙循環效率)。

4 數值計算

以某集裝箱碼頭生產作業為例進行數值計算。該碼頭前沿岸線長1 500 m，配有13臺岸橋。模擬該碼頭24 h內靠泊的5艘大型集裝箱船數據，并設定岸橋跨船移動的懲罰系數ε=20。5艘單貝位裝卸類型或多貝位裝卸類型集裝箱船的模型參數數據見表1。案例分析中作以下假設。

表1 模型參數數據

1) 每艘集裝箱船按構造分為船頭、船尾和中間等3個部分，且其裝卸量均勻分成4份，船頭和船尾各占1份，中間部分占2份，裝卸量隨機分布于每一貝位，每一貝位的裝卸量隨機分布于每一堆垛。

2) 岸橋平均作業效率為30 TEU/(臺·h)，岸橋單循環效率為28 TEU/(臺·h)，岸橋雙循環效率為32 TEU/(臺·h)。

根據表2及已知的岸橋單循環和雙循環作業效率，可得到調度模型中每一單位任務作業時間。此外，根據優化調度模型和算法可獲得5艘船舶的靠泊位置、離泊時間、所分配岸橋數量和岸橋作業任務。

表2 船舶每一貝位的岸橋作業次數

用MATLAB計算，遺傳算法迭代到400代時得到最小懲罰189，算法進化收斂圖見圖2，岸橋服務的任務見表3(表中數值為岸橋編號)。計算得出船舶靠泊位置、最后離港時刻和三部分懲罰值。調度優化結果見表4(為便于計算，離港時刻取整數)。 所設計的泊位與岸橋聯合調度優化方法與傳統集裝箱碼頭作業方式相比，在保證碼頭作業最小懲罰的基礎上，每艘船舶的作業時間都能得到相應優化。

圖2 算法進化收斂圖

貝位號船舶1船舶2船舶3船舶4船舶5118411121841113195111429511252962126296212721072128310731293108313103118413114118413124118413

表4 調度優化結果

5 結束語

基于懲罰函數的連續泊位與岸橋聯合調度模型具有復雜性特點，這里改進傳統的遺傳算法，提出一種嵌套式的遺傳算法。由案例的數值計算結果可知，該模型和算法在保證客戶滿意率最大的情況下，使每艘船舶的在港時間都得到一定程度減少。在該模型中，綜合考慮了客戶滿意率的提升問題，未來將基于客戶滿意率和船舶在港時間等因素建立多目標優化模型，進一步提高碼頭的運營效率和服務水平。

[1] LI C L，CAI X，LEE C Y. Scheduling with Multiple-Job-On-One-Processor Pattem[J]．IE Transactions，1998，30：433-445．

[2] GUAN Y，XIAO W Q，CHEUNG R K，etal．A Multiprocessor Task Scheduling Model for Berth Allocation：Heuristic and Worst-Ease Analysis[J]．Operations Research Letters，2002，30(5)：343-350．

[3] 韓駿，孫曉娜，靳志宏．集裝箱碼頭泊位與岸橋協調調度優化[J]．大連海事大學學報，2008，34(2)：117-121.

[4] 靳志宏，徐奇，韓駿，等．集裝箱碼頭泊位與岸橋聯合動態調度[J]．中國科技論文在線，2011，6(11)：809-814．

[5] AK A，ERERA A L．Simultaneous Berth and Quay Crane Scheduling for Container Ports[R]．Georgia Institute of Technology，2006．

[6] LIANG Chengji， HUANG Youfang，YANG Yang. A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning[J]. Computers & Industrial Engineering, 2009, 56: 1021-1028.

[7] BIRGER R W，DULLAERT R，SCHAEREN V．An Enriched Model for the Integrated Berth Allocation and Quay Crane Assignment Problem[J]．Expert Systems with Applications，2011，38：14136-14147．

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

[9] YANG Chunxia， WANG Xiaojun， LI Zhenfeng. An Optimization Approach for Coupling Problem of Berth Allocation and Quay Crane Assignment in Container Terminal[J]. Computers & Industrial Engineering, 2012, 63:243-253.

[10] 桂小婭，陸志強，韓笑樂. 集裝箱碼頭連續型泊位與岸橋集成調度[J]. 上海交通大學學報，2013，47(2)：226-229.

[11] 趙坤強，韓曉龍，梁承姬. 連續泊位下集裝箱碼頭港口泊位與橋吊協同調度優化研究[J]. 武漢理工大學學報，2011,33(11)：60-65.

[12] 余劉海，龐洪靜. 集裝箱碼頭連續泊位與岸橋聯合調度[J]. 科技信息，2013(9)：196-197.

[13] YAVUZ B T, TASKIN Z C, NECATI A,etal. Optimal Berth Allocation and Time-Invariant Quay Crane Assignment[J]. European Journal of Operational Research in Container Terminals, 2013, 1-14.

[14] 楊華龍,滕川川.基于擠壓算法的集裝箱碼頭泊位與岸橋聯合調度優化[J].大連海事大學學報，2014,40(3):8-12.

[15] 呂賽賽，韓曉龍. 基于船舶優先權的泊位與岸橋耦合優化[J]. 河南科學， 2014,32(4)：531-536.

UnifiedSchedulingforContinuousBerthandQuay-CraneBasedonPenaltyFunction

LIUGuiyun，CHENShanshan，ZHANGXiaoli，LIUMingtao

(Maritime College， Ningbo University， Ningbo 315211, China)

2015-10-29

浙江省軟科學項目(2015C25039)；浙江省教育廳項目(pd2013097)

劉桂云(1972—)，女，遼寧鞍山人，教授，研究方向為港口與物流管理。E-mail:liuguiyun@nbu.edu.cn

1000-4653(2016)01-0115-05

U656.1+35

A