基于改進遺傳算法的自動化港口貝位兩側進出箱模式下場橋調度模型研究

葉軍，羅浩銘，張先燏

（1.上海振華重工（集團）股份有限公司，上海 200125；2.上海交通大學機械與動力工程學院，上海 200240）

0 引言

目前我國在自動化集裝箱港口核心技術智能化管理與控制系統領域剛剛起步，與發達國家相比經驗與技術基礎還相對薄弱，需要實現港口運營的數字化、信息化和智能化，以突破國外技術壁壘，打造自主品牌。

自動化港口設備智能管理與控制系統主要包括整體調度、集卡調度、流機調度和場橋調度4個部分，如圖1 所示。其中場橋調度關系到集裝箱在堆場中的運輸效率，需要結合堆存管理、集卡、流機調度和總體調度等，在合適的時機需要選擇合適的場橋，在調度過程中同時解決場橋間的協同作業問題，實現合理避讓，以提高作業效率。

圖1 自動化港口示意圖Fig.1 Schematic diagram of the automated port

近年，國外學者研究了一些有關集裝箱碼頭場橋調度問題的方案。He 等[1]研究了場橋調度與岸橋調度的綜合問題，并將問題表述為混合整數編程模型（MIP），綜合考慮了場橋、岸橋在運行過程中能量消耗。同時，整合了遺傳算法和粒子群算法進行求解。Galle 等[2]將集裝箱碼頭堆場中場橋調度問題與集裝箱搬遷問題相結合，考慮了安排存儲、檢索和搬遷請求以及決定存儲和搬遷位置等因素，提出了一個啟發式的局部搜索方案來進行求解。Kim 等[3]研究了碼頭起重機的調度問題，建立了混合整數算法模型，該模型考慮了與起重機運行過程相關的各種約束，通過一種啟發式搜索算法來獲取最優解。Gharehgozli 等[4]研究了單場橋的調度問題，以場橋移動的時間作為目標函數，并應用了精確算法，為后續學者的研究提供了重要參考。Ma 等[5]考慮到了在實際場橋作業任務中的時間不確定性問題，并建立了兩階段的隨機混合整數模型，對小規模的實例提出了一個整數L 型方法，對大規模的實例采用模擬退火算法進行求解，對場橋實際運作有較好的模擬與優化能力。Mark 等[6]研究相鄰場橋之間的干擾問題，這種干擾會導致一臺場橋的移動被相鄰的場橋所阻擋，通過使場橋完成所有調度任務花費時間最短建立了相應數學模型，提出了一種新的混合優化算法，通過結合遺傳算法和禁忌搜索方法（GATS）進行求解，在遺傳算法的基礎上將任務時間減少了20%。

國內也有很多學者針對場橋調度問題開展了相關研究。例如，針對進口箱堆場的擁塞問題，鄭紅星等[7]研究了兩部場橋運作下的場橋調度問題，設計了相應數學優化模型，針對遺傳算法中部分子代不可行的問題引入檢測修復算子，自動修正任務編碼序號來獲得可行方案。初良勇等[8]對港口集裝箱場橋的調度問題進行系統化研究。他們研究了整片箱區的調度優化模型，多方面考慮了軌道吊移動距離、時間以及場橋運行過程中產生的各種等待時間等因素，最終使模型更符合現實情況。由韓曉龍等[9]提出，以總用時最短為目標的場橋裝載調度任務混合整數規劃模型可通過啟發式算法或模擬退火算法求解，研究表明，隨著貝位數和集裝箱種類的增多，使用模擬退火算法可節省更多時間。鄭宇超等[10]同時考慮了場橋調度作業過程中的能源消耗與工作效率兩方面的問題，通過轉換場橋調度問題模型來進行求解，使得場橋調度模型求解結果更精確。尹延冬等[11]針對集卡到達時間不確定的問題，將由此產生的搗箱問題加入到數學模型中，構建了基于領域搜索的啟發式算法，最后設計了多種算例實驗驗證了模型的有效性。

綜上所述，當前已出現多種解決自動化集裝箱港口場橋調度問題的方法。然而，場橋調度是NP 難問題，且集裝箱在堆場中涉及復雜的作業流程，不同調度方案對總成本影響很大。因此，研究結合不同場景與不同調度策略來優化場橋調度方案具有重要意義。

1 問題描述

自動化集裝箱港口作業任務基本由以下幾種類型組成：岸橋的裝船任務、卸船任務，閘口的進、提箱等任務，以及場橋的集裝箱搬運任務。其中岸橋與場橋是集裝箱港口碼頭中最關鍵的設備，承擔了主要的集裝箱搬運任務。岸橋的裝、卸船任務在系統中被納入橋機作業計劃（CWP）中，由于需要保證船期即岸橋的作業效率，裝、卸船任務的作業需要按照CWP 保證其執行效率。而對于進、提箱任務，碼頭一般對外集卡有最晚服務時間的承諾，相關設備如圖2 所示。

圖2 岸橋與場橋自動化設備與集成Fig.2 Automation equipment and integration for shore crane and yard crane

針對場橋的進、提箱任務通常采取的策略一般是場橋優先服務先到達的集卡，這種策略的優勢在于能較好地避免部分集卡的等待時間過長，同時，也便于整體調度與管理。本文研究的場橋調度問題中場橋對于集卡的服務策略采用先到先得策略。

在集裝箱碼頭中每一個集裝箱所在的位置都有一個相應的編號，而編號包含了該集裝箱所在的箱區、貝位、列、層4 種位置信息。場橋能在箱區中進行移動，完成處在不同位置集裝箱的搬運任務。

本文研究的場橋搬運場景是建立在貝位兩側進出箱模式的基礎上。貝位兩側進出箱模式是指集卡在進行集裝箱裝卸時，不只在單側通道，而是在貝位兩側通道同時進行，如圖3 所示。在這種情況下，集卡能通過選擇不同的通道提前到達目標集裝箱所在的位置，避免只存在單側通道時，集卡需要等待前方集卡完成搬運任務后再到達指定位置的情況，導致集卡不能提前就位，如圖4所示。而在貝位兩側進出箱模式下，場橋完成當前搬運任務后，只需移動到下一任務地點，無需等待集卡可能存在的移動時間，使得整體進、提箱任務完成的效率更高。

圖3 貝位兩側進出箱模式示意圖Fig.3 Double-side of bay mode of transporting container

圖4 貝位單側進出箱模式示意圖Fig.4 Single-side of bay mode of transporting container

2 場橋調度模型

2.1 模型的假設條件

為了降低算法的復雜度同時使模型進行簡化，設定一些假設條件來對模型進行約束。假設條件如下：

1）考慮1 臺場橋情況下的調度情況；

2）所有待操作的任務均位于同一箱區的同一貝位；

3）集裝箱所對應的集卡到達后再開始裝卸。

2.2 參數設定

場橋調度模型中涉及的參數與相關變量符號如表1 所示。

表1 參數與相關變量Table 1 Parameters and related variables

2.3 目標函數的建立

目標函數如式（1）所示，指在每個任務周期內，完成所有場橋調度任務的時間最小化，最終使得單個任務調度內完成任務的效率最高。

2.4 約束條件

本文建立的模型是混合整數線性規劃（Mixed Integer Linear Problem，MILP）模型，式（2）是對決策變量xij與yi之間的邏輯關系進行約束；式（3）是對每個場橋調度任務完成時間的約束；式（4）表示場橋從任務i 移動到任務j 時所花費距離；式（5）表示場橋在任務間移動時花費的時間；式（6）、式（7）通過約束關系確定了任務的相鄰情況與任務之間的先后關系，通過設置這兩類變量有助于定義簡潔的約束方程；式（8）是對任務開始時間的約束，每一個任務至少是在集卡到達泊位后開始，該約束同時考慮了集卡到達箱區的時刻與集卡到達對應集裝箱所在位置需要花費的時間，并且，由于本文的研究基于貝位兩側進出箱模式，不需要考慮鄰近任務中集卡出現排隊的情況。式（9）也是對任務開始時間的約束，場橋作業任務應該在上一個任務完成并且場橋移動到下一個任務位置后再開始；式（10）限制了參數fi，si的符號。

3 算法求解設計

因為場橋調度是NP 難問題，需要設計相應的啟發式算法進行求解。本文中使用了遺傳算法求解問題，該算法是一種經典的啟發式算法。該算法從任何給定的初始種群開始，并通過模擬自然選擇、交叉和變異等過程不斷更新種群，以獲得更優的解決方案。另外，本文在傳統的遺傳算法的基礎上，增加了改進措施。傳統遺傳算法在每次更新候選集后并沒有對子代的選擇率、變異率進行調整，依然采用初始設置恒定的參數值。而在遺傳算法實際迭代過程中，每代產生的新的種群特征存在差異。針對代際間的差異采取的策略是通過判斷子代適應度的離散程度來選擇合適的參數。算法流程框圖如圖5 所示。

圖5 改進遺傳算法程序框圖Fig.5 Improved genetic algorithm program

3.1 染色體編碼

圖6 是一條染色體，其中的pi代表了單次場橋調度任務的編號，任務編號在染色體中所處的位置對應于場橋調度任務的先后順序，例如第k個基因片段上的調度任務pi表示任務pi在第k 次場橋調度任務中進行。

圖6 染色體編碼Fig.6 Chromosome coding

3.2 染色體選擇

對染色體進行選擇的目的在于防止候選集不斷膨脹，避免計算成本不斷增加。本文中染色體選擇采取的策略是精英策略，保留候選集中完成場橋調度任務總用時較小的子代，同時剔除適應度較大的子代。假設第k 輪迭代的種群大小為n，根據種群適應度的分布情況，選擇隨機選擇的概率ρi和種群保留率γi，下一代初始種群的數量為nγi，通過選出適應度排在前nγi的染色體后，再對新的候選集中染色體按照隨機選擇概率ρi進行選擇，如圖7 所示。

圖7 染色體選擇Fig.7 Chromosome selection

3.3 染色體交叉

結合本文的編碼方式，先選出候選集中的兩個父代場橋調度方案，選擇其中的一個基因片段pi，假設該基因片段分別位于染色體的第m、n 兩個位置上，交換基因j 在兩個片段上的位置，即交換任務j 在兩個調度方案中的執行順序。需要注意的是，由于基因j 在兩個父代染色體上的位置都發生改變，對應于m～n 片段中間的基因片段位置也會同步相應調整，如圖8 所示。

圖8 染色體交叉Fig.8 Chromosome crossover

3.4 染色體變異

染色體變異的目的與染色體交叉相同，都是為了產生新的種群來尋找更優解。本文采取的染色體變異方式如圖9 所示。選取一條父代染色體，交換i、j 兩個基因片段之間所有基因片段的順序，即使任務i 到任務j 之間的所有任務倒序，從而產生新的子代。為了使得算法跳出局部最優解的能力更強，在一次迭代過程中，允許一條染色體進行多次變異。

圖9 染色體變異Fig.9 Chromosome mutation

3.5 染色體適應度計算

適應度的計算是對候選集中的調度方案進行評估，本文以式（1）作為適應度函數，通過提取候選集中每條染色體上的場橋調度方案信息，同時代入給定的場景信息，分別計算候選集中各染色體適應度。

4 案例驗證

本文以某港口的運行數據為例，每次任務周期內安排20 項場橋調度任務。分別采用傳統的遺傳算法與改進后的遺傳算法進行求解，同時迭代1 000 次，求解出的局部最優解隨迭代次數變化如圖10 所示。

圖10 遺傳算法改進前后對比Fig.10 Comparison of genetic algorithms before and after improvement

從最終改進前后求解出的局部最優解來看，改進后的遺傳算法求解效果明顯優于改進前，最終完成所有調度任務的用時減少了18.8%。從原理上分析，改進后的遺傳算法針對代際間適應度表現的差異調整選擇、變異的參數，能有效避免在選擇、變異過程中丟失種群的多樣性，在迭代過程中能減少候選集中結構相似、適應度相近染色體的產生，從而使求解過程中跳出局部最優解的概率增加。

通過仿真驗證，本文采用的貝位兩側進出箱模式與改進的遺傳算法在傳統模型的基礎上能有效提高場橋調度任務完成的效率、降低調度所需總時間，提高港口場橋調度效率。

5 結語

本文研究了自動化集裝箱港口場橋調度問題。采用貝位兩側進出箱模式來避免場橋調度過程中集卡在單側通道等待問題。另外，建立了場橋調度優化問題模型，并采用改進的遺傳算法求解。分析了每次迭代過程中的適應度離散程度，并相應地調整選擇、變異的參數。然后，參考了港口實際運行數據并代入到本文的模型中進行檢驗。最終案例分析表明，改進的遺傳算法相對于傳統的遺傳算法有明顯的改善，在避免迭代過程中局部最優解方面表現得更為出色。