連續(xù)泊位—岸橋—集卡調(diào)度模型構(gòu)建及應(yīng)用

，，， ，

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014)

由于受成本、場地和裝卸設(shè)備技術(shù)參數(shù)及投資規(guī)模的制約，有效地對港口各種資源，如泊位、岸橋和集卡等進(jìn)行集成調(diào)度才是提高集裝箱碼頭作業(yè)效率的重要途徑[1].國內(nèi)外研究學(xué)者對港口物流資源調(diào)度做了深入研究.其中，關(guān)于泊位分配的研究：Kim等[2]對大型集裝箱船舶的泊位分配物流資源調(diào)度做了深入研究，設(shè)計(jì)了模擬退火算法對所構(gòu)建的混合整數(shù)規(guī)劃模型進(jìn)行求解.Imai等[3]針對連續(xù)型泊位的分配問題建立了以集裝箱船舶的等待時間和作業(yè)時間最小為目標(biāo)的數(shù)學(xué)模型，并采用拉格朗日松馳系數(shù)算法進(jìn)行求解.關(guān)于岸橋分配的研究：禹美鳳[4]以最小化船舶總在港時間、集裝箱港口生產(chǎn)成本以及懲罰成本作為優(yōu)化目標(biāo),建立多船到達(dá)情況的不確定優(yōu)先權(quán)的柔性靠泊方式下的泊位—岸橋調(diào)度多目標(biāo)數(shù)學(xué)模型.Zhu等[5]在研究岸橋調(diào)度過程中，考慮了外界的干擾約束，并先后使用了模擬退火法、遺傳算法和貪婪算法進(jìn)行求解.關(guān)于集卡調(diào)度的研究：Nishimura等[6]以車輛路徑規(guī)劃的視角研究了集卡的動態(tài)作業(yè)調(diào)度問題.Ng等[7]以集卡完成任務(wù)的總作業(yè)時間最短為目標(biāo)，研究了集卡分配和運(yùn)輸路徑問題.近年來，越來越多學(xué)者把多種資源進(jìn)行聯(lián)合調(diào)度研究：李娜等[8]研究了連續(xù)泊位與岸橋的聯(lián)合調(diào)度問題，構(gòu)建了混合整數(shù)規(guī)劃模型，并使用新的啟發(fā)式算法進(jìn)行求解.劉慧蓮[9]考慮船舶到港時間的不確定性，建立了泊位與岸橋聯(lián)合調(diào)度的魯棒優(yōu)化模型，并用分支定界算法求解，得到了魯棒模型的最優(yōu)解.劉桂云等[10]針對連續(xù)泊位與岸橋聯(lián)合調(diào)度問題，以最小化懲罰為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，設(shè)計(jì)嵌套式遺傳算法并求得船舶的靠、離泊時間和位置及最優(yōu)裝卸序列.

通過對文獻(xiàn)的系統(tǒng)研究，對港口碼頭物流資源只進(jìn)行單獨(dú)的泊位分配、岸橋作業(yè)規(guī)劃、集卡調(diào)度研究或考慮兩個因素的聯(lián)合調(diào)度研究存在一定的缺陷和不足.而為了實(shí)現(xiàn)集裝箱港口碼頭作業(yè)效率的最優(yōu)，必須將其視為一個完整的作業(yè)系統(tǒng)，從系統(tǒng)的角度出發(fā)，對泊位、岸橋和集卡進(jìn)行集成調(diào)度研究.

1 問題描述

集裝箱碼頭前沿作業(yè)系統(tǒng)中3 個重要因素就是泊位、岸橋和集卡.它們是集裝箱港口碼頭的重要資源.船舶到港后，由于泊位資源限制會產(chǎn)生一定的候泊時間.靠泊之后，根據(jù)靠泊船舶的集裝箱數(shù)量，指派一定數(shù)量的岸橋給船舶.在完成岸橋的指派工作后，需要為每一岸橋指派一定數(shù)量的集卡為其服務(wù)，并且集卡以作業(yè)組的形式進(jìn)行裝卸集裝箱任務(wù).在這個過程中，到港船舶的等待時間、在港作業(yè)時間以及集卡運(yùn)輸集裝箱的作業(yè)時間等構(gòu)成了碼頭主要的生產(chǎn)運(yùn)作時間.所以，船舶依次到港后,如何根據(jù)現(xiàn)有有限的泊位資源,科學(xué)合理地為船舶指派泊位,會有效減少船舶的靠泊時間同時也會縮短其他船舶的待泊時間.此外,對于已經(jīng)靠泊的船舶,如何科學(xué)合理地分配岸橋數(shù)量和為岸橋服務(wù)的集卡數(shù)量,也會在一定程度上影響船舶的靠泊時間進(jìn)而影響整體的生產(chǎn)效率.與此同時，泊位分配的位置以及船舶本身的偏好靠泊位置都會影響集卡的運(yùn)輸距離，進(jìn)而影響集卡的運(yùn)輸作業(yè)時間.那么把集卡的運(yùn)輸距離控制在一個合適的范圍內(nèi)，將會提高碼頭的整體生產(chǎn)效率.因此，這3 種資源的獨(dú)立研究或是兩者之間聯(lián)合調(diào)度，都不能達(dá)到整體作業(yè)流程最優(yōu)的結(jié)果，需要將泊位、岸橋和集卡這三者進(jìn)行聯(lián)合研究才能達(dá)到集裝箱碼頭前沿作業(yè)的整體最優(yōu).

2 模型構(gòu)建

2.1 模型假設(shè)

模型建立在調(diào)度前提前收到來自船舶代理公司相關(guān)資料的基礎(chǔ)上，因此，船舶的靠泊偏好位置、裝卸作業(yè)量和各個集裝箱的存儲位置已知.此外，模型還假設(shè)泊位是連續(xù)型，不考慮水深潮汐等其他物理?xiàng)l件的限制；忽略拖輪對船舶進(jìn)出泊位時間的影響；碼頭堆場的進(jìn)口箱區(qū)的各個箱區(qū)與出口箱區(qū)的各個箱區(qū)之間的距離相同；不考慮船舶的移泊和裝卸過程中的平衡問題；每個岸橋的移動速度、工作效率相同；所有集卡作業(yè)效率相同，每輛集卡每次只能運(yùn)1 個集裝箱；集卡以作業(yè)組的形式指派給船舶，并共同服務(wù)于為船舶服務(wù)的所有岸橋；集卡到各個箱區(qū)的平均作業(yè)時間相同.

2.2 模型建立

考慮到泊位占用、岸橋與集卡的使用以及岸橋和集卡的相互等待的單位時間成本的差異，將集裝箱船舶的每個作業(yè)環(huán)節(jié)都以費(fèi)用支出和懲罰成本的形式表示.通過對泊位、岸橋和集卡這3 項(xiàng)資源的優(yōu)化配置來實(shí)現(xiàn)計(jì)劃期內(nèi)所有的到港船舶總費(fèi)用最少.目標(biāo)函數(shù)為

(1)

約束條件分別為

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

xt(c+1)k-xtck+xt(c-1)k=-1，0，1， ?t∈T，?k∈V

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

3 算法步驟

遺傳算法在搜索優(yōu)化問題的全局或是接近全局最優(yōu)解上有著良好的優(yōu)勢條件，模型得到的是相對最優(yōu)下的調(diào)度方案，所以模型采用遺傳算法進(jìn)行模型求解.在經(jīng)典的遺傳算法上作了部分改進(jìn)來求解上述模型[11].

Step1染色體編碼和種群初始生產(chǎn)，計(jì)算種群的適應(yīng)度函數(shù)值.

Step2設(shè)計(jì)迭代的終止條件，滿足終止條件即終止; 否則，執(zhí)行Step 3.

Step3對子代個體進(jìn)行交叉變異操作，計(jì)算其當(dāng)代的最優(yōu)解.

Step4更新整體最優(yōu)解.對當(dāng)代最優(yōu)解與存儲單元解進(jìn)行比較，若當(dāng)代最優(yōu)解更優(yōu)，則更新; 若存儲單元解更優(yōu)，則存儲單元解保持不變，返回Step 2.

3.1 染色體編碼和種群初始化

根據(jù)數(shù)學(xué)模型的特點(diǎn)，構(gòu)建一維染色體編碼，如圖1所示.染色體的長度是集裝箱船舶數(shù)目N的4 倍，每一段染色體長度為集裝箱船舶的數(shù)目，其中第一段(1～N)依次表示每一艘集裝箱船舶的到港時間；第二段(N+1～2N)依次表示每一艘集裝箱船舶的靠泊位置；第三段(2N+1～3N)依次表示每一艘集裝箱船舶所分配的岸橋數(shù)目；第四段(3N+1～4N)依次表示每一艘集裝箱船舶所分配的集卡數(shù)目.

12345123451234512345251617258402070503221610911814船舶的靠泊時間船舶的靠泊位置船舶分配的岸橋數(shù)船舶分配的集卡數(shù)

圖1染色體編碼

Fig.1Chromosomecoding

在生成初始種群的每個個體前，需要對集裝箱港口碼頭的相關(guān)資源進(jìn)行初始化.首先默認(rèn)岸橋最初位置是均勻分布在碼頭岸線上，然后對每艘集裝箱船舶進(jìn)行資源配置，依次設(shè)置生成集裝箱船舶的靠泊時間、靠泊位置、岸橋數(shù)目、集卡數(shù)目、實(shí)際開始裝卸時間、實(shí)際離港時間、使用的岸橋編號和使用的集卡編號.然后根據(jù)其實(shí)際開始裝卸時間和實(shí)際離港時間對岸線、岸橋和集卡資源的狀態(tài)進(jìn)行更新；根據(jù)集裝箱船舶的靠泊位置對岸橋的位置進(jìn)行更新.當(dāng)完成所有集裝箱船舶的相應(yīng)參數(shù)的生成，才進(jìn)入下一個初始解生成的重復(fù)過程.隨機(jī)生成初始種群，初始種群的個體數(shù)設(shè)置為300 個.初始解的規(guī)模需要滿足種群的合適規(guī)模才能結(jié)束初始解生成的循環(huán)過程.

3.2 適應(yīng)度設(shè)計(jì)

適應(yīng)度的值用于表示每一個個體的優(yōu)劣性.適應(yīng)度函數(shù)通常是根據(jù)模型的目標(biāo)函數(shù)轉(zhuǎn)換而成，根據(jù)目標(biāo)函數(shù)的特點(diǎn)，取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù).

3.3 選擇操作的設(shè)計(jì)

根據(jù)染色體編碼的特點(diǎn)以及所構(gòu)建模型的特殊性，采用最佳保留策略和均勻排序相結(jié)合的選擇方式[12]進(jìn)行操作.

具體的操作過程如下：

1) 根據(jù)每個個體的適應(yīng)度大小對新一代的個體進(jìn)行降序排序.

2) 將排序中最前面兩個，即復(fù)制保存最優(yōu)的兩個個體直接作為下一代個體.

3) 隨機(jī)產(chǎn)生一個整數(shù)，按照上述的排列方式，去掉排序中的隨機(jī)數(shù)個適應(yīng)度值低的個體.

4) 下一代個體的的父代將從第3 步操作后剩余的個體中隨機(jī)產(chǎn)生.每次隨機(jī)選擇兩個個體作為進(jìn)行下一步的交叉等過程的個體，隨機(jī)選擇多次直到達(dá)到足夠的個體數(shù)目要求為止.

3.4 交叉操作的設(shè)計(jì)

算法采用兩種交叉策略進(jìn)行交叉操作.在染色體的第一段采用單點(diǎn)交叉策略；在染色體的第二至四段采用算術(shù)交叉策略.具體的線性組合為

子代1號=λ×父代1號+(1-λ)×父代2號

(22)

子代2號=λ×父代2號+(1-λ)×父代1號

(23)

式中λ為0到1的隨機(jī)數(shù).在交叉操作后，為了保證子代可行性，對子代基因值進(jìn)行四舍五入.

3.5 變異操作的設(shè)計(jì)

為了保持子代在迭代過程中的多樣性需要對交叉操作之后的個體進(jìn)行相應(yīng)的變異操作.在染色體上的第一段基因與第二段基因變異操作式為

(24)

式中：λ為0到1的隨機(jī)數(shù)；G為當(dāng)前迭代代數(shù)；P為最大迭代代數(shù)；S為變異步長參數(shù)；Δ為變動范圍.

4 案例分析

4.1 基礎(chǔ)數(shù)據(jù)

以某集裝箱碼頭為例，該集裝箱碼頭的岸線長為1 700 m，共有22 臺岸橋，120 輛集卡可供服務(wù).所有岸橋的初始狀態(tài)設(shè)定：從左到右依次均勻地分布在岸線上；集卡則是在船舶靠泊之前，提前到達(dá)岸線區(qū)域進(jìn)行等待.算例隨機(jī)選取連續(xù)的28 艘到港船舶的數(shù)據(jù)作為原始數(shù)據(jù)，進(jìn)行集裝箱碼頭連續(xù)泊位—岸橋—集卡調(diào)度研究.到港時刻以第一艘集裝箱船舶到港時刻的0點(diǎn)為基準(zhǔn)，所有船舶的原始數(shù)據(jù)見表1.通過分析處理原始數(shù)據(jù)，得到集裝箱船舶的最大、最小岸橋數(shù)以及船舶的偏好靠泊位置.

表1 集裝箱船舶原始數(shù)據(jù)表Table 1 The raw data Table of container ships

4.2 求 解

圖2 個體適應(yīng)度的波動圖Fig.2 The volatility of the individual fitness

4.2.1 最優(yōu)調(diào)度方案

經(jīng)過遺傳算法優(yōu)化求解得到最優(yōu)調(diào)度方案，如表2所示.

表2 泊位—岸橋—集卡的最優(yōu)調(diào)度方案Table 2 The optimal scheduling scheme of berth-crane-trailer

4.2.2 泊位分配方案

通過算法得到岸橋的泊位分配方案，如圖3所示.由圖3可見：每艘船舶相互之間在港時間和靠泊位置上不存在交叉，證明方案的可行性.

圖3 泊位分配方案Fig.3 The scheme of berth allocation

4.2.3 岸橋作業(yè)甘特圖

圖4表示每一個岸橋在這段時間內(nèi)為每一艘集裝箱船舶服務(wù)的開始作業(yè)時刻和作業(yè)完成時刻.圖4中：方框中的編號為集裝箱船舶的編號；方框的右側(cè)正對的橫坐標(biāo)為該集裝箱船舶結(jié)束裝卸任務(wù)的時刻；方框中間正對的縱坐標(biāo)表示相應(yīng)岸橋的編號.

由圖4可知：這個計(jì)劃期內(nèi)總的被使用的岸橋數(shù)只有19 臺，而編號為20，21，22的這幾臺岸橋一直是處于閑置狀態(tài).對于集裝箱港口碼頭來說，岸邊的裝卸設(shè)備的購置費(fèi)用、維修費(fèi)用巨大，若是能夠通過模型事先確定集裝箱碼頭的岸橋設(shè)備的所需數(shù)目，在一定程度上可以為集裝箱碼頭節(jié)省大量的資金.

4.2.4 集卡作業(yè)甘特圖

裝箱碼頭的集卡數(shù)目達(dá)到了120 輛，因此選取其中的前20 輛(即編號1～20的集卡)和后24輛(即編號97～120的集卡)為例進(jìn)行表示，其中表示方法與岸橋甘特圖相同，如圖5所示.

圖4 岸橋的作業(yè)甘特圖Fig.4 Gantt chart about cranes

圖5 集卡的作業(yè)甘特圖Fig.5 Gantt chart about trailers

從集卡的作業(yè)甘特圖中可以發(fā)現(xiàn)：109～120這一段編號的集卡處于閑置狀態(tài)，因此就目前計(jì)劃期的裝卸需求而言，并不需要配置120 輛的集卡，不僅浪費(fèi)了集裝箱碼頭的空間資源，也是碼頭資金的一種浪費(fèi).因此若是集裝箱碼頭采用該模型，則可以為碼頭的設(shè)備資源購置提供相應(yīng)決策資料.

5 結(jié) 論

在數(shù)值實(shí)例中，結(jié)合所建立數(shù)學(xué)模型和設(shè)計(jì)的遺傳算法，對其進(jìn)行求解得到了最優(yōu)的調(diào)度方案，包括集裝箱船舶的泊位分配、岸橋分配以及集卡的指派情況，并繪制了岸橋和集卡的作業(yè)甘特圖.結(jié)果證明：所設(shè)計(jì)的調(diào)度模型不僅能為集裝箱碼頭提供泊位分配、岸橋分配以及集卡指派決策方案，減少集裝箱的總在港時間成本，生產(chǎn)成本和船舶延期所帶來的懲罰成本的總體費(fèi)用，也可以為碼頭相關(guān)設(shè)備的購置提供相應(yīng)的決策支持.

[1] 蔣美仙,張曉,馮定忠,等.基于Poisson過程的港口碼頭集卡預(yù)約調(diào)度優(yōu)化[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2016，44(3):292-299.

[2] KIM K H, MOON K C. Berth scheduling by simulated annealing[J]. Transportation research part B: methodological,

2003, 37(2): 541-560.

[3] IMAI A,SUN X, NISHMURA E. Berth allocation in a container port: using a continuous location space approach[J]. Transportation research part B: methodological, 2005, 39(3): 199-221.

[4] 禹美鳳.基于柔性靠泊的集裝箱港口泊位和岸橋的調(diào)度優(yōu)化[D].杭州：浙江工業(yè)大學(xué),2013.

[5] ZHU Y,LIM A. Crane scheduling with non-crossing constraint[J]. Journal of the operational research society, 2006, 57(12): 1464-1471.

[6] NISHIMURA E, IMAI A. Berth allocation planning in the public berth system by genetic algorithms[J]. European journal of operational research, 2001, 131(2): 282-292.

[7] NG W C, MAK K L, ZHANG Y X. Scheduling trucks in container terminals using a genetic algorithm[J]. Engineering optimization, 2007, 39(1): 33-47.

[8] 李娜,靳志宏.連續(xù)泊位調(diào)度與岸橋配置協(xié)同優(yōu)化[J].中國航海,2011,34(2):86-90.

[9] 劉慧蓮.不確定性條件下的集裝箱碼頭泊位分配與岸橋調(diào)度問題的研究[D].呼和浩特：內(nèi)蒙古大學(xué),2016.

[10] 劉桂云,陳珊珊,張小莉,等.基于懲罰函數(shù)的集裝箱碼頭連續(xù)泊位-岸橋聯(lián)合調(diào)度[J].中國航海,2016(1):115-119.

[11] 王衛(wèi)紅,李文瓊.基于改進(jìn)遺傳算法的高中走班制排課算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2016，44(6):601-607.

[12] 陳勇,章金紅,魯建廈.基于GA-TS混合算法的多裝配線調(diào)度建模[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2013，41(4):355-358.