自動化集裝箱碼頭岸邊集裝箱起重機(jī)與自動導(dǎo)引車協(xié)同調(diào)度研究

吳曉曉 吳敬兵

武漢理工大學(xué) 武漢 430070

0 引言

自動化設(shè)備和人工智能算法的普及極大地提高了集裝箱港口碼頭的作業(yè)效率。港口的運(yùn)作效率是船舶公司選擇掛靠的重要因素，高效運(yùn)作的港口可以縮短船舶的在港時(shí)間，降低碼頭作業(yè)成本。自動化港口的泊位、水平裝卸設(shè)備和水平運(yùn)輸設(shè)備等港口資源設(shè)備因價(jià)格昂貴，無法大規(guī)模購買和建造，故需對其進(jìn)行合理調(diào)度。水平裝卸系統(tǒng)主要是指岸邊橋式起重機(jī)（以下簡稱岸橋）和場堆橋式起重機(jī)（以下簡稱場橋），岸橋是自動化碼頭作業(yè)中裝卸的重要組成部分，針對停靠在港口船舶上的集裝箱進(jìn)行裝卸。水平運(yùn)輸設(shè)備自動導(dǎo)引車( Automated Guided Vehicle，AGV）是連接自動化碼頭裝卸設(shè)備的樞紐，岸橋和AGV的調(diào)度影響著碼頭整體的運(yùn)作效率。

岸橋的調(diào)度問題主要針對其作業(yè)順序進(jìn)行優(yōu)化，研究表明：岸橋的調(diào)度問題為NP-難問題，精確求解這類問題往往較困難[1]。Dong L等[2]研究了岸橋調(diào)度對于碼頭作業(yè)效率的影響，建立了一個混合整數(shù)規(guī)劃模型，同時(shí)設(shè)計(jì)了遺傳算法和2種基于分段編碼技術(shù)的改進(jìn)算法求解。梁承姬等[3]重點(diǎn)研究了岸橋調(diào)度和分配問題，以船舶在港時(shí)間最小為目標(biāo)，建立了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)遺傳算法進(jìn)行求解。Dominik K等[4]為了精確研究岸橋的調(diào)度問題，以最小化的最大岸橋作業(yè)完工時(shí)間為目標(biāo)，提出了一種解決岸橋調(diào)度的動態(tài)編程的方法，用動態(tài)規(guī)劃算法求解。水平運(yùn)輸系統(tǒng)作業(yè)效率的提高能提升裝卸設(shè)備的作業(yè)效率，進(jìn)而提高整個自動化碼頭的作業(yè)效率。但是過多地投入AGV會造成AGV之間的互相等待，導(dǎo)致運(yùn)輸區(qū)域的擁堵，故在滿足任務(wù)時(shí)間的要求下應(yīng)盡量減少AGV使用數(shù)量。Jin J等[5]采用調(diào)度的優(yōu)先級次序方法解決自動化港口碼頭AGV的調(diào)度問題；郭保青等[6]使用蟻群算法求解倉庫中多AGV調(diào)度的路徑問題。

自動化碼頭作業(yè)系統(tǒng)實(shí)際運(yùn)作過程中并不是靠單一的設(shè)備調(diào)度，而是需要各系統(tǒng)間的協(xié)同調(diào)度。關(guān)于子系統(tǒng)之間的調(diào)度, 目前研究的重點(diǎn)主要集中岸橋和AGV小車之間的聯(lián)合調(diào)度、AGV和場橋之間的聯(lián)合調(diào)度。He J等[7]研究了岸橋、AGV和場橋的協(xié)同調(diào)度問題，以最小化場橋成本為目標(biāo)，建立了混合整數(shù)規(guī)劃的模型，用分支定界法進(jìn)行求解。Zhao J等[8]研究了岸橋和AGV的綜合調(diào)度問題，同時(shí)以最小化集裝箱船卸載任務(wù)完成時(shí)間開發(fā)了粒子群的算法求解。自動化碼頭的調(diào)度是一個復(fù)雜的整體系統(tǒng)，對于單一的目標(biāo)優(yōu)化對提高自動化碼頭作業(yè)效率并不顯著，也不符合實(shí)際情況。然而，上述文獻(xiàn)大多集中于以單一目標(biāo)，研究2個子系統(tǒng)之間的協(xié)同調(diào)度問題，并不能反映真實(shí)港口調(diào)度過程中對于多目標(biāo)優(yōu)化的需求。本文針對于自動化港口的雙岸橋小車和AGV的2個子系統(tǒng)間的調(diào)度進(jìn)行研究，以最小化最大完成時(shí)間和最小化AGV行駛距離為目標(biāo)，建立混合整數(shù)規(guī)劃模型，同時(shí)用改進(jìn)的遺傳算法進(jìn)行求解。

1 問題描述

按照自動化碼頭功能進(jìn)行分類，其作業(yè)區(qū)可分為泊位區(qū)、岸橋作業(yè)區(qū)、水平運(yùn)輸區(qū)、堆場作業(yè)區(qū)等區(qū)域。自動化港口的布局如圖1所示。在碼頭調(diào)度過程中，任何一個最優(yōu)的作業(yè)流程往往會因另一個流程未能與其對接而無法順利實(shí)施，這就要求對碼頭作業(yè)進(jìn)行合理的規(guī)劃調(diào)度。

圖1 自動化港口布局圖

自動化碼頭的功能區(qū)域并不是完全獨(dú)立而是相互分工合作的。一般情況下，自動化港口在抵達(dá)港口前會把船舶的船型、到港時(shí)間、裝載集裝箱量和船舶預(yù)計(jì)離港時(shí)間等信息上報(bào)給碼頭的調(diào)度者，工作人員依據(jù)這些信息和設(shè)備狀態(tài)制定出相應(yīng)的泊位和岸橋計(jì)劃。船舶?？扛劭诤?，集裝箱碼頭會配置一定數(shù)量的岸橋?qū)Υ斑M(jìn)行裝卸作業(yè)。岸橋的調(diào)度主要是通過制定岸橋作業(yè)計(jì)劃來銜接岸邊和堆場作業(yè)的工作，以減少岸邊和箱區(qū)的作業(yè)沖突, 從而進(jìn)一步提高碼頭的整體運(yùn)作效率。雙小車岸橋主要由主小車和后小車構(gòu)成，其作業(yè)流程為：在主小車接收到指令后，將船舶貝位上的集裝箱拾起后放置在岸橋的中轉(zhuǎn)平臺上。雙小車岸橋的中轉(zhuǎn)平臺可同時(shí)容納2個40 ft或4個20 ft的集裝箱。然后，雙小車岸橋的門架小車從中轉(zhuǎn)平臺上將集裝箱拾起后放置在岸橋下方等待的AGV上。雙岸橋小車的模型如圖2所示。相較于傳統(tǒng)集裝箱裝卸作業(yè)流程，自動化碼頭裝卸作業(yè)的特點(diǎn)是使用了AGV來替代傳統(tǒng)拖車作業(yè)。AGV按照預(yù)先設(shè)定的軌道將集裝箱從岸橋運(yùn)輸?shù)綀鰳蜻M(jìn)行堆垛。另外，雙小車岸橋中轉(zhuǎn)平臺能將集裝箱暫存，很好地解決了岸橋和AGV之間的耦合問題，盡可能地減少AGV小車等待岸橋的時(shí)間，實(shí)現(xiàn)高效的自動化港口裝卸作業(yè)。

圖2 雙小車岸橋示意圖

顯而易見，自動化港口的岸橋調(diào)度和AGV調(diào)度計(jì)劃共同影響著整個碼頭。岸橋AGV協(xié)同調(diào)度需要充分考慮岸橋和AGV之間的相互關(guān)聯(lián)和相互影響關(guān)系，使岸橋和AGV相互銜接順利。本文重點(diǎn)研究雙小車岸橋與AGV的協(xié)同調(diào)度問題，通過對主小車和門架小車的調(diào)度實(shí)現(xiàn)雙小車岸橋與AGV調(diào)度優(yōu)化，使用遺傳算法求解，給出最優(yōu)的雙小車岸橋和AGV調(diào)度方案，并對算例進(jìn)行分析。

2 模型建立

2.1 模型假設(shè)

模型假設(shè)條件：1）岸橋QC和雙自動堆垛起重機(jī)ASC一次只能裝載或卸載1個集裝箱；2）AGV小車一次只能運(yùn)輸1個集裝箱；3）不考慮岸橋QC之間的干擾沖突；4）AGV小車勻速行駛；5）場橋ASC不能跨堆場作業(yè)。

2.2 目標(biāo)函數(shù)

2.3 集合與參數(shù)

N為進(jìn)口集裝箱集合，n∈N；L為出口集裝箱集合，l∈L；I為所有任務(wù)（集裝箱）的集合，I＝N∪L，i，i′∈I，其中0和f為虛擬起始任務(wù)和虛擬結(jié)束任務(wù)，虛擬任務(wù)的作業(yè)時(shí)間都為0；Q為QC集合，q∈Q；A為AGV集合，a，a′∈A；B為ASC集合，b∈B；K為所有設(shè)備的集合，K＝Q∪A∪B；M為一個很大的正整數(shù)；J為路徑網(wǎng)絡(luò)中的所有節(jié)點(diǎn)集合，s、m、s′、m′∈J；G為節(jié)點(diǎn)之間的有向線段；v為AGV的速度；C為所有集裝箱的最大完工時(shí)間；dms為節(jié)點(diǎn)s與節(jié)點(diǎn)m之間的距離；SQ為岸橋Q的中轉(zhuǎn)平臺可容納的集裝箱數(shù)量。

2.4 變量

1）0-1變量

在設(shè)備k上，Xkii′： Xkii′＝1，集裝箱i先于i′處理，Xkii′＝0，否則；Yki：Yki＝1，設(shè)備k處理集裝箱i，Yki＝1，否則；Zsm：Zsm＝1，通過節(jié)點(diǎn)s與節(jié)點(diǎn)m之間的連接路徑，Zsm＝0，否則；Pas：Pas＝1，AGV a經(jīng)過節(jié)點(diǎn)s，Pas＝0，否則。

2)非0-1變量

tsqi為QC q開始處理集裝箱i的時(shí)間；teqi為QC q處理集裝箱i的時(shí)間，對于進(jìn)口箱表示QC q將集裝箱從船舶送到中轉(zhuǎn)平臺再運(yùn)送到AGV上的時(shí)間，對于出口箱表示QC q將集裝箱從AGV轉(zhuǎn)移到中轉(zhuǎn)平臺再運(yùn)送到船舶上的時(shí)間；tsai為AGV a開始處理集裝箱i的時(shí)間，對于進(jìn)口箱表示AGV到達(dá)QC與AGV轉(zhuǎn)移點(diǎn)的時(shí)間，對于出口箱表示AGV到達(dá)ASC與AGV轉(zhuǎn)移點(diǎn)的時(shí)間；teai為AGV a處理集裝箱i的時(shí)間，對于進(jìn)口箱表示AGV將集裝箱運(yùn)送至ASC與AGV轉(zhuǎn)移點(diǎn)的時(shí)間，對于出口箱表示AGV將集裝箱運(yùn)送至QC與AGV轉(zhuǎn)移點(diǎn)的時(shí)間；tsbi為ASC b開始處理集裝箱i的時(shí)間；tebi為ASC b處理集裝箱i的時(shí)間，對于進(jìn)口箱表示ASC b將集裝箱從轉(zhuǎn)移點(diǎn)運(yùn)送到堆場位置的時(shí)間，對于出口箱表示ASC b將集裝箱從堆場位置運(yùn)送到AGV上的時(shí)間；tae，sm為AGV a進(jìn)入節(jié)點(diǎn)s與節(jié)點(diǎn)m之間的連接路徑的時(shí)間；tao，sm為AGV a離開節(jié)點(diǎn)s與節(jié)點(diǎn)m之間的連接路徑的時(shí)間。

2.5 約束條件

1）上層模型

由以上公式可知，式（1）、式（2）保證每臺QC的初始任務(wù)為虛擬任務(wù)0，結(jié)束任務(wù)為虛擬任務(wù)f；式（3）保證QC處理每個集裝箱的作業(yè)順序；式（4）保證每個集裝箱只能被1臺QC處理；式（5）AGV需提前到達(dá)轉(zhuǎn)移點(diǎn)等待QC；式（7）、式（8）保證在同一臺QC上前一個集裝箱的完成作業(yè)時(shí)間早于下一個集裝箱的開始作業(yè)時(shí)間；式（9）、式(10)保證每臺AGV的初始任務(wù)為虛擬任務(wù)0，結(jié)束任務(wù)為虛擬任務(wù)f；式(11) 保證AGV處理每個集裝箱的作業(yè)順序；式(12)保證每個集裝箱只能被1臺AGV處理；式(13)、式(14)保證同一臺AGV運(yùn)輸?shù)?個集裝箱的先后時(shí)間順序；式(15)、式(16)需提前到達(dá)轉(zhuǎn)移點(diǎn)等待ASC；式(17)、式 (18)保證每臺ASC的初始任務(wù)為虛擬任務(wù)0，結(jié)束任務(wù)為虛擬任務(wù)f；式(19)保證ASC處理每個集裝箱的作業(yè)順序；式(20)保證每個集裝箱只能被1臺ASC處理；式(21)、式（22）保證同一臺ASC處理2個集裝箱的先后時(shí)間順序；式（23）表示每個中轉(zhuǎn)平臺上的集裝箱數(shù)量不超最大容量限制2；式(24)路徑選擇約束；式(25)節(jié)點(diǎn)約束，同一節(jié)點(diǎn)只能通過1臺AGV；式(26)AGV a進(jìn)入和離開路徑的時(shí)間關(guān)系；式(27)連續(xù)2臺AGV進(jìn)入同一路徑的時(shí)間約束；式(28)連續(xù)2臺AGV離開同一路徑的時(shí)間約束；式(29)、式(30)QC與AGV轉(zhuǎn)移集裝箱的時(shí)間小于AGV離開路徑的時(shí)間；式(31) 、式(32)ASC與AGV轉(zhuǎn)移集裝箱的時(shí)間小于AGV離開路徑的時(shí)間。

3 遺傳算法

遺傳算法的前提條件為：1）岸橋處理集裝箱的順序已知；2）岸橋的優(yōu)先級高于小車，在小車的分配前提條件下可讓小車等待岸橋，應(yīng)盡量避免岸橋等待小車；3）在此過程中，獲得每AGV任務(wù)的等待時(shí)間和空載時(shí)間。

上述岸橋調(diào)度和AGV調(diào)度屬于典型的NP-Hard問題，對于這種相對較大的實(shí)例，數(shù)學(xué)方法無法在合理的計(jì)算時(shí)間內(nèi)為大規(guī)模集成調(diào)度問題找到最佳解決方案。大量研究表明遺傳算法可以解決集裝箱碼頭各種調(diào)度計(jì)劃問題，如岸橋調(diào)度、泊位調(diào)度、場橋起重機(jī)調(diào)度和AGV的調(diào)度等。遺傳算法是一種基于自然選擇和自然遺傳學(xué)的隨機(jī)搜索技術(shù)，是一種用于尋找優(yōu)化問題解決方案的著名元啟發(fā)式算法。GA的整體框架如圖3所示。本文使用Matlab 2020b，利用分別使用遺傳算法和禁忌搜索遺傳算法求解模型的解。

圖3 遺傳算法流程圖

3.1 染色體的編碼

采用整數(shù)編碼方法隨機(jī)生成一條染色體，每條染色體代表模型的一個解。集裝箱的編號就是構(gòu)成染色體的基因值，集裝箱在染色體的位置即為集裝箱任務(wù)的優(yōu)先順序。表1為染色體編碼的分布情況，假設(shè)共有2個岸橋QC、10個集裝箱任務(wù)、5個AGV小車來運(yùn)輸集裝箱。

表1 染色體編碼分布示意表

3.2 初始種群和適應(yīng)度函數(shù)

由于遺傳算法的搜索空間較大，在實(shí)際過程中常采用隨機(jī)生成種群的方式來增大種群個體的多樣性，盡可能增加遺傳算法的全局搜索能力，避免陷入解的局部最優(yōu)，以維持種群的多樣性。本文通過隨機(jī)生成n個染色體的全排列，就構(gòu)成了初始種群。

在遺傳算法中，染色體的適應(yīng)度值越高，則其被留存在子代的概率就越高。對于已經(jīng)建立的數(shù)學(xué)模型問題，通常直接采用模型的目標(biāo)函數(shù)值作為適應(yīng)度函數(shù)。本文采用適應(yīng)度函數(shù)值取目標(biāo)函數(shù)的倒數(shù)，F(xiàn)＝1/f，即最小化岸橋最大完工時(shí)間的倒數(shù)。

3.3 選擇運(yùn)算

在選擇算子時(shí)，采取的策略是輪盤賭和精英選擇策略保留的方式。個體被選中的概率與適應(yīng)度值有關(guān)，遺傳染色體個體的適應(yīng)度值越大，則其被選中的概率就越大。遺傳算法的選擇概率設(shè)置為0.9，使用輪盤賭選擇方式選擇產(chǎn)生的種群。選擇運(yùn)算要求適應(yīng)度高的個體將會有更多的機(jī)會遺傳到下一代群體中選擇策略。采用輪盤賭方法進(jìn)行選擇的策略是：在選擇過程中，采用比較經(jīng)典的精英選擇+輪盤賭的選擇方式。使用輪盤賭的方式選擇2個父代中的個體進(jìn)行選擇操作，具體步驟為：1）選擇2個父代中的個體；2）對2個父代的個體進(jìn)行n次交叉操作；3）計(jì)算這2個子代的適應(yīng)度值，并記為i1、i2；4）選擇max(i2,i2)最大值的一組結(jié)果（用L表示）；5）與父代的2個個體比較，比較父代適應(yīng)度值與L的大??；6）選擇大的作為新一代的2個個體，其目的是為了產(chǎn)生更好的后代。

輪盤賭的具體策略是先計(jì)算出群體中所有個體適應(yīng)度的總和，再計(jì)算出每個個體的相對適應(yīng)度大小，即是每個個體被遺傳到下一代群體中的概率。每個概率值組成一個區(qū)域，全部概率值之和為1。最后再產(chǎn)生一個0～1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個概率區(qū)域內(nèi)來確定各個個體被選中的次數(shù)。

3.4 交叉運(yùn)算

交叉運(yùn)算的目的是使遺傳算法中產(chǎn)生新的個體過程。使用交叉概率（交叉率Pc）相互交換2個個體之間的部分染色體，本文采用雙切點(diǎn)交叉法。從種群中選擇染色體P1、P2為父代，新的個體C1、C2 為子代。具體步驟為：1）選2個切點(diǎn)；2）交換父代切點(diǎn)內(nèi)部分；3）將未換部分按映射關(guān)系恢復(fù)合法性；4）調(diào)整局部優(yōu)先級，過程如表2所示。

表2 調(diào)整局部優(yōu)先級過程的染色體示例表

3.5 變異運(yùn)算

遺傳算法的變異運(yùn)算操作是對染色體個體的某一基因或某些基因按照變異率Pm進(jìn)行改變。其具體操作為選擇一個父代染色體P1，然后隨機(jī)交換染色體上。隨機(jī)地在染色體上選取2個位置，交換2個基因的序號，編碼合法，則生成子代 C1，完成染色體的變異操作。

4 數(shù)值試驗(yàn)

為了評估模型和算法的有效性，本文針對分別針對小規(guī)模問題和大規(guī)模問題進(jìn)行了驗(yàn)證。評價(jià)的指標(biāo)為最佳適應(yīng)度值（OFV）和求解時(shí)間，為了避免算法的隨機(jī)性導(dǎo)致的誤差，每個實(shí)驗(yàn)重復(fù)進(jìn)行10次。遺傳算法的參數(shù)設(shè)置不同，對于算法的求解結(jié)果不同，本文所設(shè)置的遺傳算法的參數(shù)為：最大迭代數(shù)為200、交叉概率0.85、變異概率0.2、種群規(guī)模為100個。

4.1 參數(shù)設(shè)置

以某港實(shí)際運(yùn)行情況為例，集裝箱的數(shù)量從4到70不等。假設(shè)共有2～3臺岸橋、4～12輛AGV。岸橋QC作業(yè)將集裝箱從船舶卸載到AGV或?qū)⒓b箱從AGV裝載到船舶上的時(shí)間服從均勻分布U(30,180)s；ASC場堆起重機(jī)的作業(yè)時(shí)間服從均勻分布U(60,140)s；AGV行駛路網(wǎng)的長度為200 m，寬度為150 m；道路為單向，同時(shí)道路的寬度忽略不計(jì)；場堆的長度為200 m，寬度為200 m；AGV行駛速度為5 m/s，雙小車岸橋中轉(zhuǎn)平臺的容量為2。

4.2 實(shí)驗(yàn)結(jié)果

1）小規(guī)模實(shí)驗(yàn)結(jié)果

如表3所示，通過2種方法的對比，禁忌搜索遺傳算法可獲得近似最優(yōu)解。與遺傳算法對比，禁忌搜索遺傳算法能很好地解決遺傳算法因種群多樣性降低導(dǎo)致的早熟特征，從而更好地尋求最優(yōu)解，避免陷入局部最優(yōu)解。依據(jù)表中數(shù)據(jù)，GA的計(jì)算時(shí)間57.3～397.1 s波動劇烈，而TSGA的計(jì)算時(shí)間116.3～587.3 s有波動，這表明使用TSGA相比GA在任務(wù)量增加時(shí)相對平穩(wěn)，由此判斷在大任務(wù)量時(shí)TSGA表現(xiàn)要優(yōu)于GA，兩者算法的差值能接受。

表3 禁忌搜索遺傳算法和遺傳算法對比(小規(guī)模)

隨著集裝箱任務(wù)數(shù)量的增加，2種算法的運(yùn)行時(shí)間都逐漸變長，最優(yōu)化求解差距亦較大，其中TSGA的最優(yōu)化結(jié)果小于GA，證明了TSGA算法在解決此類問題的有效性。從算例4和算例5可以看出，集裝箱的任務(wù)數(shù)量一定時(shí)候，AGV的數(shù)量越多效率越高。從算例8和算例9可以看出，盡管任務(wù)數(shù)量增加，但增加AGV的數(shù)量也能顯著降低OFV值，這表明當(dāng)增加任務(wù)的數(shù)量時(shí)，增加AGV小車的數(shù)量可以減少集裝箱的最大化完工時(shí)間，從而提高碼頭的工作效率。

以算例4為例獲得岸橋調(diào)度順序：岸橋1的集裝箱處理順序?yàn)?-10-9-4-3；岸橋2的集裝箱處理順序?yàn)?-1-5-7-8；AGV1的集裝箱處理順序?yàn)?-8；AGV2的集裝箱處理順序?yàn)?-7；AGV3的集裝箱處理順序?yàn)?-5； AGV4的集裝箱處理順序?yàn)?0-4；AGV5的集裝箱處理順序?yàn)?-3。

2）大規(guī)模實(shí)驗(yàn)結(jié)果

TSGA和GA 的Matlab 求解的結(jié)果如表4所示。從大規(guī)模算例實(shí)驗(yàn)結(jié)果來看，當(dāng)集裝箱數(shù)量超過30個，TSGA和GA的求解時(shí)間相對小規(guī)模實(shí)驗(yàn)都有顯著的增加，不同于小規(guī)模實(shí)驗(yàn)中，TSGA算法求解時(shí)間幾乎均大于GA算法。在大規(guī)模算例中，TSGA算法的求解時(shí)間和GA算法的求解時(shí)間差距不大，甚至部分算例中TSGA算法的求解時(shí)間要短于GA算法。同時(shí)，TSGA算法求解的OFV值顯著小于GA算法，更接近最優(yōu)解，這就證明TSGA算法在求解大規(guī)模算例中相較于GA算法的優(yōu)越性。通過算例10和算例13的比較，在任務(wù)數(shù)量一定的情況下，岸橋和場區(qū)數(shù)量一定，通過增加AGV的數(shù)量可顯著降低OFV值，即提高港口作業(yè)效率。由算例17和算例18可得，當(dāng)任務(wù)數(shù)量一定時(shí)，增加AGV的數(shù)量并未降低OFV值，這表明AGV的數(shù)量并非越多越好。AGV過多可能會產(chǎn)生擁堵等情況，造成效率的降低。當(dāng)任務(wù)數(shù)逐漸增加時(shí)，相應(yīng)的OFV值也顯著增加。由于模型考慮了岸橋中轉(zhuǎn)平臺的容量限制，當(dāng)集裝箱數(shù)量過多時(shí)，也可能會造成AGV的等待導(dǎo)致時(shí)間延長、工作效率降低。綜上所述，小規(guī)模和大規(guī)模實(shí)驗(yàn)中TSGA求解的OFV值均優(yōu)于GA，同時(shí)TSGA的求解時(shí)間與GA相差不大，在大規(guī)模算例中的求解時(shí)間甚至少于GA求解時(shí)間。因此，證明了TSGA在求解此雙層模型中的有效性。

表4 禁忌搜索遺傳算法和遺傳算法對比(大規(guī)模)

圖4顯示了雙層遺傳算法的收斂性，以10個集裝箱、5個AGV、2個岸橋?yàn)槔?，說明禁忌搜索遺傳算法的收斂性的穩(wěn)定性，充分說明了設(shè)計(jì)算法的穩(wěn)定性。遺傳算法的收斂速度越快，表明求解的工作時(shí)間越短，在實(shí)際自動化港口碼頭中，更高的工作效率極為重要。圖5為AGV最短路徑規(guī)劃的調(diào)度圖。

圖4 典型遺傳算法收斂圖

圖5 典型AGV小車調(diào)度圖

5 結(jié)論

本文研究了岸橋、AGV和ASC的綜合調(diào)度問題，并進(jìn)行裝卸和卸載操作，建立了雙層模型，模型中岸橋和AGV的調(diào)度被放在上層模型，其目標(biāo)是盡可能減少集裝箱的完工時(shí)間，以降低船舶?？吭诎兜臅r(shí)間，同時(shí)結(jié)合實(shí)際約束了岸橋中轉(zhuǎn)平臺的容量為2個集裝箱。模型的下層為AGV的路徑規(guī)劃，目標(biāo)為AGV行駛的路徑最短。此類問題通常可通過遺傳算法進(jìn)行求解，但隨著任務(wù)數(shù)量的增加和岸橋AGV數(shù)量的變化，遺傳算法可能會出現(xiàn)早熟情況，導(dǎo)致最優(yōu)解的求解不準(zhǔn)確。因此，對遺傳算法加以改進(jìn)，設(shè)計(jì)了禁忌搜索遺傳算法對該問題進(jìn)行求解。結(jié)果表明，在小規(guī)模的實(shí)驗(yàn)中證明了TSGA所求得的最優(yōu)解要好于GA，同時(shí)TSGA的計(jì)算時(shí)間也與GA類似。證明了所提模型和算法的有效性，并能減少裝卸時(shí)間，提高碼頭工作效率。