考慮能耗的自動化碼頭裝卸設(shè)備協(xié)調(diào)調(diào)度

艾立紅，韓曉龍

(上海海事大學(xué)物流科學(xué)與工程研究院，上海 201306)

0 引 言

作為航運(yùn)與陸運(yùn)交通的樞紐站，集裝箱碼頭在全球供應(yīng)鏈中發(fā)揮著重要作用。隨著物流量的增長和人力成本的上升，自動化碼頭越來越受到青睞，其采用的自動化裝卸設(shè)備能進(jìn)一步提升碼頭裝卸效率，降低運(yùn)輸成本，對提高經(jīng)濟(jì)效益和社會效益具有重要意義。自動化集裝箱碼頭的裝卸設(shè)備主要有3種，即岸橋(quay crane，QC)、自動引導(dǎo)車(automated guided vehicle，AGV)和自動堆垛機(jī)(automated stacker crane，ASC)，三者的作業(yè)效率和合理調(diào)度是自動化碼頭裝卸效率和節(jié)能效益提升的關(guān)鍵。

當(dāng)前，環(huán)境污染和能源消耗已經(jīng)受到廣泛關(guān)注。集裝箱碼頭由于擁有相當(dāng)數(shù)量的大型裝卸設(shè)備，是環(huán)境污染的源頭之一。綠色港口是未來港口建設(shè)的重要方向，其要求在盡量提高碼頭服務(wù)水平的情況下，減少能源消耗和碳排放。

關(guān)于集裝箱碼頭裝卸設(shè)備調(diào)度方面的研究較多。韓曉龍等[1]針對卸船作業(yè)，考慮集卡到達(dá)時間的不確定性，以最小化集卡完工時間為目標(biāo)函數(shù)，建立了QC與集卡協(xié)同調(diào)度模型，并用改進(jìn)的遺傳算法求解。CAO等[2]針對作業(yè)于進(jìn)口集裝箱的QC和集卡調(diào)度，建立混合整數(shù)規(guī)劃模型，并綜合利用遺傳算法和基于約翰遜規(guī)則的啟發(fā)式算法求解，提高了求解精度。LAU等[3]考慮QC在作業(yè)過程中的最佳作業(yè)順序，以最小化QC操作延遲時間、AGV總行程時間和自動化場橋(automated yard crane，AYC)總行程時間為目標(biāo)，建立了混合整數(shù)規(guī)劃模型，并用多層遺傳算法和遺傳最大匹配算法求解。樂美龍等[4]以船舶在港停靠時間最短為目標(biāo)，建立了自動化碼頭QC、AGV和AYC的聯(lián)合調(diào)度模型，并通過算例驗(yàn)證了模型的有效性，該模型可以提高碼頭運(yùn)輸效率。LU等[5]考慮了內(nèi)集卡行駛速度，場橋水平運(yùn)行速度、裝卸速度等不確定性因素，以最小化QC、集卡和場橋的操作總時間為目標(biāo)建立模型，用粒子群優(yōu)化算法求解。KAVESHGAR等[6]考慮了集裝箱任務(wù)之間的優(yōu)先關(guān)系、QC之間的干擾和碼頭安全裕度等現(xiàn)實(shí)約束，建立了QC和集卡的協(xié)調(diào)調(diào)度，并結(jié)合遺傳算法和貪婪算法進(jìn)行了求解。添玉等[7]針對自動化碼頭自帶提升功能的AGV和起重機(jī)的集成調(diào)度，考慮設(shè)備間的相互制約，建立了多目標(biāo)混合整數(shù)規(guī)劃模型，并用雙層遺傳算法求解。羅勛杰[8]基于目前全球全自動化碼頭水平運(yùn)輸系統(tǒng)的應(yīng)用現(xiàn)狀，對AGV和自動跨運(yùn)車兩種主要運(yùn)輸方式進(jìn)行了對比分析。盧毅勤[9]考慮內(nèi)集卡和場橋作業(yè)過程中的不確定性因素，構(gòu)建了堆場設(shè)備集成調(diào)度優(yōu)化模型，以探討不確定因素對堆場設(shè)備作業(yè)的影響。楊勇生等[10]考慮AGV和軌道式龍門吊(rail-mounted gantry crane，RMG)的任務(wù)分配約束，構(gòu)建AGV和RMG的協(xié)同調(diào)度模型，得出AGV、QC和箱區(qū)數(shù)量不同時的卸船完工時間。嚴(yán)庭玉[11]根據(jù)集裝箱碼頭裝卸作業(yè)特點(diǎn)和運(yùn)作方式，基于圖論方法構(gòu)建了裝卸設(shè)備的網(wǎng)絡(luò)調(diào)度模型，將該模型的結(jié)果與集成調(diào)度模型的結(jié)果進(jìn)行對比，證明了所建模型的有效性。

考慮能耗的集裝箱碼頭設(shè)備調(diào)度的文獻(xiàn)較少。HE等[12]以最小化所有船舶的總離港延遲時間和所有任務(wù)的總能耗為目標(biāo)建立混合整數(shù)規(guī)劃模型，開發(fā)了一種基于仿真的優(yōu)化算法求解。嚴(yán)南南等[13]考慮了集卡能耗，建立QC與集卡協(xié)調(diào)調(diào)度的雙目標(biāo)模型，并用遺傳算法求解。郭嬋嬋[14]基于混合流水車間的思想，以作業(yè)時間最短和作業(yè)能耗最低為目標(biāo)，建立QC、集卡和場橋調(diào)度的多目標(biāo)模型。SHA等[15]在考慮起重機(jī)移動距離、轉(zhuǎn)彎距離以及與總能耗直接相關(guān)的、基于實(shí)際運(yùn)行規(guī)律的關(guān)鍵因素的基礎(chǔ)上，建立了集裝箱碼頭堆場起重機(jī)的調(diào)度模型，以減少起重機(jī)的總能耗。

相比已有文獻(xiàn)，本文在集裝箱自動化碼頭QC、AGV和ASC的協(xié)調(diào)調(diào)度問題中考慮了裝卸設(shè)備的能耗約束。已有的關(guān)于集裝箱碼頭設(shè)備調(diào)度的文獻(xiàn)，大多只考慮一種設(shè)備或兩種設(shè)備的協(xié)調(diào)調(diào)度，而對能耗的考慮多體現(xiàn)在宏觀層面(如建立綠色港口評價指標(biāo)體系等)，在運(yùn)營層面考慮得較少，只有較少文獻(xiàn)考慮了集卡的能耗。本文以定量方法將能耗考慮到自動化碼頭裝卸設(shè)備的協(xié)調(diào)調(diào)度中，以設(shè)備總作業(yè)時間最短和能耗最低為目標(biāo)，建立包括QC、AGV和ASC的雙目標(biāo)調(diào)度模型。

1 模型構(gòu)建

1.1 問題描述

考慮多QC、多AGV和多ASC的情況，集裝箱作業(yè)過程為：在卸船過程中，船上集裝箱被根據(jù)貝位分配給不同的QC，每臺QC將集裝箱卸載到AGV上，AGV將集裝箱運(yùn)到指定的堆場箱區(qū)，每個箱區(qū)配備1臺ASC將集裝箱卸載到對應(yīng)箱區(qū)。裝船過程與之相反。本文要實(shí)現(xiàn)兩個目標(biāo)，分別為QC、AGV和ASC這3種設(shè)備總作業(yè)時間最短和總能耗最低。

模型假設(shè)：(1)不考慮AGV的路徑優(yōu)化；(2)ASC不能跨箱區(qū)作業(yè)；(3)ASC在計劃期內(nèi)只服務(wù)于內(nèi)部AGV。

1.2 符號定義

參數(shù)：Q為QC集合,q∈Q；K為AGV集合，k∈K；R為ASC集合,r∈R；J為所有集裝箱作業(yè)任務(wù)集合,j∈J(|J|=n)；Jq為QCq的作業(yè)任務(wù)集合，q∈Q，Jq?J(|Jq|=nq)；Jr為ASCr的作業(yè)任務(wù)集合，r∈R,Jr?J(|Jr|=nr)；αt為AGV空載時單位時間的行駛能耗，unit/s；αw為AGV負(fù)載時單位時間的行駛能耗，unit/s；αv為AGV單位時間的等待能耗，unit/s；γ為QC 單位時間的平均能耗，unit/s；η為ASC單位時間的平均能耗，unit/s；tkj為AGVk從任務(wù)j的起點(diǎn)行進(jìn)到任務(wù)j終點(diǎn)的時間；tkjj′為AGVk從上一任務(wù)j的終點(diǎn)行進(jìn)到當(dāng)前任務(wù)j′起點(diǎn)的時間；trjj′為當(dāng)任務(wù)j與j′在同一箱區(qū)時，ASCr從堆場任務(wù)j終點(diǎn)行進(jìn)到任務(wù)j′起點(diǎn)的時間；tqjj′為任務(wù)j和j′由同一臺QCq作業(yè)時，QCq從任務(wù)j終點(diǎn)行進(jìn)到任務(wù)j′起點(diǎn)的時間；τ為QC裝卸單位集裝箱的時間；p為ASC裝卸單位集裝箱的時間；λj∈{0,1}，若j為出口箱則λj為1，否則為0。

1.3 能耗模型構(gòu)建

(1)

(2)

αvλj(crj-akj))

(3)

(4)

(5)

(6)

除有特殊說明外，上述模型中：q∈Q;k∈K;r∈R;j,j′∈J,j≠j′。式(1)為AGV從任務(wù)j終點(diǎn)行進(jìn)到下一任務(wù)j′起點(diǎn)的能耗；式(2)為AGV等待QC完成任務(wù)j的能耗；式(3)為AGV等待ASC完成任務(wù)j的能耗；式(4)為AGV將任務(wù)j從起點(diǎn)運(yùn)到終點(diǎn)的能耗；式(5)和(6)分別為QC和ASC在整個工作時間內(nèi)的能耗。

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

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

ckj≥(1-λj)(crj-p), ?j∈Jr

(18)

ckj≥λj(cqj-τ), ?j∈Jq

(19)

(20)

crj≥akj+p, ?j∈Jr

(21)

akj′+M(1-φkjj′)≥(ckj+tkjj′φkjj′)λj′

(22)

(23)

akj≥(cqj+tkj)(1-λj), ?j∈Jq

(24)

(25)

crj′-p+M(1-φrjj′)≥crj+trjj′,

?j,j′∈Jr,(j≠j′)

(26)

cqj′-τ+M(1-θqjj′)≥cqj+tqjj′,

?j,j′∈Jq,(j≠j′)

(27)

skj′,wkj,srj′,wrj,sqj′,wqj,θqjj′,φkjj′,φrjj′,

λj∈{0,1}

(28)

(29)

2 遺傳算法

遺傳算法是一種模擬生物自然進(jìn)化過程的啟發(fā)式搜索算法。由于遺傳算法具有全局搜索的特征，并且搜索速度較快，所以用遺傳算法求得的解通常比用其他方法得到的解更優(yōu)。遺傳算法的編碼方法簡單，搜索面廣，交叉、變異等遺傳操作也較易實(shí)現(xiàn)，已被廣泛應(yīng)用于組合優(yōu)化、生產(chǎn)調(diào)度、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。

本文先用遺傳算法求解能耗值；根據(jù)求得的結(jié)果，設(shè)置不同的能耗值作為約束條件；對滿足能耗約束條件的染色體求適度應(yīng)值，對不滿足能耗約束條件的個體(劣質(zhì)個體)設(shè)其適應(yīng)度值為0，繼續(xù)進(jìn)行遺傳算法求解(如圖1)，實(shí)現(xiàn)能耗對求解最短時間目標(biāo)的約束功能。能耗約束值是可以調(diào)節(jié)的。

圖1 遺傳算法流程

2.1 染色體編碼

每臺QC和ASC需要作業(yè)的集裝箱編號是已計劃好的，因此對每臺QC和ASC只需要優(yōu)化其作業(yè)序列。本文針對QC、AGV、ASC的協(xié)調(diào)調(diào)度問題，采用雙層實(shí)數(shù)編碼方式。如圖2所示，每個染色體有2行：第一行代表集裝箱編號，編號序列即為相應(yīng)集裝箱被作業(yè)的順序；第二行代表為相應(yīng)集裝箱分配的AGV編號。設(shè)有10個集裝箱，按照計劃，集裝箱1～5由QC1完成，集裝箱6～10由QC2完成，集裝箱1、2、3、9、10在堆場箱區(qū)1由ASC1作業(yè)完成，集裝箱4～8在堆場箱區(qū)2由ASC2完成。根據(jù)圖2和集裝箱分配計劃，QC1作業(yè)順序?yàn)?→5→1→4→2，QC2作業(yè)順序?yàn)?→7→9→10→6，AGV1作業(yè)順序?yàn)?→2，AGV2作業(yè)順序?yàn)?→4，AGV3作業(yè)順序?yàn)?→1→6，AGV4作業(yè)順序?yàn)?→9→10，ASC1作業(yè)順序?yàn)?→1→9→10→2，ASC2作業(yè)順序?yàn)?→8→7→4→6。

圖2染色體編碼

2.2 種群初始化

隨機(jī)產(chǎn)生初始化種群，見圖3。在初始種群中，集裝箱編號的序列隨機(jī)生成，并且隨機(jī)分配AGV作業(yè)于不同的集裝箱。

2.3 適應(yīng)度函數(shù)

對滿足能耗約束條件的染色體個體計算適應(yīng)度值。本文的目標(biāo)是求取最小值，因此取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，即適應(yīng)度函數(shù)F(x)=1/f1。目標(biāo)函數(shù)值越小，適應(yīng)度值越大，相應(yīng)染色體被保留下來的概率就越大。

圖3隨機(jī)生成染色體個體

2.4 選擇、交叉、變異操作

為提高收斂速度，采用兩點(diǎn)交叉的方式。隨機(jī)選擇2個染色體和2個基因位，2個基因位的中間部分作為交叉部分。交叉完成后，子代個體中集裝箱編號有重復(fù)、缺失現(xiàn)象(見圖4)，因此要對子代染色體進(jìn)行修補(bǔ)，將重復(fù)集裝箱編號剔除，補(bǔ)充為缺失的集裝箱編號(見圖5)。

圖4 染色體個體交叉

隨機(jī)選擇一個染色體上的基因位，根據(jù)變異因子決定是否變異。變異時，如果對編碼的第一行進(jìn)行變異，則變異完成后需進(jìn)行修補(bǔ)，修補(bǔ)的編碼仍是變異前的編碼，因此對編碼的第一行進(jìn)行變異是沒有意義的，只需要對編碼的第二行進(jìn)行變異，見圖6。

圖6染色體個體變異

3 案例分析

3.1 初始數(shù)據(jù)設(shè)計

設(shè)有1艘船，2臺QC，4輛AGV，2臺ASC，50個集裝箱。設(shè)備作業(yè)于集裝箱時，根據(jù)查閱到的文獻(xiàn)隨機(jī)生成初始參數(shù)，其他恒定參數(shù)根據(jù)查閱到的文獻(xiàn)設(shè)置，見表1。

表1 參數(shù)設(shè)置

裝卸設(shè)備的作業(yè)時間通常以s為單位，但為便于計算能耗，表1中能耗單位采用unit/min。QC和ASC在提起集裝箱和平移過程中能耗是不同的，為方便計算，取QC和ASC在作業(yè)過程中的平均能耗分別為3 unit/min和 2 unit/min。

3.2 案例結(jié)果

設(shè)置最大迭代次數(shù)為500，種群規(guī)模為100，交叉概率為0.6，變異概率為0.01。

先計算得到裝卸設(shè)備的總能耗為1 600～5 000 unit。若能耗約束值過低，則裝卸時間會很長，不符合碼頭高效率的實(shí)際工作要求；若能耗約束值過高，則達(dá)不到節(jié)約能耗的要求。因此，分別設(shè)置能耗約束值為3 400、3 200、3 000、2 800、2 600 unit，計算裝卸設(shè)備在不同能耗約束下的作業(yè)時間和作業(yè)能耗，結(jié)果見表2。

表2 不同能耗約束下的作業(yè)時間和作業(yè)能耗

當(dāng)不考慮能耗時，直接計算使作業(yè)時間最短的目標(biāo)函數(shù)，算法在迭代次數(shù)為70時收斂(圖7a)，此時最短作業(yè)時間、作業(yè)能耗分別為48 378 s和2 728 unit；當(dāng)能耗約束值為3 400 unit時，算法在迭代次數(shù)為110時收斂(圖7b)，此時最優(yōu)解(即最短作業(yè)時間)比不考慮能耗時的最優(yōu)解多2 447 s(約40.8 min)，但節(jié)省能耗154 unit。

由表2可知，能耗約束值越低，裝卸設(shè)備作業(yè)能耗就越低，但相應(yīng)的作業(yè)時間就越長。當(dāng)能耗約束值為2 600 unit時，裝卸設(shè)備作業(yè)能耗降至1 986unit，比不考慮能耗時節(jié)省742 unit，但裝卸設(shè)備的最短作業(yè)時間比不考慮能耗時的最短作業(yè)時間多8 292 s(138.2 min)，裝卸效率大大降低。這可能是因?yàn)樵谘b卸過程中，為追求低能耗：AGV可能會延長等待時間，從而縮短了空載行駛時間和負(fù)載行駛時間；QC、AGV和ASC可能會改變集裝箱的作業(yè)順序，從而降低設(shè)備作業(yè)能耗，延長了裝卸設(shè)備總的裝卸時間。

表2中的結(jié)果是在滿足不同能耗約束值的條件下求得的最短作業(yè)時間和最低作業(yè)能耗，結(jié)果處于front解集，是解集中的一部分解。從表2可以看出，在計算結(jié)果中，沒有一個使作業(yè)時間和作業(yè)能耗同時最小的解，碼頭運(yùn)營商可根據(jù)需要選擇相應(yīng)的調(diào)度方案。如果運(yùn)營商對節(jié)能要求較高，則設(shè)置較低的能耗約束值；如果運(yùn)營商需要更高的效率，則設(shè)置較高的能耗約束值。

a)不考慮能耗b)能耗約束值為3 400 unit

圖7作業(yè)時間收斂曲線

4 結(jié) 論

與以往文獻(xiàn)相比，本文將能耗量化，構(gòu)建了考慮能耗的自動化碼頭裝卸設(shè)備協(xié)調(diào)調(diào)度的雙目標(biāo)模型，并用遺傳算法求解。結(jié)果顯示，自動化碼頭裝卸設(shè)備在進(jìn)行集裝箱裝卸時，考慮能耗比不考慮能耗消耗的時間更多，但能耗更少，而且能耗要求越低，裝卸時間就越長。本文針對自動化碼頭低耗能和高效率目標(biāo)，研究碼頭裝卸設(shè)備協(xié)調(diào)調(diào)度問題，符合綠色碼頭的建設(shè)要求和未來港口的發(fā)展趨勢。本文在構(gòu)建模型時，沒有考慮AGV的路徑優(yōu)化，而AGV的行駛路徑對碼頭裝卸效率和能耗有同樣重要的影響，因此以后的研究方向是將AGV的行駛路徑考慮到裝卸設(shè)備的協(xié)調(diào)調(diào)度中，對碼頭設(shè)備裝卸效率與能耗進(jìn)行更好的權(quán)衡。