混堆集裝箱堆場的出口箱位優選干擾管理

周鵬飛, 趙金秋, 尚爾進

(大連理工大學 水利工程學院，遼寧 大連 116024)

?

混堆集裝箱堆場的出口箱位優選干擾管理

周鵬飛, 趙金秋, 尚爾進

(大連理工大學 水利工程學院，遼寧 大連 116024)

針對進出口集裝箱混合存放堆場的出口收箱作業容易受干擾問題，基于出口箱收箱次列提出了堆場作業受干擾的度量方法；建立了考慮收箱次序擾動關聯成本的出口箱位優選干擾管理模型，壓箱量和龍門吊大車行駛距離的加權組合目標函數項表示收箱作業和翻箱總成本，箱位偏移的目標函數項表示干擾關聯成本；基于干擾恢復模型解的局部性特點，設計了局部加速的改進禁忌搜索算法，利用鄰域控制優化搜索方向和范圍，加速局部搜索，提高算法收斂速度。實驗結果顯示：提出的干擾管理方法比重調度提高10%以上的精度。

集裝箱運輸；堆場箱位優選；干擾管理；禁忌搜索算法；混合存放模式；集裝箱堆場；動態環境

隨著集裝箱運輸需求的不斷增長，越來越多港口為了提高堆場利用率和通過能力，開始在集裝箱碼頭堆場采用進、出口箱混合存放模式，如釜山港、香港港、上海港等。進/出口箱同場區存放的混合模式可以充分利用堆場箱位，提高了堆場資源利用率和通過能力。但混合存放模式的作業管理復雜，龍門吊堆取箱作業容易相互干擾，龍門吊作業的箱位優選需要考慮相關堆取箱作業的協調以及干擾影響。

集裝箱碼頭堆場龍門吊根據堆、取箱任務序列依次到作業點(箱位)執行作業，堆箱作業箱位點的選擇影響龍門吊作業成本，混合存放作業下還將影響關聯取箱作業等其他任務的執行。針對混合存放作業的堆場箱位選擇問題研究主要有：Gambardella等利用線性混合整數規劃為到港船舶配置岸橋、混合存放箱區及其龍門吊，減少設備沖突和等待時間，此研究未涉及箱區內的作業和壓箱量優化[1]。Zhang等針對混合存放箱區提出分配策略，并在此基礎上構建了箱區分配模型[2]，類似地，Bazzazi等提出了考慮按箱屬性分組的箱區分配模型[3]。康海貴等構建了混合存放箱區的進口箱位分配整數規劃模型，優化拖車行駛距離和同組箱占用箱區數[4]。陶經輝等將混合存放箱區分配問題分解為兩階段：階段I平衡箱區作業量和階段II平衡箱組，構建模型并進行了仿真對比分析[5]。楊曼等以平衡箱區間作業量和最小化泊位到堆場的運距為目標建立了混合存放作業下箱區分配優化模型[6]。郝聚民等基于圖搜索和模式識別方法建立了隨機條件下的混合存放作業貝位優選模型[7]。鄭紅星等根據集裝箱混合存放作業規則設定了集裝箱優先級，以集裝箱新增壓箱數最小為目標，提出了箱位分配優化方法[8]。考慮出口集裝箱到港時間的不確定性，周鵬飛等提出了出口集裝箱位分配的兩級調度策略，建立了數學規劃模型優化堆場起吊設備作業成本和翻箱量，并基于禁忌搜索開發了啟發式算法[9]。綜上可看出：1)現有混合存放作業堆場研究主要以平衡箱區作業量為目標，為進出口箱指定箱區或貝位，未考慮箱區內作業成本與翻箱量影響[1-7]；2)具體箱位優選問題研究考慮了堆箱優先級和箱重等因素，未考慮不確定干擾發生后的響應與處理以及混合存放作業下對關聯作業的干擾影響[8-9]。

混合存放模式的集裝箱位優選主要依據堆場收發箱任務計劃(客戶的提箱和交箱任務)，客戶任務容易發生干擾和偏差，造成實際作業成本上升，設備等待，甚至沖突等，因此混合存放模式堆場的箱位優選需建立有效的任務擾動恢復機制以降低干擾影響。干擾管理是由Clausen等提出的新興管理方法[10]，其核心思想是針對干擾事件，利用干擾管理模型和算法獲得干擾恢復方案，以較小的成本應對干擾事件，近年來已在航班計劃[11]、設備調度[12]等多個領域得到成功應用。針對集裝箱碼頭生產管理領域的泊位分配和岸橋調度問題，曾慶成等[13]、楊春霞等[14]和林慶福等[15]分別提出了干擾管理方法，實驗分析顯示了較好的調度性能。利用干擾管理的思想來處理堆場收發箱任務計劃的擾動，優選干擾發生后箱位恢復方案可減少堆場作業的干擾成本。

本文將針對混合存放作業堆場的出口收箱作業的箱位優選問題，考慮進口提箱和翻箱作業的干擾影響，構建干擾管理模型，并針對模型特點開發禁忌搜索算法，提高堆場龍門吊作業的抗干擾能力。

1 干擾識別與度量

混合存放的集裝箱區允許在同一時間內存放進口箱和出口箱，堆場龍門吊操作任務包括堆場收箱(堆放箱)、發箱(提取箱)以及堆場內的翻倒箱等。龍門吊作業任務的優先權不完全相同，比如臨近船舶到港時出口集裝箱的收箱作業(堆放箱)通常具有較高優先級，在其作業間隙允許發箱以及翻倒箱等。制定出口收箱作業計劃時通常要考慮節約堆場龍門吊作業成本，減少裝船時的翻倒箱等。如果客戶交箱(碼頭收箱)次序確定，堆場出口收箱作業計劃可轉化為以客戶交箱次序為已知條件，為計劃進場的出口集裝箱優選分配箱位的問題。客戶交箱次序可利用客戶預約或集卡位置信息進行估計，由于客戶預約和集卡信息具有動態性，比如客戶預約的取消或交通擁堵造成的延遲等，因此估計的交箱次序容易發生改變和干擾。如果交箱次序改變，而堆場作業仍按原計劃執行，將造成龍門吊等待、作業成本增加、外集卡的服務時間窗延長等問題，同時也影響其他作業計劃的執行，如提箱作業計劃等。圖2是箱位計劃(圖1所示)的作業干擾影響、重調度和干擾管理的示例。可以看出：箱4延遲和箱13提前，如果仍按原箱位分配方案執行將造成龍門吊大車移動增加4貝距離；如果采用重調度方法重新分配箱位，龍門吊大車的移動總距離為10貝；如果采用干擾管理方法，龍門吊大車的移動總距離為4貝，較重調度方法減少了6貝距離。

注：2(10)表示出口箱，標識碼為2，優先級為10(越大裝船越早)；灰色區域數字表示進口提箱及其次序圖1 干擾前箱位的計劃Fig.1 Slots plan before disruption

2 出口集裝箱位優選干擾管理模型

2.1 模型假設

1)進口集裝箱和出口集裝箱可在堆場的同貝位不同堆棧內存放，龍門吊按計劃優先作業出口箱；

圖2 混合存放模式的堆場作業計劃與干擾恢復示例Fig.2 Example of handling and disruption recovery in mixture-container-storage-moded yard

圖3 堆場收箱次序干擾識別(11號箱提前)Fig.3 Disruption recognition of delivery sequence

2)干擾事件發生前的堆場作業計劃(包括取箱、翻倒箱和收箱)和出口箱位分配方案已知。

3)出口箱位分配引起的壓箱量計算根據長途重箱優先裝船原則計算：裝船優先級c=d×wmax+w，w是箱重級別，d是目的港次序，wmax是最大箱重級別，c越大越早裝船。

2.2 干擾恢復的關聯成本度量

2.3 模型構建

(1)

約束可表示為

xij=xjii>j,i∈{N1+1,N1+2,…，N1+N2),

j∈{1,2,…，N1+N2}

(2)

(3)

(4)

aij+xih+xjh≠2 i

h∈{N1+1,N2+2,…，N1+N2}

(5)

xih+xjh+xij≠2 i

j,h∈{N1+1,N1+2,…，N1+N2}

(6)

(7)

(8)

i,j∈{N1+1,N1+2,…N1+N2}

(9)

i∈{N1+1,N1+2,…N1+N2}

(10)

(11)

(12)

k∈{1,2，…，B}

(13)

(14)

(15)

(16)

(17)

3 改進禁忌搜索算法

干擾管理模型的求解具有局部性，利用模型優解的局部性特點設計局部加速的改進禁忌搜索算法，算法禁忌表記錄近期搜索的解，避免迂回重復探索，保障探索的多樣性，實現算法尋優的全局性。改進禁忌搜索算法的設計要點如下：

1)禁忌搜索算法的初始解：選用干擾事件發生前的箱位計劃方案作為算法搜索的初始解；

2)探索解的適應度評價函數：探索解的優劣判別標準，利用干擾恢復模型的目標函數f(x)作為探索解適應度的評價函數，目標函數值越小越優；

3)搜索鄰域H(x)的控制：算法的搜索鄰域為可交換箱位集合，包括箱與箱的位置交換和空箱位交換兩種形式。搜索鄰域控制規則：①可交換箱對(i,j)中的箱i∈C，C為受干擾箱所在堆棧的計劃進場的集裝箱集合；②考慮箱位交換的作業成本影響，可交換箱對(i，j)的箱i和j滿足|ni-nj|≤Dis條件，ni和nj為箱i和j的客戶交箱次序，Dis為搜索鄰域的控制參數；③空箱位交換(箱位重新分配到其他棧的空位上)，用(i,z)表示，箱i和棧z滿足i∈C、z∈[max{0,bi-q},min{B,bi+q}]，bi為箱i所在的貝位，q為搜索算法的控制參數。

4)算法搜索時箱位交換的探索實施集合S(x)：算法迭代搜索時允許多對箱位同時交換可提高算法效率，但搜索鄰域中的多對箱位同時進行探索交換可能產生不可行解，因此定義無沖突的交換探索實施集合(H(x)的子集)，集合中的元素滿足下列條件：①如果(i1,j1)與(i2,j2)∈S(x)，那么i1≠j2并且i1≠i2；②如果(i1,z1)與(i2,z2)∈S(x)，那么i1≠i2并且z1≠z2；③如果(i，j)∈S(x)，那么交換后的適應度值不劣于當前解。

5)禁忌表的破禁：如果被禁忌探索解的適應度優于歷史最優值，那么將探索解的禁忌解除。

6)算法終止條件：禁忌搜索的迭代次數達到設定的迭代次數后，終止搜索，并輸出歷史最優方案。

7)禁忌搜索算法流程：定義x*最優箱位優選方案，f(x*)最優方案適應度評價值，m鄰域H(x)的探索交換。算法流程如圖4所示。

圖4 干擾恢復算法流程圖Fig.4 Recovery algorithm flowchart

4 干擾管理實驗分析

4.1 干擾管理實驗設計

以大連某集裝箱碼頭數據為基礎設計干擾管理實驗：干擾事件前的出口集裝箱位計劃利用文獻[9]提出的方法制定，堆場的提箱和翻箱任務根據不增加收箱作業等待的原則加入堆場龍門吊作業序列；客戶實際交箱時間利用正態分布N(tk,σ)模擬生成，tk為箱k的客戶預約交箱時間。實驗硬件CPU D3.19GHz/2G，算法基于C++開發實現。模型成本參數取1∶1∶0.6(壓箱量∶龍門吊大車移動∶箱位偏離)，改進禁忌搜索算法的控制參數Dis設置為20，q為1，禁忌表長度l設置為計劃總箱量，算法搜索迭代最大次數設置為50。通過同組5個隨機實驗取平均求得每組結果數據(明確說明的除外)。

4.2 改進禁忌搜索算法性能分析

提出的干擾管理模型屬于二次型，可用CPLEX求解。改進禁忌算法與CPLEX12.6的實驗對比結果見表1。CPLEX可求解小規模問題，并得到精確解，其時間消耗隨著問題規模的增大而呈指數型增長，CPLEX求解19箱問題的時間消耗在9 h以上，無法滿足現實要求。提出的改進禁忌搜索算法可得到小規模問題的較優近似解，精度誤差值不超過0.5，算法時耗遠小于CPLEX，求解120箱問題僅需3.26 s，能夠滿足實際要求。

4.3 干擾管理模型性能分析

提出的干擾管理模型與干擾事件發生后不調整方案按原計劃執行、重調度模型調整計劃的實驗對比結果見表2，實驗中采用的重調度模型是基于文獻[9]并利用干擾事件發生后的壓箱量與龍門吊大車移動距離總成本最小設計。干擾管理的相對效果實驗數據見表3。上述實驗結果分析可得出：客戶交箱次序的干擾使得不調整方案按原計劃執行的壓箱量和龍門吊作業成本都大幅度增加，因此干擾事件發生后需要有針對性地動態調整原方案；當問題規模較大時，干擾管理較重調度調整方案的方法效果更優，且規模越大優勢越明顯，如規模大于3×6×4 的算例有10%以上的平均優勢和50%的最大優勢，干擾管理較重調度方法的求解時間略低。由于干擾管理模型考慮了關聯成本因素，干擾恢復方案調整較小，減少了指令修改給龍門吊司機的情緒影響和誤操作幾率。

表1 改進禁忌搜索算法與CPLEX對比結果

注：*算法終止，未得出結果(9.3 h內存溢出)；堆場箱位空間的利用率約85%；對比數據為同組50個算例取平均值。

表2 原方案執行、重調度和干擾管理效果對比

注：表數據為10次實驗算例取均值，進、出口箱堆棧的比例約1∶3，堆場箱位空間的利用率約85%。

表3 干擾管理的相對效果表

注：總成本=龍門吊作業成本+壓箱成本，改進比率=(重調度總成本-干擾管理總成本)/重調度總成本。

干擾管理與重調度的對比改進分布如圖5所示，圖中數據點的相對改進=(重調度成本-干擾管理成本)/重調度成本，堆場箱位空間利用率約90%。對比分布圖顯示，隨著問題規模的增大干擾管理較重調度的改進越明顯，較優算例占總算例的比率也越大，問題規模達到15×6×4時，干擾管理得到較優解的算例比率占82%。不同堆場箱位空間利用率、問題規模和進/出口箱堆棧比例條件下的模型性能對比見表4，表中數據為10個實驗算例結果的平均值。總體而言，干擾管理模型的改進效果隨進/出口箱堆棧比例和問題規模的變大有增大的趨勢；當問題規模達到15×6×4時，干擾管理求解問題的精度較重調度有10%以上的改進。

圖5 不同算例的干擾管理相對改進分布圖Fig.5 Relative improvement ratio graph of distribution management in different cases

貝×棧×層(箱量)利用率進/出口箱堆棧比1∶5進/出口箱堆棧比1∶2進/出口箱堆棧比1∶1重調度干擾管理改進/%重調度干擾管理改進/%重調度干擾管理改進/%6×6×410×6×415×6×490%27.3*30.0-9.927.624.99.827.922.419.780%20.020.5-2.524.120.116.630.127.68.370%18.917.57.417.516.55.728.42222.560%13.314.6-9.823.720.513.516.312.523.390%47.546.13.060.853.711.785.771.117.080%46.443.66.047.637.221.963.949.322.970%41.238.66.355.153.82.455.446.915.460%29.932.2-7.733.332.33.041.636.213.090%112.7101.310.1117.395.518.6135.2100.425.880%102.789.812.6107.584.521.4109.684.522.970%73.765.211.580.769.114.4108.790.217.060%57.250.611.568.759.613.3106.192.812.5

注：*表中所列結果為模型的壓箱量與龍門吊大車移動距離的加權值和，其權重比為1∶1。

4.4 干擾恢復的啟動分析

F1(d)=A1{Dev≥d}/num1(d)

F2(n)=A2{ΔN≥n}/num2(n)

為干擾恢復啟動參數效果分析的評估指標。干擾管理效果隨干擾恢復啟動參數的變化趨勢如圖6所示(1 200個算例，問題規模6×6×4)。干擾管理啟動參數設置越小，實驗的算例作業成本增幅越小，如：Dev≤16的實驗算例作業成本的平均增幅1.01%，最大增幅也僅5.02%；ΔN≤6的實驗算例作業成本的平均增幅和最大增幅為0.99%和5.01%。碼頭實際中除了調度精度還需考慮實際運作效果，如果設置過小的干擾管理啟動參數勢必會造成作業計劃方案頻繁改變，不利于生產組織和碼頭作業，因此港方需考慮客戶交箱密度等綜合因素來設置實際的干擾恢復啟動參數。

圖6 干擾恢復啟動參數性能分析圖Fig.6 Illustration of disruption management performance with different trigger parameters

5 結論

1)出口集裝箱位的干擾管理有利于減少由于干擾事件造成的關聯隱性成本，實驗表明：干擾管理較重調度節約總作業成本10%以上；

2)基于局部加速的改進禁忌搜索算法通過控制探索鄰域優化了算法搜索方向，并縮小了搜索空間，使其在可接受時間內能獲得集裝箱位優選干擾管理模型的滿意解；

3)設置較小的出口集裝箱位優選干擾恢復啟動閥值參數可以獲得較小的干擾作業總成本，但過小的干擾恢復啟動閾值不利于堆場實際的生產組織，碼頭需考慮具體實際來選擇適用的啟動參數。

[1]GAMBARDELLA L M, MASTROLILLI M, RIZZOLI A E, et al. An optimization methodology for intermodal terminal management[J]. Journal of intelligent manufacturing, 2001, 12(5/6): 521-534.

[2]ZHANG C, LIU J, WAN Y, et al. Storage space allocation in container terminals[J]. Transportation research part B: methodological, 2003, 37(10): 883-903.

[3]MOHAMMAD B, NIMASAFA E I, et al. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers & industrial engineering, 2009, 56(1): 44-52.

[4]康海貴, 劉艷, 周鵬飛. 基于混堆的集裝箱堆場動態箱位分配研究[J].水運工程, 2009 (8): 73-77.

KANG Haigui, LIU Yan, ZHOU Pengfei. Research on dynamic storage space allocation based on mixture storage[J]. Port & waterway engineering, 2009 (8): 73-77.

[5]陶經輝, 汪敏. 基于混堆模式的集裝箱堆場區段分配[J]. 系統工程理論與實踐, 2009 (8): 185-192.

TAO Jinghui, WANG Min. Assign problem of container yard section based on mixed storage model[J]. Systems engineering-theory & practice, 2009 (8): 185-192.

[6]楊曼. 集裝箱碼頭堆場資源優化配置與調度研究[D]. 大連: 大連海事大學, 2011:1-72.

YANG Man. Research on optimizing allocation and deployment of resources of container terminal[D]. Daian: Dalian Maritime University, 2011: 1-72.

[7]郝聚民,紀卓尚,林焰. 混合順序作業堆場 BAY 優化模型[J].大連理工大學學報,2000 ,40(1) :102-105.

HAO Jumin, JI Zhuoshang, LIN Yan. Study of optimization of a BAY of stacking[J]. Journal of Dalian University of Technology, 2000, 40(1) : 102-105.

[8]鄭紅星, 杜亮, 董鍵. 混堆模式下集裝箱堆場箱位指派優化模型[J]. 交通運輸系統工程與信息, 2012, 12(1): 153-159.

ZHENG Hongxin, DU Liang, HUANG Jian. Optimization model on container slot allocation in container yard with mixed storage mode[J]. Journal of transportation systems engineering and information technology, 2012, 12(1): 153-159.

[9]周鵬飛, 方波. 動態環境下集裝箱碼頭堆場出口箱箱位分配建模與算法研究[J]. 控制與決策, 2011, 26(10): 1571-1576.

ZHOU Pengfei, FANG Bo. Modeling and algorithm research on export container slots allocation under dynamic environments [J]. Control and decision, 2011, 26(10): 1571-1576.

[10]CLAUSEN J, LARSEN J, LARSEN A et al. Disruption management-operations research between planning and execution[J]. OR/MS today, 2001,28(5):40-43.

[11]YU G, QI X. Disruption management: framework, models and applications[M]. [S.L.]:World Scientific, 2004.

[12]QI X, BARD J F, YU G. Disruption management for machine scheduling: the case of SPT schedules[J]. International journal of production economics, 2006, 103(1): 166-184.

[13]曾慶成, 胡祥培, 楊忠振. 集裝箱碼頭泊位分配-裝卸橋調度干擾管理模型[J]. 系統工程理論與實踐, 2010 (11): 2026-2035.

ZENG Qingcheng, HU Xiangpei, YANG Zhongzhen. Model for disruption management of berth allocation & quay crane scheduling in container terminals[J]. Systems engineering-theory & practice, 2010 (11): 2026-2035.

[14]楊春霞, 王諾. 集裝箱碼頭泊位分配干擾管理決策方法研究[J].運籌與管理, 2011 (4): 90-95.

YANG Chunxia, WANG Nuo. Decision-mnaking method management in for berth allocation disruption container terminal[J]. Operations research and management science, 2011 (4): 90-95.

[15]林慶福, 胡志華, 陶莎. 集裝箱碼頭泊位-岸橋集成分派干擾管理的分層調整策略[J]. 重慶交通大學學報:自然科學版, 2014, 33(3): 133-139.

LIN Qingfu, HU Zhihua, TAO Sha. Multi-level adjustment strategy for disruption management of berth-crane allocation problem at container terminals[J]. Journal of Chongqing Jiaotong University:natural science, 2014, 33(3): 133-139.

本文引用格式：

周鵬飛, 趙金秋, 尚爾進. 混堆集裝箱堆場的出口箱位優選干擾管理[J]. 哈爾濱工程大學學報， 2017， 38(6)： 866-873，938.

ZHOU Pengfei， ZHAO Jinqiu， SHANG Erjin. Disruption management model and algorithm for export container slots optimization in container yards of mixture storage mode[J]. Journal of Harbin Engineering University， 2017， 38(6)： 866-873，938.

Disruption management model and algorithm for export container slots optimization in container yards of mixture storage mode

ZHOU Pengfei， ZHAO Jinqiu， SHANG Erjin

(School of Hydraulic Engineering, Dalian University of Technology, Dalian 116024, China)

In view of the characteristic that handling operations are likely subjected to interference with each other in mixture-container-storage-moded yards, an operation interference measuring method was proposed based on export containers arriving sequences. A disruption management model for export container slots allocation was built to take the interference related operation cost into account, where the weighted combinatorial objective of reshuffles and gantry-crane traveling distance aims to save the total cost of gantry-crane handling and reshuffling, the slots-offset objective to reduce the related cost. Using the local feature of recovery model solution, an improved tabu-searching algorithm was developed to accelerate its convergence, in which the local searching spaces are refined by controlling the searching domain and directions. Experiments show the disruption management gains 10% improvement compared to the rescheduling.

container transportation; container yard slots optimization; disruption management; tabu-search algorithm; mixture storage mode; container storage yard; dynamic environment

2016-02-24. 網絡出版日期：2016-06-02.

國家自然科學基金項目(71101014)；教育部留學回國人員科研啟動基金項目(教外司留[2015]1098)；中央高校基本科研業務費專項資金項目(DUT16QY47).

周鵬飛(1977-), 男, 副教授.

周鵬飛，E-mail: pfzhou@dlut.edu.cn.

10.11990/jheu.201602026

http://www.cnki.net/kcms/detail/23.1390.u.20170602.1101.002.html

U6

A

1006-7043(2017)06-0866-09