基于改進(jìn)遺傳算法的自動(dòng)化港口貝位兩側(cè)進(jìn)出箱模式下場(chǎng)橋調(diào)度模型研究

葉軍，羅浩銘，張先燏

（1.上海振華重工（集團(tuán)）股份有限公司，上海 200125；2.上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海 200240）

0 引言

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

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

圖1 自動(dòng)化港口示意圖Fig.1 Schematic diagram of the automated port

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

1）考慮1 臺(tái)場(chǎng)橋情況下的調(diào)度情況；

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

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

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

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

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

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

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

2.4 約束條件

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

3 算法求解設(shè)計(jì)

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

圖5 改進(jìn)遺傳算法程序框圖Fig.5 Improved genetic algorithm program

3.1 染色體編碼

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

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

3.2 染色體選擇

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

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

3.3 染色體交叉

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

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

3.4 染色體變異

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

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

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

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

4 案例驗(yàn)證

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

圖10 遺傳算法改進(jìn)前后對(duì)比Fig.10 Comparison of genetic algorithms before and after improvement

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

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

5 結(jié)語

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