黃澤乾 丁 濤 王 雅

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

0 引 言

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

1 問題描述

1.1 模型條件設(shè)置

AGV調(diào)度問題主要是從給AGV分配任務(wù)并且選擇最佳的任務(wù)順序來完成任務(wù)從而得到最短的路徑.單AGV調(diào)度的時(shí)候就相當(dāng)于合理地分配任務(wù)的順序得到最短的路徑，而多AGV的調(diào)度需要將任務(wù)合理分配到每臺(tái)AGV上，并且使得總的AGV調(diào)度的路程最短，把多AGV調(diào)度的最短時(shí)間問題轉(zhuǎn)換為最短路徑問題[6-8].

對(duì)AGV小車的調(diào)度做如下假設(shè).

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

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

3) 當(dāng)系統(tǒng)中有任務(wù)出現(xiàn)時(shí)直接把任務(wù)轉(zhuǎn)換成運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)i到節(jié)點(diǎn)j.

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

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

1.2 模型概述

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

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

第k輛AGV執(zhí)行完第i個(gè)任務(wù)后是否繼續(xù)執(zhí)行第j個(gè)任務(wù)，即

(1)

(2)

則目標(biāo)函數(shù)為

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)為目標(biāo)函數(shù)，是所有AGV在執(zhí)行任務(wù)時(shí)，找出單個(gè)AGV執(zhí)行任務(wù)所用的最大時(shí)間；約束條件(4)(5)(6)為每個(gè)任務(wù)都被一輛AGV執(zhí)行并且只執(zhí)行一次，不重復(fù)執(zhí)行；約束條件(7)為AGV是否執(zhí)行了任務(wù)i后再執(zhí)行任務(wù)j；約束條件(8)為任務(wù)i是否被第k輛AGV執(zhí)行.

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

2 遺傳算法

2.1 編碼與解碼

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

表1 任務(wù)和小車序號(hào)分配

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

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

2.2 GA工具箱

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

3 實(shí)驗(yàn)設(shè)置

3.1 調(diào)度仿真

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

表2 各節(jié)點(diǎn)之間的最短距離

表3 各個(gè)任務(wù)和任務(wù)的起訖點(diǎn)

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

在集裝箱碼頭的作業(yè)過程中，不同的任務(wù)數(shù)量需要不同數(shù)量的AGV小車來進(jìn)行作業(yè).

所以對(duì)表2任務(wù)進(jìn)行了不同AGV小車數(shù)量的研究，設(shè)置AGV小車數(shù)從1～6得到了表4.

表4 不同數(shù)量的AGV對(duì)應(yīng)不同的時(shí)間

將表4的數(shù)據(jù)繪制成折線圖，得到橫軸為AGV小車，縱軸為進(jìn)行任務(wù)所用的時(shí)間，見圖1.

圖1 AGV數(shù)量和對(duì)應(yīng)時(shí)間

由圖1可知，隨著AGV固定數(shù)量的增長(zhǎng)，時(shí)間的減少并不是線性的，即不是固定數(shù)量的時(shí)間減少，而是凹函數(shù)形式的減少.在調(diào)用3臺(tái)AGV的到調(diào)用4臺(tái)AGV時(shí)時(shí)間的減少量明顯下降，在調(diào)用5臺(tái)到調(diào)用6臺(tái)AGV時(shí)時(shí)間沒變，出現(xiàn)這種情況意味著每個(gè)時(shí)間段的任務(wù)群需要對(duì)應(yīng)AGV小車的數(shù)量，小車的數(shù)量過多時(shí)，時(shí)間減少量降低或幾乎不變，因此,確定合適每個(gè)時(shí)間段任務(wù)群的AGV小車調(diào)度數(shù)量是非常有必要的.

3.3 卸船調(diào)度仿真

上述實(shí)驗(yàn)是假設(shè)碼頭的各個(gè)位置,比如,從集裝箱堆場(chǎng)到集裝箱修理廠，岸橋到堆場(chǎng)，岸橋到倉庫，倉庫到堆場(chǎng)等不同位置之間的調(diào)度，接下來模擬碼頭卸船時(shí)的AGV調(diào)度.假設(shè)岸橋用了兩個(gè)，堆場(chǎng)用了四個(gè)，卸一艘船，船上需要卸載的集裝箱為100TEU，使用6臺(tái)AGV小車進(jìn)行作業(yè)，每輛AGV小車的運(yùn)行都按雙線運(yùn)行并且假設(shè)小車之間不會(huì)發(fā)生碰撞和擁堵，見表5.

表5 集裝箱碼頭的岸橋和場(chǎng)最短距離

假設(shè)任務(wù)見表6.

表6 執(zhí)行任務(wù)表

卸船調(diào)度任務(wù)表見表7.

表7 卸船調(diào)度任務(wù)列表

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

4 結(jié) 束 語

港口中各個(gè)場(chǎng)地間的調(diào)度與卸船時(shí)固定路線的調(diào)度均可使用此模型，并且運(yùn)用此模型對(duì)于小車的就近點(diǎn)選擇與路徑選擇達(dá)到了任務(wù)分配均勻的目的,建立了以最末任務(wù)結(jié)束時(shí)間最小化為目標(biāo)的混合整數(shù)規(guī)劃模型，減少小車停留時(shí)間，盡量使每一輛小車都在運(yùn)行，實(shí)現(xiàn)效率最大化和調(diào)度最優(yōu)化.本模型可用于將任務(wù)提前分配給每一輛小車，得到最優(yōu)的任務(wù)分配方式，后續(xù)可通過對(duì)各種影響因素的分析調(diào)整任務(wù)的分配，進(jìn)一步提高小車作業(yè)效率.

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