集裝箱碼頭設(shè)備配置與作業(yè)調(diào)度集成優(yōu)化研究

仲昭林，孔 珊，張紀(jì)會(huì)，郭乙運(yùn)

1.青島大學(xué) 復(fù)雜性科學(xué)研究所，山東 青島 266071 2.山東省工業(yè)控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島 266071 3.青島港國(guó)際股份有限公司，山東 青島 266011

海上運(yùn)輸事業(yè)的快速發(fā)展對(duì)集裝箱碼頭作業(yè)提出了更高的要求，在提高裝卸效率的同時(shí)兼顧降本節(jié)能的目標(biāo)，實(shí)現(xiàn)碼頭綠色可持續(xù)發(fā)展[1]。自動(dòng)導(dǎo)引車(chē)（automated guided vehicle，AGV）作為碼頭無(wú)人駕駛的水平搬運(yùn)設(shè)備，沿既定路徑水平運(yùn)輸集裝箱，在碼頭降本增效方面發(fā)揮重要作用[2]。雙小車(chē)岸橋是集裝箱碼頭的主要設(shè)備，由門(mén)架小車(chē)、中轉(zhuǎn)平臺(tái)和主小車(chē)組成，結(jié)構(gòu)如圖1所示[3]。雙小車(chē)岸橋和AGV相互配合可以減少作業(yè)等待時(shí)長(zhǎng)，提高效率[4]。

圖1 雙小車(chē)岸橋示意圖Fig.1 Dual-trolley quay crane

集裝箱碼頭作業(yè)調(diào)度一直是國(guó)內(nèi)外研究熱點(diǎn)，AGV路徑規(guī)劃和調(diào)度研究是其中一個(gè)重要方向。AGV路徑規(guī)劃主要解決如何在保證AGV安全運(yùn)行距離以及避免路徑?jīng)_突的前提下減少行駛路程。Zhong等[5]研究了避免AGV死鎖的條件。范厚明等[6]提出了分階段AGV路徑規(guī)劃方法。高文文等[7]研究了考慮集裝箱優(yōu)先級(jí)的AGV路徑規(guī)劃問(wèn)題。Ma等[8]研究了AGV單次負(fù)載多個(gè)集裝箱的裝卸一體化作業(yè)調(diào)度問(wèn)題。多設(shè)備間的集成優(yōu)化研究主要集中于岸橋和AGV或者集卡的聯(lián)合調(diào)度。Hu等[9]研究了碼頭前沿自動(dòng)升降機(jī)與AGV的協(xié)調(diào)問(wèn)題，建立了兩個(gè)以運(yùn)營(yíng)成本最低為目標(biāo)的混合整數(shù)規(guī)劃模型并用改進(jìn)粒子群算法進(jìn)行求解。Kaveshgar等[10]在考慮集裝箱優(yōu)先級(jí)以及安全距離等約束條件下，以最小化作業(yè)完成時(shí)間為目標(biāo)建立了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了貪婪算法和遺傳算法相結(jié)合的求解方法。岸橋、水平搬運(yùn)設(shè)備以及場(chǎng)橋之間的聯(lián)合配置與調(diào)度優(yōu)化問(wèn)題也逐漸引起學(xué)者的關(guān)注，考慮到集成優(yōu)化問(wèn)題的復(fù)雜性，大部分學(xué)者使用啟發(fā)式算法進(jìn)行求解，但也有少數(shù)學(xué)者利用精確算法進(jìn)行求解，如Jiang等[11]，還有部分學(xué)者采用仿真方法進(jìn)行求解，如Xin等[12]。Homayouni等[13]考慮了岸橋、AGV和分平臺(tái)/檢索系統(tǒng)（SP-AS/RS）上裝卸任務(wù)的綜合調(diào)度問(wèn)題并用改進(jìn)型遺傳算法進(jìn)行求解。Yang等[14]探討了在AGV路線已知的條件下對(duì)集裝箱碼頭核心設(shè)備的綜合調(diào)度問(wèn)題，以最小化最大完工時(shí)間為目標(biāo)建立了雙層優(yōu)化模型，并設(shè)計(jì)了雙層遺傳算法的求解方法。Kizilay等[15]以最小化船舶在港時(shí)間和最大化作業(yè)效率為目標(biāo)，將集裝箱碼頭岸橋調(diào)度、堆場(chǎng)位置分配及集卡調(diào)度的集成問(wèn)題分解成混合整數(shù)規(guī)劃模型和約束模型，結(jié)果表明約束模型比混合整數(shù)規(guī)劃模型更有實(shí)際應(yīng)用價(jià)值。Jonker等[16]研究了裝卸同步作業(yè)模式下岸橋、場(chǎng)橋及AGV綜合調(diào)度問(wèn)題，將其抽象為混合流水車(chē)間調(diào)度問(wèn)題，提出了改進(jìn)模擬退火算法。

以上工作均是從提高碼頭作業(yè)效率角度進(jìn)行研究，能耗問(wèn)題并未引起足夠重視，隨著綠色可持續(xù)發(fā)展理念的逐步普及，考慮作業(yè)設(shè)備能耗節(jié)約勢(shì)在必行。此方向的研究主要集中于減少資源消耗和二氧化碳排放兩方面。在減少資源消耗方面，Kim等[17]在考慮AGV調(diào)度策略的基礎(chǔ)上，以最小化作業(yè)延誤產(chǎn)生的能耗為目標(biāo)，探討了AGV配置與調(diào)度方案。Yang等[18]以鐵水聯(lián)運(yùn)集裝箱碼頭各設(shè)備能耗為研究對(duì)象，在同步裝卸作業(yè)的基礎(chǔ)上，建立了最小化能耗和工作時(shí)間的雙目標(biāo)聯(lián)合優(yōu)化模型，并用改進(jìn)遺傳算法求解。Ai等[19]度量了碼頭核心設(shè)備不同作業(yè)狀態(tài)能耗量，建立了以最小化總作業(yè)時(shí)間和總作業(yè)能耗為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，并利用遺傳算法進(jìn)行求解。在降低二氧化碳排放方面，Wang等[20]分析了我國(guó)30個(gè)集裝箱碼頭數(shù)據(jù)，得出港口二氧化碳排放的空間布局和驅(qū)動(dòng)因素，提出了一種易于實(shí)現(xiàn)的集裝箱碼頭二氧化碳排放計(jì)算方法。Julián等[21]以巴倫西亞港為例，研究了能源消耗和二氧化碳排放在港口設(shè)備中的分布情況，提出了減少二氧化碳排放的方法。還有部分學(xué)者考慮了設(shè)備調(diào)度過(guò)程中能耗最小化問(wèn)題，如Chang[22]、He[23]等。

集裝箱碼頭緩沖區(qū)[24]的存在可以有效協(xié)調(diào)各設(shè)備作業(yè)效率。Kress等[25]在考慮同步裝卸作業(yè)時(shí)，以最小化船舶在港時(shí)間為目標(biāo)研究岸橋側(cè)緩沖區(qū)容量有限制的調(diào)度優(yōu)化問(wèn)題。程聰聰?shù)萚26]在AGV伴侶（緩沖區(qū)）容量限制條件下，對(duì)AGV調(diào)度問(wèn)題展開(kāi)了研究。秦琴等[27]利用緩沖有限流水車(chē)間調(diào)度理論研究了“雙小車(chē)岸橋+AGV+緩沖支架+自動(dòng)化軌道吊”的裝卸工藝。

從上述研究可以發(fā)現(xiàn)：（1）目前研究多以最小化作業(yè)時(shí)間為目標(biāo)，沒(méi)有兼顧能耗約束對(duì)碼頭整體調(diào)度影響。（2）大部分研究忽視了AGV調(diào)度過(guò)程中路徑?jīng)_突對(duì)運(yùn)輸效率和能耗的影響，單一裝卸過(guò)程研究較多，忽視了裝卸同步模式中作業(yè)環(huán)節(jié)的耦合作用。（3）集裝箱碼頭緩沖區(qū)的設(shè)立可以改善設(shè)備間的協(xié)調(diào)問(wèn)題，雙小車(chē)岸橋中轉(zhuǎn)平臺(tái)的存在可以減少AGV和門(mén)架小車(chē)等待時(shí)間，提高作業(yè)效率，堆場(chǎng)緩沖支架可以減少AGV和場(chǎng)橋的等待時(shí)間，降低碼頭整體作業(yè)能耗。（4）針對(duì)裝卸作業(yè)過(guò)程中能耗度量問(wèn)題，大部分學(xué)者過(guò)度簡(jiǎn)化模型，未能顧及各設(shè)備不同狀態(tài)能耗?？紤]碼頭核心設(shè)備不同作業(yè)狀態(tài)能耗，兼顧緩沖區(qū)容量和AGV無(wú)路徑?jīng)_突等限制對(duì)集裝箱碼頭設(shè)備進(jìn)行聯(lián)合配置與調(diào)度研究，具有重要的理論與實(shí)際價(jià)值。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

集裝箱碼頭作業(yè)過(guò)程中各設(shè)備相互配合，共同完成既定的裝卸任務(wù)：雙小車(chē)岸橋和場(chǎng)橋負(fù)責(zé)集裝箱垂直運(yùn)輸，AGV負(fù)責(zé)集裝箱水平搬運(yùn)。隨著任務(wù)數(shù)量增多，各設(shè)備之間可能會(huì)出現(xiàn)因銜接不當(dāng)而導(dǎo)致等待的現(xiàn)象，造成資源浪費(fèi)。當(dāng)運(yùn)行AGV數(shù)量增大時(shí)，還可能發(fā)生運(yùn)行路徑?jīng)_突，甚至造成碼頭運(yùn)行系統(tǒng)癱瘓，嚴(yán)重影響碼頭運(yùn)作效率（如圖2所示）。圖3展示了AGV水平作業(yè)區(qū)域碼頭各路徑節(jié)點(diǎn)（AGV改變行駛方向或改變作業(yè)狀態(tài)的點(diǎn)）位置布局。集裝箱碼頭作業(yè)流程可分為卸船過(guò)程和裝船過(guò)程。卸船作業(yè)時(shí)雙小車(chē)岸橋主小車(chē)將集裝箱從船上任務(wù)貝位運(yùn)送到岸橋中轉(zhuǎn)平臺(tái)，再由岸橋門(mén)架小車(chē)將集裝箱從中轉(zhuǎn)平臺(tái)運(yùn)送到AGV上并由其運(yùn)送到對(duì)應(yīng)緩沖支架上，最后由場(chǎng)橋運(yùn)送至堆場(chǎng)相應(yīng)位置堆放[28]，裝船過(guò)程則與之相反。自動(dòng)化集裝箱碼頭布局與作業(yè)流程如圖4所示。

圖2 AGV路徑?jīng)_突示意圖Fig.2 Conflict in AGV path

圖3 路徑節(jié)點(diǎn)示意圖Fig.3 Different nodes on path

圖4 自動(dòng)化集裝箱碼頭工作示意圖Fig.4 Layout of automated container terminal

由于岸橋中轉(zhuǎn)平臺(tái)和緩沖支架容量限制，當(dāng)中轉(zhuǎn)平臺(tái)上沒(méi)有多余空間存放卸船集裝箱或沒(méi)有裝船集裝箱時(shí)，岸橋主小車(chē)都要等待，從而影響裝卸效率，產(chǎn)生等待能耗。堆場(chǎng)緩沖支架也存在同樣問(wèn)題。因此，在集裝箱碼頭作業(yè)過(guò)程中，通過(guò)AGV配置與調(diào)度減少各設(shè)備等待時(shí)間，消除AGV路徑?jīng)_突、降低碼頭能耗是集裝箱碼頭作業(yè)必須解決的問(wèn)題。

因此，在考慮雙小車(chē)中轉(zhuǎn)平臺(tái)和緩沖支架容量時(shí)，結(jié)合AGV無(wú)路徑?jīng)_突約束，建立了以岸橋、場(chǎng)橋和AGV最小作業(yè)能耗之和及最小化船舶在港時(shí)間為目標(biāo)的多目標(biāo)混合整數(shù)規(guī)劃模型，并提出改進(jìn)型遺傳算法進(jìn)行求解，實(shí)現(xiàn)AGV最優(yōu)配置與作業(yè)調(diào)度集成優(yōu)化目的。

假設(shè)條件如下：

（1）集裝箱碼頭各岸橋、場(chǎng)橋和AGV均同質(zhì)且同種設(shè)備在相同狀態(tài)下單位時(shí)間能耗相同；

（2）集裝箱規(guī)格相同且不考慮堆場(chǎng)和船舶的翻箱問(wèn)題；

（3）待裝卸集裝箱位置及裝卸順序已知；

（4）集裝箱碼頭所有設(shè)備一次只執(zhí)行一個(gè)標(biāo)準(zhǔn)箱裝卸任務(wù)。

1.2 符號(hào)說(shuō)明

S、F：分別表示虛擬開(kāi)始任務(wù)和虛擬結(jié)束任務(wù)。

L：裝船集裝箱集合。

U：卸船集裝箱集合。

N：所有任務(wù)集合，N=L?U?{ }S,F。

A：AGV集合。

K：岸橋集合。

C：場(chǎng)橋集合。

L k：岸橋k的裝船集裝箱集合，k∈K。

U k：岸橋k的卸船集裝箱集合，k∈K。

L c：場(chǎng)橋c的裝船集裝箱集合，c∈C。

U c：場(chǎng)橋c的卸船集裝箱集合，c∈C。

M：足夠大的正數(shù)。

a11、a12：分別表示岸橋處于工作狀態(tài)和等待狀態(tài)時(shí)的單位時(shí)間能耗。

a21、a22、a23：分別表示AGV處于空載狀態(tài)、等待狀態(tài)和滿(mǎn)載狀態(tài)時(shí)的單位時(shí)間能耗。

a31、a32：分別表示場(chǎng)橋處于工作狀態(tài)和等待狀態(tài)時(shí)的單位時(shí)間能耗。

v：岸橋中轉(zhuǎn)平臺(tái)容量。

p：場(chǎng)橋緩沖支架容量。

H：集裝箱碼頭所有路徑節(jié)點(diǎn)集合。

Ha-：第a輛AGV路徑上具有多方向行走路徑節(jié)點(diǎn)的集合。

1.3 目標(biāo)函數(shù)

目標(biāo)函數(shù)包括兩個(gè)：最小化作業(yè)能耗和最小化船舶在港時(shí)間。令EQ、EV、EY分別表示岸橋、AGV和場(chǎng)橋的能耗，則有：

式（1）和式（3）分別表示岸橋和場(chǎng)橋在裝卸過(guò)程中的等待和工作能耗；式（2）表示AGV在裝卸作業(yè)過(guò)程中的空載、滿(mǎn)載和等待能耗之和，即AGV作業(yè)過(guò)程總能耗。

目標(biāo)函數(shù)：

式（4）和式（5）分別表示集裝箱碼頭最小化總能耗和最小化船舶在港時(shí)間。

約束條件：

模型共有四類(lèi)約束，分別為：岸橋調(diào)度約束、AGV避免路徑?jīng)_突約束、緩沖支架容量約束和場(chǎng)橋調(diào)度約束。

（1）岸橋調(diào)度約束

式（6）定義了最大化完工時(shí)間；式（7）和式（8）分別表示集裝箱在裝卸過(guò)程中的完工時(shí)間；式（9）和式（10）表示任何一個(gè)裝卸作業(yè)只有一個(gè)緊前任務(wù)和一個(gè)緊后任務(wù)；式（11）和式（12）分別表示單輛AGV一次只能執(zhí)行一個(gè)任務(wù)，一個(gè)任務(wù)只由一輛AGV執(zhí)行；式（13）表示同一岸橋主小車(chē)作業(yè)相鄰兩個(gè)任務(wù)的時(shí)間間隔要大于計(jì)劃時(shí)間間隔；式（14）表示岸橋主小車(chē)實(shí)際作業(yè)時(shí)刻不得早于計(jì)劃作業(yè)時(shí)刻；式（15）和式（16）表示在裝卸作業(yè)過(guò)程中AGV、岸橋門(mén)架小車(chē)以及岸橋主小車(chē)作業(yè)時(shí)間要求；式（17）表示同一輛AGV執(zhí)行相鄰兩個(gè)任務(wù)時(shí)間約束；式（18）和式（19）表示岸橋虛擬任務(wù)量等于AGV數(shù)量；式（20）和式（21）分別表示在裝卸作業(yè)過(guò)程中岸橋門(mén)架小車(chē)最早開(kāi)始時(shí)刻和最晚開(kāi)始時(shí)刻約束；式（22）和式（23）表示在裝卸作業(yè)過(guò)程中岸橋門(mén)架小車(chē)實(shí)際作業(yè)時(shí)間約束；式（24）和式（25）表示集裝箱裝卸作業(yè)過(guò)程中岸橋門(mén)架小車(chē)實(shí)際作業(yè)時(shí)刻確定；式（26）和式（27）表示在裝卸過(guò)程中AGV在門(mén)架小車(chē)處等待時(shí)間。

（2）AGV避免路徑?jīng)_突約束

式（28）表示AGV在集裝箱碼頭不同節(jié)點(diǎn)間運(yùn)輸時(shí)刻關(guān)系；式（29）表示AGV進(jìn)入輔路時(shí)刻和離開(kāi)輔路時(shí)刻關(guān)系；式（30）表示相鄰兩個(gè)AGV進(jìn)入同一個(gè)輔路時(shí)刻關(guān)系；式（31）表示第一輛AGV和第三輛AGV進(jìn)入輔路時(shí)刻關(guān)系；式（32）和式（33）表示在卸船作業(yè)時(shí)AGV從岸橋門(mén)架小車(chē)處出發(fā)到進(jìn)入輔路時(shí)間關(guān)系及從離開(kāi)輔路到場(chǎng)橋緩沖支架處時(shí)間關(guān)系；式（34）和式（35）表示在裝船作業(yè)階段AGV從緩沖支架出發(fā)到進(jìn)入輔路時(shí)間關(guān)系及從離開(kāi)輔路到岸橋門(mén)架小車(chē)處時(shí)間關(guān)系；式（36）和式（37）確保當(dāng)AGV進(jìn)入輔路時(shí)不會(huì)發(fā)生死鎖現(xiàn)象；式（38）和式（39）分別表示同一輛AGV在作業(yè)過(guò)程中連續(xù)執(zhí)行兩個(gè)任務(wù)時(shí)間間隔與運(yùn)輸時(shí)間之間的關(guān)系。

（3）緩沖支架容量約束

式（45）和式（46）分別表示在裝卸過(guò)程中場(chǎng)橋最早作業(yè)時(shí)刻和最遲作業(yè)時(shí)刻；式（47）和式（48）表示在裝卸過(guò)程中場(chǎng)橋?qū)嶋H作業(yè)時(shí)間和作業(yè)時(shí)間窗關(guān)系；式（49）和式（50）分別表示在裝卸過(guò)程中場(chǎng)橋?qū)嶋H作業(yè)時(shí)刻；式（51）和式（52）分別表示在裝卸過(guò)程中場(chǎng)橋作業(yè)計(jì)劃更新方式；式（53）和式（54）分別表示作業(yè)過(guò)程中場(chǎng)橋等待時(shí)間。

式（55）和式（56）分別表示各變量的取值約束。

2 算法設(shè)計(jì)

因?yàn)樗⒛Ｐ偷母叨葟?fù)雜性，現(xiàn)有軟件難以求解，所以采用改進(jìn)型遺傳算法進(jìn)行求解。具體步驟如下。

在井下工作面區(qū)域探測(cè)中，各個(gè)探測(cè)測(cè)點(diǎn)方向上波場(chǎng)變換信號(hào)間的相關(guān)程度可通過(guò)相關(guān)系數(shù)來(lái)衡量，相關(guān)系數(shù)與相關(guān)性評(píng)價(jià)見(jiàn)表1，相關(guān)系數(shù)介于1至-1，其絕對(duì)值越大，相關(guān)性越強(qiáng)，反之則相關(guān)性越弱。

2.1 染色體編碼

采用矩陣編碼方式并設(shè)計(jì)了一個(gè)兩行染色體，其中第一和第二行分別為待裝卸任務(wù)編號(hào)和場(chǎng)橋序號(hào)，染色體的長(zhǎng)度等于待裝卸集裝箱數(shù)量。以12個(gè)任務(wù)序號(hào)、4個(gè)場(chǎng)橋和3個(gè)岸橋?yàn)槔ㄈ鐖D5所示），第一行中任務(wù)序號(hào)代表作業(yè)序號(hào)，第二行序號(hào)由場(chǎng)橋所在位置決定，岸橋序號(hào)由任務(wù)所在岸橋作業(yè)區(qū)域決定（事先已知）。該編碼方式之所以沒(méi)有包含AGV調(diào)度信息，是因?yàn)樗惴ㄔ谶\(yùn)行過(guò)程中對(duì)AGV采用“首輛空閑優(yōu)先安排”策略：已知裝卸任務(wù)信息條件下優(yōu)先安排已完成當(dāng)次運(yùn)輸任務(wù)編號(hào)較小的AGV執(zhí)行下一次運(yùn)輸任務(wù)。

圖5 染色體編碼方式Fig.5 Chromosome encoding

2.2 初始種群產(chǎn)生

在式（9）~（12）限制下生成一定數(shù)量個(gè)體：每個(gè)個(gè)體的任務(wù)編號(hào)和場(chǎng)橋序號(hào)利用隨機(jī)數(shù)產(chǎn)生。所有個(gè)體構(gòu)成初始種群。

2.3 評(píng)價(jià)和選擇

具體計(jì)算過(guò)程如下：

步驟1根據(jù)式（45）~（48），計(jì)算場(chǎng)橋c計(jì)劃在緩沖支架放/取集裝箱的時(shí)間窗，同時(shí)根據(jù)式（20）~（23）計(jì)算岸橋k門(mén)架小車(chē)計(jì)劃在中轉(zhuǎn)平臺(tái)上放/取集裝箱的時(shí)間窗；根據(jù)式（28）~（39）計(jì)算第a輛AGV到達(dá)堆場(chǎng)緩沖支架的時(shí)間窗或達(dá)到岸橋處的時(shí)間窗。

步驟2對(duì)于卸船任務(wù)，若重載AGV到達(dá)堆場(chǎng)緩沖支架時(shí)刻不晚于場(chǎng)橋計(jì)劃取箱時(shí)刻，根據(jù)式（40）~（44）判斷緩沖支架任務(wù)存量，若存量在容量范圍內(nèi)，則AGV結(jié)束當(dāng)前任務(wù)并由式（18）~（19）判斷任務(wù)是否結(jié)束，若沒(méi)結(jié)束，則執(zhí)行下一個(gè)任務(wù)并由式（46）和式（48）計(jì)算場(chǎng)橋作業(yè)時(shí)間窗及實(shí)際作業(yè)時(shí)間；若其存量等于容量，則AGV等待，并由式（54）計(jì)算AGV等待時(shí)間；如果重載AGV到達(dá)堆場(chǎng)緩沖支架時(shí)刻晚于場(chǎng)橋計(jì)劃取箱時(shí)刻，根據(jù)式（40）~（44）判斷緩沖支架任務(wù)存量，若存量為0，則場(chǎng)橋等待，若存量在容量范圍內(nèi)，則AGV結(jié)束當(dāng)前任務(wù)并執(zhí)行下一個(gè)任務(wù)，再由式（52）更新進(jìn)度，同時(shí)由式（46）和式（48）計(jì)算場(chǎng)橋作業(yè)時(shí)間窗及實(shí)際作業(yè)時(shí)間；同理，若由式（50）得出空載場(chǎng)橋到達(dá)堆場(chǎng)緩沖支架時(shí)刻不晚于計(jì)劃取箱時(shí)刻，根據(jù)式（40）~（44）判斷其任務(wù)存量，若存量為0，則場(chǎng)橋等待，若存量在容量范圍內(nèi)，則由式（52）更新進(jìn)度并計(jì)算場(chǎng)橋作業(yè)時(shí)間窗和實(shí)際作業(yè)時(shí)間；若晚于計(jì)劃取箱時(shí)刻，則由式（52）和式（46）及式（48）更新進(jìn)度。若岸橋側(cè)空載AGV達(dá)到岸橋處時(shí)間早于由式（25）得出的門(mén)架小車(chē)實(shí)際作業(yè)時(shí)間，則由式（27）計(jì)算等待時(shí)間；若不早于門(mén)架小車(chē)實(shí)際作業(yè)時(shí)間，則由式（21）和式（23）更新門(mén)架小車(chē)時(shí)間窗，并由式（18）~（19）判斷任務(wù)是否結(jié)束，若沒(méi)結(jié)束則由式（13）~（14）以及式（16）~（17）更新岸橋主小車(chē)作業(yè)進(jìn)度。

步驟3對(duì)于裝船任務(wù)，若輕載AGV到達(dá)堆場(chǎng)緩沖支架時(shí)刻晚于場(chǎng)橋計(jì)劃放箱時(shí)刻，則由式（51）更新任務(wù)進(jìn)度；若到達(dá)時(shí)間不晚于場(chǎng)橋計(jì)劃取箱時(shí)間，由式（40）~（44）判斷緩沖支架任務(wù)存量，若存量為0，則AGV等待，并由式（53）計(jì)算等待時(shí)間，否則由式（51）更新任務(wù)進(jìn)度，同時(shí)由式（45）和式（47）計(jì)算場(chǎng)橋作業(yè)時(shí)間窗和實(shí)際作業(yè)時(shí)間；同理，若由式（49）作業(yè)時(shí)刻晚于計(jì)劃放箱時(shí)刻，由式（52）更新任務(wù)，并由式（45）和式（47）計(jì)算場(chǎng)橋作業(yè)時(shí)間窗及實(shí)際作業(yè)時(shí)間；如果實(shí)際作業(yè)時(shí)間不晚于計(jì)劃放箱時(shí)間，由式（40）~（44）判斷緩沖支架存量，若等于容量則場(chǎng)橋等待，否則由式（53）更新任務(wù)進(jìn)度并計(jì)算場(chǎng)橋作業(yè)時(shí)間窗和實(shí)際作業(yè)時(shí)間。同理，若岸橋側(cè)重載AGV達(dá)到岸橋處時(shí)間早于由式（24）得出的門(mén)架小車(chē)實(shí)際作業(yè)時(shí)間，則由式（26）計(jì)算重載AGV等待時(shí)間，若到達(dá)時(shí)間不晚于門(mén)架小車(chē)實(shí)際作業(yè)時(shí)間，由式（20）和式（22）更新門(mén)架小車(chē)作業(yè)任務(wù)時(shí)間窗，并由式（18）、（19）判斷任務(wù)是否結(jié)束，若沒(méi)結(jié)束，則由式（13）、（14）、（15）和式（17）更新岸橋主小車(chē)作業(yè)時(shí)間窗。

上述作業(yè)流程每執(zhí)行一次，均由式（1）~（8）計(jì)算目標(biāo)函數(shù)值并進(jìn)行存儲(chǔ)，直至任務(wù)結(jié)束輸出目標(biāo)函數(shù)值，具體算法計(jì)算流程如圖6所示。在適應(yīng)度函數(shù)設(shè)定上，本文建立的是多目標(biāo)模型且均是求其最小值，考慮到兩目標(biāo)函數(shù)值數(shù)量級(jí)差異對(duì)結(jié)果的影響，因此在設(shè)定適應(yīng)度函數(shù)時(shí)，根據(jù)權(quán)重系數(shù)的取值情況，將適應(yīng)度函數(shù)分別設(shè)置如式（57）和式（58）所示。α為權(quán)重系數(shù)。

圖6 算法流程圖Fig.6 Flowchart of algorithm

當(dāng)權(quán)重系數(shù)為0或1時(shí)，由于是單目標(biāo)函數(shù)，不用考慮目標(biāo)函數(shù)值數(shù)量級(jí)差異造成的影響，因此選用式（57）作為適應(yīng)度函數(shù)。

選擇采用輪盤(pán)賭方式實(shí)現(xiàn)。

2.4 交叉和變異

為平衡算法全局和局部搜索能力，根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)了特定的交叉和變異方式。在算法實(shí)現(xiàn)上分為內(nèi)外兩層：內(nèi)層交叉和變異的作用是搜索最優(yōu)場(chǎng)橋任務(wù)調(diào)度策略，交叉操作方法是在種群中隨機(jī)選擇兩個(gè)染色體中第二行相同基因片段交換位置，內(nèi)層變異操作方法是隨機(jī)選擇一條染色體并在第二行基因中隨機(jī)選擇兩個(gè)基因位點(diǎn)交換信息。具體操作分別如圖7（a）和圖7（b）所示。外層交叉和變異方式的作用是探索岸橋最佳調(diào)度策略，即在隨機(jī)選定的兩個(gè)父代染色體的第一行基因中隨機(jī)選擇兩個(gè)相同位置的基因片段進(jìn)行交叉操作，其變異規(guī)則與內(nèi)層變異規(guī)則相同，只是操作對(duì)象為第一行基因。具體操作流程分別如圖7（c）和圖7（d）所示。內(nèi)層和外層染色體遺傳算子操作規(guī)則為：每進(jìn)行一次外層染色體交叉和變異操作，對(duì)內(nèi)層所有染色體進(jìn)行一次相同操作。

圖7 染色體交叉和變異操作Fig.7 Chromosome cross and mutation

2.5 染色體的修復(fù)

在交叉和變異過(guò)程中可能出現(xiàn)碼頭各個(gè)設(shè)備作業(yè)量分配不均勻現(xiàn)象。針對(duì)這種情況，提出特定染色體修復(fù)策略：若各場(chǎng)橋作業(yè)分配量不同，則將作業(yè)量最大的場(chǎng)橋任務(wù)序列替換成作業(yè)量最少的場(chǎng)橋任務(wù)序列。

2.6 停止條件

當(dāng)算法運(yùn)行次數(shù)達(dá)到最大迭代次數(shù)時(shí)，算法停止。

3 算例分析

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

以某市自動(dòng)化集裝箱碼頭運(yùn)行情況為例，研究靠港船舶裝卸過(guò)程調(diào)度與配置問(wèn)題。擁有2 088 m海岸線的岸橋作業(yè)區(qū)域有7條作業(yè)車(chē)道，每條作業(yè)車(chē)道寬為4 m，均為雙向車(chē)道，采用單船作業(yè)面模式進(jìn)行作業(yè)；共有185個(gè)縱向緩沖車(chē)道，每車(chē)道寬7 m；在堆場(chǎng)和作業(yè)緩沖區(qū)之間有6條寬4 m的交替反向高速車(chē)道。碼頭整體布局如圖4所示。假設(shè)某次作業(yè)任務(wù)量為322個(gè)裝船集裝箱、182個(gè)卸船集裝箱，集裝箱具體位置已知。碼頭可供調(diào)用設(shè)備包括3臺(tái)岸橋、15輛AGV和4臺(tái)場(chǎng)橋。具體運(yùn)行參數(shù)如表1所示。

表1 設(shè)備運(yùn)行參數(shù)Table 1 Parameter value of equipment

3.2 結(jié)果與討論

利用MATALB R2019a實(shí)現(xiàn)提出的改進(jìn)型遺傳算法并在Intel?CoreTMi5-9500 CPU@3.00 GHz處理器及RAM 8.00 GB電腦上運(yùn)行。算法相關(guān)參數(shù)設(shè)置如下：（1）外層，種群規(guī)模為20，交叉概率為0.7，變異概率為0.1，最大迭代次數(shù)為50次。（2）內(nèi)層，種群規(guī)模為20，交叉概率為0.7，變異概率為0.07，最大迭代次數(shù)為50。

權(quán)重系數(shù)α直接影響最小化船舶在港時(shí)間和最小化作業(yè)總能耗，為研究權(quán)重系數(shù)對(duì)目標(biāo)函數(shù)值的影響分別將其設(shè)置為0、0.7和1.0。

圖8展示了權(quán)重系數(shù)為0時(shí)平均結(jié)果，從圖中可以發(fā)現(xiàn)總能耗值隨AGV運(yùn)行數(shù)量增加而增加，且這一規(guī)律不受集裝箱碼頭緩沖區(qū)容量限制。表2說(shuō)明AGV利用率隨運(yùn)行數(shù)量增加而降低。由圖8和表2可知，AGV運(yùn)行數(shù)量增加時(shí)，其利用率和能耗表現(xiàn)出相反變化趨勢(shì)的原因是AGV在岸橋和緩沖支架處等待所致，說(shuō)明集裝箱碼頭運(yùn)行系統(tǒng)瓶頸作業(yè)環(huán)節(jié)發(fā)生在非水平運(yùn)輸環(huán)節(jié)。圖8（c）中函數(shù)值顯著高于圖8（a）和圖8（b），說(shuō)明在該任務(wù)下單純擴(kuò)大中轉(zhuǎn)平臺(tái)容量不會(huì)減少碼頭作業(yè)能耗，進(jìn)一步證實(shí)了單純改善非瓶頸作業(yè)環(huán)節(jié)不會(huì)優(yōu)化系統(tǒng)整體運(yùn)行效率。

圖8 不同參數(shù)下能耗值變化情況Fig.8 Energy consumption under different parameters

表2 AGV利用率隨中轉(zhuǎn)平臺(tái)容量變化波動(dòng)情況（權(quán)重為0）Table 2 AGV utilization with respect to platform slots capacity（weight of 0）

當(dāng)α=0.7時(shí)，目標(biāo)函數(shù)改為式（58），經(jīng)過(guò)運(yùn)算得到目標(biāo)函數(shù)值隨參數(shù)變化情況（如圖9所示）和AGV利用率隨中轉(zhuǎn)平臺(tái)容量變化情況（如表3所示）。

表3 AGV利用率隨中轉(zhuǎn)平臺(tái)容量變化波動(dòng)情況（權(quán)重為0.7）Table 3 AGV utilization with respect to platform slots capacity（weight of 0.7）

由圖9可知，在考慮多目標(biāo)時(shí)，其目標(biāo)函數(shù)值隨AGV運(yùn)行數(shù)量增加呈現(xiàn)出梯度遞減趨勢(shì)，且該規(guī)律不受中轉(zhuǎn)平臺(tái)容量影響，說(shuō)明在特定任務(wù)規(guī)模下自動(dòng)化集裝箱碼頭AGV運(yùn)行數(shù)量對(duì)多目標(biāo)函數(shù)呈現(xiàn)邊際效益遞減趨勢(shì)。在多目標(biāo)條件下緩沖區(qū)容量等限制對(duì)碼頭運(yùn)行系統(tǒng)約束能力有限，說(shuō)明自動(dòng)化集裝箱碼頭AGV運(yùn)行數(shù)量是影響多目標(biāo)函數(shù)值的主要因素。這是因?yàn)橄鄬?duì)于岸橋和場(chǎng)橋數(shù)量而言，AGV運(yùn)行數(shù)量較多，不再成為碼頭作業(yè)流程的瓶頸環(huán)節(jié)[29]，使得碼頭運(yùn)行系統(tǒng)松弛了對(duì)AGV運(yùn)行數(shù)量約束；這也是緩沖支架容量不變時(shí)，目標(biāo)函數(shù)值隨運(yùn)行AGV數(shù)量增加而增加的原因。

圖9 不同參數(shù)下目標(biāo)函數(shù)值的變化Fig.9 Objective function under different parameters

由表3可以發(fā)現(xiàn)，AGV利用率雖然會(huì)隨中轉(zhuǎn)平臺(tái)容量變化而有小范圍波動(dòng)，但整體表現(xiàn)出隨運(yùn)行AGV數(shù)量增加而降低的趨勢(shì)，因?yàn)樵谧詣?dòng)化集裝箱碼頭系統(tǒng)中隨著運(yùn)行AGV數(shù)量增加，發(fā)生等待概率隨之增加，降低了AGV利用率。因此，為提高AGV運(yùn)行效率，在保證任務(wù)順利完成前提下，緩沖支架容量和運(yùn)行AGV數(shù)量應(yīng)盡可能少。

當(dāng)α=1.0時(shí)，得出船舶在港時(shí)間隨運(yùn)行AGV數(shù)量和緩沖支架容量變化情況（如圖10所示）和AGV利用率隨中轉(zhuǎn)平臺(tái)容量變化情況（如表4所示）。可以發(fā)現(xiàn)，在該任務(wù)下，船舶在港時(shí)間對(duì)運(yùn)行AGV數(shù)量高度敏感，隨著AGV運(yùn)行數(shù)量增加，船舶在港時(shí)間呈明顯下降趨勢(shì)；緩沖支架容量變化對(duì)船舶在港時(shí)間影響波動(dòng)較小。

由圖10和表4可以發(fā)現(xiàn)，當(dāng)以最小化船舶在港時(shí)間為目標(biāo)函數(shù)時(shí)，為加快岸橋作業(yè)效率，在避免AGV發(fā)生路徑?jīng)_突前提下得出的AGV調(diào)度方案降低了AGV等待現(xiàn)象發(fā)生的概率，縮短了碼頭任務(wù)周期，提高了設(shè)備利用率。

表4 AGV利用率隨中轉(zhuǎn)平臺(tái)容量變化波動(dòng)情況（權(quán)重為1.0）Table 4 AGV utilization with respect to platform slots capacity（weight of 1.0）

圖10 不同參數(shù)下在船舶在港時(shí)間變化情況Fig.10 Vessel’s turnaround time under different parameters

3.3 算法性能分析

本文共設(shè)計(jì)18組不同規(guī)模算例，評(píng)估算法性能。前9組利用FlexTerm仿真軟件模擬某港實(shí)際運(yùn)行效果以檢驗(yàn)結(jié)果有效性（岸橋中轉(zhuǎn)平臺(tái)容量均為2，緩沖支架容量為1，其他參數(shù)和某港實(shí)際運(yùn)行參數(shù)一致），后9組用于驗(yàn)證AGV避免路徑?jīng)_突策略的有效性。將文獻(xiàn)[6]中策略設(shè)置為對(duì)照組（CG），具體參數(shù)和該文獻(xiàn)一致。所求結(jié)果如表5、表6所示（表6中將權(quán)重設(shè)定為0，只考慮不同規(guī)模下碼頭能源消耗情況）。

表5 仿真結(jié)果與算法求解結(jié)果對(duì)比Table 5 Comparison between results of algorithm and simulation

表6 對(duì)照組與本文算法求解結(jié)果對(duì)比Table 6 Comparison between results of algorithm and control group

由表5可知，與仿真結(jié)果相比，所提算法能使碼頭在相同任務(wù)規(guī)模下平均節(jié)能89.79%，且作業(yè)規(guī)模越大節(jié)能優(yōu)勢(shì)越明顯。船舶在港時(shí)間與仿真結(jié)果相比優(yōu)勢(shì)依舊存在。

由表6結(jié)果可知，與文獻(xiàn)[6]策略相比，所提的避免AGV路徑?jīng)_突策略，在節(jié)約能耗方面具有顯著優(yōu)勢(shì)，在相同任務(wù)規(guī)模下平均降低能耗23.76%，從而進(jìn)一步證實(shí)所提避免AGV路徑?jīng)_突策略的有效性。

綜合表5和表6可知，當(dāng)裝卸任務(wù)規(guī)模不同時(shí)，算法求解結(jié)果隨之發(fā)生變化。具體表現(xiàn)為：當(dāng)AGV配置數(shù)量不變時(shí)，碼頭能源消耗量和船舶在港時(shí)間與裝卸任務(wù)規(guī)模呈同向變化關(guān)系；在任務(wù)規(guī)模不變時(shí)，船舶在港時(shí)間和AGV數(shù)量呈反向變化關(guān)系，但系統(tǒng)耦合性的存在導(dǎo)致能源消耗量和AGV數(shù)量之間變化關(guān)系不明確。

3.4 中轉(zhuǎn)平臺(tái)容量分析

本文記錄了緩沖支架容量為1時(shí)AGV裝載時(shí)間隨著中轉(zhuǎn)平臺(tái)容量變化情況，結(jié)果如圖11所示?？梢园l(fā)現(xiàn)當(dāng)中裝平臺(tái)容量設(shè)定為2時(shí)，AGV裝載時(shí)間均為最高。由此可知在不考慮岸橋機(jī)械強(qiáng)度前提下，當(dāng)岸橋中轉(zhuǎn)平臺(tái)容量為2時(shí)，自動(dòng)化集裝箱碼頭可實(shí)現(xiàn)提高AGV利用率的目的。

圖11 中轉(zhuǎn)平臺(tái)容量對(duì)AGV裝載時(shí)間的影響Fig.11 Impact of platform slots capacity on AGV loading time

4 結(jié)束語(yǔ)

本文考慮岸橋中轉(zhuǎn)平臺(tái)容量及緩沖支架容量約束，加入避免AGV路徑?jīng)_突策略，分析了岸橋、AGV和場(chǎng)橋的不同作業(yè)狀態(tài)能耗，建立了以最小化作業(yè)總能耗和船舶在港時(shí)間為目標(biāo)的雙目標(biāo)混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了雙層遺傳算法的求解方法。研究表明：AGV路徑避免沖突策略能夠顯著降低碼頭作業(yè)能耗，提高裝卸效率。集裝箱碼頭緩沖區(qū)容量、AGV運(yùn)行數(shù)量和利用率以及目標(biāo)函數(shù)值四者之間相互影響，在緩沖區(qū)容量不變的情況下，AGV數(shù)量與碼頭能耗值具有同向變化關(guān)系，與AGV利用率及船舶在港時(shí)間具有反向變化關(guān)系。本文沒(méi)有考慮自動(dòng)化集裝箱碼頭堆場(chǎng)翻箱問(wèn)題，所使用求解方法在求解速度方面有待提高。因此，使用更具求解優(yōu)勢(shì)的機(jī)器學(xué)習(xí)算法解決自動(dòng)化碼頭堆場(chǎng)翻箱問(wèn)題是今后需研究的課題。