上海國際港務(集團)股份有限公司尚東集裝箱碼頭分公司

1 引言

自動化集裝箱碼頭(ACT，Automated Container Terminal)在降低碼頭人力成本、提高港口通過能力、降低裝卸作業(yè)能耗、提升港口品牌形象等方面發(fā)揮著重要的作用，是未來港口發(fā)展的必然趨勢。集裝箱碼頭處理的集裝箱絕大多數為普通箱，冷藏箱的處理數量在碼頭總吞吐量中所占比例較小，但是基于冷藏箱的特殊作業(yè)要求，冷藏箱箱區(qū)的作業(yè)管理對碼頭作業(yè)效率及箱區(qū)作業(yè)人員工作效率都有重要的影響。

冷藏集裝箱是符合國際標準、具有隔熱性能、能保持一定低溫要求，適用于各類食品和特殊貨物冷藏貯運而進行特殊設計的集裝箱[1]。隨著世界食品工業(yè)的發(fā)展和食品冷藏運輸的需要，近年來公路、鐵路、海上食品冷藏運輸已越來越多地采用各類冷藏集裝箱。目前，國際上集裝箱尺寸和性能都已標準化，基本分為3類：20×8×8，20×8×8.6，40×8×8.6(長×寬×高，ft)，使用溫度范圍為-30(用于運送凍結食品)～+12℃(用于運送香蕉等果蔬)，更通用的范圍是-30～20℃。

冷藏箱區(qū)是集裝箱堆場中用來暫時堆存進出口冷藏箱的區(qū)域，自動化集裝箱碼頭冷藏箱區(qū)的布置不同于傳統(tǒng)集裝箱碼頭的平行布置，而是垂直于碼頭岸線。由于冷藏箱內的貨物需要保持一定的溫度，如冷藏集裝箱運送凍結貨時通常使用溫度應不高于-18℃；箱內的貨物是水果蔬菜時，其箱內溫度應保持在12℃左右；冷凍貨長距離運輸時，箱內設定溫度與設定溫度差不能超過3℃；若運送冷卻貨，其溫度誤差應不大于0.5℃，最好不大于0.25℃。因此，為保證箱區(qū)內冷藏箱的箱內溫度，箱區(qū)內設有專門的電源支架，支架上設有電源插頭，當冷藏箱進場后應該及時插電，而在冷藏箱離場前又應該及時拔掉電源。

本文闡述了冷藏箱箱區(qū)的結構與插拔電操作的約束和目標；基于傳統(tǒng)帶有時間窗的TSP問題，考慮箱區(qū)中冷藏箱的插拔電時間窗約束，以操作員行走路徑最小為目標建立整數規(guī)劃模型，以確定待插拔電的冷藏箱的插拔電作業(yè)順序；對模型求解，并將求解結果同當前碼頭冷藏箱區(qū)插拔電策略作比較。

2 問題描述

上海洋山深水港四期全自動化集裝箱碼頭共有6塊冷藏箱箱區(qū)，分布在14#與15#、30#與31#、46#與47#箱區(qū)，每個箱區(qū)靠近陸側垂直于碼頭岸線布置(如圖1所示)。相鄰的2個箱區(qū)之間設有AGV(Automated Guided Vehicle，自動導引車)車道，插拔電操作人員只允許在通道和支架上行走，如果需要跨箱區(qū)作業(yè)，只能通過箱區(qū)間通道進入另一箱區(qū)。冷藏箱區(qū)支架結構圖見圖2。一個箱區(qū)共有8個大貝和2個小貝，每個貝位可以堆放7排，除第一排只能在第三、四層碼放2層冷藏箱外，其余每排可以放4層冷藏箱。

圖1 冷藏箱區(qū)平面圖

圖2 冷藏箱區(qū)支架結構圖

冷藏箱在運輸途中或是堆場中都有嚴格的溫度要求，提前拔電或延后插電都有可能使箱內溫度不能達到要求，造成貨物腐敗。因此當冷藏箱進場后應該及時插電，一般要求進場后10 min內插上電源；在冷藏箱離場前應該及時拔掉電源，一般要求出場前30 min內拔掉電源。這樣每個需要進出場的冷藏箱的插拔電都有一個具體的時間窗，工作人員應該嚴格按照該時間窗前往各冷藏箱位進行插拔電。假設箱區(qū)中有一個冷藏箱i需要插或拔電，要求的時間窗為[ei，li]，那么操作員能為i插拔電的時間不能早于ei，如果早于ei，則必須等待，但也不能晚于li。另一方面，操作員接到的插拔電任務通常是多個冷藏箱，這些冷藏箱又分布在箱區(qū)的不同地方，箱區(qū)的長度超過100 m，箱區(qū)間通道之間的距離超過50 m，如果操作員沒能在箱區(qū)里選擇較好的插拔電順序，為了完成所有插拔電任務，則需要行走很長距離，造成人員疲憊。

如何在滿足各待插拔電的時間窗約束的情況下，使操作員在順利完成所有插拔電任務后所行走的距離最短，是本文研究的主要問題。從根本上來說，該問題就是一個帶有時間窗的TSP問題，將分布在不同場箱位所有的待插拔電冷藏箱抽象為TSP問題中的各個城市節(jié)點，任意兩場箱位之間的距離抽象為城市之間的距離，各個箱子插拔電時間窗抽象為各個城市的服務時間窗[2-3]。

在計算距離時，因為箱子在排位中隨機分布，為了計算方便，對扶梯的位置作折中處理，假設扶梯位于支架的正中間，可以從最底層垂直上到最高層，如圖2(b)所示。任意一個冷藏箱的場箱位可以表示為(z,b,r,t)，其中，z表示箱區(qū)，b表示貝位，r表示排位，t表示層位。假設冷藏箱i的場箱位為(zi,bi,ri,ti)，冷藏箱j的場箱位為(zj,bj,rj,tj)。dij表示在箱區(qū)1和2內任意2個冷藏箱i和j之間的操作員行走距離；箱區(qū)之間的外通道距離zij=50 m，當跨箱區(qū)作業(yè)時有效；stsi和stsj表示i和j到扶梯的距離，當需要上下扶梯時有效，即當在第一排作業(yè)時無效；ssi和ssj表示i和j上(下)扶梯的距離，當需要上下扶梯時有效；sai和saj表示從某一貝位第一層某位置(扶梯處或第一層其他排位處)到通道的距離，都有效；sbbij表示兩貝位通道之間的通道距離，跨箱區(qū)時無效；sbli和sblj表示從i和j所在貝位到Bay1的通道距離，僅在跨箱區(qū)時有效；則dij=stsi+stsj+ssi+ssj+stai+staj+sbbij+sbli+sblj+zij，但是求和時各單項的有效性視具體情況而定[4]。

3 數學模型

3.1 參數設定

3.2 假設條件

為了方便問題的研究，作如下假設：

(1)假設人始終勻速行走，且步速是1 m/s，這樣tij與dij在數值上是相等的。

(2)在計算冷藏箱之間的距離時，假設扶梯位于支架的正中間。

(3)現實情況下，由于冷藏箱內貨物的不同，所要求的溫度不同的，對溫差變化的敏感度也是不同的，進而插拔電的提前時間是不同的。這里對該問題進行了簡化，只考慮所有冷藏箱的進出場屬性，即假設所有進場箱或出場箱的允許提前插拔電時間是相同的，所有的冷藏箱進場后10 min內應該插上電源，而出場前30 min內應該拔掉電源。

(4)假設操作員只在相鄰的2個箱區(qū)作業(yè)，不涉及更多冷藏箱區(qū)。

3.3 決策變量

(1)xij。如果操作員行走路線經過弧，則xij=1，否則為0。

(2)ati。操作員到達冷藏箱i(支架)的時間。

(3)wti。箱子i插拔電的等待時間，wti≥0，則i的插拔電開始時間是ati+wti，箱子i插拔電結束時間為ati+wti+sti。

(4)ui。虛擬變量，取值為正整數，表示節(jié)點i的遍歷順序，如果冷藏箱i是第t個操作的冷藏箱，則ui=t。

完整模型如下：

(1)

(2)

(3)

ui-uj+nxij≤n-1，?i，j∈V1}，i≠j

(4)

ati≤li，?i∈V

(5)

eti≤ati+wti≤li，?i∈V

(6)

ati+wti+sti+tij+(1-xij)M≤atj，

?i，j∈V，i≠j

(7)

at1=wt1=st1=0

(8)

wti=max{0，eti-ati}，?i∈V

(9)

ati，wti，sti≥0，?i∈V

(10)

xij=0，1，?i，j∈V，i≠j

(11)

ui∈Z，?i∈V

(12)

式(1)為目標函數，最小化行走距離；式(2)、(3)為訪問唯一性約束，1個節(jié)點只進入和離開1次；式(4)為次回路消除約束；式(5)表示到達時間不能晚于插拔電要求的最遲時間；式(6)表示開始插拔電時間務必在時間窗內；式(7)為前驅與后繼節(jié)點之間的時間關系；式(8)為起始點處的時間參數；式(9)表示在時間窗之前到達就會有等待時間；式(10)、(11)、(12)為參數和決策變量的基本取值范圍[8-9]。

4 模型求解與算例分析

現實情況下，某一次插拔電任務操作員需要插拔電的冷藏箱數量通常不多，該模型的計算復雜度不大，如果采用啟發(fā)式算法求解，則存在計算結果不穩(wěn)定的現象，并且也不能確保得到的是最優(yōu)解。因此本文對該模型的求解采用精確算法，即用MATLAB軟件Yalmip工具箱調用ILOG Cplex求解器求解。

現假設相鄰兩箱區(qū)共有10個插拔電任務，這10個冷藏箱的箱位與時間窗見表1。其中，(1,1,1,1)表示該冷藏箱位于第1箱區(qū)、第1貝、第1排、第1層，并設定其為任一任務的出發(fā)點，非任務點，其他箱位含義同理；時間窗為該冷藏箱節(jié)點的最早與最晚插拔電時間，如(1,1,3,1)的時間窗為(100,700)，表示該冷藏箱的插拔電要求的最早開始時間是第100 s，最晚開始時間是第700 s。表2給出了這11個節(jié)點之間的距離，用MATLAB求解得到的結果如表3中“優(yōu)化模型”一欄所示。

表1 待插拔電冷藏箱箱位與時間窗

表2 各任務點之間的距離

碼頭目前擬采用的策略是按照時間最緊迫或下一距離最近法。按照時間最緊迫策略，則在完成當前冷藏箱的插拔電作業(yè)之后，應該選擇帶有與當前時間最接近的最晚插拔電時間的冷藏箱作為下一作業(yè)箱；按照下一距離最短策略，則在完成當前冷藏箱的插拔電作業(yè)之后，應該選擇與當前所在位置最接近的冷藏箱作為下一待插拔電的冷藏箱。用這兩種策略安排出的行走路徑計劃所得到的結果如表3中“時間最緊迫”與“下一距離最短”兩欄所示。

表3 幾種插拔電順序策略的比較

由表3可以看出，使用不同策略得到的結果是不同的。若使用第一種策略，時間窗可以很好的滿足，但是往往會由于過分追求時間窗而導致作業(yè)任務路徑不簡潔，部分路段重復行走次數增多，最終導致總行走距離延長，其路徑雖滿足時間窗約束，但是總行走距離卻是3種策略中最長的。若使用第二種策略，作業(yè)路徑簡潔明了，減少多余回路，但會出現錯過時間窗的情況。而使用優(yōu)化模型與精確算法求解所得到的結果最優(yōu)，在滿足時間窗約束的前提下，可得到一個最短路徑。

5 結語

實際案例分析表明，“時間最緊迫”與“下一距離最短”這2種策略不能滿足碼頭實際操作的需要，而采用采用建立優(yōu)化模型與選擇精確求解算法，可解決考慮時間窗約束的自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑優(yōu)化問題，具有較高的實用性與適用性，能為碼頭冷藏箱區(qū)插拔電作業(yè)提供很大便利。

本文采用的模型只考慮了基本的時間窗約束，在實際情況下，可能會遇到某個箱子的時間窗無法滿足的情況，這時模型就求解不出可行解。因此，進一步研究可以考慮軟時間窗約束，對不滿足時間窗的操作進行懲罰，當該懲罰最小化時，即求出最優(yōu)解。另外，本文將進出口箱子的插拔電提前時間作統(tǒng)一處理，后期研究需要考慮不同貨物對該時間的影響。