于 蒙，呂艷洋，李文峰

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

1 引言

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

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

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

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

2 問(wèn)題描述

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

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

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

3 模型建立

3.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 模型求解

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

4.1 染色體編碼

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

圖1 染色體示意圖

4.2 種群初始化

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

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

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

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

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

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

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

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

4.3.1 非支配排序

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

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

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

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

4.3.2 擁擠度排序

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

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

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

4.4 混合非劣排序遺傳算法過(guò)程

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

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

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

步驟3：確定初始溫度；

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

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

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

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

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

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

5 算例分析

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

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

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

圖3 箱區(qū)示意圖

5.2 結(jié)果分析

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

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

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

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

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

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

表4 評(píng)價(jià)決策結(jié)果

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

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

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

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

6 結(jié)語(yǔ)

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