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

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

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

【部分圖文】：

自動化集裝箱碼頭布局

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

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

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



本文編號：3454814