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

(寧波大學(xué) 海運(yùn)學(xué)院， 浙江 寧波 315211)

基于懲罰函數(shù)的集裝箱碼頭連續(xù)泊位-岸橋聯(lián)合調(diào)度

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

(寧波大學(xué) 海運(yùn)學(xué)院， 浙江 寧波 315211)

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

交通運(yùn)輸經(jīng)濟(jì)學(xué)； 集裝箱碼頭； 泊位與岸橋； 聯(lián)合調(diào)度； 遺傳算法； 懲罰函數(shù)

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

研究集裝箱碼頭生產(chǎn)調(diào)度問題對(duì)提高碼頭服務(wù)能力和運(yùn)營效率，進(jìn)而提升全球物流效率具有重要意義。泊位與岸橋調(diào)度是集裝箱碼頭調(diào)度的核心內(nèi)容，國內(nèi)外很多學(xué)者都對(duì)此進(jìn)行過研究，提出了具有實(shí)踐指導(dǎo)意義的優(yōu)化方法。一些成熟的理論研究己應(yīng)用于碼頭實(shí)際生產(chǎn)作業(yè)中。

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

此外，還有一些學(xué)者對(duì)岸橋裝卸調(diào)度進(jìn)行研究。趙坤強(qiáng)等[11]分別研究分配泊位和岸橋數(shù)量模型及岸橋裝卸調(diào)度模型。余劉海等[12]在計(jì)劃周期內(nèi)研究泊位分配與岸橋在任務(wù)間的動(dòng)態(tài)調(diào)度，建立基于任務(wù)的連續(xù)泊位與岸橋協(xié)調(diào)調(diào)度模型。YAVUZ等[13]等研究泊位分配、岸橋分配(數(shù)量)和岸橋裝卸調(diào)度問題，設(shè)計(jì)一種能求解大規(guī)模問題的算法。楊華龍等[14]建立以最小化船舶在港時(shí)間和最大化岸橋利用率為目標(biāo)的連續(xù)泊位與岸橋聯(lián)合調(diào)度模型。呂賽賽等[15]依據(jù)作業(yè)量確定船舶的優(yōu)先權(quán)，建立基于船舶優(yōu)先權(quán)的泊位與岸橋耦合優(yōu)化模型。

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

1 問題描述

1.1問題假設(shè)

研究泊位與岸橋聯(lián)合調(diào)度問題時(shí)，不僅要考慮靠泊時(shí)間和位置的最優(yōu)，還要考慮岸橋?qū)ρb卸時(shí)間的影響及岸橋能在多艘船舶間動(dòng)態(tài)調(diào)度。根據(jù)問題的特性和現(xiàn)實(shí)約束，為便于分析，提出以下假設(shè)： 連續(xù)泊位各處均符合船舶靠泊水深條件；船舶靠泊和離港操作時(shí)間不計(jì)； 岸橋位于同一軌道，從左至右依次編號(hào)，兩臺(tái)岸橋之間存在安全距離，假定為一個(gè)貝位； 岸橋水平移動(dòng)時(shí)間忽略不計(jì)； 由于船方要求和船舶大小的限制，每艘船舶都有最小和最大岸橋數(shù)限制； 船舶停泊期間不會(huì)移動(dòng)； 每艘船舶都有其最優(yōu)靠泊位置； 某一時(shí)刻，岸線上所有船舶的貝位從左至右依次編號(hào)。

1.2符號(hào)定義

為詳細(xì)描述連續(xù)泊位與岸橋聯(lián)合調(diào)度的過程，對(duì)相應(yīng)符號(hào)進(jìn)行定義。

1.2.1集合符號(hào)

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

1.2.2參數(shù)符號(hào)

1.2.3決策變量

2 調(diào)度模型

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

建立目標(biāo)函數(shù)最小化懲罰值，分為3個(gè)部分： 第1部分涉及船舶最佳離港延遲懲罰系數(shù)，每艘船舶都有其最佳離港時(shí)間，船舶作業(yè)時(shí)間可看成在港時(shí)間； 第2部分涉及船舶靠泊位置和船舶偏離最優(yōu)靠泊位置的懲罰，每艘船舶都有其最優(yōu)靠泊位置，在最優(yōu)位置對(duì)應(yīng)的出口堆場(chǎng)區(qū)和進(jìn)口堆場(chǎng)區(qū)集卡運(yùn)輸成本最小，一旦偏移將導(dǎo)致集卡運(yùn)輸距離增加； 第3部分是對(duì)每艘船舶分配的岸橋數(shù)量增加的懲罰。由于岸橋的移動(dòng)會(huì)增加岸橋的移動(dòng)成本，因此限定岸橋在船舶之間大范圍移動(dòng)，設(shè)置一艘船舶岸橋數(shù)量增加的懲罰。具體表達(dá)為

(1)

2.2約束條件

約束條件表達(dá)為

(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期開始空閑的時(shí)刻；式(4)定義岸橋服務(wù)單個(gè)任務(wù)所需要的時(shí)間；式(5)確保船舶作業(yè)開始時(shí)間在到達(dá)之后；式(6)定義船舶作業(yè)的結(jié)束時(shí)間；式(7)為碼頭岸橋總數(shù)量的約束；式(8)表示岸橋只有在滿足上述要求時(shí)才可開始作業(yè)；式(9)表示一個(gè)岸橋在某一時(shí)刻只能為一項(xiàng)任務(wù)服務(wù)；式(10)定義任務(wù)的開始時(shí)間；式(11)定義任務(wù)的結(jié)束時(shí)間；式(12)表示一個(gè)岸橋只能為一艘船舶服務(wù)；式(13)和式(14)限制岸橋不可跨越作業(yè)；式(15)定義某時(shí)刻服務(wù)于同一船舶的岸橋數(shù)量；式(16)定義某一時(shí)刻到下一時(shí)刻岸橋數(shù)量的增加量；式(17)通過左偏差和右偏差定義岸橋靠泊位置；式(18)確保所有的船舶在岸線內(nèi)靠泊；式(19)和式(20)確保沒有兩艘船舶在同一地點(diǎn)、同一時(shí)刻被服務(wù)。

3 求解算法

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

1) 內(nèi)循環(huán)1用于求解泊位分配問題，運(yùn)用遺傳算法迭代循環(huán)求解泊位調(diào)度最優(yōu)值。

2) 內(nèi)循環(huán)2用于求解岸橋分配與調(diào)度問題，運(yùn)用遺傳算法迭代循環(huán)求最優(yōu)值。

3) 外循環(huán)算法主要用于傳遞2個(gè)內(nèi)循環(huán)之間的參數(shù)，實(shí)現(xiàn)2個(gè)問題的銜接；此外，還可通過2個(gè)內(nèi)循環(huán)的迭代和反饋不斷改進(jìn)泊位與岸橋聯(lián)合調(diào)度解的質(zhì)量和計(jì)劃的性能。

嵌套式循環(huán)算法流程見圖1，設(shè)計(jì)思路如下。

圖1 嵌套式循環(huán)算法流程

1) 初始化：k=1。

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

3) 根據(jù)設(shè)定的作業(yè)時(shí)間，運(yùn)用遺傳算法求解泊位計(jì)劃，獲得每艘船舶的靠泊時(shí)間和位置。

4) 根據(jù)獲得的泊位計(jì)劃，把內(nèi)循環(huán)1中的結(jié)果參數(shù)傳遞到內(nèi)循環(huán)2中，運(yùn)用遺傳算法求解岸橋分配與調(diào)度，獲得岸橋作業(yè)順序。

5) 判斷步驟“4)”獲得的岸橋調(diào)度結(jié)果是否正確、合理，若“是”，進(jìn)入步驟“6)”，否則重新設(shè)定初始船舶作業(yè)時(shí)間，重復(fù)步驟“3)”。

6) 判斷外循環(huán)的迭代次數(shù)是否滿足設(shè)定次數(shù)G，若“是”，進(jìn)入步驟“7)”，否則根據(jù)當(dāng)前的岸橋分配與調(diào)度結(jié)果更新船舶作業(yè)時(shí)間，重復(fù)步驟“3)”。

7) 當(dāng)?shù)螖?shù)滿足要求時(shí)，退出循環(huán)，輸出最終解。

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

4 數(shù)值計(jì)算

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

表1 模型參數(shù)數(shù)據(jù)

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

2) 岸橋平均作業(yè)效率為30 TEU/(臺(tái)·h)，岸橋單循環(huán)效率為28 TEU/(臺(tái)·h)，岸橋雙循環(huán)效率為32 TEU/(臺(tái)·h)。

根據(jù)表2及已知的岸橋單循環(huán)和雙循環(huán)作業(yè)效率，可得到調(diào)度模型中每一單位任務(wù)作業(yè)時(shí)間。此外，根據(jù)優(yōu)化調(diào)度模型和算法可獲得5艘船舶的靠泊位置、離泊時(shí)間、所分配岸橋數(shù)量和岸橋作業(yè)任務(wù)。

表2 船舶每一貝位的岸橋作業(yè)次數(shù)

用MATLAB計(jì)算，遺傳算法迭代到400代時(shí)得到最小懲罰189，算法進(jìn)化收斂圖見圖2，岸橋服務(wù)的任務(wù)見表3(表中數(shù)值為岸橋編號(hào))。計(jì)算得出船舶靠泊位置、最后離港時(shí)刻和三部分懲罰值。調(diào)度優(yōu)化結(jié)果見表4(為便于計(jì)算，離港時(shí)刻取整數(shù))。 所設(shè)計(jì)的泊位與岸橋聯(lián)合調(diào)度優(yōu)化方法與傳統(tǒng)集裝箱碼頭作業(yè)方式相比，在保證碼頭作業(yè)最小懲罰的基礎(chǔ)上，每艘船舶的作業(yè)時(shí)間都能得到相應(yīng)優(yōu)化。

圖2 算法進(jìn)化收斂圖

貝位號(hào)船舶1船舶2船舶3船舶4船舶5118411121841113195111429511252962126296212721072128310731293108313103118413114118413124118413

表4 調(diào)度優(yōu)化結(jié)果

5 結(jié)束語

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

[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] 韓駿，孫曉娜，靳志宏．集裝箱碼頭泊位與岸橋協(xié)調(diào)調(diào)度優(yōu)化[J]．大連海事大學(xué)學(xué)報(bào)，2008，34(2)：117-121.

[4] 靳志宏，徐奇，韓駿，等．集裝箱碼頭泊位與岸橋聯(lián)合動(dòng)態(tài)調(diào)度[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]．武漢理工大學(xué)學(xué)報(bào)，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] 桂小婭，陸志強(qiáng)，韓笑樂. 集裝箱碼頭連續(xù)型泊位與岸橋集成調(diào)度[J]. 上海交通大學(xué)學(xué)報(bào)，2013，47(2)：226-229.

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

[12] 余劉海，龐洪靜. 集裝箱碼頭連續(xù)泊位與岸橋聯(lián)合調(diào)度[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] 楊華龍,滕川川.基于擠壓算法的集裝箱碼頭泊位與岸橋聯(lián)合調(diào)度優(yōu)化[J].大連海事大學(xué)學(xué)報(bào)，2014,40(3):8-12.

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

UnifiedSchedulingforContinuousBerthandQuay-CraneBasedonPenaltyFunction

LIUGuiyun，CHENShanshan，ZHANGXiaoli，LIUMingtao

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

2015-10-29

浙江省軟科學(xué)項(xiàng)目(2015C25039)；浙江省教育廳項(xiàng)目(pd2013097)

劉桂云(1972—)，女，遼寧鞍山人，教授，研究方向?yàn)楦劭谂c物流管理。E-mail:liuguiyun@nbu.edu.cn

1000-4653(2016)01-0115-05

U656.1+35

A