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

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

0 引 言

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

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

1 問題描述

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

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

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

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

2 數(shù)學模型

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

2.1 第1階段模型

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

2.1.1 符號定義

符號定義如下：

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

2.1.2 決策變量

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

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

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

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

2.1.4 性質一

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

2.2 第2階段模型

2.2.1 符號定義

2.2.2 決策變量

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

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

(15)

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

(16)

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

(17)

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

3 模型驗證

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

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

在此基礎上，根據(jù)建立的第2階段模型，當場橋數(shù)量r=1，即單場橋作業(yè)時，場橋最優(yōu)行駛路徑如圖2，場橋作業(yè)順序及對應貝位內取箱數(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

當場橋數(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ù)學模型可直接進行求解，且運算時間較短。同時，上述算例的求解及計算結果驗證了數(shù)學模型的準確性，且采用雙場橋比單場橋行駛距離更短，為碼頭堆場資源調度提供決策支持。

4 數(shù)值試驗

4.1 算例分析

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

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

表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 算法比較

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

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

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

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

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

表8 算法比較Table 8 Algorithm comparison

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

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

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

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

5 結 語

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