集裝箱碼頭場(chǎng)橋調(diào)度優(yōu)化模型研究

郭文文，計(jì)明軍，祝慧靈，周文杰

(1.上海海洋大學(xué) 工程學(xué)院，上海 201306;2.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連116026；3.大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026)

0 引 言

集裝箱碼頭是連接不同運(yùn)輸方式的關(guān)鍵節(jié)點(diǎn)，其裝船效率直接影響著碼頭的通過(guò)能力[1-2]，場(chǎng)橋作為碼頭物流系統(tǒng)的重要組成部分，其運(yùn)作效率的高低直接影響著裝船作業(yè)的運(yùn)作水平[3]。國(guó)內(nèi)外相關(guān)學(xué)者以對(duì)場(chǎng)橋調(diào)度優(yōu)化問(wèn)題有不同程度的研究，研究對(duì)象主要分為單臺(tái)場(chǎng)橋和兩臺(tái)場(chǎng)橋。針對(duì)單場(chǎng)橋行駛路徑優(yōu)化問(wèn)題，K.Y.KIM等[4]只考慮一臺(tái)場(chǎng)橋在同一方向街區(qū)內(nèi)作業(yè)路線，建立目標(biāo)函數(shù)為最小化場(chǎng)橋在貝位的啟動(dòng)時(shí)間和行駛時(shí)間的數(shù)學(xué)模型；在該研究的基礎(chǔ)上，K.H.KIM等[5]、A.H.GHAREHGOZLI等[6]對(duì)模型進(jìn)行改進(jìn)，建立最小化場(chǎng)橋作業(yè)時(shí)間的數(shù)學(xué)模型，并分別利用動(dòng)態(tài)規(guī)劃和兩階段算法進(jìn)行求解。然而，上述研究并未考慮集卡對(duì)場(chǎng)橋調(diào)度的影響，因此，W.C.NG等[7]考慮了集卡到來(lái)時(shí)刻對(duì)場(chǎng)橋調(diào)度的影響，研究已知作業(yè)任務(wù)數(shù)量和預(yù)期時(shí)間下的單場(chǎng)橋作業(yè)順序問(wèn)題。該類研究成果均將場(chǎng)橋作業(yè)任務(wù)看做若干子任務(wù)，并未對(duì)子任務(wù)進(jìn)行劃分，為了進(jìn)一步優(yōu)化場(chǎng)橋路徑；陳雷雷等[8]將場(chǎng)橋作業(yè)任務(wù)分為階段任務(wù)和階段內(nèi)子任務(wù)，建立了最小化階段之間移動(dòng)距離的基于狀態(tài)節(jié)點(diǎn)網(wǎng)絡(luò)的路徑優(yōu)化模型，然而模型只考慮了階段間的距離，忽略了階段內(nèi)的場(chǎng)橋移動(dòng)距離，難以保證求得最優(yōu)的場(chǎng)橋行駛路線。針對(duì)兩臺(tái)場(chǎng)橋行駛路徑優(yōu)化問(wèn)題，部分學(xué)者考慮到集裝箱碼頭的實(shí)際操作，研究了兩臺(tái)場(chǎng)橋可跨越作業(yè)和同時(shí)作業(yè)兩種方式的調(diào)度優(yōu)化問(wèn)題；I.F .A.VIS等[9]研究了一個(gè)堆場(chǎng)街區(qū)內(nèi)兩臺(tái)可跨越的場(chǎng)橋調(diào)度問(wèn)題；邊展等[10]考慮了兩臺(tái)軌道式龍門吊同時(shí)作業(yè)的約束，研究場(chǎng)橋行駛路徑問(wèn)題。

上述研究成果多在K.Y.KIM等[4]的基礎(chǔ)上對(duì)算法進(jìn)行深入的討論和細(xì)化，對(duì)數(shù)學(xué)模型的優(yōu)化研究較少，且多用啟發(fā)式算法進(jìn)行求解，難以求得最優(yōu)解，筆者在已知岸橋作業(yè)子計(jì)劃和堆場(chǎng)貝位箱量分布的前提下，考慮了單場(chǎng)橋和多場(chǎng)橋的協(xié)同作業(yè)，區(qū)別于現(xiàn)存文獻(xiàn)以作業(yè)時(shí)間為目標(biāo)建立的數(shù)學(xué)模型，從場(chǎng)橋移動(dòng)路徑的角度建立了作業(yè)貝位數(shù)最少及行駛路徑最短的兩階段模型，并針對(duì)數(shù)學(xué)模型在AMPL集成開(kāi)發(fā)環(huán)境下利用CPLEX求解器求解場(chǎng)橋取箱位置、取箱數(shù)量以及取箱路線。兩階段模型能夠提高求解效率，且可直接應(yīng)用于大規(guī)模算例的求解，為碼頭調(diào)度人員提供決策支持。

1 問(wèn)題描述

碼頭實(shí)際裝船作業(yè)中，往往按照集裝箱類型將整個(gè)裝船任務(wù)劃分為多個(gè)子任務(wù)，如表1，每個(gè)子任務(wù)需求的集裝箱為同種類型。規(guī)定同一堆場(chǎng)貝位上僅堆存重量、尺寸相同的集裝箱，即同一類型的集裝箱，如圖1。分析可知每個(gè)堆場(chǎng)貝位上箱量有限，單個(gè)貝位可能無(wú)法滿足一個(gè)子任務(wù)要求提取的箱量，即一個(gè)子任務(wù)需求的集裝箱可能堆存在多個(gè)貝位內(nèi)；同時(shí)，多個(gè)子任務(wù)需求的集裝箱也可能是相同類型的集裝箱。因此，子任務(wù)和堆場(chǎng)貝位就出現(xiàn)了多對(duì)多的選擇，產(chǎn)生多種場(chǎng)橋行駛路徑，而場(chǎng)橋數(shù)量的不同，也會(huì)產(chǎn)生不同的行駛路徑，進(jìn)而影響堆場(chǎng)作業(yè)效率。

表1 岸橋作業(yè)計(jì)劃Table 1 Quay crane operation plan

圖1 堆場(chǎng)貝位箱量分布Fig.1 Distribution of the number of containers in the storage yard

因此，在已知岸橋作業(yè)子計(jì)劃和堆場(chǎng)貝位箱量分布的前提下，假設(shè)岸橋作業(yè)子任務(wù)要求按順序依次完成，每個(gè)子任務(wù)作業(yè)的開(kāi)始必須在前一個(gè)子任務(wù)完成作業(yè)以后，同時(shí)堆場(chǎng)貝位要求堆放在同一街區(qū)內(nèi)或在同一直線上，并將貝位依次編號(hào)。假設(shè)堆場(chǎng)內(nèi)初始存放的集裝箱種類和數(shù)量與整個(gè)裝船任務(wù)的集裝箱種類與數(shù)量完全一致，同種類型的集裝箱完全等同，取箱過(guò)程中不存在倒箱問(wèn)題。在此基礎(chǔ)上，以場(chǎng)橋總移動(dòng)距離為目標(biāo)對(duì)碼頭場(chǎng)橋調(diào)度問(wèn)題進(jìn)行研究，著重于縮短場(chǎng)橋行駛距離，提高堆場(chǎng)作業(yè)效率。

2 數(shù)學(xué)模型

建立了可直接求解的兩階段數(shù)學(xué)模型，第1階段為線性規(guī)劃模型，確定子任務(wù)內(nèi)場(chǎng)橋需要作業(yè)的貝位號(hào)及對(duì)應(yīng)貝位內(nèi)的取箱數(shù)量；第2階段結(jié)合第1階段求得的取箱數(shù)量，以總移動(dòng)距離最短為目標(biāo)，確定每臺(tái)場(chǎng)橋作業(yè)的貝位號(hào)序列和對(duì)應(yīng)貝位內(nèi)的取箱數(shù)量以及場(chǎng)橋行駛路徑。

2.1 第1階段模型

第1階段在劃分子任務(wù)的基礎(chǔ)上進(jìn)行研究，主要目的是確定每個(gè)子任務(wù)內(nèi)場(chǎng)橋作業(yè)的堆場(chǎng)貝位號(hào)及對(duì)應(yīng)貝位內(nèi)的取箱數(shù)量。

2.1.1 符號(hào)定義

符號(hào)定義如下：

i為堆場(chǎng)貝位編號(hào)，i=1,2,…,m；m為堆場(chǎng)貝位總數(shù)；k為子任務(wù)編號(hào)，k=1,2,…,n；n為裝船任務(wù)被劃分的子任務(wù)總數(shù)；g為集裝箱類型，g=1,2,…,G，其中1=A，2=B，3=C……依次類推；G為集裝箱類型總數(shù)；φ(g)為存放g類箱的堆場(chǎng)貝位號(hào)集合；ξ(g)為需求g類箱的子任務(wù)編號(hào)集合；hk為子任務(wù)k所需求的集裝箱類型；uk為子任務(wù)k所需求的集裝箱數(shù)量；cgi為貝位i中堆存g型箱的初始數(shù)量；M為足夠大的數(shù)值。

2.1.2 決策變量

xik為場(chǎng)橋在子任務(wù)k中從貝位i中提取集裝箱的數(shù)量，為非負(fù)整數(shù)。

2.1.3 目標(biāo)函數(shù)和約束條件

目標(biāo)函數(shù)為：

(1)

約束條件為：

(2)

(3)

(4)

xik≤M·Xik[k=1,2,…,n，i∈φ(hk)]

(5)

xik≥Xik[k=1,2,…,n,i∈φ(hk)]

(6)

xik≥0 [k=1,2,…,n,i∈φ(hk)]

(7)

Xik∈{0，1}[k=1,2,…,n,i∈φ(hk)]

(8)

其中，式(1)為提取所有子任務(wù)需求的集裝箱后場(chǎng)橋作業(yè)過(guò)的堆場(chǎng)貝位數(shù)最?。皇?2)為每個(gè)子任務(wù)都能完成所需求的箱量；式(3)為堆場(chǎng)貝位內(nèi)集裝箱的初始存儲(chǔ)量與所有子任務(wù)需求的箱量一致；式(4)為所有子任務(wù)在某一貝位的提箱量之和等于該貝位堆存的集裝箱；式(5)和式(6)為xik和Xik的關(guān)系，當(dāng)xik為正整數(shù)時(shí)，Xik為1，當(dāng)xik為0時(shí)，Xik為0；式(7)為決策變量是非負(fù)整數(shù)，當(dāng)場(chǎng)橋在子任務(wù)k中從貝位i中提取集裝箱時(shí)，xik為正整數(shù)，否則為0；式(8)為Xik是0～1變量。

第1階段模型的求解結(jié)果是滿足約束條件的xik解中非零數(shù)最少、零值最多的解，也就是場(chǎng)橋完成裝船子任務(wù)作業(yè)的堆場(chǎng)貝位數(shù)最少的解，用矩陣Aik表示上述解，定義其對(duì)應(yīng)的0～1矩陣為Bik，根據(jù)性質(zhì)一，分析可知上述解集中肯定存在滿足場(chǎng)橋行駛總路徑最短的解。

2.1.4 性質(zhì)一

矩陣Aik中所有的元素中，如果元素零越多則非零元素越少，當(dāng)元素零的個(gè)數(shù)最多時(shí)，所有非零元素所在行的差值之和不大于其他時(shí)候的和，即當(dāng)元素零最多時(shí)，解中一定存在使將所有非零元素所在的行按列隨機(jī)排列后相鄰差值之和最小的情況。

2.2 第2階段模型

2.2.1 符號(hào)定義

2.2.2 決策變量

2.2.3 目標(biāo)函數(shù)和約束條件

目標(biāo)函數(shù)為：

(9)

約束條件為：

(10)

(11)

(i∈φk，k=1,2,…,n,r=1,2,…,R)

(12)

(13)

(14)

(k=1,2,…,n,r=1,2,r′,…,R)

評(píng)析 例3的解答，讓學(xué)生回憶平移的性質(zhì)：平移中對(duì)應(yīng)點(diǎn)之間的連線平行且相等，圖形左右平移中對(duì)應(yīng)點(diǎn)的縱坐標(biāo)的不變性；例4的解答，讓學(xué)生把握解平移問(wèn)題的一條主線——對(duì)應(yīng)點(diǎn)的連線平行且相等，對(duì)應(yīng)邊平行且相等，由此得平行四邊形；例5的解答，從“沒(méi)有現(xiàn)成點(diǎn)”到找點(diǎn)，再找其對(duì)應(yīng)點(diǎn)，讓學(xué)生學(xué)會(huì)了聯(lián)想和轉(zhuǎn)化；例6的第一問(wèn)，需確定相似三角形求OE，第二問(wèn)需根據(jù)平移中對(duì)應(yīng)點(diǎn)之間平移的方向和距離的相同性構(gòu)造全等三角形，將兩條變量線段A′B、BE′轉(zhuǎn)換化成有公共動(dòng)點(diǎn)A′的線段，將兩條變量線段的和的最小值問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間，線段最短”的問(wèn)題.

(15)

k=1,2,…,n,r=1,2,…,R)

(16)

k=1,2,…,n,r=1,2,…,R)

(17)

其中，式(9)為最小化場(chǎng)橋完成子任務(wù)的移動(dòng)距離；式(10)和式(11)為場(chǎng)橋從o點(diǎn)開(kāi)始到d點(diǎn)結(jié)束；式(12)為作業(yè)的堆場(chǎng)貝位的流入量和流出量必須相等；式(13)為每個(gè)子任務(wù)中避免形成回路，|φk|為集合φk的元素個(gè)數(shù)；式(14)為場(chǎng)橋進(jìn)行作業(yè)時(shí)必須完成一個(gè)子任務(wù)才能進(jìn)行下一個(gè)子任務(wù)工作；式(15)為場(chǎng)橋作業(yè)的安全距離且避免跨越作業(yè)；式(16)和式(17)為決策變量為0～1變量。

3 模型驗(yàn)證

在AMPL集成開(kāi)發(fā)環(huán)境下調(diào)用CPLEX求解器對(duì)模型直接求解，Intel(R) Xeon(R) CPU E5- 1603v3 2.8 GHz及8G內(nèi)存平臺(tái)下測(cè)得兩階段模型的最優(yōu)解，驗(yàn)證模型的準(zhǔn)確性。以表1和圖2的具體算例為例，集裝箱船總裝箱量為156 TEU，其中，A型箱60 TEU，B型箱26 TEU，C型箱70 TEU。利用CPLEX求解器對(duì)第1階段模型進(jìn)行求解，計(jì)算得出滿足約束條件的xik的集合Aik及其對(duì)應(yīng)的0～1矩陣Bik，結(jié)果為：

第1階段目標(biāo)值Z=10，即場(chǎng)橋作業(yè)的最少貝位數(shù)為10，CPU運(yùn)行時(shí)間t1=0.05 s，每個(gè)子任務(wù)的作業(yè)貝位為矩陣Bik非零元素所在的行，對(duì)應(yīng)貝位的取箱數(shù)量為矩陣Aik中的非零元素。

在此基礎(chǔ)上，根據(jù)建立的第2階段模型，當(dāng)場(chǎng)橋數(shù)量r=1，即單場(chǎng)橋作業(yè)時(shí)，場(chǎng)橋最優(yōu)行駛路徑如圖2，場(chǎng)橋作業(yè)順序及對(duì)應(yīng)貝位內(nèi)取箱數(shù)量如表2，最短移動(dòng)距離S=17 m，CPU運(yùn)行時(shí)間t2=0.04 s，兩階段的總運(yùn)行時(shí)間為t=0.09 s。

圖2 單場(chǎng)橋作業(yè)行駛路徑Fig.2 Travel route for single yard crane

表2 單場(chǎng)橋作業(yè)下貝位的取箱數(shù)量Table 2 Number of containers taken from the bay under single yard crane operation

當(dāng)場(chǎng)橋數(shù)量r=2，即雙場(chǎng)橋作業(yè)時(shí)，場(chǎng)橋的最優(yōu)行駛路徑如圖3，場(chǎng)橋作業(yè)順序及貝位取箱數(shù)量如表3，最短移動(dòng)距離為S=12 m，CPU運(yùn)行時(shí)間t2=0.05 s，兩階段的總運(yùn)行時(shí)間為t=0.1 s。

圖3 雙場(chǎng)橋作業(yè)行駛路徑Fig.3 Travel route for double yard crane

表3 雙場(chǎng)橋作業(yè)下貝位的取箱數(shù)量Table 3 Number of containers taken from the bay under double yard crane operation

由上述算例可知，筆者建立的數(shù)學(xué)模型可直接進(jìn)行求解，且運(yùn)算時(shí)間較短。同時(shí)，上述算例的求解及計(jì)算結(jié)果驗(yàn)證了數(shù)學(xué)模型的準(zhǔn)確性，且采用雙場(chǎng)橋比單場(chǎng)橋行駛距離更短，為碼頭堆場(chǎng)資源調(diào)度提供決策支持。

4 數(shù)值試驗(yàn)

4.1 算例分析

運(yùn)用兩階段模型對(duì)以下8組算例進(jìn)行求解，表4和表5分別為單場(chǎng)橋與雙場(chǎng)橋作業(yè)時(shí)，堆場(chǎng)作業(yè)的貝位數(shù)及場(chǎng)橋移動(dòng)距離。

由表4、表5和圖4可知，在第1階段求得的作業(yè)貝位及取箱數(shù)量下，第2階段采用單場(chǎng)橋或雙場(chǎng)橋確定作業(yè)路線時(shí)，場(chǎng)橋總行駛距離相差不大，也就是說(shuō)場(chǎng)橋行駛距離與其數(shù)量沒(méi)有密切的關(guān)系。堆場(chǎng)為節(jié)省場(chǎng)橋作業(yè)成本，可選擇單場(chǎng)橋進(jìn)行堆場(chǎng)作業(yè)，但隨著提取箱量的增加，單場(chǎng)橋作業(yè)并不能滿足裝船時(shí)間的要求，而采用雙場(chǎng)橋在提高作業(yè)效率的同時(shí)也會(huì)增加一定的作業(yè)成本。因此，如果裝船作業(yè)時(shí)間較短，碼頭更注重于作業(yè)效率，可采用雙場(chǎng)橋，否則可采用單場(chǎng)橋。利用CPLEX對(duì)模型進(jìn)行求解，可以較快地得到最優(yōu)結(jié)果，運(yùn)行時(shí)間較短，證明了模型的準(zhǔn)確性和高效性。

表4 單場(chǎng)橋作業(yè)貝位數(shù)及距離Table 4 Number of operation bays and travel distance for single yard crane

表5 雙場(chǎng)橋作業(yè)貝位數(shù)及距離Table 5 Number of operation bays and travel distance for double yard crane

圖4 不同取箱數(shù)量行駛距離比較Fig.4 Comparison of driving distance for different numbers of containers taken out

4.2 算法比較

為進(jìn)一步驗(yàn)證算法的優(yōu)越性，將建立的兩階段模型直接求解與文獻(xiàn)[8]中的順序作業(yè)法、貪婪作業(yè)法、基于整數(shù)編碼的遺傳算法進(jìn)行比較，驗(yàn)證了兩階段模型的有效性，表6和表7為文獻(xiàn)中的算例。

表6 岸橋作業(yè)計(jì)劃Table 6 Quay crane operation plan

表7 堆場(chǎng)箱量堆存狀態(tài)Table 7 Yard bays stacking status

根據(jù)文中建立的模型，采用單場(chǎng)橋作業(yè)，利用兩階段模型進(jìn)行求解的結(jié)果為Z=22，S=266，兩階段的總運(yùn)行時(shí)間為t=0.4。由此可知文中的兩階段模型場(chǎng)橋總移動(dòng)貝位數(shù)為266，作業(yè)路徑如圖5，與文獻(xiàn)[8]中算法進(jìn)行比較，結(jié)果如表8。

圖5 兩階段模型作業(yè)路徑Fig.5 Travel route of two-stage model

表8 算法比較Table 8 Algorithm comparison

表8中模型的改進(jìn)程度為兩階段數(shù)學(xué)模型與順序作業(yè)法、貪婪作業(yè)法及遺傳算法相比的改進(jìn)程度，負(fù)號(hào)表示兩階段模型的移動(dòng)總貝位數(shù)小于其它算法下的移動(dòng)總貝位數(shù)。由表8可知兩階段模型與順序作業(yè)法下的移動(dòng)總貝位數(shù)887相比，總移動(dòng)距離縮短了70.0%，與貪婪作業(yè)法下的643相比，總移動(dòng)距離縮短了58.6%，與遺傳算法下的595相比，總移動(dòng)距離縮短了55.3%。因此，建立的兩階段模型能夠明顯的縮短場(chǎng)橋移動(dòng)距離。

為進(jìn)一步驗(yàn)證模型的普遍性，利用文獻(xiàn)[8]中的順序作業(yè)法與貪婪作業(yè)法對(duì)上述算例求解，且與兩階段模型進(jìn)行對(duì)比，具體結(jié)果如表9。

表9 單場(chǎng)橋下算例比較Table 9 Comparison of examples for single yard crane

表9中負(fù)號(hào)表示兩階段模型下場(chǎng)橋行駛的總距離要小于順序作業(yè)法及貪婪作業(yè)法下的行駛距離，數(shù)值大小表示兩階段模型下行駛總距離的減少程度。結(jié)果表明，建立的兩階段模型可以較快地得到最優(yōu)解，在單場(chǎng)橋作業(yè)的情況下，與順序作業(yè)法相比，行駛距離縮短10%～30%，與貪婪作業(yè)法相比，行駛距離縮短10%左右，表明筆者建立的模型具有更顯著的應(yīng)用價(jià)值和研究意義。

5 結(jié) 語(yǔ)

在已知岸橋作業(yè)任務(wù)及堆場(chǎng)貝位箱量分布的條件下研究集裝箱碼頭場(chǎng)橋調(diào)度優(yōu)化問(wèn)題，與現(xiàn)有數(shù)學(xué)模型對(duì)比，建立了場(chǎng)橋作業(yè)貝位數(shù)最少及行駛距離最短的兩階段場(chǎng)橋移動(dòng)路徑模型，將問(wèn)題進(jìn)行簡(jiǎn)單化、分步化，運(yùn)用兩階段模型對(duì)場(chǎng)橋取箱位置、取箱數(shù)量以及取箱路線進(jìn)行求解，得到場(chǎng)橋在每個(gè)任務(wù)中作業(yè)的堆場(chǎng)貝位的順序及對(duì)應(yīng)貝位內(nèi)的提箱數(shù)量，使得場(chǎng)橋行駛距離最短。與現(xiàn)有文獻(xiàn)比較，兩階段模型比順序作業(yè)法縮短10%～30%的行駛距離，比貪婪作業(yè)法縮短10%左右的行駛距離，且優(yōu)于文獻(xiàn)中的遺傳算法，驗(yàn)證了模型的準(zhǔn)確性和有效性。為碼頭工作人員提供了決策支持，有利于提高集裝箱碼頭的運(yùn)營(yíng)效率。