[發(fā)明專利]基于增強(qiáng)型Dijkstra算法的無信號燈交叉路口車輛調(diào)度方法

有效

• 申請?zhí)枺?/td>: 202110596352.8
• 申請日: 2021-05-30
• 公開（公告）號: CN113313957B
• 公開（公告）日: 2022-07-05
• 發(fā)明（設(shè)計）人: 孫寧;吳偉豪;肖廣兵;張涌;徐曉美;潘義勇;馬健霄
• 申請（專利權(quán)）人: 南京林業(yè)大學(xué)
• 主分類號: G08G1/0967
• 分類號: G08G1/0967;G08G1/0968
• 代理公司: 南京科闊知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 32400
• 代理人: 王清義

針對車輛在通過無信號燈交叉路口時存在等待時間長，通行效率低的問題，提出了一種基于增強(qiáng)型Dijkstra算法的無信號燈交叉路口車輛調(diào)度方法。本專利以智能車輛為研究對象，把交叉路口網(wǎng)格化，由網(wǎng)格之間的連線描述車輛的行駛軌跡，創(chuàng)新的制定了動態(tài)網(wǎng)格權(quán)值賦值原則，通過確定網(wǎng)格的方向權(quán)值、安全權(quán)值和優(yōu)先級權(quán)值為車輛尋找到通行時間最短的路徑。增強(qiáng)型Dijkstra算法在Dijkstra算法的基礎(chǔ)上進(jìn)行改進(jìn)，實(shí)現(xiàn)了動態(tài)權(quán)值下求最短路徑的目的，可以根據(jù)實(shí)際車輛環(huán)境靈活調(diào)整每個車輛的行駛軌跡。仿真結(jié)果表明，增強(qiáng)型Dijkstra算法調(diào)度能夠在保持較低的沖突次數(shù)的前提下減少車輛總通行時間，在一定條件下相比Dijkstra算法，車輛平均停車延誤減少1.5s，沖突率下降13％。

技術(shù)領(lǐng)域

本發(fā)明涉及無信號燈交叉路口車輛調(diào)度方法，尤其是采用Dijkstra算法的車輛調(diào)度方法。

背景技術(shù)

智能車輛在無信號燈交叉路口的通行調(diào)度是當(dāng)前無人駕駛領(lǐng)域的研究熱點(diǎn)。調(diào)度策略的優(yōu)劣直接影響到智能車輛在交叉路口的通行效率和行駛安全。但受制于車載傳感器的感知范圍，以及樓宇、車體等對電磁信號的遮擋，每個智能車輛只能感知到局部道路信息，難以實(shí)現(xiàn)交叉路口的全局優(yōu)化調(diào)度，頻繁發(fā)生沖突起停、碰撞追尾等問題。這不僅降低了智能車輛在交叉路口的通行效率，還增加了交通事故發(fā)生的風(fēng)險。

相關(guān)交叉路口調(diào)度方案可分為集中式和分布式兩類。集中式車輛調(diào)度以全局最優(yōu)為調(diào)度目標(biāo)，通常由智能路基單元(Road Side Unit,RSU)搜集獲取全局信息并進(jìn)行調(diào)度規(guī)劃，再將調(diào)度策略發(fā)送至每個智能車輛。集中式車輛調(diào)度模式簡單，但對路基單元的算力要求較高，且網(wǎng)絡(luò)負(fù)載過于集中，系統(tǒng)可靠性較差。相比之下，分布式車輛調(diào)度采用去中心化的系統(tǒng)架構(gòu)，每個智能車輛僅利用自身感知的局部信息進(jìn)行調(diào)度規(guī)劃。雖然分布式車輛調(diào)度模式存在全局尋優(yōu)困難等問題，但不依賴于中心節(jié)點(diǎn)(如路基單元RSU等)，具有算量小、負(fù)載相對均衡等優(yōu)點(diǎn)，表現(xiàn)出較好的應(yīng)用前景。

當(dāng)前主流的分布式車輛調(diào)度方案主要分為以下三類：

(1)網(wǎng)格權(quán)值法，其基本原理是將交叉路口描述為一個網(wǎng)格圖，每個網(wǎng)格具有不同權(quán)值，每個車輛依據(jù)網(wǎng)格權(quán)值選擇下一步前進(jìn)的目標(biāo)網(wǎng)格，進(jìn)而得出最優(yōu)調(diào)度策略，如改進(jìn)Dijkstra算法、快速擴(kuò)展隨機(jī)樹(RRT)算法和A*算法等。劉子豪等人結(jié)合跳躍點(diǎn)搜索理論，用選取的關(guān)鍵點(diǎn)代替了傳統(tǒng)A*算法中Openlist和Closelist的點(diǎn)，提高了調(diào)度算法的尋優(yōu)速度；姜辰凱等人提出了一種基于時間窗的改進(jìn)Dijkstra算法，實(shí)現(xiàn)多AGV的動態(tài)路徑規(guī)劃。該算法能夠在最優(yōu)路徑下避免沖突與死鎖，使系統(tǒng)具有較好的魯棒性。吳偉等人提出了交叉路口網(wǎng)格化下的車輛調(diào)度優(yōu)化模型和時間優(yōu)化分配算法，以交叉口總延誤最小為控制目標(biāo)，運(yùn)用分支定界法確定車輛在交叉口的最佳行駛路徑、速度及駛?cè)霑r刻。此類算法雖然模型簡單，但均屬于靜態(tài)算法，并不是適用于移動車輛較多的路口調(diào)度場景。

(2)仿生調(diào)度法，即智能車輛通過模擬自然界生物的行為規(guī)律對交叉路口下的調(diào)度策略進(jìn)行尋優(yōu)，具有自學(xué)習(xí)、自決定等特點(diǎn)，如優(yōu)化粒子群算法、改進(jìn)遺傳算法和人工魚群算法等。Zhuofei Li等人基于遺傳算法的優(yōu)化方法對車輛通過序列進(jìn)行決策，同時計算最優(yōu)車輛軌跡，降低了交叉口平均行程時延；覃磊等人提出了一種基于改進(jìn)的人工魚群算法的車輛優(yōu)化調(diào)度方法，首先將車輛與路徑通過三維粒子編碼方法進(jìn)行編碼，構(gòu)造有效的車輛路徑，再通過原始算法進(jìn)行迭代，尋找最優(yōu)解，仿真表明該算法具有較快的收斂速度，而且以較大的概率收斂于人工魚群算法的最優(yōu)解。陳秋蓮等人本專利提出了一種基于神經(jīng)網(wǎng)絡(luò)和三次樣條曲線函數(shù)的改進(jìn)粒子群算法，統(tǒng)一了靜態(tài)和動態(tài)障礙物環(huán)境表示和碰撞檢測模型，能夠快速規(guī)劃出光滑的無碰撞機(jī)器人路徑，使得路徑長度更短，算法的迭代次數(shù)更少。Jian Wang等人提出了一種解決車輛調(diào)度問題的混合蟻群算法，在分析其優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了考慮實(shí)時路況的蟻群算法的改進(jìn)策略，提高了求解動態(tài)VRP的算法性能。此類算法對環(huán)境、參數(shù)和任務(wù)的變化具有較強(qiáng)的適用性和靈活性，但其全局搜索能力弱，尋優(yōu)時間受個體分布的影響明顯。