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

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

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

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

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