張艷偉， 譚永慶， 莫滿華， 王 楠

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

隨著集裝箱運輸業(yè)務的發(fā)展，港口集裝箱吞吐量持續(xù)增長，業(yè)務量增長及船舶大型化對集裝箱碼頭作業(yè)能力和作業(yè)效率產(chǎn)生巨大沖擊。同貝同步裝卸［1］模式通過對裝、卸兩類集裝箱的裝卸順序優(yōu)化，實現(xiàn)岸橋及水平搬運設(shè)備充分利用，是提高集裝箱碼頭裝卸作業(yè)效率和資源利用率的有效途徑。

國內(nèi)外學者關(guān)于集裝箱船舶的裝船順序問題［2-4］已經(jīng)取得了豐富的研究成果，該問題主要考慮滿足裝船技術(shù)要求前提下以堆場內(nèi)翻箱次數(shù)最少為優(yōu)化目標，利用遺傳算法、啟發(fā)式算法［5］進行求解；然而針對同貝同步裝卸作業(yè)模式，裝船與卸船配合才是其提升效率的關(guān)鍵所在，Zhang［6］在Goodchild［1］基礎(chǔ)上以最大化岸橋的雙循環(huán)操作次數(shù)為優(yōu)化目標，利用混合啟發(fā)式算法求解岸橋裝卸順序問題；Wang［7］研究了帶艙蓋板約束的雙循環(huán)岸橋調(diào)度問題，通過對艙位間作業(yè)順序優(yōu)化和艙內(nèi)列之間順序優(yōu)化達到減少岸橋空載行程的目的；張文韜［8］基于遺傳算法有效求解考慮艙蓋板約束的岸橋作業(yè)序列優(yōu)化問題；考慮到集裝箱裝卸受到岸橋、集卡以及場橋等多作業(yè)設(shè)備的影響，ALT等［9］設(shè)計粒子群算法求解岸橋和集卡聯(lián)合調(diào)度問題以減少岸橋與集卡間雙向等待時間；Kaveshgar等［10］結(jié)合貪婪算法設(shè)計遺傳算法求解岸橋與集卡聯(lián)合調(diào)度模型；Vahdani 等［11］針對多個碼頭間集卡共享情況下岸橋與集卡聯(lián)合調(diào)度，建立以碼頭運營成本最小和碼頭溢出工作量最小為目標的雙目標優(yōu)化模型，制定了集卡分配和岸橋匹配方案。

綜上，目前已有研究大多考慮先卸后裝模式下岸橋與集卡調(diào)度或同貝同步裝卸船模式下集裝箱裝卸順序問題。本文研究同貝同步裝卸模式下，船舶貝位內(nèi)岸橋裝卸集裝箱作業(yè)序列與集卡任務分配及指派聯(lián)合優(yōu)化，同時考慮艙蓋板等空間約束對同步裝卸船順序的影響，以及集卡雙向重載與岸橋同步裝卸作業(yè)配合等。針對同貝同步裝卸模式下，裝卸船作業(yè)序列空間約束多、集卡調(diào)度復雜度大等問題特征，研究設(shè)計改進遺傳算法-改進非支配排序多目標遺傳算法（IGA-INSGA-II）兩階段決策算法。第一階段，考慮艙蓋板約束及堆場翻箱影響，設(shè)計基于空間約束算子的改進遺傳算法求解船舶貝位內(nèi)岸橋作業(yè)序列優(yōu)化問題；基于第一階段裝卸船順序優(yōu)化序列，第二階段考慮既定船舶多臺岸橋共享集卡，以及最大化集卡雙向重載配合岸橋同步裝卸，設(shè)計基于最早可作業(yè)時間優(yōu)先的分段式編碼多目標遺傳算法求解集卡水平搬運任務分配與指派問題。

1 問題描述

常規(guī)先卸后裝情況下，岸橋移動到既定船舶貝位，先完成卸船作業(yè)，再進行裝船作業(yè)。與先卸后裝裝卸船模式不同，同貝同步裝卸是指在集卡及場橋的協(xié)同配合下，岸橋?qū)Υ柏愇粌?nèi)的集裝箱同步進行卸載和裝載作業(yè)，將集卡上一個出口箱裝載到船上后立即卸載一個進口箱到同一輛集卡上，實現(xiàn)岸橋與集卡的雙程重載，如圖1所示。

圖1 同貝同步裝卸船模式Fig.1 Dual cycling model of loading /unloading ship

同步裝卸的關(guān)鍵在于岸橋裝卸、集卡雙向搬運及堆場收發(fā)箱等多設(shè)備多環(huán)節(jié)的協(xié)同配合，其難點在于需要考慮艙蓋板等空間約束及堆場翻箱等復雜影響，優(yōu)化決策同時裝、卸集裝箱的裝卸船作業(yè)順序，并針對裝卸作業(yè)順序給出優(yōu)化的集卡水平搬運調(diào)度方案，有效銜接岸橋同貝同步裝卸實施。本文以“岸橋-集卡-場橋”裝卸工藝集裝箱碼頭同貝同步裝卸船系統(tǒng)為研究對象，集卡為單船作業(yè)面調(diào)度模式，船舶貝位內(nèi)的裝卸過程可分解為單卸船作業(yè)、混合裝卸作業(yè)以及單裝船作業(yè)三個階段。船舶既定貝位的積載、配載狀態(tài)及各階段岸橋、集卡等設(shè)備配置狀況已知，以岸橋裝卸總次數(shù)及堆場翻箱次數(shù)最小為岸橋裝卸作業(yè)序列問題優(yōu)化目標，綜合考慮艙蓋板對裝卸順序的影響，確定船舶貝位內(nèi)集裝箱裝、卸順序；基于優(yōu)化的裝卸順序，以岸橋最大完工時間最小化和集卡總等待時間最小化為目標完成集卡任務分配與指派優(yōu)化。

2 模型構(gòu)建

結(jié)合生產(chǎn)實際，做出如下假設(shè)：

（1）基于嚴格配載模式，按照積、配載圖裝卸集裝箱。

（2）只考慮40英尺集裝箱，不考慮船舶穩(wěn)定性等因素對船舶貝位內(nèi)裝卸作業(yè)順序的影響。

（3）堆場資源充足，不存在堆場擁堵，集卡在堆場場橋下無排隊。

（4）岸橋、場橋不存在帶箱等待集卡，集卡完全就位后，岸橋、場橋開始裝、卸箱起吊。

2.1 集合

TS為船舶貝位內(nèi)裝卸集裝箱集合，TS=TSI∪TSO，其中TSI表示卸載集裝箱集合，TSO表示裝載集裝箱集合；TSf為船舶貝位作業(yè)階段f卸載、裝載集裝箱的集合，f=1，2，3，TS=TS1∪TS2∪TS3；Kf為船舶貝位作業(yè)階段f配備集卡的集合；R為艙口集合；S為船舶貝位內(nèi)需裝卸所有列的集合，S=Sr，uI∪Sr，uO∪Sr，dI∪Sr，dO，其中Sr，uI表示艙口r艙蓋板上需要卸載的列集合；Sr，uO為艙口r艙蓋板上需要裝載的列集合；Sr，dO為艙口r艙蓋板下需要裝載的列集合；Sr，dI為艙口r艙蓋板下需要卸載的列集合。

2.2 參數(shù)

相關(guān)參數(shù)及含義如表1所示。

表1 參數(shù)設(shè)定Tab.1 Parameter setting

2.3 決策變量

uij為0-1 變量，當集裝箱i和j屬于船舶同一貝位，j是i的緊后工序任務，且i和j可由岸橋同步作業(yè)時，uij為1，否則為0。zij為0-1 變量，當集裝箱i和j由同一臺岸橋裝卸，且j是i的后序任務時為1，否則為0；xik為0-1 變量，當集裝箱i由集卡k搬運時為1，否則為0；yijk為0-1 變量，當集卡k搬運完集裝箱i后立即搬運集裝箱j時為1，否則為0。

2.4 多目標優(yōu)化模型

目標函數(shù)：

約束：

目標函數(shù)式（1）表示最小化岸橋裝卸總次數(shù)和堆場翻箱次數(shù)，目標函數(shù)式（2）表示最小化岸橋最大完工時間，目標函數(shù)式（3）表示最小化集卡總等待時間；約束式（4）～（7）限制任意一個集裝箱在岸橋或集卡的前序和后序作業(yè)；式（8）表示任意一個集裝箱只由一個集卡搬運；式（9）～（13）根據(jù)集裝箱在船舶貝位上的空間位置限制其裝卸順序；式（14）表示任意作業(yè)任務在岸橋處的開始時間受當前岸橋前序任務的結(jié)束時間影響；式（15）～（17）表示任意作業(yè)任務在岸橋處的開始時間受當前集卡前序任務結(jié)束時間的影響；式（18）～（20）表示任意任務在集卡上的實際開始時間與當前集卡前序任務的結(jié)束時間以及岸橋作業(yè)完成時間的關(guān)系；式（21）～（24）更新當前任務在集卡上的預計作業(yè)開始時間；式（25）計算集卡總等待時間。

3 求解算法設(shè)計

設(shè)計兩階段求解算法，算法流程如圖2 所示，其中擾動參數(shù)tur計數(shù)，TUR為給定擾動閾值。

圖2 IGA-INSGA-II算法流程Fig.2 Flowchart of IGA-INSGA-II Algorithm

利用IGA求解同貝同步裝卸模式下集裝箱岸橋裝卸作業(yè)序列，其中IGA主要改進包括：設(shè)計空間約束算子及種群擾動，空間約束算子與罰函數(shù)結(jié)合，保證所有解滿足艙蓋板空間約束、列內(nèi)上下箱位及同一箱位裝卸箱空間約束等，設(shè)計種群擾動策略促進種群進化，有效避免陷入局部最優(yōu)解；設(shè)計INSGA-II求解集卡任務分配與指派問題，INSGA-II主要改進包括：根據(jù)貝位作業(yè)階段和集卡數(shù)量配置約束，設(shè)計分段式編碼，設(shè)計基于岸橋最早可作業(yè)時間優(yōu)先的解碼策略等有效減少計算復雜度。

3.1 IGA設(shè)計

基于船舶貝位內(nèi)集裝箱裝卸順序空間約束設(shè)計空間約束算子，約束算子與罰函數(shù)配合，保證所有解均為可行解，設(shè)計擾動策略避免算法陷入局部最優(yōu)。

3.1.1 編碼及解碼

圖3 染色體編碼示意圖Fig.3 Chromosome coding diagram

基因表示裝卸列編號，一條染色體為一個裝卸船順序方案。根據(jù)船舶貝位積載圖和配載圖，劃分艙內(nèi)外并分別統(tǒng)計既定貝位需要裝卸的集裝箱列的數(shù)量，以最大卸船列數(shù)量為界限，卸船列用小于該界限值的整數(shù)依次編號，裝船列用大于該值的整數(shù)進行編號，利用貪婪準則初始化種群，使每個列的卸載編號排列在裝載編號之前；解碼時，根據(jù)船舶積載圖和配載圖信息，以及船舶艙位先卸后裝、卸船列從上至下進行卸船作業(yè)、裝船列從下至上進行裝船作業(yè)等生產(chǎn)啟發(fā)信息，交叉讀取卸載列和裝載列對應的集裝箱，得到集裝箱作業(yè)序列。

3.1.2 罰函數(shù)的構(gòu)建

為保證算法迭代過程中同列集裝箱先卸后裝，設(shè)計懲罰項σP(x)，其中σ為懲罰因子，取很大的正數(shù)；P(x)是染色體x的函數(shù)，當遍歷整條染色體過程中出現(xiàn)同列先裝后卸的排列狀態(tài)時，P(x)加1；F1(x)為目標函數(shù)，利用式（26）計算染色體適應度值，即

3.1.3 交叉重組與變異算子

采用順序交叉算子完成交叉操作。在染色體上的隨機生成三個位置，將染色體劃分為四段，交換中間兩個片段，完成染色體變異操作。

一個股票有沒有機構(gòu)在活動？有沒有新資金介入？這些問題應該怎么看？筆者下面介紹一下自己的方法和步驟，分為“動態(tài)看盤”和“靜態(tài)看盤”兩種。

3.1.4 空間約束算子

針對集裝箱列之間艙蓋板上下空間約束，設(shè)計空間約束算子約束艙蓋板上下集裝箱列的裝卸順序，如圖4所示。

圖4 空間約束算子示意圖Fig.4 Schematic diagram of reconstruction operator

（1）遍歷染色體中某一艙位上下需要卸載的集裝箱列，取出其基因編號和在染色體中的位置，按照升序?qū)θ〕龅幕蛭恢眠M行排序，形成基因位置排序序列；

（2）將取出的基因按照艙蓋板上方卸載列在前，下方卸載列在后的原則排序，形成基因序列；

（3）根據(jù)基因序列按照基因位置排序序列對原染色體對應位置的基因進行替換；

（4）根據(jù)上述步驟原理，按照艙蓋板下集裝箱列優(yōu)先裝載原則，對染色體中該艙位需要裝載集裝箱列的裝載順序進行約束；

（5）重復上述步驟直到染色體中所有艙位的裝載順序都滿足約束。

3.1.5 擾動設(shè)計

為減少遺傳算法陷入局部最優(yōu)解，設(shè)計局部調(diào)整和部分初始化擾動策略。當種群進化過程中連續(xù)多代目標函數(shù)值未改進時，取出其中排序靠后的一半個體進行調(diào)整：

（1）利用貪婪策略對取出種群中前一半個體局部調(diào)整：當染色體中出現(xiàn)連續(xù)兩個裝船集裝箱列基因時，取出后一個裝船列對應的卸載編碼并將其插入到兩個連續(xù)裝載列基因之間；

（2）采用半初始化策略［12］對取出種群中后一半染色體處理：利用隨機生成染色體替換表現(xiàn)最差的染色體。

3.2 INSGA-II設(shè)計

基于岸橋最早可作業(yè)時間優(yōu)先指派原則設(shè)計分段編碼及解碼方法，實現(xiàn)集卡水平搬運任務指派。

3.2.1 分段式編碼

在已知集裝箱裝卸作業(yè)順序的基礎(chǔ)上，對整條船舶“多岸橋-多集卡”匹配同貝同步裝卸，進行集卡任務指派方案優(yōu)化。以配備2臺岸橋同時開始，各裝卸一個貝位為例。開始階段，貝位內(nèi)2臺岸橋僅進行卸船作業(yè)，為單卸船階段；任何一個貝位開始進行同步裝卸即進入混合裝卸階段；最后為單裝船階段。已知單卸船階段配備K1輛集卡，集卡編號分別為1、2、…、K1；混合裝卸階段、單裝船階段分別配備K2輛和K3輛集卡，且均可服務于2臺岸橋。對不同作業(yè)階段水平搬運任務進行分段式整數(shù)編碼，基因表示執(zhí)行該貝位搬運任務集卡的編號。貝位內(nèi)配對同步裝卸的兩個集裝箱應該由同一輛集卡搬運，為減少計算復雜度對配對的搬運任務進行標記并簡化編碼，如圖5所示。

圖5 分段式編碼示意圖Fig.5 Schematic diagram of segmented coding

3.2.2 基于岸橋最早可作業(yè)時間優(yōu)先的解碼方法

針對任務分配與指派問題，現(xiàn)有研究多采用兩段式編碼［13］或者多行矩陣式編碼［14］，由于1輛集卡可協(xié)同服務于多臺岸橋，本文設(shè)計的染色體編碼對多臺岸橋?qū)乃邪徇\任務進行分配，不同岸橋作業(yè)任務之間沒有優(yōu)先級，基于岸橋最早可作業(yè)優(yōu)先指派原則進行集卡任務指派，解碼方案：

（1）初始化岸橋?qū)嶋H作業(yè)開始時間tai、集卡搬運計劃開始時間ksi、集卡搬運實際開始時間kai，設(shè)定集卡位置參數(shù)；

（2）讀取染色體中每臺岸橋的集卡分配方案，比較所有岸橋當前任務最早可作業(yè)時間，若相同則隨機選擇一臺岸橋，否則選擇計劃開始時間最早的岸橋，按照染色體分配的集卡執(zhí)行其當前集裝箱裝卸任務，記錄集卡作業(yè)順序；

（3）根據(jù)式（14）～（24）更新當前集裝箱裝卸任務的岸橋?qū)嶋H開始作業(yè)時間、集卡實際開始作業(yè)時間、當前任務序列內(nèi)后續(xù)任務的計劃開始作業(yè)時間；

（4）根據(jù)最優(yōu)染色體和任務執(zhí)行順序輸出集卡的任務分配和指派方案。

3.2.3 遺傳操作

采用精英策略和擁擠度比較算子進行個體選擇，利用模擬二進制交叉算子進行染色體交叉，采用多項式變異算子進行染色體變異操作。

4 算例分析

4.1 算例及參數(shù)設(shè)定

（1）算例設(shè)計

裝船順序優(yōu)化算例船舶貝位內(nèi)包含3個艙蓋板，小規(guī)模算例既定貝位需卸載34個集裝箱，裝載33個集裝箱；大規(guī)模算例貝位內(nèi)卸載130個集裝箱，裝載125個集裝箱，相關(guān)積載、配載圖及集裝箱信息均已知。集卡調(diào)度算例，兩臺岸橋同時對2個貝位進行作業(yè)，設(shè)計裝卸量為14個集裝箱、22個集裝箱、60個和118個集裝箱4個不同規(guī)模算例，其中，裝箱、卸箱、可同步裝卸的集裝箱等信息由上層裝船順序優(yōu)化結(jié)果獲取。

（2）參數(shù)設(shè)計

將式（26）中σ設(shè)為1 000；考慮堆場的翻箱次數(shù)權(quán)重系數(shù)ω取值范圍為（ 0，1 ），取0 ～ 1之間的離散值進行實驗，如圖6所示。

圖6 ω對目標函數(shù)的影響Fig.6 ω influence on objective function

結(jié)果表明，ω對目標函數(shù)值產(chǎn)生線性影響，不影響尋優(yōu)方向。綜合考慮翻箱次數(shù)相對于岸橋裝卸的重要性，將ω設(shè)為0.5進行后續(xù)實驗。

集卡任務調(diào)度算例，參考張笑菊［15］設(shè)置設(shè)備數(shù)量、裝卸速度等相關(guān)參數(shù)，如表2所示。

表2 參數(shù)設(shè)定Tab.2 Parameter setting

4.2 結(jié)果分析

采用Python編程，實驗在PC（Intel（R） Core（TM）i5-6200U CPU @ 2.30GHz 2.40 GHz內(nèi)存8.00 GB）上進行。集裝箱裝卸作業(yè)順序優(yōu)化，基于算例對遺傳算法（GA），粒子群算法（PSO）以及本文的改進遺傳算法（IGA）進行測試，其中，IGA設(shè)定種群數(shù)量100，精英保存率0.1，交叉概率0.9，變異概率0.1，擾動閾值設(shè)為10；GA種群數(shù)量為200，其余參數(shù)相同，PSO種群數(shù)量200，個體最優(yōu)值保存概率0.9，種群最優(yōu)值保存概率0.9，迭代次數(shù)均為200代。集卡任務分配與指派算例中，算法參數(shù)均設(shè)置為種群數(shù)500，交叉概率0.9，變異概率0.1，進化代數(shù)300代。各算法20次實驗結(jié)果如表3及圖7所示，算法收斂狀態(tài)如圖8所示。

表3 算法測試結(jié)果對比Tab.3 Comparison of algorithm test

圖7 IGA、PSO、GA算法20次最優(yōu)解對比Fig.7 Comparison of 20 times results of each algorithm

圖8 IGA、GA、PSO算法收斂對比Fig.8 Comparison of convergence of different algorithms

（1）集裝箱裝卸作業(yè)順序結(jié)果分析

通過上述2個算例對比可知，本文改進的遺傳算法跳出局部最優(yōu)解及尋優(yōu)的能力具有明顯優(yōu)勢，較常規(guī)遺傳算法及粒子群算法，運行20次平均結(jié)果分別提升約8.51%、13.47%；計算用時較GA有較大幅度減少，較PSO有所增加，且計算時間控制在3min以內(nèi)。實驗結(jié)果表明，本文改進遺傳算法能有效求解同貝同步裝卸作業(yè)模式下岸橋作業(yè)序列優(yōu)化問題。

（2）集卡任務分配與指派結(jié)果分析

將本文INSGA-II與兩段式編碼的NSGA-II及參考向量引導多目標優(yōu)化進化算法（Reference Vector Guided Evolutionary Algorithm，RVEA）對比，求解結(jié)果如表4及圖9所示。

表4 集卡調(diào)度優(yōu)化求解結(jié)果Tab.4 solution of truck dispatching

圖9 不同規(guī)模算例帕累托前沿解對比Fig.9 Comparison of Pareto front of different scale examples

其中，表4 中平均決策時間為連續(xù)運行20 次的平均計算時間，每個案例選擇三個帕累托前沿解對應的方案，方案1、方案2 和方案3 的函數(shù)值如表4。結(jié)果顯示，INSGA-II 較兩段式編碼NSGA-II 及RVEA，岸橋最大完工時間及集卡總等待時間減少明顯。表明，采用改進編碼解碼策略以及岸橋最早可作業(yè)時間優(yōu)先指派策略，解分布比較均勻，不同規(guī)模算例優(yōu)化方案具有優(yōu)勢。

5 結(jié)語

本文針對集裝箱碼頭同貝同步裝卸作業(yè)模式下，船舶貝位內(nèi)集裝箱岸橋裝卸作業(yè)序列決策優(yōu)化與集卡聯(lián)合調(diào)度問題，綜合考慮艙蓋板約束以及堆場翻箱等因素，構(gòu)建包含岸橋裝卸總次數(shù)最小化、總作業(yè)時間最小化、集卡總等待時間最小化為目標的數(shù)學模型。鑒于問題的NP 難特性，設(shè)計兩階段IGA-INSGA-II求解算法，利用IGA求解岸橋裝卸作業(yè)序列決策問題，通過設(shè)計空間約束算子和種群擾動策略有效增強IGA 尋優(yōu)與跳出局部最優(yōu)解的能力，利用INSGA-II 求解集卡的任務分配與指派問題，通過改進編碼與指派策略有效提升了算法的尋優(yōu)能力，實驗驗證了算法和模型的有效性。下一步研究將考慮不同箱型同貝同步裝卸順序優(yōu)化、不確定因素下岸橋和集卡聯(lián)合調(diào)度及優(yōu)化方案韌性研究。

作者貢獻聲明：

張艷偉：確定研究方向，指導模型構(gòu)建，撰寫文稿；

譚永慶：構(gòu)建模型并編程求解，撰寫文稿；

莫滿華、王楠：文獻查閱、文稿修改。