[發(fā)明專利]一種考慮路段相關(guān)性的時(shí)變隨機(jī)網(wǎng)絡(luò)動(dòng)態(tài)路徑搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710573641.X
• 申請(qǐng)日: 2017-07-14
• 公開（公告）號(hào): CN107145991B
• 公開（公告）日: 2020-06-19
• 發(fā)明（設(shè)計(jì)）人: 陳鵬;童睿;王云鵬;魯光泉;鹿應(yīng)榮
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明公開了一種考慮路段相關(guān)性的時(shí)變隨機(jī)網(wǎng)絡(luò)動(dòng)態(tài)路徑搜索方法，屬于智能交通領(lǐng)域，包括：1、采集路網(wǎng)狀態(tài)信息，并基于預(yù)處理后的數(shù)據(jù)，建立動(dòng)態(tài)行程時(shí)間數(shù)據(jù)庫(kù)；2、出行者設(shè)定本次出行需求；3、設(shè)置遺傳算法參數(shù)，產(chǎn)生初始路徑集，構(gòu)建適應(yīng)度函數(shù)計(jì)算候選路徑適應(yīng)度；4、基于遺傳算法迭代搜索最優(yōu)路徑，車輛按照迭代得到的最優(yōu)路徑行駛；5、通過判斷車輛狀態(tài)及路網(wǎng)狀態(tài)，實(shí)現(xiàn)最優(yōu)路徑的實(shí)時(shí)更新，以確保車輛持續(xù)在最優(yōu)路徑內(nèi)行駛，直至目的地。本發(fā)明所提出的算法，不但充分考慮了路網(wǎng)時(shí)變、行程時(shí)間隨機(jī)分布、路段相關(guān)性等一系列復(fù)雜因素，同時(shí)，較好地保證了遺傳算法的求解速度和求解精度，更有利于實(shí)現(xiàn)動(dòng)態(tài)路徑搜索方法。

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

本發(fā)明公開了一種考慮路段相關(guān)性的時(shí)變隨機(jī)網(wǎng)絡(luò)動(dòng)態(tài)路徑搜索方法，屬于智能交通技術(shù)領(lǐng)域。

背景技術(shù)

隨著城市的不斷發(fā)展和擴(kuò)張，人們的出行需求也越來越多樣化和準(zhǔn)時(shí)化。在實(shí)際道路網(wǎng)絡(luò)中，交通狀態(tài)在不斷變化，突發(fā)的交通擁堵可能給出行者帶來巨大的損失。所以，如何在實(shí)時(shí)變化的交通網(wǎng)絡(luò)中找到從起點(diǎn)到終點(diǎn)的最優(yōu)路徑成為滿足出行者出行需求的關(guān)鍵問題。

時(shí)變隨機(jī)網(wǎng)絡(luò)能夠較好地模擬實(shí)際路網(wǎng)。在時(shí)變隨機(jī)網(wǎng)絡(luò)中，每一條路段的行程時(shí)間都是一個(gè)隨機(jī)變量，在足夠小的時(shí)間段內(nèi)服從某一分布，且該分布的參數(shù)也會(huì)隨著時(shí)間的變化而變化。根據(jù)實(shí)際采集的行程時(shí)間數(shù)據(jù)的分布擬合結(jié)果來看，通常行程時(shí)間的分布可以假定為正態(tài)分布、對(duì)數(shù)正態(tài)分布、伽馬分布、威布爾分布等。在時(shí)變隨機(jī)網(wǎng)絡(luò)中進(jìn)行路徑搜索，比在傳統(tǒng)的靜態(tài)確定性網(wǎng)絡(luò)中搜索得到的結(jié)果更符合實(shí)際路網(wǎng)情況，從而使得結(jié)果更準(zhǔn)確。路段相關(guān)性是指路段之間相互關(guān)聯(lián)的性質(zhì)，可以用路段行程時(shí)間的相關(guān)系數(shù)來量化。在考慮路段相關(guān)性的基礎(chǔ)上進(jìn)行路徑搜索，較傳統(tǒng)假設(shè)路段之間相互獨(dú)立的方式更為合理。

遺傳算法是一種對(duì)自然的進(jìn)化過程進(jìn)行模仿的搜索最優(yōu)解的方法。首先，算法中會(huì)設(shè)計(jì)編碼表示問題的可行解，為簡(jiǎn)單起見，往往使用二進(jìn)制編碼表示可行解。然后，生成一個(gè)初始的可行解群，再按照優(yōu)勝劣汰原則，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，從而生成新解。接下來，保留其中高質(zhì)量的解并將較差的解舍棄，按此方式不斷循環(huán)迭代直至滿足終止條件。整個(gè)求解過程就像種群不斷繁衍進(jìn)化，后生代種群相比于前代來說，總是能夠更好地適應(yīng)當(dāng)前所生存的環(huán)境。最后我們得到末代種群，將其中最優(yōu)個(gè)體經(jīng)過反編碼，即可作為問題近似最優(yōu)解。本發(fā)明中的動(dòng)態(tài)路徑搜索方法將基于遺傳算法實(shí)現(xiàn)。

發(fā)明內(nèi)容

本發(fā)明目的在于改善現(xiàn)有相關(guān)技術(shù)，提出一種考慮路段相關(guān)性的時(shí)變隨機(jī)網(wǎng)絡(luò)動(dòng)態(tài)路徑搜索方法。大量實(shí)際路段行程時(shí)間數(shù)據(jù)擬合分布結(jié)果表明，對(duì)數(shù)正態(tài)分布對(duì)路段行程時(shí)間分布的擬合效果最好，所以通常假設(shè)路段行程時(shí)間服從對(duì)數(shù)正態(tài)分布。因此，在本發(fā)明中，以路段行程時(shí)間服從對(duì)數(shù)正態(tài)分布為例。在考慮路段相關(guān)性時(shí)，傳統(tǒng)的卷積方法不再適用于計(jì)算路徑行程時(shí)間，多數(shù)情況下借助蒙特卡洛仿真的方法生成大量的路段行程時(shí)間隨機(jī)數(shù)，然后再通過相加并排序來計(jì)算隨機(jī)網(wǎng)絡(luò)中的路徑行程時(shí)間及其可靠性。這種直接應(yīng)用蒙特卡洛仿真的計(jì)算方法需要付出大量的計(jì)算成本，往往不能滿足動(dòng)態(tài)路徑搜索求解時(shí)間限制的要求。基于以上技術(shù)問題，本發(fā)明所提出的方法，不但充分考慮了路網(wǎng)時(shí)變、行程時(shí)間隨機(jī)分布、路段相關(guān)性等一系列復(fù)雜因素，同時(shí)，較好地保證了遺傳算法的求解速度和求解精度，更有利于實(shí)現(xiàn)動(dòng)態(tài)路徑搜索方法。

本發(fā)明的一種考慮路段相關(guān)性的時(shí)變隨機(jī)網(wǎng)絡(luò)動(dòng)態(tài)路徑搜索方法，包括以下幾個(gè)步驟：

步驟一、采集路網(wǎng)狀態(tài)信息，并基于預(yù)處理后的數(shù)據(jù)，建立動(dòng)態(tài)行程時(shí)間數(shù)據(jù)庫(kù)；

步驟二、出行者設(shè)定本次出行的始發(fā)地、目的地和行程時(shí)間可靠度；

步驟三、設(shè)置遺傳算法參數(shù)，并基于所產(chǎn)生的初始路徑集及構(gòu)建的適應(yīng)度函數(shù)計(jì)算候選路徑適應(yīng)度；

步驟四、基于遺傳算法迭代搜索最優(yōu)路徑，車輛按照迭代后所得到的當(dāng)前最優(yōu)路徑行駛；