国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

倉儲物流中自動導(dǎo)引車的路徑規(guī)劃研究*

2019-01-03 02:51劉敬一孫維堂董君陶
關(guān)鍵詞:隊(duì)列調(diào)度沖突

劉敬一,孫維堂,劉 閩,董君陶

(1.中國科學(xué)院大學(xué),北京 100049;2.中國科學(xué)院 沈陽計(jì)算技術(shù)研究所 智能控制與裝備部,沈陽 110168;3.沈陽市環(huán)境監(jiān)測中心站 沈陽 110000;4沈陽市第二十七中學(xué) 沈陽 110011)

0 引言

隨著柔性制造系統(tǒng)的廣泛應(yīng)用,國內(nèi)對自動導(dǎo)引車的需求量也漸漸增長。在整個自動化倉儲物流中,AGV運(yùn)輸成本占總成本比重較高,倉儲任務(wù)的精準(zhǔn)調(diào)度以及AGV良好的路徑規(guī)劃策略,對提高物流作業(yè)效率、降低運(yùn)輸成本有重要意義。

針對多AGV的路徑尋優(yōu)問題,劉國棟等[1]提出了一種兩階段的交通控制方法來解決AGV路徑?jīng)_突問題,王佳溶[2]提出改進(jìn)型的兩階段控制策略,他們針對任務(wù)的優(yōu)先級未做詳細(xì)描述,當(dāng)任務(wù)和車輛非常多時,容易產(chǎn)生任務(wù)饑餓;胡彬等[3]提出一種基于時間窗的動態(tài)路徑規(guī)劃方法,先搜索出備選路徑,然后通過計(jì)算和排布時間窗來規(guī)避沖突,但提出的時間窗是基于邊的,也就是一條較長車道只能被一臺AGV保留,效率比節(jié)點(diǎn)時間窗低。

對AGV路徑規(guī)劃中路徑成本最優(yōu)化以及調(diào)度效率問題,提出一種基于優(yōu)先級隊(duì)列和時間窗動態(tài)排序的路徑規(guī)劃方法。首先構(gòu)建任務(wù)優(yōu)先級隊(duì)列,然后用A-Star算法啟發(fā)式搜索路徑,通過對節(jié)點(diǎn)時間窗進(jìn)行精確計(jì)算和加鎖,實(shí)現(xiàn)了多AGV的路徑實(shí)時規(guī)劃和動態(tài)調(diào)優(yōu),在無碰撞沖突條件下保證了倉儲物流路徑成本最低,而且提高了系統(tǒng)運(yùn)行效率。

1 問題描述

1.1 環(huán)境地圖

本文所考慮的是自動化倉儲物流中AGV群體運(yùn)動規(guī)則問題,根據(jù)其所在的倉儲環(huán)境采用拓?fù)浣7?gòu)建地圖,并作以下假設(shè):

(1)相鄰節(jié)點(diǎn)間的路線為單行道可雙向行駛。

(2)AGV在4個方向上以同一速度勻速行駛,且轉(zhuǎn)向速度固定;

(3)AGV間安全制動距離為0.8m;

(4)AGV共有4種狀態(tài):無任務(wù)靜止?fàn)顟B(tài)(包括充電狀態(tài)),有任務(wù)待負(fù)載行駛狀態(tài),負(fù)載搬運(yùn)狀態(tài),臨時等待狀態(tài)。

圖1 倉儲環(huán)境下拓?fù)涞貓D

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

針對AGV倉儲物流環(huán)境,建立拓?fù)涞貓D,如圖1所示,在有向連接網(wǎng)絡(luò)G=中,V代表網(wǎng)絡(luò)中節(jié)點(diǎn)的集合V={v1,v2,…,vn},E代表網(wǎng)絡(luò)中邊的集合E={e1,e2,…,em}, 且每條邊可以用相鄰節(jié)點(diǎn)有序?qū)肀硎荆?/p>

ey={vp→vq:vp,vq∈V}

(1)

多AGV路徑規(guī)劃的目的是規(guī)劃出一條時間代價最小的路徑。AGV在倉儲環(huán)境中的耗時分為到達(dá)裝載點(diǎn)時間,搬運(yùn)狀態(tài)時間和避障等待時間,分別設(shè)為的tk、carrytk和Ωk。因此所有AGV的時間代價之和可由以下公式得到:

(2)

其中,k為倉儲任務(wù)的編號。

1.3 任務(wù)調(diào)度

(1)亟待充電且攜帶任務(wù),將已分配的任務(wù)作為高優(yōu)先級重新分配,然后將充電任務(wù)作為中優(yōu)先級重新分配;

(2)亟待充電且無任務(wù)無負(fù)載,將充電任務(wù)作為中優(yōu)先級重新分配;

(3)一般性實(shí)時任務(wù)作為低優(yōu)先級分配;

(4)同一優(yōu)先級按照FCFS方法分配。

1.4 避障要素

(1)相向相遇沖突。如圖2所示,相向行駛的兩輛車相遇;

圖2 相向沖突示意圖

(2)垂直相遇沖突。如圖3所示,垂直方向的兩輛車在節(jié)點(diǎn)相遇;

圖3 垂直相遇沖突示意圖

(3)占位沖突(車輛空閑)。如圖4所示,前方因AGV空閑停車阻止了其他車的前進(jìn)。

圖4 占位沖突1示意圖

(4)占位沖突(故障)。如圖5所示,前方因故障停車阻止了其他車的前進(jìn)。

圖5 占位沖突2示意圖

(5)追尾沖突(超速)。如圖6所示,即將趕超。

圖6 追尾沖突示意圖

2 基于時間窗的避障路線規(guī)劃法

2.1 時間窗定義

如圖1所示,在有向連接網(wǎng)絡(luò)G=(V,E)中,假設(shè)有x輛車參與任務(wù)執(zhí)行,那么任務(wù)的AGV集合為A={a1,a2,…,ax}。所有任務(wù)的起點(diǎn)、終點(diǎn)都不同,那么任務(wù)的起點(diǎn)集合和終點(diǎn)的集合分別記為S和D,且S?V,D?V。那么自動導(dǎo)引車所經(jīng)過節(jié)點(diǎn)的時間窗可以定義為:

(3)

圖7 節(jié)點(diǎn)保留時間窗模型圖

2.2 時間窗計(jì)算

為了保障倉儲物流過程的安全性,需要對時間窗進(jìn)行精準(zhǔn)計(jì)算,如圖7所示。設(shè)AGV到達(dá)節(jié)點(diǎn)i的時間為ti,則有公式:

(4)

其中,tb為車輛安全制動時間,te為允許最大誤差時間,包括在節(jié)點(diǎn)處突發(fā)斷電及故障引起的制動誤差。

如圖8所示,設(shè)AGV車身的長度為l,AGV直行通過節(jié)點(diǎn)時,則有公式:

(5)

其中,vst是小車統(tǒng)一默認(rèn)的直行速度。

圖8 自動導(dǎo)引車通過節(jié)點(diǎn)i示意圖

如圖9所示,當(dāng)AGV在節(jié)點(diǎn)處轉(zhuǎn)彎時,則有:

(6)

其中,vtu是小車轉(zhuǎn)彎通過節(jié)點(diǎn)的速度。

圖9 自動導(dǎo)引車轉(zhuǎn)彎通過節(jié)點(diǎn)i示意圖

2.3 AGV最優(yōu)路徑規(guī)劃算法

在進(jìn)行多AGV路徑尋優(yōu)時,采用拓?fù)浣7?gòu)建倉儲電子地圖,且攜帶任務(wù)的AGV在運(yùn)行過程中可雙向行駛。將一個倉儲搬運(yùn)任務(wù)定義為:

carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}

(7)

其中,PQk表示第k個任務(wù)的實(shí)時優(yōu)先級,參數(shù)越大優(yōu)先級越低;btk表示第k個任務(wù)的開始時間;Sk和Dk分別表示第k個任務(wù)的裝載點(diǎn)和卸載點(diǎn),且Sk∈V、Dk∈V;枚舉類型的參數(shù)LBk(t)表示第k個任務(wù)的搬運(yùn)狀態(tài),如公式(8)所示。

(8)

給任務(wù)分配不同的優(yōu)先級PQ:如圖10所示,將任務(wù)隊(duì)列劃分為高中低三個優(yōu)先級隊(duì)列,分別用PQh、PQm和PQl來表示。

(1)當(dāng)LBk(t)=0時,小車正在去裝載點(diǎn)的路途中,即當(dāng)有任務(wù)無負(fù)載的AGV小車亟待充電或突發(fā)斷電等故障時,已安排的任務(wù)的需要重新分配,將該任務(wù)carryk(t)放入高優(yōu)先級隊(duì)列,將充電或維修任務(wù)放入中優(yōu)先級隊(duì)列;

(2)當(dāng)LBk(t)=1時,AGV在裝載點(diǎn)Sk和目的地Dk之間,即有任務(wù)有負(fù)載的AGV亟待充電或突發(fā)斷電等故障時,已安排的任務(wù)的需要重新初始化,因?yàn)檠b載點(diǎn)Sk已經(jīng)改變,然后將新任務(wù)carryk(t)放入高優(yōu)先級隊(duì)列,將充電或維修任務(wù)放入中優(yōu)先級隊(duì)列;

(3) 把一般性實(shí)時任務(wù)放入低優(yōu)先級隊(duì)列。

圖10 三叉堆優(yōu)先級隊(duì)列示意圖

體現(xiàn)在沖突一:后續(xù)的長任務(wù)需要不斷地尋找次優(yōu)路線;體現(xiàn)在沖突二:后續(xù)的長任務(wù)需要不斷地負(fù)載等待。二者都容易造成任務(wù)饑餓,會降低調(diào)度系統(tǒng)的效率。

我們有了任務(wù)的優(yōu)先級分配和時間窗的計(jì)算,下面來介紹路徑規(guī)劃算法的具體實(shí)現(xiàn)步驟,如圖11所示。

(1)根據(jù)上位機(jī)系統(tǒng)管理員輸入倉儲物流參數(shù),將任務(wù)劃分優(yōu)先級,插入優(yōu)先級隊(duì)列,并初始化多個運(yùn)輸任務(wù),carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}。

(2)按照任務(wù)的優(yōu)先級順序進(jìn)行車輛調(diào)度:選用離裝載點(diǎn)[6]最近的空閑AGV來執(zhí)行任務(wù)。

(3)用A-Star算法對路徑進(jìn)行啟發(fā)式搜索,得到臨時的最短行駛路徑。

(5)初始化節(jié)點(diǎn)時間窗Wk,如果存在任務(wù)p和q使Wp∩Wq≠?,說明節(jié)點(diǎn)時間窗因尚未加鎖而出現(xiàn)重疊現(xiàn)象,即在的某個保留時間窗內(nèi)出現(xiàn)了其他車輛[7]。

(6)根據(jù)重疊時間窗和拓?fù)涞貓D,來確定將會發(fā)生哪種節(jié)點(diǎn)沖突,然后對每個節(jié)點(diǎn)的時間窗加鎖。如果存在如圖2所示的沖突一相向相遇沖突[8],選擇PQk(t)較大的任務(wù)重新調(diào)度,由于根據(jù)啟發(fā)式算法規(guī)劃的臨時最優(yōu)路線會出現(xiàn)碰撞[9],因此需要繼續(xù)搜索次優(yōu)路徑,返回執(zhí)行步驟(3),若最后所有路線都會出現(xiàn)沖突一,那么返回執(zhí)行步驟(2)更換AGV車輛;如果沖突類型只剩沖突二垂直相遇沖突[10],那么攜帶低優(yōu)先級任務(wù)的AGV原地等待一個節(jié)點(diǎn)時間窗的時間,直到重疊窗口消失;如果兩種沖突都存在,則先按照相向相遇沖突處理。

(7)生成可執(zhí)行任務(wù)(指定AGV,明確路線),AGV執(zhí)行完任務(wù)空閑后,由于該AGV可能成為其他任務(wù)的障礙,所以要優(yōu)先派發(fā)該車輛。重復(fù)執(zhí)行步驟(1)等待管理員動態(tài)分發(fā)新需求。

圖11 AGV路徑規(guī)劃算法流程圖

考慮其他三種沖突,任務(wù)執(zhí)行過程中,對于沖突三,那么將更改此空閑AGV所占有的節(jié)點(diǎn)周圍四條邊的權(quán)重為無窮大,修改任務(wù)的起始點(diǎn),執(zhí)行算法中的步驟(3);對于沖突四,可能為突發(fā)斷電(非亟待充電提醒)或機(jī)械老化等故障,需要人工維修或清除,然后更新可用AGV信息;對于沖突五,由于環(huán)境中假設(shè)AGV速度相同,所以不會出現(xiàn)趕超沖突,即使在前面的AGV制動減速的時候也不會出現(xiàn)趕超沖突,因?yàn)樵谟?jì)算時間窗時,AGV制動時間tb已經(jīng)被保留在時間窗內(nèi)。

3 算法仿真驗(yàn)證

使用 Visual Studio 2015作為仿真開發(fā)平臺,編寫調(diào)度程序?qū)μ岢龅穆窂綄?yōu)算法進(jìn)行驗(yàn)證。選取某倉儲物流中心如圖1拓?fù)涞貓D所示,倉儲區(qū)域長30m,寬30m,倉儲節(jié)點(diǎn)36(不包括充電區(qū)域),144個貨架,14條車道縱橫交錯,AGV直行速度為0.5m/s。轉(zhuǎn)向時間固定為2s。

設(shè)計(jì)兩組仿真對比實(shí)驗(yàn):一組是無時間窗加鎖和有時間窗加鎖的路徑尋優(yōu)結(jié)果,另一組是不含優(yōu)先級隊(duì)列和含優(yōu)先級隊(duì)列的路徑尋優(yōu)結(jié)果。從兩個維度來驗(yàn)證所提出算法的可行性和高效性。

(1)針對第一種仿真對比實(shí)驗(yàn),我們分別初始化三個任務(wù):

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={2,0,g3,b3, -1}。

carry3(t)={3,0,e1,b2, -1}。

首先根據(jù)任務(wù)的預(yù)估時間來初始化優(yōu)先級,時間越長,PQk(t)數(shù)字越小,優(yōu)先級越高。

無時間窗加鎖的情況如圖12所示,執(zhí)行任務(wù)carry1(t)的車輛將會與執(zhí)行carry3(t)的車輛在b1到c1路段發(fā)生相向相遇沖突,執(zhí)行任務(wù)carry1(t)的車輛將會與執(zhí)行carry2(t)的車輛在c3節(jié)點(diǎn)發(fā)生垂直相遇沖突[11];

圖12 無時間窗加鎖含優(yōu)先級路徑尋優(yōu)結(jié)果

含時間窗加鎖的情況如圖13所示,由于經(jīng)過時間窗的重新排布,任務(wù)carry3(t)已經(jīng)重新規(guī)劃路線,有效避免與任務(wù)carry1(t)相向相遇沖突,且在節(jié)點(diǎn)c2進(jìn)行等待規(guī)避,避免垂直相遇沖突,任務(wù)carry3(t)將會在節(jié)點(diǎn)c3處進(jìn)行規(guī)避等待,有效避免死鎖和碰撞[12]。

圖13 含時間窗加鎖含優(yōu)先級路徑尋優(yōu)結(jié)果

(2)針對第二種仿真對比實(shí)驗(yàn),在不含優(yōu)先級的算法中我們分別初始化三個任務(wù),這里PQk(t)均為1,即:

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={1,0,g3,b3, -1}。

carry3(t)={1,0,e1,b2, -1}。

算法執(zhí)行過程如圖14所示。

圖14 含時間窗加鎖不含優(yōu)先級路徑尋優(yōu)結(jié)果

考慮圖13和圖14所示的兩種仿真執(zhí)行過程,對不含優(yōu)先級和含優(yōu)先級的兩種調(diào)度算法進(jìn)行路徑代價對比,如表1和表2所示。根據(jù)目標(biāo)函數(shù)公式計(jì)算出:含優(yōu)先級的調(diào)度算法路徑成本Cost小于不含優(yōu)先級的調(diào)度算法。

表1 不含優(yōu)先級隊(duì)列的調(diào)度算法執(zhí)行分析

表2 含優(yōu)先級隊(duì)列的調(diào)度算法執(zhí)行分析

4 結(jié)論

對多AGV路徑尋優(yōu)和調(diào)度效率問題,提出基于優(yōu)先級隊(duì)列和時間窗模型的調(diào)度算法。在多AGV動態(tài)路徑尋優(yōu)中,解決了多AGV的碰撞沖突問題,而且通過構(gòu)建任務(wù)優(yōu)先級隊(duì)列優(yōu)先級優(yōu)化了調(diào)度順序,不僅保證了路徑最優(yōu),而且可以避免任務(wù)饑餓與死鎖。最后通過仿真實(shí)驗(yàn)得出,算法在保證車輛無碰撞的條件下可使AGV路徑成本最低,同時提高了任務(wù)和車輛調(diào)度的效率。

猜你喜歡
隊(duì)列調(diào)度沖突
耶路撒冷爆發(fā)大規(guī)模沖突
隊(duì)列里的小秘密
基于多隊(duì)列切換的SDN擁塞控制*
《調(diào)度集中系統(tǒng)(CTC)/列車調(diào)度指揮系統(tǒng)(TDCS)維護(hù)手冊》正式出版
電力調(diào)度自動化中UPS電源的應(yīng)用探討
基于強(qiáng)化學(xué)習(xí)的時間觸發(fā)通信調(diào)度方法
在隊(duì)列里
CTC調(diào)度集中與計(jì)算機(jī)聯(lián)鎖通信接口的分析
豐田加速駛?cè)胱詣玉{駛隊(duì)列
論跨文化交流中的沖突與調(diào)解
五河县| 沙坪坝区| 盐池县| 华亭县| 台前县| 革吉县| 海丰县| 威宁| 临沂市| 广南县| 克拉玛依市| 黄梅县| 个旧市| 赤水市| 盐池县| 龙陵县| 巴青县| 石阡县| 平原县| 望城县| 沂南县| 淮北市| 宕昌县| 天台县| 开远市| 同江市| 色达县| 太仆寺旗| 巴林右旗| 盐源县| 卓资县| 祁阳县| 靖远县| 高平市| 浦东新区| 龙川县| 裕民县| 乌拉特中旗| 万载县| 浏阳市| 界首市|