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

郭文文，計明軍，祝慧靈，周文杰

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

0 引 言

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

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

1 問題描述

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

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

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

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

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

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

2.1 第1階段模型

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

2.1.1 符號定義

符號定義如下：

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

2.1.2 決策變量

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

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

2.1.4 性質(zhì)一

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

2.2 第2階段模型

2.2.1 符號定義

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)

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

(15)

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

(16)

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

(17)

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

3 模型驗證

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

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

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

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

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

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

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

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

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

4 數(shù)值試驗

4.1 算例分析

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

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

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

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

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

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

根據(jù)文中建立的模型，采用單場橋作業(yè)，利用兩階段模型進(jìn)行求解的結(jié)果為Z=22，S=266，兩階段的總運行時間為t=0.4。由此可知文中的兩階段模型場橋總移動貝位數(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ù)號表示兩階段模型的移動總貝位數(shù)小于其它算法下的移動總貝位數(shù)。由表8可知兩階段模型與順序作業(yè)法下的移動總貝位數(shù)887相比，總移動距離縮短了70.0%，與貪婪作業(yè)法下的643相比，總移動距離縮短了58.6%，與遺傳算法下的595相比，總移動距離縮短了55.3%。因此，建立的兩階段模型能夠明顯的縮短場橋移動距離。

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

表9 單場橋下算例比較Table 9 Comparison of examples for single yard crane

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

5 結(jié) 語

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