鄭曉軍, 郭星澤, 寧詩(shī)鐸, 鄭人豪， 史彥軍

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

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

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

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

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

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

1.1 停車(chē)流程分析

AGV智能停車(chē)場(chǎng)的停車(chē)流程可分為3個(gè)部分：存取車(chē)請(qǐng)求、調(diào)度系統(tǒng)分配以及AGV系統(tǒng)運(yùn)輸，用戶(hù)在發(fā)送停車(chē)請(qǐng)求后就可以離開(kāi)，調(diào)度系統(tǒng)在生成任務(wù)時(shí)需要為車(chē)輛分配停車(chē)位資源與泊車(chē)AGV，然后對(duì)泊車(chē)路徑進(jìn)行規(guī)劃，最后由AGV系統(tǒng)進(jìn)行運(yùn)輸，如圖1所示。本文研究主要集中在調(diào)度系統(tǒng)生成任務(wù)的停車(chē)位分配。

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

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

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

圖2 停車(chē)場(chǎng)路徑干涉Fig.2 Path interference diagram

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

1.2 環(huán)境建模

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

圖3 停車(chē)場(chǎng)拓?fù)淠Ｐ虵ig.3 Topological model of parking lot

本文研究的停車(chē)場(chǎng)的信息如表1所示。

根據(jù)所研究的問(wèn)題，對(duì)停車(chē)場(chǎng)的通用假設(shè)參考文獻(xiàn)[9]，在此基礎(chǔ)上，針對(duì)實(shí)際研究的停車(chē)場(chǎng)要求，本文研究提出了新的假設(shè)。

表1 改造停車(chē)場(chǎng)信息表Table 1 Modification of parking lot information

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

(2)為防止停車(chē)場(chǎng)內(nèi)趕超沖突，前一輛AGV進(jìn)入停車(chē)場(chǎng)后，下一輛AGV需要等待10 s后進(jìn)入停車(chē)場(chǎng)。

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

結(jié)合實(shí)際的AGV智能停車(chē)場(chǎng)環(huán)境及以上特征，將AGV智能停車(chē)場(chǎng)的現(xiàn)場(chǎng)物理環(huán)境抽象建立拓?fù)浣Y(jié)構(gòu)模型，繪制路口節(jié)點(diǎn)和各功能站點(diǎn)的連通圖，如圖3所示。

2 代價(jià)模型構(gòu)建及資源分配算法

2.1 代價(jià)評(píng)價(jià)模型

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

圖4 停車(chē)代價(jià)計(jì)算流程Fig.4 Flow chart of parking cost calculation

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

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

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

(1)

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

本文模型將接受任務(wù)的停車(chē)代價(jià)最小為目標(biāo)函數(shù)，約束為將可以停入停車(chē)場(chǎng)的待停車(chē)輛均停入停車(chē)場(chǎng)內(nèi)，通過(guò)合理降低智能停車(chē)場(chǎng)的總體停車(chē)代價(jià)，提高智能停車(chē)場(chǎng)的吞吐效率。

代價(jià)函數(shù)可以隨著研究的深入引入不同的概念，將其設(shè)置成總停車(chē)時(shí)長(zhǎng)最小、AGV消耗電量最小，轉(zhuǎn)彎次數(shù)最少、行駛路程最短、死鎖次數(shù)最小等等不同的概念，也可以是不行概念的融合，將其設(shè)置的越精細(xì)，對(duì)AGV的運(yùn)行預(yù)測(cè)的越準(zhǔn)確，對(duì)提升停車(chē)場(chǎng)的效率效果越明顯。

2.2 路徑干涉概率模型

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

(2)

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

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

(3)

任務(wù)m與任務(wù)m′的中的干涉路徑長(zhǎng)度計(jì)算公式為

(4)

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

(5)

在得到任務(wù)m與任務(wù)m′的干涉概率后，就可以整體對(duì)停車(chē)任務(wù)的干涉概率進(jìn)行計(jì)算，計(jì)算公式為

(6)

式(6)中：cm為任務(wù)m的停車(chē)代價(jià)。

基于停車(chē)場(chǎng)干涉概率最小的計(jì)算公式為

(7)

2.3 停車(chē)資源分配方法

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

一般為節(jié)省智能停車(chē)場(chǎng)內(nèi)的資源消耗，會(huì)將待停車(chē)輛集中停放在同一區(qū)域以節(jié)省資源浪費(fèi)，故本文將智能停車(chē)場(chǎng)劃分為A、B、C三個(gè)區(qū)域，根據(jù)不同的待停車(chē)輛密度開(kāi)放不同的區(qū)域。

假設(shè)目前停車(chē)場(chǎng)內(nèi)沒(méi)有車(chē)輛，待停車(chē)輛等待停入停車(chē)場(chǎng)，根據(jù)不同的待停車(chē)輛數(shù)量開(kāi)放區(qū)域的方案如表2所示，分區(qū)結(jié)果如圖3所示。

表2 不同停車(chē)數(shù)量開(kāi)放區(qū)域表Table 2 Open area with different number of parking

3 算例分析與驗(yàn)證

3.1 計(jì)算及仿真結(jié)果

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

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

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

3.2 結(jié)果分析

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

表3 累計(jì)干涉概率計(jì)算結(jié)果表Table 3 The calculation result of cumulative interference probability

表4 仿真數(shù)據(jù)表Table 4 Simulation results

圖6 干涉概率計(jì)算結(jié)果Fig.6 The calculation result of cumulative interference probability

如圖7所示，利用Plant Simulation進(jìn)行投放4輛AGV進(jìn)行仿真的結(jié)果表明，總仿真時(shí)長(zhǎng)的大小與干涉概率的大小呈正相關(guān)關(guān)系，圖中標(biāo)識(shí)出在方案2運(yùn)輸時(shí)，累計(jì)干涉概率在減小，隨之總仿真時(shí)長(zhǎng)TPD也隨之減小。

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

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

圖8 不同AGV下的仿真時(shí)長(zhǎng)Fig.8 The Simulation duration under different AGV transportation schemes

圖9 等待時(shí)間占比圖Fig.9 The proportion of waiting time

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

圖10 仿真過(guò)程圖Fig.10 Simulation process

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

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

4 結(jié)論

停車(chē)領(lǐng)域的AGV可以自由地選擇終點(diǎn)，而通過(guò)對(duì)停車(chē)資源進(jìn)行合理分配，通過(guò)對(duì)AGV之間可能出現(xiàn)的沖突進(jìn)行預(yù)測(cè)并減少?zèng)_突，可以有效降低AGV的等待時(shí)間，提高智能停車(chē)場(chǎng)的運(yùn)輸效率。在停車(chē)場(chǎng)對(duì)停車(chē)任務(wù)有大量需求時(shí)，路徑之間的干涉比較多，若不對(duì)沖突進(jìn)行預(yù)測(cè)，就會(huì)造成大量等待時(shí)間的浪費(fèi)。本文做出了以下創(chuàng)新工作。

(1)針對(duì)智能停車(chē)場(chǎng)可以自由選擇終點(diǎn)這一特點(diǎn)，提出了一種全新的停車(chē)分配方案代價(jià)評(píng)價(jià)模型，將路徑干涉概率模型引入代價(jià)評(píng)價(jià)模型，通過(guò)路徑干涉概率模型對(duì)停車(chē)位分配方案進(jìn)行評(píng)價(jià)。

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

經(jīng)過(guò)仿真驗(yàn)證，在44個(gè)停車(chē)位，投入運(yùn)輸4輛AGV的情況下，通過(guò)基于遺傳算法的整體分配方法可以將總停車(chē)時(shí)長(zhǎng)降低30.4%。