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

艾立紅，韓曉龍

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

0 引 言

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

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

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

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

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

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

1.2 符號(hào)定義

參數(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空載時(shí)單位時(shí)間的行駛能耗，unit/s；αw為AGV負(fù)載時(shí)單位時(shí)間的行駛能耗，unit/s；αv為AGV單位時(shí)間的等待能耗，unit/s；γ為QC 單位時(shí)間的平均能耗，unit/s；η為ASC單位時(shí)間的平均能耗，unit/s；tkj為AGVk從任務(wù)j的起點(diǎn)行進(jìn)到任務(wù)j終點(diǎn)的時(shí)間；tkjj′為AGVk從上一任務(wù)j的終點(diǎn)行進(jìn)到當(dāng)前任務(wù)j′起點(diǎn)的時(shí)間；trjj′為當(dāng)任務(wù)j與j′在同一箱區(qū)時(shí)，ASCr從堆場(chǎng)任務(wù)j終點(diǎn)行進(jìn)到任務(wù)j′起點(diǎn)的時(shí)間；tqjj′為任務(wù)j和j′由同一臺(tái)QCq作業(yè)時(shí)，QCq從任務(wù)j終點(diǎn)行進(jìn)到任務(wù)j′起點(diǎn)的時(shí)間；τ為QC裝卸單位集裝箱的時(shí)間；p為ASC裝卸單位集裝箱的時(shí)間；λj∈{0,1}，若j為出口箱則λj為1，否則為0。

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

(1)

(2)

αvλj(crj-akj))

(3)

(4)

(5)

(6)

除有特殊說(shuō)明外，上述模型中：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在整個(gè)工作時(shí)間內(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)化過(guò)程的啟發(fā)式搜索算法。由于遺傳算法具有全局搜索的特征，并且搜索速度較快，所以用遺傳算法求得的解通常比用其他方法得到的解更優(yōu)。遺傳算法的編碼方法簡(jiǎn)單，搜索面廣，交叉、變異等遺傳操作也較易實(shí)現(xiàn)，已被廣泛應(yīng)用于組合優(yōu)化、生產(chǎn)調(diào)度、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。

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

圖1 遺傳算法流程

2.1 染色體編碼

每臺(tái)QC和ASC需要作業(yè)的集裝箱編號(hào)是已計(jì)劃好的，因此對(duì)每臺(tái)QC和ASC只需要優(yōu)化其作業(yè)序列。本文針對(duì)QC、AGV、ASC的協(xié)調(diào)調(diào)度問(wèn)題，采用雙層實(shí)數(shù)編碼方式。如圖2所示，每個(gè)染色體有2行：第一行代表集裝箱編號(hào)，編號(hào)序列即為相應(yīng)集裝箱被作業(yè)的順序；第二行代表為相應(yīng)集裝箱分配的AGV編號(hào)。設(shè)有10個(gè)集裝箱，按照計(jì)劃，集裝箱1～5由QC1完成，集裝箱6～10由QC2完成，集裝箱1、2、3、9、10在堆場(chǎng)箱區(qū)1由ASC1作業(yè)完成，集裝箱4～8在堆場(chǎng)箱區(qū)2由ASC2完成。根據(jù)圖2和集裝箱分配計(jì)劃，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)生初始化種群，見(jiàn)圖3。在初始種群中，集裝箱編號(hào)的序列隨機(jī)生成，并且隨機(jī)分配AGV作業(yè)于不同的集裝箱。

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

對(duì)滿足能耗約束條件的染色體個(gè)體計(jì)算適應(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)染色體被保留下來(lái)的概率就越大。

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

2.4 選擇、交叉、變異操作

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

圖4 染色體個(gè)體交叉

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

圖6染色體個(gè)體變異

3 案例分析

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

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

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

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

3.2 案例結(jié)果

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

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

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

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

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

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

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

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

4 結(jié) 論

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