鄭亞紅 徐玖龍 謝 淳

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

0 引 言

自動(dòng)導(dǎo)引運(yùn)輸車(chē)(automated guided vehicle，AGV)純電力驅(qū)動(dòng)，采用無(wú)人駕駛技術(shù)，同集卡相比，具有節(jié)能減排、智能行駛、降低人工勞動(dòng)強(qiáng)度等顯著優(yōu)勢(shì).如今設(shè)備的自動(dòng)控制技術(shù)已經(jīng)日趨成熟，整個(gè)碼頭的效率瓶頸主要集中AGV的調(diào)度優(yōu)化層面.近年來(lái)國(guó)內(nèi)外學(xué)者對(duì)自動(dòng)化碼頭AGV作業(yè)的相關(guān)研究大多數(shù)仍集中在傳統(tǒng)的調(diào)度問(wèn)題，很少考慮其充電/換電過(guò)程.Vis[2]將AGV運(yùn)輸系統(tǒng)調(diào)度問(wèn)題分為調(diào)度問(wèn)題(dispatching problem)和調(diào)度及路徑問(wèn)題(dispatching and routing problem)，前者是基于作業(yè)任務(wù)對(duì)AGV進(jìn)行分派并制定其作業(yè)時(shí)間表，后者同時(shí)進(jìn)行調(diào)度和路徑選擇的決策.而大部分研究中的調(diào)度問(wèn)題其實(shí)包含了路徑問(wèn)題，可以稱(chēng)之為一種廣義的調(diào)度問(wèn)題.目前關(guān)于這類(lèi)調(diào)度問(wèn)題的研究主要有兩個(gè)方向：①對(duì)問(wèn)題或模型的擴(kuò)展，從文獻(xiàn)[3]基于將所有的AGV分派到同一岸橋的假設(shè)的簡(jiǎn)單問(wèn)題，發(fā)展到現(xiàn)在研究的多岸橋、考慮AGV行駛時(shí)間和岸橋作業(yè)時(shí)間延遲[4]、不同策略下的AGV自適應(yīng)調(diào)度[5]、減少AGV的空載行駛以實(shí)現(xiàn)減排[6]等更切于實(shí)際的復(fù)雜問(wèn)題，此外在決策變量類(lèi)型、車(chē)輛性能、目標(biāo)函數(shù)、約束條件、調(diào)度規(guī)則等方面有所區(qū)別；②對(duì)這類(lèi)NP難問(wèn)題的求解方法的探索，目前主要應(yīng)用的方法有啟發(fā)式算法、智能學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、對(duì)混合整數(shù)規(guī)劃模型的約束松弛、基于時(shí)間Petri網(wǎng)的建模等，還有的借鑒了FMS(柔性制造系統(tǒng))中的研究方法.

AGV續(xù)航有充電和更換整體電池包(簡(jiǎn)稱(chēng)換電)兩種不同方式，本研究基于前期對(duì)洋山四期自動(dòng)化碼頭的調(diào)研展開(kāi)，著重探討換電這種方式.石楠路等[7]的研究，考慮了AGV的換電過(guò)程，以提高AGV作業(yè)效率為優(yōu)化目標(biāo)構(gòu)建了AGV作業(yè)調(diào)度混合整數(shù)優(yōu)化模型，并通過(guò)遺傳算法求解.從研究結(jié)論看，雖然減少AGV換電排隊(duì)時(shí)間，但是大大降低了AGV電池利用率，因?yàn)闉榱隋e(cuò)開(kāi)AGV換電時(shí)間，有的AGV在電量消耗很少的時(shí)候就前往換電站換電，從資源利用的角度看實(shí)際上產(chǎn)生了較大的浪費(fèi).張亞琦等[8]的研究，關(guān)注了AGV的充電過(guò)程，將AGV充電后的續(xù)航能力約束條件考慮進(jìn)調(diào)度模型中，進(jìn)行AGV充電與作業(yè)的聯(lián)合優(yōu)化.

文中在對(duì)洋山四期自動(dòng)化碼頭的調(diào)研和國(guó)內(nèi)外現(xiàn)有研究特別是文獻(xiàn)[8]的基礎(chǔ)上，結(jié)合自動(dòng)化集裝箱碼頭AGV實(shí)際生產(chǎn)作業(yè)流程和換電需求特性，以優(yōu)化AGV換電模式為切入點(diǎn)進(jìn)行換電管理優(yōu)化，同時(shí)將AGV換電和作業(yè)進(jìn)行協(xié)同，建立二者協(xié)同的調(diào)度模型，減少AGV在換電站的排隊(duì)等待時(shí)間，兼顧考慮提高AGV電池利用率，最終實(shí)現(xiàn)提高AGV作業(yè)效率.

1 問(wèn)題描述

AGV換電站及其配套設(shè)施占地面積較大，一般建設(shè)在AGV運(yùn)行車(chē)道的盡頭，見(jiàn)圖1.AGV調(diào)度同傳統(tǒng)碼頭中集卡調(diào)度的主要區(qū)別就是需要保證AGV的續(xù)航能力，杜絕AGV電量耗盡帶來(lái)的系列問(wèn)題.由于現(xiàn)有的AGV路徑規(guī)劃系統(tǒng)和AGV無(wú)人駕駛技術(shù)不夠成熟，易出現(xiàn)由于一臺(tái)AGV未能及時(shí)更換電池包導(dǎo)致沒(méi)有足夠電量返回?fù)Q電站而停在車(chē)道的情況.更嚴(yán)重地，可能造成其他工作的AGV因?yàn)檐?chē)道被占用為防止發(fā)生碰撞而觸發(fā)車(chē)輛死鎖現(xiàn)象，進(jìn)而導(dǎo)致越來(lái)越多的AGV堵塞在行車(chē)道上，引發(fā)碼頭上的交通癱瘓.實(shí)際上一旦出現(xiàn)AGV電量不足而導(dǎo)致停工的情況，中控室將指派維修員對(duì)AGV進(jìn)行臨時(shí)充電，甚至需要重新規(guī)劃調(diào)度系統(tǒng)，無(wú)疑會(huì)增加碼頭的人力成本和時(shí)間成本.因此，AGV正常運(yùn)行的前提條件是，必須確保AGV有充足的電量使其在電量耗盡之前到達(dá)換電站.

圖1 自動(dòng)化集裝箱碼頭AGV作業(yè)區(qū)域示意圖

以卸船為例，自動(dòng)化碼頭AGV工藝過(guò)程為：AGV 從AQC(自動(dòng)化岸橋)接箱后，沿環(huán)形道路完成水平運(yùn)輸，由ARMG(自動(dòng)化龍門(mén)吊)提箱，然后AGV沿環(huán)形道路返回AQC下方執(zhí)行下一任務(wù).AGV運(yùn)輸集裝箱過(guò)程實(shí)際上是一個(gè)循環(huán)過(guò)程，見(jiàn)圖2.假設(shè)AGV從換電站(或車(chē)場(chǎng))出發(fā)時(shí)為滿電狀態(tài)，SOC(電量狀態(tài))值為1，指派該AGV從岸橋1(位置O1)運(yùn)輸集裝箱T1至箱區(qū)1(位置D1)，完成該任務(wù)T1后，AGV根據(jù)實(shí)時(shí)SOC值判斷是否能夠繼續(xù)完成別的任務(wù)，如果仍有足夠電量則接著去完成任務(wù)T2，因此指派該AGV行駛至岸橋2(位置O2)，將集裝箱T2運(yùn)輸?shù)较鋮^(qū)2(位置D2)；而如果AGV的電池剩余電量不足以使其完成其他任務(wù)，則指派該AGV前往換電站(終點(diǎn))進(jìn)行換電，直至其換電完成，表示該AGV的一個(gè)循環(huán)過(guò)程結(jié)束；其后，AGV從該換電站出發(fā)，執(zhí)行新的循環(huán)過(guò)程直至AGV完成所有任務(wù).同時(shí)需要考慮的是，由于AGV空車(chē)行駛、重車(chē)行駛以及等待狀態(tài)三種情況下耗電量有較大的差異，因此需要進(jìn)行空駛行程、重載行程和排隊(duì)等待過(guò)程的區(qū)分，分別計(jì)算不同狀態(tài)下AGV的耗電量.

圖2 AGV運(yùn)輸循環(huán)過(guò)程示意圖

根據(jù)前期對(duì)洋山四期自動(dòng)化碼頭的調(diào)研，得知其現(xiàn)有的換電模式為.當(dāng)AGV電池包SOC值低于40%時(shí)即前往換電站進(jìn)行換電.現(xiàn)有模式的弊端，一方面在于換電SOC臨界值過(guò)大會(huì)引起電池電量利用率下降而提高電池使用成本，另一方面在于頻繁的換電可能會(huì)造成換電過(guò)程中出現(xiàn)AGV在換電站排隊(duì)等待的現(xiàn)象，從而進(jìn)一步地造成AGV作業(yè)完工時(shí)間的延遲.因此，如何設(shè)計(jì)合理的換電模式、將換電模式同調(diào)度策略進(jìn)行集成是建立調(diào)度模型的關(guān)鍵和難點(diǎn).

2 模型構(gòu)建

2.1 符號(hào)說(shuō)明

2.2 數(shù)學(xué)模型

為減少AGV在換電站的排隊(duì)及等待時(shí)間，降低換電過(guò)程對(duì)AGV調(diào)度的影響以提高整體作業(yè)效率，建立AGV作業(yè)與換電過(guò)程協(xié)同調(diào)度優(yōu)化模型.模型的目標(biāo)函數(shù)與約束條件如下.

(1)

s.t.

(2)

?i≠j,v∈V

(3)

?i∈I,v∈V

(4)

?i≠j,v∈V

(5)

?i≠j,v∈V

(6)

(7)

∑j∈I+(〗i}xjiv=yivn,?i∈I,v∈V

(8)

(9)

xijv+xjiv≤1,?i,j∈I,i≠j,v∈V

(10)

∑i∈Ix0+1,i,v=1,?v∈V

(11)

∑i∈Ixi,O+2,v=1,?v∈V

(12)

xi,O+1,v=0,?i∈I+,v∈V

(13)

xO+2,j,v=0,?j∈I+,v∈V

(14)

?i,j∈I,v∈V

(15)

(16)

(17)

(18)

∑rvv′=1,?v≠v′

(19)

(20)

(21)

3 遺傳算法求解

3.1 染色體編碼過(guò)程

一條染色體即問(wèn)題的一個(gè)可行解，表征AGV分配到的任務(wù)，為了保證整個(gè)迭代過(guò)程中解的可行性，換電過(guò)程不直接顯示在染色體中.2.1中總的集裝箱任務(wù)數(shù)為|I|，總的AGV數(shù)量為|V|.每一臺(tái)AGV完成多個(gè)循環(huán)運(yùn)輸，一條染色體由|I|個(gè)1到|V|之間的正整數(shù)組成.圖3為15個(gè)任務(wù)、五臺(tái)AGV對(duì)應(yīng)的問(wèn)題的染色體編碼示意圖，AGV編號(hào)對(duì)應(yīng)的任務(wù)編號(hào)即為分配給該AGV的運(yùn)輸任務(wù).例如，AGV2分配的任務(wù)列表task_AGV為{2 4 7 10}，對(duì)應(yīng)的任務(wù)編號(hào)依次為2、4、7、10，因此AGV1執(zhí)行任務(wù)的路徑route_AGV為：車(chē)場(chǎng)/換電站→任務(wù)2→任務(wù)4→任務(wù)7→任務(wù)10→車(chē)場(chǎng)/換電站.

圖3 染色體編碼示意圖

3.2 染色體解碼過(guò)程

染色體解碼過(guò)程即計(jì)算適應(yīng)度值的過(guò)程.|V|臺(tái)AGV需要在若干循環(huán)內(nèi)完成|I|個(gè)任務(wù)，因此在遺傳算法的解碼操作過(guò)程中，需要考慮到每一臺(tái)AGV在不同的任務(wù)循環(huán)周期內(nèi)所分配到的任務(wù).圖4為遺傳算法過(guò)程中染色體解碼流程圖.整個(gè)解碼過(guò)程主要包括兩個(gè)步驟，即生成初始AGV任務(wù)路徑和判斷是否進(jìn)行換電兩個(gè)部分.

3.3 適應(yīng)度函數(shù)

3.4 遺傳算子

3.4.1選擇算子

采用輪盤(pán)賭的方法，每一條染色體在輪盤(pán)上占有的面積根據(jù)適應(yīng)度函數(shù)值按比例表示出來(lái)，即個(gè)體適應(yīng)度值越大，被選擇的幾率越大.經(jīng)過(guò)實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)在其他算子不變的情況下采用謝菲爾德遺傳算法工具箱中的輪盤(pán)賭rws函數(shù)得出的結(jié)果較好，見(jiàn)表1.

表1 AGV1需完成的4個(gè)任務(wù)的屬性

3.4.2交叉算子

對(duì)于排列式染色體，通常采用單點(diǎn)或兩點(diǎn)均勻交叉法，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)兩者的差別不大，因此選擇更為簡(jiǎn)單的單點(diǎn)交叉法：首先在種群中隨機(jī)選擇兩條父代染色體P1和P2，然后隨機(jī)選擇一處切點(diǎn)，在這兩條染色體中均復(fù)制從染色體的第一個(gè)基因到該切點(diǎn)間的染色體片段r1和r2，最后將r1和r2交換位置，得到兩條子代染色體C1和C2，染色體交叉過(guò)程見(jiàn)圖5.

圖5 染色體交叉過(guò)程

3.4.3變異算子

采取隨機(jī)改變1個(gè)基因位的基因的變異方法：在父代染色體P中隨機(jī)選擇1個(gè)基因位，將其替代為一個(gè)新的可行的基因，產(chǎn)生新的子代染色體.染色體變異過(guò)程見(jiàn)圖6.

圖6 染色體變異過(guò)程

4 數(shù)值實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證所構(gòu)建模型的有效性和遺傳算法的可行性，利用MATLAB軟件對(duì)以下數(shù)值例子進(jìn)行分析計(jì)算.隨機(jī)產(chǎn)生100個(gè)集裝箱任務(wù)樣本，任務(wù)順序即按照編號(hào)順序，任務(wù)屬性見(jiàn)表2，存放于Excel表格中.

表2 集裝箱任務(wù)屬性

為方便程序計(jì)算，設(shè)置2個(gè)換電站、8個(gè)堆場(chǎng)箱區(qū)、3臺(tái)岸橋以及AGV停車(chē)場(chǎng)四類(lèi)節(jié)點(diǎn)的坐標(biāo)見(jiàn)表3.

共有15臺(tái)AGV可供使用，假設(shè)AGV重車(chē)平均行駛速度為3 m/s，空車(chē)平均行駛速度為4 m/s，AGV在空車(chē)行駛狀態(tài)下的耗電率為0.01%/m，重車(chē)耗電率為0.02%/m，因?yàn)榭紤]了等待時(shí)間，設(shè)置等待狀態(tài)下的耗電率為0.005%/s.使用兩個(gè)換電站，每個(gè)換電站同一時(shí)刻只允許一臺(tái)AGV進(jìn)行換電工作，換電站的作業(yè)時(shí)間誤差不考慮，即每一個(gè)AGV換電時(shí)間相同，均為300 s/臺(tái)，換電站內(nèi)的電池儲(chǔ)備充足.設(shè)置遺傳算法中種群大小N_pop=100，最大迭代次數(shù)MAXGEN=200.其他參數(shù)都相同，換電SOC值為60%時(shí)，通過(guò)對(duì)在不同的Pc和Pm值條件下進(jìn)行10次實(shí)驗(yàn)得到的平均makespan(最末完成任務(wù)時(shí)間)的對(duì)比，最終擇優(yōu)選擇交叉概率Pc=0.7，變異概率Pm=0.05.

表3 節(jié)點(diǎn)坐標(biāo)

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

換電SOC臨界值是換電模式的核心，也是模型中最重要的決策變量.依次設(shè)置SOC臨界值為60%，70%，80%，90%和100%，進(jìn)行五組實(shí)驗(yàn)對(duì)比，結(jié)果見(jiàn)表4.由表4可知，換電SOC值越大換電次數(shù)越少，最末任務(wù)完成時(shí)間并沒(méi)有隨著SOC值的增大而持續(xù)降低.在實(shí)際營(yíng)運(yùn)過(guò)程中，除了實(shí)現(xiàn)降低總的任務(wù)完成時(shí)間目標(biāo)外，還需考慮AGV在前往換電站過(guò)程中以及在換電站的排隊(duì)等待過(guò)程中的能量消耗，那么，設(shè)置一定的冗余電量來(lái)應(yīng)對(duì)一些不確定性是有必要的.因此，綜合來(lái)看，較優(yōu)的方案為換電SOC臨界值取值70%.

表4 不同換電SOC值條件下的結(jié)果對(duì)比

利用Matlab R2016b軟件編程設(shè)計(jì)遺傳算法進(jìn)行問(wèn)題的求解，采用上述參數(shù)，并設(shè)置種群數(shù)為N_pop=200，迭代代數(shù)MAXGEN=500，遺傳算法迭代計(jì)算的收斂過(guò)程見(jiàn)圖7，得出的近似最優(yōu)解對(duì)應(yīng)的AGV作業(yè)甘特圖見(jiàn)圖8.由圖7可知，在170代的時(shí)候已收斂至近似最優(yōu)解.圖8中灰色矩形表示AGV換電時(shí)間.由圖8可知，在該方案下有4臺(tái)AGV進(jìn)行了換電，且AGV在換電站排隊(duì)等待時(shí)間較短.15臺(tái)AGV的最大最末任務(wù)完成時(shí)間為3 103.8 s，同表2中最末任務(wù)的最早可開(kāi)始時(shí)間2 992 s相比時(shí)間間隔很小，即該方案所需要的所有任務(wù)完成時(shí)間同初始設(shè)置的AGV最末任務(wù)開(kāi)始執(zhí)行時(shí)間之間的增量較小，可以認(rèn)為是合理可行的調(diào)度方案.

圖7 遺傳算法收斂過(guò)程

圖8 AGV作業(yè)甘特圖

5 結(jié) 束 語(yǔ)

針對(duì)實(shí)際運(yùn)營(yíng)中的自動(dòng)化集裝箱碼頭AGV作業(yè)效率待提升的問(wèn)題，從AGV換電管理優(yōu)化和AGV換電與作業(yè)集成調(diào)度的視覺(jué)，構(gòu)建調(diào)度模型并采用遺傳算法求解.模型中區(qū)分了AGV實(shí)際生產(chǎn)作業(yè)中不同狀態(tài)下AGV的耗電特性，模型決策變量除了集裝箱是否分配到某臺(tái)AGV之外，還包括AGV換電過(guò)程中的關(guān)鍵決策問(wèn)題——換電SOC值.通過(guò)數(shù)值實(shí)驗(yàn)分析得出結(jié)論：合理的換電SOC值同換電次數(shù)及總的任務(wù)完成時(shí)間相關(guān)，AGV換電與作業(yè)協(xié)同調(diào)度可以有效減少AGV在換電站的排隊(duì)等待時(shí)間，從而提高自動(dòng)化集裝箱碼頭AGV的整體作業(yè)效率.

需要指出的是，由于關(guān)注重點(diǎn)是AGV的作業(yè)效率，故只考慮了AGV等待岸橋或龍門(mén)吊準(zhǔn)備集裝箱的時(shí)間，沒(méi)有考慮岸橋或龍門(mén)吊等待AGV的時(shí)間.從提高碼頭總的裝卸效率的角度來(lái)看，設(shè)備之間的配合、協(xié)調(diào)，以及設(shè)備數(shù)量匹配等也都是非常值得研究的問(wèn)題.