葉軍，羅浩銘，張先燏

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

0 引言

目前我國在自動化集裝箱港口核心技術(shù)智能化管理與控制系統(tǒng)領(lǐng)域剛剛起步，與發(fā)達國家相比經(jīng)驗與技術(shù)基礎(chǔ)還相對薄弱，需要實現(xiàn)港口運營的數(shù)字化、信息化和智能化，以突破國外技術(shù)壁壘，打造自主品牌。

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

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

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

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

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

1 問題描述

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

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

針對場橋的進、提箱任務(wù)通常采取的策略一般是場橋優(yōu)先服務(wù)先到達的集卡，這種策略的優(yōu)勢在于能較好地避免部分集卡的等待時間過長，同時，也便于整體調(diào)度與管理。本文研究的場橋調(diào)度問題中場橋?qū)τ诩ǖ姆?wù)策略采用先到先得策略。

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

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

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

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

2 場橋調(diào)度模型

2.1 模型的假設(shè)條件

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

1）考慮1 臺場橋情況下的調(diào)度情況；

2）所有待操作的任務(wù)均位于同一箱區(qū)的同一貝位；

3）集裝箱所對應(yīng)的集卡到達后再開始裝卸。

2.2 參數(shù)設(shè)定

場橋調(diào)度模型中涉及的參數(shù)與相關(guān)變量符號如表1 所示。

表1 參數(shù)與相關(guān)變量Table 1 Parameters and related variables

2.3 目標函數(shù)的建立

目標函數(shù)如式（1）所示，指在每個任務(wù)周期內(nèi)，完成所有場橋調(diào)度任務(wù)的時間最小化，最終使得單個任務(wù)調(diào)度內(nèi)完成任務(wù)的效率最高。

2.4 約束條件

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

3 算法求解設(shè)計

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

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

3.1 染色體編碼

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

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

3.2 染色體選擇

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

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

3.3 染色體交叉

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

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

3.4 染色體變異

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

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

3.5 染色體適應(yīng)度計算

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

4 案例驗證

本文以某港口的運行數(shù)據(jù)為例，每次任務(wù)周期內(nèi)安排20 項場橋調(diào)度任務(wù)。分別采用傳統(tǒng)的遺傳算法與改進后的遺傳算法進行求解，同時迭代1 000 次，求解出的局部最優(yōu)解隨迭代次數(shù)變化如圖10 所示。

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

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

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

5 結(jié)語

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