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

1 引言

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

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

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

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

2 問題描述

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

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

圖2 冷藏箱區(qū)支架結(jié)構(gòu)圖

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

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

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

3 數(shù)學(xué)模型

3.1 參數(shù)設(shè)定

3.2 假設(shè)條件

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

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

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

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

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

3.3 決策變量

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

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

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

(4)ui。虛擬變量，取值為正整數(shù)，表示節(jié)點(diǎn)i的遍歷順序，如果冷藏箱i是第t個(gè)操作的冷藏箱，則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)為目標(biāo)函數(shù)，最小化行走距離；式(2)、(3)為訪問唯一性約束，1個(gè)節(jié)點(diǎn)只進(jìn)入和離開1次；式(4)為次回路消除約束；式(5)表示到達(dá)時(shí)間不能晚于插拔電要求的最遲時(shí)間；式(6)表示開始插拔電時(shí)間務(wù)必在時(shí)間窗內(nèi)；式(7)為前驅(qū)與后繼節(jié)點(diǎn)之間的時(shí)間關(guān)系；式(8)為起始點(diǎn)處的時(shí)間參數(shù)；式(9)表示在時(shí)間窗之前到達(dá)就會(huì)有等待時(shí)間；式(10)、(11)、(12)為參數(shù)和決策變量的基本取值范圍[8-9]。

4 模型求解與算例分析

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

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

表1 待插拔電冷藏箱箱位與時(shí)間窗

表2 各任務(wù)點(diǎn)之間的距離

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

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

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

5 結(jié)語

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

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