張 彥，梁承姬

(上海海事大學 物流研究中心，上海201306)

隨著中國港口經(jīng)濟的發(fā)展，各港口集裝箱吞吐量不斷上升，然而，如何利用現(xiàn)有設備資源對集裝箱進行運輸和調度，以滿足班輪公司的需求，成為港口管理層面臨的挑戰(zhàn)。由于橋吊為港口稀缺資源，筆者在對港口集裝箱運輸車輛進行數(shù)量優(yōu)化的同時，將橋吊資源考慮進去并以時間窗作為其資源約束，在滿足各任務時間窗約束的情況下保證現(xiàn)有的集卡設備能夠得到最大限度的利用。

集卡起著連接岸邊橋吊和堆場龍門吊工作的中轉作用，其工作效率的高低直接影響到岸邊任務完成的時間和堆存任務能否順暢進行，進而影響到班輪公司能否按照預定時間安排離開泊位。集卡數(shù)量在很大程度上影響著碼頭的工作效率，但是兩者并非嚴格的線性關系。在一定范圍內增加集卡數(shù)量能夠提高碼頭的工作效率，但是當集卡數(shù)量達到一定量的時候，由于港口道路情況的限制，繼續(xù)增加集卡數(shù)量反而會降低碼頭的工作效率。同時集卡作業(yè)具有動態(tài)性，一臺集卡可以連續(xù)工作，完成多個任務，因此有關集卡數(shù)量的動態(tài)優(yōu)化也成為可能。集卡的數(shù)量問題是關系到整個港口生產(chǎn)效率和成本的關鍵問題。

目前國內外有關集卡配置的研究比較少，大部分是附帶在集卡調度問題上，但是一次的集卡調度得出的集卡數(shù)量可信度并不能令人信服，因此對于集卡配置問題還需要進行單獨研究。PYUNG 等采用兩階段啟發(fā)式研究了港口靜態(tài)環(huán)境下集卡數(shù)量和路徑問題。第一階段以車輛運輸時間最短為目標，求得AGV 的數(shù)量下限［1］。第二階段采用禁忌搜索算法在AGV 數(shù)量最少情況下求解AGV 路徑問題。MAURO 等采用啟發(fā)式對有時間窗約束的集卡數(shù)量和路徑問題進行了研究，并給出了比較詳細的啟發(fā)式算法步驟［2］。IRIS 等研究了時間窗約束下，運輸車輛數(shù)量最小化問題［3］。PYUNG 等研究了有多個收發(fā)點的AGV 數(shù)量問題，使用排隊模型來估計部分等待時間，在滿足預定的等待時間約束情況下，按照最近車輛優(yōu)先選擇的原則，對AGV數(shù)量最小化進行了求解，并進行了多次實驗來進行驗證［4］。JI 等對自動化碼頭的運輸系統(tǒng)進行了數(shù)學分析，提出了一個近似的數(shù)學分析模型，并進行了多次仿真實驗對模型進行了驗證［5］。NGUYEN和KIM 建立了混合整數(shù)規(guī)劃模型求解自動化碼頭中跨運機的最優(yōu)任務問題，并針對問題的時間復雜度建立了啟發(fā)式算法以滿足計算時間要求［6］。KIM 和BAE 針對已知的集裝箱作業(yè)任務順序表安排如何調度AGV 小車，使用了混合整數(shù)規(guī)劃對小車的作業(yè)任務安排進行了優(yōu)化，最后采用啟發(fā)式算法對模型進行了求解［7］。

國內對集卡數(shù)量問題的研究比較少，往往是數(shù)量問題包含在路徑優(yōu)化模型中。王軍和許曉雷研究了作業(yè)面模式下，綜合考慮岸橋作業(yè)時間、場橋作業(yè)時間，建立了以裝卸箱總作業(yè)時間最短為目標的集卡路徑問題。其思路是將所有集卡簡化成一臺集卡進行作業(yè)，因此并沒有考慮集卡數(shù)量問題［8］。曾慶成和楊忠振研究了集裝箱港口裝卸過程中集卡調度問題和最小化裝卸橋等待時間［9］。趙寧等研究了集卡的利用率，建立了集裝箱港口發(fā)箱任務的集卡指派模型［10］。楊靜蕾、丁以中以上海外高橋集裝箱碼頭為例，構建包括多種設備資源的動態(tài)多級排隊網(wǎng)絡，通過仿真得出了最優(yōu)機械配比和岸橋臺數(shù)［11］。韓曉龍研究了裝卸作業(yè)中的資源配置問題，在岸橋分配優(yōu)化的動態(tài)規(guī)劃模型之后，提出集卡的配置模型，求出保證岸橋連續(xù)作業(yè)的集卡最小配置數(shù)量并對集卡路徑問題進行了研究［12］。

從以上研究可以發(fā)現(xiàn)，針對集卡數(shù)量問題進行的單獨研究還很少，把運輸車輛數(shù)量和路徑綜合進行研究往往只關注如何安排集卡路徑而忽視了對集卡數(shù)量進行優(yōu)化，由于單獨研究車輛數(shù)量問題對實際減少港口運作成本影響很大，因此將集卡數(shù)量作為關鍵問題進行深入研究很有必要。

1 問題描述

岸橋裝卸的每個任務都有一個時間窗，［sti，dti］表示最早開始時間和最晚結束時間。時間窗是在比較滯后成本和提前成本的基礎上均衡得到的，同時由于時間窗的存在，使橋吊和集卡工作具有更多的靈活性。碼頭前沿加一個緩存區(qū)，能夠更合理地使用橋吊，減少橋吊的工作等待時間，同時有利于集卡的調度。時間窗的分段數(shù)就是緩存區(qū)的大小。為了使集卡數(shù)量最小，集卡可以在滿足前后兩個任務時間約束的前提下自由地選擇開始時間，可大大地方便集卡的調度工作。集卡的前后任務可以用一個最大流網(wǎng)絡圖來表示，如圖1 所示。網(wǎng)絡圖節(jié)點代表任務的時間窗，由于每個任務只能由一輛車來運輸，因此弧的最大流量為1，據(jù)此尋找完成所有任務所需的最少集卡數(shù)量。

圖1 網(wǎng)絡示意圖

2 集卡數(shù)量計算模型

2.1 前提和假設

集卡數(shù)量計算模型假設如下:①集裝箱任務總數(shù)已知;②每個集裝箱的最早開始時間和最遲結束時間已知;③每個集裝箱的起點和目的地均已知;④有足夠的場橋處理集卡所運集裝箱，不考慮場橋因素;⑤集卡開始工作位置和結束位置都位于同一位置;⑥不考慮集卡擁擠的干擾。

該模型是在已知集裝箱預編排計劃下建立的集卡需求量模型，故有關集裝箱的數(shù)量和堆存位置都是已知的，因此假設①到假設③都是合理的。由于橋吊是稀缺資源，集裝箱港口一般會優(yōu)先考慮橋吊作業(yè)，而場橋數(shù)量一般都能滿足要求，即不允許場橋耽誤集卡運輸時間，因此假設④也是合理的。在港口集卡開始工作前和結束工作后都有固定的位置用來停放集卡，因此假設⑤是合理的。該模型建立過程中并不考慮集卡數(shù)量過多造成的干擾，可以不考慮擁擠的因素。

2.2 模型建立

建立的混合整數(shù)規(guī)劃模型如下:

上述公式的含義為:

式(1)為在起始節(jié)點，流出減流入為v，即所使用的最少數(shù)量;

式(2)為在終止節(jié)點，流出減流入為－v;

式(3)為在中間節(jié)點，流入=流出;

式(4)為每個集裝箱只能運輸一次，因此只有一個開始時間;

式(5)為兩個集裝箱由同一輛集卡相繼完成所需滿足的條件;

式(6)為所有集裝箱任務的工作時間加上相繼任務的準備時間之和要小于總的工作時間;

式(7)和式(8)表示決策變量為0/ 1 變量。

3 數(shù)值仿真示例分析

仿真采用隨機生成的數(shù)據(jù)，使用Cplex V12.2求解器對上述模型進行模擬。用于測試的計算機配置為:Intel(R)Core(TM)2 Duo CPU T5450 @1.66 GHz，0.99 GB RAMS。

3.1 測試問題和參數(shù)設置

數(shù)值仿真進行了3 組實驗，每組實驗的時間數(shù)據(jù)都采用隨機生成得到。設總工作時間為T。其中，每個任務的工作時間wi通過均勻分布U(1，3)產(chǎn)生，每個任務的開始時間si通過均勻分布U(0，T)生成，而任務i 和任務j 的準備時間Pij通過均勻分布U(0，3)生成。

第1 組實驗是對集卡的使用數(shù)量進行頻數(shù)統(tǒng)計，實驗數(shù)據(jù)如表1 所示，工作時間從100 min 逐步增加到200 min、300 min 和400 min，從而計算不同集卡數(shù)量出現(xiàn)的次數(shù)。為了保證實驗的隨機性，該實驗在不同的工作時間下對20、30、40、50個任務各進行10 次實驗，每個工作時間作為1 組實驗進行匯總，最后匯總4 組實驗結果，也就是在每個工作時間下總共進行了40 次實驗，而總實驗次數(shù)是160 次。第2 組實驗是對集卡的數(shù)量增長率進行分析，所采用的實驗數(shù)據(jù)與第1 組實驗一致，在集卡數(shù)量分別為2 臺和3 臺的情況下，觀測集卡數(shù)量隨任務量變化的情況，同時對比在4 種工作時間情況下，兩種集卡數(shù)量出現(xiàn)頻數(shù)的變化趨勢。第3 組實驗是對集卡的使用數(shù)量與工作量之間的關系進行分析，實驗組合如表2 所示，在工作總時間為100 min，對任務由20 個最終增至200 個的不同實驗組情況下，每組進行10 次隨機實驗，觀察集卡使用量的變化情況。

表1 第1 和第2 組實驗組合

表2 第3 組實驗組合

3.2 結果分析

要注意的是，模型的重點并不在于求解集卡路徑，由于每次實驗的結果都是變動的，因此由所得結果無法判定哪次實驗所得路徑是集卡最優(yōu)路徑。在確定了集卡的最優(yōu)數(shù)量之后，可以根據(jù)實驗結果與集卡最優(yōu)數(shù)量相吻合而得到的集卡路徑，參考安排集裝箱的位置。

(1)第1 組實驗結果分析。由表1 數(shù)據(jù)，使用Cplex V12.2 求解，可得到表3 數(shù)據(jù)。

表3 集卡使用頻數(shù)統(tǒng)計

由表3 可看出，隨著時間的變化，在相同任務量下，工作時間越長，集卡平均使用量越低，由此可以看出，在總任務量較少的情況下，使用2 臺集卡基本可滿足要求。在相同任務量下，集卡工作時間越長，其可閑置的時間就越多，因此可以使用較少數(shù)量的集卡來完成所有任務。在總工作時間為300 min 時，2 臺集卡出現(xiàn)的次數(shù)是最多的，這時可以僅安排2 臺集卡工作，即能滿足要求。

(2)第2 組實驗結果分析。集卡數(shù)量增長趨勢如圖2 所示。由圖2 可看出，總工作時間越短，集卡數(shù)量增加的速度越快。當任務由30 個增到40 個，總工作時間為400 min 的情況下，10 次實驗中3 臺集卡出現(xiàn)的次數(shù)由2 次增加到4 次，頻數(shù)增加了20%;而當總工作時間減小為100 min時，在10 次實驗中，3 臺集卡出現(xiàn)的次數(shù)立即由2次增加到了7 次，頻數(shù)增加了50%。也就是說，在集卡調度過程中，總工作時間與成本成反比，減少集卡的使用成本，是以增加工作時間來保證的。

圖2 集卡數(shù)量增長率趨勢圖

(3)第3 組實驗結果分析。圖3 為集卡數(shù)量變化趨勢圖?？梢钥闯觯S著工作任務的增多，集卡的使用數(shù)量有逐漸增加的趨勢。當工作時間固定為100 min 時，隨著任務量的增加，3 臺集卡出現(xiàn)的次數(shù)逐漸增加，而2 臺集卡出現(xiàn)的次數(shù)相應減少。在任務量為40 個時，2 臺集卡出現(xiàn)的次數(shù)驟減，從8 臺降低到3 臺，說明任務量超過40 個時，2 臺集卡已經(jīng)遠遠無法滿足工作需求。在任務量為120 個時，2 臺集卡已經(jīng)不能滿足要求，10次隨機實驗集卡使用量均為3 臺。繼續(xù)增加任務量，集卡使用量增加到了4 臺，隨著任務量的繼續(xù)增加，3 臺集卡出現(xiàn)的次數(shù)在降低，而4 臺集卡出現(xiàn)次數(shù)逐漸增加，但在120 ～200 個任務范圍內，3臺集卡的出現(xiàn)頻數(shù)保持在90%。據(jù)此可將工作時間為100 min，任務量為40 個看作轉折點。當任務量小于40 個時，選擇2 臺集卡，當任務量在40 ～200 個之間時，選擇3 臺集卡。這樣安排集卡既能滿足任務量需求，又能保證集卡使用成本最低。

圖3 集卡數(shù)量隨工作量變化趨勢圖

4 結論

針對集裝箱港口運輸過程，為保證橋吊資源得到優(yōu)先滿足，為集裝箱任務添加了時間窗約束，從而為工作過程中需要的集卡數(shù)量問題建立了一個MIP 模型，目標是按既定的集裝箱任務編排表確定最少的集卡使用量。筆者采用隨機模擬工作時間，采用連續(xù)遞增的時間窗，將任務的最晚結束時間限制在一定的范圍內，從而在滿足相繼任務時間窗的條件下對問題進行了求解。數(shù)值仿真成功地對模型進行了求解，得到了合理的集卡數(shù)量，同時通過對比分析，也說明了任務量和集卡數(shù)量的相關關系。仿真結果從理論上保證了模型的現(xiàn)實意義，比較符合現(xiàn)實的生產(chǎn)狀況。

［1］ PYUNG H K，WOON S L，DONG W J.Fleet sizing and vehicle routing for container transportation in a static environment［J］.OR Spectrum，2004(26):193－209.

［2］ MAURO D A，MICHELE M，CORRADA P，et al.Heuristic approaches for the fleet size and mix vehicle routing problem with time windows ［J］. Transportation Science，2007，41(4):516－526.

［3］ IRIS F A，VIS R B M，DE K，et al.Minimum vehicle fleet size under time－window constraints at a container terminal［J］. Transportation Science，2005，39(2):249－260.

［4］ PYUNG H K，JAEJIN J，JUNGDAE S. Estimation of part waiting time and fleet sizing in AGV systems［J］.The International Journal of Flexible Manufacturing Systems，2005(16):211－228.

［5］ JI M，XIA J.Analysis of vehicle requirements in a general automated guided vehicle system based transportation system［J］.Computers ＆ Industrial Engineering，2010(59):544－551.

［6］ NGUYEN V D，KIM K H. A dispatching method for automated lifting vehicles in automated port container terminals［J］. Computers ＆ Industrial Engineering，2009(56):1002－1020.

［7］ KIM K H，BAE J W.A look－ahead dispatching method for automated guided vehicles in automated port container terminals［J］.Transportation Science，2004，38(2):224－234.

［8］ 王軍，許曉雷. 集裝箱碼頭集卡作業(yè)的路徑選擇［J］.大連海事大學學報，2011，37(2):25－27.

［9］ 曾慶成，楊忠振.集裝箱碼頭集卡調度模型與Q 學習算法［J］.哈爾濱工程大學學報，2008，29(1):1－4.

［10］趙寧，宓為建，何軍良.集裝箱碼頭發(fā)箱任務的集卡指派模型［J］.上海海事大學學報，2011，32(1):8－12.

［11］ 楊靜蕾，丁以中.集裝箱港口設備配置的模擬研究［J］.系統(tǒng)仿真學報，2003，15(8):12－17.

［12］韓曉龍.集裝箱港口裝卸作業(yè)資源配置研究［D］.上海:上海海事大學圖書館，2005.