集裝箱碼頭送箱集卡預(yù)約與場橋調(diào)度協(xié)同優(yōu)化

馬夢知，范厚明，計明軍，郭振峰

(大連海事大學(xué)交通運輸工程學(xué)院，遼寧大連116026)

0 引言

集裝箱碼頭經(jīng)營者和研究者一直在探索提升碼頭集港效率的新方法，以適應(yīng)貨主和船公司越來越高的集港要求.傳統(tǒng)集港方式對于送箱時間普遍沒有約束，存在較大的隨機性，且碼頭與港外堆場缺少信息的交互溝通，高峰時段集中到港使得場橋等設(shè)備使用不平衡，甚至超負荷運轉(zhuǎn).因此，迫切需要優(yōu)化調(diào)度場橋，合理分配集港時間，從而緩解高峰時段閘口或堆場擁堵及場橋“供不應(yīng)求”的問題.

針對場橋在箱區(qū)間的調(diào)度問題，Zhang等[1]以堆場所有規(guī)劃時段未完成作業(yè)量的總和最小為目標(biāo)建立混合整數(shù)規(guī)劃模型，求取場橋最佳的移動時間和路徑，但忽略了送箱集卡不會在時段開始之初就全部到達箱區(qū)這一客觀事實.因此，Linn等[2]在對箱區(qū)和場橋類型進行判斷的基礎(chǔ)上，建立了以各時段堆場未完成作業(yè)量最少為目標(biāo)的場橋調(diào)度模型，但不能保證所有時段堆場未完成的作業(yè)量總和最小.李建忠[3]構(gòu)建以所有時段堆場未完成的作業(yè)總和及場橋閑置時間最小為目標(biāo)的規(guī)劃模型，并采用基于啟發(fā)式方法的Lagrangian松弛算法求解模型.

目前，國內(nèi)外已有港口利用集卡預(yù)約系統(tǒng)對集卡到港時間進行管理，考慮到未按預(yù)約時段集港的懲罰成本(集卡早到時需在緩沖區(qū)內(nèi)等待，而晚到則需要船放箱才能裝船[4])，集卡都會盡量準(zhǔn)時到港，因此，根據(jù)預(yù)約份額制定的場橋調(diào)度計劃更準(zhǔn)確.針對集卡到港時間管理的問題，Zhang等[5]構(gòu)建了閘口和堆場二級排隊網(wǎng)絡(luò)，以最小化集卡平均周轉(zhuǎn)時間為目標(biāo)建立集卡預(yù)約優(yōu)化模型，但沒有考慮到預(yù)約機制給集卡司機造成的不便.因此，Chen G.等[6]以同時最小化集卡等待時間和預(yù)約前后集港時段調(diào)整的集卡數(shù)為目標(biāo)建立集卡預(yù)約優(yōu)化模型.曾慶成等[7]利用休假式排隊模型描述碼頭內(nèi)部集卡和外部集卡的特征，建立了內(nèi)外集卡協(xié)同服務(wù)的碼頭集卡預(yù)約優(yōu)化模型.邵乾虔等[8]提出了碼頭與車隊信息互聯(lián)互通的碼頭集疏港聯(lián)動預(yù)約模式.

通過對現(xiàn)有研究成果的梳理發(fā)現(xiàn)，目前針對碼頭堆場內(nèi)場橋調(diào)度與集港預(yù)約份額分配的研究都是獨立進行的.但兩者是相互承接、相互關(guān)聯(lián)的，場橋調(diào)度策略直接關(guān)系到整個集港過程的效率，而預(yù)約份額分配方案又決定了場橋的調(diào)度策略.因此，本文以整個決策期送箱集卡在閘口的排隊等待時間、預(yù)約集港導(dǎo)致集港時段調(diào)整的集卡數(shù)及所有預(yù)約時段未完成的作業(yè)量所需的場橋作業(yè)時間最小為上層規(guī)劃目標(biāo)，以每個預(yù)約時段未完成作業(yè)量所需的場橋作業(yè)時間最小為下層規(guī)劃目標(biāo)，建立集裝箱碼頭送箱集卡預(yù)約與場橋調(diào)度協(xié)同優(yōu)化模型.

1 問題描述與模型假設(shè)

1.1 問題描述

預(yù)約集港即集裝箱碼頭根據(jù)堆場的機力配備情況，設(shè)置各個集港時段的最大集港量(預(yù)約份額)，港外堆場則根據(jù)碼頭公布的集港信息及自身運力情況在網(wǎng)上預(yù)約集港時段，并在預(yù)約的時段內(nèi)送箱到港.送箱集卡到達碼頭閘口后隨機選擇1條閘口通道排隊等待進港，閘口收箱員對出口箱及相關(guān)文件檢驗無誤后指示外集卡到指定箱區(qū)等待場橋服務(wù).為了充分利用場橋的作業(yè)能力，場橋在完成當(dāng)前箱區(qū)較少的作業(yè)任務(wù)后需要轉(zhuǎn)移到任務(wù)量較多的箱區(qū).因此，碼頭可根據(jù)集港計劃準(zhǔn)確制定未來1天的場橋調(diào)度計劃.

1.2 模型假設(shè)

(1)決策期為1天；

(2)用工作時間衡量場橋的工作能力，在不考慮設(shè)備故障的情況下，所有場橋各調(diào)度計劃時段的工作能力是相同的；

(3)每個時段內(nèi)每臺場橋最多只能轉(zhuǎn)場1次；

(4)為避免場橋間潛在的碰撞危險，同一箱區(qū)最多配備2臺場橋；

(5)場橋移動的開始和結(jié)束時間都在同一時段內(nèi)；

(6)碼頭閘口處可被視為N個M M 1型排隊系統(tǒng)，N為閘口通道個數(shù).

2 模型構(gòu)建

2.1 模型參數(shù)與變量定義

(1)輸入?yún)?shù).

p為時段編號，將1天分成P個預(yù)約時段，p=1,2,…,P；t為將每個時段p分成σ個小的時間間隔，并以時間間隔中的某個時刻t(t=1,2,…,Pσ)代表該時間間隔；n為閘口通道的編號，n=1,2,…,N；i為出口箱區(qū)的編號，i=1,2,…,I；j為服務(wù)于出口箱區(qū)的場橋編號，j=1,2,…,J；λi,p為偏好在時段p到港并將集裝箱送到箱區(qū)i的集卡數(shù)；C為單臺場橋1個時段內(nèi)的作業(yè)能力，；τ為場橋完成1次操作所需要的平均時間；v為船舶編號，根據(jù)截載時間由早到晚依次編號，v=1,2,…,V；tv為船舶v的截載時間；ci,v為到達箱區(qū)i給船舶v送箱的集卡數(shù)；Ti,j,p為時段p場橋 j移動至箱區(qū)i所需的時間；ri,p為時段p開始之初箱區(qū)i配備的場橋數(shù).

(2)衍生變量.為t時刻通道n處集卡平均排隊長度；為t時刻通道n處集卡到達率；為t時刻通道n處集卡離開率；為t時刻通道n的利用率；為t時刻通道n的服務(wù)率；為時段p集卡在通道n的平均等待時間；為時段p不需要增加場橋的箱區(qū)(即場橋作業(yè)能力大于等于作業(yè)量)集合；為時段p無法再增加場橋的箱區(qū)(即場橋作業(yè)能力小于作業(yè)量，且已配置2臺場橋)集合；為時段p需要增加場橋的箱區(qū)(即場橋作業(yè)能力小于作業(yè)量，且配置的場橋數(shù)小于2)集合；Rp為時段p可移動的場橋集合；為場橋調(diào)度前，時段p箱區(qū)i未完成作業(yè)量所需的場橋作業(yè)時間；為場橋調(diào)度后，時段p箱區(qū)i富余的場橋作業(yè)時間；Fi,p為時段p結(jié)束時箱區(qū)i未完成作業(yè)量所需的場橋作業(yè)時間；為時段p場橋j(j∈ Rp)被移動前富余的作業(yè)時間；為時段p場橋j(j∈ Rp)富余的作業(yè)時間不足以移動到的箱區(qū)集合，且.

(3)決策變量.

時段p箱區(qū)i的預(yù)約份額；xi,j,p為0-1變量，時段p場橋j移動至箱區(qū)i時，xi,j,p=1，否則xi,j,p=0.

2.2 上層規(guī)劃模型

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

約束條件：

式(1)為目標(biāo)函數(shù)，以整個決策期集卡在閘口的排隊等待時間、預(yù)約導(dǎo)致集港時段調(diào)整的集卡數(shù)及所有時段未完成的作業(yè)量所需的場橋作業(yè)時間總和最小為目標(biāo)，F(xiàn)p由下層規(guī)劃求得；式(2)表示預(yù)約前后集卡到達量守恒；式(3)表示將集卡到達量轉(zhuǎn)化為較小時間間隔的集卡到達率；式(4)表示排隊隊長的變化等于到達率減去離開率；式(5)表示t時刻通道i處的集卡離開率；式(6)表示t時刻通道i的利用率；式(7)表示集卡在閘口的平均等待時間；式(8)表示預(yù)約份額要保障集卡在相應(yīng)船舶截載前運抵碼頭；式(9)表示預(yù)約份額非負.

2.3 下層規(guī)劃模型

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

約束條件：

式(10)為目標(biāo)函數(shù)，以時段p未完成作業(yè)量所需的場橋作業(yè)時間最小為目標(biāo)；式(11)～式(13)表示箱區(qū)i不需要或無法增加場橋，場橋j不可移動或富余的作業(yè)時間不足以移動到箱區(qū)i時，場橋j不能調(diào)往箱區(qū)i；式(14)表示場橋每個時段最多移動1次；式(15)表示時段p結(jié)束時箱區(qū)i未完成的作業(yè)量所需的場橋作業(yè)時間；式(16)表示1個箱區(qū)最多配備2臺場橋；式(17)表示非負約束.

下層規(guī)劃模型中的變量，以及箱區(qū)和場橋(Rp)的分類均由λy*i,p及當(dāng)前箱區(qū)配備的場橋數(shù)確定.集裝箱碼頭的實際生產(chǎn)運營中箱區(qū)的作業(yè)任務(wù)并無法在各個時段開始時就全部到達，即直至?xí)r段結(jié)束場橋都要服務(wù)于該箱區(qū).因此，上述變量及箱區(qū)、場橋分類的確定方法如下.

(1)，且ri,p=2時，箱區(qū)，該箱區(qū)的場橋

(2)，且ri,p＜2時，箱區(qū)i∈BSp，該箱區(qū)的場橋

(3)時，箱區(qū)i∈BpE，該箱區(qū)的場橋.

(4)時，箱區(qū)，但箱區(qū)i現(xiàn)有場橋的分類需進一步討論：

①時，場橋；ri,p=2時，，且場橋j2在箱區(qū)i服務(wù)Oj2后空閑，滿足的箱區(qū)

②時，場橋j∈Rp，，滿足的箱區(qū)；.時，場橋，，滿足的箱區(qū)，滿足的箱區(qū)時，，滿足的箱區(qū)

3 算法設(shè)計

二層規(guī)劃問題的嵌套本性導(dǎo)致其可行解集不再具備凸性和閉性，且非處處可微，從而阻礙了梯度法、最小二乘等利用導(dǎo)數(shù)的優(yōu)化算法的使用.而遺傳算法對函數(shù)的可導(dǎo)性沒有要求，加之其全局收斂性、隱含的并行性和較強的魯棒性，使其能夠有效求解結(jié)構(gòu)復(fù)雜的二層規(guī)劃問題.因此，本文設(shè)計了并行遺傳算法(Parallel Genetic Algorithm，PGA)對模型進行求解，算法流程如圖1所示.

圖1 PGA求解二層規(guī)劃模型的流程圖Fig.1 The flow chart of PGA for bi-level programming

算法步驟：

Step 1編碼與初始種群.染色體的基因依次為各箱區(qū)各預(yù)約時段的集卡到達量，即H臺服務(wù)器分別在式(2)和式(8)的約束下，隨機生成一定數(shù)量的個體.

Step 2計算適應(yīng)度.鑒于本文是求解目標(biāo)函數(shù)的最小值，取作為適應(yīng)度函數(shù).其中，M為足夠大的整數(shù).

Step 3選擇操作.使用輪盤賭選擇算子，對子種群中的染色體進行選擇.

Step 4交叉操作.本文采用隨機錯位算術(shù)交叉算子對父代進行交叉操作生成子代.為滿足式(2)的約束，僅對表示同一箱區(qū)的部分染色體進行交叉.同時，為了滿足式(8)的約束，根據(jù)船舶的截載時間設(shè)置交叉點，對每兩個相鄰交叉點間的基因進行隨機配對.然后，對配對的2個等位基因g1i和g2j進行式(18)的算術(shù)運算.

Step 5 變異操作.為保證變異后仍滿足式(2)的約束，隨機選擇1條染色體中同一箱區(qū)的2個基因gim和gin(n＞m)進行變異.為了滿足式(8)的約束，gim變異的下限如式(19)所示，變異的上限為隨機產(chǎn)生范圍內(nèi)的整數(shù)δ，則變異后，具體操作過程如圖3所示.

式中：β為一個常數(shù)，取0.5.

新產(chǎn)生的染色體各有A個非整數(shù)基因，將染色體1的前A2個非整數(shù)基因向上取整，后A2個非整數(shù)基因向下取整，染色體2中對應(yīng)的基因位進行相反操作，如圖2所示.t1=8，t2=20，t3=24，ci,v取值如表1所示.場橋在各箱區(qū)間移動所需要的時間如表2所示.

圖2 隨機錯位算術(shù)交叉操作示意圖Fig.2 Schematic diagram of random dislocation arithmetic crossover

圖3 變異操作示意圖Fig.3 Schematic diagram of mutation

Step 6子種群的遷移.當(dāng)G/GE=0時，用子種群中適應(yīng)度值最大的前NE個個體替換掉相鄰子種群中適應(yīng)度值最小的NE個個體.

Step 7當(dāng)算法的進化代數(shù)達到最大進化代數(shù)，算法終止.

4 算例分析

4.1 算例描述

以天津東方海陸集裝箱碼頭的實際數(shù)據(jù)進行實例分析，該集裝箱碼頭擁有2條集港通道，15個出口箱區(qū)，10臺場橋服務(wù)出口箱區(qū)，如圖4所示.模型參數(shù)取值為：，

表1 箱區(qū)集卡到達信息Table 1 The arrival information of trucks for export containers in each block

圖4 決策開始前箱區(qū)的場橋配置情況Fig.4 The allocation of cranes at the beginning of the decision-making horizon

表2 場橋在各箱區(qū)間的移動時間Table 2 Crane traveling time between blocks (min)

4.2 運算結(jié)果

利用Matlabr2010b編寫算法程序，并在PC(CPU：四核酷睿3.2 GHz；內(nèi)存：4 G)上運行.本文設(shè)計的并行遺傳算法的收斂過程如圖5所示，迭代5 000次后算法終止，共耗時3 971.11 s，目標(biāo)函數(shù)值收斂于2 922.3.

預(yù)約前后集卡到達量和平均等待時間如圖6所示，實施預(yù)約集港前，集卡在閘口的平均等待時間為5.553 min，最長等待時間為12.336 min；實施預(yù)約集港后，集卡在閘口的平均等待時間和最長等待時間分別降至4.309 min和4.820 min.結(jié)果表明，預(yù)約集港有削峰平谷的作用，能有效緩解送箱集卡在閘口處長時間排隊等待的問題.根據(jù)預(yù)約集港下的集卡到達量得到場橋調(diào)度方案如圖7所示.

圖5 PGA的收斂過程Fig.5 Convergence procedure of CPGA

圖6 預(yù)約前后集卡到達量和平均等待時間Fig.6 Number of trucks arrival at each block and waiting time before and after appointment

4.3 不同優(yōu)化策略的對比與分析

為了與本文提出協(xié)同優(yōu)化模型進行對比，同時，對同一算例的獨立決策策略進行數(shù)值實驗，即先優(yōu)化集港預(yù)約份額，根據(jù)得到的最優(yōu)集港預(yù)約份額分配方案優(yōu)化場橋的調(diào)度，運算結(jié)果如表3所示.可見，兩種優(yōu)化策略都能有效降低集卡在閘口的等待時間，且獨立決策下集港時段被迫改變的集卡數(shù)更少.但是，由于集港預(yù)約份額優(yōu)化過程中沒有考慮場橋調(diào)度，導(dǎo)致獨立優(yōu)化策略下整個決策期所有箱區(qū)未完成作業(yè)量要遠大于協(xié)同優(yōu)化策略.對比結(jié)果表明，本文建立的模型能夠?qū)崿F(xiàn)送箱集卡預(yù)約與場橋調(diào)度的協(xié)同優(yōu)化，更大限度提高集港過程中集裝箱碼頭閘口和堆場的整體作業(yè)效率.

圖7 場橋調(diào)度方案Fig.7 The crane deployment plan

表3 不同優(yōu)化策略的實驗結(jié)果Table 3 Experimental results of different optimization strategies

5 結(jié) 論

針對送箱集卡隨機到港引起的場橋作業(yè)不均衡，以及高峰時段場橋資源緊缺、集裝箱碼頭擁堵等問題，構(gòu)建送箱集卡預(yù)約與場橋調(diào)度協(xié)同優(yōu)化的二層規(guī)劃模型，并設(shè)計PGA算法求解模型.算例分析驗證了本文所建優(yōu)化模型的正確性和所設(shè)計算法的有效性，結(jié)果表明：

(1)實施預(yù)約集港后，送箱集卡在閘口的最長等待時間由12.336 min縮短為4.820 min，可見，實施預(yù)約集港能夠顯著降低送箱集卡在閘口的排隊等待時間；

(2)獨立決策策略下所有箱區(qū)未完成作業(yè)量所需的場橋作業(yè)時間為345 min，而協(xié)同優(yōu)化策略下沒有未完成作業(yè)量，可見，協(xié)同優(yōu)化比獨立決策更有利于提高送箱過程中集裝箱碼頭閘口和堆場的整體作業(yè)效率.

但本文還存在不足，如每個時段的場橋調(diào)度優(yōu)化都是獨立進行的，沒有考慮場橋的動態(tài)調(diào)度問題，未來需進一步研究場橋動態(tài)調(diào)度與集卡預(yù)約份額協(xié)同優(yōu)化，以及其他高效啟發(fā)式算法的應(yīng)用.

[1]ZHANG C,WAN Y,LIU J,et al.Dynamic crane deployment in container storage yards[J].Transportation Research Part B：Methodological,2002,36(6)：537-555.

[2]LINN R,LIU J,WAN Y,et al.Rubber tired gantry crane deployment for container yard operation[J].Computers&Industrial Engineering,2003,45(3)：429-442.

[3]李建忠.碼頭堆場龍門起重機動態(tài)配置優(yōu)化模型[J].交通運輸工程學(xué)報,2005,5(1)：70-74.[LI J Z.Crane dynamic deployment model of container storage yard[J].Journal of Traffic and Transportation Engineering,2005,5(1)：70-74.]

[4]吳達,冉祥辰.集裝箱預(yù)約集港的探索與實踐[J].港口經(jīng)濟,2012(3)：5-9.[WU D,RAN X C.Exploration and practice of export container appointment in container terminals[J].Port Economy,2012(3)：5-9.]

[5]ZHANG X,ZENG Q,CHEN W.Optimization model for truck appointment in container terminals[J].Procedia-Social and Behavioral Sciences,2013,96(6)：1938-1947.

[6]CHEN G,GOVINDAN K,GOLIAS M M.Reducing truck emissions at container terminals in a low carbon economy：Proposal of a queueing-based bi-objective model for optimizing truck arrival pattern[J].Transportation Research Part E,2013,55(6)：3-22.

[7]曾慶成,張笑菊,張倩.內(nèi)外集卡協(xié)同服務(wù)的碼頭集卡預(yù)約優(yōu)化模型[J].交通運輸工程學(xué)報,2016,16(1)：115-122.[ZENG Q C,ZHANG X J,ZHANG Q.Optimization model of terminal container truck appointment based on coordinated service of inner and outercontainertrucks[J].JournalofTraffic and Transportation Engineering,2016,16(1)：115-122.]

[8]邵乾虔,靳志宏,邢磊.基于聯(lián)動預(yù)約模式的集裝箱碼頭集疏港仿真優(yōu)化[J].交通運輸系統(tǒng)工程與信息,2016,16(4)：217-224.[SHAO Q Q,JIN Z H,XING L.Simulation optimization of consolidation and configuration in container terminals based on cooperative appointment[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(4)：217-224.]