梁承姬,黃 帥
上海海事大學(xué) 物流科學(xué)與工程研究院,上海201306
隨著經(jīng)濟全球化以及信息技術(shù)的不斷發(fā)展,特別是中國持續(xù)推進對外開放以及“一帶一路”倡議使得貨物貿(mào)易需求迅速提升,中國港口得到了快速發(fā)展。但伴隨著激烈的市場競爭,高效率運作對于港口的作用越來越突顯。場橋作為港口的昂貴資源,對堆場物流系統(tǒng)甚至是整個港口物流系統(tǒng)都起著推動作用[1]。高效的場橋調(diào)度計劃能夠使得場橋與其他機械設(shè)備資源更好地協(xié)調(diào)工作,在滿足實際約束的情況下盡可能地縮短船舶的在港裝卸時間,加快貨物的運轉(zhuǎn)周期。
在前期研究中,為了簡化問題難度,大多數(shù)學(xué)者針對單個場橋進行調(diào)度優(yōu)化研究。Ng W C等[2]考慮集裝箱任務(wù)準備時間不同情況下的場橋調(diào)度問題,通過分支界定法對模型求解。Huang等[3]針對單場橋調(diào)度問題提出了兩種改進最小成本的啟發(fā)式算法。韓曉龍等[4]分別運用啟發(fā)式算法和模擬退火算法對單箱區(qū)單場橋調(diào)度問題進行研究,通過結(jié)果對比分析得出模擬退火算法在運算時間和路徑優(yōu)化方面都優(yōu)于啟發(fā)式算法。
隨著航運業(yè)的發(fā)展以及信息化技術(shù)水平的提高,專家學(xué)者開始研究多場橋并行調(diào)度問題,考慮了場橋同時作業(yè)的安全距離等限制條件。Li Wenkai 等[5]利用滾動時域算法研究單個箱區(qū)內(nèi)多場橋調(diào)度問題。Wu Yong等[6]則在文獻[5]的基礎(chǔ)上,將提箱延遲任務(wù)數(shù)考慮到目標函數(shù)中并用啟發(fā)式算法進行求解。劉志雄等[7]設(shè)計了一種三維坐標表示方法來確定場橋移動過程中的位置,從而利用混合演化算法求解得到最優(yōu)的場橋轉(zhuǎn)場次數(shù)及作業(yè)完工時間。梁承姬等[8]研究單個箱區(qū)中多臺場橋在干擾情況下基于混堆模式的存取箱同時進行的調(diào)度問題。邵乾虔等[9]將進口箱場橋作業(yè)調(diào)度問題分解成場橋路徑優(yōu)化問題和貝內(nèi)翻箱作業(yè)優(yōu)化問題,建立動態(tài)優(yōu)化模型。Speer等[10]通過仿真模型詳細討論了場橋移動干涉等約束,并提出用分支定界法求解場橋的實時調(diào)度問題。初良勇等[11]研究在外集卡預(yù)約模式下的多箱區(qū)多場橋調(diào)度,利用模擬退火算法進行求解,并與實際人工操作對比,從而驗證算法的有效性。曹朋亮等[12]考慮了集卡作業(yè)面模式下的場橋與集卡聯(lián)合調(diào)度,利用改進遺傳算法確定場橋作業(yè)量,進而得到優(yōu)化后的場橋最短行駛路徑。初良勇等[13]在文獻[11]的基礎(chǔ)上設(shè)計了基于遺傳算法的模型,并與文獻[11]的結(jié)果對比,驗證該方法可以大幅度降低成本。
綜上,現(xiàn)有關(guān)于場橋調(diào)度的文獻大部分都是以場橋路徑最短或者場橋完工時間最小化為目標。但隨著港口信息化水平的不斷提高,集裝箱港口開始采用外集卡預(yù)約模式,這也意味著可以提前確定集卡運輸集裝箱任務(wù)的到達時間和總?cè)蝿?wù)量,集卡與場橋之間的匹配度可以進一步優(yōu)化,從而提高場橋的作業(yè)效率。但是當前很少有文獻考慮到了這一因素。因此本文針對多箱區(qū)多場橋調(diào)度問題,考慮到場橋在箱區(qū)內(nèi)與箱區(qū)間作業(yè)的干涉約束,根據(jù)集卡到達時間(即準備時間),提出了計劃時間段和基于集裝箱任務(wù)組的時間窗,并采用遺傳算法求解以場橋移動成本及延誤成本最小化為目標的模型。
后方堆場作為存儲或者中轉(zhuǎn)集裝箱的場地,在整個碼頭中處于核心地位。而場橋是堆場中進行集裝箱堆取作業(yè)的機械設(shè)備,其工作效率的高低直接影響到堆場乃至整個港口的服務(wù)水平。由于堆場內(nèi)集裝箱裝卸任務(wù)工作量分布不均勻,場橋需要在箱區(qū)間頻繁進行移動。而場橋在箱區(qū)間的移動和轉(zhuǎn)彎會占用大量的時間和空間,容易導(dǎo)致堆場通道堵塞,進而增加場橋與集裝箱任務(wù)組之間的相互等待時間。
因此本文提出了計劃時間段和時間窗的概念,在考慮場橋移動成本最小的基礎(chǔ)上最小化兩者相互等待成本,同時考慮到多箱區(qū)多場橋作業(yè)過程中不可跨越和保持安全距離等現(xiàn)實約束。根據(jù)上海某集裝箱港口的實際數(shù)據(jù),研究在某一個計劃時間域內(nèi)(本文選取4 h)按照各個集裝箱任務(wù)組的準備時間劃分成四個計劃時間段:0~60,60~120,120~180,180~240,各個任務(wù)組要在其對應(yīng)的計劃時間段內(nèi)分開完成調(diào)度。在每個計劃時間段再按各個集裝箱任務(wù)組的準備時間設(shè)計一個時間范圍(即時間窗),若場橋在這個時間窗外作業(yè)則給予一定的單位時間成本處罰。如圖1所示,集裝箱任務(wù)組最早能被服務(wù)的時刻即為其準備時間,最晚被服務(wù)時刻是任務(wù)組等待時間上限。但集裝箱任務(wù)組實際開始操作時間則為任務(wù)組最早能被服務(wù)時刻與場橋到達時刻兩者之間的較大值。
圖1 集裝箱任務(wù)組時間窗示意圖
(1)本文研究的堆場區(qū)域如圖2所示。
(2)堆場上場橋操作的集裝箱都是20 英尺標準集裝箱,且按照不同類型不同目的地將同一箱區(qū)同一貝位的集裝箱作為一個任務(wù)組來處理。
(3)所有場橋的工作參數(shù)都是相同的,包括移動速度,進行轉(zhuǎn)場作業(yè)時的轉(zhuǎn)彎時間,操作集裝箱的時間都是固定值。
(4)不考慮由于設(shè)備新舊程度不同而可能導(dǎo)致的能耗不同,每臺場橋的移動成本相同。
圖2 集裝箱港口堆場示意圖
(5)規(guī)定每臺場橋初始時刻位于要操作的第一個集裝箱任務(wù)組貝位,結(jié)束所有分配任務(wù)后位于最后一個集裝箱任務(wù)組貝位。
(6)場橋操作完集裝箱任務(wù)組i 后隨即按最短路徑移動到下一個任務(wù)組j 所處的貝位。
(7)設(shè)定場橋在水平方向箱區(qū)間的移動距離按貝位差進行計算,在垂直方向箱區(qū)間的移動距離按箱區(qū)通道和箱區(qū)寬度計算。
(8)集裝箱任務(wù)組的準備時間根據(jù)集卡預(yù)約時間轉(zhuǎn)變而來,假定其在堆場所處位置都是已知且固定不變的。
(9)本文不考慮每個計劃時間段內(nèi)有未完成的任務(wù)情況,即在每個時間段結(jié)束時場橋必須完成當前時間段內(nèi)的所有任務(wù)。
(10)每個計劃時間段被分配的集裝箱數(shù)量不能超過任一場橋在該時間段的總工作能力(即每小時場橋最多可處理20個集裝箱任務(wù)的裝卸)。
(1)參數(shù)
c,c′:場橋,c,c′∈C;
b:箱區(qū),b ∈B;
k:計劃時間段,k ∈K ;
i,j,o:集裝箱任務(wù)組,i,j,o ∈M ;
pi:集裝箱任務(wù)組i 包含的集裝箱數(shù);
TGk:k 計劃時間段內(nèi)集裝箱任務(wù)組總數(shù);
Bp:垂直方向中間通道寬度;
Bw:單個箱區(qū)的寬度;
l:單個貝位的長度;
u:單個箱區(qū)的貝位數(shù);
mi:集裝箱任務(wù)組i 所對應(yīng)的貝位;
ni:集裝箱任務(wù)組i 所對應(yīng)的箱區(qū);
Tturn:場橋轉(zhuǎn)場作業(yè)時2次轉(zhuǎn)彎90°的總時間;
q:場橋操作單個集裝箱的時間;
v:場橋移動速度;
W1:場橋移動成本;
W2:場橋到達時間早于集裝箱任務(wù)組準備時間的單位時間懲罰金額;
W3:超過集裝箱任務(wù)組等待時間上限的單位時間懲罰金額;
ETi:集裝箱任務(wù)組i 的準備時間(即集裝箱任務(wù)組i 最早被服務(wù)時刻);
LTi:集裝箱任務(wù)組i 最晚被服務(wù)的時間上限;
Sic:場橋c 操作集裝箱任務(wù)組i 的開始時刻;
OTi:集裝箱任務(wù)組i 的操作時間;
FTi:集裝箱任務(wù)組i 的操作完成時刻;
MTij:場橋從集裝箱任務(wù)組i 移動到任務(wù)組j 的時間;
dij:場橋從集裝箱任務(wù)組i 移動到任務(wù)組j 的距離;
(2)集合
C:堆場箱區(qū)內(nèi)可工作的場橋集合;
B:堆場箱區(qū)集合;
K :計劃域內(nèi)計劃時間段集合;
M :集裝箱任務(wù)組集合;
Mk:k 計劃時間段內(nèi)集裝箱任務(wù)組集合;
Mkb:k 計劃時間段內(nèi)b 箱區(qū)的集裝箱任務(wù)組集合;
Nc:場橋c 操作的集裝箱任務(wù)組集合;
(3)決策變量
Vcibk:0-1,若在b 箱區(qū)k 計劃時間段內(nèi)場橋c 操作集裝箱任務(wù)組i 則為1,否則為0;
Uijbk:0-1,判斷在b 箱區(qū)k 計劃時間段內(nèi)的集裝箱任務(wù)組i,j 是否同時被處理,當FTj≥FTi-OTi且FTi≥FTj-OTi時則為0,否則為1;
xijc:0-1,若場橋c 操作集裝箱任務(wù)組i,j 且操作順序為i →j 時則為1,否則為0。
ωic:0-1,若場橋c 操作集裝箱任務(wù)組i 時則為1,否則為0。
其中:
其中:
式(1)借鑒了文獻[11]的目標函數(shù),其中第1部分表示最小化場橋的移動成本,第2 部分在第1 部分基礎(chǔ)上最小化場橋與集裝箱任務(wù)組之間的相互等待成本。
本文將集裝箱任務(wù)組按計劃時間段分批次分批量進行作業(yè)從而減少場橋在箱區(qū)間頻繁進行轉(zhuǎn)場作業(yè):約束條件(2)表示在任一時間段內(nèi)場橋處理的集裝箱任務(wù)組數(shù);約束條件(3)保證在任一計劃時間段內(nèi)任意一個集裝箱任務(wù)組只能分配給一臺場橋進行作業(yè);約束條件(4)保證任一計劃時間段內(nèi)一臺場橋只能同時操作一個集裝箱任務(wù)組;約束條件(5)保證在任意時刻不同場橋間須保持一定的安全作業(yè)距離;約束條件(6)保證任一計劃時間段內(nèi)每個箱區(qū)至多有2 臺場橋同時工作。在每個計劃時間段內(nèi)再采用時間窗對場橋作業(yè)進行約束:約束條件(7)和(8)表示任一場橋進行作業(yè)時至多有一個緊前作業(yè)和緊后作業(yè);約束條件(9)表示任一場橋進行作業(yè)時至少有一個緊前作業(yè)或緊后作業(yè);約束條件(10)定義了相關(guān)變量之間的關(guān)系;約束條件(11)定義了同一場橋處理前后兩個集裝箱任務(wù)組的作業(yè)時間關(guān)系;約束條件(12)保證任一集裝箱任務(wù)組等待被操作的時間不能超過等待上限。
由于場橋全局調(diào)度問題是一個NP 難的問題,在以往的研究中通常采用智能優(yōu)化算法求解。而針對本文模型特點,遺傳算法不僅能將約束條件嵌入算法結(jié)構(gòu)中,解決其高復(fù)雜度性,而且能提高在解的空間中的搜索次數(shù),增加搜索到最優(yōu)解的概率,縮短優(yōu)化時間。并且根據(jù)參考文獻[13]有專家學(xué)者采用遺傳算法進行求解并獲得了較好的結(jié)果。因此本文考慮使用遺傳算法來解決這個問題。
首先對集裝箱任務(wù)組和場橋進行編號,根據(jù)不同計劃時間段劃分集裝箱任務(wù)組,然后將不同時間段的任務(wù)組分配給相應(yīng)的場橋并按照一定的順序進行場橋調(diào)度作業(yè)。如圖3 所示,本文采用二維整數(shù)形式編碼,分別用來表示集裝箱任務(wù)組以及場橋的作業(yè)順序。其中染色體中非0的基因值表示集裝箱任務(wù)組和場橋的編號,而染色體中的間隔符“0”則將染色體分為4 個部分,從左往右分別表示第1~4 個計劃時間段的場橋調(diào)度計劃。例如第一段染色體表示在第一個計劃時間段內(nèi)場橋1 做任務(wù)組9,場橋2 做任務(wù)組3,場橋3 做任務(wù)組16和5,場橋4 做任務(wù)組13,其中場橋3 先做任務(wù)組16,再做任務(wù)組5。
圖3 染色體編碼示意圖
初始種群的產(chǎn)生和選擇對算法的實現(xiàn)有很大的影響。通常會采取兩種方式生成初始種群:(1)啟發(fā)式方法;(2)隨機生成法。前者雖然能生成更高質(zhì)量的初始個體,但是容易陷入局部最優(yōu)解,而后者則有利于初始種群的多樣性。因此本文采用隨機生成法在滿足基本約束條件的情況下生成初始種群,并且規(guī)定可行解只是初始種群的一部分,具體規(guī)則如下:
(1)對于染色體中集裝箱任務(wù)組的優(yōu)先級部分,首先根據(jù)每個計劃時間段劃分集裝箱任務(wù)組數(shù)確定間隔符號“0”的基因位,然后在每個時間段內(nèi)隨機排列被分配的集裝箱任務(wù)組編號,并且要滿足約束條件(3)。
(2)場橋部分則按照各個時間段內(nèi)的集裝箱任務(wù)組隨機產(chǎn)生可工作的場橋編號,但要保證在該計劃時間段內(nèi)分配給場橋的任務(wù)數(shù)不能超過場橋的工作能力。
遺傳算法中適應(yīng)度函數(shù)值來評價一個個體(解)的好壞,其直接關(guān)系到最終解的質(zhì)量和搜索效率。本文選取目標函數(shù)的值作為適應(yīng)度值,在計算適應(yīng)度值時,需要判斷是否滿足模型中的約束條件:(1)通過設(shè)定時間步長,每隔一定的時間間隔確定堆場內(nèi)場橋所處的貝位,再計算場橋之間是否處于同一箱區(qū)以及是否保持一定的安全距離;(2)利用拉格朗日松弛法引入一個很大的正數(shù)作為懲罰項來限制每個計劃時間段結(jié)束時場橋必須完成該時間段內(nèi)的所有任務(wù)組,而對于場橋提前到達或者延誤的情況,則分別設(shè)置相應(yīng)的單位時間懲罰金額。
4.4.1 選擇操作
本文采用輪盤賭法進行選擇運算,其主要思想是根據(jù)每個染色體的適值比例確定該個體的選擇概率或者生存概率[14],將父代染色體和子代染色體按適應(yīng)度值大小進行排序,從中選擇適應(yīng)度好的個體組成新的種群。
4.4.2 交叉操作
本文采用雙切點交叉法,具體步驟如圖4所示。其中未交換的染色體片段按映射關(guān)系恢復(fù)合法性時只針對集裝箱任務(wù)組,而場橋部分不變更。
4.4.3 變異操作
圖4 交叉操作示意圖
變異運算是產(chǎn)生新個體的輔助方法,它有助于提高局部搜素能力,同時保持種群的多樣性,防止發(fā)生早熟現(xiàn)象。本文采用逆轉(zhuǎn)變異法[15],即在染色體場橋部分中隨機選擇兩點,將其基因值進行對換,這也用于解決染色體中出現(xiàn)場橋之間相互跨越現(xiàn)象。如圖5所示,場橋3在去往任務(wù)組16作業(yè)的移動過程中會與場橋1前往任務(wù)組9的途中發(fā)生場橋跨越,此時若在保證在該計劃時間段內(nèi)完成所有任務(wù)組的前提下,將其換成其他可工作的場橋4,則可把上面的不可行解轉(zhuǎn)化成可行解,從而在一定程度上保持了種群的多樣性。但由于染色體中的間隔符“0”沒有實際意義,所以規(guī)定在變異操作中不能選擇“0”基因位進行交換。
圖5 變異操作示意圖
4.4.4 基因修復(fù)
在經(jīng)過交叉和變異操作以后,可能會產(chǎn)生一些不符合約束條件的染色體,因此需要進行基因修復(fù):
步驟1 在交叉后,若交換的染色體片段正好是“0”基因位,則意味著交叉無意義。因此需要重新生成新的切點。同理在變異操作中若交換的兩基因位值相等,也需要重新隨機生成交換點。若不存在這種情況則轉(zhuǎn)到步驟2。
步驟2 在交叉變異后,需要判斷相鄰兩個“0”基因位之間的染色體片段中是否滿足假設(shè)條件(10)。若不滿足,則需要將超出場橋工作能力的集裝箱任務(wù)分配給這個時間段相對任務(wù)最少的場橋。
通過以上操作產(chǎn)生的新個體將會替代原先種群中適應(yīng)度較差的染色體,這個迭代過程持續(xù)到最大迭代次數(shù)時停止。
本文采用上海某集裝箱港口的實際運營數(shù)據(jù)進行研究,通過與實際作業(yè)情況以及其他算法的優(yōu)化結(jié)果進行對比進而驗證上述所提模型和算法的有效性和適用性。運行環(huán)境為Intel?CoreTMi5處理器、內(nèi)存8 GB、硬盤128 GB的個人計算機,使用Matlab2016a運行本文的遺傳算法來求解算例。
本文選取該港口堆場中某塊區(qū)域的6 個箱區(qū)進行研究,數(shù)據(jù)規(guī)模為:每個箱區(qū)由60 個貝位組成,每個貝位又由6 列組成。為了便于后續(xù)計算場橋在箱區(qū)間作業(yè)的移動距離,本文設(shè)定水平方向的中間過道為3個貝位距離,垂直方向的中間過道為2個貝位距離。在計劃時間4 小時內(nèi)處理200 個集裝箱任務(wù)數(shù)量,可用的場橋數(shù)量為4 臺,每臺場橋處理單個集裝箱的操作時間為3 min,假定集裝箱任務(wù)組要在其準備時間后的30 min內(nèi)被服務(wù)[13],場橋移動成本、場橋與任務(wù)組相互等待的懲罰金額等數(shù)據(jù)在算法主程序中給出,其他輸入數(shù)據(jù)見表1~6。
表1 箱區(qū)1任務(wù)量數(shù)據(jù)
表2 箱區(qū)2任務(wù)量數(shù)據(jù)
表3 箱區(qū)3任務(wù)量數(shù)據(jù)
表4 箱區(qū)4任務(wù)量數(shù)據(jù)
表5 箱區(qū)5任務(wù)量數(shù)據(jù)
表6 箱區(qū)6任務(wù)量數(shù)據(jù)
針對本文模型,在算法中設(shè)置了相應(yīng)的參數(shù):種群大小N=300,迭代次數(shù)G=500,交叉概率PC=0.85,變異概率PM=0.2。通過Matlab運行求解,得到遺傳算法的結(jié)果收斂圖,如圖6所示。由算法收斂圖中可以看到,大約迭代到130 代時得到最終的收斂結(jié)果,避免了前期陷入局部解。
圖6 GA收斂圖
根據(jù)本文模型和所設(shè)計的算法得到計劃時間域內(nèi)的作業(yè)任務(wù)分配以及場橋的作業(yè)順序。如圖7 是各個計劃時間段內(nèi)場橋調(diào)度甘特圖,可以看出該結(jié)果既滿足模型中分配給場橋的任務(wù)數(shù)不超過其工作能力的要求,也滿足每個集裝箱任務(wù)組在計劃時間段結(jié)束的約束。
為了更加清楚直觀地看到場橋的作業(yè)任務(wù)順序,如圖8~11所示為各個計劃時間段內(nèi)分配給各個場橋作業(yè)的集裝箱任務(wù)組及其開始時刻和結(jié)束時刻,圖中的數(shù)字分別對應(yīng)算例中的任務(wù)組編號,灰色空白部分則為場橋與集裝箱任務(wù)組之間的相互等待時間。其中選取集裝箱任務(wù)組準備時間和場橋到達任務(wù)組對應(yīng)貝位時間這兩者中較大的值作為每個任務(wù)組開始操作的時間,從而得到每個集裝箱任務(wù)組的開始時刻,再根據(jù)表格里任務(wù)組對應(yīng)的數(shù)量得到場橋操作時間和結(jié)束時刻。
圖7 計劃時間域內(nèi)場橋調(diào)度甘特圖
圖8 計劃時間段1內(nèi)各場橋調(diào)度方案圖
圖9 計劃時間段2內(nèi)各場橋調(diào)度方案圖
圖10 計劃時間段3內(nèi)各場橋調(diào)度方案圖
圖11 計劃時間段4內(nèi)各場橋調(diào)方案圖
為了進一步驗證本文所提模型與算法的有效性,將遺傳算法所得結(jié)果與實際運營操作進行對比,結(jié)果見表7所示。從表7 中可以看出不論是在作業(yè)時間還是目標函數(shù)值方面,本文采用的遺傳算法都使得結(jié)果更優(yōu)化,不僅縮短了場橋作業(yè)時間,而且大幅度降低了運營成本。
表7 運算結(jié)果對比表
為了驗證模型與算法的適用性和穩(wěn)定性,選取了8個試驗?zāi)_本,采用遺傳算法和粒子群算法分別針對不同規(guī)模大小的算例進行試驗對比,每個腳本下的目標函數(shù)值均采取試驗10 次取最優(yōu)值的方法,CPU 時間取值則為10 次試驗結(jié)果的平均值,具體結(jié)果如表8 所示,其中S 為箱區(qū)數(shù),Y 為場橋數(shù),T 為總集裝箱任務(wù)數(shù)。
表8 GA與PSO試驗結(jié)果對比
從表8 中可以看到,對于場橋全局調(diào)度問題,結(jié)果表明這兩種算法的結(jié)果幾乎一致。在這八組試驗?zāi)_本中,每組遺傳算法求解得到的解和粒子群算法的解都相差不大,但遺傳算法的運行時間相對較快些,并且其收斂速度更快,從而驗證了遺傳算法在求解本文所提出的場橋全局調(diào)度模型時的穩(wěn)定性和有效性。
本文針對某計劃時間域內(nèi)集裝箱港口的全局場橋調(diào)度問題進行了研究。考慮到場橋作業(yè)過程的不可相互跨越和保持一定的安全距離等約束,引入計劃時間段和時間窗的概念,以場橋移動成本和場橋與集裝箱任務(wù)組之間相互等待成本最小化為目標建立了優(yōu)化模型,并設(shè)計遺傳算法進行求解,結(jié)果表明該模型和算法可以有效解決多箱區(qū)多場橋調(diào)度中場橋相互干擾和安全距離等問題,并且有效減少了不必要的等待時間,為解決大規(guī)模的場橋調(diào)度問題提供了科學(xué)合理的決策依據(jù)。但在實際操作中,場橋的工作效率還受眾多不確定因素的影響,例如機械設(shè)備故障或者船舶提前進港等情況,因此未來可以考慮不確定因素影響下的集卡與場橋聯(lián)合調(diào)度,從而更加優(yōu)化集裝箱港口的堆場操作。