吳曉曉 吳敬兵

武漢理工大學 武漢 430070

0 引言

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

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

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

1 問題描述

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

圖1 自動化港口布局圖

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

圖2 雙小車岸橋示意圖

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

2 模型建立

2.1 模型假設

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

2.2 目標函數

2.3 集合與參數

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

2.4 變量

1）0-1變量

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

2)非0-1變量

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

2.5 約束條件

1）上層模型

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

3 遺傳算法

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

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

圖3 遺傳算法流程圖

3.1 染色體的編碼

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

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

3.2 初始種群和適應度函數

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

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

3.3 選擇運算

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

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

3.4 交叉運算

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

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

3.5 變異運算

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

4 數值試驗

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

4.1 參數設置

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

4.2 實驗結果

1）小規(guī)模實驗結果

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

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

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

以算例4為例獲得岸橋調度順序：岸橋1的集裝箱處理順序為2-10-9-4-3；岸橋2的集裝箱處理順序為6-1-5-7-8；AGV1的集裝箱處理順序為9-8；AGV2的集裝箱處理順序為2-7；AGV3的集裝箱處理順序為6-5； AGV4的集裝箱處理順序為10-4；AGV5的集裝箱處理順序為1-3。

2）大規(guī)模實驗結果

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

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

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

圖4 典型遺傳算法收斂圖

圖5 典型AGV小車調度圖

5 結論

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