面向城市交通的簡化路網(wǎng)模型及路徑規(guī)劃問題的研究.pdf

1、隨著城市中交通堵塞情況的越來越嚴重，出行者對簡潔、高效的路徑規(guī)劃算法的要求日益迫切。如何根據(jù)現(xiàn)實的道路交通狀況構(gòu)建合理而有效的路網(wǎng)模型，并在路網(wǎng)模型的基礎上設計出滿足出行者需求的簡捷有效的路徑規(guī)劃有著非常重要的意義。在實際應用中，比較常見的路網(wǎng)模型都考慮了比較復雜的交通限制信息（例如：路寬、車流量、由于施工、交通事故等對道路進行限行的規(guī)定），而路徑規(guī)劃的目標也會在路網(wǎng)模型的基礎上根據(jù)出行者的要求進行多目標或單目標的規(guī)劃。
　　目前

2、，國內(nèi)外研究提出的道路交通網(wǎng)絡模型比較多，包括各種復雜的靜態(tài)路網(wǎng)模型、動態(tài)路網(wǎng)模型、以及實時路網(wǎng)模型等。這些復雜路網(wǎng)模型雖然在一定程度上可以更好地描述現(xiàn)實交通路況，但這些模型考慮的因素普遍比較繁多，比如為了計算交叉口的時延就考慮排隊等待的長度、環(huán)形道的長度、交叉口的車流量等，另外還有考慮動態(tài)交通流以及紅綠和交叉口延時等，因此導致路徑規(guī)劃算法的設計過于繁瑣，不僅計算效率顯著下降，而且所需道路信息難以實時精確地采集，從而不能很好地響應城市內(nèi)

3、出行者的導航要求。針對這種情況，本文重點研究了如何在保證路徑規(guī)劃效果的前題下，盡可能考慮較少的因素來簡化路網(wǎng)模型，更好地響應城市出行者的導航要求。論文研究主要貢獻如下：
　?、偈紫?，考慮城市交通的基本特點，研究提出了一種簡潔實用的的簡化靜態(tài)路網(wǎng)模型。并在該模型的基礎上設計了改進的Dijkstra算法，即S-Dijkstra算法，來解決城市路徑規(guī)劃問題。該模型僅要求采集很少的道路通行信息，卻能簡接地反映道路轉(zhuǎn)彎延時、通行速度、紅綠燈

4、和斑馬線等復雜因素對車輛通行時間的間接影響，具有簡單實用的特點。
　?、谶M而，通過按照城市交通動態(tài)變化的特殊規(guī)律，將一個工作日內(nèi)道路通行時段劃分為不同的時間段，對上述簡化模型進行擴展，構(gòu)建了一種基于時間段劃分的簡化動態(tài)路網(wǎng)模型。并給出了能在該模型上正常運行的改進Dijkstra算法，即D-Dijkstra算法，來解決適合城市內(nèi)汽車導航的動態(tài)路徑規(guī)劃問題。
　?、圩詈螅疚耐ㄟ^將限定搜索的矩形區(qū)域法和分層方法結(jié)合運用到上述提出