基于閘口資源配置的送箱集卡預約優化模型*

于 蒙 周 密

(武漢理工大學物流工程學院 武漢 430063)

0 引 言

隨著國際貿易的快速發展，集裝箱進出口量越來越大，集卡作為運輸集裝箱的主要工具，其需求量也快速增加，這將出現高峰時期港口運輸集裝箱的集卡同時抵達碼頭，造成港口各個節點擁堵.由于碼頭是一個集成作業系統，一個環節的作業效率將影響整個碼頭的作業效率，所以，港口擁堵將降低整個碼頭的作業效率.

為緩解集卡在港口的擁堵，國內外很多港口，如洛杉磯港、溫哥華港，以及上海洋山港等先后實行了集卡預約系統.國內外學者也做了很多研究，Chen等[1]通過為每支到港船舶制定時間窗來管理集卡的到達，從而緩解集裝箱碼頭閘口的擁堵.Zhang等[2]利用休假式排隊模型描述場橋協同服務內外集卡的過程，基于非平穩的排隊理論更準確的估計了外集卡在閘口和堆場的平均等待時間.Yi等[3]提出了一種預約調度方法，該方法考慮了停留在碼頭內的集卡成本、滯期費、集裝箱運輸成本，每個時間窗和每個區塊允許的約會次數以及每個時間窗內可用集卡的數量.與以前的研究不同，該研究在構建預約時間表時考慮預約對終端等待時間的影響.利用基于Frank-Wolfe算法的數學公式和啟發式算法，以在合理的計算時間內解決該問題；滕藤等[4]為緩解碼頭的擁堵問題，利用基于支持向量機和卡爾曼濾波的方法預測集卡到達的時間，提高集卡到達時間的準確性；曾慶成等[5]在預約模型中考慮了內部集卡對堆場作業的影響，提出了基于內外集卡協同服務的優化模型，利用休假式排隊系統，結合遺傳算法優化集卡在碼頭的等待成本；楊惠云等[6]根據不同預約時段集卡到達類型的不同來改變閘口的數量，結果表明，可變閘口調度的集卡預約優化減少了集卡的排隊時間.

綜上所述，目前碼頭集卡預約排隊模型大多考慮集卡到達、服務分布等規律，而未考慮碼頭資源的優化配置.閘口通道數和堆場的容量有限也是造成碼頭擁堵的原因，以送箱集卡為研究對象，當閘口通道數目有限時，可根據不同預約時段集卡的集港數量來安排閘口數[7-8].因此，在考慮碼頭現有設施條件下，優化其閘口的資源配置，建立集卡到港預約排隊模型，并結合自適應遺傳算法優化集卡預約額，從而使集卡在閘口和堆場的平均等待時間最小.

1 集卡預約優化模型的構建

1.1 問題描述

集卡進入碼頭后，先后經過閘口和堆場完成運輸任務，然后從出場閘口離開.在碼頭實際中，港口集裝箱的進出口業務繁多，集卡到港時間的隨機性是碼頭擁堵的重要原因，集卡預約可控制集卡的集港量，使集卡到港時間相對確定.閘口通道數有限也會造成集卡大量排隊，閘口送提箱通道的業務不同，所需的服務時間也不同，當送箱通道服務有過大壓力時，在不影響提箱集卡作業的前提下，可開放一定數量的提箱通道協助送箱集卡完成進閘業務.集卡進入堆場后，需要在堆場排隊，若堆場排隊隊長過長，堆場容量有限，反過來又會導致集卡在閘口的排隊[9].

為解決上述問題，在集卡預約模式下，考慮閘口資源和堆場容量對集卡排隊的影響建立預約模型.在閘口處，可視為M/M/C(t)的排隊模型，每個堆場分區滿足M/G/1/R的排隊模型，以集卡在閘口和堆場平均等待時間最小為優化目標，優化各時段的預約份額，建立如下模型.

1.2 預約模型的建立

1.2.1參數定義

1.2.2預約模型的構建

目標函數：

(1)

約束條件:

(2)

(3)

m=T/p

(4)

閘口處：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

堆場處：

(12)

(13)

(14)

(15)

(16)

(17)

(18)

式(1)為集卡在閘口和堆場平均等待時間最??；式(2)為集卡總數等于決策期內預約份額之和；式(3)為在預約時段內集卡未到和遲到后實際到達的數量；式(4)為將預約時段p劃分為t的數量；式(5)為t時刻集卡到達閘口的量；式(6)為t時刻在閘口g的集卡到達量；式(7)為t時刻第g個閘口利用率與隊長的關系；式(8)為在閘口g處集卡排隊和不需要排隊的隊長；式(9)為t時刻第g個閘口集卡的離開量；式(10)為集卡P時段在閘口的平均等待時間；式(11)為閘口處集卡在決策期的平均等待時間；式(12)為t時刻集卡到達堆場的量；式(13)為t時刻堆場隊長與利用率的關系；式(14)為堆場y處集卡排隊和不需要排隊的隊長；式(15)為集卡在任意時刻不超過其容量限制；式(16)為t時刻集卡離開堆場的量；式(17)為集卡P時段在堆場的平均等待時間；式(18)為堆場處集卡在決策期的平均等待時間.

2 算法設計

由于傳統遺傳算法在進化過程中最優解易丟失，容易陷入局部最優解，所以，本文采用適應度值排序的自適應遺傳算法，使算法不易陷入局部最優，具體算法步驟如下.

步驟1編碼及種群初始化 染色體采用實數編碼的方式進行編碼，一條染色體的長度為決策期內預約時段數，其基因值表示集卡預約數，首先隨機生成一組正整數，使其和等于在決策期內集卡的預約總數，圖1為一條染色體，初始種群數為200.

圖1 染色體示意圖

步驟2

碧洲計算適應度 根據模型約束式(2)～式(18)，計算每個個體的排隊等待時間

F

，其適應度值

f

可見式(19)，計算每條染色體的適應度值，并求出種群適應度的平均值與個體適應度值排序.

f=1/F

(19)

步驟3選擇與交叉 本文采用輪盤賭進行選擇，隨機從父代中選擇兩個個體交叉，由于本文采用的實數編碼，所以采用融合交叉的方式對父代染色體進行交叉，見式(20)，其中α為參數，0<α<1.

(20)

將選中的兩個個體適應度值較大的排序號代入到計算交叉概率pc的式(21)中,用適應度值的排序號替代適應度值能適當增加迭代后期的交叉概率，從而使算法不易陷入局部最優.

式中：N1為選中的兩個染色體中適應度值較大的序號；N2為種群平均適應度值的序號；N3為種群最大適應度值的序號；Pc1為最大交叉概率；Pc2為最小交叉概率.

步驟4變異 變異采用實值變異的方式，為確保變異后解的可行性且便以操作，隨機選中染色體的兩點，保證兩點的差值為(0,3],互換兩點的數值即可實現變異操作，變異過程見圖2.

圖2 染色體變異示意圖

變異概率pm按式(22)進行自適應調整，其中，Pm1為最大變異概率，Pm2為最小變異概率.

(22)

步驟5算法終止 當進化次數達到最大進化次數后，算法終止，得出集卡預約等待時間最小的預約方案作為最優解，否則算法返回第二步.

3 實例分析

3.1 算例設計

以某集裝箱碼頭為例進行分析，將決策期N定為7 d，并將其分為84個預約時段，所以每個預約時段長度為2 h.該碼頭有八個進場閘口，每個閘口的服務能力為40輛/h，場橋服務能力為20輛/h，決策期內集卡預約到港量為5 000輛 ，堆場最大容量為10.

該碼頭閘口有四個送箱通道，四個提箱通道，在不影響提箱集卡作業的前提條件下，本文只考慮送箱集卡的預約優化問題.當預約兩小時內集卡的到港數小于40輛時，滿足閘口和堆場的服務能力，此時開放1個送箱通道；當預約兩小時內集卡的到港數在161～200輛時，此時需要開放4個送箱通道和1個提箱通道.由于每個預約時段的集卡到達量在變化，所以各預約時段集卡所需的閘口通道數見表1,這樣不僅可提高閘口的利用率，也能節約碼頭資源.

表1 不同時段集卡預約到港量對應的閘口通道數目

3.2 模型驗證

通過以上數據，運用matlab對預約模型進行編程，見圖3，得出集卡在碼頭的平均等待時間為14.13 min,根據對碼頭的調研，集卡的實際平均周轉時間大約為22 min，驗證了建立模型的可行性.

圖3 算法收斂圖

3.3 預約優化模型驗證

圖4為有無預約情況下等待時間和集卡到達量的對比，發現未實施預約前，集卡在某些時段大量集港，存在擁堵現象，而某些時段集港數極低，造成碼頭資源的浪費；實施預約后，集卡在每個預約時段的集港數量控制在50～80輛，將高峰時段的集卡數分散到集港低谷期，有效的減少了碼頭擁堵現象.

圖4 集卡到港規律對比

預約實施前后集卡在碼頭的平均等待時間變化見表2，變化趨勢見圖5.結果表明，未實施預約前，在閘口處集卡的平均等待時間為4.89 min，最高等待時間為13.86 min，預約后平均等待時間降為3.97 min，減少約1 min，相比未預約之前，集卡集港較均勻，所以預約集港能明顯降低集卡的排隊時間.

表2 集卡在碼頭的等待時間 min

圖5 集卡在碼頭的排隊等待時間

未實施預約前，在堆場處集卡的平均等待時間為15.73 min，最高等待時間約為38 min，預約后集卡的平均等待時間降為10.16 min，減少了5.57 min，預約后最高等待時間降為20 min.

4 結 束 語

為解決集卡在集裝箱碼頭的堵塞問題，在閘口處，通過設置可變閘口的方式來配置閘口通道資源，在堆場處，考慮場橋的服務能力來限制堆場容量，從而提高整個碼頭的通行能力.本文考慮閘口和堆場的條件約束構建了集卡預約優化模型，通過優化各時段的集卡預約到港數目來減少集卡的平均等待時間.為求解預約優化模型，設計了采用適應度值排序的自適應的遺傳算法來求解模型.結果表明，考慮閘口和堆場資源限制的預約模型能有效的減少集卡在閘口和堆場的排隊時間.