[發(fā)明專利]基于改進(jìn)蟻群算法的高速公路多點(diǎn)協(xié)同救援路徑規(guī)劃方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011036654.1
• 申請(qǐng)日: 2020-09-27
• 公開(kāi)（公告）號(hào): CN112146673B
• 公開(kāi)（公告）日: 2022-07-22
• 發(fā)明（設(shè)計(jì)）人: 范曉武
• 申請(qǐng)（專利權(quán)）人: 浙江綜合交通大數(shù)據(jù)中心有限公司
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34;G05D1/02
• 代理公司: 杭州浙科專利事務(wù)所(普通合伙) 33213
• 代理人: 孫孟輝

1.一種基于改進(jìn)蟻群算法的高速公路多點(diǎn)協(xié)同救援路徑規(guī)劃方法，其特征在于，包括以下步驟：

(1)根據(jù)高速公路路網(wǎng)結(jié)構(gòu)信息生成高速公路路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖，獲取高速公路路網(wǎng)交通流數(shù)據(jù)和救援起點(diǎn)與終點(diǎn)信息；

(2)綜合考慮路徑通行時(shí)間少和路徑安全性高兩項(xiàng)優(yōu)化目標(biāo)，設(shè)計(jì)路徑多目標(biāo)優(yōu)化評(píng)價(jià)函數(shù)；

(3)基于高速公路救援路徑規(guī)劃的特點(diǎn)出發(fā)，設(shè)計(jì)改進(jìn)的蟻群算法：根據(jù)事故點(diǎn)的位置改進(jìn)蟻群算法的初始信息素濃度設(shè)置；綜合下一目標(biāo)路徑長(zhǎng)度最短、下一目標(biāo)距事故點(diǎn)的直線距離最短、搜索角度最小及路段風(fēng)險(xiǎn)性小這些要求，設(shè)計(jì)啟發(fā)函數(shù)；引入阻抗時(shí)間，使用隨機(jī)選擇機(jī)制改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則；改進(jìn)局部信息素更新和全局信息素更新結(jié)合策略；設(shè)計(jì)信息素?fù)]發(fā)系數(shù)隨迭代次數(shù)增加而逐漸減小的策略；

(4)采用改進(jìn)的蟻群算法，以多目標(biāo)優(yōu)化評(píng)價(jià)函數(shù)為指標(biāo)，規(guī)劃各救援點(diǎn)到各事故點(diǎn)的最優(yōu)救援路徑；

(5)針對(duì)各事故點(diǎn)有各自的救援車(chē)輛需求數(shù)，各救援點(diǎn)需要派遣救援車(chē)輛進(jìn)行協(xié)同救援的問(wèn)題，建立多救援點(diǎn)協(xié)同救援派遣數(shù)學(xué)模型，將供需不平衡問(wèn)題轉(zhuǎn)換為供需平衡問(wèn)題，采用表上作業(yè)法確定救援車(chē)輛派遣方案，得到各救援點(diǎn)到各事故點(diǎn)的派遣車(chē)輛數(shù)；

在步驟(2)中，所述綜合考慮路徑通行時(shí)間少和路徑風(fēng)險(xiǎn)性小兩項(xiàng)優(yōu)化目標(biāo)，設(shè)計(jì)路徑多目標(biāo)優(yōu)化評(píng)價(jià)函數(shù)，具體如下：

路徑評(píng)價(jià)函數(shù)公式為：

min Z＝ω₁Z₁+ω₂Z₂ (1)

其中,Z表示多目標(biāo)優(yōu)化路徑評(píng)價(jià)函數(shù)的數(shù)值，Z₁表示該路徑通行所花費(fèi)的時(shí)間目標(biāo)評(píng)價(jià)函數(shù)，Z₂表示道路安全因素目標(biāo)評(píng)價(jià)函數(shù)；ω₁，ω₂分別表示Z₁，Z₂所占比重，采用專家打分法根據(jù)實(shí)際情況而定；

由于該路徑通行所花費(fèi)的時(shí)間目標(biāo)評(píng)價(jià)函數(shù)和道路安全因素目標(biāo)評(píng)價(jià)函數(shù)的單位不同，所以在計(jì)算總目標(biāo)評(píng)價(jià)函數(shù)之前應(yīng)先無(wú)量綱化規(guī)范各目標(biāo)評(píng)價(jià)函數(shù)：

其中，Z_i,i＝1,2表示第i個(gè)目標(biāo)評(píng)價(jià)函數(shù)，Z_i,min表示第i個(gè)目標(biāo)評(píng)價(jià)函數(shù)的最小值，Z_i,max表示第i個(gè)目標(biāo)評(píng)價(jià)函數(shù)的最大值；

最小路徑通行時(shí)間目標(biāo)

路徑通行時(shí)間反應(yīng)了救援車(chē)輛在高速公路上前往事故發(fā)生點(diǎn)花費(fèi)最短時(shí)間的要求，車(chē)輛在路段ij上的通行時(shí)間表示為t_ij，總路徑通行時(shí)間表示為Y₁：

式(3)中，t₀為該路段自由流行駛時(shí)間，Q為該路段的實(shí)際交通流量，C為該路段的通行能力，α₁和β₁為待定參數(shù)，取值為0.15和4；式(4)中，N表示路網(wǎng)節(jié)點(diǎn)數(shù)量，x_ij為決策變量，取值為1表示選擇路段ij，取值為0表示不選擇路段ij；

最小路徑風(fēng)險(xiǎn)目標(biāo)

路徑風(fēng)險(xiǎn)反應(yīng)了救援車(chē)輛在高速公路上前往事故發(fā)生點(diǎn)的路徑最安全的要求，能夠提高救援路線的安全性，具體公式如下：

其中，e_ij表示路段ij的風(fēng)險(xiǎn)系數(shù)；

在步驟(3)中，所述根據(jù)事故點(diǎn)的位置改進(jìn)蟻群算法的初始信息素濃度設(shè)置，具體如下：

其中，ε表示路段上的信息素初始濃度，ε+ε₀表示與事故點(diǎn)e相鄰接節(jié)點(diǎn)的相鄰路段的信息素初始濃度；

所述綜合下一目標(biāo)路徑長(zhǎng)度最短、下一目標(biāo)距事故點(diǎn)的直線距離最短、搜索角度最小及路段風(fēng)險(xiǎn)性小這些要求，設(shè)計(jì)啟發(fā)函數(shù)，具體如下：

將下一節(jié)點(diǎn)趨向終點(diǎn)的直線距離、方向因素考慮進(jìn)來(lái)，并綜合了路段ij的風(fēng)險(xiǎn)系數(shù)，啟發(fā)函數(shù)設(shè)置為：

其中，d_ij表示路段ij的實(shí)際距離，d_ja為節(jié)點(diǎn)j與事故點(diǎn)a之間的直線距離，Δθ表示路段ij所在直線與路段ja所在直線之間的夾角；μ₁,μ₂,μ₃為待定參數(shù)；

所述引入阻抗時(shí)間，使用隨機(jī)選擇機(jī)制改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則，具體如下：

其中，式(8)為傳統(tǒng)蟻群算法的狀態(tài)轉(zhuǎn)移公式，也稱為隨機(jī)比例規(guī)則，τ_ij表示路段ij上的信息素濃度；η_ij表示路段ij之間的啟發(fā)式信息；w_ij為路段ij之間路阻通行時(shí)間的倒數(shù)；α為信息素權(quán)重因子；β為啟發(fā)式信息權(quán)重因子；r為路阻通行時(shí)間權(quán)重因子；allowed_k表示螞蟻k可選的節(jié)點(diǎn)集合，且allowed_k＝{1,2,…,n}-tabu_k,tabu_k為螞蟻k的禁忌表,它記錄了當(dāng)前時(shí)刻螞蟻所搜索過(guò)的節(jié)點(diǎn),約束螞蟻不能在此次循環(huán)中第二次訪問(wèn)這些節(jié)點(diǎn)；

式(9)為使用隨機(jī)選擇機(jī)制改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則，q₁,q₂為分類選擇參數(shù)，r為隨機(jī)因子，其中q₁,q₂,r∈(0，1)。