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

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

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

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

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