考慮低碳的場橋全局調度多目標優化

于 蒙，呂艷洋，李文峰

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

1 引言

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

國內外學者對于綠色港口、低碳港口理論和場橋調度優化問題的研究已有較長的歷史。單場橋作業調度的研究主要考慮場橋路徑優化問題和場橋操作次序問題。韓曉龍，等[1]分別運用啟發式算法和模擬退火算法對單箱區單場橋調度問題進行研究，通過兩種方法的結果對比得出模擬退火算法更優的結論。KIM，等[2]以單個場橋為研究對象，研究了外集卡進場作業序列問題。NgWC，等[3]通過分值定界法考慮集裝箱任務準備時間不同情況下的場橋調度問題。

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

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

2 問題描述

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

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

表1 設備單次作業碳排放量

3 模型建立

3.1 模型假設

（1）堆場上場橋操作任務都以20英尺標準集裝箱（TEU）為單位，且將同一箱區同一貝位作為一個任務組來處理；

（2）忽略每臺場橋的設備老舊可能導致的能耗不同以及場橋司機駕駛經驗不同的影響，假設每臺場橋的移動成本相同；

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

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

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

（6）計劃期內場橋的任務量、任務所在位置、集卡到達時間以及場橋操作任務的時間都是已知的；

（7）堆場列間過道兩側的貝位數相同，且箱區之間過道寬度為兩個貝位，列間過道寬度為三個貝位；

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

3.2 模型相關參數說明

表2 模型中的基本參數

3.3 數學模型

考慮低碳的場橋全局調度多目標優化模型可表述為下面的形式。

式（1）表示考慮場橋作業時間和作業任務均勻

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

4 模型求解

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

4.1 染色體編碼

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

圖1 染色體示意圖

4.2 種群初始化

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

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

步驟2：選擇1、2兩個任務判斷是否在同時作業，若是則進行步驟3，否則選擇2、3兩個任務繼續步驟2；

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

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

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

4.3 多目標適應度評價

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

4.3.1 非支配排序

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

步驟2：對每一個目標函數k∈N，判斷個體i與j的支配關系；

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

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

4.3.2 擁擠度排序

步驟1：對每一個非支配排序層次內的個體按照第k個個體的目標函數f_k排序，設排序第一和排序最后一個個體的擁擠度為無窮大。即f_min=f_max=inf，其它個體的擁擠度y為：

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

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

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

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

步驟1：按照4.2步驟隨機初始化種群；

步驟2：評價每一個個體的適應度并進行非支配排序和擁擠度排序，得出Pareto解；

步驟3：確定初始溫度；

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

步驟5：進行退溫操作；

步驟6：若滿足運算精度或迭代次數等停止條件時，輸出當前最優值，搜索結束，否則返回步驟4繼續搜索。

4.5 基于Analytic Hierarchy Process（AHP）的多目標決策

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

圖2 多目標方案的AHP遞階結構

5 算例分析

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

5.1 數據輸入

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

圖3 箱區示意圖

5.2 結果分析

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

表3 算法參數設置

圖4和圖5分別為多目標與單目標兩種方案所得解的計算結果對比圖。

圖4 多目標方案求解所得Pareto前沿

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

圖5 單目標方案算法收斂過程

表4 評價決策結果

故Pareto方案7為多目標方案的最合適方案。即多目標方案成本為10 220元，碳排放量為728.8kg，轉場次數為9次。

把多目標方案最優結果與單目標方案的最優結果做對比，對比結果見表5。

表5 不同方案結果對比

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

6 結語

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