移動機器人智能車場停車資源調度分配

鄭曉軍, 郭星澤, 寧詩鐸, 鄭人豪， 史彥軍

(1.大連交通大學機械工程學院， 大連 116028； 2.大連理工大學機械工程學院， 大連 116024)

“十四五”時期，推動高質量發(fā)展，構筑美好生活新圖景，迫切需要新興產業(yè)和技術的強力支撐，生活智能化、制造智能化成為社會的重要發(fā)展目標。截至2021年6月，中國汽車保有量已達3.84億輛，“停車難”成為人們出行和汽車制造業(yè)存放車輛的新挑戰(zhàn)。移動機器人(automated guided vehicle，AGV)智能停車場以其智能化程度高、占地面積小、存取車方便、降低停車者無效巡游時間等優(yōu)勢展示出強大的市場潛力，可廣泛應用于如民航業(yè)停車場[1]、汽車制造企業(yè)的產品停放場區(qū)[2]以及大型商圈等對停放車輛有大量需求的場景。

在AGV的關鍵技術研究中，AGV的調度分配研究是主要難點和研究熱點。目前，關于AGV的有關調度分配研究比較全面，但大多數以柔性制造系統(tǒng)和自動化碼頭為應用場景，中外學者對AGV系統(tǒng)的研究主要集中在路徑規(guī)劃、任務調度和沖突處理上[3]；路徑規(guī)劃的研究有：文獻[4]針對目前倉儲AGV路徑規(guī)劃中存在的轉彎次數多、沖突節(jié)點多的問題，對單AGV提出了一種基于障礙預測的改進A*算法；文獻[5]提出了兩階段優(yōu)化算法，首先根據AGV行駛規(guī)則生成初始路徑，然后設計碰撞檢測及避免算法對可能發(fā)生沖突的路徑交叉點進行主動避撞調度。任務調度的文獻有：文獻[6]針對AGV的柔性作業(yè)車間調度問題，以最小化完工時間為目標，提出一種灰狼算法進行求解，有效平衡了算法的勘探能力和局部搜索能力；文獻[7]對具有有限物流運輸能力的智能車間AGV調度算法展開研究，為企業(yè)配置AGV小車及選擇AGV調度規(guī)則提供一種有效的方法，保證了車間的生產效率；對于沖突處理的文獻有：文獻[8]針對實時動態(tài)環(huán)境下自動化分揀倉庫中多AGV任務指派和路徑規(guī)劃的協(xié)同調度問題，以最小化加權總搬運完成時間為目標建立了混合整數線性規(guī)劃模型，并提出一種集中與分散決策相結合的在線協(xié)同調度算法；文獻[9]提出了一種基于停車等待、臨時規(guī)避以及重新規(guī)劃路徑相結合的沖突解決策略，將沖突節(jié)點的路口數量、臨時規(guī)避時間與重新規(guī)劃路徑所用的時間進行綜合考慮。

上述學者均通過對AGV的調度分配與路徑規(guī)劃進行研究，提升了AGV的運輸效率，但國內大多數研究對AGV運行情況的預測不足，大部分研究都是在沖突發(fā)生后進行協(xié)調，會造成AGV不必要的等待和停頓，對沖突預測問題考慮較少[10]。

在比較停車領域的AGV與物流、柔性制造車間等領域的AGV時發(fā)現(xiàn)：停車領域的AGV在任務規(guī)劃時可以自由地選擇目標停車位，故需著重研究停車資源的分配結果對AGV智能停車場運輸效率的影響。基于以上研究，現(xiàn)針對大型商圈、民航業(yè)停車場在高峰時段以及汽車制造業(yè)停車場在生產制造后，要求同時、一次性大量的停車背景下，提出一種基于停車代價計算模型，通過對不同分配方案的停車代價進行計算，通過預測任務之間可能出現(xiàn)的路徑干涉降低AGV在運輸期間出現(xiàn)的沖突，并通過仿真驗證合理分配停車資源，能夠有效提升整個停車場的運輸效率，從源頭減少沖突的產生。

1 停車流程問題分析及環(huán)境建模

1.1 停車流程分析

AGV智能停車場的停車流程可分為3個部分：存取車請求、調度系統(tǒng)分配以及AGV系統(tǒng)運輸，用戶在發(fā)送停車請求后就可以離開，調度系統(tǒng)在生成任務時需要為車輛分配停車位資源與泊車AGV，然后對泊車路徑進行規(guī)劃，最后由AGV系統(tǒng)進行運輸，如圖1所示。本文研究主要集中在調度系統(tǒng)生成任務的停車位分配。

圖1 停車系統(tǒng)示意圖Fig.1 Parking system diagram

AGV智能停車場在高峰時段正常運轉時，需要處理大量的任務請求，AGV系統(tǒng)需要不斷將任務請求納入到待執(zhí)行任務隊列；由于任務量巨大，一臺AGV無法在規(guī)定時間內完成任務，一般需要多臺AGV同時進行工作。但投入越多的停車AGV，會帶來更高的成本與管理難題[11]，系統(tǒng)也越容易陷入局部或全局死鎖，造成AGV智能停車場的效率降低。

相較于柔性制造業(yè)車間、自動化碼頭等領域，經過改造后的停車場布局比較規(guī)整，規(guī)劃出的路徑比較單一，很難規(guī)劃出多條路徑；而為了提高停車場的最大增容率，一般將場內通道設置為雙向單車道(同一時間、同一方向只能被一輛AGV占用)，也增加路徑之間的干涉，AGV在運輸時更容易陷入沖突，造成不必要的等待和停頓：如圖2所示，假設任務m1為存車任務將待停車輛從v1運輸至目標停車位v2，任務m2為回程任務從v3至v1，任務m1的路徑集合為{e1，e2，e3，e4}，任務m2的路徑集合為{e1，e2，e5}，兩個任務之間的干涉路徑集合為{e1，e2}，假設任務m1的優(yōu)先級高于任務m2的優(yōu)先級，那么任務m2的AGV必須等待任務m1的AGV完成干涉路徑{e1，e2}后才能開始繼續(xù)行進，造成了等待時間的浪費。

圖2 停車場路徑干涉Fig.2 Path interference diagram

若AGV系統(tǒng)在進行任務時，優(yōu)先級低的任務未進行等待，開始了路徑干涉部分的任務，則AGV之間就會陷入直線相向沖突死鎖和轉彎沖突死鎖，如圖 1所示，AGV需要將死鎖信息傳回調度系統(tǒng)，調度系統(tǒng)需要根據沖突解決策略安排某一任務進行等待或重新對任務路徑二次規(guī)劃，同樣造成了時間和停車資源上的浪費，而引入的AGV數量越多，停車場內的等待和沖突產生的就會越多，造成的資源浪費越多，故通過合理規(guī)劃停車任務的停車位，將相鄰任務的停車位錯開，可以合理減少相鄰任務的路徑干涉，提高停車場的運輸效率。

1.2 環(huán)境建模

在現(xiàn)有的AGV路徑規(guī)劃研究中，已得到應用的環(huán)境建模方法有自由空間法、柵格法和拓撲地圖法等。其中，柵格法的柵格具有信息量少、結構簡單的特點[12-13]，故柵格地圖應用比較廣泛；但粒度不容易界定，且建模效率不高，拓撲法的構造過程簡單、存儲小空間且計算效率高；基于典型停車場特征，本文采用拓撲法對停車場模型進行建模，該方法是將特殊位置的狀態(tài)和位置信息抽象為節(jié)點形式，用有向線段連接相鄰的節(jié)點，表征連通狀態(tài)，形成點線相連的關系網，拓撲地圖在搜索計算最短路徑時的復雜程度取決于停車環(huán)境的可通行的節(jié)點的數量[14]。

圖3 停車場拓撲模型Fig.3 Topological model of parking lot

本文研究的停車場的信息如表1所示。

根據所研究的問題，對停車場的通用假設參考文獻[9]，在此基礎上，針對實際研究的停車場要求，本文研究提出了新的假設。

表1 改造停車場信息表Table 1 Modification of parking lot information

(1)在出入口一次只能有一輛AGV進行裝車，需要等到載車的AGV進入停車場后才能進行下一輛車的裝車。

(2)為防止停車場內趕超沖突，前一輛AGV進入停車場后，下一輛AGV需要等待10 s后進入停車場。

(3)在大型商圈、民航業(yè)停車場以及汽車制造業(yè)停車場在生產制造后，等待停入停車場的車輛數>停車內空余的停車位數量。

結合實際的AGV智能停車場環(huán)境及以上特征，將AGV智能停車場的現(xiàn)場物理環(huán)境抽象建立拓撲結構模型，繪制路口節(jié)點和各功能站點的連通圖，如圖3所示。

2 代價模型構建及資源分配算法

2.1 代價評價模型

智能停車場在接收調度任務后，需要根據停車位分配模型對停車位資源進行分配，在進行分配后，由停車AGV進行運輸。在此基礎上引入“代價”的概念，在調度系統(tǒng)將停車資源分配后，進行車輛停入停車位的代價計算，作為停車資源分配方案的評價指標，代價可以是不同的概念：死鎖出現(xiàn)次數最小，停車時間最少等，也可以是不同指標的融合，停車代價的計算流程如圖 4所示。當待停車輛發(fā)送停車請求時，一般會根據停車資源分配方法對待停車輛的車位進行分配；當為待停車輛分配車位后，需要利用本文提出的代價評價模型對車位分配的方案進行評價，最后根據評價出的代價選擇最優(yōu)的車位分配方案。

圖4 停車代價計算流程Fig.4 Flow chart of parking cost calculation

本文研究提出了一種全新的智能停車場停車位分配方案的代價計算的概念，假設現(xiàn)有|I|輛待停車輛等待停入停車場，智能停車場內有|J|個空閑停車位，則智能停車場接收到的任務集合為M={I,J}，M集合中的元素為mij，表示將當前待停車輛i停入停車位j。

本文模型建立的思想為將|M|個任務中，賦給每一個任務mij停車代價，在計算過程中，將每一輛待停車輛i停入空閑停車位j都會計算出停車代價cm，在整體規(guī)劃出停車任務后，以整體的停車代價最小為目標函數。

目標函數為

(1)

式(1)中：z為完成停車任務后的代價之和；I為待停車輛集合；J為空閑停車位集合；Cm為任務m的停車代價。

本文模型將接受任務的停車代價最小為目標函數，約束為將可以停入停車場的待停車輛均停入停車場內，通過合理降低智能停車場的總體停車代價，提高智能停車場的吞吐效率。

代價函數可以隨著研究的深入引入不同的概念，將其設置成總停車時長最小、AGV消耗電量最小，轉彎次數最少、行駛路程最短、死鎖次數最小等等不同的概念，也可以是不行概念的融合，將其設置的越精細，對AGV的運行預測的越準確，對提升停車場的效率效果越明顯。

2.2 路徑干涉概率模型

代價模型旨在預測AGV的運行情況，本文通過引入路徑干涉概率的概念，通過計算停車資源分配方案的路徑干涉概率，對AGV之間可能出現(xiàn)的沖突進行預測，通過減少AGV之前可能出現(xiàn)的沖突，降低等待時間和沖突的產生，提高停車場的運輸效率。路徑可以描述為圖論問題[15]，表示為r={V,E}；對于每一個任務m，調度系統(tǒng)都會規(guī)劃為其規(guī)劃出一條路徑，在得到任務m的路徑Rm后，可以對任務m的總體路徑進行計算，任務的m總路徑長度為

(2)

式(2)中：lm為任務m規(guī)劃出的路徑Rm的總長度；Rm為任務的路徑集合m；lr為任務某一段路徑的長度。

本文引入的干涉概率表示為任務m在運輸過程中可能與其他任務的路徑干涉的概率。任務m與任務m′的中的路徑是否干涉(pmm′)表示為

(3)

任務m與任務m′的中的干涉路徑長度計算公式為

(4)

在得到任務m與任務m′的之間的干涉路徑的長度后，任務m與任務m′的干涉概率(pmm′)計算公式為

(5)

在得到任務m與任務m′的干涉概率后，就可以整體對停車任務的干涉概率進行計算，計算公式為

(6)

式(6)中：cm為任務m的停車代價。

基于停車場干涉概率最小的計算公式為

(7)

2.3 停車資源分配方法

目前智能停車場常用的停車資源調度分配策略一般為隨機分配(randomly allocate the parking lot to the pick-up point, RA)和優(yōu)先分配距離取車點最近的停車位(first allocate the nearest parking lot to the pick-up point, FAN)兩種方法[16]。本文在此基礎上加入了交替分配按照距離取車點最近的停車位(alternately allocate the nearest parking lot to the pick-up point, AAN)和根據干涉概率整體規(guī)劃分配停車位(according to the probability of interference to allocate the parking lot to the pick-up point, APIA)兩種方法。AAN為根據停車點距離出入口的距離，按照一遠一近交替將車輛停入停車場，APIA為按照沖突概率整體對停車資源進行規(guī)劃。

一般為節(jié)省智能停車場內的資源消耗，會將待停車輛集中停放在同一區(qū)域以節(jié)省資源浪費，故本文將智能停車場劃分為A、B、C三個區(qū)域，根據不同的待停車輛密度開放不同的區(qū)域。

假設目前停車場內沒有車輛，待停車輛等待停入停車場，根據不同的待停車輛數量開放區(qū)域的方案如表2所示，分區(qū)結果如圖3所示。

表2 不同停車數量開放區(qū)域表Table 2 Open area with different number of parking

3 算例分析與驗證

3.1 計算及仿真結果

2.3節(jié)介紹了現(xiàn)存的兩種停車資源分配方法RA與FAN，在此基礎上提出了AAN與APIA兩種方法。由于隨機分配算法無法計算出穩(wěn)定的結果，很難對計算結果進行量化分析以及與其他算法進行對比，故將其舍棄，著重對FAN、AAN、APIA 3種方法進行計算；FAN、AAN直接可以按照規(guī)則對其進行分配，并計算分配方案的累計沖突概率。而AIPA方法需要對停車資源按照目標函數進行全局規(guī)劃，本文利用JAVA語言對停車方案進行編碼，得到一個沒有重復元素的排列編碼，如圖 5所示，將累計沖突概率設置為適應度函數，利用MOEA框架下的遺傳算法進行整體規(guī)劃，算法中的選擇操作使用輪盤賭操作，算法中的交叉與變異算子均使用正常排列編碼的單點交叉和基本位變異，得到的停車位分配順序與累計沖突概率如表3所示。

圖5 解碼示意圖Fig.5 Decoding diagram

而累計干涉概率還是對AGV的運行情況進行預測，本文為證明減少任務之間的累計干涉概率對停車場運輸效率的影響，利用Plant Simulation軟件對停車場進行仿真：對不同AGV數量進行仿真，將所有停車任務均已完成且最后一輛AGV返回出入口的時間作為仿真總停車時長(total parking duration，TPD)，將仿真總時長作為停車場運輸效率的評價指標，并統(tǒng)計不同情況下的沖突等待次數(total waiting times，TWT)與總等待時間(total waiting duration，TWD)，結果如表4所示。

3.2 結果分析

為了更直觀地觀察路徑干涉概率數據，將路徑干涉概率的數據繪制為折線圖，如圖 6所示，在不同方案下，路徑之間的干涉概率呈下降趨勢。從圖6中可以看出，3種方案的下降趨勢：方案3>方案2>方案1，在方案1中，開放區(qū)域的停車位數量較少，路徑之間的干涉概率FAN>APIA>AAN，且干涉概率相差不大，故本文提出的模型在這種情況下效果并不明顯；而在開放區(qū)域的停車位數量超過28時，從圖6中可以明顯看出，路徑的干涉概率FAN>AAN>APIA，累計沖突概率下降明顯。在停車資源分配方案研究時，若在停車位數量比較少，本文所研究的路徑干涉概率并不明顯適用，在停車要求少時，如方案1的情況，利用不同方法所求出的累計沖突概率下降率很小，故本文所研究的情況主要適用于大型商圈、民航業(yè)停車場在高峰時段以及汽車制造業(yè)停車場在生產制造后，要求同時、一次性大量的停車背景。

表3 累計干涉概率計算結果表Table 3 The calculation result of cumulative interference probability

表4 仿真數據表Table 4 Simulation results

圖6 干涉概率計算結果Fig.6 The calculation result of cumulative interference probability

如圖7所示，利用Plant Simulation進行投放4輛AGV進行仿真的結果表明，總仿真時長的大小與干涉概率的大小呈正相關關系，圖中標識出在方案2運輸時，累計干涉概率在減小，隨之總仿真時長TPD也隨之減小。

圖7 4輛AGV仿真結果Fig.7 Simulation results using 4 AGVs for transportation

由圖 6可以得出，本文提出的干涉概率模型的效果在停車位數量比較多時比較明顯的，故本文著重研究在方案3下的沖突概率與仿真總時間關系。

圖8 不同AGV下的仿真時長Fig.8 The Simulation duration under different AGV transportation schemes

圖9 等待時間占比圖Fig.9 The proportion of waiting time

由圖 8可以看出，在方案1下，當只投放2輛AGV時，總仿真時長比較大，且并不隨著累計干涉概率的下降呈現(xiàn)TPD：FAN>AAN>APIA，而是FAN>APIA>AAN，這也說明了當只有2輛AGV運行時，AGV之間的沖突比較少，從仿真過程中及圖 9可以看出，兩輛AGV在大部分時間均處于運行狀態(tài)，待停車輛在等待的時間占停車總時間的比重很小，停車場的效率較低，故應該繼續(xù)投入AGV以減少總仿真時長，增加智能停車場的吞吐效率。

圖10 仿真過程圖Fig.10 Simulation process

如圖 9所示，在投入越多的AGV時，在仿真過程中等待時間的占比是明顯增大的，這說明當AGV數量增加時，AGV之間的沖突明顯增多，與圖 8結合來看，當投入3輛AGV時，等待時間并沒有明顯增多，而多投入了一臺AGV，可以明顯增加停車場的運輸效率；而當投入4臺AGV時，等待時間的占比從25%躍遷至82%，這時投入AGV的效果適得其反，由于AGV之間的沖突明顯增多，造成等待時間的增加、停車場的資源浪費，降低了停車場的運輸效率。而當使用3輛AGV及以上時，F(xiàn)AN方法的等待時間明顯較AAN與APIA方法的等待時間長，而從圖 11可以看出，在圖 11 (a)中，在3 500 s以后，等待時間出現(xiàn)的頻次增多且時間越來越長，而通過AAN和APIA方法對停車資源進行規(guī)劃后，沖突概率的減小使得AGV的等待時間平均且分散，這是由于FAN方法在分配停車資源時，任務之間的車位非常近，尤其到了后期，任務的停車資源集中在C區(qū)，C區(qū)的停車位相較于A、B區(qū)距離更遠，AGV在回到出入口裝車后，需等待C區(qū)的AGV在停車后經過漫長的路徑返回出入口，且隨著完成任務越來越多，等待時間就越來越長，如圖10所示，在后期停車時，必須等待右上方的車輛經過漫長的主干道，左下方的AGV才能開始任務，而AAN與APIA將相鄰任務的停車位比較分散，如圖11(b)和圖11(c)所示，AGV的等待時間比較分散，并不會出現(xiàn)圖 10所示的情況。

圖11 方案3等待時間分布圖Fig.11 The distribution of waiting time under different methods

4 結論

停車領域的AGV可以自由地選擇終點，而通過對停車資源進行合理分配，通過對AGV之間可能出現(xiàn)的沖突進行預測并減少沖突，可以有效降低AGV的等待時間，提高智能停車場的運輸效率。在停車場對停車任務有大量需求時，路徑之間的干涉比較多，若不對沖突進行預測，就會造成大量等待時間的浪費。本文做出了以下創(chuàng)新工作。

(1)針對智能停車場可以自由選擇終點這一特點，提出了一種全新的停車分配方案代價評價模型，將路徑干涉概率模型引入代價評價模型，通過路徑干涉概率模型對停車位分配方案進行評價。

(2)針對現(xiàn)有的停車資源分配方法在停車高峰需求的情況下魯棒性不強的情況，本文提出了基于距離交替分配以及基于遺傳算法整體分配兩種算法，對停車位進行分配。

經過仿真驗證，在44個停車位，投入運輸4輛AGV的情況下，通過基于遺傳算法的整體分配方法可以將總停車時長降低30.4%。