離散時(shí)間窗下集卡數(shù)量動(dòng)態(tài)優(yōu)化研究

張 彥，梁承姬

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

2.1 前提和假設(shè)

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

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

2.2 模型建立

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

上述公式的含義為:

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

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

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

式(4)為每個(gè)集裝箱只能運(yùn)輸一次，因此只有一個(gè)開(kāi)始時(shí)間;

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

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

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

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

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

3.1 測(cè)試問(wèn)題和參數(shù)設(shè)置

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

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

表1 第1 和第2 組實(shí)驗(yàn)組合

表2 第3 組實(shí)驗(yàn)組合

3.2 結(jié)果分析

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

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

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

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

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

圖2 集卡數(shù)量增長(zhǎng)率趨勢(shì)圖

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

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

4 結(jié)論

針對(duì)集裝箱港口運(yùn)輸過(guò)程，為保證橋吊資源得到優(yōu)先滿足，為集裝箱任務(wù)添加了時(shí)間窗約束，從而為工作過(guò)程中需要的集卡數(shù)量問(wèn)題建立了一個(gè)MIP 模型，目標(biāo)是按既定的集裝箱任務(wù)編排表確定最少的集卡使用量。筆者采用隨機(jī)模擬工作時(shí)間，采用連續(xù)遞增的時(shí)間窗，將任務(wù)的最晚結(jié)束時(shí)間限制在一定的范圍內(nèi)，從而在滿足相繼任務(wù)時(shí)間窗的條件下對(duì)問(wèn)題進(jìn)行了求解。數(shù)值仿真成功地對(duì)模型進(jìn)行了求解，得到了合理的集卡數(shù)量，同時(shí)通過(guò)對(duì)比分析，也說(shuō)明了任務(wù)量和集卡數(shù)量的相關(guān)關(guān)系。仿真結(jié)果從理論上保證了模型的現(xiàn)實(shí)意義，比較符合現(xiàn)實(shí)的生產(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］.大連海事大學(xué)學(xué)報(bào)，2011，37(2):25－27.

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

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

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

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