大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文摘要智能交通系統(tǒng)中的核心問題是最優(yōu)路徑選擇問題。本文分析了交通道路網(wǎng)絡(luò)的具體特點，主要包括線性分布特點、網(wǎng)絡(luò)分布特點、分段分布特點、動態(tài)性特點和車輛行駛的自主性特點等。將交通網(wǎng)絡(luò)抽象成一個由邊和節(jié)點組成的圖，并根據(jù)圖論的相關(guān)理論和知識構(gòu)建起交通網(wǎng)絡(luò)模型，包括交通道路節(jié)點模型，交叉口和道路模型，并對上述道路模型信息進行存儲，以構(gòu)建好的交通道路模型為基礎(chǔ)研究智能交通系統(tǒng)中的最優(yōu)路徑問題?？紤]了實際道路中存在一定的交通阻抗，是算法更具有應(yīng)用價值，在Ｄｉｊｋｓｔｒａ算法的基礎(chǔ)上進行了改進，縮短了道路搜索時問，提高了最優(yōu)路徑選擇的效率。數(shù)據(jù)庫的選擇與設(shè)計是系統(tǒng)實現(xiàn)中不可或缺的重要組成部分，優(yōu)秀的數(shù)據(jù)庫選擇和設(shè)計方案能夠提高最優(yōu)路徑選擇的效率、也提高了整個智能交通系統(tǒng)的工作效率。本文使用了ＧＩＳ數(shù)據(jù)模型與數(shù)據(jù)庫的管理設(shè)計，主要包括ＧＩＳ數(shù)據(jù)的簡介、選擇Ｏｒａｃｌｅ的理由、ＧＩＳ數(shù)據(jù)向Ｏｒａｃｌｅ中的導(dǎo)入和存儲、Ｏｒａｃｌｅ中ＧＩＳ數(shù)據(jù)的訪問和維護。對道路交通系統(tǒng)的建模、最優(yōu)路徑選擇算法的研究以及數(shù)據(jù)庫的開發(fā)設(shè)計目的是建立一‘套接近實際情況的最優(yōu)路徑選擇系統(tǒng)。本文利用Ｍａｐｌｎｆｏ軟件繪制交通系統(tǒng)的電子地圖，開發(fā)工具使用ＧＩＳ控件ＭａｐＸ與ＶｉｓｕａｌＣ＋＋。將經(jīng)典的Ｄｉｊｋｓｔｒａ算法和改進的Ｏｉｊｋｓｔｒａ算法進行編碼實現(xiàn)，使之在最優(yōu)路徑選擇系統(tǒng)中正確運行。關(guān)鍵詞：智能交通系統(tǒng)，最優(yōu)路徑，ＧＩＳ數(shù)據(jù)，系統(tǒng)設(shè)計智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)ＤｅｓｉｇｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｈｅＯｐｔｉｍａｌＰａｔｈｉｎＩｎｔｅｌｌｉｇｅｎｔＴｒａｎｓｐｏｒｔａｔｉｏｎＳｙｓｔｅｍｓＡｂｓｔｒａｃｔＴｈｅｏｐｔｉｍａｌｐａｔｈｉｓａｎｉｍｐｏｒｔａｎｔｐａｒｔｏｆｔｈｅｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ．Ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｓｔｈｅｓｐｅｃｉｆｉｃｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｔｒａｆｆｉｃａｎｄｒｏａｄｎｅｔｗｏｒｋ，ｉｎｃｌｕｄｉｎｇｌｉｎｅａｒｄｉｓｔｒｉｂｕｔｉｏｎｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｎｅｔｗｏｒｋｄｉｓｔｒｉｂｕｔｉｏｎｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ｓｅｇｍｅｎｔｅｄｄｉｓｔｒｉｂｕｔｉｏｎｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ｄｙｎａｍｉｃｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｖｅｈｉｃｌｅｓａｕｔｏｎｏｍｏｕｓｆｅａｔｕｒｅｓ．Ａｂｓｔｒａｃｔｔｒａｎｓｐｏｒｔａｔｉｏｎｎｅｔｗｏｒｋａｓａｇｒａｐｈｏｆｅｄｇｅｓａｎｄｎｏｄｅｓ，ａｎｄｂｕｉｌｄａｔｒａｎｓｐｏｒｔａｔｉｏｎｎｅｔｗｏｒｋｍｏｄｅｌｂａｓｅｄｏｎｇｒａｐｈｔｈｅｏｒｙｔｈｅｏｒｙａｎｄｋｎｏｗｌｅｄｇｅ，ｉｎｃｌｕｄｉｎｇｔｒａｆｆｉｃｒｏａｄｎｏｄｅｍｏｄｅｌ，ｉｎｔｅｒｓｅｃｔｉｏｎｓａｎｄｒｏａｄｍｏｄｅｌ，ａｎｄｓｔｏｒａｇｅｏｆｔｈｅｒｏａｄｍｏｄｅｌｉｎｆｏｒｍａｔｉｏｎｔｏｂｕｉｌｄｇｏｏｄｔｒａｆｆｉｃｒｏａｄｍｏｄｅｌｆｏｒｂａｓｉｃｒｅｓｅａｒｃｈｉｎｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍｓ，ｔｈｅｏｐｔｉｍａｌｐａｔｈ．Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅａｃｔｕａｌｒｏａｄｔｒａｆｆｉｃｉｍｐｅｄａｎｃｅ，ｉｓｔｈｅａｌｇｏｒｉｔｈｍｍｏｒｅａｐｐｌｉｃａｔｉｏｎｉｍｐｒｏｖｅｄｖａｌｕｅｏｎｔｈｅｂａｓｉｓｏｆｔｈｅＯｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍ，ｓｈｏｒｔｅｎｉｎｇｔｈｅｐａｔｈｓｅａｒｃｈｔｉｍｅ，ａｎｄｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｓｅｌｅｃｔｉｏｎｏｆｔｈｅｏｐｔｉｍａｌｐａｔｈ．Ｔｈｅｄａｔａｂａｓｅｉｓａｎｉｍｐｏｒｔａｎｔｐａｒｔｏｆａｎｉｎｔｅｇｒａｌｓｙｓｔｅｍｄｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ｄａｔａｂａｓｅｓｅｌｅｃｔｉｏｎａｎｄｄｅｓｉｇｎｏｆａｄｉｒｅｃｔｉｍｐａｃｔｏｎｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｐａｔｈｐｌａｎｎｉｎｇｓｙｓｔｅｍ．ＴｈｉｓａｒｔｉｃｌｅＵｓｅＳｔｈｅｄｅｓｉｇｎｏｆａＧＩＳｄａｔａｍｏｄｅｌａｎｄｄａｔａｂａｓｅｍａｎａｇｅｍｅｎｔ，ｍａｉｎｌｙｉｎｃｌｕｄｉｎｇｔｈｅｉｎｔｒｏｄｕｃｔｉｏｎｏｆＧＩＳｄａｔａ，ｓｅｌｅｃｔＯｒａｃｌｅｒｅａｓｏｎｉｍｐｏｒｔｅｄａｎｄｓｔｏｒｅｄｉｎｔｈｅＯｒａｃｌｅ，ＧＩＳｄａｔａ，ｔｈｅＯｒａｅｌｅＧＩＳｄａｔａａｃｃｅｓｓａｎｄｍａｉｎｔｅｎａｎｃｅ．Ｍｏｄｅｌｉｎｇｏｆｒｏａｄｔｒａｆｆｉｃｓｙｓｔｅｍ，ｔｈｅｏｐｔｉｍａｌｐａｔｈｓｅｌｅｃｔｉｏｎａｌｇｏｒｉｔｈｍ弱ｗｅｌｌａｓｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｔｈｅｄａｔａｂａｓｅｉｓｄｅｓｉｇｎｅｄｔｏｅｓｔａｂｌｉｓｈｔｈｅｏｐｔｉｍａｌｒｏｕｔｅｓｅｌｅｃｔｉｏｎｓｙｓｔｅｍｓｅｔｃｌｏｓｅｔｏｔｈｅａｃｔｕａｌｓｉｔｕａｔｉｏｎ．ＤｒａｗｎｅｌｅｃｔｒｏｎｉｃｍａｐｉｓｍａｄｅｂｙＭａｐｌｎｆｏｓｏｔｔｗａｒｅｄｅｖｅｌｏｐｍｅｎｔｔｏｏｌｓａｎｄｔｈｅｔｏｏｌｓｕｓｃＧＩＳｃｏｍｐｏｎｅｎｔＭａｐＸａｎｄＶｉｓｕａｌＣ＋＋．ＣｌａｓｓｉｃａｌＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍａｎｄｉｍｐｒｏｖｅｄＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍｗｅｒｅｉｍｐｌｅｍｅｎｔｅｄ．Ｔｈｅｏｐｔｉｍａｌｐａｔｈｓｅｌｅｃｔｉｏｎｓｙｓｔｅｍｉｓｐｒｏｖｅｄｃｏｒｒｅｃｔｌｙ．Ｋ鑼Ｗｏｒｄｓ：ＩｎｔｅｌｌｉｇｅｎｔＴｒａｎｓｐｏｒｔａｔｉｏｎＳｙｓｔｅｍｓ；Ｏｐｔｉｍａｌｐａｔｈ；ＧＩＳｄａｔａ；ＳｙｓｔｅｍｄｅｓｉｇｎＩＩ大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文目錄摘要………………ＩＡｂｓｔｒａｃｔ……．．…．．．．．……………ＩＩ引言………………ｌｌ基礎(chǔ)知識…………ｌＯ１．１路徑優(yōu)化算法概述………一１０１．１．１Ｆｌｏｙｄ算法…………．１０１．１．２Ｄｉｊｋｓｔｒａ算法…………１ｌ１．１．３ＧＰＳＲ算法…………１２１．２圖論簡介…………………．１２１．２．１圖的概念……………一１３１．２．２圖的表示………………１３１．２．３圖的存儲……………．１５１．３本章小結(jié)…………………．１６２最優(yōu)路徑…………１７２．１城市交通模型建立…………．１７２．１．１道路節(jié)點模型………１８２．１．２交叉口和道路模型…………………１９２．２交通模型數(shù)據(jù)存儲………一２ｌ２．２．１數(shù)據(jù)預(yù)處理…………２１２．２．２交通路徑模型建立與數(shù)據(jù)存儲……２ｌ２．３最優(yōu)路徑選擇………………２３２．３．１最優(yōu)路徑的求解過程………………２３２．３．２經(jīng)典Ｄｉｊｋｓｔｒａ算法分析……………．２４２．３．３交通阻抗分析………２５２．３．４Ｄｉｉｋｓ咖算法改進…………………．２８２．４本章小結(jié)…………………．２９３Ｇｌｓ數(shù)據(jù)模型和數(shù)據(jù)庫設(shè)計……………………．．３０３．１ＧＩＳ數(shù)據(jù)模型建立…………３０３．１．１空間數(shù)據(jù)模型№¨……………………３０３．１．２屬性數(shù)據(jù)模型………３２３．２ＧＩＳ數(shù)據(jù)的管理與組織……………………３２－Ⅲ．智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)３．２．１ＧＩＳ數(shù)據(jù)管理原則呻１………………３３３．２．２ＧＩＳ數(shù)據(jù)的組織……………………３３３．３ＯｒａｃｌｅＳｐａｔｉａｌ簡介………。３４３．４空間數(shù)據(jù)向Ｏｒａｃｌｅ中的導(dǎo)入……………。３７３．５ＧＩＳ數(shù)據(jù)在０１Ｔ，Ｒｌｅ中的存儲………………３７３．５．１道路數(shù)據(jù)在Ｏｒａｃｌｅ中的存儲………３８３．５．２節(jié)點數(shù)據(jù)在Ｏｒａｃｌｅ中的存儲………．４０３．５．３分層道路數(shù)據(jù)在Ｏｒａｃｌｅ中的存儲…………………４１３．５．４多比例尺道路數(shù)據(jù)在Ｏｒａｃｌｅ中的存儲……………４１３．６Ｏｒｅ．ａｌｅ中ＧＩＳ數(shù)據(jù)的訪問………………。４ｌ３．７Ｏｒｃａｌｅ中ＧＩＳ數(shù)據(jù)的維護………………一４２３．７．１數(shù)據(jù)庫表的創(chuàng)建、刪除……………一４２３．７．２數(shù)據(jù)庫記錄的添加、刪除和修改…………………一４２３．８本章小結(jié)…………………一４２４路徑優(yōu)化算法系統(tǒng)實現(xiàn)…………．４３４．１電子地圖制作………………４３４．１．１電子地圖制作的原則…………………４３４．１．２ＭａｐＩｎｆｏ軟件概述……………………４３４．１．３Ｍａｐｌｎｆｏ電子地圖的繪制……………４３４．１．５電子地圖的實現(xiàn)……………………４６４．２開發(fā)工具選擇……………一４６４．２．１ＭａｐＸ的特點……………………４６４．２．２ＶｉｓｕａｌＣ＋＋………………．４７４．３仿真結(jié)果與分析…………一４７４．４本章小結(jié)…………………．４８結(jié)論…………………………一４９參考文獻……………５０致謝……………一５４大連理工大學(xué)學(xué)位論文版權(quán)使用授權(quán)書……………５５ＩＶ大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文引言隨著我國改革開放經(jīng)濟的發(fā)展，人口數(shù)量的不斷增多，城市的數(shù)量和規(guī)模不斷增大和增多，城市化程度和趨勢十分明顯，城市交通問題成為目前影響和制約我國經(jīng)濟發(fā)展和社會進步的主要因素。近年來，我國ＧＤＰ以８％－１０９６的較高的速度增長，城市化程度逐漸提高，社會經(jīng)濟迅速發(fā)展，這對城市交通系統(tǒng)的要求提出了挑戰(zhàn)，而我國大部分城市都集中在東部沿海地區(qū)，人口密度和區(qū)域面積與其他地區(qū)不成比例。不論是上海北京等特大城市還是其他省會城市或地級市，普遍存在交通問題，城市車輛不斷增多，人口越發(fā)密集，道路環(huán)境不斷惡化等原因都是導(dǎo)致城市交通問題的主要方面。主要體現(xiàn)在分時段的交通擁堵、交通事故頻發(fā)和環(huán)境污染嚴重等。交通運輸是國民經(jīng)濟發(fā)展的重要支柱。長期以來，西方發(fā)達國家和發(fā)展中國家的大中城市都不同程度的存在交通問題，如車輛行駛緩慢、交通擁擠、交通事故頻繁以及由于交通不暢引起的交通事故人員傷亡和環(huán)境污染等。這些問題的解決需依靠各種信息技術(shù)來解決口１。交通擁堵已經(jīng)成為制約交通運輸事業(yè)發(fā)展的瓶頸，不僅降低了物資運輸或人員交流的效率，影響人們正常出行，并且很大程度上降低社會發(fā)展效率。統(tǒng)計了我國大約６６７個城市中，在上下班或者假日的交通高峰期，約有６７％的道路機動車行駛變得緩慢，甚至擁堵或發(fā)生交通事故。一些大中城市交通環(huán)境脆弱，由于道路設(shè)計或交通規(guī)則不合理，導(dǎo)致高峰時段交通擁堵嚴重，如果城市中某一條主干道發(fā)生交通事故而交通堵塞則可常常引發(fā)大面積、長時間的交通擁堵，尤其是特大城市的主干道和次干道的交通流經(jīng)常在高峰時段已達到飽和或超飽和狀態(tài)（如上?；虮本?，正常的經(jīng)濟往來，貨物運輸，市民出行等會受到嚴重影響。公路或鐵路的交通系統(tǒng)建設(shè)是我國針對交通運輸?shù)幕A(chǔ)設(shè)施建設(shè)，在國家的經(jīng)濟發(fā)展中起到不可替代的作用，是連接兩個城市之間的貨物、人員、信息流的大動脈，較好的公路交通環(huán)境對于各個地區(qū)的經(jīng)濟建設(shè)、減小城鄉(xiāng)之間的經(jīng)濟差距起到了非常好的促進作用乜１。隨著我國現(xiàn)代化建設(shè)的不斷深化，城市化水平不斷提高，城市規(guī)模和人口數(shù)量也在不斷的擴大，這使得機動車的數(shù)量也在不斷增加，在不斷提高人民生活水平的同時，人們的日?；顒右苍诩眲≡黾?，這給地區(qū)之問的交通流通帶來很大壓力。由于發(fā)展的需求，城市的規(guī)模和人口不斷擴大，而交通道路資源是有限的，交通擁堵，意外交通事故和交通環(huán)境的污染等一系列問題由此產(chǎn)生，尤其是北京、上海等大城市，這些交通問題尤其突出。而造成交通擁堵、交通事故和環(huán)境污染的另一個重要原因是信息管理的缺失和不夠重視。經(jīng)過近幾年的發(fā)展，政府部門對ＩＴ基礎(chǔ)設(shè)施建設(shè)已經(jīng)初具規(guī)模，我國信息化產(chǎn)智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)業(yè)建設(shè)正處在由信息資源建設(shè)向信息資源管理轉(zhuǎn)換的重要時期。交通擁堵交通事故和交通污染對一個城市造成的影響包括，增加了城市運行的成本，降低了各項服務(wù)質(zhì)量，對于醫(yī)療救護、消防和警務(wù)事務(wù)的影響極為致命。交通事故的數(shù)量和頻率在國內(nèi)大中城市每年都會不同程度的增加，事故死亡率為８－１０７６左右。交通設(shè)旅建設(shè)、管理和規(guī)劃中需要的信息具有范圍廣、數(shù)據(jù)量大、復(fù)雜多變等特點，且絕大多數(shù)信息擁有空問意義上的特性。尋求一種對數(shù)據(jù)采集、數(shù)據(jù)挖掘和整合、數(shù)據(jù)存儲和管理能夠有效管理，并能將這些信息作為布局規(guī)劃、交通建設(shè)、戰(zhàn)略決策和信息管理等方面的工具成為人們不斷追求的目標。在我國，幾乎絕大多數(shù)社會信息資源和數(shù)據(jù)庫掌握在各級政府部門手中。聯(lián)合國教科文組織曾經(jīng)對政府部門掌握的社會信息數(shù)據(jù)進行統(tǒng)計和分析，其研究的報告顯示，７０—８５％的社會信息是有對經(jīng)濟發(fā)展有價值的。對中國來說，政府部門及其相關(guān)單位掌握這國內(nèi)社會信息的６０９６以上，而這些大量的寶貴的信息資源并沒有被政府部門充分利用口１。由于近幾年我國政府認識到這一點，加大交通系統(tǒng)管理的投入，在交通系統(tǒng)的管理方面雖有較大進展，但信息資源管理中仍然存在著信息量缺乏嚴重、質(zhì)量提高速度慢、管理結(jié)構(gòu)不平衡、流動不通暢和體制不健全、機制含糊、標準不統(tǒng)一等問題。由于國家戰(zhàn)略和保密政務(wù)信息公開制度不完善，各部門溝通不夠?qū)е滦畔①Y源采集重復(fù)，管理機制不夠先進導(dǎo)致開發(fā)利用的市場化、產(chǎn)業(yè)化程度偏低等缺點。通過最近一個世紀的發(fā)展，西方發(fā)達國家達到鼎盛，從這些國家城市化的發(fā)展歷史來看，機動車數(shù)量的增長永遠快于道路加寬加多的速度，增加停車場數(shù)量等基礎(chǔ)設(shè)施建設(shè)來解決當前出現(xiàn)的交通問題。解決這些交通問題的最有效、最根本的途徑還是通過加快高新技術(shù)管理，通過信息技術(shù)來提高和完善交通信息管理的能力，提高交通運輸?shù)男?。解決交通問題出現(xiàn)了新的思路和辦法，因此智能交通系統(tǒng)（ＩｎｉｅｌｌｉｇｅｎｉＴｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ，ＩＴＳ）Ｈ１的誕生為解決交通問題提供了全新的方式。隨著計算機技術(shù)和電子技術(shù)的不斷發(fā)展，以及電子地圖測繪技術(shù)的不斷進步，這使得地理信息系統(tǒng)也得到了長足的進步，這些技術(shù)的發(fā)展都給智能交通系統(tǒng)的發(fā)展奠定了良好的基礎(chǔ)。通過中西交通道路系統(tǒng)的比較，我國城市交通系統(tǒng)的主要問題包括陸１交通管理技術(shù)落后，交通系統(tǒng)的發(fā)展永遠跟不上社會發(fā)展的要求，交通系統(tǒng)供需矛盾突出。為大道交通系統(tǒng)的可持續(xù)發(fā)展，從根本上解決問題上述交通擁堵問題，并保持大中城市交通可持續(xù)發(fā)展帶動城市的可持續(xù)反戰(zhàn)，除了合理地進行交通道路等基礎(chǔ)設(shè)施建設(shè)外，另一個切實可行的辦法就是引進西方先進的高科技管理技術(shù)改進我們的交通系統(tǒng)，并使其符合我國國情，建立高性能高效率的智能城市交通系統(tǒng)（ＩＴＳ）。智能交通系統(tǒng)（ＩＴＳ）通過充２大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文分發(fā)揮現(xiàn)有交通資源潛力和系統(tǒng)內(nèi)部協(xié)同作用產(chǎn)生的效力，能夠為城市交通提供更安全、更舒適、更高效率和更高品質(zhì)的新型城市交通系統(tǒng)嘲。智能交通系統(tǒng)的目標是利用現(xiàn)金的計算機技術(shù)和先進的網(wǎng)絡(luò)管理來減少交通擁堵、交通事故和環(huán)境污染，與此同時，交通系統(tǒng)能夠有效的正常的運行。在交通、計算機、電子通信、信息技術(shù)和系統(tǒng)科學(xué)與工程應(yīng)用領(lǐng)域中，智能交通系統(tǒng)是日前許多國內(nèi)外學(xué)者和研究機構(gòu)集中、深入的研究領(lǐng)域之一，具有非常好的發(fā)展前景。車輛導(dǎo)航系統(tǒng)（ｖＮＳ）是城市智能交通系統(tǒng)的核心內(nèi)容之一，主要依據(jù)實時的路況信息來提高道路的通行能力，是減少交通擁堵、以外交通事故和環(huán)境污染的有效辦法。隨著交通事業(yè)的不斷發(fā)展，基礎(chǔ)設(shè)施建設(shè)的不斷完善，城市交通的網(wǎng)絡(luò)建設(shè)步伐的加快，交通設(shè)旆的不斷完善，以及交通管理措施的不斷細化、改進和應(yīng)用，駕駛員有了更多的自主選擇空問。但是如果缺少路況的引導(dǎo)方法，這些資源將會被浪費、而且交通擁堵、交通事故和環(huán)境污染也會不斷增加。因此，對目前的交通系統(tǒng)來說，急需一套行之有效的車輛管理和導(dǎo)航系統(tǒng)來彌補這個不足，是駕駛員了解實時路況，避免交通擁堵，這樣能夠減少交通事故的發(fā)生，減少環(huán)境污染，安全方便的到達目的地。在西方發(fā)達國家的車輛導(dǎo)航系統(tǒng)研究中，所能夠?qū)崿F(xiàn)的也只是以同時期的歷史數(shù)據(jù)為導(dǎo)航依據(jù)，而基于實時路況信息的動態(tài)導(dǎo)航系統(tǒng)還處在研究當中，沒有達到應(yīng)用水平。在我國，由于受到經(jīng)濟水平、技術(shù)條件和交通道路特點的限制，對只能交通系統(tǒng)的研究和開發(fā)應(yīng)用起步晚于西方發(fā)達國家，國外的某些技術(shù)應(yīng)用也不能完全使用于中國的特殊復(fù)雜的交通環(huán)境，不能照搬或照抄西方國家交通系統(tǒng)的制度和理念。隨著我國交通運輸業(yè)的不斷發(fā)展，交通環(huán)境日益惡化的今天，研究出一套能夠適應(yīng)我國國情的現(xiàn)代智能交通系統(tǒng)和車輛導(dǎo)航系統(tǒng)，使之能夠為人們出行提供重要的交通信息，避免交通擁堵，減少交通事故，為駕駛者提供最佳的駕駛路徑，達到交通的路網(wǎng)暢通已經(jīng)迫在眉睫。如果能夠?qū)囕v導(dǎo)航系統(tǒng)提供行之有效的最佳路徑選擇算法，就能為人們出行提供有效、合理有效的出行路徑，從而提高交通系統(tǒng)運行的效率。最佳路徑選擇問題是智能交通系統(tǒng)中的重要組成部分，也是交通地理信息系統(tǒng)研究中的一個熱點問題之一，是出行路徑設(shè)計與優(yōu)化、現(xiàn)有有限資源重新利用和分配等問題的基礎(chǔ)。因此最優(yōu)路徑選擇與優(yōu)化問題是實時的動態(tài)交通系統(tǒng)中具有具有重要現(xiàn)實意義的研究課題。目前國內(nèi)外已經(jīng)有許多學(xué)者和研究機構(gòu)對最佳路徑選擇做了深入研究，并取得了很好的效果。最佳路勁的算法研究不僅可以應(yīng)用在交通網(wǎng)絡(luò)系統(tǒng)中，而且對出行決策、校車路徑查詢、快遞物流、資源分配等方面也有很好的應(yīng)用價值。道路交通系統(tǒng)中最佳路徑選擇的研究能夠為綜合信息管理和只能決策提供先進、科學(xué)和行之有效的判決依據(jù)；為人們出行提供便利的交通運輸條件；為車輛的運行提供安智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)全保障：提高了現(xiàn)代交通道路的利用效率；幫助車輛減少尾氣排放和燃油等資源的消耗：對于建設(shè)資源節(jié)約型社會具有劃時代的意義。歐美等西方發(fā)達國家在近一個世紀的飛速發(fā)展中，交通擁堵問題在以前和現(xiàn)在都是制約其發(fā)展的主要方面，因此很早就對智能交通系統(tǒng)的研究投入大量的人力、物力和財力Ⅲ。美國智能交通系統(tǒng)的發(fā)展尤為突出，幾個發(fā)展較快的方面分別是車輛安全系統(tǒng)、公路和車輛管理系統(tǒng)、電子收費系統(tǒng)、自動定位系統(tǒng)和商業(yè)車輛管理系統(tǒng)。美國先后分別頒布了對其智能交通系統(tǒng)發(fā)展具有重要意義的兩部法律，即１９９１年頒布的綜合運輸效率化法案６（ＩＳＴＥＡ，ＩｎｔｅｒｍｏｄａｌＳｕｒｆａｃｅＴｒａｎｓｐｏｒｔａｔｉｏｎＥｆｆｉｅｃｉｅｎｃｙＡｃｔ）和１９９８年頒布的２ｌ世紀的運輸平衡法案（ＴＥＡ－２１，ｔｈｅＴｒａｎｓｐｏｒｔａｔｉｏｎＥｑｕｋｙＡｃｔｆｏｒｔｈｅ２１ｓｔＣｅｎｔｕｒｙ），這兩部道路交通建設(shè)法律從法律的角度和較高的高度統(tǒng)一規(guī)劃智能交通系統(tǒng)（ＩＴＳ）的發(fā)展，制定投資計劃。繼美國對智能交通系統(tǒng)的研究開展之后，歐洲、日本等國家對智能交通系統(tǒng)的相關(guān)領(lǐng)域的研究開發(fā)也相繼展開。經(jīng)過數(shù)十年的發(fā)展，美、歐、日已經(jīng)成為國際智能交通系統(tǒng)研究的主要研究開發(fā)基地。另外一些國家和地區(qū)的智能交通系統(tǒng)（ＩＴＳ）研究也取得長足的發(fā)展，如加拿大、澳大利亞、韓國等。歐洲在智能交通系統(tǒng)（ＩＴＳ）方面研究的進展介于美國和日本之間。由于歐盟中各個國家對交通系統(tǒng)需求的不一致，導(dǎo)致對ＩＩＳ的投資比較分散，不能集中所有國家的資源共同研究和開發(fā)同一套系統(tǒng)，整個歐洲建立同一的交通信息附體體系較難。然后在研究開發(fā)車輛控制系統(tǒng)（ＡｄｖａｎｃｅｄＶｅｈｉｃｌｅＣｏｎｔｒｏｌＳｙｓｔｅｍ，ＡＶＣＳ）、旅行信息系統(tǒng)（ＡｄｖａｎｃｅｄＴｒａｖｅｌＩｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍｓ，ＡＴＩＳ）、電子收費系統(tǒng)（ＡｄｖａｎｃｅｄＥｌｅｃｔｒｏｎｉｃＴｏｌｌＣｏｌｌｅｃｔｉｏｎＳｙｓｔｅｍ）、商業(yè)車輛運行系統(tǒng)（ＡｄｖａｎｃｅｄＣｏｍｍｅｒｅｉａｌＶｅｈｉｃｌｅｓＯｐｅｒａｔｉｎｇＳｙｓｔｅｍ，ＡＣＶｏＳ）等方面，前景十分可觀。日本目前有五個國家部門負責智能交通系統(tǒng)的建設(shè)和相關(guān)活動，這五個部門分別為：建設(shè)省、警視廳、國際貿(mào)易和工業(yè)省、運輸省以及郵電省阻１。這五個部門同時經(jīng)由其他的組織來促進ＩＴＳ的發(fā)展，例如車輛、道路和交通智能化社團（ｔｈｅＶｅｈｉｃｌｅ，ＲｏａｄａｎｄＴｒａｆｆｉｃＩｎｔｅｌｌｉｇｅｎｃｅＳｏｃｉｅｔｙ，簡稱ＶＥＲＴＩＳ，一個致力于推動ＩＴＳ發(fā)展的行業(yè)學(xué)術(shù)組織）和ＩＳＯ廠ｒＣ２０４全國委員會（Ｉｓ０舊ｃ２０４ＮａｔｉｏｎａｌＣｏｍｍｉｔｔｅｅ，致力于推動ＩＴＳ國際標準的建立）等等。日本于１９９８年開始構(gòu)建智能交通系統(tǒng)（ＩＴＳ）框架，提出建設(shè)７個終端服務(wù)系統(tǒng)。日本政府在智能交通系統(tǒng)（ＩＴＳ）領(lǐng)域的研究與實踐投入了大量人力和物力，通過很多相關(guān)政策的制定，希望能夠形成智能交通系統(tǒng)產(chǎn)業(yè)化來推動國民經(jīng)濟的發(fā)展。在幾４大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文年的時間里內(nèi)，日本本國共有４００萬套車內(nèi)導(dǎo)航系統(tǒng)得到了實際的應(yīng)用。在智能交通系統(tǒng)（ＩＴＳ）的應(yīng)用中主要集中在交通咨詢服務(wù)、電子收費系統(tǒng)、公共交通管理服務(wù)、以及緊急車輛優(yōu)先等方面。日本目前有一億兩千萬人口，每天公路上行駛的大小車輛大約有七千萬。據(jù)日本建設(shè)省統(tǒng)計，日本每年由交通事故導(dǎo)致的傷亡人口達到１００萬人之多。在這樣一個狹窄而又擁擠的島國上，人口密度極大，緩解交通擁堵這樣的世界性難題智能依靠智能交通系統(tǒng)（ＩＴＳ）來完成。除了歐美國家及日本等發(fā)達國家以外，一些發(fā)展中國家也開始對智能交通系統(tǒng)（ＩＴＳ）進行全面的研究與開發(fā)，如韓國建設(shè)交通部門制訂了全面ＩＴＳ框架結(jié)構(gòu)和發(fā)展規(guī)劃，新加坡在全國推廣不停車收費政策等韓國政府頒布了一項關(guān)于智能交通系統(tǒng)的計劃用于引導(dǎo)智能交通系統(tǒng)的發(fā)展，即“２１世紀ＩＴＳ總計劃”，對五年前制定的計劃基礎(chǔ)上進行了更新和改進，加快其發(fā)展速度，預(yù)計在２０３０年之前政府對智能交通（ＩＴＳ）的投資總額達到７５億美元。目前，韓國的城市的高速公路和一些普通公路以及全國的各大交通線路都采用了最先進的現(xiàn)代的交通管理系統(tǒng)。自１９９５年以來，韓國首都警察署與道路安全管理委員會通過商議一同開發(fā)了具有韓國特色的交通信號系統(tǒng)，該系統(tǒng)具有很強個性，突出地展現(xiàn)了首爾交通的特色之處陽１。除了解決交通問題以外，另一個重要的原因則是智能交通系統(tǒng)（ｒｒＳ）將成為高新技術(shù)應(yīng)用產(chǎn)業(yè)最大的份額之一，這就可以解釋不論發(fā)達國家還是發(fā)展中國家為什么對智能交通系統(tǒng)（ＩＴＳ）領(lǐng)域投資如此巨大。目前ＩＴＳ關(guān)鍵技術(shù)分支主要有以下１０個方面呻一伽：（１）海上突發(fā)事件快速檢測、預(yù)警和遠程搜救資源調(diào)度技術(shù)（２）大范圍高密度異構(gòu)公共服務(wù)整合、優(yōu)化定制和協(xié)同技術(shù)（３）軍事運輸資源的定位、可視化跟蹤和投送能力保障技術(shù)（４）復(fù)雜交通流道路狀態(tài)監(jiān)測、預(yù)報和緊急事件管理技術(shù)（５）大范圍高密度條件下的客戶服務(wù)仿真與引導(dǎo)技術(shù)（６）大規(guī)模智能交通系統(tǒng)綜合集成、采集和管理技術(shù)（７）城市道路交通仿真評估和交通網(wǎng)絡(luò)誘導(dǎo)技術(shù)（８）一體化運輸任務(wù)規(guī)劃、推演、效能評估和資源調(diào)度技術(shù)（９）高速公路聯(lián)網(wǎng)不停車收費系統(tǒng)成套關(guān)鍵技術(shù)（１０）重大事件條件下交通協(xié)調(diào)管理技術(shù)智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)中國政府的交通管理部門以及相關(guān)專家，充分認識到智能交通系統(tǒng)（ＩＴＳ）對社會發(fā)展的重要作用，對交通系統(tǒng)領(lǐng)域研究的更加重視。在２０００年國家ＩＴＳ“十五”示范工程開始啟動，其中包括杭州、廣州、深圳、重慶、上海、中山等多個城市ｎ“。在２００１年１２月又啟動了“十五”國家科技攻關(guān)重大招標項目“智能交通系統(tǒng)關(guān)鍵技術(shù)開發(fā)和示范工程”，在“十一五”綜合交通體系規(guī)劃的發(fā)展中，我國也明確指出：“要加強交通樞紐和綜合交通信息網(wǎng)絡(luò)建設(shè)，構(gòu)建現(xiàn)代化的智能交通系統(tǒng)?！蔽覈鴮χ悄芙煌ㄏ到y(tǒng)的規(guī)劃主要在以下四個方面進行重點研究：ｌ，城市交通資源優(yōu)化配置技術(shù)；２，智能交通系統(tǒng)的控制與管理技術(shù)；３，交通安全信息的預(yù)報、救援和安全保障等技術(shù)；４，城市交通信息資源無條件共享及各部門互相協(xié)同服務(wù)技術(shù)。目前，智能交通系統(tǒng)（ＩＴＳ）在我國的實際應(yīng)用可概括三大領(lǐng)域口２１：ｌ，公路交通系統(tǒng)的信息化建設(shè)，其中包括高速公路建設(shè)、以及國家主干道和次干道的公路建設(shè)問題；２，城市交通道路管理信息化和服務(wù)的人性化：３，城市公交系統(tǒng)信息化。北京、廣州兩大城市在城市智能交通系統(tǒng)的建設(shè)中走在我國前列。目前北京市對智能交通系統(tǒng)（ＩＴＳ）的開發(fā)體現(xiàn)在四個方面：交通道路實時控制與管理、高速公路管理和指揮、公共交通系統(tǒng)指揮與調(diào)度、緊急事件響應(yīng)和反饋，包括大約三十個子系統(tǒng)，分散在各個交通管理部門和交通運營部門。北京市將在“十一五”規(guī)劃期間投資兩千億元人民幣構(gòu)建起新型交通系統(tǒng)，投資主要用于交通系統(tǒng)的改進升級和完善，重點將包括高速公路建設(shè)與維護、軌道交通線路的建設(shè)與維護以及智能交通系統(tǒng)的建設(shè)與維護，占北京市每年支出費用的６０％。其中，對智能交通系統(tǒng)建設(shè)與維護只占有１．５％，與國外發(fā)達國家對該方面的投資相比還差很遠。本文研究的最優(yōu)路徑問題是指在交通路網(wǎng)的一對給定的起點和終點之間找出一條通路，使得車輛從起點到終點所走過的路程最短、耗時最少、費用最低等。在很早之前就有了求解最優(yōu)路徑問題的提出，但是發(fā)展速度相對緩慢。有許多與最優(yōu)路徑求解相關(guān)的學(xué)科在側(cè)面對這個問題做過研究，如運籌學(xué)、計算機科學(xué)、圖論、數(shù)論、交通工程學(xué)理論、地理信息科學(xué)研究等ｎ…。日前網(wǎng)絡(luò)發(fā)展十分迅速，而網(wǎng)絡(luò)的構(gòu)成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來解決很多網(wǎng)絡(luò)方面的問題。經(jīng)典學(xué)科中的圖論、數(shù)論與計算機科學(xué)以及數(shù)據(jù)結(jié)構(gòu)與算法的有效結(jié)合使得對最優(yōu)路徑算法的研究有了很大進展。國內(nèi)外大量研究機構(gòu)和相關(guān)學(xué)者對最優(yōu)路徑問題的解決進行過深入研究與探討。數(shù)學(xué)家Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ在１９５９年就提出了標號設(shè)定法用于解決路徑問題ｎ“，形成了目前仍被視為經(jīng)典的Ｄｉｊｋｓｔｒａ算法。自從Ｄｉｊｋｓｔｒａ算法面世以后，又歷經(jīng)了很多學(xué)者對該算法的改進與發(fā)展，因此有關(guān)最優(yōu)路徑選擇問題的研究成果不斷涌現(xiàn)，使其求解速度和求解效一６大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文率不斷提高［１５］ｏ解決最優(yōu)路徑問題的其他常用的算法還包括Ｂｅｌｌｍａｎｎ引，Ｆｏｒｄｎ７１，Ｍｏｏｒｅｎ踟等人分別提出的動態(tài)規(guī)劃（ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇ，ＤＰ）算法，又被業(yè)內(nèi)稱為Ｂｅｌｌｍａｎ－ｆｏｕｌ算法，該算法解決網(wǎng)絡(luò)最優(yōu)路徑問題中單源點問題；Ｐａｐｅｎ鍆，Ｐａｌｌｏｔｔｉｎｏ口印等人各自提出的增長圖（ＧｒａＰｈ－Ｇｒｏｗｔｈ）算法；Ｇｌｏｖｅｒ瞻婦等人結(jié)合以上各算法思想的閾值提出了新的算法；Ｈａｒｔ．Ｅｔａｉ［２７］提出了Ａ牛啟發(fā)式搜索算法解決最優(yōu)路徑選擇問題等。最優(yōu)路徑選擇算法在不同的應(yīng)用條件下可以按照不同的方法進行分類晗２｜。如按照時間順序來分類，分為動態(tài)最優(yōu)路徑選擇問題和靜態(tài)最優(yōu)路徑選擇問題；如果按照確定性和非確定性來劃分，分為確定型和隨機型最優(yōu)路徑選擇問題；如果按照網(wǎng)絡(luò)規(guī)模大小劃分，可分為小規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)最優(yōu)路徑選擇問題：如果按照計算方式來劃分，可分為串行和并行最優(yōu)路徑選擇算法。各種不同類別的最優(yōu)路徑選擇算法相互組合可以成為解決不同問題的各種各樣算法。最優(yōu)路徑問題按照是否是單源問題還可以分為單源最優(yōu)路徑選擇問題及全源最優(yōu)路徑選擇問題。其中單源最優(yōu)路徑選擇問題更具有實際應(yīng)用的意義，而且良好的單源路勁問題的算法可為全源最優(yōu)路徑問題提供良好的研究基礎(chǔ)，因此本文在研究最優(yōu)路徑選擇問題的過程巾只考慮單源最優(yōu)路徑選擇問題。目前的研究成果中可用于求解單源最優(yōu)路徑選擇問題的算法層出不窮∞１，早期就發(fā)展起米的的基于限制條件的深度優(yōu)先搜索算法、基于鄰接矩陣和鄰接表的Ｄｉｊｋｓｔｒａ算法、基于有向無環(huán)圖的動態(tài)規(guī)劃算法、最大相關(guān)邊算法、最大相關(guān)點算法、超圖數(shù)據(jù)結(jié)構(gòu)的深度優(yōu)化搜索算法等。針對具體實際環(huán)境可能是網(wǎng)絡(luò)特征不同、應(yīng)用需求不同及具體的軟硬件環(huán)境不同，各種算法在空間和時間復(fù)雜度、易實現(xiàn)程度等方面各有各的特點。雖然這些算法可以解決某一類的實際路勁選擇問題，但是每種算法在其應(yīng)用方面還存在一一定的局限性，許多學(xué)者對這些經(jīng)典的基本的算法進行了改進和發(fā)展瞰１，并得到了良好的效果。在這些研究中陸１，一方面是優(yōu)化實際網(wǎng)絡(luò)特征的動態(tài)結(jié)構(gòu)陸’盯１，在相同的時間復(fù)雜度的基礎(chǔ)上盡量提高算法計算的效率；第二方面是限制網(wǎng)絡(luò)特征，如要求網(wǎng)絡(luò)中的邊的權(quán)值是整數(shù)等等陴１等，用于采用基數(shù)堆等數(shù)據(jù)結(jié)構(gòu)設(shè)計算法；第三方面是采用有損算法的特征，如限制搜索范圍啪瑚１、限定搜索方向口”及限制搜索幾何層次遞歸次數(shù)等等陋３；第四方面是采用拓撲層次編碼路徑視圖嘲，存儲最短路徑部分實例化編碼；第五方面是采用并行計算ｍ’３５１的方法。隨著人工智能領(lǐng)域的發(fā)展，許多學(xué)者和研究機構(gòu)將人工智能的相關(guān)算法與最優(yōu)路徑選擇算法相結(jié)合，形成了一一些新一‘代的最優(yōu)路徑選擇算法啪Ⅻ１，其中就包括蟻群算法，蟻群算法是一種進化算法，模擬了基于種群的進化，在求解最優(yōu)路徑問題方面有很大優(yōu)勢。智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)本課題研究動態(tài)交通最優(yōu)路徑算法，主要研究內(nèi)容如下：（１）建立城市交通模型利用圖論的相關(guān)理論和知識，對圖中的節(jié)點和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。以完整的交通道路網(wǎng)絡(luò)作為模型建立對象，只需要對道路中的相關(guān)數(shù)據(jù)和參數(shù)進行顯示和計算，但在實際的交通道路當中，交通特征是實時變化的，這與交通道路模型密不可分。首先，在同一條道路上不同的車道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。例如：在早晚的上下班的高峰區(qū)段，進出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。其次，不同方向的車道由于具有不同的拓撲關(guān)系，因此交通規(guī)則有可能不同。由于在節(jié)點圖層和路段圖層中分別存儲的點、線圖元是分別獨立的，兩個圖層問不想關(guān)聯(lián)。為建立點線各個元素之間的空間拓撲關(guān)系，使他們構(gòu)成有機整體，需要分別在存儲點線信息的兩張表文件中擴展一定長度的字段，用對象的屬性字段之問的相互聯(lián)系來建立交通網(wǎng)絡(luò)圖的拓撲關(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機整體即他們的拓撲關(guān)系結(jié)構(gòu)圖。（２）Ｄｉｊｋｓｔｒａ最優(yōu)路徑算法改進與道路阻抗分析由于動態(tài)路徑所具有的特點是信息的實時變化，需要在搜索過程中實時檢測道路系統(tǒng)的信息變化，并將變化后的信息納入搜索算法當中。同時，其他路段的交通限制信息也會影響最優(yōu)路徑選定的結(jié)果。因此，在實際情況中需要對Ｄｉｊｋｓｔｒａ算法進行改良和擴展。交通阻抗是指車輛在交通道路上正常行駛時的運行距離、費用、時間、舒適度以及道路暢通情況等素的綜合，即人、車、路、環(huán)境等四個方面因素對交通出行帶來的綜合阻力效應(yīng)。針對某一個具體的交通網(wǎng)絡(luò)，其阻抗函數(shù)所代表的意義根據(jù)實際情況而不同。在城市交通系統(tǒng)中，道路上交通阻抗可以分為兩部分，即路段的交通阻抗和節(jié)點（道路交叉口）的交通阻抗。最優(yōu)路徑選擇問題的主要依據(jù)是計算出各個路段和交叉口的交通阻抗，交通阻抗常用的指標有出行時問、出行距離和路段或節(jié)點需要花費的費用。（３）路徑選擇系統(tǒng)仿真與實現(xiàn)從宏觀來說，制作以路徑優(yōu)化為目的的專用電子地圖時要遵循的原則是：以誘導(dǎo)為中心，以為路徑優(yōu)化算法服務(wù)為目的，忽略與路徑選擇無關(guān)的路網(wǎng)要素，重點描述對路徑選擇相關(guān)的內(nèi)容，以最小的代價來表達及存儲路網(wǎng)。８大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文電子地圖一般是借助專業(yè)的繪制地圖的軟件來完成的。在本文中的電子地圖相關(guān)數(shù)據(jù)信息主要是通過ＭａｐＩｎｆｏ軟件，該軟件將地圖的圖元對象屬性以“表”和“記錄”的方式保存下來，系統(tǒng)使用其信息是利用數(shù)據(jù)庫進行學(xué)習和調(diào)用，從而可以將地圖信息進行動態(tài)地繪制并可以放大、縮小或旋轉(zhuǎn)等操作。論文共分為五章：第一章引言。介紹了本文的研究背景及意義，闡述了國內(nèi)外對智能交通系統(tǒng)研究的基本現(xiàn)狀、最優(yōu)路徑算法研究的的基本概況和存在的問題，并對論文的內(nèi)容組織和章節(jié)安排進行了說明。第二章基礎(chǔ)知識概述。詳細描述了經(jīng)典路徑優(yōu)化算法內(nèi)容，包括Ｆｌｏｙｄ、Ｄｉｊｋｓｔｒａ、ＧＰＳＲ算法等。對圖論做了一定的介紹，包括圖的概念、圖的表示和圖的存儲。第三章最優(yōu)路徑算法。本文在經(jīng)典的Ｄｉｊｋｓｔｒａ算法基礎(chǔ)上進行了改進，并對實際的交通系統(tǒng)中進行了阻抗分析，將交通阻抗融入最優(yōu)路徑選擇中，增加實用性。第四章ＧＩＳ數(shù)據(jù)模型和數(shù)據(jù)庫設(shè)計。包括ＧＩＳ數(shù)據(jù)模的建立、管理與組織。對ＯｒａｃｌｅＳｐａｔｉａｌ進行了介紹，包括空間數(shù)據(jù)向Ｏｒａｃｌｅ的導(dǎo)入和存儲，Ｏｒａｃｌｅ中ＧＩＳ數(shù)據(jù)的訪問和維護。第五章系統(tǒng)仿真與實現(xiàn)。使用ＭａｐＩｎｆｏＰｒｏｆｅｓｓｉｏｎａｌ軟件進行地圖制作，然后利用Ｄｅｌｐｈｉ、ＶｉｓｕａｌＣ＋＋、ＶｉｓｕａｌＢａｓｉｃ等開發(fā)平臺進行二者的集成開發(fā)。第六章結(jié)束語。智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)１基礎(chǔ)知識１．１路徑優(yōu)化算法概述國內(nèi)外的研究機構(gòu)和學(xué)者對不同的路徑優(yōu)化算法進行了研究、分析、比較和論證，比較經(jīng)典的路徑優(yōu)化算法有Ｆｌｏｙｄ算法、Ｄｉｊｋｓｔｍ算法、ＧＰＳＲ算法、遺傳算法、蟻群算法等。實際的交通網(wǎng)絡(luò)是一個復(fù)雜的動態(tài)網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)，它包括各種道路的限制信息以及交通流量的實時信息，然而現(xiàn)有的所有路徑優(yōu)化算法均是對某種抽象的具體網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化計算各種，這就需要對實際的交通網(wǎng)絡(luò)建立模型。路徑優(yōu)化的效率和速度室友所建立模型的準確程度來決定的口８１。日前，國內(nèi)外學(xué)者己經(jīng)有許多傳統(tǒng)的經(jīng)典算法用來解決路徑優(yōu)化問題，但這些算法具有共同的點就是并沒考慮實際出行的具體特點特點，如路況信息、道路質(zhì)量、道路上的車流量等。最短路徑算法求出的僅僅是在空間距離最短的路徑，但在實際應(yīng)用中人們需要的是最優(yōu)路徑，最優(yōu)路徑不一定是距離最短，還要考慮交通阻抗的問題，比如想要求得從Ａ地到Ｂ地的最優(yōu)路徑，這個問題是指在所有從Ａ地到Ｂ地的所有路線當中選擇最優(yōu)的一條，包括最節(jié)省時問，最節(jié)省資源，是駕駛者最舒適，對交通工具的各項消耗最小等。最優(yōu)路徑問題并不是普通意義上的距離最短路徑選擇問題。實際情況下最優(yōu)路徑選擇問題包括兩層含義：首先最優(yōu)路徑是一條可以從Ａ地到達Ｂ地的暢通的路徑；其次這條路徑在所有路徑當中是最佳的。從Ａ地到Ｂ地想要找一條最優(yōu)路徑，應(yīng)是一條的所用時間最短、駕駛者最舒適、道路上的車輛數(shù)量較少啪１，或?qū)煌ㄜ囕v的損耗最硝、。１．１．１Ｆｌｏｙｄ算法Ｆｌｏｙｄ算法Ⅲ“”是由Ｆｌｏｙｄ在１９６２年提出的。將圖的節(jié)點和邊的信息計算利用矩陣計算來完成，通過一個圖的權(quán)值矩陣中求出交通網(wǎng)絡(luò)中任意兩點之問的最短路徑?；舅枷耄罕热缜髨D中兩節(jié)點Ｖｉ到ｖｊ的之問的最短路徑問題。如果ｖｉ，ｖｊ之間有邊存在，即在ｖｉ與ｖｊ之間隨意選取一條長度為ａ的路徑，該路徑只是路徑選擇的初始值，一般不是最短路徑，需要利用最短路徑算法進行迭代計算和比較。首先若ｖｉ到Ｖｊ之間存在點ｖ０存在路徑（ｖｉ，ｖ０，叼），則比較（ｖｉ，ｖｊ）與（ｖｉ，ｖ０，ｖｊ）的路徑的長度，取得從ｖｉ到ｖｊ的結(jié)點數(shù)小于或等于０的最短路徑。如果在路徑上再增添一結(jié)點ｖｌ，則路徑變?yōu)椋ǎ觯椋觯?，ｖｊ），如果其中子路徑（ｖｉ，ｖ１）與（ｖｌ，ｖｊ）分別是當前找到的結(jié)點數(shù)不大于０的最短路徑。那么（ｖｉ，ｖｌ，ｖｊ）這條路徑就是從ｖｉ到ｖｊ的中間結(jié)點數(shù)大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文目小于或等于１的一條最短路徑。將它和最初選取的從ｖｉ到ｖｊ中間那條路徑進行比較，從中選出中間結(jié)點個數(shù)小于或等于ｌ的最短路徑，利用此方法，再次增加一個結(jié)點進行迭代計算，繼續(xù)試探。依次類推，經(jīng)過多次迭代計算后，最后求得的從ｖｉ到ｖｊ的路徑一定是在距離上的最短路徑。Ｆ１０ｙｄ算法相當于窮舉型算法，其時問復(fù)雜度為Ｏ（１１２）。在計算最短路徑過程中，用鄰接矩陣Ｇ來表示圖，如果從Ｖｉ到Ｖｊ有路徑可以到達，則Ｇ［ｉ，ｊ】＝ｄ，路徑長度用ｄ表示；否則Ｇ［ｉ，ｊ】＿０。用矩陣Ｄ用來表示圖中所有插入點的信息，Ｄ［ｉ，ｊ】表示從點ｉ到點ｊ需要插入的節(jié)點，初始化Ｄ［ｉ，ｊ一。把Ｄ中各個插入點信息存儲在圖中，比較插入點后的路徑距離的變化情況，Ｇ［ｉ，ｊ】＝ｍｉｎ（６［ｉ，ｊ】，６［ｉ，ｋ】＋Ｇ【Ｉ【，Ｊ１），如果Ｇ［ｉ，ｊ】的值變小，則Ｄ［ｉ，ｊ１－ｋ。比如，要尋找從Ｖ５到Ｖ１的路徑。根據(jù)Ｄ，假如Ｄ（５，１）＝３則說明從Ｖ５到Ｖ１經(jīng)過Ｖ３，路徑為｛ｖ５，Ｖ３，Ｖ１ｌ，如果Ｄ（５，３）＿３，說明Ｖ５與Ｖ３直接相連，如果Ｄ（３，１）＝ｌ，說明Ｖ３與Ｖ１直接相連。Ｆｌｏｙｄ算法是一種動態(tài)規(guī)劃算法，由于是窮舉法進行計算，因此對于稠密圖效果較好。此算法思路簡單，該算法對于稠密圖來說，效率要高于經(jīng)典的Ｄ獨ｓｔｒａ算法。但缺點是時間復(fù)雜度較高，不適合大規(guī)模數(shù)據(jù)的計算，耗時較長。１．１．２Ｄ西ｋｓｔｍ算法Ｄｉｊｋｓｔｒａ算法Ｈ厶例由荷蘭數(shù)學(xué)家ＥｄＳｇｅｒＷｙｂｃＤ．ｊｋｓｔ豫在１９５９年提出來的，是一種單源最短路算法適用于非負權(quán)值網(wǎng)絡(luò)的計算，是目前在求解最短路徑問題較為完備且應(yīng)用廣泛的算法之一，可以計算出圖中從指定結(jié)點到圖中其他任意節(jié)點之問的最短路徑。在一個圖Ｇ中，Ｄ嵇ｋｇｃｍ算法不但可以給出兩指定結(jié)點之間的一條具有權(quán)值最下送的路徑，且還可找出從指定點到圖Ｇ中所有結(jié)點的最短路徑。Ｄ蝎ｓ咖算法的缺點就是當網(wǎng)絡(luò)中結(jié)點數(shù)量較大時，就會增加算法的復(fù)雜度，降低了效率。該算法通過圖中的每個節(jié)點ｖ建立額外的信息數(shù)組，存儲從其他任意節(jié)點Ｓ到ｖ的最短路徑。在初始狀態(tài)下，原始節(jié)點Ｓ的路徑長度值被賦為０即ｄｉｓ］的值為０，同時假設(shè)其他所有節(jié)點到該節(jié)點的路徑長度為無窮大，用無窮大長度的路徑表示任何其他節(jié)點到該結(jié)點的路徑是未知的。如果存在從Ｓ到ｖ的路徑，那么當蘇算法結(jié)束時ｄＨ中儲存的信息是Ｓ到ｖ的距離最短路徑；如果從Ｓ到ｖ的路徑不存在，則ｄ【Ｖ】中儲存信息是無窮大。Ｄ．ｊｓｔｍ算法的操作對邊進行了拓展：如果從Ｕ到ｖ的路徑是存在的，將邊（ｕ，ｖ）添加到（ｓ，ｖ）尾部，則這條新的路徑的長度為ｄＭ＋ｗ（ｕ，ｖ）。如果這條路徑的長度比已知的路徑長度ｄ【ｖ】的值小，我們可以用新的路徑來代替原有路徑。這種拓展邊的迭代運算一直進行，一直運行到所有的ｄＭ都代表從Ｓ到ｖ最短路徑為止。算法需要維護兩個結(jié)點集Ｑ和Ｐ，集合Ｐ保留了我們通過迭代運算所得的所有ｄＮ的最短路徑的智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)值結(jié)點，而集合Ｑ則保留其他剩下的所有結(jié)點。集合Ｐ初始狀態(tài)為空，而后每一步都有一個結(jié)點從集合Ｑ中轉(zhuǎn)移到集合Ｐ中，并相應(yīng)的在Ｑ中刪除該節(jié)點信息。１．１．３ＧＰＳＲ算法ＧＰＳＲ路由算法的思路是利用地理位置信息進行最優(yōu)路徑選擇，該算法需要通過貪婪轉(zhuǎn)發(fā)算法來建立與其他信息之間的關(guān)聯(lián)和路由。當節(jié)點ｓ向Ｄ轉(zhuǎn)發(fā)數(shù)據(jù)分組時，他首先找到與相鄰節(jié)點中距離最小的那個節(jié)點，然后將數(shù)據(jù)分組轉(zhuǎn)發(fā)給那個節(jié)點，將距離最小的那個節(jié)點稱為跳點，然后將Ｓ的數(shù)據(jù)傳送給這個跳點，該過程需要一直迭代計算，直到分組數(shù)據(jù)全部到達節(jié)點Ｄ。利用歐氏距離計算距離方法計算距離該節(jié)點最近的相鄰節(jié)點，但如果數(shù)據(jù)傳輸?shù)哪骋还?jié)點是發(fā)現(xiàn)沒有找到下一個距離最小的節(jié)點使得數(shù)據(jù)傳送的目標節(jié)點時，導(dǎo)致了數(shù)據(jù)傳輸?shù)氖?。在發(fā)生生無法傳送數(shù)據(jù)時，節(jié)點能夠探測到周圍的空洞，并利用右手法則沿著空洞周圍的節(jié)點傳輸數(shù)據(jù)來解決這類問題。該方法的優(yōu)點在于米面了在節(jié)點信息中存儲建立和維護路由表信息，只需要利用相鄰節(jié)點進行路徑選取即可進行，幾乎是不需要任何協(xié)議輔助；并且利用歐氏距離最小的方法進行路由，數(shù)據(jù)傳輸?shù)难訒r最??；并能夠保證只要網(wǎng)絡(luò)路徑不被破壞，數(shù)據(jù)一定能到傳送到目標節(jié)點中去。但該算法存在這一定的缺點，當網(wǎng)絡(luò)中的某節(jié)點與源點集中在兩個區(qū)域時，由于通信的不平衡能夠?qū)е虏糠止?jié)點無效，從而是網(wǎng)絡(luò)的連通性遭到破壞；另一方面是該方法需要ＧＰＳ定位系統(tǒng)的輔助來計算幾點的位置信息。ＧＰＳＲ中貪婪轉(zhuǎn)發(fā)算法能夠正常轉(zhuǎn)發(fā)數(shù)據(jù)的前提是：目的結(jié)點的位置都包含于每個數(shù)據(jù)分組中，每個結(jié)點都有鄰居結(jié)點列表信息以及鄰居結(jié)點和本結(jié)點的位置信息。在實際的路線選取過程中，我們將路口與上述的結(jié)點對用。在電子地圖中，每個路口都有坐標位置和列表信息，那么在算法程序中我們首先要做的是讓每個結(jié)點都包含一條鄰居結(jié)點鏈表，并將結(jié)點號與位置信息關(guān)聯(lián)起來。１．２圖論簡介圖論（ＧｒａｐｈＴｈｅｏｒｙ）是組合數(shù)學(xué)的一個分支，它源于瑞士數(shù)學(xué)家歐拉（Ｅｕｌｃｒ）１７３６年對于著名的哥尼斯堡七橋問題的解決，從而使歐拉成為了圖論的創(chuàng)始人。圖論是數(shù)學(xué)學(xué)科當中比較年輕的一個分支。在圖論被提出后的兩百年中，圖論的發(fā)展相對緩慢，但自從圖論與大量的實際問題相結(jié)合，在物理學(xué)、化學(xué)、信息論、運籌學(xué)、計算機科學(xué)、控制論、社會科學(xué)，經(jīng)濟管理等各種學(xué)科中找到了更廣泛的應(yīng)用，使圖論在近幾十年來得到了快速的的發(fā)展。目前在圖論領(lǐng)域中形成了兩個不同的方向：抽象圖論和最優(yōu)化圖大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文論。前者主要研究圖的性質(zhì)，后者主要討論與圖有關(guān)的優(yōu)化問題。最優(yōu)化圖論既可以算作圖論中的一個研究方向，也可以看作運籌學(xué)中最優(yōu)化理論的組成部分【“”。圖論中的圖是由若干節(jié)點以及兩節(jié)點之間的連線所構(gòu)成的圖形，圖論的研究對象是圖，這種圖形不考慮點的大小、形狀和邊的形狀、長度、大小以及邊與邊的角度等幾何問題，而主要表達的是點點之間通過線的連通關(guān)系，通?？梢杂脕砻枋瞿承┦挛镏g的相互關(guān)系，即用點來代表事件發(fā)生，用連接兩點的邊表示兩個事件之間的關(guān)系。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。１．２．１圖的概念無向圖是指有序三元組（ｙ，Ｅ，沙）中邊沒有方向，其中集合ｙ被稱為結(jié)點集，ｙ中的元素稱為結(jié)點：集合Ｅ被稱為邊集，Ｅ中的元素被稱為邊；而函數(shù)∥是邊集Ｅ到無序結(jié)點對兒所構(gòu)成的集合的一個映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。如果Ｐ是一條邊，“，＇，兩個結(jié)點，且滿足∥（助＝ｚｎ，，那么就可稱為ｅ連接：并且稱Ⅳ，ｙ為Ｅ的端點。每條邊與邊兩端的節(jié)點是相互關(guān)聯(lián)的因此稱為相互關(guān)聯(lián)，與同一條邊相關(guān)聯(lián)的節(jié)點或者與同一個節(jié)點相互關(guān)聯(lián)的邊稱為相鄰的節(jié)點或者相鄰的邊，具有相同兩個節(jié)點的邊稱為重合邊或者是平行邊，兩個節(jié)點相同的邊組成環(huán)，簡單圖就是沒有環(huán)和重邊的圖。每個結(jié)點度數(shù)相同的簡單圖稱為正則圖，最大度與最小度恰好相差１的簡單圖被稱為幾乎正則圖。圖的結(jié)點的個數(shù)稱為圖的階。１．２．２圖的表示由點集合礦和點與點之間的連線的集合Ｅ所組成的集合對（礦，Ｅ）可以構(gòu)成圖，用Ｇ（Ｖ，目來表示。圖Ｇ（Ｖ，毋由其結(jié)點與邊之間的關(guān)系確定，且是唯一的。也由它的結(jié)點對兒之間的鄰接關(guān)系唯一確定。ｙ中的元素為結(jié)點，Ｅ中的元素為邊。節(jié)點集合ｙ與邊集合Ｅ均為有限的圖稱為有限圖。圖２．１圖的結(jié)構(gòu)Ｆｉｇ．２．１Ｔｈｅｓｔｒｕｃｔｕｒｅｏｆｇｒａｐｈ智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)在圖２．１中，節(jié)點集合Ｖ＝｛彳，Ｂ，Ｃ，Ｄ｝，包括四個結(jié)點，邊集合為Ｅ＝｛ｑ，ｅ２，ｅ３，ｅ４，島，ｅ６，ｅ７，ｅｓ｝，包括８條邊。連接兩個節(jié)點間的邊可能不唯一，如ｑ，屹同時連接Ａ和Ｂ。連接同一節(jié)點的邊稱為自圈，如％。Ｇ的結(jié)點和邊交替組成的有限序列為：Ｗ＝ｖｏｅｌｖｌｅ２ｖ２ｅ３…％唯（２．１）如果葉－ｌ，Ｋ恰好是ｑ的端點（１≤ｆ≤ｋ），我們稱礦是一條從ｖ０至＝Ｕｖｋ的途徑。ｖｏ和唯稱為形的起點和終點，礦中包含的邊的數(shù)日ｋ被稱為形的長度，而起點和終點之間的結(jié)點稱為路徑形的內(nèi)部結(jié)點。對于簡單圖來說，兩點之問的邊最多只有一條，因此可以把形簡單寫成圖Ｇ的結(jié)點的序列：Ｗ＝ＶｏＶＩＶ２…唯（２．２）這里只要求Ｅ小Ｍ是相鄰的。序列信息中結(jié)點不能重復(fù)出現(xiàn)的路徑被稱為路。顯然，如果在Ｇ中存在以ｖ０為起點，心為終點的途徑，則一定存在分別以ｖ０和唯為起點和終點的路。當％＝唯且長度為正值的途徑稱為閉途徑。如果只有相同的起點和終點，而其他結(jié)點都不相同，這樣的閉途徑被稱為圈，或者回路。對于圈來說，任何一點都可以看作是圈的起點或終點，圈通過每個結(jié)點都只有一次機會?？紤]Ｇ中的某一對結(jié)點（“，ｖ），如果Ｇ中存在一條連接ｗ的路，我們就說結(jié)點“，ｖ是連通的。結(jié)點的連通性質(zhì)在圖Ｇ的結(jié)點集合ｙ上定義了一個等價的關(guān)系。它具有對稱性和傳遞性，因此可以把結(jié)點集合ｙ劃分為Ｗ個等價類，即：Ｖ＝ＫＵＫＵ…Ｕ圪（２．３）圖的這種節(jié)點和邊相互關(guān)聯(lián)關(guān)系均可以用數(shù)學(xué)中的矩陣來進行描述，包括圖Ｇ的關(guān)聯(lián)矩陣，鄰接矩陣和回路矩陣等等。一個圖的矩陣表示不僅僅是對圖的一種表示方法，更重要的是可以通過對這些矩陣的分析與討論得到有關(guān)圖的若干個性質(zhì)，而且對圖的‘些運算和操作也可以轉(zhuǎn)化為對矩陣的計算。設(shè)Ｇ是一個階數(shù)為ｐ，邊數(shù)為ｇ的圖，其中結(jié)點集合Ｖ（Ｇ）＝“，ｖ２，…，ｖ，＞，邊集合Ｅ（Ｇ）＝｛Ｐｌ，ｅ２，…，島）。圖Ｇ的鄰接矩陣定義為Ｉ／Ｘ／＇／的矩陣Ａ＝【ａ／／】，其中ａｏ．＝｛１０瓷器囂泣４，２１萁他情況旺一’圖Ｇ的關(guān)聯(lián)矩陣定義為大?。睿颍木仃嚕拢剑郏簦铩?，其中大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文％＝器慧組５，對于鄰接矩陣和關(guān)聯(lián)矩陣來說，有些很重要的性質(zhì)。矩陣首先要依賴于結(jié)點和邊而存在。在任何情況下，鄰接矩陣都是一個主對角線為全０的、大小為ｒ／ｘ／’的對稱矩陣。鄰接矩陣第ｉ行或者是第ｉ列中數(shù)值１的個數(shù)是結(jié)點ｕ的度。圖用矩陣表示后，對圖論的分析和討論就可以通過對矩陣的圖譜的分析討論來發(fā)現(xiàn)圖的主要性質(zhì)和結(jié)構(gòu)。通常在圖像分割中，對連接兩結(jié)點的邊賦予一定的權(quán)值來表示結(jié)點之間的相似程度，用與鄰接矩陣或關(guān)聯(lián)矩陣相似的矩陣形式來表示加權(quán)矩陣，稱為相似度矩陣Ｗ＝【％】：％＝心鬣篙’泣６，其中Ｊ。代表結(jié)點之間的相似程度的數(shù)值。如果用相似度矩陣形的行列式ｄｅｔＷ（Ｅ）表示圖Ｇ，記為ｄｅｔＧ。圖的特征多項式記為Ｐ（Ｇ；Ａ）：Ｐ（Ｇ；Ａ）＝卜１）’ｄｅｔ［Ｗ（Ｇ）－Ｉ］＝∑ｃ，２ｐ一（２．７）形的特征值也被稱為圖Ｇ的特征值，圖Ｇ的所有特征值稱為Ｇ的譜，記為ＳｐｅｃＧ。因此，使用圖Ｇ的譜解決聚類問題的方法又被稱為譜方法。近年來，譜方法在應(yīng)用圖論的圖像分割方法中為學(xué)者所研究和應(yīng)用，也得到的廣泛的發(fā)展與應(yīng)用。１．２．３圖的存儲（１）鄰接表表結(jié)點頭結(jié)點匝丑三圈Ｅ圈圖２．２鄰接表結(jié)構(gòu)Ｆｉｇ．２．２Ｔｈｅｓｔｒｕｃｔｕｒｅｏｆａｄｊａｃｅｎｃｙｌｉｓｔ鄰接表以一種以鏈式存儲結(jié)構(gòu)所構(gòu)成的圖。在鄰接表中，圖中的每個節(jié)點都會有一個單鏈表與之對應(yīng)，第，個單鏈表中的結(jié)點數(shù)據(jù)表示依附于結(jié)點ｕ。三個域構(gòu)成了每個節(jié)點，，其中結(jié)點的鄰接點域的數(shù)值表示與結(jié)點－相鄰節(jié)點在圖中的具體位置，結(jié)點的鏈域?qū)⒅甘鞠乱粭l邊的結(jié)點，結(jié)點數(shù)據(jù)域存儲的是圖中邊的信息，如權(quán)值、方向等。每個鏈表都會有一個表頭結(jié)點與之對應(yīng)，在表頭結(jié)點中，設(shè)有存儲結(jié)點ｑ的各個域及與該智能交通系統(tǒng)中晟優(yōu)路徑選擇的設(shè)計與實現(xiàn)信息有關(guān)的相關(guān)數(shù)據(jù)域。如圖２．２所示。這些表頭結(jié)點存儲數(shù)據(jù)的形式通常是順序存儲的，這樣存儲方式便于隨即訪問任何一個節(jié)點的鏈表信息。若無向圖中有ｅ條邊和有刀個結(jié)點構(gòu)成，則它的鄰接表需要有２ｅ個表結(jié)點和刀個頭結(jié)點與之對應(yīng)。顯然，在邊是稀疏ｆＰ＜＜＿ｎ（ｎ－１）１的情況下，用鄰接表表示圖比使用鄰＼ｚ／接矩陣表示更節(jié)省存儲空問。在有向圖中，第ｆ?zhèn)€鏈表中的結(jié)點個數(shù)只是結(jié)點ｖ。的出度，為求入度，必須遍歷整個鄰接表。而在無向圖的鄰接表中，結(jié)點Ｍ的度恰好為第ｉ個鏈表中的結(jié)點數(shù)。在所有鏈表中其鄰接點域的值為ｆ的結(jié)點個數(shù)是結(jié)點Ｅ的入度。有時，可以建立一個有向圖的逆鄰接表，建立一個鏈接以％為頭的弧的表對每個結(jié)點Ｂ，為了便于確定結(jié)點的入度或以結(jié)點Ｈ為頭的弧。（２）十字鏈表十字鏈表針對有向圖的另一種存儲結(jié)構(gòu)。可以看成是一種新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。在十字鏈表中，每一條邊都有一個節(jié)點與之對應(yīng)，每一個節(jié)點也有一個節(jié)點與之對應(yīng)。１．３本章小結(jié)本章對最優(yōu)路徑算法和圖論的相關(guān)理論知識進行了簡單概述。對幾個經(jīng)典的最優(yōu)路徑選擇算法進行了介紹，如Ｆｌｏｙｄ算法、Ｄｉｊｋｓｔｍ算法、ＧＰＳＲ算法，并分析了他們的優(yōu)點和不足。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運籌學(xué)、計算機理論、控制論、社會科學(xué)等不同領(lǐng)域和學(xué)科的結(jié)合方面。介紹了圖的概念、圖的構(gòu)成，圖的表示方法和圖的存儲方法。１６—大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文２最優(yōu)路徑２．１城市交通模型建立在我國經(jīng)濟快速發(fā)展的環(huán)境下，各個大城市及其附近地區(qū)都不斷呈現(xiàn)出新的產(chǎn)業(yè)布局，并伴隨著人口的增長和大量流動的重新分布，這些問題都對中國的城市建設(shè)和發(fā)展提出了更高的要求和新的挑戰(zhàn)，同時也提供了新的發(fā)展機遇。經(jīng)歷了多年以經(jīng)濟規(guī)模數(shù)據(jù)為衡量地區(qū)發(fā)展標準的模式之后，人們開始思考從可持續(xù)發(fā)展的角度來看待經(jīng)濟發(fā)展和生活質(zhì)量的關(guān)系。交通建設(shè)一直都是支撐著經(jīng)濟發(fā)展、產(chǎn)業(yè)進步和居民生活的有力支柱，所以在實現(xiàn)經(jīng)濟發(fā)展模式轉(zhuǎn)變的過程中，改革交通發(fā)展政策法規(guī)、增強交通管理能力、提高執(zhí)行政策的有效性、并保證這一過程的民主化和科學(xué)化Ｈ６—７’，是交通建設(shè)發(fā)展的主要目標和方向。城市交通的規(guī)劃過程，是實現(xiàn)交通發(fā)展的基本過程，而精確的有效的交通需求模型是規(guī)劃過程不可或缺的重要環(huán)節(jié)。依靠地理信息的特征可以客觀的認識交通網(wǎng)絡(luò)工作機理，而不是依靠分層的要素進行認識，交通網(wǎng)絡(luò)的數(shù)據(jù)模型可以幫助我們認識交通系統(tǒng)的構(gòu)成。傳統(tǒng)的交通網(wǎng)絡(luò)系統(tǒng)模型當中只是一個簡單的二維模型，模型中只包含了節(jié)點和邊等簡單信息，而實際的交通網(wǎng)絡(luò)要比這復(fù)雜得多，需要完成的恢復(fù)實際交通系統(tǒng)的各項特征ｍ１因此，必須對實際的交通網(wǎng)絡(luò)有一定深入的認識和了解，然后建立對應(yīng)的數(shù)據(jù)模型，交通網(wǎng)絡(luò)應(yīng)該包含四個基本要素，分別是交通區(qū)域，交通特征，事件和事件點。交通特征是交通系統(tǒng)具有的內(nèi)在屬性。交通網(wǎng)絡(luò)的地理信息特征主要由節(jié)點和邊線兩部分要素構(gòu)成。節(jié)點的情況相對復(fù)雜，需要考慮到兩條邊之間的交點和多條邊之間的交點，邊線是連接兩個節(jié)點之問的關(guān)聯(lián)信息，是抽象交通路線而成。一般情況下，在交通屬性數(shù)據(jù)中存儲的交通道路名稱是定義交通特征集合的重要標準。交通特征標識與區(qū)域標識聯(lián)合形成的復(fù)合標識稱為交通特征，該交通特征提供了整體的惟一標識。存儲在節(jié)點中的事件包括物理特性、交通特征的屬性、偶然事件、應(yīng)急相應(yīng)時間等。而事件又可以分為點事件和線事件。將交通特征屬性加入的事件的范疇便于管理，便于描述可能發(fā)生的分段變化，例如分段限速等。事件點指點事件發(fā)生的具體位置和時間，對于線事件來說，事件點是線事件的起始和終止位置。交通網(wǎng)絡(luò)構(gòu)成要素中具有地理特征的同時，還具有交通流的特征，具有隨空間變化和隨事件變化的特性。交通流在交通網(wǎng)絡(luò)上的不但隨位置的不同而不同，，而且在相同位置也會隨著不同時間的不同而變得不同。因此在對交通網(wǎng)絡(luò)建立模型時需要考慮到實智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)際情況下交通流的特點。最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運輸效率。因此，應(yīng)當首先考慮交通流的特征。一般地，交通網(wǎng)絡(luò)有如下特點：（１）線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建?？梢砸揽繄D論的相關(guān)理論和知識；（２）網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個負載的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜：（３）分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時間差異性；（４）動態(tài)性特點，交通網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時間的變化而變化，失意哥時變系統(tǒng)：（５）車輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時間和行駛路線等是他的一個最顯著特征。以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進的方法使得道路的車道信息加入到節(jié)點和邊的信息中。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當中經(jīng)常和車道關(guān)聯(lián)密切。第一，在同一一條道路上不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。２．１．１道路節(jié)點模型可以將交通網(wǎng)絡(luò)抽象成一個有向圖，圖中的邊帶有一定的權(quán)值，但這個抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。在實際情況中人民出行是從一個地方到另一個地方，這種不能簡單的歸結(jié)在圖中從一個節(jié)點到另一個節(jié)點的轉(zhuǎn)移，實際情況的交通網(wǎng)絡(luò)運行是非常復(fù)雜的，所以不能簡單的把某一個具體的地方當成是圖中的某個節(jié)點，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。交通地址的交叉口所抽象的節(jié)點和將具體地址被抽象成圖中的節(jié)點是不相等價的，需要考慮實際情況，因此交通節(jié)點的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點的阻抗值可以視為零。具體情況可分為以下幾種：（１）地名節(jié)點和交通線路之間的距離很近的情況（如圖３．１ａ）彳、曰為分別表示某一個交通線的兩個端點，ｃ點表示ＡＢ沿線中距離沿線距離較近的某一地點，從ｃ點到交通線ＡＢ的所需要的時間可以忽略，這是可以在ＡＢ邊上加入一點ｃ’，連接ＣＣ’，使得ＣＣ‘垂直ＡＢ，此時可以將ｃ’作為表示地名的節(jié)點，這該條交通線可以抽象為兩條邊的組合分別為ＡＣ和ｃ’曰，將ｃ點排除在交通網(wǎng)絡(luò)之外。這樣大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文做的目的是降低網(wǎng)絡(luò)的負載度，有保證交通網(wǎng)絡(luò)模型的可用性，保證了最優(yōu)路徑選擇的準確性。（２）地名節(jié)點距離交通線很遠（如圖３．１ｂ）如地點節(jié)點ｃ和ＡＢ之間的距離很遠，則按照實際情況把ＣＣ’抽象為交通網(wǎng)絡(luò)的一條邊，把ｃ’抽象為交通網(wǎng)絡(luò)中的交通節(jié)點，而不能忽略不計，則ｃ點到節(jié)點彳點或曰點的實際路徑可以表示為兩條路徑的組合。（３）地名節(jié)點距離交通節(jié)點較近（如圖３．１ｅ）如地點節(jié)點ｃ交通節(jié)點彳、口巾的某一個節(jié)點很近，則將Ｃ點與距離他很近的地點節(jié)點合并為一個節(jié)點進行考慮，屬于這兩個節(jié)點的屬性信息也相應(yīng)的合并。經(jīng)過抽象后組成的交通網(wǎng)絡(luò)圖如圖３．１ｄ所示。Ｃ●８Ｃ。）Ａ（ｃ）（ｄ）圖３．１交通網(wǎng)絡(luò)節(jié)點模型Ｆｉｇ．３．１Ｔｈｅｍｏｄｅｌｏｆｔｒａｎｓｐｏｒｔｎｅｔｗｏｒｋｎｏｄｅ２．１．２交叉口和道路模型將道路的數(shù)據(jù)模型抽象為一條線，因此選擇道路中問的中心線表示道路數(shù)據(jù)模型，這種建模方法不能很好的描述交通道路的屬性信息，丟失很多信息量。實際生活中的道路不能簡單的抽象為一條直線，因為有些道路存在很多車道，每個車道的屬性信息不盡相同，多車道的交通道路屬性信息較為復(fù)雜。在ＧＰＳ進行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車道信息密切相關(guān)。首先，同一條交通道路的不同車道之問有這不同的屬一１９智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)性信息，包括行駛方向，交通規(guī)則，交通量變化，以及與其他道路的連接關(guān)系等；其次，同一條道路的不同方向車道與相鄰接車道往往有著不同的拓撲關(guān)系；再次，交通網(wǎng)絡(luò)中有些車道限制向左轉(zhuǎn)或向右轉(zhuǎn)，他們的屬性信息千差萬別。此外，任何車道可以在任意在一點開始或者結(jié)束。因此，把車道信息作為基本建模的要素構(gòu)建交通網(wǎng)絡(luò)建模，。對于復(fù)雜的道路信息分多情情況討論：（１）對于同向并行的車道來說，不同車道間的交通特性大致相同，在這種交通特性基本相同的情況下，可以把多個車道合并成一個車道進行考慮，目的是減小模型的復(fù)雜度，如圖３．２所示。攀鏊然羹蠹建鬃黌ｉ黍簍鬻鬻ｉ；霧ｉ攀ｌ鋈攀鎏糞ｉｉ鬻囊鬻薹霪蒸蒸蒸囊霧纛曩蒸藏霾纂鬻ｉｉｉｉ｝；Ｉ｜｜ＩＩ｜｜｜｜鬻薹ｉ：ｊｉｉｉｉｊｉｉ鎏攀簍鬻攀攀攀：ｉ鬻纂攀ｉ菱鬻蒸霾霧霧霧熏囊薰｜｛｜｜囊囊囊黍纛簍纛震籬ｉｉ；ｉ黍鍪攀戮羹蘩鬻鬢ｉ藜；｜｜ｉｉｉｉｉ；夔攀ｉ黍；攀蒸繁菱糞鬻黍ｉｉ圖３．２同向車道示意圖Ｆｉｇ．３．２Ｔｈｅｄｉａｇｒａｍｏｆｔｈｅｓ［１ｌｅｄｉｒｅｃｔｉｏｎｌａｎｅ（２）每一條道路都有起止點和終止點，而起點或終點一般都是交通網(wǎng)絡(luò)巾的交叉口，可以將交叉口抽象為網(wǎng)絡(luò)中的一個節(jié)點，但道路和交叉口的連接比較復(fù)雜，需要考慮這種情況。普通的道路交叉口如圖３．３所示。這種交叉口的各個車道都與交叉口的節(jié)點相互連接。圖３．３普通交叉路口示意圖Ｆｉｇ．３．３Ｔｈｅｄｉａｇｒａｍｏｆｏｒｄｉｎａｒｙｉｎｔｅｒｓｅｃｔｉｏｎ大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文如圖３．４所示的車道分為兩部分，允許左轉(zhuǎn)和不允許左轉(zhuǎn)的車道，因此允許左轉(zhuǎn)的車道在較差口出將會存在節(jié)點，不允許左轉(zhuǎn)的車道模型在交叉口處不存在及誒但。圖３．４車道限制左轉(zhuǎn)示意圖Ｆｉｇ．３．４ＴｈｅｄｉａｇｒａｍｏｆＬａｎｅｗｈｉｃｈｈａｓｒｅｓｔｒｉｃｔｉｏｎｓｏｆｔｕｒｎｎｉｎｇｌｅｆｔ２．２交通模型數(shù)據(jù)存儲２．２．１數(shù)據(jù)預(yù)處理在實際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進行優(yōu)化和預(yù)處理，建立相應(yīng)的拓撲關(guān)系圖譜。矢量圖形的預(yù)處理的一般包括㈨：（１）對原始道路圖像進行拓撲關(guān)系檢查并進行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來的道路拆分成多條道路的集合：（２）為每一條剪斷后的道路建立拓撲關(guān)系，并定義其屬性特征，如道路名稱、道路長度、交通流等特征；（３）將地圖經(jīng)過上述處理之后生成拓撲文件。２．２．２交通路徑模型建立與數(shù)據(jù)存儲（１）交通路徑模型的建立最短路徑選擇的前提是對交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對原始的交通道路進行預(yù)處理之后就可以確定道路之間的拓撲關(guān)系，進而可以建立以道路拓撲關(guān)系為基準的交通系統(tǒng)模型，拓撲關(guān)系中包括線性實體之間的模型，線性實體與節(jié)點之問的模型，節(jié)點與節(jié)點之間的模型，以及他們的連通性等嘞１。使用圖中的節(jié)點表示交通系統(tǒng)的的較差路徑，道路交叉ＩＺｌ即是圖中的節(jié)點，兩個節(jié)點之間的道路在圖中用弧表示，就是圖的智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)邊，路段的長度以及消耗時問等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點圖層，一部分是交通道路圖層。節(jié)點圖層表示交通交叉口或者道路的起始點或終止點，用點對象來表示，路段圖層存儲這連接各個節(jié)點的交通路徑以及他們的屬性信息，用線對象表示嘲１。在兩圖層中分別存儲的節(jié)點信息和路段信息分別是獨立的，下一步就是建立兩個圖層之問的拓撲聯(lián)系，使得兩個圖層構(gòu)成有機整體，形成交通路徑系統(tǒng)的完整性，需要用兩個圖層所對應(yīng)的兩張表中的文件擴展出一定的字段，用對象的屬性信息來代表兩個圖層之間的拓撲關(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓撲關(guān)系結(jié)構(gòu)圖。表３．１為節(jié)點的屬性數(shù)據(jù)結(jié)構(gòu)。交通路徑的限制信息是交通導(dǎo)航中需要終點考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實際的道路中交通限制信息十分復(fù)雜，而且隨時發(fā)生變化。本文考慮的交通限制信息只考慮了禁止通行的信息。如果某條道路出現(xiàn)禁止通行的限制信息，用節(jié)點的交通限制信息來表示。如圖３．５所示，如果車輛從結(jié)點Ｉ往結(jié)點２行駛時，在結(jié)點２處的限制信息為禁止向右轉(zhuǎn)，這表示如果想要從節(jié)點１到達節(jié)點４就必須經(jīng)過節(jié)點２。所以，對于該禁行標志就可以加入一個點對（１，４）來表示２處禁止通行，用４來表示禁止通行的終止點節(jié)點，用１表示禁止通行的起始點節(jié)點序號。實際上，節(jié)點２處的禁止通信信息可以不只有一個，可以有多個，例如從結(jié)點向結(jié)點２行駛時，該處的禁止通行信息為禁止左轉(zhuǎn)，于是點對（５，３）也要加入禁止通行信息。這樣，節(jié)點２出的所有禁止通行信息成為該處禁止通行的標識嘞，。表３．１節(jié)點屬性的數(shù)據(jù)結(jié)構(gòu)（ｐｌａｃｅ．ｔａｂ）７ｒ｛Ｉｂ．３．１１１圮ａｔｔｒｉｂｕｔｅｄａｔａｓ仃Ｉ】ｃｔｌⅡ℃ｏｆｔｈｅｎｏｄｅ路段的屬性數(shù)據(jù)結(jié)構(gòu)如表３．２所示。大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文表３．２路段屬性數(shù)據(jù)結(jié)構(gòu)（ｓｔｅｃｔｓ．ｔａｂ）Ｔａｂ．３．２ＴｈｅａｔｔｎｑＤｕｔｅｄａｔａｓｔｒｕｃｔｕｒｅｏｆｔｈｅｓｔｒｅｅｔ圖３．５交通禁行信息示意圖Ｆｉｇ．３．５Ｔｈｅｄｉａｇｒａｍｏｆｌｒａｆｆｉｃｆｏｒｂｉｄｄｅｎｉｎｆｏｒｍａｔｉｏｎ（２）數(shù)據(jù)存儲一般地，在計算機中大多采用利用鄰接表和鄰接矩陣的方法存儲有向圖。順序表Ｚｏ，巧，…匕一。的形式在鄰接局長呢中存儲圖中所有的結(jié)點，以ｍ×ｌｒｎ大小的矩陣存儲圖的邊。使用鄰接矩陣來表示圖的存儲淺顯易懂，也可以通過鄰接矩陣來存儲邊的權(quán)值信息和節(jié)點信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法【５３】２．３最優(yōu)路徑選擇２．３．１最優(yōu)路徑的求解過程在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問題轉(zhuǎn)化成優(yōu)化問題來解決，應(yīng)用優(yōu)化理論的相關(guān)思想和思路解決最優(yōu)路徑優(yōu)化問題。求解過程包括以下四個步驟酬：（１）交通網(wǎng)絡(luò)模型建立；（２）交通道路權(quán)重的計算；智能交通系統(tǒng)中最優(yōu)路徑選擇的設(shè)計與實現(xiàn)（３）利用最短路徑計算方法求解交通網(wǎng)絡(luò)中的最短路徑問題；（４）將交通網(wǎng)絡(luò)圖中的最短路徑問題轉(zhuǎn)化為現(xiàn)實交通網(wǎng)絡(luò)中的路段集合。其中，建立交通網(wǎng)絡(luò)模型是最優(yōu)路徑選擇的基礎(chǔ)，交通網(wǎng)絡(luò)模型中道路權(quán)值的計算以及利用權(quán)值信息求解最短路徑是關(guān)鍵。道路的權(quán)值是計算現(xiàn)實問題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準確與否在很大程度上取決于道路權(quán)值的設(shè)計和計算。２．３．２經(jīng)典Ｄｉｊｋｓｔｒａ算法分析在１９５９年荷蘭數(shù)學(xué)家ＥＷ．Ｄｉｊｋｓｔｒａ首先提出的Ｄｉｊｋｓｔｒａ算法哺１，該算法是一種單源最短路徑的搜索算法，他適用于非負權(quán)值網(wǎng)絡(luò)的，是目前求解最短路問題的理論上最完備、應(yīng)用范圍最廣的算法，可以計算出從圖中的某一節(jié)點到其他任意節(jié)點的最短路徑搜索結(jié)果。Ｄｉｊｋｓｔｒａ是一種迭代的貪心策略的路徑搜索算法，他根據(jù)路徑的長短逐漸增長來搜索點數(shù)，構(gòu)造了一顆路徑樹，從而得到路徑樹中的根部節(jié)點到其他任意節(jié)點的最短路徑結(jié)果。具體方法：設(shè)最短路徑的終點存放在集合ｓ中，在初始狀態(tài)下，只有一個元素點ｖ０存儲在集合ｓ中。在以后的計算步驟中，沒計算出一條路徑（ｖｏ，…，ｖｋ），就將此路徑加入到集合ｓ巾，知道圖中的全部節(jié)點都加入的集合中為止。向量ｄ是為了計算方便引入的一個輔助向量，他的第ｉ個分量表示從源點ｖ０到第ｉ個節(jié)點ｖ，的最短路徑長度。在引入萬的輔助向量，第ｉ個分量乃表示結(jié)點Ｍ的前繼結(jié)點。初始狀態(tài)為：碼＝ｎｕｌｌ，４＝００，ｔ＝０（匕為源點）。假設(shè)第一條最短路徑為（ｖｏ，唯），其中ｋ滿足吐＝ｍ岫｛喀Ｉ啊∈Ｖ－ｖｏ），貝ｔＪＴ－條最短路徑（終點為１，，），或是（Ｖｏ，Ｋ，■），或是０＇ｏ，ｖ，）。在一般情況下，假設(shè)ｓ是存放已經(jīng)求出的最短路徑的終點的集合，則下一條最短路徑的中間節(jié)點一定是Ｓ中的節(jié)點，其長度為以＝ｍｉｎ｛ｄａＩ■∈Ｖ—Ｓ）。在每次求得一條最短路徑之后，將其終點咋加入集合Ｓ，然后對所有的其他結(jié)點計算Ｈ＝Ｖ—ｓ，修改其４，％；西＝ｒａｉｎ｛ｄ，，以＋ｃ（唯，Ｈ）｝，乃＝坼。其中，ｃ（Ｋ，ｕ）是弧線（ｈ，Ｍ）上的權(quán)值。以上算法能夠計算出從源點到達其他任意結(jié)點的最短路徑長度。通過對石中元素的回溯可求出路徑所經(jīng)過的結(jié)點。根據(jù)上述思路，設(shè)帶權(quán)值的有向圖為Ｇ＝（礦，司，其中礦是數(shù)量為ｎ的結(jié)點集，Ｅ是數(shù)量為ｍ的邊集，ｗ為權(quán)值向量。具體算法步驟如下：（１）對ｄ和石進行初始化；（２）ｓ集合初始為空，Ｓ＝ｆ２ｊ；大連理Ｔ人學(xué)專業(yè)學(xué)位碩士學(xué)位論文（３）（４）（５）（６）（７）（８）為當前圖中的所有結(jié)點賦值給集合Ｑ，Ｑ＝ＨＧ】：循環(huán)條件：ｗｈｉｌｅＱ≠ｆ２ｊ；提取出集合Ｑ中最ｔＪ，ｄ值的結(jié)點，并賦給甜，Ｕ＝ＰｏｉｎｔＭｉｎ（Ｑ）：將提取出的結(jié)點加入Ｓ集合，Ｓ＝Ｓｕ｛ｕ）；對于每個結(jié)點ｖＥＡｄＪＩｕ】，計算并修改ｖ的ｄ和，ｒ；結(jié)束。最初Ｄｉｊｋｓｔｒａ算法開發(fā)的目的是計算網(wǎng)絡(luò)圖中兩節(jié)點之間的最短路徑問題，當該算法應(yīng)用到交通網(wǎng)絡(luò)的最短路徑搜索時，由于起始點和終止點都是已知的，因此只需要從起始點開始搜索，按照其搜索原則尋找最短路徑，一直搜索的終止點為止，需要對該算法進行優(yōu)化和改進，才能使用到交通網(wǎng)絡(luò)的最優(yōu)路徑選擇系統(tǒng)當中。從算法的原理可以發(fā)現(xiàn)，當交通網(wǎng)絡(luò)十分龐大時，該算法的計算量是十分巨大的，如果將該算法直接用于交通網(wǎng)絡(luò)的最優(yōu)路徑選擇算法當中，不能達到應(yīng)用的實時性要求，因此需要對該算法的性能進行提升式改進。另外，該算法只是路徑搜索，對于交通網(wǎng)絡(luò)中的路徑權(quán)值問題沒有任何解決辦法，因此該算法可以作為最優(yōu)路徑選擇的主要路徑搜索算法，而對于權(quán)值的提取和計算，需要額外增加輔助算法來完成，能夠反映交通網(wǎng)絡(luò)系統(tǒng)在實時狀態(tài)下權(quán)值的變化情況哺１。２．３．３交通阻抗分析交通阻抗