【文章內(nèi)容簡(jiǎn)介】 這些表頭結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的形式通常是順序存儲(chǔ)的，這樣存儲(chǔ)方式便于隨即訪問(wèn)任何一個(gè)節(jié)點(diǎn)的鏈表信息。 (2)十字鏈 表 十字鏈表針對(duì)有向圖的另一種存儲(chǔ)結(jié)構(gòu)?？梢钥闯墒且环N新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。在十字鏈表中，每一條邊都有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)，每一個(gè)節(jié)點(diǎn)也有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)。 2． 3 本章小結(jié) 本章對(duì)最優(yōu)路徑算法和圖論的相關(guān)理論知識(shí)進(jìn)行了簡(jiǎn)單概述。對(duì)幾個(gè)經(jīng)典的最優(yōu)路徑選擇算法進(jìn)行了介紹，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他們的優(yōu)點(diǎn)和不足。圖論在近幾十年來(lái)得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運(yùn)籌學(xué)、計(jì)算機(jī)理論、控制論、社會(huì)科學(xué)等不同領(lǐng)域和學(xué)科的結(jié)合方面 。 3 最優(yōu)路徑 最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運(yùn)輸效率。因此，應(yīng)當(dāng)首先考慮交通流的特征。一般地，交通網(wǎng)絡(luò)有如下特點(diǎn)： (1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問(wèn)分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 8 絡(luò)建模可以依靠圖論的相關(guān)理論和知識(shí)； (2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個(gè)負(fù)載的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜： (3)分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時(shí)間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時(shí)間差異性； (4)動(dòng)態(tài)性特點(diǎn)，交通 網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時(shí)間的變化而變化，失意是時(shí)變系統(tǒng)： (5)車(chē)輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時(shí)間和行駛路線等是他的一個(gè)最顯著特征。 以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進(jìn)的方法使得道路的車(chē)道信息加入到節(jié)點(diǎn)和邊的信息中。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當(dāng)中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當(dāng)中經(jīng)常和車(chē)道關(guān)聯(lián)密切。在同一一條道路上不同方向的車(chē)道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。 3． 1 建立城市交通模型 利用圖論 的相關(guān)理論和知識(shí)，對(duì)圖中的節(jié)點(diǎn)和邊設(shè)法加入車(chē)道信息用于模擬就哀痛系統(tǒng)。以完整的交通道路網(wǎng)絡(luò)作為模型建立對(duì)象，只需要對(duì)道路中的相關(guān)數(shù)據(jù)和參數(shù)進(jìn)行顯示和計(jì)算，但在實(shí)際的交通道路當(dāng)中，交通特征是實(shí)時(shí)變化的，這與交通道路模型密不可分。首先，在同一條道路上不同的車(chē)道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車(chē)流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車(chē)道的單向車(chē)道上。其次， 不同方向的車(chē)道由于具有不同的拓?fù)潢P(guān) 系，因此交通規(guī)則有可能不同。由于在節(jié)點(diǎn)圖層和路段圖層中分別存儲(chǔ)的點(diǎn)、線圖元是分別獨(dú)立的，兩個(gè)圖層問(wèn)不想關(guān)聯(lián)。為建立點(diǎn)線各個(gè)元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機(jī)整體，需要分別在存儲(chǔ)點(diǎn)線信息的兩張表文件中擴(kuò)展一定長(zhǎng)度的字段，用對(duì)象的屬性字段之問(wèn)的相互聯(lián)系來(lái)建立交通網(wǎng)絡(luò)圖的拓?fù)潢P(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機(jī)整體即他們的拓?fù)潢P(guān)系結(jié)構(gòu)圖。 武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 9 3． 1． 1 道路節(jié)點(diǎn)模型 可以將交通網(wǎng)絡(luò)抽象成一個(gè)有向圖，圖中的邊帶有一定的權(quán)值，但這個(gè)抽象的有向圖如何建立起來(lái)需要視具體的應(yīng)用環(huán)境而定。在實(shí)際情況中人民出行是從一個(gè)地方 到另一個(gè)地方，這種不能簡(jiǎn)單的歸結(jié)在圖中從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移，實(shí)際情況的交通網(wǎng)絡(luò)運(yùn)行是非常復(fù)雜的，所以不能簡(jiǎn)單的把某一個(gè)具體的地方當(dāng)成是圖中的某個(gè)節(jié)點(diǎn)，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點(diǎn)以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。交通地址的交叉口所抽象的節(jié)點(diǎn)和將具體地址被抽象成圖中的節(jié)點(diǎn)是不相等價(jià)的，需要考慮實(shí)際情況，因此交通節(jié)點(diǎn)的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點(diǎn)的阻抗值可以視為零。 3． 1． 2 交叉口和道路模型 將道路的數(shù)據(jù)模型抽象為一條線，因此選擇道路中問(wèn)的中 心線表示道路數(shù)據(jù)模型，這種建模方法不能很好的描述交通道路的屬性信息，丟失很多信息量。實(shí)際生活中的道路不能簡(jiǎn)單的抽象為一條直線，因?yàn)橛行┑缆反嬖诤芏嘬?chē)道，每個(gè)車(chē)道的屬性信息不盡相同，多車(chē)道的交通道路屬性信息較為復(fù)雜。在 GPS進(jìn)行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車(chē)道信息密切相關(guān)。 3． 2 交通模型數(shù)據(jù)存儲(chǔ) 3． 2． 1 數(shù)據(jù)預(yù)處理 在實(shí)際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對(duì)原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進(jìn)行優(yōu)化和預(yù)處理，建立相應(yīng)的拓?fù)潢P(guān)系圖譜。矢量圖形的預(yù) 處理的一般包括： (1)對(duì)原始道路圖像進(jìn)行拓?fù)潢P(guān)系檢查并進(jìn)行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來(lái)的道路拆分成多條道路的集合： (2)為每一條剪斷后的道路建立拓?fù)潢P(guān)系，并定義其屬性特征，如道路名稱、道路長(zhǎng)度、交通流等特征； (3)將地圖經(jīng)過(guò)上述處理之后生成拓?fù)湮募? 武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 10 3． 2． 2 交通路徑模型建立與數(shù)據(jù)存儲(chǔ) （ 1）交通路徑模型的建立 最短路徑選擇的前提是對(duì)交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對(duì)原始的交通道路進(jìn)行預(yù)處理之后就可以確定道路之間的拓?fù)潢P(guān)系，進(jìn)而可以建立以道路拓?fù)潢P(guān)系為基準(zhǔn)的交通系統(tǒng)模型 ，拓?fù)潢P(guān)系中包括線性實(shí)體之間的模型，線性實(shí)體與節(jié)點(diǎn)之問(wèn)的模型，節(jié)點(diǎn)與節(jié)點(diǎn)之間的模型，以及他們的連通性等。使用圖中的節(jié)點(diǎn)表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的道路在圖中用弧表示，就是圖的邊，路段的長(zhǎng)度以及消耗時(shí)問(wèn)等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點(diǎn)圖層，一部分是交通道路圖層。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)對(duì)象來(lái)表示，路段圖層存儲(chǔ)這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對(duì)象表示。在兩圖層中分別存儲(chǔ)的節(jié)點(diǎn)信息和 路段信息分別是獨(dú)立的，下一步就是建立兩個(gè)圖層之問(wèn)的拓?fù)渎?lián)系，使得兩個(gè)圖層構(gòu)成有機(jī)整體，形成交通路徑系統(tǒng)的完整性，需要用兩個(gè)圖層所對(duì)應(yīng)的兩張表中的文件擴(kuò)展出一定的字段，用對(duì)象的屬性信息來(lái)代表兩個(gè)圖層之間的拓?fù)潢P(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓?fù)潢P(guān)系結(jié)構(gòu)圖。 交通路徑的限制信息是交通導(dǎo)航中需要終點(diǎn)考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實(shí)際的道路中交通限制信息十分復(fù)雜，而且隨時(shí)發(fā)生變化。本文考慮的交通限制信息只考慮了禁止通行的信息。如果某條道路出現(xiàn)禁止通行的限制信息，用節(jié)點(diǎn)的 交通限制信息來(lái)表示。 （ 2）數(shù)據(jù)存儲(chǔ) 一般地，在計(jì)算機(jī)中大多采用利用鄰接表和鄰接矩陣的方法存儲(chǔ)有向圖。順序表 V0， V1， ?Vm1。的形式在鄰接局長(zhǎng)呢中存儲(chǔ)圖中所有的結(jié)點(diǎn)，以 m m 大小的矩陣存儲(chǔ)圖的邊。使用鄰接矩陣來(lái)表示圖的存儲(chǔ)淺顯易懂，也可以通過(guò)鄰接矩陣來(lái)存儲(chǔ)邊的權(quán)值信息和節(jié)點(diǎn)信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法。 武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 11 3． 3 最優(yōu)路徑選擇 3． 3． 1 最優(yōu)路徑的求解過(guò)程 在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問(wèn)題轉(zhuǎn)化成優(yōu)化問(wèn)題來(lái)解決，應(yīng)用優(yōu)化理論的相關(guān)思想 和思路解決最優(yōu)路徑優(yōu)化問(wèn)題。求解過(guò)程包括以下四個(gè)步驟酬： (1)交通網(wǎng)絡(luò)模型建立； (2)交通道路權(quán)重的計(jì)算； (3)利用最短路徑計(jì)算方法求解交通網(wǎng)絡(luò)中的最短路徑問(wèn)題； (4)將交通網(wǎng)絡(luò)圖中的最短路徑問(wèn)題轉(zhuǎn)化為現(xiàn)實(shí)交通網(wǎng)絡(luò)中的路段集合。 其中，建立交通網(wǎng)絡(luò)模型是最優(yōu)路徑選擇的基礎(chǔ)，交通網(wǎng)絡(luò)模型中道路權(quán)值的計(jì)算以及利用權(quán)值信息求解最短路徑是關(guān)鍵。道路的權(quán)值是計(jì)算現(xiàn)實(shí)問(wèn)題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與否在很大程度上取決于道路權(quán)值的設(shè)計(jì)和計(jì)算。 3． 3． 2 經(jīng)典 Dijkstra 算法分析 在 1959 年荷蘭 數(shù)學(xué)家 EW． Dijkstra 首先提出的 Dijkstra 算法，該算法是一種單源最短路徑的搜索算法，他適用于非負(fù)權(quán)值網(wǎng)絡(luò)的，是目前求解最短路問(wèn)題的理論上最完備、應(yīng)用范圍最廣的算法，可以計(jì)算出從圖中的某一節(jié)點(diǎn)到其他任意節(jié)點(diǎn)的最短路徑搜索結(jié)果 .Dijkstra 是一種迭代的貪心策略的路徑搜索算法，他根據(jù)路徑的長(zhǎng)短逐漸增長(zhǎng)來(lái)搜索點(diǎn)數(shù)，構(gòu)造了一顆路徑樹(shù)，從而得到路徑樹(shù)中的根部節(jié)點(diǎn)到其他任意節(jié)點(diǎn)的最短路徑結(jié)果。假設(shè)帶權(quán)值的有向圖為 G=(V，E)，其中 V是數(shù)量為 n 的結(jié)點(diǎn)集， E 是數(shù)量為 m的邊集， w為權(quán)值向量。具體算法步驟如下： (1) 對(duì) d 和 x 進(jìn)行初始化； (2)s 集合初始為空， S=Φ ； （ 3）為當(dāng)前圖中的所有結(jié)點(diǎn)賦值給集合 Q， Q=V[G]： (4)循環(huán)條件： while Q≠ Φ ； 武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 12 (5)提取出集合 Q中最小 d值的結(jié)點(diǎn)，并賦給甜， U=PointMin(Q)： (6)將提取出的結(jié)點(diǎn)加入 S集合， S=S∪ {u}； (7)對(duì)于每個(gè)結(jié)點(diǎn) v€ Adj[u]，計(jì)算并修改 v的 d和， π ； (8)結(jié)束。 最初 Dijkstra 算法開(kāi)發(fā)的目的是計(jì)算網(wǎng)絡(luò)圖中兩節(jié)點(diǎn)之間的最短路徑問(wèn)題，當(dāng)該算法應(yīng)用到交通網(wǎng)絡(luò)的最短路徑搜索時(shí)，由于起始點(diǎn)和終止點(diǎn)都是已知的，因 此只需要從起始點(diǎn)開(kāi)始搜索，按照其搜索原則尋找最短路徑，一直搜索的終止點(diǎn)為止，需要對(duì)該算法進(jìn)行優(yōu)化和改進(jìn)，才能使用到交通網(wǎng)絡(luò)的最優(yōu)路徑選擇系統(tǒng)當(dāng)中。從算法的原理可以發(fā)現(xiàn)，當(dāng)交通網(wǎng)絡(luò)十分龐大時(shí)，該算法的計(jì)算量是十分巨大的，如果將該算法直接用于交通網(wǎng)絡(luò)的最優(yōu)路徑選擇算法當(dāng)中，不能達(dá)到應(yīng)用的實(shí)時(shí)性要求，因此需要對(duì)該算法的性能進(jìn)行提升式改進(jìn)。另外，該算法只是路徑搜索，對(duì)于交通網(wǎng)絡(luò)中的路徑權(quán)值問(wèn)題沒(méi)有任何解決辦法，因此該算法可以作為最優(yōu)路徑選擇的主要路徑搜索算法，而對(duì)于權(quán)值的提取和計(jì)算，需要額外增加輔助算法來(lái)完成，能夠 反映交通網(wǎng)絡(luò)系統(tǒng)在實(shí)時(shí)狀態(tài)下權(quán)值的變化情況。 3． 3． 3 Dijkstra 算法改進(jìn) 由于動(dòng)態(tài)路徑所具有的特點(diǎn)，需要在搜索過(guò)程中實(shí)時(shí)導(dǎo)入交通系統(tǒng)中的更新的信息，而 Dijkstra 算法不能適用與大規(guī)模交通網(wǎng)絡(luò)的路徑搜索問(wèn)題，因此需要對(duì) Dijkstra 算法進(jìn)行改進(jìn)，改進(jìn)的 Dijkstra 算法的具體計(jì)算步驟如下： (1)初始化：設(shè) S 僅包含原節(jié)點(diǎn)，原節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn) (m)，令 d=0，π =φ，其他各節(jié)點(diǎn)的 d=∞，π =φ： (2)如果 S中包含全部節(jié)點(diǎn)，轉(zhuǎn)入 (6)；否則轉(zhuǎn)入 (3)； (3)根據(jù)當(dāng)前節(jié)點(diǎn)歷后面連接的路段自動(dòng)生 成節(jié)點(diǎn) m 的后繼結(jié)點(diǎn)，對(duì)每一個(gè)后繼節(jié)點(diǎn) n，計(jì)算如下： a．計(jì)算車(chē)輛到達(dá)節(jié)點(diǎn)歷時(shí)對(duì)應(yīng)的 Sk 值；計(jì)算車(chē)輛在節(jié)點(diǎn) m與節(jié)點(diǎn) n之問(wèn)的時(shí)問(wèn)花費(fèi)； b．如果 d(n)d(m)+time(m， n)，則將 d(n)=d(m)+time(m， n)，π (n)=m：否則轉(zhuǎn)入 (4)； 武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 13 (4)排除與節(jié)點(diǎn) m相鄰的節(jié)點(diǎn)的限制信息并讀取 m的限制信息。搜索 d 值最小的結(jié)點(diǎn)并將當(dāng)前節(jié)點(diǎn)設(shè)為 (m)，將結(jié)點(diǎn) m 加入到集合 S 中，轉(zhuǎn)入步驟 (2)；否則程序終止，這時(shí)，對(duì)每個(gè)屬于 S 的節(jié)點(diǎn)，其 d值就是原節(jié)點(diǎn)到達(dá)此節(jié)點(diǎn)的最短路徑需要花費(fèi)的時(shí)間； (5)根據(jù) s 中節(jié)點(diǎn)的屬 性信息開(kāi)始回溯，一直回溯到起始的源節(jié)點(diǎn)，最后報(bào)告結(jié)果路徑 。 (6)算法結(jié)束。 當(dāng)算法結(jié)束時(shí)，集合 S 中的每個(gè)節(jié)點(diǎn)，其 d值表示的就是原始節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)利用最短路徑所耗費(fèi)的市靜安。若 s表示交通路徑中路段數(shù)， Z表示交通路徑中的節(jié)點(diǎn)的個(gè)數(shù)，則改進(jìn)算法的時(shí)間復(fù)雜度最大值為 O(z^2+s)+O(z^2） 3． 3. 4 交通阻抗分析 交通阻抗是車(chē)輛運(yùn)行在交通道路上時(shí)，根據(jù)運(yùn)行的距離、時(shí)間、舒適度、擁堵情況、交通費(fèi)用和人的舒適度等綜合因素，需要考慮到即人、車(chē)、路、環(huán)境相互影響，對(duì)交通出行的阻力作用值。針對(duì)不同的交通網(wǎng)絡(luò)系 統(tǒng)，阻抗值的計(jì)算方法不同，需要考慮到的阻礙因素也不同。城市交通系統(tǒng)的交通阻抗可分為兩類(lèi)，節(jié)點(diǎn)交通阻抗和道路交通阻抗，節(jié)點(diǎn)交通阻抗表示的是交叉口的交通阻抗。 交通阻抗的計(jì)算指標(biāo)主要表現(xiàn)在阻抗函數(shù)的確定，為了將交通阻抗使用語(yǔ)一般性的公路系統(tǒng)，將路徑誘導(dǎo)算法中采用廣義上的交通阻抗。所謂廣義交通阻抗，是指出行者從起始點(diǎn)開(kāi)始駕駛機(jī)動(dòng)車(chē)到達(dá)終點(diǎn)而付出的代價(jià)以及對(duì)交通道路系統(tǒng)帶來(lái)的負(fù)面效應(yīng)的綜合。它的要素應(yīng)該包括出行時(shí)間、出行方式、出行費(fèi)用、使用資源、車(chē)輛磨損、環(huán)境污染程度等。因此交通阻抗的最小值為以上各個(gè)元素最小值的總 和，而最大值為以上各個(gè)元素最大值的總和。在路徑選擇中，有出行時(shí)間長(zhǎng)度、行駛距離長(zhǎng)度、擁擠程度、道路質(zhì)量和出行費(fèi)用等評(píng)價(jià)指標(biāo)，以提供不同的應(yīng)用環(huán)境進(jìn)行選擇使用。當(dāng)交通網(wǎng)絡(luò)中交通流量分布比較均勻，沒(méi)有出現(xiàn)交通意外事故等特殊情況時(shí)，這五種評(píng)價(jià)方法不會(huì)互相矛盾的，當(dāng)交通道路中出現(xiàn)交通擁堵，交通事故等特殊情況時(shí)，這五種評(píng)價(jià)方法所得到的結(jié)果可能不同，有存在矛盾的地方，但一般來(lái)說(shuō)，實(shí)際情況下考慮出行的交通阻抗，一般采用一武漢紡織大學(xué) 2021屆畢業(yè)設(shè)計(jì)論文 14 時(shí)問(wèn)為評(píng)價(jià)標(biāo)準(zhǔn)來(lái)作為交通那個(gè)阻抗的評(píng)價(jià)指標(biāo)。 3. 4 本章小結(jié) 本章利用圖論的相關(guān)理論和方法對(duì)交通 道路進(jìn)行分析。分析了經(jīng)典的最優(yōu)路徑