基于社區(qū)發(fā)現(xiàn)的動態(tài)路徑規(guī)劃問題研究.pdf

1、近年來，國內(nèi)經(jīng)濟的迅速發(fā)展帶來了交通需求的日益增長，交通擁堵已經(jīng)成為大中城市交通的普遍現(xiàn)象，這影響了人們出行的安全與效率。車輛導(dǎo)航系統(tǒng)在此背景下變得越來越重要，車輛導(dǎo)航系統(tǒng)可以通過提供給出行者有效的路徑規(guī)劃方案來解決道路的擁堵狀況。車輛導(dǎo)航系統(tǒng)核心的功能是在短時間內(nèi)給出一條最優(yōu)或近似最優(yōu)的出行路徑，這對路徑規(guī)劃算法的實時性和準(zhǔn)確性提出了很高的要求。
　　由于交通網(wǎng)絡(luò)規(guī)模龐大，傳統(tǒng)的路徑規(guī)劃算法不能很好地應(yīng)用于車輛導(dǎo)航中。目前對導(dǎo)航

2、領(lǐng)域路徑規(guī)劃算法的研究都會結(jié)合分層技術(shù)，通過分治與劃分，把網(wǎng)絡(luò)劃分為多個子網(wǎng)從而降低搜索空間的范圍使傳統(tǒng)算法能夠很好的應(yīng)用。社區(qū)發(fā)現(xiàn)能夠發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，將聯(lián)系緊密的節(jié)點組成一個社區(qū)，聯(lián)系稀疏的節(jié)點組成不同社區(qū)，從而形成層次化的結(jié)構(gòu)。本文基于社區(qū)發(fā)現(xiàn)思想研究了對交通路網(wǎng)分層的策略和基于分層路網(wǎng)下的動態(tài)路徑規(guī)劃算法，主要研究內(nèi)容和結(jié)果如下：
　　以通行時間為相似性標(biāo)準(zhǔn)對路網(wǎng)進行分層，抽象出基于社區(qū)發(fā)現(xiàn)的多層交通路網(wǎng)模型。在此模型

3、的基礎(chǔ)上提出了一個分層路徑搜索策略，在該策略中優(yōu)先對稀疏的高層路網(wǎng)進行搜索，將高層搜索的結(jié)果作為低層的搜索范圍，根據(jù)多層路網(wǎng)模型由高到低逐層減小搜索范圍，使實際路網(wǎng)的搜索區(qū)域被限定在一個很小的范圍中。而且該策略中每一層是獨立搜索的，在實現(xiàn)的時候可以根據(jù)需要進行不同的調(diào)整。將該策略進行算法實現(xiàn)并應(yīng)用到福州市交通路網(wǎng)進行實驗仿真，結(jié)果表明，該策略不僅降低了搜索范圍，提高了搜索效率，同時提高了大區(qū)域搜索時的精準(zhǔn)度。
　　將本文提出的分層

4、路徑搜索策略應(yīng)用到不同交通場景進行實驗仿真，如道路施工、交通事故等，對路網(wǎng)分層結(jié)構(gòu)進行動態(tài)局部調(diào)整并進行重新規(guī)劃。實驗表明本文提出的策略能夠使車輛有效地規(guī)避道路施工、交通事故等路段。
　　在基于社區(qū)發(fā)現(xiàn)的分層搜索策略的基礎(chǔ)上，針對動態(tài)環(huán)境下車輛行駛一段時間后路況變化而導(dǎo)致車輛在行駛過程需要經(jīng)常重新規(guī)劃路徑的問題，引入歷史統(tǒng)計數(shù)據(jù)因素，對動態(tài)實時路況進行分析。對蟻群算法進行改進并應(yīng)用到本文提出的分層搜索策略的第一層路徑搜索中，仿真實