[發(fā)明專(zhuān)利]一種城市的有效路徑集搜索方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110281475.2
• 申請(qǐng)日: 2021-03-16
• 公開(kāi)（公告）號(hào): CN113065073A
• 公開(kāi)（公告）日: 2021-07-02
• 發(fā)明（設(shè)計(jì)）人: 王煒;金坤;李欣然;秦韶陽(yáng);周偉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 東南大學(xué)
• 主分類(lèi)號(hào): G06F16/9537
• 分類(lèi)號(hào): G06F16/9537;G06F16/9535;G06F16/29
• 代理公司: 南京經(jīng)緯專(zhuān)利商標(biāo)代理有限公司 32200
• 代理人: 羅運(yùn)紅

本申請(qǐng)涉及一種城市的有效路徑集搜索方法。該方法包括：獲取目標(biāo)分配區(qū)域內(nèi)所有節(jié)點(diǎn)的節(jié)點(diǎn)信息、所有路段的路段信息及所有OD點(diǎn)對(duì)的OD點(diǎn)對(duì)信息；根據(jù)所有節(jié)點(diǎn)的所述節(jié)點(diǎn)信息和所有路段的所述路段信息，構(gòu)建電子道路地圖網(wǎng)絡(luò)；根據(jù)所述電子道路地圖網(wǎng)絡(luò)，構(gòu)建對(duì)偶的電子道路地圖網(wǎng)絡(luò)；根據(jù)所有OD點(diǎn)對(duì)的所述OD點(diǎn)對(duì)信息及所述對(duì)偶的電子道路地圖網(wǎng)絡(luò)進(jìn)行有效路徑集的搜索，獲得所述目標(biāo)分配區(qū)域內(nèi)的有效路徑集，能夠面向城市大規(guī)模網(wǎng)絡(luò)實(shí)現(xiàn)有效路徑集的快速搜索，基于確定有效路段，進(jìn)一步確定有效路徑，避免了有效路徑集搜索中可能出現(xiàn)的組合爆炸情況，最終實(shí)現(xiàn)有效路徑的篩選，加速了有效路徑集的搜索。

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

本申請(qǐng)涉及道路交通技術(shù)領(lǐng)域，特別是涉及一種城市的有效路徑集搜索方法。

背景技術(shù)

在交通規(guī)劃中，常常使用“四階段”法，即交通發(fā)生與吸引預(yù)測(cè)，交通分布預(yù)測(cè)，交通方式劃分預(yù)測(cè)及交通分配預(yù)測(cè)。其中，交通分配是城市交通宏觀(guān)規(guī)劃中最核心重要的環(huán)節(jié)。它將給定的OD交通量，按照一定的原則分配到城市復(fù)雜的道路網(wǎng)絡(luò)上，為城市出行者提供出行建議、為城市規(guī)劃者提供定量化的分析與評(píng)估。

交通分配一般可分為平衡分配與非平衡分配，其中非平衡分配具有模型簡(jiǎn)潔易懂，分配效率高，貼近實(shí)際情況等優(yōu)點(diǎn)，因而被廣泛使用。非平衡分配又可分為多路徑分配與單路徑分配，其中多路徑分配綜合考慮了出行者的多路徑選擇行為。它反映了出行路徑的行程時(shí)間、距離等因素對(duì)出行者的影響，從而確定出行者選擇某條出行路徑的概率，進(jìn)而將各交通小區(qū)之間的出行次數(shù)按比例分配到起訖小區(qū)之間的所有有效出行路徑上去。因此，應(yīng)用多路徑分配的前提就是確定各交通小區(qū)之間的有效出行路徑集合。

隨著圖論、計(jì)算機(jī)技術(shù)的不斷發(fā)展，利用計(jì)算機(jī)進(jìn)行交通分配的算法和技術(shù)得到了巨大的提升與進(jìn)步。眾多學(xué)者對(duì)多路徑分配進(jìn)行了研究，他們考慮了多種實(shí)際影響出行者路徑選擇行為的因素，構(gòu)建了許多精妙且符合實(shí)際的模型。然而，對(duì)于有效出行路徑集合生成的研究卻很少，往往采用樸素的深度優(yōu)先搜索(DFS)或K-最短路(KSP)等算法。這些現(xiàn)有的有效路徑集搜索方法大多局限在中小規(guī)模的交通網(wǎng)絡(luò)上使用，應(yīng)用到大規(guī)模交通網(wǎng)絡(luò)上的效果往往不盡人意。這些搜索方法極易陷入路徑“組合爆炸”的危機(jī)中，導(dǎo)致有效路徑集搜索的效率低。

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

基于此，有必要針對(duì)上述技術(shù)問(wèn)題，提供一種能夠提高有效路徑集搜索的效率的城市的有效路徑集搜索方法。

一種城市的有效路徑集搜索方法，所述方法包括：

獲取目標(biāo)分配區(qū)域內(nèi)所有節(jié)點(diǎn)的節(jié)點(diǎn)信息、所有路段的路段信息及所有OD點(diǎn)對(duì)的OD點(diǎn)對(duì)信息；

根據(jù)所有節(jié)點(diǎn)的所述節(jié)點(diǎn)信息和所有路段的所述路段信息，構(gòu)建電子道路地圖網(wǎng)絡(luò)；

根據(jù)所述電子道路地圖網(wǎng)絡(luò)，構(gòu)建對(duì)偶的電子道路地圖網(wǎng)絡(luò)；

根據(jù)所有OD點(diǎn)對(duì)的所述OD點(diǎn)對(duì)信息及所述對(duì)偶的電子道路地圖網(wǎng)絡(luò)進(jìn)行有效路徑集的搜索，獲得所述目標(biāo)分配區(qū)域內(nèi)的有效路徑集。

在其中一個(gè)實(shí)施例中，所述根據(jù)所有OD點(diǎn)對(duì)的所述OD點(diǎn)對(duì)信息及所述對(duì)偶的電子道路地圖網(wǎng)絡(luò)進(jìn)行有效路徑集的搜索，獲得所述目標(biāo)分配區(qū)域內(nèi)的有效路徑集的步驟，包括：

根據(jù)所有OD點(diǎn)對(duì)的所述OD點(diǎn)對(duì)信息，確定所有OD點(diǎn)對(duì)的OD點(diǎn)對(duì)終節(jié)點(diǎn)；

基于堆優(yōu)化的最短路算法，計(jì)算所述OD點(diǎn)對(duì)終節(jié)點(diǎn)到所述對(duì)偶的電子道路地圖網(wǎng)絡(luò)的對(duì)偶節(jié)點(diǎn)集合中所有其他節(jié)點(diǎn)的最短距離，獲得所述OD點(diǎn)對(duì)終節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短距離；

根據(jù)所述OD點(diǎn)對(duì)終節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短距離，確定有效路段；

根據(jù)所述有效路段，在所述電子道路地圖網(wǎng)絡(luò)中進(jìn)行深度優(yōu)先搜索，確定所述目標(biāo)分配區(qū)域內(nèi)的有效路徑集。

在其中一個(gè)實(shí)施例中，所述根據(jù)所述OD點(diǎn)對(duì)終節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短距離，確定有效路段的步驟，包括：