【正文】 時(shí)間最短，都不一定是行車意義上的最短路徑。因?yàn)槌诵问骄嚯x或形式時(shí)間外，最優(yōu)路徑的選擇還需要考慮很多無法預(yù)期或定量化的因素。本節(jié)利用實(shí)際城市道路網(wǎng)絡(luò)中路段的不同等級特性，構(gòu)造了不同于方向搜索策略的另一種啟發(fā)式搜索策略，即分層搜索策略，給出了利用該搜索策略設(shè)計(jì)分層道路網(wǎng)絡(luò)和基于分層道路網(wǎng)絡(luò)設(shè)計(jì)分層路徑規(guī)劃算法的具體方法。分層路徑規(guī)劃算法（簡稱算法 32）的基本思想是：根據(jù)道路網(wǎng)絡(luò)中路段的不同等級特性，將整個(gè)道路網(wǎng)絡(luò)分為不同的層次，每一層包含道路網(wǎng)絡(luò)不同級別的細(xì)節(jié)。高層道路網(wǎng)絡(luò)是其相鄰低層道路網(wǎng)絡(luò)的抽象和濃縮，低層則是其相鄰高層道路網(wǎng)絡(luò)的具體擴(kuò)展。換言之，任一高層道路網(wǎng)絡(luò)內(nèi)的路段和節(jié)點(diǎn)都包含于其相鄰的低層道路網(wǎng)絡(luò)內(nèi)，而任意一個(gè)低層道路網(wǎng)絡(luò)除了包含其相鄰高層道路網(wǎng)絡(luò)內(nèi)的路段和節(jié)點(diǎn)外，還包含更多的其他路段和節(jié)點(diǎn)。這樣，在進(jìn)行路徑規(guī)劃是，我們便可以先在高層空間進(jìn)行搜索，然后在搜索高層空間獲得的結(jié)果基礎(chǔ)上再添上低層空間的細(xì)節(jié)，得到問題的最終解。（1）城市道路網(wǎng)絡(luò)中路段的分等級特性多數(shù)城市道路網(wǎng)絡(luò)存在的一個(gè)事實(shí)是其中的路段具有不同等級特性。這些不同的道路等級一般又都對應(yīng)著不同的行車環(huán)境，如道路的行車時(shí)速限制、道路上紅綠燈的設(shè)置間距、道路的寬度及路面質(zhì)量等多種與行車密切相關(guān)的因素。（2）道路網(wǎng)絡(luò)的分層方法第三章 路徑規(guī)劃的分析及設(shè)計(jì) 23將分層思想引入到道路網(wǎng)絡(luò)的設(shè)計(jì)中，即根據(jù)道路網(wǎng)路中路段的不同等級特性，將整個(gè)道路網(wǎng)絡(luò) RN 分為不同的層。（3）分層道路網(wǎng)絡(luò)的表示分層道路網(wǎng)絡(luò)的表示是指分層道路網(wǎng)絡(luò)如何在計(jì)算機(jī)中表示和存儲，它是算法 32 的基礎(chǔ)。設(shè)計(jì)中，首先采用 ArcNode 模型將整個(gè)道路網(wǎng)絡(luò)表示為：G=(N,A,B)，這里 N={N1，N2，…,Nn}是道路網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，A={aij|1≤i≤n,1≤j≤MaxNum，其中 MaxNum 是 RN 的最大鄰接節(jié)點(diǎn)數(shù)}是 RN 中各節(jié)點(diǎn)間鄰接關(guān)系的集合，aij 表示第 j 個(gè)與節(jié)點(diǎn) i 鄰接的節(jié)點(diǎn)，而且認(rèn)為兩節(jié)點(diǎn)間的邊是雙向的，B={bij|1≤i≤n,1≤j≤MaxNum ，其中 MaxNum 是 RN 的最大鄰接節(jié)點(diǎn)數(shù)}是 RN 中各鄰接節(jié)點(diǎn)間連接邊的權(quán)值合集，bij 表示節(jié)點(diǎn) i 與節(jié)點(diǎn) aij之間的邊的權(quán)值，而且認(rèn)為兩節(jié)點(diǎn)間的邊是雙向的，另外，每條路段都有一個(gè)非負(fù)的權(quán)值和它關(guān)聯(lián)，每條道路則是由一系列首尾相連的路段構(gòu)成，它的權(quán)值是組成它的所有路段的權(quán)值之和。然后，為了將 RN 分為 HRN 和 LRN，定義一個(gè)標(biāo)記數(shù)組Mark1 來標(biāo)記 RN 中的節(jié)點(diǎn)屬于哪些 HRN，若 Mark1(i)=1，則表示節(jié)點(diǎn) i 不僅屬于LRN，而且同時(shí)屬于 HRN，這樣便將 RN 從邏輯上分成了高低兩層。輸入：具有拓?fù)浣Y(jié)構(gòu)矢量化道路網(wǎng)絡(luò) RN 及其對應(yīng)分層道路網(wǎng)絡(luò) HRN 和 LRN，起點(diǎn) S、終點(diǎn) D 為道路網(wǎng)絡(luò)中任意指定的兩個(gè)節(jié)點(diǎn)。輸出：節(jié)點(diǎn) S 和節(jié)點(diǎn) D 之間的一條最優(yōu)路徑。步驟一，初始化，完成路網(wǎng)數(shù)據(jù)加載及程序運(yùn)行環(huán)境設(shè)置。步驟二，判斷節(jié)點(diǎn) S 和 D 所在的路網(wǎng)層次，若節(jié)點(diǎn) S 和 D 都已經(jīng)在 HRN 中，則算法 32 直接轉(zhuǎn)入步驟三；否則，若節(jié)點(diǎn) S 不在 HRN 中，則算法必須先在 S 附近的小區(qū)域內(nèi)調(diào)用算法 RP0 的實(shí)現(xiàn)程序進(jìn)行結(jié)算，由它進(jìn)入高層路網(wǎng)的最短路徑L1及相應(yīng)的位于高層路網(wǎng)上的節(jié)點(diǎn) S′，對節(jié)點(diǎn) D 作類似的處理，求出相應(yīng)的最短路徑 L2及相應(yīng)的位于高層路網(wǎng)上的節(jié)點(diǎn) D′。步驟三，在 HRN 中對節(jié)點(diǎn) S（或?qū)?yīng)節(jié)點(diǎn) S′）和 D（或?qū)?yīng)節(jié)點(diǎn) D′）調(diào)用算法 RP0 的實(shí)現(xiàn)程序解算其最短路徑 L0。步驟四，綜合 L0、L1 及 L2為 L，將 L 作為節(jié)點(diǎn) S 和 D 之間的一條最優(yōu)路徑輸出。GPS 車載導(dǎo)航儀的路徑規(guī)劃研究24 限制搜索區(qū)域的分層路徑規(guī)劃算法由于方向搜索策略和分層搜索策略是從兩個(gè)不同的角度降低算法搜索空間的，因此可以考慮將二者有機(jī)結(jié)合，以便同時(shí)從不同角度縮小算法的搜索空間，設(shè)計(jì)更為合理的路徑規(guī)劃算法。本節(jié)從這一設(shè)計(jì)思路出發(fā)，將前面的算法 31 和算法32 進(jìn)行有機(jī)結(jié)合，利用方向和分層搜索相結(jié)合策略，提出了新的算法 33.算法 33 的基本思想是：先進(jìn)行分層路徑規(guī)劃，然后再對高層網(wǎng)絡(luò)中的兩個(gè)相應(yīng)節(jié)點(diǎn)進(jìn)行路徑規(guī)劃時(shí)，采用限制搜索區(qū)域的路徑規(guī)劃算法。與算法 32 不同的是，算法 33 在 HRN 中搜索時(shí)，只對落入限制區(qū)域范圍內(nèi)的 HRN 進(jìn)行搜索，而不是在整個(gè) HRN 中進(jìn)行搜索，因此它只保證搜索結(jié)果與算法 32 相同的同時(shí)，搜索效率卻比算法 31 和算法 32 都高。輸入：具有拓?fù)浣Y(jié)構(gòu)的矢量化道路網(wǎng)絡(luò) RN，RN 對應(yīng)的分層道路網(wǎng)絡(luò) HRN 和LRN，路徑規(guī)劃的起點(diǎn) S 和終點(diǎn) D，閾值 T1和 T2。輸出：節(jié)點(diǎn) S 和節(jié)點(diǎn) D 之間的一條行車最優(yōu)路徑。步驟一，初始化，完成路網(wǎng)數(shù)據(jù)加載及程序運(yùn)行環(huán)境設(shè)置。步驟二，判斷節(jié)點(diǎn) S 和 D 所在的路網(wǎng)層次，若節(jié)點(diǎn) S 和 D 都已在 HRN 中，則算法直接轉(zhuǎn)入步驟三；否則，若節(jié)點(diǎn) S 不在 HRN 中，則算法現(xiàn)在 S 附近小區(qū)域內(nèi)調(diào)用算法 RP0 子程序搜索由它進(jìn)入 HRN 的最短路徑 L1及相應(yīng)的位于 HRN 上的節(jié)點(diǎn)S′，然后，對節(jié)點(diǎn) D 作同樣的處理，求得相應(yīng)的最短路徑 L2及相應(yīng)的位于 HRN上的節(jié)點(diǎn) D′。步驟三，根據(jù)閾值 T1和 T2，在 HRN 中對節(jié)點(diǎn) S（或?qū)?yīng)的節(jié)點(diǎn) S′）和D（或?qū)?yīng)的節(jié)點(diǎn) D′）構(gòu)造限制搜索區(qū)域，然后調(diào)用算法 RP0 的子程序解算最優(yōu)路徑 L0。步驟四，綜合 L0、L1 及 L2為 L，將 L 作為節(jié)點(diǎn) S 和 D 之間的最優(yōu)路徑輸出。第四章 路徑規(guī)劃的優(yōu)缺點(diǎn)分析 25第四章 路徑規(guī)劃的優(yōu)缺點(diǎn)分析 算法的實(shí)驗(yàn)結(jié)果將算法 RP0、算法 3算法 32 及算法 33 四種算法同時(shí)應(yīng)用于西安市二環(huán)內(nèi)道路網(wǎng)絡(luò)中，在給定起始節(jié)點(diǎn) 1979 和 1264 時(shí)，圖 ～圖 分別是算法RP0、算法 3算法 32 和算法 33 的搜索結(jié)果顯示。圖中，粗線為搜索出的最短路徑。圖 算法 RP0圖 算法 31GPS 車載導(dǎo)航儀的路徑規(guī)劃研究26圖 算法 32圖 算法 33 算法實(shí)驗(yàn)結(jié)果的比對及優(yōu)缺點(diǎn)分析表 41 列出了四種算法搜索結(jié)果的部分性能對比。在表 41 中，N1 表示起點(diǎn)，N2表示終點(diǎn)；T1 表示算法 RP0 所用的搜索時(shí)間，T2 表示算法 32 所用的搜索時(shí)間，T3表示算法 31 所用的搜索時(shí)間， ，T4 表示算法 33 所用的搜索時(shí)間；D1 表示算法 RP0 規(guī)劃出的最優(yōu)路徑長度，D2 表示算法 32 規(guī)劃出的最優(yōu)路徑長度，D3 表示算法 31 規(guī)劃出的最優(yōu)路徑長度，D4 表示算法 33 規(guī)劃出的最優(yōu)路徑長度。從表 41 可以看出，算法 33 較算法 31 和算法 32 的搜索效率高，體現(xiàn)在第四章 路徑規(guī)劃的優(yōu)缺點(diǎn)分析 27相同輸入是 T4 比 T1 的十分之一還小，比 T2 的三分之一還小。從 DDD3 和D4 四列可以看出，算法 33 和算法 32 規(guī)劃出的最優(yōu)路徑相同，且其長度比算法RP0 和算法 31 規(guī)劃出的最短路徑長度稍長，這樣的規(guī)劃結(jié)果更符合實(shí)際系統(tǒng)要求，因?yàn)槎鄶?shù)駕駛員都希望行車過程中能盡量走這種路徑。表 41 算法 RP0、332 與 33 搜索結(jié)果性能對比N1 N2 T1/s T2/s T3/s T4/s D1/m D2/m D3/m D4/m1979 1264 27215 28514 27215 285141170 955 20747 21055 20747 285142350 3730 7662 8374 7662 83742853 3275 17306 17395 17306 173951979 5498 25763 27902 25763 279026421 5691 15567 16031 15567 160313736 1264 15853 17100 15853 171003736 3730 9094 1012 9094 1012GPS 車載導(dǎo)航儀的路徑規(guī)劃研究28第五章 結(jié)論 29第五章 結(jié)論 論文小結(jié)在進(jìn)行本論文的研究過稱中，本人得出以下結(jié)論：路徑規(guī)劃是車載導(dǎo)航系統(tǒng)中的基礎(chǔ)，是系統(tǒng)設(shè)計(jì)中的核心內(nèi)容。本文對 GPS 車載導(dǎo)航系統(tǒng)的總體結(jié)構(gòu)進(jìn)行了簡單的研究，并介紹了本文內(nèi)所涉及的相關(guān)知識，如 GPS、GIS、電子地圖數(shù)據(jù)庫、拓?fù)渚W(wǎng)絡(luò)等，重點(diǎn)對路徑規(guī)劃的算法進(jìn)行了詳細(xì)研究，綜合考慮了多種最短路徑選擇算法。本設(shè)計(jì)以 MapInfo 地理信息系統(tǒng)軟件為工具，實(shí)現(xiàn)了 Dijkstra算法,并作了一定的改進(jìn)，并在數(shù)字地圖上顯示了要求的最短路徑的結(jié)果，設(shè)計(jì)基本達(dá)到預(yù)期目標(biāo)。 路徑規(guī)劃系統(tǒng)的展望鑒于個(gè)人的能力有限，本論文所進(jìn)行的路徑規(guī)劃研究并不能完全解決車載導(dǎo)航系統(tǒng)的需求，因此還存在以下問題有待進(jìn)一步研究和改進(jìn)的地方：（1）顯示地圖上任意兩點(diǎn)間的最短距離：本文中是將用戶任意選擇的點(diǎn)與其最近的節(jié)點(diǎn)相匹配，求出的是匹配后兩點(diǎn)之間的最短距離，這樣顯示的時(shí)候不能以用戶所選的點(diǎn)為起始點(diǎn)和終止點(diǎn)，甚至在有些情況下會出現(xiàn)錯(cuò)誤。如何使用戶選擇的任意點(diǎn)匹配到道路地圖上，還需要進(jìn)一步的研究。（2）最佳路徑分析：最佳路徑分析要比最短路徑分析復(fù)雜的多。在實(shí)際應(yīng)用中，要考慮到實(shí)際路況信息，例如道路堵塞等。本文規(guī)劃出的僅僅是最短路徑，沒有聯(lián)系實(shí)際的路況。（3）同路況監(jiān)測系統(tǒng)的集成：在交通網(wǎng)絡(luò)中，車輛的運(yùn)行過程是一個(gè)動態(tài)變化的過程，交通網(wǎng)絡(luò)中的所有節(jié)點(diǎn)和路段的某些屬性并不是一成不變的，而是是隨著時(shí)間不斷變化的，并且極可能影響到路徑規(guī)劃的準(zhǔn)確性，導(dǎo)致提供不正確的規(guī)劃結(jié)果。因此僅使用靜態(tài)網(wǎng)絡(luò)中的靜態(tài)信息來進(jìn)行路徑規(guī)劃，結(jié)果可能不能滿足用戶實(shí)際的需要。在實(shí)際行駛時(shí),需要知道當(dāng)前各路段交通的狀況，以便給用戶提供真正的“最佳路徑” 。（4）基礎(chǔ)道路數(shù)據(jù)的更新：在城市在不斷地發(fā)展變化中城市路網(wǎng)也在變化，GPS 車載導(dǎo)航儀的路徑規(guī)劃研究30因此系統(tǒng)所用的數(shù)字地圖也需要實(shí)時(shí)更新，所以實(shí)時(shí)更新 GIS 也需要進(jìn)一步討論。（5）道路網(wǎng)數(shù)據(jù)模型的改進(jìn)：本文中并沒有考慮到城市交通設(shè)施中實(shí)際存在的立交橋及單向車道等特殊道路，需要在交通道路方面進(jìn)一步改進(jìn)數(shù)據(jù)模型，完整地表達(dá)各個(gè)道路的拓?fù)潢P(guān)系。（6）復(fù)雜地形上的路徑規(guī)劃：要進(jìn)行路徑規(guī)劃的區(qū)域也許是一個(gè)復(fù)雜的地理區(qū)域，包括河流、丘陵、建筑物等。如果要使路徑規(guī)劃系統(tǒng)適應(yīng)這些復(fù)雜地形上的路徑規(guī)劃，就需要有能夠適應(yīng)三維圖形上的路徑規(guī)劃算法加以輔助。致謝 31致 謝在本論文即將完成之際，我要感謝我的導(dǎo)師王文朋老師。在完成論文的過程中王老師給了我許多建議及指導(dǎo)，王老師的諄諄教誨、嚴(yán)格要求以及他那極具啟發(fā)性的指導(dǎo)和嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度使我受益非淺，無論在理論上還是實(shí)踐上他都給了我莫大的幫助，使我自身得到了不少提高。在此，我要對王老師表示最崇高的敬意和最衷心的感謝。另外我還要感謝我的同學(xué)們，他們也給了我許多有益的建議。最后再次衷心的感謝所有支持和幫助我的老師和同學(xué)們。32參考文獻(xiàn) 33參考文獻(xiàn)[1] 黃丁發(fā)，張獻(xiàn)州，熊永良，李春華，周樂韜，羅德安，GPS 衛(wèi)星導(dǎo)航定位技術(shù)與方法，科學(xué)出版社，2022 年[2] 常青，楊東凱，寇艷紅，張其善，車輛導(dǎo)航定位方法及應(yīng)用，機(jī)械工業(yè)出版社，2022年 5 月[3] 付夢印，鄧志紅，劉彤，智能車輛導(dǎo)航技術(shù)，科學(xué)出版社，2022 年[4] 楊柳，車載導(dǎo)航系統(tǒng)中路徑規(guī)劃算法的研究及實(shí)現(xiàn)，北京交通大學(xué)碩士研究生學(xué)位論文，2022 年 6 月[5] 屈展，車載導(dǎo)航系統(tǒng)中路徑規(guī)劃問題的研究，蘭州理工大學(xué)碩士研究生學(xué)位論文，2022 年 9 月[6] 王亞文，智能交通系統(tǒng)中路徑規(guī)劃算法研究與系統(tǒng)設(shè)計(jì)，陜西師范大學(xué)碩士研究生學(xué)位論文，2022 年 5 月[7] 付夢印，李杰，鄧志紅，限制搜索區(qū)域的距離最短路徑規(guī)劃算法，北京理工大學(xué)學(xué)報(bào)，2022 年[8] 付夢印，李杰，鄧志紅，基于分層道路網(wǎng)絡(luò)的新型路徑規(guī)劃算法，北京理工大學(xué)學(xué)報(bào)，2022 年[9] 付夢印，李杰，鄧志紅，限制搜索區(qū)域的分層路徑規(guī)劃算法，北京理工大學(xué)學(xué)報(bào)，2022 年[10] 吳秀琳，劉永革，王利軍，MapInfo 中文標(biāo)準(zhǔn)版教程，清華大學(xué)出版社，