考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV 聯合配置及調度優化

范厚明 郭振峰 岳麗君 馬夢知

集裝箱船大型化發展對集裝箱碼頭前沿作業提出了更高的要求,一方面要求提高碼頭裝卸效率和服務水平,另一方面要求降低成本并減少能耗,推動集裝箱碼頭綠色低碳發展.以人工操作為主體的集裝箱碼頭因不能及時準確地獲知裝卸全過程信息,導致生產效率降低和能耗增加[1].為了提高碼頭裝卸效率和服務水平,早在1993 年,荷蘭鹿特丹港就開始建設運營自動化集裝箱碼頭,接著倫敦港、川崎港、新加坡港、漢堡港、廈門遠海、上海洋山港等港口相繼建成自動化集裝箱碼頭.經過二十多年的發展,目前自動化碼頭技術已經逐漸成熟和完善,特別是為了適應節能環保要求,已將早期使用的內燃機驅動的設備轉換為電力驅動,岸邊作業采用雙小車岸橋進行船舶裝卸作業,水平運輸采用自動導引車(Automated guided vehicle,AGV),堆場使用自動化軌道吊(Automated rail mounted gantry crane,ARMG),“雙小車岸橋+AGV+ARMG”的裝卸工藝系統被應用于大多數自動化集裝箱碼頭.Sim[2]指出碼頭裝卸作業的能耗在碼頭作業總能耗中占比48.3 %,聯合優化雙小車岸橋與AGV 的配置及調度以減少碼頭裝卸作業的能耗,對集裝箱碼頭實現綠色低碳發展有重要意義.

已有學者對集裝箱碼頭裝卸作業能耗、岸橋和AGV 的配置和調度等問題展開了研究.鄭松等[3]將碼頭系統的管理和控制過程通過平行系統融合在一起,以實現對港機設備的最優控制.He 等[4]指出岸橋和AGV 的配置和調度是裝卸作業過程中兩個密切相連的生產決策問題,岸橋的配置和調度決定船舶作業時間,AGV 的配置和調度影響岸橋和ARMG的取/放箱時間,聯合優化裝卸設備的配置和調度,降低自動化集裝箱碼頭裝卸作業過程中的能耗成為研究熱點問題.岸橋把待卸船集裝箱從船上提起放到運輸工具上,又把待裝船集裝箱放到船上,是碼頭裝卸作業中重要的一環,關于減少岸橋作業中能耗的問題,部分學者從資源配置的角度出發,研究碼頭現有泊位和岸橋的分配方案.例如,Chang 等[5]研究了一種泊位岸橋調度策略,并通過實例分析驗證了策略的有效性和可靠性.He[6]以最小化船舶延誤和最小化作業能耗為目標,構建了泊位分配和岸橋分配問題混合整數優化模型,并基于集成仿真的優化方法探索解空間.

在已知泊位計劃下優化岸橋在港口所有船舶之間調度以實現裝卸船時間最短的研究方面,Chang 等[7]研究了動態船舶到達條件下岸橋調度問題,提出一種基于動態滾動策略的岸橋調度方法,建立了以最小化港口所有船舶的裝卸作業時間和均衡岸橋作業時間為目標的優化模型,采用遺傳算法求解,得到各個船上集裝箱任務的最佳裝卸順序和完成時間.Zhang 等[8]考慮了裝卸過程中船舶的縱向穩定性,建立了具有穩定性約束的岸橋調度優化模型,引入了一種基于滑動窗的啟發式算法以修復違反穩定性約束的岸橋調度序列,并將模型求解結果與不考慮船舶穩定性的結果進行了比較和分析,驗證了模型和算法的有效性.

部分學者從優化每個集裝箱裝卸作業時間的角度出發,研究了岸橋調度對減少裝卸能耗和裝卸完工時間的作用.Liu 等[9]研究了單船岸橋分配和調度問題,以最小化卸載過程中二氧化碳排放量為目標建立了AGV 排隊模型.Liang 等[10]從岸橋任務調度和數量配置兩個方面研究了岸橋調度問題,通過分析每個任務的最早可作業時刻和要求完工時刻,建立了岸橋調度和配置的耦合模型,并應用循環迭代的方法求解每個時間窗內岸橋配置和調度方案.Msakni 等[11]針對碼頭岸橋調度問題,以單個集裝箱為任務單位,提出了增加割平面和基于圖的二分搜索算法求模型的精確解,并通過對比不同規模任務下的岸橋調度結果,驗證模型和算法的有效性.Kim 等[12]考慮到任務的優先關系和岸橋間安全距離,建立了岸橋調度的混合整數規劃模型,提出了一種基于分支定界的貪婪隨機自適應算法求解該模型.Nguyen 等[13]分別采用遺傳算法和遺傳規劃算法求解岸橋裝卸過程中集裝箱的優先級,使所求得的調度方案能在不確定環境下達到相對穩定的岸橋完工時間.

AGV 在自動化集裝箱碼頭中作為水平運輸工具從岸橋下接收卸船集裝箱送至堆場,在堆場接收待裝船集裝箱送至岸橋.雖然AGV 的能耗只占碼頭作業總能耗的1.04 %,但是它的調度和配置對岸橋和場橋的作業能耗產生很大影響.關于減少AGV作業中能耗的問題,部分學者研究了AGV 的調度策略,Kim 等[14]以減少自動化集裝箱碼頭因船舶作業延誤產生的能耗為目標調度AGV,求解最優的AGV 配置調度方案.Choe 等[15]提出了OnPL (Online preference learning)算法,通過更新偏好函數動態地調整AGV 的調度策略.Kim 等[16]研究了多標準調度策略下自動化集裝箱碼頭AGV 調度,基于不同的場景對問題仿真模擬得到AGV 的調度方案.部分學者從岸橋和AGV 協同調度的角度出發,Xin 等[17]將集裝箱碼頭的集裝箱運輸作業看作是由連續時間的低級形態和動態離散事件的高級形態這兩部分組成,提出了一種分層控制結構,在岸橋和AGV 的數量已知的條件下,最小化上層岸橋作業完工時間和下層AGV 的能耗.Peng 等[18]量化了碼頭作業中設備的配置對總碳排放量的影響,建立了基于復雜排隊網絡的仿真模型,優化岸橋、場橋和AGV 的配比.Yang 等[19]基于混合流水車間調度問題(HFSS),以最小化總作業時間和最小能耗為目標,提出并求解了岸橋、內集卡和場橋裝卸作業的雙目標聯合優化模型.Dkhil 等[20]針對自動化集裝箱碼頭岸橋、AGV 和場橋的作業問題,提出了以最小化岸橋完工時間和最小化AGV 配置數量為目標的優化模型,并采用Cplex 求解.Yang 等[21]研究了同時裝卸作業的岸橋、場橋和AGV 的集成調度,設計了基于預防性擁塞規則的通用算法模擬處理自動化集裝箱碼頭裝卸作業.

部分學者考慮了AGV 運輸過程中的不確定環境的影響,Singgih 等[22]研究了自動化集裝箱碼頭AGV 運輸路徑規劃問題,考慮了AGV 在運輸過程中因交通擁堵導致的等待時間,以最小化運輸時間和等待時間為目標構建整數規劃模型,應用改進Dijkstra 算法求解.Legato 等[23]考慮岸橋裝卸效率不恒定時岸橋和車輛的調度問題,以最小化岸橋等待時間和AGV 路徑沖突導致的擁堵時間為目標構建優化模型,采用模擬退火算法求解模型,并通過仿真實驗確定適用于實例的算法參數.Xin 等[24]提出了一種無沖突調度算法,用于生成AGV 的無碰撞軌跡及岸橋、場橋的時刻表,降低AGV 運行的平均距離.

從現有研究中可以看出,岸橋裝卸作業中產生的能耗在碼頭作業總能耗中占較大比重,AGV 到達岸橋下的時間影響岸橋裝卸作業能耗.已有關于減少碼頭裝卸作業能耗的研究中:1)多以最小化作業岸橋的完工時間為目標,沒有考慮要求船舶在港總裝卸時間對岸橋配置的影響.實際調度過程中需要在保證所有車輛準時到達岸橋下的前提下,規劃出能耗最低的運輸方案[25].2)大多針對卸船階段或裝卸同步階段下岸橋和AGV 的調度,忽略了裝卸作業的各個階段的聯系.3)為了避免岸橋延遲給碼頭帶來的損失,AGV 的配置數量較多,增加了不必要的運輸能耗,AGV 的利用率較低.4)在AGV 調度過程中忽略了可續航時間對調度的影響,不符合實際碼頭作業情況,現實中AGV 在耗盡電量前需駛往換電站更換電池或充電,此過程中AGV 不可使用.5)缺乏對緩沖區的研究,雙小車岸橋的緩沖平臺可以減少岸橋和AGV 相互等待能耗,堆場的緩沖區可以減少AGV 在堆場的等待能耗.因此,本文對考慮能耗節約的雙小車岸橋與AGV 聯合配置及調度問題進行研究,保證岸橋主小車不延誤等待,在運輸過程中AGV 續航時間、雙小車岸橋中轉平臺容量和堆場緩沖支架容量約束下,研究雙小車岸橋與AGV 聯合配置及調度優化問題具有重要的理論與實際價值.

本文架構如下:1) 模型建立,該部分構建了考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV 聯合配置及調度優化模型.2) 模型求解,該部分進行了算法設計,分別應用枚舉算法和遺傳算法求解岸橋調度的最優解并AGV 調度的滿意解.3) 算例分析,該部分采用實例驗證了模型及其算法的有效性.4) 結論,該部分總結了研究成果并提出了未來研究方向.

1 模型建立

1.1 問題描述

集裝箱船在特定泊位靠港后,碼頭根據要求的船舶在港總裝卸時間和船舶配積載信息配置及調度岸橋和AGV.雙小車岸橋因具有中轉平臺可以減少岸橋和AGV 相互等待時間而被廣泛應用于自動化集裝箱碼頭,如圖1 所示.

圖1 雙小車岸橋示意圖Fig.1 The dual-trolley quay crane

在岸橋裝船過程中,AGV 從箱區的緩沖支架上取裝船集裝箱至岸橋的門架小車下方,岸橋門架小車將集裝箱從AGV 上抓起放至中轉平臺,岸橋主小車空閑時再將中轉平臺上的集裝箱吊起裝至船上;岸橋卸船過程中,主小車放卸船箱到中轉平臺,門架小車從中轉平臺取箱放至AGV,由其運送到該箱所在箱區,待箱區的緩沖支架空閑時將集裝箱放到緩沖支架上.多個岸橋同時進行裝卸作業有利于加快船舶裝卸速度,但由于岸橋不可跨越且兩兩之間需要保持安全距離,配置過多岸橋會產生相互干擾而引起的額外等待時間,不僅會影響船舶在港裝卸作業時間,也會增加碼頭作業能耗.

在裝卸船過程中,AGV 的配置和調度方案影響岸橋實際完工時間,配置數量過少可能會出現岸橋主小車等待AGV,導致岸橋作業延誤,影響完工時間.調度方案不合理使得運輸過程中岸橋門架小車等待AGV、AGV 空載和等待能耗增加.如圖2所示,空載AGV 在箱區6 接收裝船集裝箱后,根據集裝箱所屬船貝信息,前往岸橋C 下交付集裝箱.交箱后的AGV 可調往堆場箱區(路線2)作業下一個裝船任務,也可調往岸橋B (路線3) 或岸橋A(路線4)作業下一個卸船任務.根據岸橋調度方案制定合理的AGV 配置和調度方案,能保證岸橋主小車不延誤的同時,減少岸橋門架小車等待AGV的能耗、AGV 在岸橋和場橋下的等待能耗、AGV的載箱能耗和空載能耗.

圖2 碼頭布局和AGV 運輸流程示意圖Fig.2 Automated container terminal layout and AGV transportation process

本文分兩階段研究單船作業面模式下雙小車岸橋和AGV 的聯合配置和調度問題.第一階段根據待裝卸集裝箱數量和位置配置岸橋,位于同一貝位的甲板箱或艙內箱的所有裝或卸作業稱為一個任務,同一貝位中岸橋作業的先后順序為先卸甲板箱再卸艙內箱,先裝艙內箱再裝甲板箱.如圖3 所示,待裝卸集裝箱分布在6 個不同的貝位,貝位編號為1 的32 個集裝箱的卸船作業為任務1,自左向右按先卸船再裝船的順序依次編號,可知岸橋的總裝卸任務量為24,如圖4 所示.第二階段根據所有作業該船的岸橋主小車和門架小車的計劃作業時間調度和配置AGV,調度過程中一個集裝箱為一個作業單元,并考慮AGV 續航能力和往返換電站運輸時間的約束.由于岸橋延遲會產生較高損失,所以AGV 調度過程中需要保證AGV 到達時間不會使岸橋主小車等待.

圖3 待裝卸集裝箱分布示意圖Fig.3 Containers to be loaded and unloaded

圖4 岸橋任務編號示意圖Fig.4 Task number of quay crane

本文研究基于以下假設:1)所有岸橋在同一軌道上移動且作業效率、油耗等性能相同或服從同一分布類型;2)岸橋從編號小的船貝到編號大的船貝順序移動作業,完成所分配的卸船任務后再從編號小的船貝到編號大的船貝開始裝船作業;3)不考慮AGV 運輸過程中的路徑沖突等不確定因素;4)箱區下均設有緩沖支架,每個箱區有且僅有一臺ARMG,所有ARMG 的工作能力、油耗等性能相同;5)所有集裝箱的箱型一致,所有AGV 的行駛速度、油耗等性能相同或服從同一分布類型.

1.2 第一階段岸橋的配置與調度優化模型

第一階段是為各岸橋分配裝卸任務并安排作業的先后順序,以在規定的船舶總裝卸時間內完成對所有任務的裝卸作業,優化的目標是岸橋能耗最小.

1)集合、參數及狀態變量

i:任務編號,i=1,2···,I;

k:岸橋編號,k=1,2···,K;

b:船舶貝位編號,b=1,2···,B;

Ni:任務i中待裝卸的集裝箱數量;

li:任務i所在貝位位置;

lSk:岸橋k開始作業時刻所在的貝位位置;

lFk:岸橋k完工時刻所在的貝位位置;

lsaf:安全貝位距離;

ψ:不能同時作業的任務集合,ψ={(i,j)|i,j ∈I,|:lj?li|≤lsaf};

τ1:岸橋沿船舶縱向移動一個貝位所需時間;

τ2:岸橋主小車完成一次取/放箱作業所需時間;

C1:每臺岸橋單位時間的作業能耗;

C2:每臺岸橋單位時間的移動能耗;

C3:每臺岸橋單位時間的等待能耗;

tF:船舶在港總裝卸時間;

ti:任務i的作業時間;

Tik:岸橋k:裝卸完任務i內所有集裝箱的完工時刻;

tij:岸橋完成當前任務i:后開始任務j前因其他岸橋干擾需等待的時間;

2)決策變量

xik:岸橋k:作業任務i時為1,否則為0;

zijk:岸橋k:作業完任務i:后作業任務j時為1,否則為0;

3)數學模型

目標函數:

約束條件:

式(1)為目標函數,表示總能耗最小化,總能耗包括岸橋作業能耗、岸橋移動能耗和干擾造成的等待能耗;式(2)表示每個任務只能且必須分配一個岸橋為其作業;式(3)和式(4)表示每個岸橋有且僅有一個開始任務和一個結束任務;式(5)表示每個任務均有且僅有一個緊前任務和緊后任務;式(6)任務i的作業時間;式(7)表示岸橋總完工時間小于船舶在港總裝卸時間;式(8)表示若任務i和任務j不能同時被作業,則岸橋k完成任務i并移動到安全距離后,下一個岸橋才能開始作業任務j,即船舶裝卸過程中,岸橋間始終保持安全距離;式(9)表示岸橋k上一個任務的完成時刻與下一個任務的完成時刻之間的關系;式(10)和(11)定義了變量類型及取值范圍.

1.3 第二階段AGV 的配置與調度優化模型

第二階段是為各AGV 分配裝卸任務并安排作業的先后順序,以保證每個岸橋主小車不延遲,優化的目標為AGV 的作業總能耗最小.

1)集合、參數及狀態變量

L:裝船集裝箱集合;

D:卸船集裝箱的集合;

n:集裝箱編號,n=1,2,···,N;

a:AGV 編號,a=1,2,···,A;

c:場橋編號,c=1,2,···,C;

Tnc:場橋c:作業集裝箱n的時刻,即在緩沖支架取 裝船集裝箱n的時刻或放卸船集裝箱n到緩沖 支架上的時刻;

Tna:第a:輛AGV 在箱區/岸橋下開始作業集裝箱n的時刻;

tna:第a:輛AGV 從箱區(岸橋下)出發將集裝箱n運輸到岸橋下(箱區)所用的時間;

tnn′:AGV 交付集裝箱n后前往下一個集裝箱所在 位置的空駛時間;

wnka:運載集裝箱n:的第a:輛AGV 在岸橋k下的等待時間;

wnca:運載集裝箱n:的第a:輛AGV 在場橋c下的等待時間;

C4:岸橋的門架小車等AGV 時單位時間的等待 能耗;

C5:每輛AGV 單位時間載箱移動能耗;

C6:每輛AGV 單位時間的空載移動能耗;

C7:每輛AGV 在岸橋或場橋下單位時間的等待 能耗;

p1:雙小車岸橋中轉平臺的容量;

p2:每個箱區緩沖支架的容量,即每個箱區的緩沖 支架上可以同時放置集裝箱的數量;

τ3:岸橋的門架小車完成一次取/放箱作業所需要 的平均時間;

τ4:場橋完成一次取/放箱作業所需要的平均時間;

τ5:AGV 往返充電站所需時間;

v1:AGV 載箱行駛速度;

v0:AGV 空載行駛速度;

2)決策變量

yna:集裝箱n:被分配給車a時等于1,否則等于0;

znn′a:第a:輛AGV 運輸完集裝箱n后去運輸下一個集裝箱n′時等于1,否則等于0;

una:當車a:運輸完集裝箱n后剩余電量小于安全電 量時等于1,否則等于0;

3)數學模型

目標函數:

約束條件:

式(12)為目標函數表示AGV 運輸過程的能耗最小化,即門架小車等待AGV 的能耗、AGV 的載箱能耗、AGV 的空載能耗、AGV 在岸橋和場橋下等待能耗之和最小化;式(13)表示一個集裝箱由且僅由一輛AGV 運輸;式(14)和式(15)表示每個AGV 有且僅有一個開始任務和一個結束任務;式(16)表示岸橋主小車的實際作業時刻不晚于計劃作業時刻,即保證岸橋主小車不延誤;式(17)和式(18)分別表示岸橋門架小車放下裝船集裝箱到中轉平臺或從平臺取卸船集裝箱的時間窗;式(19)和式(20)分別表示岸橋門架小車裝船或卸船時在中轉平臺的實際作業時刻應滿足時間窗約束;式(21)和式(22)分別表示作業裝船集裝箱n或卸船集裝箱n時,岸橋門架小車實際作業時刻與AGV 到達時刻的關系;式(23)表示更新后的門架小車計劃作業時刻;式(24)和式(25)分別表示AGV 運輸裝船箱或卸船箱時在緩沖支架的實際作業時刻應滿足時間窗約束;式(26)和式(27)分別表示AGV 在場橋c下取裝船箱或放卸船箱時滿足時間窗約束;式(28)和式(29)分別表示AGV 交付裝船集裝箱n或提取卸船集裝箱n時在岸橋門架小車下的等待時間;式(30)和(31)分別表示AGV 提取裝船集裝箱n或交付卸船集裝箱n時在場橋下的等待時間;式(32)和式(33)分別表示AGV 在送完裝船集裝箱n后,開始作業下一個裝船集裝箱或卸船集裝箱的時間約束;式(34)和式(35)分別表示AGV 在送完卸船集裝箱n后,開始作業下一個裝船集裝箱或卸船集裝箱的時間約束;式(36)表示AGV 的利用率,即載箱能耗和空載能耗在總能耗中的占比;式(37)和式(38)分別表示參數的類型和取值范圍.

2 模型求解

2.1 第一階段模型求解

第一階段模型研究岸橋的配置和調度問題,考慮任務優先級和岸橋間安全距離的約束將待裝卸任務分配給各個岸橋.該模型的求解結果直接影響第二階段AGV 的調度和配置,需設計一種算法求第一階段模型精確的最優解.又因Lee[26]證明了考慮岸橋間安全距離的岸橋調度問題屬于NP 完全問題,無法在多項式時間內解決大規模問題,故需設計一種策略減少計算量.本文采用枚舉算法(Enumeration algorithm,EA)求模型的最優解,為減少計算量,將位于同一貝位的甲板箱或艙內箱的所有裝或卸作業視為一個任務,第一個岸橋的起始點位置和最后一個岸橋的終點位置視為已知,岸橋k的終點視為岸橋k+1 的起點,岸橋之間不可跨越,故可將問題簡化為在任務集合I中為k個岸橋選擇2(k?1)個始終點.算法復雜度為 O(n2k?2),具體步驟如下:

1)將所有任務按裝卸作業的先后順序排列.岸橋裝卸順序為:同一岸橋,裝/卸船任務中編號較小的貝位早于編號較大的貝位,卸船任務早于裝船任務;同一貝位,卸船時甲板箱早于艙內箱,裝船時艙內箱早于甲板箱.

2)尋找不同岸橋配置方案下的最優調度方案.考慮到岸橋的不可跨越性和岸橋間的安全距離,列出不同配置方案中所有滿足約束的岸橋調度方案,并計算其目標函數值,目標值最小的調度方案即為該岸橋配置方案下的最優調度方案.

3)確定最優的岸橋配置與調度方案.在滿足船舶在港總裝卸時間的前提下,比較不同岸橋配置數量下的最優目標值,即可得到岸橋調度與配置的最優解.

2.2 第二階段模型求解

由于第二階段優化AGV 運行能耗的同時考慮了AGV 的充電時間和岸橋中轉平臺、場橋下緩沖支架的容量約束,這增加了問題的非線性,使得模型變得異常復雜,無法使用CPLEX 等軟件求解.本文根據問題特點改進遺傳算法對模型求解,具體步驟如下:

1)解的編碼

采用矩陣編碼的方式,設計一個兩行的染色體,染色體的長度為待裝卸集裝箱數量,染色體第一行的基因值表示集裝箱作業序號,第二行的基因值表示為每個集裝箱分配的AGV.由配積載圖和第一階段岸橋分配結果,可知每個集裝箱的作業岸橋序號、場橋序號.假設某一時刻3 臺岸橋同時裝卸集裝箱,6 輛AGV 參與運輸集裝箱,其中作業順序為27 的集裝箱,由序號為7 的場橋和序號為2 的岸橋作業,并分配給序號為1 的AGV 運輸,則染色體如圖5 所示:

圖5 染色體示意圖Fig.5 The chromosome

2)生成初始種群

在式(13)～(15)的約束下生成一定數量的個體,其中每個個體的任務序列和AGV 作業量利用隨機數生成,所有的個體構成初始種群.

3)評價與選擇

根據每個個體的基因值,計算目標函數值,具體過程如下:

1)由式(17)～(20)計算岸橋k的門架小車計劃提/放集裝箱n的時間窗,由式(24)～(27)計算AGV 在場橋c下計劃提/放集裝箱n的時間窗

2)對于裝船集裝箱n,若空載AGV 到達時間早于場橋最早放箱時間,則在場橋下等待;若AGV 到達時間晚于,表示箱區內的緩沖支架已全被占用,則場橋需要等待AGV;否則,AGV 將從緩沖支架提箱前往岸橋k下;若重載AGV 到達時間早于,則在岸橋下等待;若AGV 到達時間晚于,則岸橋的主小車和門架小車均需等待AGV;若AGV 在時間窗內到達,則岸橋的門架小車等待,由式(22)和(23)更新;否則,AGV 交付集裝箱n后前往服務下一集裝箱n′.

3)對于卸船集裝箱n,若空載AGV 到達時間早于岸橋k的門架小車最早放箱時間,則在場橋下等待;若AGV 到達時間晚于,則岸橋的主小車和門架小車均需等待AGV;AGV 在時間窗內到達,則岸橋的門架小車等待,由式(22)和(23)更新,AGV 將從岸橋的門架小車下提箱前往場橋c下;若重載AGV到達時間早于,則在場橋下等待;若AGV 到達時間晚于,則場橋需要等待AGV;否則,AGV交付集裝箱n后前往服務下一集裝箱n′.

目標函數計算流程如圖6 所示.因為岸橋主小車和場橋的延遲會給碼頭作業帶來較大的損失,故設岸橋主小車和場橋的延遲能耗為無窮大.本文模型以最小化能耗為目標,設目標函數的倒數為適應度值.

圖6 目標函數求解流程圖Fig.6 Solution flowchart

4)交叉與變異

為提高算法的局部搜索能力,保證種群的多樣性與質量,根據問題特征設計了交叉和變異方式,如圖7 所示.將種群中所有個體分組,隨機選擇8個個體為一組,種群中適應度最高的個體為全局最優解,每組中適應度最高的個體為局部最優解,局部最優解直接保留至下一代.采用兩點交叉算子對染色體全局最優解和局部最優解進行交叉操作,隨機生成交叉點位,交叉操作可產生4 個新個體,具體變化方式見圖7(a).采用基因倒置、基因互換和更新斷點的方式對局部最優染色體變異,產生其余三個新個體,變異操作具體變化方式見圖7(b)、(c)和(d),每代的交叉變異操作均可產生新的個體.

圖7 交叉和變異Fig.7 Crossover and variation

5)不滿足約束個體的處理

在基因變異的過程中,導致岸橋主小車和場橋作業延誤的個體序列,其延誤能耗設為無窮大,則該個體的適應度值為無窮小,不會遺傳到下一代.

6)終止規則

當算法的迭代次數達到最大值時,算法終止.

3 算例分析

3.1 算例描述

本文以上海洋山港自動化集裝箱碼頭為例,研究某靠港船舶裝卸作業過程.碼頭整體布局和水平運輸交通規則見圖2.AGV 所在的QC 作業區共7條行車道,每條車道寬4 m,其中4 條為裝卸車道,3 條為穿越車道,裝卸車道成對布置,并與穿越車道相間隔.緩沖車道縱向27 m,可雙向行駛,堆場行駛區共有8 條雙向車道,且相鄰車道行駛方向相反;箱區之間的距離為35 米.AGV 更換電池一次可續航480 分鐘.

船上集裝箱的位置分布[26]如圖8 所示,共20個待裝卸貝位.碼頭裝卸作業采用“雙小車岸橋＋AGV＋ARMG”的生產方案,岸橋、AGV 的運輸速度及作業能耗等相關參數[27?28]見表1.堆場有9 個箱區用于堆放待卸船集裝箱和待裝船集裝箱.雙小車岸橋中轉平臺的容量為2,兩岸橋安全作業間距設為1 貝位.每個箱區下緩沖支架的容量為4.

表1 設備參數取值Table 1 Equipment parameter value

圖8 待裝卸集裝箱船Fig.8 The ship of containers to be loaded and unloaded

3.2 算例求解及結果分析

1)第一階段岸橋調度與配置優化結果

采用Matlab 2016 進行編程求解,設船舶在港總裝卸時間為44 小時,則碼頭需要配置和調度岸橋以在44 小時內完成所有的裝卸作業.岸橋配置數量為2 時,如表2 所示,最小完工時間為4 709 min,不能在要求的時間內完工;岸橋配置數量為3 和4 時,岸橋的完工時間、作業能耗,每臺岸橋的調度方案、開始和完工時間的詳細求解結果如表 2 所示,配置3 臺岸橋的能耗接近于配置2 臺岸橋,但可以在規定時間內完成裝卸作業,配置4 臺岸橋的能耗和時間均高于配置3 臺岸橋,表明岸橋數量過多時岸橋之間存在干擾等待現象,增加了額外的作業時間和作業能耗.所以最優岸橋配置數量為3 臺,最小岸橋作業能耗為11 505 kw·h,完工時間為2 605 min.該配置方案下最優的調度方案為:卸船作業時,岸橋1 卸貝 1～3、岸橋2 卸貝 3～10、岸橋3 卸貝 11～20;裝船作業時,岸橋1 裝貝位1～13、岸橋2 裝貝位14～18、岸橋3 裝貝位19～20.在此過程中,岸橋1 在第640 min 結束卸船作業開始裝船,岸橋3 在第2 323 min 時才結束卸船作業,裝卸同步作業時間達1 683 min,有利于減少AGV 的空載能耗.岸橋在貝位間的實時行走路徑如圖9 所示.由圖9 可知岸橋作業路線無交點,且任意時刻保持安全距離.

圖9 岸橋作業路線圖Fig.9 Path to the dual-trolley quay cranes

表2 岸橋調度方案比較Table 2 Comparison of dual-trolley quay crane scheduling schemes

2)第二階段AGV 調度與配置優化結果

第二階段要為以上3 769 個待裝卸集裝箱分配AGV,基于第一階段岸橋調度優化的求解結果,采用Matlab 編程求解不同AGV 配置方案下的調度方案,種群大小設為120,最大迭代次數為1 500次.可得最優解為配置7 輛AGV,AGV 運行總能耗為3 857 kw·h,AGV 利用率為55.5 %.AGV 調度方案如表3 所示.

表3 AGV 調度結果Table 3 The scheduling results of AGV

3)結果分析與對比

為了驗證本文設計的第二階段算法和模型的有效性,基于混合流水線調度問題計算裝卸完工時間的理論下界值[29].計算公式為:

調度過程中不改變AGV 的配置方案,因此AGV 的總運行時間至少為×K,由此可知:

其中,f2表示第二階段的AGV 作業能耗的下界值,即重載能耗、空載能耗和等待能耗之和.隨機生成圖8 所示集裝箱船上各個貝位內待裝卸集裝箱的數量,得到8 組不同規模的算例,其他參數設置不變,將每組算例的程序運行10 次計算結果的平均值,將本文改進遺傳算法、傳統遺傳算法得到的目標函數值,與基于混合流水線調度問題計算的理論下界值進行比較,結果如表4 所示.

表4 中,f1和A1分別表示采用本文改進遺傳算法所得目標函數值和AGV 配置數量;和A2分別表示傳統遺傳算法所得目標函數值和AGV 配置數量.GAP1=(f2?)/f2,GAP2=(f2??)/f2?,分別表示本文算法與傳統遺傳算法所得結果與下界值的差距.由表4 可知,本文算法所得滿意解優于傳統算法,在問題規模較大的情況下,本文算法性能較好.

表4 平均計算結果與下界的比較Table 4 Comparison of average calculation results with lower boundary

為了進一步驗證本文調度策略的優越性,對不同船舶在港總裝卸時間下岸橋的配置及調度、不同AGV 配置原則下AGV 的配置及調度進行實驗,實驗中相關參數不變,改變船舶在港總裝卸時間和AGV 的配置原則,其中,AGV 配置原則一為AGV作業能耗最小,AGV 配置原則二為AGV 配置數量最少,AGV 配置原則三為按1:3 的比例配置岸橋和AGV[30].實驗結果如表5 所示.

從表5 可以看出,船舶在港總裝卸時間影響岸橋的配置和調度,對比實驗9 和實驗10 可知,在港總裝卸時間越短,為滿足要求需要配置岸橋數量越多;對比實驗9 和實驗10,實驗11、12 和實驗13 可知,岸橋配置數量相同的條件下,在港總裝卸時間越短作業能耗越高.

從圖10 可以看出,岸橋調度方案已知的條件下,采用不同的AGV 配置原則會產生不同的作業能耗,AGV 的利用率也不同.按1:3 的比例配置岸橋和AGV (原則三)在產生很高作業能耗的同時降低了AGV 的利用率,在實驗9、10 中AGV 配置數量為9,實驗11、12 和13 中AGV 配置數量為12 時,AGV 利用率均偏低;以最小化配置數量為原則調度AGV (原則二)時,在雙小車岸橋的中轉平臺和堆場緩沖支架的解耦作用下,實驗4 中的岸橋和AGV 的配置比例升至1:1.75 時仍能保證岸橋作業不延遲.雖然不存在岸橋主小車等待AGV 的現象,但門架小車等待時間較長導致作業能耗較高,AGV 利用率偏低;以最小化作業能耗為目標考慮岸橋和AGV 的聯合調度(原則一),可在岸橋不延遲的條件下,優化AGV 的調度作業使其利用率最大,就實驗10 而言,采用此配置原則較原則二、三可分別為碼頭縮減4.5 %和8.08 %的AGV 運行能耗.

圖10 不同AGV 配置數量下各實驗的AGV 利用率Fig.10 AGV utilization rate of each experiment under different configurations

3.3 隨機因素對結果影響分析

在實際生產調度過程中,裝卸調度系統的性能受諸多隨機因素影響.如,不同堆存位置的集裝箱,岸橋作業時間不同;AGV 在充電站的排隊時間影響其往返時間;AGV 送取箱過程中速度變化使得其到達目的地的時間變化.以上隨機因素可能會導致岸橋主小車延誤,影響完工時間.本文分別圍繞每個集裝箱的岸橋作業時間、AGV 往返充電站的時間、AGV 的運行速度這三類隨機性因素展開實驗,實驗設計如表6 所示.

表6 考慮隨機因素影響的實驗設計Table 6 Experimental design considering the influence of random factors

在各個實驗中分別計算不同配置方案岸橋主小車的延遲時間Del、AGV 的利用率ρ和運輸總能耗,其中=f2+C3×Dle.根據實驗輸出數據,分析某一因素的隨機性對調度系統性能產生的影響.實驗結果如表7 所示.

由表7 可知,每個集裝箱的岸橋作業時間、AGV 往返充電站的時間和AGV 的運行速度三種隨機因素均對AGV 的配置和調度結果產生了影響.比較實驗14 和15 可知,同樣的AGV 配置數量下,每個集裝箱的岸橋作業時間服從泊松分布時,較于岸橋作業時間確定的實驗,更可能使得岸橋主小車延遲,通過增加AGV 的配置數量,可以減小這類隨機因素的影響.比較實驗15 和16 可知,AGV往返充電站時間服從均值為負指數分布時,較于充電時間確定的實驗,岸橋主小車延遲時間更長.比較實驗16 和17 可知,AGV 的空載速度、重載速度服從正態分布時,較于速度確定的實驗,可能產生較長的岸橋主小車延遲,但增加AGV 配置數量會使其利用率降低,卻不能消除岸橋延遲.

表7 考慮隨機因素影響的實驗結果Table 7 Experimental results considering the influence of random factors

當確定性集裝箱碼頭配置與調度系統中某一參數發生隨機性變化時,往往會產生岸橋主小車延遲,可能導致船舶在港總裝卸作業時間增加.但AGV配置數量和調度方案的改變可能會減小隨機性帶來的影響,提高系統性能.

4 結論

本文對集裝箱碼頭雙小車岸橋與AGV 聯合配置及調度問題進行的研究中,考慮了雙小車岸橋中轉平臺約束和箱區緩沖支架容量約束、AGV 在運輸過程中續航時間的約束;以岸橋的能耗最小為第一階段模型的優化目標,以AGV 運輸過程的能耗最小為第二階段目標建立兩階段優化模型,采用EA 算法求解岸橋主小車的作業時間;在確保岸橋主小車作業不延誤前提下,改進遺傳算法確定AGV的最優作業序列;在此基礎上,針對不同的要求船舶在港總裝卸時間和不同AGV 配置原則下的岸橋和AGV 配置和調度方案進行分析和對比,以驗證模型和算法的有效性.本文研究可以得到以下結論:

1)本文所構建的兩階段調度優化模型能有效解決岸橋和AGV 的聯合配置及調度問題,所得岸橋和AGV 的配置和調度方案能保證在船舶在港總裝卸時間內完成所有集裝箱的裝卸作業.

2)船舶在港總裝卸時間影響岸橋的配置調度方案和作業能耗.岸橋的作業效率是一定的,因此要求在港總裝卸時間越短,岸橋的配置數量越多;在相同的岸橋配置方案下,為了保證岸橋不等待,在港總裝卸時間越短,所需的AGV 配置數量越多,AGV 的作業能耗越大.

3)本文研究單船作業面調度模式下,考慮雙小車岸橋緩沖平臺和箱區緩沖支架的解耦作用以及AGV 續航時間約束下的岸橋和AGV 的配置與調度,所得岸橋和AGV 的最優配置比例約為1:2.33,小于文獻[30]的研究中仿真所得最優比例1:3.在岸橋的緩沖平臺和箱區緩沖支架的作用下,針對上海洋山港的碼頭布局及現有岸橋的作業效率和AGV 的運行速度來看,若不考慮不確定環境及其它影響因素,岸橋和AGV 的配置比例降為1:1.75時仍可保證岸橋主小車不延遲,但因AGV數量較少導致門架小車和場橋等待能耗增加,故不一定能保證碼頭整體裝卸作業能耗最低.

本文的研究較符合實際自動化集裝箱碼頭船舶裝卸過程,但本文還存在一些不足,未考慮裝卸過程中不確定因素,而實際作業過程中岸橋和AGV的故障、AGV 行駛中路徑沖突和路徑擁堵等不確定情況會影響集裝箱的作業時間.因此,考慮不確定因素下的岸橋和AGV 聯合調度問題將作為未來的研究方向.