自動化集裝箱碼頭AGV調度研究

黃澤乾 丁 濤 王 雅

(武漢理工大學交通學院 武漢 430063)

0 引 言

全自動化小車屬于一種自主移動的機器人，在沒有接觸控制的情況下能夠實現隔空控制貨物運輸，并且能夠提前設定運輸軌跡，從而完全實現無人化，節省人力的使用，降低工人的勞動強度，能大幅降低人工費；全自動小車全電動化，能夠充電無限續航，節省燃料費，達到節能減排、降低成本、提高效率的目的[1-3].如今碼頭前沿的擁擠較程度大，小車工作效率較低，與預想的工作效率差距較大[4].小車運行過程中需要眾多因素來對任務進行分配，從而提高碼頭前沿運行效率[5].文中旨在通過線性規劃模型，運用遺傳算法對模型進行優化求解，使小車對任務進行擇優自動選擇，選擇方法為最短路法.

1 問題描述

1.1 模型條件設置

AGV調度問題主要是從給AGV分配任務并且選擇最佳的任務順序來完成任務從而得到最短的路徑.單AGV調度的時候就相當于合理地分配任務的順序得到最短的路徑，而多AGV的調度需要將任務合理分配到每臺AGV上，并且使得總的AGV調度的路程最短，把多AGV調度的最短時間問題轉換為最短路徑問題[6-8].

對AGV小車的調度做如下假設.

1) 一般的情況下小車在運行過程中有加速和減速，但是小車的加速和減速在每次任務中都是必要的，并不影響實驗的最后結果，所以假設所有小車都是勻速行駛.

2) 假設AGV小車的通信始終都是良好的，不存在設備故障情況.

3) 當系統中有任務出現時直接把任務轉換成運輸網絡的節點i到節點j.

4) 由于集裝箱的裝載時間和卸載時間都是必需的，此處只研究通過就近點選取達到規劃路徑問題，因此，忽略集裝箱裝卸時間.

5) 在速度一定的情況下，最短時間問題可轉換為最短路徑的問題.

1.2 模型概述

在以上假設的基礎上，設置集裝箱一個碼頭的區域有a(a∈(1,2,…,m))輛AGV小車，在某一時間段內有b(b∈(1,2,…,n))個集裝箱任務需要處理，在處理任務的過程中從a輛AGV小車中隨機選取k(k≤a)輛小車去執行任務，任務的起點直接為小車的起點.本模型是AGV小車調度的路徑問題，但是設定的小車是勻速行駛，所以最短路徑轉換為最短時間問題.

在進行任務i的時候，di為任務i起點到終點做完后的最短路徑，做完任務i后做任務j,dij為任務i的終點到任務j的起點的最短路徑，其中i，j∈{1,2,…,n}.

第k輛AGV執行完第i個任務后是否繼續執行第j個任務，即

(1)

(2)

則目標函數為

min {maxg(k)=∑i∑jxijk(di+dij)}

k∈{1,2,…,a}

(3)

s.t.

(4)

j∈{1,2,…,b},k∈{1,2,…,a}

(5)

i∈{1,2,…,b},k∈{1,2,…,a}

(6)

xijk∈{0,1},i,j=1,2,…,b,k∈{1,2,…,a}

(7)

yki∈{0,1},i=1,2,…,b,k∈{1,2,…,a}

(8)

約束條件(3)為目標函數，是所有AGV在執行任務時，找出單個AGV執行任務所用的最大時間；約束條件(4)(5)(6)為每個任務都被一輛AGV執行并且只執行一次，不重復執行；約束條件(7)為AGV是否執行了任務i后再執行任務j；約束條件(8)為任務i是否被第k輛AGV執行.

該模型的意義在于每個任務都被執行并且只被一輛AGV小車執行一次，并且在AGV只有一輛的時候只制作任務執行順序，目標函數就是在滿足以上條件的情況下，使得完成這個時間段的所有任務所耗的時間最少，使得最后在完成每個任務的前提下，實現任務順序的合理分配和路徑的合理選擇[9-10].

2 遺傳算法

2.1 編碼與解碼

編碼過程 需要生成任務數和小車數的矩陣y，舉例見表1.

表1 任務和小車序號分配

若第i個任務被第k輛小車執行，那么對應的(k，i)則為1，被執行的任務不再重復執行所以其余小車對應此任務的位置均為0，因此，每一列只允許有一個1.接著在滿足一列只能有一個1的情況下只能對每一列單獨編碼.

每個任務都被AGV1小車執行，取出第一列[1,0,0]，第一列長度為3，隨機生成一個數x，對列的長度取余向0取整最后取絕對值加1，得到需要取出這一列的第幾位數，并將取出的數放入另外一個初始為空的矩陣中，刪除此列的此位數，形成一個新列，對此列重復進行直到列的元素全被取到另一個矩陣中；重復以上步驟直到每一個任務都被重新編排最后解碼形成新的矩陣y.

2.2 GA工具箱

基于建立的上述模型和對算法求解的仿真，根據模型在MATLAB中編寫遺傳算法，由于用于求解工具為gatool，因此，只需編碼、解碼和適應度函數便能滿足求解條件.

3 實驗設置

3.1 調度仿真

為了驗證上述算法的可行性，假設整個集裝箱碼頭的一個區域有六個節點(在此處各個節點可代表碼頭堆場、岸橋、倉庫、集裝箱修理場，集裝箱清潔場地等集裝箱需要搬運的場地)，各個節點之間的最短距離見表2.現在有b個任務由a輛AGV小車完成，AGV小車的行駛速度為1(將時間最短問題轉換為路徑最短問題)，這b個任務的起訖點見表3.使用MATLAB中的遺傳算法工具箱來進行求解最優解.使用默認的參數：交叉概率0.8，變異概率0.2.

表2 各節點之間的最短距離

表3 各個任務和任務的起訖點

3.2 實驗結果

在集裝箱碼頭的作業過程中，不同的任務數量需要不同數量的AGV小車來進行作業.

所以對表2任務進行了不同AGV小車數量的研究，設置AGV小車數從1～6得到了表4.

表4 不同數量的AGV對應不同的時間

將表4的數據繪制成折線圖，得到橫軸為AGV小車，縱軸為進行任務所用的時間，見圖1.

圖1 AGV數量和對應時間

由圖1可知，隨著AGV固定數量的增長，時間的減少并不是線性的，即不是固定數量的時間減少，而是凹函數形式的減少.在調用3臺AGV的到調用4臺AGV時時間的減少量明顯下降，在調用5臺到調用6臺AGV時時間沒變，出現這種情況意味著每個時間段的任務群需要對應AGV小車的數量，小車的數量過多時，時間減少量降低或幾乎不變，因此,確定合適每個時間段任務群的AGV小車調度數量是非常有必要的.

3.3 卸船調度仿真

上述實驗是假設碼頭的各個位置,比如,從集裝箱堆場到集裝箱修理廠，岸橋到堆場，岸橋到倉庫，倉庫到堆場等不同位置之間的調度，接下來模擬碼頭卸船時的AGV調度.假設岸橋用了兩個，堆場用了四個，卸一艘船，船上需要卸載的集裝箱為100TEU，使用6臺AGV小車進行作業，每輛AGV小車的運行都按雙線運行并且假設小車之間不會發生碰撞和擁堵，見表5.

表5 集裝箱碼頭的岸橋和場最短距離

假設任務見表6.

表6 執行任務表

卸船調度任務表見表7.

表7 卸船調度任務列表

由表7可知，在擬定了小車的運行路徑的時候,每輛小車的任務分配與用時仍然非常均衡.由節點順序可以看出，每一輛小車都是盡量在完成了一個調度任務后，尋找就近的岸橋進行下一個任務的調度，使得空載行駛的距離較短，比如,從1號岸橋運送集裝箱到了6號堆場后，再找到2號裝卸橋繼續作業，而不是回到1號裝卸橋，減少空載距離，每臺AGV小車任務分配得很均衡，用時都相差不大，實現了AGV小車調度高效運行.

4 結 束 語

港口中各個場地間的調度與卸船時固定路線的調度均可使用此模型，并且運用此模型對于小車的就近點選擇與路徑選擇達到了任務分配均勻的目的,建立了以最末任務結束時間最小化為目標的混合整數規劃模型，減少小車停留時間，盡量使每一輛小車都在運行，實現效率最大化和調度最優化.本模型可用于將任務提前分配給每一輛小車，得到最優的任務分配方式，后續可通過對各種影響因素的分析調整任務的分配，進一步提高小車作業效率.

文中未考慮具體的某種不確定性因素對集裝箱碼頭調度的影響、AGV小車的避障問題，以及某種具體的因素對小車數量的影響，以后可針對此類問題再做深入研究.