考慮作業(yè)狀態(tài)能耗的集裝箱碼頭設(shè)備協(xié)調(diào)調(diào)度

代江濤，韓曉龍

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

交通運(yùn)輸產(chǎn)生的大量二氧化碳是全球環(huán)境的重大威脅，交通運(yùn)輸?shù)哪茉聪膯?wèn)題需要妥善處理。集裝箱碼頭作為航運(yùn)與陸運(yùn)交通的樞紐，是交通產(chǎn)業(yè)的重要構(gòu)成部分，降低集裝箱碼頭能源消耗，推進(jìn)建設(shè)綠色港口正逐漸得到重視。集裝箱碼頭的裝卸設(shè)備主要包括：岸橋（QC）、場(chǎng)橋（YC）、集卡（IT）。由于集裝箱碼頭的各作業(yè)環(huán)節(jié)相互耦合，實(shí)現(xiàn)各設(shè)備的協(xié)調(diào)調(diào)度對(duì)于提高集裝箱碼頭的服務(wù)水平以及降低其能源消耗尤其重要。

當(dāng)前國(guó)內(nèi)外對(duì)于集裝箱碼頭各設(shè)備的調(diào)度問(wèn)題已有較多研究。關(guān)于兩種設(shè)備的調(diào)度問(wèn)題，Cao 等[1]研究進(jìn)口集裝箱作業(yè)中集卡與QC的調(diào)度，構(gòu)建了混合整數(shù)規(guī)劃模型，并且用遺傳算法和基于約翰遜規(guī)則的啟發(fā)式算法進(jìn)行求解，求解的精度得到提高；韓曉龍等[2]考慮集卡的動(dòng)態(tài)性到達(dá)以及作業(yè)時(shí)間的不確定性，構(gòu)建集卡與QC的協(xié)同調(diào)度模型，并且使用CHC算法（Cross generation Heterogeneous recombination Cataclysmic mutation，跨時(shí)代異物種重組大變異算法）進(jìn)行求解；梁承姬等[3]考慮集裝箱優(yōu)先級(jí)及岸橋干擾等約束，構(gòu)建以最小化最大完工時(shí)間為目標(biāo)的數(shù)學(xué)模型，對(duì)比粒子群算法和遺傳算法后得到遺傳算法更具有效性的結(jié)論；盧毅勤等[4]考慮了YC和內(nèi)集卡作業(yè)時(shí)的不確定性因素，建立堆場(chǎng)設(shè)備集成調(diào)度的優(yōu)化模型，并設(shè)計(jì)了粒子群算法進(jìn)行求解；楊勇生等[5]考慮了RMG（Rail Mounted Gantry，軌道式龍門吊）和AGV的任務(wù)分配約束，并以最小化卸船作業(yè)完工時(shí)間為目標(biāo)建立了RMG和AGV的協(xié)同調(diào)度模型；梁承姬等[6]針對(duì)AGV和雙小車岸橋的協(xié)同調(diào)度問(wèn)題，設(shè)計(jì)了啟發(fā)式算法和遺傳算法求解所建立的以總完工時(shí)間最小為目標(biāo)的混合整數(shù)規(guī)劃模型；陳寧等[7]使用基于混合流水車間調(diào)度的方法解決AGV與雙小車岸橋的聯(lián)合調(diào)度，建立以作業(yè)時(shí)間最小為目標(biāo)的三階段混合整數(shù)規(guī)劃模型并使用遺傳算法求解；唐世科等[8]建立了帶有時(shí)間窗約束的AGV與雙小車岸橋的以總完工時(shí)間最小為目標(biāo)的協(xié)調(diào)調(diào)度模型，并使用遺傳算法求解；關(guān)于三種及以上設(shè)備的協(xié)調(diào)調(diào)度，曾慶成等[9]構(gòu)建了QC、集卡以及龍門吊的集成調(diào)度模型，并設(shè)計(jì)了神經(jīng)網(wǎng)絡(luò)算法和模擬退火算法為基礎(chǔ)的混合優(yōu)化算法進(jìn)行求解；Homayouni 等[10]使用遺傳算法對(duì)自動(dòng)化集裝箱碼頭協(xié)同調(diào)度問(wèn)題進(jìn)行求解，比較模擬退火算法得出集裝箱任務(wù)增加時(shí)，遺傳算法的求解效率比模擬退火算法更優(yōu)；吳遠(yuǎn)焰等[11]設(shè)計(jì)了一種改進(jìn)的遺傳算法解決自動(dòng)化碼頭中三種核心設(shè)備的調(diào)度問(wèn)題，通過(guò)不同規(guī)模的數(shù)值仿真以及與CPLEX求解結(jié)果的對(duì)比證明其所設(shè)計(jì)的遺傳算法可以找到高質(zhì)量的近似最優(yōu)解；Lau 等[12]以最小化AGV的總行程時(shí)間、QC的操作延遲時(shí)間和自動(dòng)化場(chǎng)橋（AYC）的總行程時(shí)間為目標(biāo)構(gòu)建了混合整數(shù)規(guī)劃模型，并采用多層遺傳算法和遺傳最大匹配算法進(jìn)行求解；欒晨等[13]抽象雙循環(huán)模式下的QC、AGV 和YC 協(xié)調(diào)調(diào)度問(wèn)題為混合整數(shù)規(guī)劃模型，并使用基于啟發(fā)式的自適應(yīng)遺傳算法求解；Yang等[14]針對(duì)QC、AGV和YC的集成調(diào)度問(wèn)題，設(shè)計(jì)了一種基于預(yù)防性擁塞規(guī)則的通用算法進(jìn)行求解；馬越匯等[15]綜合考慮自動(dòng)化集裝箱碼頭的各種不確定性因素，構(gòu)建了以最小化QC、AGV、龍門吊和堆場(chǎng)作業(yè)最晚結(jié)束時(shí)間為目標(biāo)的模型；秦琴等[16]基于緩沖有限的柔性流水車間調(diào)度理論解決雙小車岸橋、AGV、緩沖支架和自動(dòng)化軌道吊的協(xié)調(diào)調(diào)度問(wèn)題，建立優(yōu)化模型并設(shè)計(jì)初始解由NEH啟發(fā)式算法產(chǎn)生的遺傳算法進(jìn)行求解。

以上關(guān)于集裝箱碼頭各設(shè)備協(xié)調(diào)調(diào)度的研究?jī)H從時(shí)間角度考慮調(diào)度的優(yōu)化，而實(shí)際作業(yè)過(guò)程中能耗因素也是影響作業(yè)調(diào)度的一大重要因素。

集裝箱碼頭在各設(shè)備能耗方面的研究相對(duì)較少，He等[17]集成粒子群優(yōu)化算法（PSO）以及遺傳算法，并使用仿真優(yōu)化方法實(shí)現(xiàn)了最小化所有船舶的總出發(fā)延誤以及全部任務(wù)的總能耗最小的目標(biāo)；He等[18]轉(zhuǎn)化YC調(diào)度問(wèn)題為具有軟時(shí)間窗（VRPSTW）的車輛路徑問(wèn)題，構(gòu)建了最小化總?cè)蝿?wù)完成時(shí)間以及YC總能耗的雙目標(biāo)混合整數(shù)規(guī)劃模型，并使用融合粒子群算法和遺傳算法的優(yōu)化算法進(jìn)行求解；范厚明等[19]在AGV 與雙小車岸橋的調(diào)度問(wèn)題中，考慮雙小車岸橋中轉(zhuǎn)平臺(tái)的容量、AGV的續(xù)航時(shí)間以及堆場(chǎng)緩沖支架容量的約束建立了兩階段優(yōu)化模型，并使用枚舉法和改進(jìn)遺傳算法求解；嚴(yán)南南等[20]考慮集卡的能耗并構(gòu)建集卡和QC協(xié)調(diào)調(diào)度的雙目標(biāo)模型，并用遺傳算法進(jìn)行求解；郭嬋嬋等[21]結(jié)合混合流水車間的思想，以最小化裝卸設(shè)備總作業(yè)時(shí)間和機(jī)械能耗為目標(biāo)構(gòu)建了包含QC、YC和集卡的雙目標(biāo)集成調(diào)度優(yōu)化模型，并且采用基于遺傳算法和模擬退火算法的混合算法進(jìn)行求解。艾立紅等[22]考慮作業(yè)過(guò)程中QC、YC 的平均能耗以及AGV 的不同作業(yè)狀態(tài)下的能耗，以最小化總作業(yè)時(shí)間和總作業(yè)能耗為目標(biāo)建立了多目標(biāo)混合整數(shù)規(guī)劃模型，并使用遺傳算法求解；Yang等[23]以最小化能耗和最小化總作業(yè)時(shí)間為目標(biāo)，基于混合流水車間調(diào)度問(wèn)題構(gòu)建并求解了QC、內(nèi)集卡和YC的雙目標(biāo)優(yōu)化模型。

現(xiàn)有集裝箱碼頭設(shè)備協(xié)調(diào)調(diào)度的能耗相關(guān)研究中，針對(duì)裝卸作業(yè)過(guò)程產(chǎn)生的能耗僅考慮了集卡的不同作業(yè)狀態(tài)下的能耗不同，卻沒有考慮作業(yè)過(guò)程中岸橋和場(chǎng)橋在不同作業(yè)狀態(tài)下的單位時(shí)間平均能耗不同，未對(duì)岸橋和場(chǎng)橋進(jìn)行作業(yè)狀態(tài)劃分，未考慮岸橋或場(chǎng)橋在作業(yè)過(guò)程中可能存在等待集卡的情況。本文針對(duì)集裝箱碼頭中岸橋、場(chǎng)橋和集卡的調(diào)度問(wèn)題，分析三種設(shè)備在作業(yè)過(guò)程中可能出現(xiàn)的各種作業(yè)狀態(tài)，劃分集卡的作業(yè)狀態(tài)為空載行駛狀態(tài)、負(fù)載行駛狀態(tài)和等待狀態(tài)；劃分岸橋、場(chǎng)橋的作業(yè)狀態(tài)為裝卸集裝箱狀態(tài)和等待狀態(tài)。量化各設(shè)備不同作業(yè)狀態(tài)下的不同能耗，建立最小化總完工時(shí)間和總作業(yè)能耗的多目標(biāo)混合整數(shù)規(guī)劃模型。使用改進(jìn)自適應(yīng)遺傳算法求解模型并將結(jié)果分別與CPLEX和傳統(tǒng)遺傳算法的求解結(jié)果作對(duì)比以驗(yàn)證算法的優(yōu)秀性，最后改變作業(yè)時(shí)間目標(biāo)和能耗目標(biāo)的權(quán)重進(jìn)行求解以作進(jìn)一步分析。

1 模型構(gòu)建

1.1 問(wèn)題描述

在集裝箱碼頭的裝卸作業(yè)過(guò)程中各設(shè)備之間往往會(huì)出現(xiàn)銜接不及時(shí)的情況，這樣會(huì)造成各設(shè)備出現(xiàn)等待情況。如卸船作業(yè)過(guò)程中若集卡不能及時(shí)到達(dá)指定岸橋處則岸橋需要等待集卡，相反若集卡到達(dá)岸橋處時(shí)岸橋還未準(zhǔn)備好開始任務(wù)則集卡需要等待岸橋。

本文綜合分析裝卸作業(yè)過(guò)程中各設(shè)備可能出現(xiàn)的作業(yè)狀態(tài)，量化各設(shè)備不同作業(yè)狀態(tài)下的作業(yè)時(shí)間，以計(jì)算各設(shè)備不同作業(yè)狀態(tài)下的能耗。本文使用權(quán)重系數(shù)法給時(shí)間目標(biāo)和能耗目標(biāo)分配權(quán)重，總目標(biāo)為實(shí)現(xiàn)裝卸作業(yè)的總完工時(shí)間最小以及總作業(yè)能耗最小。

模型假設(shè)：（1）不考慮岸橋和場(chǎng)橋翻箱；（2）場(chǎng)橋在計(jì)劃期間僅服務(wù)內(nèi)部的集卡；（3）集卡的路徑規(guī)劃不作考慮。

1.2 符號(hào)定義

1.2.1 模型參數(shù)

Q表示岸橋集合，q∈Q；

Y表示場(chǎng)橋集合，y∈Y；

V表示集卡集合，v∈V；

J表示集裝箱任務(wù)集合，J1表示進(jìn)口箱任務(wù)集合，J0表示出口箱任務(wù)集合，J1?J0=J；

θu、θl、θw分別表示集卡處于空載行駛狀態(tài)、負(fù)載行駛狀態(tài)及等待狀態(tài)時(shí)的單位時(shí)間平均能耗（unit/s）；

αl、αw分別表示岸橋處于裝卸集裝箱狀態(tài)及等待狀態(tài)時(shí)的單位時(shí)間平均能耗（unit/s）；

βl、βw分別表示場(chǎng)橋處于裝卸集裝箱狀態(tài)及等待狀態(tài)時(shí)的單位時(shí)間平均能耗（unit/s）；

tvii′表示集卡v從任務(wù)i的終點(diǎn)移動(dòng)至任務(wù)i′的起點(diǎn)所用時(shí)間；

tqii′表示任務(wù)i和i′都由岸橋q作業(yè)時(shí)岸橋q從任務(wù)i的終點(diǎn)移動(dòng)到任務(wù)i′的起點(diǎn)所用時(shí)間；

tyii′表示任務(wù)i和i′位于同一箱區(qū)且都由場(chǎng)橋y作業(yè)時(shí)場(chǎng)橋y從任務(wù)i的終點(diǎn)移動(dòng)到任務(wù)i′的起點(diǎn)所用時(shí)間；

δ表示岸橋作業(yè)一個(gè)集裝箱所用時(shí)間；

ε表示場(chǎng)橋作業(yè)一個(gè)集裝箱所用時(shí)間；

Tvi表示集卡v作業(yè)任務(wù)i時(shí)從任務(wù)i的起始節(jié)點(diǎn)行進(jìn)到其終點(diǎn)所用時(shí)間；

M表示一個(gè)足夠大的正數(shù)；

φi∈{0 ,1}，φi=1 表示進(jìn)口箱任務(wù)，否則表示出口箱任務(wù)。

1.2.2 輔助決策變量

sqi、tqi分別表示岸橋q作業(yè)任務(wù)i的開始時(shí)刻與結(jié)束時(shí)刻；

syi、tyi分別表示場(chǎng)橋y作業(yè)任務(wù)i的開始時(shí)刻與結(jié)束時(shí)刻；

svi、tvi分別表示集卡v作業(yè)任務(wù)i的開始時(shí)刻與結(jié)束時(shí)刻。

各設(shè)備作業(yè)任務(wù)i的開始時(shí)刻與結(jié)束時(shí)刻定義為：svi為集卡v到達(dá)任務(wù)i起始節(jié)點(diǎn)時(shí)刻，tvi為集卡v完成任務(wù)i的集裝箱交接時(shí)刻；任務(wù)i為進(jìn)口箱任務(wù)時(shí)，sqi為岸橋q在船舶上的提箱時(shí)刻，tqi為岸橋q與集卡交接的時(shí)刻，syi為場(chǎng)橋y就緒與集卡交接集裝箱的時(shí)刻，tyi為場(chǎng)橋y完成集裝箱裝卸的時(shí)刻；任務(wù)i為出口箱任務(wù)時(shí)，sqi為岸橋q就緒與集卡交接集裝箱的時(shí)刻，tqi為岸橋q完成集裝箱裝卸的時(shí)刻，syi為場(chǎng)橋y在堆場(chǎng)的提箱時(shí)刻，tyi為場(chǎng)橋y與集卡的交接時(shí)刻。

1.2.3 決策變量

γqvi表示在作業(yè)任務(wù)i時(shí)集卡v到達(dá)岸橋q處的時(shí)刻；

ηyvi表示在作業(yè)任務(wù)i時(shí)集卡v到達(dá)場(chǎng)橋y處的時(shí)刻；

?qvi表示在作業(yè)任務(wù)i時(shí)岸橋q等待集卡v所用的時(shí)間；

ψyvi表示在作業(yè)任務(wù)i時(shí)場(chǎng)橋y等待集卡v所用的時(shí)間

；表示在作業(yè)任務(wù)i時(shí)集卡v等待場(chǎng)橋y所用的時(shí)間；

avii′∈{0 ,1}，任務(wù)i和i′都由同一集卡v作業(yè)并且i于i′前完成則avii′=1，否則avii′=0；

bqii′∈{0 ,1}，任務(wù)i和i′都由同一岸橋q作業(yè)并且i于i′前完成則bqii′=1，否則bqii′=0；

cyii′∈{0 ,1}，任務(wù)i和i′都由同一場(chǎng)橋y作業(yè)并且i于i′前完成則cyii′=1，否則cyii′=0；

kvi′∈{0 ,1}，任務(wù)i′為集卡v的開始任務(wù)則kvi′=1，否則kvi′=0；

pvi∈{0 ,1}，任務(wù)i為集卡v的結(jié)束任務(wù)則pvi=1，否則pvi=0；

kqi′∈{0 ,1}，任務(wù)i′為岸橋q的開始任務(wù)則kqi′=1，否則kqi′=0；

pqi∈{0 ,1}，任務(wù)i為岸橋q的結(jié)束任務(wù)則pqi=1，否則pqi=0；

kyi′∈{0 ,1}，任務(wù)i′為場(chǎng)橋y的開始任務(wù)則kyi′=1，否則kyi′=0；

pyi∈{0 ,1}，任務(wù)i為場(chǎng)橋y的結(jié)束任務(wù)則pyi=1，否則pyi=0。

1.3 能耗模型

式（1）和（2）分別為考慮裝卸集裝箱狀態(tài)及等待狀態(tài)能耗的岸橋、場(chǎng)橋在整個(gè)作業(yè)過(guò)程中的總能耗；式（3）為集卡在任務(wù)節(jié)點(diǎn)間空載行駛狀態(tài)產(chǎn)生的能耗、運(yùn)輸集裝箱即負(fù)載行駛狀態(tài)產(chǎn)生的能耗及在岸橋側(cè)、場(chǎng)橋側(cè)等待狀態(tài)下產(chǎn)生的能耗之和，即集卡在整個(gè)作業(yè)過(guò)程中的總能耗。

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

下述的所有表達(dá)式中除在式中特別標(biāo)注外，?i,i′∈J,i≠i′，v∈V，q∈Q，y∈Y。

式（4）為目標(biāo)函數(shù)之一，目標(biāo)為使岸橋、場(chǎng)橋、集卡裝卸作業(yè)總完工時(shí)間最??；式（5）為另一個(gè)目標(biāo)函數(shù)，目標(biāo)為使各設(shè)備的總能耗最小。

式（6）～（11）表示岸橋、場(chǎng)橋、集卡作業(yè)集裝箱任務(wù)時(shí)，每個(gè)任務(wù)僅能被作業(yè)一次。

式（12）和（13）表示岸橋、場(chǎng)橋、集卡開始作業(yè)或者結(jié)束作業(yè)一次并且僅一次。

式（14）～（16）表示岸橋、場(chǎng)橋、集卡作業(yè)任務(wù)i的開始時(shí)刻與結(jié)束時(shí)刻的關(guān)系，岸橋、場(chǎng)橋結(jié)束作業(yè)時(shí)刻應(yīng)不早于開始作業(yè)時(shí)刻與裝卸一個(gè)集裝箱所需時(shí)間之和，集卡結(jié)束作業(yè)時(shí)刻應(yīng)不早于開始作業(yè)時(shí)刻與其在任務(wù)節(jié)點(diǎn)間運(yùn)輸集裝箱時(shí)間之和。

式（17）表示當(dāng)集卡v結(jié)束作業(yè)任務(wù)i后繼續(xù)作業(yè)任務(wù)i′，并且i′為出口箱任務(wù)時(shí)集卡v到達(dá)場(chǎng)橋y處的時(shí)刻應(yīng)不早于集卡v結(jié)束作業(yè)任務(wù)i的時(shí)刻與集卡v在任務(wù)節(jié)點(diǎn)i和i′間移動(dòng)所用的時(shí)間之和；式（18）表示當(dāng)集卡v完成任務(wù)i后繼續(xù)作業(yè)任務(wù)i′，并且i′是進(jìn)口箱任務(wù)時(shí)集卡v到達(dá)岸橋q處時(shí)刻應(yīng)不早于集卡v結(jié)束作業(yè)任務(wù)i時(shí)刻與集卡v在任務(wù)i和i′間移動(dòng)所用的時(shí)間之和。

式（19）表示任務(wù)i為進(jìn)口箱任務(wù)時(shí)集卡v到達(dá)場(chǎng)橋y處時(shí)刻應(yīng)不早于岸橋q結(jié)束任務(wù)i時(shí)刻與集卡v在任務(wù)i的開始節(jié)點(diǎn)與結(jié)束節(jié)點(diǎn)之間的行駛時(shí)間之和；式（20）表示任務(wù)i為出口箱任務(wù)時(shí)集卡v到達(dá)岸橋q處時(shí)刻應(yīng)不早于場(chǎng)橋y結(jié)束任務(wù)i時(shí)刻與集卡v在任務(wù)i的開始節(jié)點(diǎn)與結(jié)束節(jié)點(diǎn)之間的行駛時(shí)間之和。

式（21）表示當(dāng)任務(wù)i和i′都由岸橋q作業(yè)，且岸橋q結(jié)束作業(yè)i后緊接著作業(yè)i′時(shí)，岸橋q開始作業(yè)i′的時(shí)刻應(yīng)不早于其結(jié)束作業(yè)i的時(shí)刻與其在任務(wù)節(jié)點(diǎn)i和i′間的移動(dòng)時(shí)間之和；式（22）表示當(dāng)任務(wù)i和i′都位于同一箱區(qū)且都由場(chǎng)橋y作業(yè)，且場(chǎng)橋y結(jié)束作業(yè)i后緊接著作業(yè)i′時(shí)，場(chǎng)橋y開始作業(yè)i′的時(shí)刻應(yīng)不早于其結(jié)束作業(yè)i的時(shí)刻與其在任務(wù)節(jié)點(diǎn)i和i′間的移動(dòng)時(shí)間之和。

式（23）～（26）表示任務(wù)i為進(jìn)口箱任務(wù)時(shí)各設(shè)備等待時(shí)間的約束，岸橋q等待集卡v的時(shí)間應(yīng)該不小于集卡v到達(dá)岸橋q處時(shí)刻與岸橋q就緒交接集裝箱的時(shí)刻之差，場(chǎng)橋y等待集卡v的時(shí)間應(yīng)該不小于集卡v到達(dá)場(chǎng)橋y處時(shí)刻與場(chǎng)橋y作業(yè)任務(wù)i的開始時(shí)刻之差，集卡v等待岸橋q的時(shí)間應(yīng)該不小于岸橋q就緒交接集裝箱的時(shí)刻與集卡v到達(dá)岸橋q處時(shí)刻之差，集卡v等待場(chǎng)橋y的時(shí)間應(yīng)該不小于場(chǎng)橋y作業(yè)任務(wù)i的開始時(shí)刻與集卡v到達(dá)場(chǎng)橋y處時(shí)刻之差；式（27）～（30）表示任務(wù)i為出口箱任務(wù)時(shí)各設(shè)備等待時(shí)間的約束。

式（31）～（33）表示各決策變量的約束。

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

本文所建模型的求解計(jì)算難度比較大，屬于NP 難問(wèn)題。針對(duì)研究問(wèn)題和所建模型的特點(diǎn)，遺傳算法較適合于本文的求解。遺傳算法的迭代過(guò)程中染色體變異的概率Pm和染色體交叉的概率Pc對(duì)求解結(jié)果有較大影響，若二者過(guò)大則容易在迭代初期破壞適應(yīng)度高的染色體個(gè)體；若二者過(guò)小則在迭代后期不易產(chǎn)生新個(gè)體，使得算法陷入局部最優(yōu)解，造成早熟。針對(duì)這一問(wèn)題本文采用改進(jìn)自適應(yīng)遺傳算法進(jìn)行求解，其中關(guān)于Pm和Pc的改進(jìn)主要由以下調(diào)整公式體現(xiàn)：

式（34）和（35）中，fmax表示種群個(gè)體的最大適應(yīng)度值；favg表示種群個(gè)體的平均適應(yīng)度值；f′表示進(jìn)行交叉操作的兩個(gè)個(gè)體中的較大適應(yīng)度值；f表示進(jìn)行變異操作的個(gè)體的適應(yīng)度值；Pc1表示最大交叉概率，設(shè)置為Pc1=0.9；Pc2表示最小交叉概率，設(shè)置為Pc2=0.6；Pm1表示最大變異概率，設(shè)置為Pm1=0.1；Pm2表示最小變異概率，設(shè)置為Pm2=0.01。

算法流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flow chart

2.1 染色體編碼

本文使用雙層實(shí)數(shù)編碼方法，如圖2所示。染色體由兩層組成：第一層為集裝箱編號(hào)（數(shù)字順序即為作業(yè)順序），第二層為分配給該集裝箱任務(wù)的IT編號(hào)。假設(shè)10 個(gè)集裝箱任務(wù)有1 臺(tái)QC、3 臺(tái)YC 和6 輛IT 作業(yè)。已知YC 的作業(yè)計(jì)劃：YC1 于堆場(chǎng)1 作業(yè)集裝箱1、3、8；YC2于堆場(chǎng)2作業(yè)集裝箱2、4、5；YC3于堆場(chǎng)3作業(yè)集裝箱6、7、9、10。則各裝卸設(shè)備的作業(yè)順序?yàn)椋篞C：5→3→7→6→1→9→8→10→2→4；YC1：3→1→8；YC2：5→2→4；YC3：7→6→9→10；IT1：5→10；IT2：6→2；IT3：8→4；IT4：3→1；IT5：9；IT6：7。

圖2 染色體編碼示例Fig.2 Chromosome coding example

2.2 種群初始化

通過(guò)隨機(jī)生成來(lái)確保種群具有多樣性：第一層為集裝箱編號(hào)的隨機(jī)序列（permutation），第二層中每個(gè)基因?yàn)镮T編號(hào)的隨機(jī)抽樣，如圖3所示。

圖3 種群初始化染色體示例Fig.3 Chromosome example of initial population

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

本文采取權(quán)重系數(shù)法給各目標(biāo)分配權(quán)重以將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化成單目標(biāo)規(guī)劃問(wèn)題，設(shè)置目標(biāo)函數(shù)f1的權(quán)重系數(shù)為x，則f2的權(quán)重系數(shù)為1-x。因?yàn)槟繕?biāo)為求最小值，所以適應(yīng)度函數(shù)為：

2.4 遺傳操作

2.4.1 選擇

使用隨機(jī)通用采樣（Stochastic Universal Sampling）方法來(lái)選擇父代個(gè)體，此方法通過(guò)隨機(jī)選擇一次即可選定N個(gè)父代個(gè)體。首先依據(jù)個(gè)體的適應(yīng)度值求出各個(gè)體的被選概率，接著求出各個(gè)體被選的期望個(gè)數(shù)，然后構(gòu)造出一個(gè)輪盤，轉(zhuǎn)動(dòng)一次輪盤，N條指針?biāo)競(jìng)€(gè)體被選作父體進(jìn)行次代演化。

2.4.2 交叉

分別在兩個(gè)父代染色體隨機(jī)選擇兩個(gè)相同位置的基因，并將其中間部分作為交叉部分，如圖4 所示。交叉所得子代染色體中可能會(huì)存在集裝箱編號(hào)缺失或重復(fù)的情況，故要進(jìn)行子代染色體修補(bǔ)操作：逐個(gè)檢測(cè)子代染色體的基因，刪除重復(fù)的集裝箱編號(hào)并補(bǔ)充為所缺失的編號(hào)隨機(jī)值，如圖5所示。

圖4 染色體交叉Fig.4 Chromosome cross

圖5 修補(bǔ)所得子代染色體Fig.5 Progeny chromosome after repaired

2.4.3 變異

隨機(jī)選擇某一染色體的某一基因，依據(jù)變異因子判斷是否變異。進(jìn)行變異操作時(shí)若變異染色體的第一行則變異后還需修補(bǔ)，而修補(bǔ)前后該基因的編號(hào)相同，故變異染色體第一行沒有意義，只需變異染色體第二行。變異方式為將該染色體第二行某一基因的值替換為不同于原值的IT編號(hào)的隨機(jī)抽樣值，如圖6所示。

圖6 染色體變異Fig.6 Chromosome variation

3 案例分析

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

假設(shè)有1艘船舶，集裝箱碼頭有2臺(tái)QC、6臺(tái)YC及12輛IT，所需作業(yè)的集裝箱數(shù)根據(jù)算例設(shè)置，各QC、YC所需作業(yè)的集裝箱任務(wù)已知，各設(shè)備的作業(yè)順序以及各集裝箱的作業(yè)IT由算法隨機(jī)生成。集裝箱碼頭各設(shè)備的參數(shù)設(shè)定如表1，通常各裝卸設(shè)備作業(yè)時(shí)間以s 為單位，但是為了計(jì)算方便表中各設(shè)備的能耗參數(shù)單位使用unit/min。

表1 參數(shù)設(shè)置Table 1 Parameter settings

本文使用MATLAB編碼算法求解以檢驗(yàn)?zāi)Ｐ秃退惴ǖ挠行?。算法的相關(guān)設(shè)置為：種群規(guī)模為100，最大迭代次數(shù)為200，最大交叉概率為0.9，最小交叉概率為0.6，最大變異概率為0.1，最小變異概率為0.01。

3.2 算法性能分析

設(shè)置5組規(guī)模不同的算例評(píng)估算法的性能，當(dāng)不考慮能耗即x=1 時(shí)的CPLEX 和算法的求解結(jié)果如表2，其中算法求解結(jié)果為10 次運(yùn)行結(jié)果的平均值，誤差為算法所求比較于CPLEX 所求的f1和f2的誤差平均值的絕對(duì)值。如圖7 為集裝箱數(shù)為50 時(shí)的一次算法求解結(jié)果，算法在迭代118次時(shí)收斂，由于未考慮能耗目標(biāo)，故最優(yōu)解為最小總完工時(shí)間，為5 813 s。

圖7 規(guī)模為50及時(shí)間權(quán)重為1的一次算法收斂圖Fig.7 One algorithm convergence diagram of 50 containers while x=1

表2 CPLEX與算法求解結(jié)果對(duì)比Table 2 Results comparison of CPLEX and the algorithm

由表2可知，集裝箱數(shù)為20、50、80時(shí)遺傳算法的求解結(jié)果與CPLEX 的求解結(jié)果誤差較小，在可接受范圍內(nèi)，可知遺傳算法具有有效性。而當(dāng)集裝箱數(shù)上升至100 時(shí)CPLEX 的求解結(jié)果不如遺傳算法的求解結(jié)果優(yōu)秀，且運(yùn)行時(shí)間較長(zhǎng)；當(dāng)集裝箱數(shù)達(dá)到150 個(gè)時(shí)CPLEX雖然可以得到可行解，但運(yùn)行時(shí)間遠(yuǎn)超過(guò)遺傳算法，求解精度也與遺傳算法相差較大。對(duì)比可知本文設(shè)計(jì)的遺傳算法比CPLEX 有更高的求解效率，且求解效果較好，求解大規(guī)模算例的優(yōu)勢(shì)更大。

使用傳統(tǒng)遺傳算法對(duì)模型進(jìn)行求解并與本文采用的算法求解結(jié)果對(duì)比，結(jié)果如表3所示。

表3 兩種算法的求解結(jié)果對(duì)比Table 3 Results comparison of two algorithms

由表中數(shù)據(jù)分析可知，相較于傳統(tǒng)的遺傳算法，本文所采用的算法在求解速度上有一定的優(yōu)勢(shì)，且求解效果更好。

3.3 算法結(jié)果分析

為研究最小總完工時(shí)間和最小總作業(yè)能耗與權(quán)重系數(shù)x的關(guān)系，變化x的值進(jìn)行求解分析，其中x的值人為規(guī)定，且以固定值遞減。

當(dāng)設(shè)置x為0.88，集裝箱數(shù)為50 時(shí)算法收斂效果如圖8。運(yùn)行10次算法取其平均值，求得最小總完工時(shí)間為6 471 s，比不考慮能耗時(shí)增長(zhǎng)了672 s。而最小總能耗為1 832 unit，比不考慮能耗時(shí)減少了115 unit。推測(cè)可能由于提高了能耗目標(biāo)在總目標(biāo)中的權(quán)重，使得為了減少能耗作業(yè)順序發(fā)生了改變，導(dǎo)致作業(yè)時(shí)間增加；此外為了降低能耗作業(yè)順序的改變可能導(dǎo)致集卡在任務(wù)節(jié)點(diǎn)間空載行駛和負(fù)載行駛時(shí)的時(shí)間減少，但延長(zhǎng)了集卡在各任務(wù)節(jié)點(diǎn)處的等待時(shí)間，從而導(dǎo)致總作業(yè)能耗降低而總完工時(shí)間卻延長(zhǎng)了。

圖8 規(guī)模為50及時(shí)間權(quán)重為0.88的算法收斂圖Fig.8 Algorithm convergence diagram of 50 containers while x=0.88

為進(jìn)一步研究權(quán)重系數(shù)x對(duì)最小總完工時(shí)間和最小總作業(yè)能耗的影響，設(shè)置不同的x值并進(jìn)行求解。運(yùn)行算法10次取平均值，求解結(jié)果如表4所示。

表4 變化權(quán)重系數(shù)x 的算法結(jié)果Table 4 Results of the algorithm under different x

為更清晰地反映算法求解所得數(shù)據(jù)的變化情況，將以上數(shù)據(jù)繪制成折線圖，如圖9、圖10所示。

圖9 總完工時(shí)間走勢(shì)圖Fig.9 Line chart of operation time

圖10 總作業(yè)能耗走勢(shì)圖Fig.10 Line chart of energy consumption

表4中的算法結(jié)果是全部解集的部分解，由表中數(shù)據(jù)和圖9、圖10分析可知當(dāng)權(quán)重系數(shù)x的值逐漸減小即能耗目標(biāo)所占權(quán)重逐漸增大時(shí)，最小總完工時(shí)間逐漸增大，而最小總作業(yè)能耗逐漸降低，說(shuō)明能耗和作業(yè)時(shí)間是兩個(gè)相互沖突的目標(biāo)，即在追求低能耗時(shí)可能會(huì)犧牲作業(yè)效率。所得結(jié)果中沒有同時(shí)使總完工時(shí)間和總作業(yè)能耗都達(dá)到最小的解，決策者應(yīng)該確定一個(gè)合理的權(quán)重值，同時(shí)兼顧效率和能耗，碼頭擁堵時(shí)為提高作業(yè)效率則可以適當(dāng)降低能耗所占權(quán)重，設(shè)置較大的x值；碼頭空閑時(shí)為了節(jié)約能源則可以適當(dāng)提高能耗所占權(quán)重，設(shè)置較小的x值。

4 結(jié)論

相較于已有研究，本文進(jìn)一步考慮了岸橋、場(chǎng)橋在實(shí)際作業(yè)過(guò)程中會(huì)出現(xiàn)的兩種作業(yè)狀態(tài)，即裝卸集裝箱狀態(tài)及等待狀態(tài)，并且考慮集卡的三種作業(yè)狀態(tài)即負(fù)載行駛狀態(tài)、空載行駛狀態(tài)及等待狀態(tài)，在岸橋、場(chǎng)橋和集卡的協(xié)調(diào)調(diào)度問(wèn)題中量化各設(shè)備在不同作業(yè)狀態(tài)下的能耗，建立了考慮作業(yè)狀態(tài)能耗的集裝箱碼頭設(shè)備協(xié)調(diào)調(diào)度模型，并使用MATLAB 編碼改進(jìn)自適應(yīng)遺傳算法求得了模型的近似解。從求解結(jié)果可知，集裝箱碼頭裝卸設(shè)備作業(yè)時(shí)總完工時(shí)間與總作業(yè)能耗與其在目標(biāo)函數(shù)中的權(quán)重有關(guān)，能耗所占權(quán)重越高則裝卸設(shè)備的總完工時(shí)間越長(zhǎng)，但是總作業(yè)能耗越小，因此考慮作業(yè)狀態(tài)能耗相較于不考慮能耗時(shí)的設(shè)備協(xié)調(diào)調(diào)度更貼合集裝箱碼頭實(shí)際作業(yè)情況，可以幫助決策者更好地權(quán)衡作業(yè)時(shí)間和能耗目標(biāo)。本文對(duì)于多目標(biāo)規(guī)劃問(wèn)題采取權(quán)重系數(shù)法給各目標(biāo)函數(shù)分配權(quán)重以轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題進(jìn)行求解，但模型中各目標(biāo)函數(shù)的權(quán)重分配對(duì)求解結(jié)果有較大影響，如何合理分配各目標(biāo)函數(shù)在總目標(biāo)中的權(quán)重是以后需要研究的課題。