考慮低碳的場橋全局調(diào)度多目標(biāo)優(yōu)化

于 蒙，呂艷洋，李文峰

（武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063）

1 引言

隨著中國持續(xù)推進(jìn)經(jīng)濟(jì)全球化，國內(nèi)貨物貿(mào)易需求迅速提升，密集的海運(yùn)航線和港口操作產(chǎn)生了大量的碳排放。因此，有必要對我國集裝箱碼頭的運(yùn)作管理進(jìn)行低碳研究，降低港口碳排放量，提高港口運(yùn)營效率。

國內(nèi)外學(xué)者對于綠色港口、低碳港口理論和場橋調(diào)度優(yōu)化問題的研究已有較長的歷史。單場橋作業(yè)調(diào)度的研究主要考慮場橋路徑優(yōu)化問題和場橋操作次序問題。韓曉龍，等[1]分別運(yùn)用啟發(fā)式算法和模擬退火算法對單箱區(qū)單場橋調(diào)度問題進(jìn)行研究，通過兩種方法的結(jié)果對比得出模擬退火算法更優(yōu)的結(jié)論。KIM，等[2]以單個場橋?yàn)檠芯繉ο?，研究了外集卡進(jìn)場作業(yè)序列問題。NgWC，等[3]通過分值定界法考慮集裝箱任務(wù)準(zhǔn)備時間不同情況下的場橋調(diào)度問題。

多場橋作業(yè)調(diào)度問題的研究主要針對多場橋同時作業(yè)的安全距離以及多場橋在不同箱區(qū)分配的問題。He，等[4]以完成任務(wù)組總的遲延時間和場橋能源消耗最小化為目標(biāo)，構(gòu)建場橋調(diào)度混合整數(shù)規(guī)劃模型。賈志剛[5]以延遲任務(wù)量、轉(zhuǎn)場總時間與空閑總時間三者最小化為目標(biāo)構(gòu)建了場橋的調(diào)度模型，將啟發(fā)式算法和遺傳算法相結(jié)合來優(yōu)化求解。Jin，等[6]對堆場空間分配和場橋配置整合優(yōu)化問題進(jìn)行了研究，為集裝箱分配堆存子箱區(qū)，明確各時段場橋的工作區(qū)域。鄭紅星，等[7]對混堆箱區(qū)多場橋調(diào)度問題展開研究，并且考慮內(nèi)外集卡等待時間以及內(nèi)外集卡等待的優(yōu)先級問題。Liang，等[8]建立了包括堆存子系統(tǒng)、場橋調(diào)度子系統(tǒng)和協(xié)調(diào)控制子系統(tǒng)的協(xié)調(diào)優(yōu)化模型，為進(jìn)口箱分配堆存箱區(qū)，并確定了場橋作業(yè)計劃。Speer，等[9]通過仿真模型詳細(xì)討論了場橋移動干涉等約束，并提出用分支定界法求解場橋的實(shí)時調(diào)度問題。梁承姬，等[10]研究單個箱區(qū)中多臺場橋在干擾情況下基于混堆模式的存取箱同時進(jìn)行的調(diào)度問題。黃曉波，等[11]考慮根據(jù)裝卸過程中所產(chǎn)生的移動碳排放、裝卸碳排放和準(zhǔn)備碳排放3種排放源，建立了輪胎式龍門吊調(diào)度的混合整數(shù)規(guī)劃模型，目標(biāo)是使輪胎式龍門吊的碳排放量達(dá)到最小。周穎，等[12]考慮用全自動軌道式龍門起重機(jī)替換輪胎式龍門吊，在堆場計劃作業(yè)量不變的基礎(chǔ)上，以降低堆場碳排放量為約束，建立多階段混合整數(shù)規(guī)劃模型。

綜上，現(xiàn)有場橋研究大多考慮場橋行走路徑、完工時間以及堆場作業(yè)成本，基于碳排放量最小化的場橋作業(yè)優(yōu)化問題研究較少。因此，本文綜合考慮場橋全局調(diào)度以及場橋與集卡相互作業(yè)關(guān)系，建立以堆場作業(yè)過程中場橋與集卡碳排放量和作業(yè)成本最小化以及場橋轉(zhuǎn)場次數(shù)最小化為評價指標(biāo)的多目標(biāo)約束優(yōu)化模型。

2 問題描述

場橋全局調(diào)度作業(yè)會產(chǎn)生不必要的設(shè)備準(zhǔn)備時間即設(shè)備非作業(yè)時間，如集卡與場橋的相互等待時間和場橋的移動和轉(zhuǎn)場時間。所以，在減少碳排放量時還需要保證港口作業(yè)效率。因此，本文從碼頭實(shí)際情況出發(fā)，對于場橋裝卸過程中碳排放源進(jìn)行詳細(xì)分析，綜合考慮5種排放源并考慮多臺場橋空間上的不可跨越性和其他約束條件，兼顧場橋的作業(yè)效率和作業(yè)成本以及碳排放量，建立以場橋與集卡的綜合碳排放量最小和綜合作業(yè)成本最小以及場橋轉(zhuǎn)場次數(shù)最少為評價指標(biāo)的多目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，解決場橋移動路徑問題和裝卸任務(wù)指派問題。

場橋移動碳排放C0隨著行駛距離增加而增加，場橋裝卸碳排放C1隨著服務(wù)集裝箱的數(shù)量增加而增加，場橋準(zhǔn)備碳排放C2隨著停駐次數(shù)增加而增加，場橋與集卡的相互等待碳排放C3和C4隨著兩者相互等待時間的增加而增加。設(shè)備單次作業(yè)碳排放量見表1。

表1 設(shè)備單次作業(yè)碳排放量

3 模型建立

3.1 模型假設(shè)

（1）堆場上場橋操作任務(wù)都以20英尺標(biāo)準(zhǔn)集裝箱（TEU）為單位，且將同一箱區(qū)同一貝位作為一個任務(wù)組來處理；

（2）忽略每臺場橋的設(shè)備老舊可能導(dǎo)致的能耗不同以及場橋司機(jī)駕駛經(jīng)驗(yàn)不同的影響，假設(shè)每臺場橋的移動成本相同；

（3）在同一箱區(qū)內(nèi)操作的場橋之間必須保持一定的距離和不可跨越以保證安全；

（4）場橋初始時刻位于其初始操作任務(wù)所在貝位，操作完最后一個任務(wù)后即停留在原地直至所有場橋作業(yè)結(jié)束；

（5）場橋操作完一個任務(wù)隨即沿著最短路徑移動到下一個任務(wù)所在貝位處；

（6）計劃期內(nèi)場橋的任務(wù)量、任務(wù)所在位置、集卡到達(dá)時間以及場橋操作任務(wù)的時間都是已知的；

（7）堆場列間過道兩側(cè)的貝位數(shù)相同，且箱區(qū)之間過道寬度為兩個貝位，列間過道寬度為三個貝位；

（8）每一個時間段貝位分配的集裝箱數(shù)量不能超過任一場橋在該時間段的總工作能力（每小時場橋最多可處理20個集裝箱任務(wù)的裝卸）。

3.2 模型相關(guān)參數(shù)說明

表2 模型中的基本參數(shù)

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

考慮低碳的場橋全局調(diào)度多目標(biāo)優(yōu)化模型可表述為下面的形式。

式（1）表示考慮場橋作業(yè)時間和作業(yè)任務(wù)均勻

條件下的場橋作業(yè)成本和場橋與集卡的相互等待成本之和最小。引入指數(shù)函數(shù)eδ(ΔT+ΔN)來考慮場橋作業(yè)時間和場橋作業(yè)任務(wù)量的均衡，其中ΔT表示最大場橋完成作業(yè)時間與最小場橋作業(yè)完成時間的差值；ΔN表示最大場橋作業(yè)任務(wù)量與最小場橋作業(yè)任務(wù)量的差值；式（2）表示場橋與集卡總碳排量最??；式（3）表示所有場橋的轉(zhuǎn)場次數(shù)總和最小；式（4）表示所有場橋操作任務(wù)總數(shù)為N；式（5）表示由場橋c操作的任務(wù)數(shù)為N*c；式（6）表示場橋停駐次數(shù)等于裝卸任務(wù)總數(shù)與2倍場橋轉(zhuǎn)彎次數(shù)的和；式（7）保證在任意一個計劃時間段內(nèi)任意一個集裝箱任務(wù)組只能分配給一臺場橋進(jìn)行作業(yè)；式（8）保證任意一個計劃時間段內(nèi)一臺場橋只能同時操作一個集裝箱任務(wù)組；式（9）保證任意一個計劃時間段內(nèi)每個箱區(qū)至多有2臺場橋同時工作；式（10）-（11）分別表示場橋各任務(wù)的完成時刻和場橋到達(dá)作業(yè)任務(wù)的時刻之間的關(guān)系；式（12）用于計算場橋各時刻所在貝位；式（13）表示場橋與集卡的相互等待時間成本的計算函數(shù)；式（14）保證場橋間留有安全作業(yè)距離；式（15）表示場橋c對任務(wù)i，j的示性函數(shù)；式（16）表示任意一個場橋進(jìn)行作業(yè)時至多有一個緊前作業(yè)和緊后作業(yè)；式（17）任意一個場橋進(jìn)行作業(yè)時至少有一個緊前作業(yè)或緊后作業(yè)；式（18）表示場橋c從任務(wù)i行駛到任務(wù)j的場橋移動成本；式（19）表示場橋與集卡的相互等待時間成本。

4 模型求解

非劣排序遺傳算法Non-dominated Sorting Genetic Algorithm-II（NSGA-II）[13]從經(jīng)典的遺傳算法發(fā)展而來，具有良好的自組織性和自適應(yīng)性，及容錯能力強(qiáng)等優(yōu)點(diǎn)，易收斂且具有個體多樣性。模擬退火算法Simulated Annealing Algorithm（SA）是一種基于隨機(jī)尋優(yōu)方式的目標(biāo)優(yōu)化算法，具備較強(qiáng)的局部搜索能力。所以本文采用遺傳算法與模擬退火算法相結(jié)合的混合非劣排序遺傳算法求解模型，并給出數(shù)值分析算例證明了本文模型和算法的有效性。

4.1 染色體編碼

采用基于工序的實(shí)數(shù)編碼，場橋部分編碼規(guī)則為：設(shè)定4臺場橋在堆場同時作業(yè)，按照每一個任務(wù)組分配的集裝箱數(shù)量隨機(jī)分配4臺場橋。其中染色體示意圖如圖1所示，以14個算例數(shù)據(jù)為例，14個作業(yè)任務(wù)分別對應(yīng)一個指定的場橋，并且任務(wù)分配滿足約束條件（7）-（8）。

圖1 染色體示意圖

4.2 種群初始化

本文使用Matlab中的遺傳算法工具箱對初始種群進(jìn)行設(shè)定。遺傳算法工具箱得出的初始種群需要判斷是否滿足場橋作業(yè)安全距離以及同一時間同一箱區(qū)最多有兩臺場橋同時作業(yè)的限制，即約束條件（9）和（14）。為達(dá)到上述效果，對每一場橋的作業(yè)任務(wù)設(shè)置了算法判斷過程，判斷步驟如下：

步驟1：對每一個場橋的所有作業(yè)任務(wù)按照作業(yè)時間從小到大排序；

步驟2：選擇1、2兩個任務(wù)判斷是否在同時作業(yè)，若是則進(jìn)行步驟3，否則選擇2、3兩個任務(wù)繼續(xù)步驟2；

步驟3：繼續(xù)判斷下一個任務(wù)是否與前兩個任務(wù)同箱區(qū)，若是則判斷安全距離，否則選擇2、3兩個任務(wù)繼續(xù)步驟2；

步驟4：若1、2兩個任務(wù)處于安全距離則判斷2、3是否同時作業(yè)，否則結(jié)束程序；

步驟5：按照上述步驟依次判斷所有任務(wù)。

4.3 多目標(biāo)適應(yīng)度評價

多目標(biāo)優(yōu)化問題中，需要協(xié)調(diào)折中各個目標(biāo)函數(shù)，得到由折中解構(gòu)成的一個最優(yōu)解集。Pareto方法適合解決多目標(biāo)問題，帕累托層是根據(jù)個體之間的支配關(guān)系將個體劃分為不同的層級，每個解所處的層數(shù)越低，解的質(zhì)量越高，第一層級個體不被任何個體支配，即帕累托前沿解集。除了利用層級來劃分個體收斂性的優(yōu)劣，算法利用多樣性指標(biāo)擁擠距離來確定具有相同層級個體的優(yōu)劣。其中非支配排序和擁擠度排序的具體實(shí)現(xiàn)步驟如下：

4.3.1 非支配排序

步驟1：對每一個個體i∈N，判斷個體i支配的其他個體總數(shù)individual(i).n和支配個體i的其他個體集合individual(i).p；

步驟2：對每一個目標(biāo)函數(shù)k∈N，判斷個體i與j的支配關(guān)系；

步驟3：individual(i).n=0的個體即非支配排序等級最高的個體，令其front=1；

步驟4：按照上述步驟1-3依次判斷出所有個體的排序等級。

4.3.2 擁擠度排序

步驟1：對每一個非支配排序?qū)哟蝺?nèi)的個體按照第k個個體的目標(biāo)函數(shù)f_k排序，設(shè)排序第一和排序最后一個個體的擁擠度為無窮大。即f_min=f_max=inf，其它個體的擁擠度y為：

步驟2：按照步驟1依次計算每一個目標(biāo)函數(shù)得出的擁擠度排序值；

步驟3：將各個目標(biāo)函數(shù)得出的擁擠度值分別相加得出每一個個體的總排序值。

4.4 混合非劣排序遺傳算法過程

本文采用遺傳算法與模擬退火算法相結(jié)合的混合非劣排序遺傳算法，將模擬退火算法引入到NSGA-II中，解決了NSGA-II局部搜索能力較弱的問題，其步驟如下：

步驟1：按照4.2步驟隨機(jī)初始化種群；

步驟2：評價每一個個體的適應(yīng)度并進(jìn)行非支配排序和擁擠度排序，得出Pareto解；

步驟3：確定初始溫度；

步驟4：用遺傳算法得到新種群，并更新Pareto解；

步驟5：進(jìn)行退溫操作；

步驟6：若滿足運(yùn)算精度或迭代次數(shù)等停止條件時，輸出當(dāng)前最優(yōu)值，搜索結(jié)束，否則返回步驟4繼續(xù)搜索。

4.5 基于Analytic Hierarchy Process（AHP）的多目標(biāo)決策

基于Pareto求解得到一組Pareto解集即Pareto前沿，而對于實(shí)際問題，需要決策者篩選一個最滿意的非劣解用于實(shí)際生產(chǎn)。AHP是一種將定量和定性有效結(jié)合處理多目標(biāo)問題的決策技術(shù)，可以運(yùn)用于多目標(biāo)方案的決策。本文采用AHP方法，以多個目標(biāo)為決策準(zhǔn)則，對得到的Pareto前沿給出的非劣解方案進(jìn)行排序和評估。AHP遞階結(jié)構(gòu)如圖2所示。

圖2 多目標(biāo)方案的AHP遞階結(jié)構(gòu)

5 算例分析

采用數(shù)值實(shí)驗(yàn)來驗(yàn)證本文所提出模型和算法的有效性。算法由Matlab2016編程實(shí)現(xiàn)，所得結(jié)果均在Inter Core i5以及8RBRAM的x64PC上測得。

5.1 數(shù)據(jù)輸入

通過采集某集裝箱港口實(shí)際運(yùn)營數(shù)據(jù)，驗(yàn)證本文所建立模型以及用于求解模型的啟發(fā)式算法的有效性。選取某港口3個出口箱區(qū)進(jìn)行研究，箱區(qū)示意圖如圖3所示。每一個箱區(qū)包含兩列，每一列包含30個貝位。本文設(shè)定水平方向的中間過道為2個貝位距離，垂直方向的中間過道為1個貝位距離。在計劃時間120min內(nèi)處理40個集裝箱任務(wù)數(shù)量，可用的場橋數(shù)量為4臺。場橋移動單位時間成本，場橋與集卡的相互等待成本等數(shù)據(jù)在主程序中給出。

圖3 箱區(qū)示意圖

5.2 結(jié)果分析

針對本文模型，采用5.1節(jié)試驗(yàn)數(shù)據(jù)，通過MATLAB運(yùn)用遺傳算法和模擬退火算法相結(jié)合的混合算法求解僅考慮成本的單目標(biāo)方案，用加入模擬退火算法的非劣排序遺傳算法（多目標(biāo)方案需要用非劣排序）求解本文提出的綜合考慮作業(yè)成本、碳排放量和場橋轉(zhuǎn)場次數(shù)的多目標(biāo)方案。為了保證兩種方案對比的有效性，兩種方案的遺傳算法和模擬退火算法參數(shù)設(shè)置完全相同，具體參數(shù)見表3。

表3 算法參數(shù)設(shè)置

圖4和圖5分別為多目標(biāo)與單目標(biāo)兩種方案所得解的計算結(jié)果對比圖。

圖4 多目標(biāo)方案求解所得Pareto前沿

由圖5可知，單目標(biāo)方案進(jìn)化至49代時目標(biāo)值收斂于7 553元。從圖4可知，多目標(biāo)方案獲得的15種結(jié)果較為集中，表明該算法收斂。對于該15個非劣解的平衡方案，運(yùn)用層次分析法可以分析得到一個最優(yōu)方案，層次分析法決策結(jié)果見表4。

圖5 單目標(biāo)方案算法收斂過程

表4 評價決策結(jié)果

故Pareto方案7為多目標(biāo)方案的最合適方案。即多目標(biāo)方案成本為10 220元，碳排放量為728.8kg，轉(zhuǎn)場次數(shù)為9次。

把多目標(biāo)方案最優(yōu)結(jié)果與單目標(biāo)方案的最優(yōu)結(jié)果做對比，對比結(jié)果見表5。

表5 不同方案結(jié)果對比

對比兩個方案的結(jié)果，可以得出多目標(biāo)方案實(shí)驗(yàn)運(yùn)行時間增加2.52s，相差很少可以忽略。多目標(biāo)方案轉(zhuǎn)場次數(shù)相對于單目標(biāo)方案減少了4次，總成本增加20.76%，但是其總碳排放量減少34.89%，有效的降低了場橋工作的碳排放量。

6 結(jié)語

本文整體考慮場橋與集卡作業(yè)過程中的碳排放源，降低港口作業(yè)的碳排放，同時保證港口作業(yè)效率，減少港口的運(yùn)營成本。本文創(chuàng)新點(diǎn)在于同時考慮場橋的碳排放量最小化和作業(yè)成本最小化以及轉(zhuǎn)場次數(shù)最小來確定場橋的作業(yè)方案，還考慮了場橋與外集卡的作業(yè)聯(lián)系，提高了堆場的作業(yè)效率。使用混合非劣排序遺傳算法求解場橋的最優(yōu)作業(yè)方案。數(shù)值算例顯示碳排放量降低34.89%，證明了模型和算法的有效性。但本文沒有考慮翻箱因素和集卡到達(dá)時間不確定性的影響。并且模型假設(shè)每個任務(wù)作業(yè)時間已知，但是在實(shí)際操作中進(jìn)出口箱的選位和作業(yè)先后順序都會對堆場作業(yè)造成影響，后續(xù)的研究方向是將場橋的多箱區(qū)調(diào)度與集卡到達(dá)時間和堆存位置選擇的不確定性進(jìn)行集成優(yōu)化。