針對(duì)自動(dòng)化集裝箱碼頭水平搬運(yùn)作業(yè)中自動(dòng)化導(dǎo)引車路徑?jīng)_突問題,提出一種基于時(shí)空網(wǎng)絡(luò)的路徑優(yōu)化方法。對(duì)于單個(gè)運(yùn)輸需求,首先,將路網(wǎng)離散化為網(wǎng)格網(wǎng)絡(luò),設(shè)計(jì)依據(jù)時(shí)間可更新的時(shí)空網(wǎng)絡(luò);其次,以任務(wù)完工時(shí)間最短為目標(biāo),基于時(shí)空網(wǎng)絡(luò)下可用路段集合來建立車輛路徑優(yōu)化模型;最后,在時(shí)空網(wǎng)絡(luò)上運(yùn)用最短路徑算法求解得最短路徑。對(duì)于多個(gè)運(yùn)輸需求,為避免路徑?jīng)_突,根據(jù)當(dāng)前運(yùn)輸需求的路徑規(guī)劃結(jié)果更新下一個(gè)運(yùn)輸需求的時(shí)空網(wǎng)絡(luò),并通過迭代最終獲得滿足規(guī)避碰撞和緩解擁堵條件的路徑規(guī)劃。計(jì)算實(shí)驗(yàn)中,與基本最短路徑求解策略（求解算法P）相比,所提方法的碰撞次數(shù)降低為0并且最小相對(duì)距離始終大于安全距離;與停車等待求解策略（求解算法SP）相比,所提方法最多減少任務(wù)總延誤時(shí)間24 s,且明顯降低延誤任務(wù)占比以及路網(wǎng)平均擁堵度,最大降低程度分別為2. 25%和0. 68%。實(shí)驗(yàn)結(jié)果表明,所提方法能夠有效求解大規(guī)模沖突規(guī)避的路徑規(guī)劃問題,并顯著提高自動(dòng)化導(dǎo)引車的作業(yè)效率。 

【文章來源】：計(jì)算機(jī)應(yīng)用. 2020,40(07)北大核心CSCD

【文章頁數(shù)】：9 頁

【部分圖文】：

自動(dòng)化集裝箱碼頭布局

通常，將一輛AGV從任務(wù)的O點(diǎn)到D點(diǎn)的行駛路徑設(shè)為兩點(diǎn)之間的最短路徑，并且假定該最短路徑上的所有路段都是通暢可行的[23]，然而該做法沒有考慮AGV在實(shí)際路段中的運(yùn)行軌跡以及運(yùn)行過程中的實(shí)時(shí)動(dòng)態(tài)干涉，導(dǎo)致AGV根據(jù)規(guī)劃路徑進(jìn)行作業(yè)時(shí)產(chǎn)生沖突。路徑?jīng)_突情況包括碰撞和擁堵，在圖2中，舉例說明AGV沖突問題。任務(wù)1和任務(wù)2同為進(jìn)口箱作業(yè)，任務(wù)1和任務(wù)2的OD點(diǎn)分別為O1D1、O2D2，實(shí)線表示小車實(shí)際經(jīng)過的路線，虛線表示計(jì)劃行駛但未行駛的路線。圖2(a）展示了碰撞的發(fā)生情況，執(zhí)行任務(wù)1的AGV與執(zhí)行任務(wù)2的AGV在不同時(shí)刻出發(fā)卻在同一時(shí)刻到達(dá)點(diǎn)A，發(fā)生碰撞導(dǎo)致任務(wù)執(zhí)行失敗。圖2(b）展示了擁堵的發(fā)生情況，執(zhí)行任務(wù)1和執(zhí)行任務(wù)2的2輛AGV會(huì)在同一時(shí)刻到達(dá)A點(diǎn)，但為避免碰撞，執(zhí)行任務(wù)2的AGV行駛到緩沖區(qū)B點(diǎn)時(shí)停車等待，造成擁堵現(xiàn)象。AGV發(fā)生碰撞將直接導(dǎo)致設(shè)備損壞，大幅度增加成本，設(shè)備停留在路段中占用路段資源，可能與即將行駛進(jìn)路網(wǎng)的AGV發(fā)生二次碰撞，并且處理碰撞事故所需時(shí)間和人力成本較高；等待是避免碰撞的常用手段，但AGV減速及加速過程所消耗的電力成本較高，并且AGV等待減少了可用的道路資源，道路會(huì)因?yàn)锳GV的等待而出現(xiàn)擁堵，嚴(yán)重時(shí)會(huì)導(dǎo)致整個(gè)路網(wǎng)癱瘓導(dǎo)致ACT被迫停止運(yùn)作。所以，當(dāng)路段本身成為臨界資源時(shí)，AGV對(duì)路段具有獨(dú)占性，因此，考慮AGV在不同時(shí)刻在路網(wǎng)上的狀態(tài)是判別碰撞和擁堵的前提條件。在AGV的行駛過程中，從當(dāng)前時(shí)刻的位置出發(fā)，下一時(shí)刻可選的到達(dá)位置通常有多個(gè)；在各個(gè)不同位置上的下一個(gè)可能到達(dá)的位置又是不同的，因此，建立在道路網(wǎng)絡(luò)背景下隨時(shí)間演變的時(shí)空網(wǎng)絡(luò)。利用AGV在不同時(shí)刻可能到達(dá)的不同位置，從而刻畫出AGV從任務(wù)起點(diǎn)出發(fā)的一個(gè)可行的帶有時(shí)間和位置標(biāo)簽的網(wǎng)絡(luò)，路徑規(guī)劃則是在該網(wǎng)絡(luò)中選擇一條完工時(shí)間最短的路徑。本文在ACT背景下建立AGV時(shí)空網(wǎng)絡(luò)，在時(shí)空網(wǎng)絡(luò)中規(guī)劃AGV最短路徑，以任務(wù)完工時(shí)間最短為目標(biāo)，建立數(shù)學(xué)模型并設(shè)計(jì)時(shí)空網(wǎng)絡(luò)算法，使規(guī)劃路徑規(guī)避碰撞并緩解擁堵。

基于以上的概念和模型，設(shè)計(jì)基于時(shí)空網(wǎng)絡(luò)的算法——TS-SP(Tempo-Spatial Shortest Path),TS-SP算法由算法1和算法2組成。其中，算法1通過生成時(shí)空網(wǎng)絡(luò)，更新時(shí)空網(wǎng)絡(luò)，以及調(diào)用M2計(jì)算最短路徑獲得給定一個(gè)OD的AGV路徑；算法2調(diào)用算法1，通過迭代策略求解OD任務(wù)序列中的所有O和D配對(duì)的路徑。算法2根據(jù)已獲得的路徑更新不可用節(jié)點(diǎn)集合-NT（步驟5）以實(shí)時(shí)檢測(cè)沖突，而算法1則利用不可用節(jié)點(diǎn)集合更新時(shí)空網(wǎng)絡(luò)（步驟2）以實(shí)時(shí)規(guī)避沖突并進(jìn)行一次路徑規(guī)劃（步驟3），因此針對(duì)多個(gè)OD任務(wù)，在時(shí)空網(wǎng)絡(luò)上運(yùn)用最短路徑算法，根據(jù)路徑結(jié)果更新時(shí)空網(wǎng)絡(luò)，并通過迭代最終獲得滿足避碰和緩解擁堵條件的路徑規(guī)劃，而M2的求解過程能夠通過拓展基本最短路徑算法（如Dijkstra算法）實(shí)現(xiàn)。時(shí)空網(wǎng)絡(luò)算法流程如圖3所示。算法開始，依據(jù)時(shí)間順序從任務(wù)集中選取任務(wù)執(zhí)行。針對(duì)每一個(gè)當(dāng)前任務(wù)，首先生成時(shí)空網(wǎng)絡(luò)，并依據(jù)當(dāng)前的不可用節(jié)點(diǎn)集合更新時(shí)空網(wǎng)絡(luò)，接著在更新后的時(shí)空網(wǎng)絡(luò)中采用Dijkstra算法計(jì)算任務(wù)最短路徑，并依據(jù)當(dāng)前任務(wù)的最短路徑結(jié)果更新不可用節(jié)點(diǎn)集合。判斷任務(wù)集是否為空：任務(wù)集不為空則選擇下一個(gè)任務(wù)執(zhí)行；任務(wù)集為空則說明已完成所有任務(wù)，算法結(jié)束。算法1單個(gè)OD任務(wù)最短路徑優(yōu)化算法（Single＿OD＿SP）。

【參考文獻(xiàn)】：
期刊論文
[1]融合多目標(biāo)與速度控制的AGV全局路徑規(guī)劃[J]. 郭興海,計(jì)明軍,張衛(wèi)丹.  控制與決策. 2020(06)
[2]基于蟻群算法及博弈論的多Agent路徑規(guī)劃算法[J]. 鄭延斌,王林林,席鵬雪,樊文鑫,韓夢(mèng)云.  計(jì)算機(jī)應(yīng)用. 2019(03)
[3]多自動(dòng)導(dǎo)引車路徑規(guī)劃的誘導(dǎo)蟻群粒子群算法[J]. 李軍軍,許波桅,楊勇生,吳華鋒.  計(jì)算機(jī)集成制造系統(tǒng). 2017(12)
[4]基于改進(jìn)遺傳算法的自動(dòng)導(dǎo)引小車動(dòng)態(tài)路徑規(guī)劃及其實(shí)現(xiàn)[J]. 劉二輝,姚錫凡,藍(lán)宏宇,金鴻.  計(jì)算機(jī)集成制造系統(tǒng). 2018(06)



本文編號(hào)：3454814