道路信息查詢系統(tǒng)設(shè)計(jì)摘要自九十年代初期以來(lái)，世界上已有許多國(guó)家開(kāi)始對(duì)路線信息查詢系統(tǒng)進(jìn)行了研究和開(kāi)發(fā)。路線信息查詢系統(tǒng)是一種迅速查出所在地區(qū)某單位或住宅地點(diǎn)，并依照你當(dāng)前所在地點(diǎn)查出對(duì)行人去某地的最佳乘車路線及到達(dá)離目的地最近后，如何行走的最佳行走路線，對(duì)駕駛員則提供一條從出發(fā)地到目的地的時(shí)間最短時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)最優(yōu)的行車路線，而對(duì)外地旅客還可提供各類賓館、旅店、飛機(jī)、火車時(shí)刻表、購(gòu)物及旅游場(chǎng)所等服務(wù)信息。使用該系統(tǒng)后，方便了廣大游客，避免了游客因環(huán)境的不熟悉所帶來(lái)困難。本文對(duì)路線信息查詢系統(tǒng)進(jìn)行了研究，并開(kāi)發(fā)了一個(gè)路線信息查詢RMQS1.0,(RoadMessageQuerySystem）。RMQS1.0系統(tǒng)的主要特點(diǎn)和功能如下1、根椐你掌握的信息迅速查出所在地區(qū)某單位或住宅地點(diǎn)2、對(duì)地圖進(jìn)行瀏覽和查出所在地區(qū)某單位或住宅地點(diǎn)3、對(duì)駕駛員提供一條從出發(fā)地到目的地的時(shí)間最短時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)最優(yōu)的行車路線4、為游客找到去某地最佳乘車路線和所經(jīng)過(guò)的站名，并提供下車后如何到目的地的最佳行走路線。5、對(duì)騎車人提供一條從出發(fā)地到目的地的距離最短的騎車路徑。6、為游客提供旅行其他必要的信息。本文研究的重點(diǎn)是路線信息查詢系統(tǒng)中的最優(yōu)乘車路線搜索算法部分、行車路線搜索算法部分。在RMQS1.0系統(tǒng)中用了兩種算法。第一種是最優(yōu)乘車路線搜索算法，用了啟發(fā)式搜索算法（A*），這種算法應(yīng)用了啟發(fā)式知識(shí)，使算法執(zhí)行時(shí)所搜索的節(jié)點(diǎn)數(shù)大大減少，運(yùn)行速度快；第二種是行車路線搜索算法，用了啟發(fā)式知識(shí)，它是本文提出的應(yīng)用于對(duì)時(shí)間最短、距離最短、時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)后產(chǎn)生的最優(yōu)行車路線搜索算法。本文對(duì)數(shù)字地圖數(shù)據(jù)庫(kù)也進(jìn)行了比較深入的探討，并參照國(guó)外開(kāi)發(fā)數(shù)字地圖數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)和方法。關(guān)鍵詞：RMQS1.0；數(shù)據(jù)庫(kù)ABSTRACTSincetheearly1990s,manycountriesintheworldhavebeguntoresearchanddeveloprouteinformationquerysystem.Therouteinformationinquirysystemisamethodtoquicklyfindoutthelocationofaunitorresidenceinthearea,andfindoutthebestrouteforpedestrianstogotoacertainplaceandhowtowalkafterreachingthenearestplacefromthedestinationaccordingtoyourcurrentlocation.Itprovidesthedriverwiththeshortesttimefromthestartingplacetothedestinationandthebestdrivingroutewithcomprehensiveevaluationofconsumptioncost.Forforeignpassengers,itcanalsoprovideallkindsofhotelsHotel,plane,traintimetable,shoppingandtouristplacesandotherserviceinformation.Afterusingthesystem,itisconvenientforthemajorityoftouristsandavoidsthedifficultiescausedbytheunfamiliarenvironment.Thispaperstudiestherouteinformationquerysystem,anddevelopsarouteinformationqueryrmqs1.0(roadmessagequerysystem).Themainfeaturesandfunctionsofrmqs1.0systemareasfollows1.Accordingtotheinformationyouhave,quicklyfindoutthelocationofaunitorresidenceinyourarea2.Browsethemapandfindoutthelocationofaunitorresidenceinthearea3.Providethedriverwiththeshortesttimefromthedeparturetothedestinationandthebestdrivingroutewithcomprehensiveevaluationoftimeandcost4.Findthebestbusroutetoaplaceandthestationname,andprovidethebestwalkingroutetothedestinationaftergettingoff.5.Providecyclistswithacyclingpathwiththeshortestdistancefromthestartingpointtothedestination.6.Providetouristswithothernecessaryinformationfortravel.Thispaperfocusesontheoptimalrideroutesearchalgorithmanddrivingroutesearchalgorithmintherouteinformationquerysystem.Twoalgorithmsareusedinrmqs1.0system.Thefirstistheoptimalbusroutesearchalgorithm,whichusesheuristicsearchalgorithm(a*),whichappliesheuristicknowledgetogreatlyreducethenumberofnodessearchedduringtheexecutionofthealgorithmandrunfast;Thesecondistheroutesearchalgorithm,whichusesheuristicknowledge.Itistheoptimalroutesearchalgorithmproposedinthisthesisafterthecomprehensiveevaluationoftheshortesttime,theshortestdistance,timeandcost.Thispaperalsomakesamorein-depthdiscussiononthedigitalmapdatabase,andreferstothestandardsandmethodsofdevelopingthedigitalmapdatabaseabroad.Keywords:rmqs1.0；database目錄TOC\o"1-2"\h\u30057第一章緒言 緒言隨著世界經(jīng)濟(jì)的不斷發(fā)展，世界各國(guó)不斷的對(duì)城市建設(shè)進(jìn)行改造，以便使其成為現(xiàn)代化都市，尤其在中國(guó)近幾年里大中小城市的市政建設(shè)都發(fā)生了巨大的變化，同時(shí)對(duì)舊城區(qū)也進(jìn)行了改造。隨著經(jīng)濟(jì)的繁榮、各種機(jī)動(dòng)車輛與日俱增，以及外出旅游也成為新時(shí)尚，人們迫切地需要提供城市的各種道路、旅游服務(wù)等信息，以便經(jīng)濟(jì)快捷地享受旅行帶來(lái)的樂(lè)趣。路線信息查詢系統(tǒng)（RoadMessageQuerySystem，簡(jiǎn)稱RMQS）就是在這種情況下應(yīng)運(yùn)而生的一種新的路線查詢和導(dǎo)游服務(wù)系統(tǒng)。本章將著重介紹路線查詢和導(dǎo)游服務(wù)系統(tǒng)的一般組成結(jié)構(gòu)，分類以及國(guó)內(nèi)外進(jìn)展和發(fā)展趨勢(shì)。由于我國(guó)在路線信息查詢目前還不十分完善，需要做大量的工作，尤其在道路數(shù)字地圖數(shù)據(jù)庫(kù)的構(gòu)造、數(shù)字地圖圖象處理和最優(yōu)路線搜索算法方面，還需要進(jìn)一步改進(jìn)、提高。對(duì)道路數(shù)字地圖數(shù)據(jù)庫(kù)的構(gòu)造，采用地圖矢量化方法進(jìn)行數(shù)字地圖數(shù)據(jù)庫(kù)的構(gòu)造；對(duì)數(shù)字地圖圖象處理包括：數(shù)字地圖顯示、數(shù)字化地圖、數(shù)字化圖象放大和縮小處理。對(duì)最優(yōu)路線搜索算法要從以下三方面考慮：第一、行人的最佳乘車路線及下車后如何走到目的地的最佳行走路線第二、騎車人的距離最短的行車路線第三、駕駛員有以下三種情況的選擇：時(shí)間最短、路徑最短和時(shí)間與消耗費(fèi)用評(píng)估分別來(lái)進(jìn)行最優(yōu)路線搜索1.1路線信息查詢系統(tǒng)的結(jié)構(gòu)和分類所謂路線信息查詢系統(tǒng),是指一種新的路線查詢和導(dǎo)游服務(wù)系統(tǒng)，它利用計(jì)算機(jī)幫助游客或駕駛員找到一條從出發(fā)地到目的地的最優(yōu)路線，同時(shí)向駕駛員提供圖形和文字說(shuō)明的路線引導(dǎo)圖，向游客提供乘車路線及所經(jīng)過(guò)的站名的路線引導(dǎo)圖，并配以文字說(shuō)明。使用該系統(tǒng)后，使游客旅游、住宿更加便利，且能適當(dāng)?shù)臏p少了交通堵塞的發(fā)生，減少車輛在道路上的逗留時(shí)間，節(jié)約了顧客費(fèi)用，并在某種程度上實(shí)現(xiàn)了交通流量在各條路段的合理再分配。據(jù)英國(guó)交通和公路研究實(shí)驗(yàn)室估計(jì)，給司機(jī)提供行駛路線信息，可減少行車時(shí)間8-12%。此外，應(yīng)用這種系統(tǒng)，能幫助對(duì)地理環(huán)境不熟悉的游客或駕駛員準(zhǔn)確、快速地到達(dá)目的地。路線信息查詢系統(tǒng)的一般組成結(jié)構(gòu)如圖1.1所示。路線決策模塊在整個(gè)路線信息查詢系統(tǒng)的核心。其功能包括：找出目的地的具體位置、為游客提供一條到目的地的乘車路線及下車。圖1.1路線信息查詢系統(tǒng)的功能結(jié)構(gòu)圖后行走的路線圖、對(duì)地圖進(jìn)行流覽、為駕駛員提供一條到目的地的時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)最優(yōu)的行車路線引導(dǎo)、以及提供旅游、住宿信息及飛機(jī)、火車時(shí)刻表等信息。數(shù)字地圖數(shù)據(jù)庫(kù)用來(lái)存儲(chǔ)道路網(wǎng)絡(luò)的拓?fù)湫畔?，以及其它的相關(guān)數(shù)據(jù)。交通流量數(shù)據(jù)庫(kù)用來(lái)存儲(chǔ)道路網(wǎng)絡(luò)中各個(gè)公路在不同時(shí)間段內(nèi)通過(guò)該公路的時(shí)間和所消耗的費(fèi)用的綜合評(píng)估值。單位數(shù)據(jù)庫(kù)用來(lái)存儲(chǔ)所在地區(qū)所有單位和住宅樓的指示性圖形。站點(diǎn)數(shù)字地圖數(shù)據(jù)庫(kù)用來(lái)存儲(chǔ)交通路線上各公交車站的具體信息。用戶界面以圖形文字說(shuō)明與用戶進(jìn)行交互。路線信息查詢系統(tǒng)的運(yùn)行原理可以總結(jié)為：各種數(shù)據(jù)源把位置、方向、字地圖、單位信息、旅游信息、交通流量信息和起止點(diǎn)等數(shù)據(jù)在計(jì)算機(jī)中進(jìn)行處理。計(jì)算機(jī)利用所獲得的信息計(jì)算出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路線并產(chǎn)生引導(dǎo)路線圖，并以圖形和文字的形式輸出。游客或司機(jī)根據(jù)所得到的信息來(lái)決定如何行駛，安全、節(jié)約、快速地到達(dá)目的地。上面介紹的是路線信息查詢系統(tǒng)的一般結(jié)構(gòu)。然而，在不同的國(guó)家和不同時(shí)期，路線信息查詢系統(tǒng)的結(jié)構(gòu)是有區(qū)別的。下面我們按不同的標(biāo)準(zhǔn)對(duì)路線信息查詢系統(tǒng)進(jìn)行分類。根據(jù)路線信息查詢系統(tǒng)所使用的數(shù)據(jù)來(lái)源不同，可以把路線信息查詢系統(tǒng)分為靜態(tài)系統(tǒng)和動(dòng)態(tài)系統(tǒng)。靜態(tài)系統(tǒng)使用靜態(tài)數(shù)據(jù)，即數(shù)字地圖數(shù)據(jù)庫(kù)、單位數(shù)據(jù)庫(kù)、旅游數(shù)據(jù)庫(kù)。動(dòng)態(tài)系統(tǒng)使用的是實(shí)時(shí)交通信息。靜態(tài)系統(tǒng)結(jié)構(gòu)簡(jiǎn)單，而動(dòng)態(tài)系統(tǒng)需要附加動(dòng)態(tài)信息拾取設(shè)備和通訊手段，及更復(fù)雜的查詢算法附加動(dòng)態(tài)信息拾取設(shè)備和通訊手段，及更復(fù)雜的查詢算法。1.2路線信息查詢系統(tǒng)發(fā)展的歷史、現(xiàn)狀與趨勢(shì)1.2.1路線信息查詢系統(tǒng)的發(fā)展歷史人類很早就開(kāi)始使用路標(biāo)來(lái)指示方向，并且在汽車還未出現(xiàn)前就發(fā)明了許多導(dǎo)航設(shè)備。據(jù)我國(guó)古代文獻(xiàn)通記載，在漢朝未期就出現(xiàn)了里程計(jì)；在公元200—300年，發(fā)明了指南車；在公元11世紀(jì)，又發(fā)明了磁羅盤。利用這些設(shè)備可以較準(zhǔn)確的確定車子行進(jìn)的方向和行使的距離。六十年代未，由于科學(xué)技術(shù)的發(fā)展，人們開(kāi)始對(duì)動(dòng)態(tài)引導(dǎo)系統(tǒng)進(jìn)行研究。在美國(guó)，出現(xiàn)了電子引導(dǎo)系統(tǒng)（ElectronicGuidanceSystem），它能接收外部的無(wú)線電信號(hào)，獲得所需的信息。電子引導(dǎo)系統(tǒng)在很大程度上克服了路標(biāo)和地圖的缺點(diǎn)（靜態(tài)、易過(guò)時(shí)，有時(shí)給出不完整甚至錯(cuò)誤的信息）。在英國(guó)，有一種傳統(tǒng)的行車路線咨詢服務(wù)。提供此項(xiàng)服務(wù)的有AA、RAC等組織。司機(jī)只要把起點(diǎn)和終點(diǎn)以及選擇路線的標(biāo)準(zhǔn)告訴某一組織，就可以得到路線服務(wù)信息。它們提供的服務(wù)形式主要有兩種：1.行車路線圖：在一張地圖上，把行車路線用特殊的顏色或高亮度顯著地標(biāo)記出來(lái)。2.文字指令表：在表中，用項(xiàng)細(xì)的描述告述司機(jī)每一步該如何走，包括經(jīng)過(guò)的街道。公路和沿路的建筑物等。起初，這種服務(wù)都是用手工完成的。后來(lái)，隨著計(jì)算機(jī)技術(shù)的發(fā)展，手工作業(yè)逐步被計(jì)算機(jī)作業(yè)所代替。1.2.2路線查尋系統(tǒng)的發(fā)展現(xiàn)狀現(xiàn)代計(jì)算機(jī)和通訊技術(shù)的飛速發(fā)展，給真正意義上的路線查尋系統(tǒng)的產(chǎn)生創(chuàng)造了條件。美國(guó)、日本和歐洲在這方面的研究與開(kāi)發(fā)水平處于領(lǐng)先地位。首先看一看美國(guó)的情況。美國(guó)在八十年代提出了一個(gè)交通戰(zhàn)略計(jì)劃，叫做“智能車輛／公路系統(tǒng)（IVHS）”計(jì)劃，在IVHS中，一個(gè)很重要的組成部分就是路線引導(dǎo)系統(tǒng)。圖1.2所示是它們的關(guān)系圖。圖1.2IVHS系統(tǒng)構(gòu)成圖在歐洲也有兩個(gè)交通戰(zhàn)略計(jì)劃，叫做PROMETHEUS和DRIVE、PROMETHEUS計(jì)劃的目標(biāo)是開(kāi)發(fā)公路交通電子系統(tǒng)，參加者是歐洲的大部分汽車制造商。DRIVE計(jì)劃的目標(biāo)是建立集成的公路運(yùn)輸環(huán)境，它包括很多具體的項(xiàng)目。1.2.3路線查尋系統(tǒng)的未來(lái)發(fā)展趨勢(shì)一、路線引導(dǎo)系統(tǒng)和交通控制系統(tǒng)的集成路線引導(dǎo)系統(tǒng)和交通控制系統(tǒng)所需求的數(shù)據(jù)互有重疊，兩個(gè)系統(tǒng)相互作用。路線引導(dǎo)的結(jié)果影響交通信號(hào)的控制，反過(guò)來(lái)，交通信號(hào)的控制又影響對(duì)路線的選則。所以兩個(gè)系統(tǒng)的集成可以共享數(shù)據(jù)，消除不穩(wěn)定性和反饋的負(fù)作用，提高整個(gè)交通網(wǎng)絡(luò)的性能。兩系統(tǒng)的集成有三個(gè)不同的成次：（1）互換數(shù)據(jù)（2）一個(gè)系統(tǒng)的輸出作為另一個(gè)襲用的輸出，反之亦然。（3）完全的集成二、預(yù)測(cè)型引導(dǎo)系統(tǒng)路線引導(dǎo)系統(tǒng)的目標(biāo)是要提供智能和安全的建議，這就要求不僅中國(guó)要考慮當(dāng)前的交通狀況，同時(shí)也要考慮在汽車到達(dá)目的地的過(guò)程中將要發(fā)生的情況。在計(jì)算最優(yōu)路線時(shí)，使用路段的預(yù)測(cè)權(quán)值，而不是當(dāng)前權(quán)值，這樣的系統(tǒng)就叫做預(yù)測(cè)型引導(dǎo)系統(tǒng)。三、通訊手段不斷更新汽車和交通控制中心的通訊可考慮的方式有紅外通訊、微波通訊、FM無(wú)線通訊、衛(wèi)星通訊等。在歐洲，蜂窩移動(dòng)電話網(wǎng)絡(luò)正在逐步建立起來(lái)，以移動(dòng)電話為通訊手段將會(huì)被越來(lái)越多的路線引導(dǎo)系統(tǒng)所采納。九十年代是以來(lái)，計(jì)算機(jī)網(wǎng)絡(luò)在全世界范圍內(nèi)得到了迅速的普及和應(yīng)用?？梢韵胂?，若把許多車輛組成一個(gè)計(jì)算機(jī)無(wú)線通訊網(wǎng)，使每一輛車都成為一個(gè)流動(dòng)的網(wǎng)絡(luò)站點(diǎn)，則不但車輛可以和網(wǎng)絡(luò)中心通訊，而且車輛之間也可以互換信息。四、路線引導(dǎo)系統(tǒng)向路線綜合查尋系統(tǒng)過(guò)度交通路線引導(dǎo)系統(tǒng)只向司機(jī)提供路線引導(dǎo)信息。然而，司機(jī)卻需要更多的信息?，F(xiàn)代技術(shù)的發(fā)展為此提供了可能。未來(lái)的交通路線引導(dǎo)系統(tǒng)將發(fā)展成為一個(gè)路線綜合查尋系統(tǒng)。它不僅提供路線信息，而且可以提供其它方面的信息，如有關(guān)周圍旅館、飯店的情況等。此外，還可以作為娛樂(lè)系統(tǒng)，播放多媒體圖象和音樂(lè)。五、路線綜合查尋系統(tǒng)由個(gè)體引導(dǎo)向集群引導(dǎo)轉(zhuǎn)變當(dāng)安裝有路線引導(dǎo)系統(tǒng)的車輛為數(shù)不多時(shí)，各個(gè)車輛在計(jì)算最優(yōu)路線時(shí)可以不考慮其它車輛，而只根據(jù)所獲得的當(dāng)前交通信息計(jì)算即可。然而，若許多車輛都安裝了路線引導(dǎo)設(shè)備，個(gè)體引導(dǎo)可能會(huì)出現(xiàn)這種情況：許多車輛離開(kāi)某一交通擁擠路段，都駛向某一暢通地區(qū)，從而造成新的交通堵塞。為了避免這一情況，在計(jì)算最優(yōu)路線時(shí)，必須統(tǒng)籌考慮，實(shí)現(xiàn)集群引導(dǎo)。1.3我國(guó)研究和建立路線綜合查尋系統(tǒng)的必要性和現(xiàn)實(shí)性公路運(yùn)輸對(duì)于一個(gè)國(guó)家來(lái)說(shuō)是不可缺少的交通動(dòng)脈，要想搞好交通除了作好宣傳教育外，還要著手解決交通堵塞現(xiàn)象，減少交通堵塞及交通事故的發(fā)生，避免對(duì)國(guó)家會(huì)造成巨大的經(jīng)濟(jì)損失。公路運(yùn)輸?shù)陌l(fā)展水平也是衡量一個(gè)國(guó)家經(jīng)濟(jì)發(fā)展程度的標(biāo)志。我國(guó)是世界上人口最多的國(guó)家，特別是在大城市，人口密度非常大。隨著經(jīng)濟(jì)的發(fā)展，城市內(nèi)的各種車輛也急劇增加。同時(shí)，道路新建、擴(kuò)建、對(duì)新舊城區(qū)的建設(shè)、改造，使城市的道路網(wǎng)絡(luò)狀況發(fā)生了極大的變化。然而，我國(guó)在路線查詢系統(tǒng)方面研究不多，于國(guó)外有很大的差距。我國(guó)應(yīng)借鑒國(guó)外已有的理論和技術(shù)，研究和開(kāi)發(fā)符合我國(guó)國(guó)情的路線綜合查尋系統(tǒng)，盡快方便廣大的顧客的需要，在不遠(yuǎn)的將來(lái)，在此基礎(chǔ)上對(duì)交通進(jìn)行管理和控制，進(jìn)而實(shí)現(xiàn)路線綜合查詢系統(tǒng)。1.4已有工作基礎(chǔ)和本論文的研究?jī)?nèi)容本人對(duì)數(shù)字地圖信息的矢量化圖象處理，以及啟發(fā)式搜索算法，曾經(jīng)做了大量的學(xué)習(xí)和研究工作；并且對(duì)道路狀況（掌握單行線、各個(gè)時(shí)間段中道路的車流量情況及所需要的花費(fèi)）、交通規(guī)則、公交車線路及車站位置等特定信息做大量的調(diào)查與分析工作。在此基礎(chǔ)上，本文主要研究如何利用計(jì)算機(jī)內(nèi)的各種信息，對(duì)行人提供最佳乘車路線及下車后如何走到目的地的最佳行走路線；對(duì)騎車人提供距離最短的騎車路線；對(duì)駕駛員有以下三種情況的選擇：時(shí)間最短、路徑最短和時(shí)間與消耗費(fèi)用評(píng)估分別來(lái)進(jìn)行最優(yōu)行車路線。它利用計(jì)算機(jī)幫助游客或駕駛員找到一條從出發(fā)地到目的地的最優(yōu)路線，同時(shí)向駕駛員提供路線引導(dǎo)地圖，向游客提供最優(yōu)乘車路線及所經(jīng)過(guò)的站名的引導(dǎo)地圖，以及游客下車后到目的地的最優(yōu)行走路線。應(yīng)用這種系統(tǒng)，能幫助對(duì)地理環(huán)境不熟悉的游客或駕駛員準(zhǔn)確、快速地到達(dá)目的地。它包括內(nèi)容如下：(1)如何將道路地圖信息轉(zhuǎn)化為數(shù)字地圖數(shù)據(jù)庫(kù)，來(lái)存儲(chǔ)道路網(wǎng)絡(luò)的拓?fù)湫畔?，以及其它的相關(guān)數(shù)據(jù)信息。(2)如何根據(jù)道路上的具體情況，根據(jù)不同用戶的要求時(shí)實(shí)計(jì)算出最優(yōu)路線。(3)如何將所在地區(qū)所有單位、住宅樓的具體信息和與其有關(guān)的相關(guān)信息，建造單位數(shù)據(jù)庫(kù)。(4)如何將存儲(chǔ)公交車站頂點(diǎn)網(wǎng)絡(luò)的拓?fù)湫畔?，及相關(guān)數(shù)據(jù)，建立公交電汽車車站地圖數(shù)據(jù)庫(kù)。(5)如何利用用戶所掌握的某單位的具體信息（如地址、電話、單位類別等）來(lái)查找該單位的具體位置及信息。(6)如何向用戶提供常用服務(wù)信息（飛機(jī)時(shí)刻表及售票地點(diǎn)、火車時(shí)刻表及售票地點(diǎn)、賓館、旅店、名勝古跡、購(gòu)物場(chǎng)所、醫(yī)院、派出所、銀行及出租車汽車公司等）。(7)如何將計(jì)算得出的信息，直觀的顯示給用戶。其核心內(nèi)容是建立數(shù)字地圖數(shù)據(jù)庫(kù)和啟發(fā)式路線搜索算法。小結(jié)：本章主要討論了路線綜合查尋系統(tǒng)的概念、結(jié)構(gòu)和分類，路線綜合查尋系統(tǒng)的發(fā)展、現(xiàn)狀和趨勢(shì)。路線綜合查尋系統(tǒng)作為一種新生事物，它在人們現(xiàn)實(shí)生活中所起的作用已經(jīng)開(kāi)始被人們所重視。計(jì)算機(jī)和通訊技術(shù)近幾年來(lái)發(fā)展十分迅速，人們的生活也隨著它們的發(fā)展而改變。路線綜合查尋系統(tǒng)正是靠這兩項(xiàng)技術(shù)發(fā)展起來(lái)的。在不遠(yuǎn)的將來(lái)為司機(jī)提供了大量的路線和交通信息，使司機(jī)在自己的車內(nèi)就能知道所有道路網(wǎng)絡(luò)的交通狀況，而可以迅速的到達(dá)目的地是我們以后最終要實(shí)現(xiàn)的目標(biāo)。路線綜合查尋系統(tǒng)組成及實(shí)現(xiàn)技術(shù)本人開(kāi)發(fā)了一個(gè)路線信息查詢系統(tǒng)RMQS1.0系統(tǒng)。在RMQS1.0系統(tǒng)中，對(duì)最優(yōu)路線搜索做了比較深入的研究，并提出了一個(gè)新的路線搜索算法啟發(fā)式搜索算法。本章將對(duì)RMQS1.0系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程進(jìn)行了詳細(xì)描述。2.1系統(tǒng)總體設(shè)計(jì)2.1.1路線信息查詢系統(tǒng)結(jié)構(gòu)和功能路線信息查詢系統(tǒng)結(jié)構(gòu)如圖3.1所示。圖2.1為路線綜合查詢系統(tǒng)組成的總體模塊結(jié)構(gòu)圖查詢系統(tǒng)所具有的特點(diǎn)和功能如下：1)地圖的局部放大、縮小顯示。2)按不同類別、單位地址、單位電話和地圖查詢等情況進(jìn)行查詢。3)按照時(shí)間最短、路徑最短和時(shí)間與消耗費(fèi)用評(píng)估來(lái)進(jìn)行最優(yōu)路線搜索，也就是說(shuō)，用戶可以按照自己的需要選擇不同的路線行駛。并向用戶提供圖形、文字兩種說(shuō)明。該系統(tǒng)向用戶提供多種形式的引導(dǎo)信息，使用戶及時(shí)準(zhǔn)確的掌握所需的信息，滿足顧客的要求。4)方便的起止地址輸入。路線信息查詢系統(tǒng)向用戶提供一個(gè)起止地址的輸入窗口，用戶需在地址列表中用鼠標(biāo)進(jìn)行選擇或直接由鍵盤輸入，即可輸入出發(fā)地和目的地名稱。5)在最優(yōu)乘車路線在地圖上的顯示并配以文字說(shuō)明。6)能對(duì)沈陽(yáng)市所有單位、住家進(jìn)行查詢。該系統(tǒng)向用戶提供多種形式的地點(diǎn)查詢，使用戶迅速找到所查單位或住家的地址。7)能對(duì)沈陽(yáng)市所有賓館、飛機(jī)和列車時(shí)刻表、旅游和購(gòu)物場(chǎng)所等進(jìn)行查詢。使用戶及時(shí)準(zhǔn)確的掌握所需的信息。2.1.2路線信息查詢系統(tǒng)運(yùn)行的系統(tǒng)平臺(tái)1、路線信息查詢系統(tǒng)運(yùn)行的硬件環(huán)境為：·586微機(jī)：586主板，PENTIUM200的CPU，64M內(nèi)存，2G硬盤。路線信息查詢系統(tǒng)的開(kāi)發(fā)和運(yùn)行都是在上述硬件平臺(tái)上進(jìn)行的。·數(shù)字化儀：型號(hào)為SummagraphicBitPadOneMode11。數(shù)字化儀包括數(shù)字化圖形輸入板和點(diǎn)收取設(shè)備（游標(biāo)或觸筆）。數(shù)字化儀用來(lái)把紙張地圖轉(zhuǎn)化為數(shù)字地圖存到計(jì)算機(jī)中。2、路線信息查詢系統(tǒng)運(yùn)行的軟件環(huán)境是：·中文Windows95Windows95操作系統(tǒng)是路線信息查詢系統(tǒng)運(yùn)行的操作系統(tǒng)。·AutoCAD利用該軟件和數(shù)字化儀，可以形成數(shù)字地圖數(shù)據(jù)庫(kù)?！owerBuilder5.0PowerBuilder5.0是系統(tǒng)應(yīng)用的開(kāi)發(fā)工具。PowerBuilder5.0是優(yōu)秀的可視化編程語(yǔ)言，它采用事件驅(qū)動(dòng)編程方法，開(kāi)發(fā)效率高。PowerBuilder5.0提供ODBC（開(kāi)放數(shù)據(jù)庫(kù)互連）支持，可以訪問(wèn)Access、Foxpro等多種類型的數(shù)據(jù)庫(kù)。PowerBuilder5.0可以直接調(diào)用WindowsAPI函數(shù)，從而大大提高PowerBuilder5.0的功能和靈活性。正因?yàn)镻owerBuilder5.0具有這些優(yōu)點(diǎn)，所以本系統(tǒng)全部采用PowerBuilder5.0語(yǔ)言進(jìn)行開(kāi)發(fā)。2.1.3路線信息查詢系統(tǒng)的開(kāi)發(fā)過(guò)程路線信息查詢系統(tǒng)的各個(gè)功能模塊是一個(gè)統(tǒng)一的整體，整個(gè)系統(tǒng)的開(kāi)發(fā)可以分為五個(gè)步驟來(lái)進(jìn)行：建立數(shù)字地圖數(shù)據(jù)庫(kù)和各種類型的數(shù)據(jù)庫(kù)主要的任務(wù)是將紙張地圖進(jìn)行數(shù)字化，得到數(shù)字地圖數(shù)據(jù)。數(shù)字地圖數(shù)據(jù)庫(kù)和建立好的各種類型的數(shù)據(jù)庫(kù)就成為地圖顯示、路線搜索和路線引導(dǎo)的數(shù)據(jù)源。2、顯示數(shù)字地圖和文字說(shuō)明以圖形方式顯示數(shù)字地圖并配以文字說(shuō)明，是向司機(jī)提供最直接的方式之一。它的主要任務(wù)是利用數(shù)字地圖數(shù)據(jù)庫(kù)的數(shù)據(jù)，創(chuàng)建圖元文件，并在屏幕上顯示出來(lái)。3、最優(yōu)行車路線搜索最優(yōu)行車路線搜索模塊是本文研究的重點(diǎn)。主要是針對(duì)道路網(wǎng)絡(luò)的實(shí)際情況，根據(jù)顧客的要求找出從起點(diǎn)到終點(diǎn)的最優(yōu)路線的算法。最優(yōu)路徑的算法指的是速度快、節(jié)約、所得的結(jié)果是接近或等于最優(yōu)值，并生成圖形、文字的路線引導(dǎo)圖。4、最優(yōu)乘車路線搜索在路線信息查詢系統(tǒng)中，提供給旅客的乘車路線是按經(jīng)過(guò)最少站點(diǎn)的數(shù)量找出從起點(diǎn)到終點(diǎn)的最優(yōu)乘車路線，并提供圖形、文字的乘車路線引導(dǎo)圖。5、設(shè)計(jì)用戶界面好的軟件系統(tǒng)必須具備好的用戶界面，界面的好壞直接影響軟件性能的發(fā)揮。把設(shè)計(jì)用戶界面作為系統(tǒng)開(kāi)發(fā)最后階段，就是要把前面所做的工作集成到一起，使各個(gè)功能模塊之間能夠相互協(xié)調(diào)，給用戶提供一個(gè)舒適的使用環(huán)境。下面各節(jié)將按照上面所述的順序詳細(xì)地闡述每個(gè)步驟中使用地算法，所遇到地問(wèn)題和解決方法，以及所得結(jié)論。2.2系統(tǒng)模塊路線綜合查尋系統(tǒng)是由系統(tǒng)維護(hù)模塊、單位查詢模塊、路線決策模塊和服務(wù)區(qū)、服務(wù)查詢四大功能模塊組成。各模塊之間相互關(guān)聯(lián)，互通信息，協(xié)同完成整個(gè)系統(tǒng)的功能。下面將分別對(duì)四個(gè)模塊的實(shí)現(xiàn)方法和技術(shù)進(jìn)行介紹。2.2.1系統(tǒng)維護(hù)模塊系統(tǒng)維護(hù)模塊提供了對(duì)數(shù)字地圖數(shù)據(jù)庫(kù)、單位地圖數(shù)據(jù)庫(kù)、交通流量數(shù)據(jù)庫(kù)和車站地圖數(shù)據(jù)庫(kù)進(jìn)行增加、刪除、修改的功能，當(dāng)?shù)缆贰挝?、交通流量、公交汽車站及車次發(fā)生變化時(shí)，能夠隨時(shí)進(jìn)行增加、刪除、修改，以便更好地為顧客服務(wù)。一、數(shù)字地圖數(shù)據(jù)庫(kù)的維護(hù)當(dāng)城市道路網(wǎng)絡(luò)發(fā)生修改后，數(shù)字地圖數(shù)據(jù)庫(kù)也應(yīng)相應(yīng)的進(jìn)行修改，考慮到有時(shí)在一張白紙上臨時(shí)畫上含有路線與代表大樓、機(jī)關(guān)、單位等“最小點(diǎn)”的示意性草圖。利用多用戶操作過(guò)程可形成該草圖的臨時(shí)性電子地圖數(shù)據(jù)文件。由于所給出的兩點(diǎn)坐標(biāo)不可能精確，及草圖不可能符合比例尺要求，而系統(tǒng)在輸出顯示時(shí)是以“電子地圖”疊加在原來(lái)的電子地圖上面的方式，如不加以修正，就會(huì)引起混亂。為了克服這種現(xiàn)象，系統(tǒng)利用其已形成的標(biāo)準(zhǔn)電子地圖數(shù)據(jù)庫(kù)，按新輸入的電子草圖的道路名稱、“最小點(diǎn)”名稱自動(dòng)核對(duì)并進(jìn)行位置修正，結(jié)果實(shí)際顯示的結(jié)果是在原電子地圖上精確地標(biāo)出了他要畫出的那些內(nèi)容(全部以高亮度或特殊顏色出現(xiàn))。對(duì)若干臨時(shí)性的“最小點(diǎn)”很可能原電子地圖不存在，經(jīng)上述修正過(guò)程之后，該“最小點(diǎn)”的位置相對(duì)于草圖上道路(兩側(cè))的位置關(guān)系而獲得了一定程度的修正，程序操作員用鼠標(biāo)對(duì)該點(diǎn)位置稍加修正，就會(huì)出現(xiàn)滿意的結(jié)果。在屏幕上電子地圖為背景或通過(guò)輸入經(jīng)、緯度獲得代表不同對(duì)象的“最小點(diǎn)”位置，作為鼠標(biāo)觸發(fā)對(duì)象，實(shí)現(xiàn)對(duì)該點(diǎn)實(shí)際對(duì)象的信息輸入或輸出?！白钚↑c(diǎn)”顯示圖標(biāo)由用戶指定，其在屏幕上出現(xiàn)時(shí)占有的“面積”不受圖形放大或縮小的影響。二、單位地圖數(shù)據(jù)庫(kù)的維護(hù)當(dāng)某單位所在地發(fā)生變化、單位已經(jīng)不存在、有新的單位產(chǎn)生時(shí)，要對(duì)數(shù)據(jù)庫(kù)進(jìn)行增加、修改和刪除，以保持?jǐn)?shù)據(jù)庫(kù)的完整性和一致性。圖2.2為路線綜合查詢系統(tǒng)中系統(tǒng)維護(hù)模塊結(jié)構(gòu)圖三、車站地圖數(shù)據(jù)庫(kù)的維護(hù)當(dāng)某公交車站的位置發(fā)生變化、有新的公交車線路產(chǎn)生、某路公交線路取消時(shí)，要對(duì)車站數(shù)據(jù)庫(kù)進(jìn)行增加、修改和刪除，以保持?jǐn)?shù)據(jù)庫(kù)的完整性。交通流量數(shù)據(jù)庫(kù)的維護(hù)（一）如何維護(hù)當(dāng)某段公路的交通流量，在某以時(shí)間段發(fā)生變化、某條道路發(fā)生改變（如該為單行線）、新的道路產(chǎn)生等情況時(shí)，要對(duì)交通流量數(shù)據(jù)庫(kù)進(jìn)行增加、修改和刪除，以保持?jǐn)?shù)據(jù)庫(kù)的實(shí)時(shí)性、完整性。（二）對(duì)未來(lái)的展望近十幾年來(lái)，科學(xué)技術(shù)有了迅速的發(fā)展，尤其體現(xiàn)在通訊技術(shù)和計(jì)算機(jī)技術(shù)。在通訊方面，移動(dòng)通訊被受關(guān)注。移動(dòng)通訊的一個(gè)在重要應(yīng)用領(lǐng)域是在車輛、船只和飛機(jī)上。在車輛上安裝移動(dòng)電臺(tái)（車臺(tái)），就可以和交通中心進(jìn)行通訊，獲取實(shí)時(shí)交通信息和向交通中心反饋信息。前面兩節(jié)簡(jiǎn)述了射頻通訊和紅外通訊，下面將介紹其它幾種已經(jīng)獲得應(yīng)用或正在研究的移動(dòng)通訊方式。1）數(shù)字蜂窩移動(dòng)通訊蜂窩移動(dòng)通訊自其80年代問(wèn)世以來(lái)，發(fā)展十分迅速。目前，第一代模擬蜂窩移動(dòng)電話系統(tǒng)正在被第二代數(shù)字蜂窩移動(dòng)電話系統(tǒng)所取代。當(dāng)前國(guó)際上正在開(kāi)發(fā)和已進(jìn)入商用的數(shù)字蜂窩移動(dòng)系統(tǒng)有三種制式：第一種是歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)（CEPT）建議的泛歐數(shù)字移動(dòng)通訊系統(tǒng)（GSM），第二種是美國(guó)電信工業(yè)協(xié)會(huì)（TIA）提出的DAMPS（IS-54）系統(tǒng)，第三種是日本的JDC（DNTT）系統(tǒng)。GMS系統(tǒng)是當(dāng)前發(fā)展最成熟的一種數(shù)字系統(tǒng)，具有頻率利用率高，成本低，保密性好，可以全歐漫游等優(yōu)點(diǎn)。蜂窩移動(dòng)電話通訊系統(tǒng)以若干個(gè)相鄰的蜂房式（正六邊形）小區(qū)覆蓋范圍組成服務(wù)的大中容量移動(dòng)電話通訊系統(tǒng)。蜂窩移動(dòng)電話通訊系統(tǒng)由移動(dòng)業(yè)務(wù)交換中心、基站、移動(dòng)臺(tái)（車載臺(tái)、手持臺(tái)等）及傳輸電路組成。圖2.4所示為數(shù)字蜂窩移動(dòng)通訊示意。這種系統(tǒng)除了能提供話音外，還可以提供多種非話業(yè)務(wù)（數(shù)據(jù)業(yè)務(wù)等），可用于車輛和交通控制中心進(jìn)行通訊。衛(wèi)星移動(dòng)通訊衛(wèi)星移動(dòng)通訊系統(tǒng)是指以衛(wèi)星為基礎(chǔ)，在廣泛地理區(qū)域內(nèi)，為行駛中的車輛、船等移動(dòng)物體提供多種業(yè)務(wù)的系統(tǒng)，即通過(guò)衛(wèi)星實(shí)現(xiàn)移動(dòng)臺(tái)與固定臺(tái)、移動(dòng)臺(tái)與移動(dòng)臺(tái)以及移動(dòng)臺(tái)或固定臺(tái)與公共網(wǎng)用戶之間的通訊。它既有衛(wèi)星通訊的覆蓋面又有移動(dòng)通訊的靈活務(wù)。移動(dòng)衛(wèi)星通訊系統(tǒng)主要由衛(wèi)星轉(zhuǎn)發(fā)器、主站（網(wǎng)絡(luò)控制中心）、基站、網(wǎng)間轉(zhuǎn)接站、網(wǎng)絡(luò)協(xié)調(diào)站和遠(yuǎn)程移動(dòng)站組成。數(shù)據(jù)廣播數(shù)據(jù)廣播是利用數(shù)字編碼傳輸技術(shù)通過(guò)無(wú)線信道向多用戶傳輸信息的方式。它的基本原理是：運(yùn)用調(diào)制解調(diào)技術(shù)，將信息轉(zhuǎn)換為數(shù)字信號(hào)發(fā)射出去，再通過(guò)接收機(jī)對(duì)信號(hào)解調(diào)，還原為原來(lái)的數(shù)據(jù)。調(diào)頻解調(diào)占有較寬的頻帶，所以可以在不影響調(diào)頻廣播的前提下，利用空閑的頻帶（SCA副信道）傳輸信號(hào)，同調(diào)頻廣播一起發(fā)送出去。美國(guó)各大中城市中，已由80%以上的調(diào)頻廣播臺(tái)開(kāi)展SCA業(yè)務(wù)。日本已成功研制出調(diào)頻副信道固定接收信息的系統(tǒng)設(shè)備，移動(dòng)接收信息的系統(tǒng)已完成了基礎(chǔ)實(shí)驗(yàn)，除了用于傳輸時(shí)交通信息外，還傳輸股市行情等數(shù)據(jù)。數(shù)據(jù)廣播作為信息傳輸?shù)男路绞骄哂兴俣瓤?、傳輸成本低，可移?dòng)接收和多用戶接收等特點(diǎn)，可彌補(bǔ)其它傳輸方式的不足，尤其在我國(guó)通訊尚不十分發(fā)達(dá)的情況下，普及應(yīng)用數(shù)據(jù)廣播對(duì)有效提高信息利用率、擴(kuò)大信息傳播范圍、提高信息共享程度具有十分重要的意義。我國(guó)現(xiàn)有調(diào)頻臺(tái)4000多個(gè)，其中4千瓦以上的大功率調(diào)頻臺(tái)1000多個(gè)，每個(gè)調(diào)頻臺(tái)都有SCA復(fù)信道可利用，因此我國(guó)的SCA資源十分豐富。由于復(fù)信道是利用調(diào)頻臺(tái)原有的發(fā)射設(shè)備和天線，與調(diào)頻廣播同時(shí)發(fā)送的，這樣就為副信道的利用提供了便利。2.2.2查詢模塊查詢模塊主要是為了讓用戶根據(jù)其所掌握的部分不完備的信息，迅速查取用戶所想了解的相關(guān)所有詳細(xì)信息，它包括單位類別查詢、單位名稱查詢、單位地址查詢、單位電話查詢和單位名稱尾字查詢，也可在地圖上任意點(diǎn)中某一位置就能反映出該位置的單位，及相關(guān)的其它應(yīng)信息。單位類別查詢是根據(jù)單位的行業(yè)（如廠礦、郵電、機(jī)電、衛(wèi)生等）來(lái)實(shí)現(xiàn)。單位地點(diǎn)查詢是根據(jù)單位的郵政編碼和所在區(qū)、街道等信息來(lái)實(shí)現(xiàn)。單位名稱查詢是根據(jù)單位的名稱，也可以是單位的尾字來(lái)實(shí)現(xiàn)。單位電話號(hào)碼查詢是根據(jù)單位的電話號(hào)碼來(lái)實(shí)現(xiàn)。以上四種查詢可以是與的關(guān)系，若所掌握的單位信息不詳細(xì)則把符合該條件的所有單位都列出來(lái)共顧客來(lái)選擇。地圖查詢是顧客知道所查詢的單位在地圖上的位置時(shí)，通過(guò)把光標(biāo)移到該位置時(shí)，擊打鼠標(biāo)左鍵后系統(tǒng)自動(dòng)顯示出該單位的信息來(lái)實(shí)現(xiàn)。單位查詢模塊利用存儲(chǔ)在單位地圖數(shù)據(jù)庫(kù)中的信息，能迅速、有效地查出所需單位的信息。單位查詢模塊結(jié)構(gòu)圖如下：圖2.3路線綜合查詢系統(tǒng)中單位查詢模塊結(jié)構(gòu)圖2.2.3決策支持模塊決策支持模塊的功能包括最優(yōu)乘車線路的查詢、騎車路線查詢、時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)最優(yōu)的行車路線查詢及相關(guān)信息的顯示。此模塊接收駕駛員或游客的輸入數(shù)據(jù)，再根據(jù)計(jì)算機(jī)中所包含的有關(guān)道路、乘車的信息和出發(fā)地、目的地的位置數(shù)據(jù)，計(jì)算出最優(yōu)或準(zhǔn)最優(yōu)路線。然后，將最優(yōu)路線引導(dǎo)信息等顯示在屏幕上，配以文字說(shuō)明并打印出來(lái)。決策支持模塊是本文研究的重點(diǎn)，利用數(shù)字地圖數(shù)據(jù)庫(kù)和交通流量數(shù)據(jù)庫(kù)來(lái)計(jì)算出最佳路線。決策支持模塊結(jié)構(gòu)圖如下：圖2.4路線綜合查詢系統(tǒng)中路線決策模塊結(jié)構(gòu)圖目前，有很多最優(yōu)路線搜索算法，如比較典型的圖論中的Dijkstra算法，人工智能中的啟發(fā)式搜索算法等。對(duì)于算法的選擇，主要看其運(yùn)行效率計(jì)算時(shí)間的長(zhǎng)短，所得路線得最優(yōu)化程度。本文將在第四章進(jìn)行詳細(xì)的討論。一、乘車路線查詢模塊這是路線信息查詢系統(tǒng)系統(tǒng)的一個(gè)主要部分。在進(jìn)行搜索之前，首先由用戶輸入目的地。然后，乘車路線查詢模塊對(duì)游客計(jì)算出一條從出發(fā)點(diǎn)到達(dá)目的地，所經(jīng)過(guò)車站站點(diǎn)最少的最佳乘車路線。二、騎車路線查詢模塊騎車路線查詢模塊對(duì)騎車人提供一條從出發(fā)點(diǎn)到達(dá)目的地，所經(jīng)過(guò)的距離最短的最佳騎車路線。本文采用了人工智能中的啟發(fā)式搜索算法思想來(lái)實(shí)現(xiàn)。三、行車路線查詢模塊這是路線信息查詢系統(tǒng)系統(tǒng)的一個(gè)關(guān)鍵部分，對(duì)駕駛員計(jì)算出一條從出發(fā)點(diǎn)到達(dá)目的地的時(shí)間和消耗費(fèi)用綜合評(píng)價(jià)最優(yōu)的行車路線。本文采用了人工智能中的啟發(fā)式搜索算法，建立了一個(gè)關(guān)于時(shí)間、距離和消耗費(fèi)用的功能評(píng)價(jià)函數(shù)來(lái)實(shí)現(xiàn)。四、路線引導(dǎo)圖路線引導(dǎo)圖就是在路線搜索結(jié)束后，把路線圖打印出來(lái)并配以文字說(shuō)明，引導(dǎo)旅客或駕駛員下一步的路線如何走。對(duì)駕駛員提供行車路線引導(dǎo)圖，在地圖上把所經(jīng)過(guò)的路口以亮點(diǎn)的形式顯示出來(lái)，并在所經(jīng)過(guò)的道路中，標(biāo)出有明顯標(biāo)志的單位和所要經(jīng)過(guò)的街道名。對(duì)游客提供乘車路線引導(dǎo)圖，在地圖上把乘車所經(jīng)過(guò)的車站以點(diǎn)的顯示出來(lái)，并用文字說(shuō)明該站點(diǎn)的站名和所乘的車次，如果要轉(zhuǎn)車，則提供如何轉(zhuǎn)車的說(shuō)明。2.2.4服務(wù)查詢模塊服務(wù)信息查詢是為顧客提供了飛機(jī)時(shí)刻表及售票地點(diǎn)、火車時(shí)刻表及售票地點(diǎn)、賓館、旅店、名勝古跡、購(gòu)物場(chǎng)所、特殊服務(wù)（包括醫(yī)院、派出所、銀行及出租車汽車公司等信息）等查詢功能。此功能為顧客更好的、合理的安排游覽時(shí)間和先后次序提供了保障。圖2.5路線綜合查詢系統(tǒng)中服務(wù)查詢模塊結(jié)構(gòu)圖2.2.5人機(jī)界面人機(jī)界面是用戶與系統(tǒng)聯(lián)系的窗口。人機(jī)界面的好壞，決定著路線查詢系統(tǒng)能否被用戶接受，決定著系統(tǒng)的性能能否有效地發(fā)揮。人機(jī)界面的硬件組成一般包括：彩色顯示器、喇叭等輸出設(shè)備，鍵盤、鼠標(biāo)等輸入設(shè)備。通過(guò)人機(jī)界面，用戶可以查詢所需的信息（出發(fā)地、目的地等），并得到聲音提示和圖文并茂的信息顯示。隨著計(jì)算機(jī)性能的不斷提高和軟件技術(shù)的不斷發(fā)展，以WINDOWS為代表的多窗口圖形用戶界面正在成為應(yīng)用的主流。在圖形用戶界面下，用戶只要用鼠標(biāo)點(diǎn)幾下就可以完成大部分的操作。人機(jī)界面對(duì)于一個(gè)應(yīng)用系統(tǒng)來(lái)說(shuō)是十分重要的。應(yīng)用系統(tǒng)只有具備好的人機(jī)界面，才容易被用戶所接受，才能使其功能得到比較充分的發(fā)揮。在路線信息查詢系統(tǒng)中,實(shí)現(xiàn)了多文檔圖形用戶界面。容許用戶在一個(gè)應(yīng)用中使用多個(gè)文件。小結(jié)：路線信息查詢系統(tǒng)由查詢模塊、系統(tǒng)維護(hù)模塊、決策支持模塊、服務(wù)信息查詢模塊組成。本章對(duì)查詢模塊、系統(tǒng)維護(hù)模塊、服務(wù)信息查詢模塊的功能進(jìn)行了較為詳細(xì)的論述，對(duì)決策支持模塊只進(jìn)行了簡(jiǎn)單說(shuō)明。數(shù)字地圖數(shù)據(jù)庫(kù)是路線引導(dǎo)系統(tǒng)中使用的最重要的數(shù)據(jù)源，它在三大模塊中都要用到。下一章將對(duì)數(shù)字地圖數(shù)據(jù)庫(kù)的內(nèi)容、數(shù)字地圖數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)和創(chuàng)建數(shù)字地圖數(shù)據(jù)庫(kù)的步驟進(jìn)行說(shuō)明。決策支持模塊是本文研究的重點(diǎn)，這方面的內(nèi)容將在后面的章節(jié)進(jìn)行詳細(xì)的討論。數(shù)據(jù)庫(kù)的設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)庫(kù)的設(shè)計(jì)和具體實(shí)現(xiàn)是開(kāi)發(fā)道路查詢系統(tǒng)的基礎(chǔ)，良好的數(shù)據(jù)庫(kù)設(shè)計(jì)對(duì)圖形的快速顯示、提高搜索數(shù)據(jù)和運(yùn)算時(shí)間都占有重要的地位。隨著科學(xué)技術(shù)的進(jìn)步，探索、研究和實(shí)現(xiàn)數(shù)據(jù)庫(kù)的設(shè)計(jì)是我們的追求。3.1建立數(shù)字地圖數(shù)據(jù)庫(kù)3.1.1數(shù)字地圖數(shù)據(jù)庫(kù)總體概述道路數(shù)字地圖數(shù)據(jù)庫(kù)是路線綜合查尋系統(tǒng)的基礎(chǔ)。所謂數(shù)據(jù)庫(kù)就是相關(guān)數(shù)據(jù)的集合。一般道路數(shù)字地圖數(shù)據(jù)庫(kù)存儲(chǔ)的數(shù)據(jù)分為動(dòng)態(tài)和靜態(tài)兩種。例如，路線的位置、長(zhǎng)度是靜態(tài)數(shù)據(jù)，而交通流量是動(dòng)態(tài)數(shù)據(jù)。道路網(wǎng)絡(luò)可以看作為圖論中的圖。所有道路相當(dāng)于圖中的邊,或叫做鏈；所有路口相當(dāng)于圖的頂點(diǎn)，或叫做節(jié)點(diǎn)。節(jié)點(diǎn)和鏈組成的圖是實(shí)際地圖的一種向量表示。道路數(shù)字地圖數(shù)據(jù)庫(kù)是節(jié)點(diǎn)和鏈的數(shù)據(jù)的集合。節(jié)點(diǎn)和鏈都以記錄的形式存儲(chǔ)在數(shù)據(jù)庫(kù)中。節(jié)點(diǎn)的記錄包括以下數(shù)據(jù)項(xiàng)：節(jié)點(diǎn)號(hào)、節(jié)點(diǎn)名、位置坐標(biāo)、所在鏈號(hào)、轉(zhuǎn)彎限制等。鏈記錄中的數(shù)據(jù)項(xiàng)有：鏈號(hào)、鏈名、起止節(jié)點(diǎn)、鏈長(zhǎng)、車輛通過(guò)該鏈各個(gè)時(shí)刻的行駛時(shí)間等。地圖數(shù)據(jù)在邏輯組織時(shí)一般分為若干層，即有一個(gè)基本層和多個(gè)附加層?；緦又写鎯?chǔ)的是組要街道的數(shù)據(jù)，附加層中是有關(guān)某類實(shí)體的數(shù)據(jù)，如旅館、飛機(jī)場(chǎng)、火車站、單位等。各個(gè)附加層可以透明的疊加到基本層上。這種組織形式便于對(duì)地圖上的內(nèi)容進(jìn)行人為控制。為了減少冗余，有最大限度的靈活性，地圖數(shù)據(jù)在物理組織時(shí)一般分為多個(gè)文件。每個(gè)文件存儲(chǔ)一類數(shù)據(jù)，各個(gè)文件之間通過(guò)共同的數(shù)據(jù)項(xiàng)連接起來(lái)。1、數(shù)字公路地圖標(biāo)準(zhǔn)整個(gè)公路網(wǎng)絡(luò)由主公路網(wǎng)（BasicRoadNetwork）和全公路網(wǎng)（AllRoadNetwork）組成。主公路網(wǎng)由國(guó)家級(jí)和省級(jí)高速公路以及寬度對(duì)于等于5.5米的公路組成。全公路網(wǎng)包括非主公路網(wǎng)覆蓋下的全部道路且寬度大于3米的公路。2、位置和道路表示用正規(guī)化坐標(biāo)（X：0-10000；Y：0-10000）來(lái)表示實(shí)體的位置。道路網(wǎng)絡(luò)由節(jié)點(diǎn)和鏈組成。為了精確的說(shuō)明高速公路和汽車專用公路在不同方向上表示為兩條獨(dú)立的公路。節(jié)點(diǎn)可以是交叉路口、路尾、道路屬性變化點(diǎn)。主公路網(wǎng)使用四位數(shù)字的節(jié)點(diǎn)號(hào)碼，全公路網(wǎng)使用五位數(shù)字的節(jié)點(diǎn)號(hào)碼。鏈號(hào)由其端點(diǎn)節(jié)點(diǎn)號(hào)組合而成。3、數(shù)據(jù)庫(kù)的結(jié)構(gòu)數(shù)據(jù)庫(kù)由一組文件組成，每個(gè)文件包含表3.1所列的數(shù)據(jù)。表3.1數(shù)據(jù)庫(kù)層次4、數(shù)據(jù)來(lái)源獲取數(shù)據(jù)的來(lái)源有：a）1：25000的地形圖。對(duì)郊區(qū)、農(nóng)村用1：50000的地形圖b）公路交通管理局所提供的數(shù)據(jù)c）市城市建設(shè)地名辦公室所提供各單位地址及道路的名稱d）其它參考資料和數(shù)據(jù)道路數(shù)字地圖數(shù)據(jù)庫(kù)所包含的數(shù)據(jù)量大，數(shù)據(jù)類型多，需要大量的人力、物力來(lái)完成。開(kāi)發(fā)數(shù)據(jù)庫(kù)一般包括四個(gè)步驟：數(shù)據(jù)準(zhǔn)備、數(shù)據(jù)輸入、數(shù)據(jù)校驗(yàn)和數(shù)據(jù)維護(hù)。數(shù)據(jù)準(zhǔn)備即獲取原始的數(shù)據(jù)。一般從有關(guān)公路管理機(jī)構(gòu)、城市建設(shè)機(jī)構(gòu)、地名管理機(jī)構(gòu)和交通信息。數(shù)據(jù)輸入就是把原始數(shù)據(jù)輸入到計(jì)算機(jī)的過(guò)程。此過(guò)程要用數(shù)字化儀、掃描儀等設(shè)備。數(shù)據(jù)校驗(yàn)的主要任務(wù)是將輸入到計(jì)算機(jī)中的數(shù)據(jù)和原始數(shù)據(jù)相比較，并修正出現(xiàn)的錯(cuò)誤。數(shù)據(jù)校驗(yàn)是十分必要和關(guān)鍵的一步。一般在數(shù)據(jù)輸入過(guò)程的重要環(huán)節(jié)都要進(jìn)行數(shù)據(jù)校驗(yàn)，以確保數(shù)據(jù)的正確性和完整性。數(shù)據(jù)維護(hù)，指的是數(shù)據(jù)庫(kù)建成之后的后期工作，主要是數(shù)據(jù)的更新。這一階段工作量也很大，因?yàn)槊磕甓紩?huì)有舊路改建和新路建成。道路數(shù)字地圖數(shù)據(jù)庫(kù)的最主要的應(yīng)用是路線查詢系統(tǒng)。路線搜索，路線引導(dǎo)，地圖顯示等都需要道路數(shù)字地圖數(shù)據(jù)庫(kù)的支持。但是，隨著道路數(shù)字地圖數(shù)據(jù)庫(kù)的發(fā)展，它將開(kāi)始應(yīng)用到越來(lái)越多的領(lǐng)域：交通事故分析系統(tǒng)環(huán)境管理系統(tǒng)公路檢測(cè)系統(tǒng)等。不同的國(guó)家地區(qū)，不同的開(kāi)發(fā)者，根據(jù)當(dāng)?shù)氐奶厥馇闆r，針對(duì)不同的目的數(shù)據(jù)庫(kù)的內(nèi)容和組織形式也不盡相同。這就為數(shù)據(jù)庫(kù)間的數(shù)據(jù)共享和判斷數(shù)據(jù)庫(kù)的質(zhì)量好壞提出了麾題。為此，世界上一些發(fā)達(dá)國(guó)家制定了相應(yīng)的數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)來(lái)解決這個(gè)問(wèn)題。3.1.2數(shù)字地圖數(shù)據(jù)庫(kù)具體設(shè)計(jì)在建立數(shù)據(jù)庫(kù)之前，首先要進(jìn)行數(shù)據(jù)庫(kù)設(shè)計(jì)。這里主要指數(shù)據(jù)庫(kù)概念設(shè)計(jì)和邏輯設(shè)計(jì)。數(shù)據(jù)庫(kù)概念設(shè)計(jì)就是根據(jù)需求分析得到的材料，繪制出數(shù)據(jù)庫(kù)的初步設(shè)計(jì)。進(jìn)行概念設(shè)計(jì)通常所使用的概念數(shù)據(jù)模型是實(shí)體-關(guān)系模型，即E-R圖。數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的任務(wù)是根據(jù)設(shè)計(jì)的結(jié)果，設(shè)計(jì)數(shù)據(jù)庫(kù)的概念模式和外模式。采用自頂向下的設(shè)計(jì)方法，進(jìn)行概念設(shè)計(jì)，得到如圖3.2的E-R圖。圖3.1對(duì)數(shù)字地圖數(shù)據(jù)庫(kù)進(jìn)行概念設(shè)計(jì)所得到的E-R圖把E-R圖轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型后，有如下兩種關(guān)系：節(jié)點(diǎn)（節(jié)點(diǎn)號(hào)、節(jié)點(diǎn)橫坐標(biāo)、節(jié)點(diǎn)縱坐標(biāo)）2)鏈（鏈號(hào)、鏈名、鏈長(zhǎng)、起始節(jié)點(diǎn)號(hào)、終止節(jié)點(diǎn)號(hào)、禁行標(biāo)志節(jié)點(diǎn)、道路屬性）經(jīng)過(guò)綜合分析，將上面兩個(gè)關(guān)系轉(zhuǎn)化為Node和Link兩個(gè)表。它們的結(jié)構(gòu)如下：表3.2Node表的結(jié)構(gòu)3.1.3地圖矢量化1、矢量交通地圖的自動(dòng)生成方法為：①彩色掃描儀對(duì)交通地圖的掃描輸入。在分塊掃描時(shí)則依據(jù)不同情況進(jìn)行(按分塊區(qū)域坐標(biāo)數(shù)據(jù))自動(dòng)拼接或插入②道路特征指定(顏色或?qū)挾?與提取，矢量交通路線圖的自動(dòng)生成③路名與路況、總長(zhǎng)、交叉點(diǎn)等信息的計(jì)算機(jī)輔助輸入與基本數(shù)據(jù)庫(kù)建立。④精確位置修正。包括區(qū)域兩點(diǎn)式坐標(biāo)定位，比例尺豎向或橫向線性補(bǔ)償，局部路線修正等⑤允許在包括道路屬性的子功能上，由用戶增添對(duì)該條道路特定的信息標(biāo)題并輸入信息內(nèi)容，形成擴(kuò)展數(shù)據(jù)庫(kù)點(diǎn)信息生成方法為：①以屏幕上電子地圖為背景或通過(guò)輸入經(jīng)、緯度獲得代表不同對(duì)象的“最小點(diǎn)”位置，作為鼠標(biāo)觸發(fā)對(duì)象，實(shí)現(xiàn)對(duì)該點(diǎn)實(shí)際對(duì)象的信息輸入或輸出?！白钚↑c(diǎn)”顯示圖標(biāo)由用戶指定，其在屏幕上出現(xiàn)時(shí)占有的“面積”不受圖形放大或縮小的影響②點(diǎn)信息包括名稱、屬性等文字信息，并自動(dòng)進(jìn)行數(shù)據(jù)格式轉(zhuǎn)化形成壓縮形式的信息數(shù)據(jù)庫(kù)③點(diǎn)信息修改。實(shí)時(shí)打開(kāi)相應(yīng)的Windows應(yīng)用軟件進(jìn)行再編輯，形成修改后的信息數(shù)據(jù)庫(kù)文件。另外也可換位置修改。④允許對(duì)不同的點(diǎn)增加不同的信息標(biāo)題與信息內(nèi)容。當(dāng)然，將來(lái)輸出顯示該點(diǎn)信息時(shí)亦為相應(yīng)標(biāo)題與內(nèi)容3、臨時(shí)性點(diǎn)、路線草圖疊加考慮到有時(shí)在一張白紙上臨時(shí)畫上含有路線與代表大樓、機(jī)關(guān)、單位等“最小點(diǎn)”的示意性草圖。顯然，利用上述第⒈點(diǎn)的多用戶操作過(guò)程可形成該草的臨時(shí)性電子地圖數(shù)據(jù)文件。由于所給出的兩點(diǎn)坐標(biāo)不可能精確，及草圖不可能符合比例尺要求，而系統(tǒng)在輸出顯示時(shí)是以“電子地圖”疊加在原來(lái)的電子地圖上面的方式，如不加以修正，就會(huì)引起混亂。為了克服這種現(xiàn)象，系統(tǒng)利用其已形成的標(biāo)準(zhǔn)電子地圖數(shù)據(jù)庫(kù)，按新輸入的電子草圖的道路名稱、“最小點(diǎn)”名稱自動(dòng)核對(duì)并進(jìn)行位置修正，結(jié)果實(shí)際顯示的結(jié)果是在原電子地圖上精確地標(biāo)出了他要畫出的那些內(nèi)容(全部以高亮度或特殊顏色出現(xiàn))。對(duì)若干臨時(shí)性的“最小點(diǎn)”很可能原電子地圖不存在，經(jīng)上述修正過(guò)程之后，該“最小點(diǎn)”的位置相對(duì)于草圖上道路(兩側(cè))的位置關(guān)系而獲得了一定程度的修正，在用鼠標(biāo)對(duì)該點(diǎn)位置稍加修正，就會(huì)出現(xiàn)滿意的結(jié)果。4、實(shí)時(shí)信息疊加與立即使用，以及新信息的添加規(guī)則對(duì)已經(jīng)形成的矢量電子地圖及相應(yīng)的文字信息數(shù)據(jù)庫(kù)文件是作為永久性存儲(chǔ)并利用備份、糾錯(cuò)等功能對(duì)已形成的“精確地圖”嚴(yán)加維護(hù)。區(qū)域地圖顯示時(shí)用以形成顯示屏上的主體背景。對(duì)臨時(shí)性的草圖總是先形成臨時(shí)性的以矢量電子地圖為核心(和索引文件)的信息數(shù)據(jù)文件，并當(dāng)即調(diào)用原有“永久性”數(shù)據(jù)庫(kù)對(duì)新的“臨時(shí)性”數(shù)據(jù)文件進(jìn)行自動(dòng)修正(如上述第條所述)與疊加顯示。系統(tǒng)將自動(dòng)提取出臨時(shí)數(shù)據(jù)文件中的新信息，并添加進(jìn)“永久性”數(shù)據(jù)庫(kù)。兩種情況下，實(shí)時(shí)信息均可被使用。5、輔助決策功能系統(tǒng)使用戶在電子地圖顯示屏前用鼠標(biāo)隨時(shí)打開(kāi)任一條道路、任一“最小點(diǎn)”圖標(biāo)，在相應(yīng)的彈出窗口子菜單上提取所要求的各種信息，這是系統(tǒng)輸出時(shí)的基本功能。系統(tǒng)的輔助決策功能不是指這種功能，而是直接分為一般詢問(wèn)、高級(jí)決策與用戶指定決策三種形式的決策子菜單功能。一般詢問(wèn)包括詢問(wèn)任一點(diǎn)位置、任兩點(diǎn)距離、任一方塊面積、任一區(qū)域內(nèi)的特種對(duì)象信息(例如報(bào)警單位電話救護(hù)單位地址、電話等)。高級(jí)決策指帶有一定尋優(yōu)規(guī)劃，由系統(tǒng)實(shí)時(shí)按照已安排好的決策計(jì)算步驟，根據(jù)用戶所指點(diǎn)或路的輸入信息，從系統(tǒng)信息數(shù)據(jù)庫(kù)提取相關(guān)信息并經(jīng)計(jì)算顯示告訴用戶的有關(guān)“實(shí)時(shí)決策”結(jié)果，例如封閉指定點(diǎn)的所有交通要道列表，離指定點(diǎn)最近的救護(hù)單位信息，去該指定點(diǎn)的最優(yōu)路線等。用戶指定決策與高級(jí)決策類似，但系統(tǒng)必須按照用戶安排好的決策計(jì)算步驟來(lái)進(jìn)行決策并顯示相應(yīng)決策參考信息。數(shù)字化儀是進(jìn)行圖紙數(shù)字化的專用設(shè)備。AutoDesk公司的AutoCAD軟件是進(jìn)行計(jì)算機(jī)輔助設(shè)計(jì)的專用軟件，功能強(qiáng)大。提供一種數(shù)字化儀接口。通過(guò)此接口，可以實(shí)現(xiàn)地圖數(shù)據(jù)的計(jì)算機(jī)輸入。本系統(tǒng)在進(jìn)行地圖數(shù)字化時(shí)，所使用的數(shù)字化儀為SummagraphicBitPadOneModel11。該數(shù)字化儀圖形輸入板面積為420*330MM，有兩個(gè)定位器（點(diǎn)拾取設(shè)備），一個(gè)是四按鈕游標(biāo)，另一個(gè)是類似筆的觸筆。數(shù)字化儀通過(guò)電纜連接到計(jì)算機(jī)的一個(gè)串行輸入/輸出口上（缺省值為COM1）。重新配置。配置過(guò)程如下：（1）啟動(dòng)AutoCAD，進(jìn)入主菜單。0.ExitAutoCAD1.BeginaNewDrawing2.EditanExistingDrawing3.PlotaDrawing4.PrinterPlotaDrawing5.ConfigureAutoCAD6.FileUnlashes7.CompileShape/FontDescriptionfile8.ConvertOldDrawingFile9.RecoverDamagedDrawingEnterSelection:選擇5，進(jìn)入AutoCAD配置菜單。0.ExitToMainMenu1.ShowCurrentConfiguration2.AllowDetailedConfiguration3.ConfigureVideoDisplay4.ConfigureDigitizer5.ConfigurePlotter6.ConfigurePrinterPlotter7.ConfigureSystemConsole8.ConfigureOperatingParametersEnterSelection:0選擇4（配置數(shù)字化儀），屏幕出現(xiàn)可用的數(shù)字化儀一覽表。從列表中選擇SummagraphicBitPad，然后回車，從型號(hào)列表中選擇OneModel11。保存配置，退出AutoCAD。再次啟動(dòng)AutoCAD，配置生效。在啟動(dòng)配置好的AutoCAD后，從菜單中選擇“1”，進(jìn)入圖形編輯窗口。此刻還不能馬上進(jìn)行數(shù)字化工作，必須首先用TABLET命令重新配置數(shù)字化儀圖形輸入板并進(jìn)行校準(zhǔn)。在一般情況下，數(shù)字化圖形板有效區(qū)域的大部分都用作AutoCAD的菜單區(qū)使用。現(xiàn)在要把整個(gè)有效區(qū)域用作圖形數(shù)字化之用，所以需要重新配置數(shù)字化圖形板。否則，就不能拾取屏幕指點(diǎn)區(qū)以外的點(diǎn)。這時(shí)，圖形板的校準(zhǔn)工作完成。再次執(zhí)行TABLE命令，從“Option”中選擇“On”，打開(kāi)圖形輸入板方式，這時(shí)就可以進(jìn)行正子真正的數(shù)字化工作。在數(shù)字化時(shí)，對(duì)于線狀實(shí)體（公路、鐵路、河流等）使用“LINE”命令，對(duì)于點(diǎn)狀實(shí)體（建筑物等）使用“POINT”命令。在數(shù)字化完成后，以圖形交換文件格式把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中。由于所使用的圖形輸入板比較小，地圖比較大，一次無(wú)法完成全部地圖的數(shù)字化。解決的方法是，把整個(gè)地圖分成幾個(gè)小塊，對(duì)每個(gè)小塊分別進(jìn)行數(shù)字化。在更換數(shù)字化區(qū)域時(shí)，必須重新使用TABLE命令，使地圖坐標(biāo)和屏幕坐標(biāo)對(duì)應(yīng)起來(lái)。3.1.4數(shù)據(jù)轉(zhuǎn)換用AutoCAD把地圖數(shù)字化之后，生成圖形交換文件。圖形交換文件中存儲(chǔ)的時(shí)點(diǎn)的坐標(biāo)?，F(xiàn)在的任務(wù)是要把圖形交換文件中有用的數(shù)據(jù)轉(zhuǎn)換PowerBuilder數(shù)據(jù)庫(kù)中。下面說(shuō)明一下圖形交換文件的結(jié)構(gòu)。圖形交換文件是ASCII文件，擴(kuò)展名為DXF。它由五個(gè)段組成：標(biāo)題段、表段、塊段、實(shí)體段、和文件結(jié)束。標(biāo)題段由描述圖形信息的一組標(biāo)題變量組成，標(biāo)題變量的值確定圖形的參數(shù)設(shè)置和當(dāng)前狀態(tài)。表段包含了若干個(gè)表，每個(gè)表又包含可變數(shù)目的表項(xiàng)塊段包括所有的塊定義，它記錄了當(dāng)前的圖層名、塊的種類、塊的插入基點(diǎn)和組成塊的所有成員。實(shí)體段記錄了每個(gè)實(shí)體的名稱、圖層名、線型名、基面高度、厚度和有關(guān)的幾何數(shù)據(jù)。文件的最小組成單元是組（Group），每組占兩行。第一行為組代碼，第二行是組值，組值的數(shù)據(jù)類型取決于組代碼的值。組代碼與組值之間的關(guān)系列于表3.4中。表3.5組代碼和組值對(duì)應(yīng)關(guān)系表3.6組代碼的意義根據(jù)組代碼的值，可以容易地從圖形轉(zhuǎn)換文件中讀出需要的數(shù)據(jù)。在已知圖形轉(zhuǎn)換文件格式和要轉(zhuǎn)換成的數(shù)據(jù)庫(kù)文件格式的情況下，可按如下步驟進(jìn)行轉(zhuǎn)換：1、打開(kāi)準(zhǔn)備接收?qǐng)D形轉(zhuǎn)換文件中的信息數(shù)據(jù)庫(kù)。2、打開(kāi)圖形轉(zhuǎn)換文件，準(zhǔn)備讀取數(shù)據(jù)。3、從圖形轉(zhuǎn)換文件中讀取一行數(shù)據(jù)，賦給變量TEMPDATA。如果其值不等于ENTITIES，則循環(huán)，直到相等為止，即找到實(shí)體段的開(kāi)始。4、按照第三步的方法，從實(shí)體段中找到值為L(zhǎng)INE的行，它標(biāo)志著一條直線的開(kāi)始。5、讀取數(shù)據(jù)，直到等于10。組代碼為10時(shí)，它的組值是直線端點(diǎn)X坐標(biāo)值。在X坐標(biāo)后面一行是組代碼20，它的組值是直線端點(diǎn)的Y坐標(biāo)值。6、讀取直線另一端點(diǎn)的坐標(biāo)。7、將得到的直線坐標(biāo)數(shù)據(jù)寫入數(shù)據(jù)庫(kù)文件中。其中，點(diǎn)的坐標(biāo)值寫入NODES表中，而把直線的起點(diǎn)和終點(diǎn)信息記錄在LINK表中。8、重復(fù)執(zhí)行4-7步，TEMPDATA=“ENDSEC”。9、關(guān)閉所有的文件，然后結(jié)束在把圖形轉(zhuǎn)換文件中的數(shù)據(jù)全部輸入數(shù)字地圖數(shù)據(jù)庫(kù)之后，數(shù)據(jù)庫(kù)并沒(méi)有完全建好，還需要進(jìn)一步的處理，以滿足整個(gè)系統(tǒng)的需要。還要做以下的工作：·輸入節(jié)點(diǎn)類型信息。因?yàn)樵趫D形轉(zhuǎn)換文件中沒(méi)有記錄有關(guān)節(jié)點(diǎn)類型的數(shù)據(jù)，必須手工處理?！で宄齆ODES表中的冗余記錄。一條直線有兩個(gè)端點(diǎn)，兩條直線相交則有一個(gè)公共端點(diǎn)。在數(shù)據(jù)轉(zhuǎn)換過(guò)程中，只是把所有的點(diǎn)都寫入數(shù)據(jù)庫(kù)中，這樣公共端點(diǎn)接被存儲(chǔ)多次，造成空間浪費(fèi)，必須清除?！ぬ畛銵INK表的POINTONLINK字段。在數(shù)據(jù)轉(zhuǎn)換時(shí)，在LINK表中只記錄了路段的起點(diǎn)和終點(diǎn)，而沒(méi)有記錄路段的形節(jié)點(diǎn)?！ぽ斎肫渌畔?。如道路的長(zhǎng)度、寬度、地址、時(shí)間表等。上面的工作全部完成之后，一個(gè)比較完整的數(shù)字地圖數(shù)據(jù)庫(kù)就建成了。系統(tǒng)的其它模塊都是以這個(gè)數(shù)據(jù)庫(kù)作為基本的數(shù)據(jù)來(lái)源，是以后工作的基礎(chǔ)。3.1.5顯示地圖與文字說(shuō)明路線信息查詢系統(tǒng)向用戶提供圖形化地圖并且能在地圖上顯示各種文字信息說(shuō)明。通常，在屏幕上顯示數(shù)字地圖的方法是：從數(shù)據(jù)庫(kù)中讀取路段的起點(diǎn)和終點(diǎn)的坐標(biāo)，然后在屏幕上畫線，直到整幅地圖畫完。但是，這種方法的致命弱點(diǎn)是速度太慢，不能滿足應(yīng)用要求。為此使用一種新的方法（圖元文件法）事在必行。一、圖元文件的建立圖元文件是建立所需文本或圖象的GDI命令的集合。圖元文件是用二進(jìn)制編碼的GDI函數(shù)集，通過(guò)產(chǎn)生一個(gè)圖元文件設(shè)備環(huán)境來(lái)產(chǎn)生一個(gè)圖元文件，這些GDI調(diào)用實(shí)際上并不做任何工作，而是把它們存放在圖元文件中。在關(guān)閉圖元文件設(shè)備環(huán)境時(shí)，得到圖元文件的一個(gè)句柄，然后可以在實(shí)際設(shè)備環(huán)境上操作圖元文件時(shí)，WINDOWS將圖元文件分解為記錄并使用每個(gè)記錄中的參數(shù)執(zhí)行合適的函數(shù)。圖元文件和位圖文件相比，有幾個(gè)顯著的優(yōu)點(diǎn)：占用內(nèi)存空間小，比位圖具備更大的設(shè)備獨(dú)立性，可以進(jìn)行無(wú)級(jí)放大而不失真。圖元文件不及位圖文件的一點(diǎn)是顯示速度稍慢。通過(guò)在中直接調(diào)用函數(shù)，大大增強(qiáng)了自身功能和編程的靈活性。使用函數(shù)的另一個(gè)優(yōu)點(diǎn)是可以是程序執(zhí)行速度明顯加快。二、圖元文件的顯示圖元文件建立好后，如何將其顯示在屏幕，在給出具體的顯示之前，首先要了解WINDOWS的坐標(biāo)系統(tǒng)和映射方式。為了保持設(shè)備無(wú)關(guān)性，在WINDOWSGDI函數(shù)中，所使用的坐標(biāo)都是以“邏輯單元”為單位的。WINDOWS必須把這些邏輯單元轉(zhuǎn)換成設(shè)備單元，即象素。這種轉(zhuǎn)換是由映射方式、窗口和視口原點(diǎn)及窗口和視口限度控制的，映射方式也影響原點(diǎn)和X軸及Y軸的定位。映射方式定義了WINDOWSGDI如何將函數(shù)中給出的邏輯坐標(biāo)映射成設(shè)備坐標(biāo)。其中，MM_TEXT為缺省的映射方式。在這種方式下，邏輯單元和物理單元相等，可以直接以象素為單位進(jìn)行工作。MM_TEXT映射方式所使用的坐標(biāo)系如圖3.3所示：左上角為坐標(biāo)原點(diǎn)(0,0)，X軸的坐標(biāo)自左向右增加，Y軸坐標(biāo)自上而下遞增。這種坐標(biāo)系統(tǒng)符合人們的習(xí)慣。第八種映射方式為MM_ANISOTROPIC，它是一種“不受限制”方式，可以改變窗口和視口的限度值，使X軸和Y軸上的邏輯單位具有不同的物理量綱。在后面的地圖顯示子程序中，將用到這種方式。WINDOWS使用下面的兩組公式進(jìn)行邏輯坐標(biāo)和設(shè)備坐標(biāo)的相互轉(zhuǎn)換。表3.7大表在大多數(shù)映射方式中，限度值是由映射方式隱含的并且不能改變，每個(gè)限度值本身意義，但由它構(gòu)成的四個(gè)比值（xViewExt/xWinExt、yViewExt/yWinExt、xWinExt/xViewExt、yWinExt/yViewExt）是用來(lái)對(duì)邏輯單位進(jìn)行擴(kuò)展或壓縮的比例因子。在地圖數(shù)字化時(shí)所采用的坐標(biāo)系如圖所示的坐標(biāo)系。圖3.2圖標(biāo)所以在顯示地圖時(shí)，還必須使用同樣的坐標(biāo)系，即左下角為坐標(biāo)原點(diǎn)（0,0）,x軸坐標(biāo)向右增加，y軸坐標(biāo)向上增加。所以，必須把Windows默認(rèn)映射方式所使用的坐標(biāo)系轉(zhuǎn)換成圖3.4所示的坐標(biāo)系。在完成坐標(biāo)系轉(zhuǎn)換之后，調(diào)用函數(shù)即可把圖元文件中的內(nèi)容重放出來(lái)。在上面的程序中，Soure是一個(gè)圖片框?qū)ο蟮拿Q。在連續(xù)調(diào)用SetMapMode（設(shè)置映射方式）、SetWindowExt（設(shè)置窗口限度值）、SetViewportExt（設(shè)置視口限度值）、SetViewportOrg（設(shè)置視口原點(diǎn)）四個(gè)函數(shù)之后，圖片框被置于正確的坐標(biāo)系之下。圖片框的左下角為坐標(biāo)原點(diǎn)（0,0）右上角坐標(biāo)為（MapWidth,MapHeight），如圖3.5所示。通過(guò)調(diào)用PlayMetaFile函數(shù)，整幅地圖在圖片框中完整的重畫出來(lái)。圖3.3圖片框在坐標(biāo)系的位置（MapWidth,MapHeight）三、地圖瀏覽與縮放功能的實(shí)現(xiàn)在路線信息查詢系統(tǒng)中，提供了地圖瀏覽和局部放大功能。實(shí)現(xiàn)此功能的基本方法是：在屏幕工作區(qū)放置兩個(gè)大小不同的顯示“窗口”（實(shí)際是兩個(gè)圖片框，分別叫做Picture1和Picture2,Picture1為較小的圖片框）；在較小的窗口中顯示整幅地圖，在較大的窗口中顯示地圖的一個(gè)局部；用鼠標(biāo)單擊較小窗口的一點(diǎn)，則用了一個(gè)縮放因子來(lái)動(dòng)態(tài)調(diào)整地圖的放大倍數(shù)。實(shí)現(xiàn)地圖瀏覽與縮放功能所依據(jù)的基本原理是：1、圖元文件的放大不失真特性。2、Windows映射方式及坐標(biāo)系變換原理。圖3.4地圖瀏覽與放大原理示意圖按照地圖流覽與放大功能的基本實(shí)現(xiàn)思路，用鼠標(biāo)單擊Picture1中任意一點(diǎn)P1(x1,y1)，則P1點(diǎn)應(yīng)該顯示在Picture2的中心位置P2(x2,y2)點(diǎn)處。也就是說(shuō)，點(diǎn)p1和點(diǎn)p2的邏輯坐標(biāo)是一樣的。Picturel中的某一點(diǎn)和Picture2的中心點(diǎn)的這種約束對(duì)應(yīng)顯示關(guān)系，可分為以下幾步來(lái)實(shí)現(xiàn)：所使用的符號(hào)意義如表3.8所示。表3.8表數(shù)整幅地圖顯示于圖3.6所示的虛擬圖片框內(nèi)，但只有落在實(shí)線框中的部分是可見(jiàn)的。前面所述的變換過(guò)程，實(shí)際是在改變虛擬圖片框的大小，從而使實(shí)線框中可見(jiàn)部分的放大比例得到改變：圖3.5圖四、地圖信息的文字顯示對(duì)于乘車路線，則在地圖上把所經(jīng)過(guò)的車站的位置顯示出來(lái)，并把所經(jīng)過(guò)的站點(diǎn)在圖的下方配以文字說(shuō)明；對(duì)于行車路線，則把所經(jīng)過(guò)的道路口，以一個(gè)點(diǎn)的形式顯示出來(lái)，在圖的下方把兩點(diǎn)之間所經(jīng)過(guò)的街道名稱顯示出來(lái)。3.1.6建立單位地圖數(shù)據(jù)庫(kù)對(duì)單位地圖數(shù)據(jù)庫(kù)要求包括單位的郵政編碼、電話號(hào)碼、地址、行業(yè)類別、在地圖上的坐標(biāo)等信息。數(shù)據(jù)庫(kù)的結(jié)構(gòu)如下：表3.9單位表的結(jié)構(gòu)3.1.7建立車站地圖數(shù)據(jù)庫(kù)對(duì)車站地圖數(shù)據(jù)庫(kù)包括各個(gè)車站的站點(diǎn)及每個(gè)站點(diǎn)所經(jīng)過(guò)的車次、名稱和站名等信息。采用自頂向下的設(shè)計(jì)方法，進(jìn)行概念設(shè)計(jì)，得到如圖3.2的E-R圖。圖3.7對(duì)車站站點(diǎn)進(jìn)行概念設(shè)計(jì)所得到的E-R圖把E-R圖轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型后，有如下三種關(guān)系：1)節(jié)點(diǎn)（節(jié)點(diǎn)號(hào)、節(jié)點(diǎn)橫坐標(biāo)、節(jié)點(diǎn)縱坐標(biāo)、經(jīng)過(guò)該點(diǎn)的所有車次）。2)鏈（鏈號(hào)、起始節(jié)點(diǎn)號(hào)、終止節(jié)點(diǎn)號(hào)）3)轉(zhuǎn)車（編號(hào)、節(jié)點(diǎn)號(hào)、下車車次、下車站名、上車車次、上車站名、轉(zhuǎn)車說(shuō)明）經(jīng)過(guò)綜合分析，將上面兩個(gè)關(guān)系轉(zhuǎn)化為CNode、CLink和Change三個(gè)表。它們的結(jié)構(gòu)如下：表3.10CNode表的結(jié)構(gòu)表3.11Clink表的結(jié)構(gòu)3.1.8建立交通流量數(shù)據(jù)庫(kù)對(duì)交通流量數(shù)據(jù)庫(kù)，則把每條道路按一天24小時(shí)的交通流量的變化劃分為一個(gè)個(gè)的時(shí)間段，計(jì)算出每段時(shí)間車輛通過(guò)該道路的時(shí)間。當(dāng)以后通訊條件改善時(shí)，把這個(gè)數(shù)據(jù)庫(kù)變成時(shí)實(shí)的交通流量數(shù)據(jù)庫(kù)采用自頂向下的設(shè)計(jì)方法，進(jìn)行概念設(shè)計(jì)，得到如圖3.2的E-R圖圖3.8對(duì)交通流量進(jìn)行概念設(shè)計(jì)所得到的E-R圖把E-R圖轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型后，有如下兩種關(guān)系：時(shí)間（鏈號(hào)、各時(shí)間段通過(guò)該道路的時(shí)間）費(fèi)用（鏈號(hào)、各時(shí)間段通過(guò)該道路所需費(fèi)用）經(jīng)過(guò)綜合分析，將上面兩個(gè)關(guān)系轉(zhuǎn)化為Timecost、Change兩個(gè)表。因?yàn)樗鼈兘Y(jié)構(gòu)類似，所以只寫一個(gè)表，表的結(jié)構(gòu)如下：表3.13交通流量Timecost表的結(jié)構(gòu)小結(jié)：本章對(duì)路線信息查詢系統(tǒng)中數(shù)據(jù)庫(kù)的設(shè)計(jì)和開(kāi)發(fā)過(guò)程進(jìn)行了詳細(xì)論述，在下一章將對(duì)最優(yōu)路線搜索算法作了重點(diǎn)討論。建立數(shù)字地圖數(shù)據(jù)庫(kù)是整個(gè)系統(tǒng)開(kāi)發(fā)的基礎(chǔ)。建庫(kù)過(guò)程包括數(shù)據(jù)庫(kù)設(shè)計(jì)、地圖數(shù)字化和數(shù)據(jù)輸入等步驟。利用建立好的數(shù)字地圖數(shù)據(jù)庫(kù)在路線信息查詢系統(tǒng)中實(shí)現(xiàn)了數(shù)字地圖的顯示及瀏覽放大功能。第四章路線搜索算法本節(jié)主要討論應(yīng)用于路線搜索子系統(tǒng)中的算法。路線搜索子系統(tǒng)是路線信息查詢系統(tǒng)的一個(gè)關(guān)鍵部分。它必須要滿足一定的實(shí)時(shí)性要求，既在給定的時(shí)間內(nèi)能夠找出一條最優(yōu)或準(zhǔn)最優(yōu)路線。道路網(wǎng)絡(luò)可以抽象成圖論中的圖。道路的交叉路口可看作是圖的頂點(diǎn)（或稱為節(jié)點(diǎn)），兩個(gè)交叉路口之間的路段可看作圖的邊（后稱為鏈）。這樣，道路網(wǎng)絡(luò)中求解最優(yōu)路線的問(wèn)題就轉(zhuǎn)化為圖論中的最短路徑問(wèn)題。目前，已經(jīng)有許多較成熟的算法來(lái)解決圖的搜索問(wèn)題。其中，最著名的算法是Dijkstra算法。此外，深度優(yōu)先算法和廣度優(yōu)先算法也被廣泛應(yīng)用。這些算法有個(gè)共同的缺點(diǎn)，就是計(jì)算時(shí)間隨節(jié)點(diǎn)數(shù)的增加而呈指數(shù)增長(zhǎng)。本節(jié)在對(duì)啟發(fā)式搜索算法進(jìn)行實(shí)驗(yàn)研究的基礎(chǔ)上，結(jié)合神經(jīng)網(wǎng)絡(luò)中的遺傳算法，提出了一個(gè)新的方法，稱做啟發(fā)式遺傳算法。在討論具體算法之前，先說(shuō)明一下數(shù)據(jù)庫(kù)中的數(shù)據(jù)在內(nèi)存中是如何存儲(chǔ)的。為了快速方便的讀取數(shù)據(jù)庫(kù)中的數(shù)據(jù)，定義了如下的記錄結(jié)構(gòu)存儲(chǔ)每個(gè)節(jié)點(diǎn)的信息。通過(guò)訪問(wèn)相應(yīng)節(jié)點(diǎn)記錄的各個(gè)域就可以得到所需的數(shù)據(jù)。4.1啟發(fā)式算法啟發(fā)式搜索是人工智能領(lǐng)域中一種基本的問(wèn)題解決方法。這種方法使用啟發(fā)式知識(shí)來(lái)改善搜索算法的性能。在啟發(fā)式算法中，啟發(fā)式知識(shí)通過(guò)評(píng)價(jià)函數(shù)f(n)來(lái)表示。f(n)的值等于經(jīng)過(guò)節(jié)點(diǎn)n的最優(yōu)路徑的實(shí)際權(quán)值。f(n)可看作是兩部分相加的和F(n)=g(n)+h(n)其中，g(n)是從起始位置到節(jié)點(diǎn)n的最優(yōu)路徑權(quán)值。h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的權(quán)值。如果定義f’(n)、g’(n)和h’(n)分別為f(n)、g(n)和h(n)的估計(jì)值。那么f’(n)=g’(n)+h’(n)其中，g’(n)可以正確地計(jì)算出來(lái)，即g’(n)=g(n)。h’(n)是從節(jié)點(diǎn)n到終點(diǎn)的估計(jì)權(quán)值。如果對(duì)于圖中任意一個(gè)節(jié)點(diǎn)，h’(n)小于等于h(n)均成立，那么稱啟發(fā)式算法為A*算法。A*算法已經(jīng)被證明是可采納的。即只要存在一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，A*設(shè)法就可以找到它。啟發(fā)式搜索算法比傳統(tǒng)的Dijkstra算法所擴(kuò)展的節(jié)點(diǎn)數(shù)要少的多。在此算法的每一步，都是選擇“最好”的節(jié)點(diǎn)進(jìn)行擴(kuò)展。所謂“最好”是指其f’(n)的值最小。當(dāng)?shù)竭_(dá)目標(biāo)節(jié)點(diǎn)時(shí)，最優(yōu)路徑也就找道了。4.2改進(jìn)的啟發(fā)式算法雙向Dijkstra算法：雙向算法已用于操作查找分析，見(jiàn)[LR89.Ma]。雙向查找算法有兩部分。第一階段我們交替兩個(gè)無(wú)向查找：一個(gè)從S開(kāi)始，生長(zhǎng)成S的一組點(diǎn)，這組點(diǎn)到S的最小路徑是已知的；第二個(gè)包括d的一組點(diǎn)D，D中的點(diǎn)到d的最小距離是已知的。交替地給S和D加入結(jié)點(diǎn)，直至S到D的邊產(chǎn)生。因此最短路徑位于S和D地查找樹(shù)中和S到D的邊。算法的幾何意義如下：我們?cè)趕和t上產(chǎn)生兩個(gè)球，每一步，球增加一個(gè)單元。當(dāng)兩個(gè)球撞破時(shí)，算法結(jié)束：即存在一頂點(diǎn)是兩個(gè)球的公共頂。路徑s~v~t為s到t的最短路徑，v是公共頂。引理：①s到t的最短路徑至多有一條從S到D集合的邊。②w(s-k-t)≤2w(s-t)證明：①w(s-k-t)是s到t過(guò)k的最短路徑的權(quán)。讓P=s~x-a-y~t表示最短路徑含另一條邊。從Dijkstra算法可得到不等式：w(s-x)+w(xa)≥w(s,k)。w(t-y)+w(y-a)≥w(y,k)。因此，w(s-x)+w(x-a)+w(ty)+w(y-a)≥w(s,k)+w(y,k),矛盾。②令s到t的最短路徑為s~x-y~t,x∈S,y∈D.可得以下不等式w(s,k)≤w(s-x)+w(x-y)；w(y,k)≤w(t-y)+w(y-x)?！鄔(s,k)+w(k,y)≤w(s-x)+w(x-y)+w(t-y)+w(y-x)≤2w(sx-y-t)定理8.2讓a,b,c的常量定義n結(jié)點(diǎn)有向圖的一組可能分配。邊(i,j)有可能(alogn)/b被表示。對(duì)這些邊，邊長(zhǎng)度le對(duì)可能分布是獨(dú)立的，密度函數(shù)fe界于b,c之間。查找s-t的最短路徑的雙向Dijkstra時(shí)間為O(√n)。小結(jié)：本章對(duì)最優(yōu)路線搜索算法作了重點(diǎn)討論。第五章建立符合我國(guó)國(guó)情的路線信息查詢系統(tǒng)國(guó)外已經(jīng)有了較成熟的路線信息查詢系統(tǒng)。但是，如果把這些系統(tǒng)直接拿到我國(guó)使用，不一定適合我國(guó)國(guó)情。因?yàn)槲覈?guó)的交通有其自己的特點(diǎn)，在建立路線信息查詢系統(tǒng)時(shí)必須考慮我國(guó)交通狀況。本章將對(duì)我國(guó)的交通現(xiàn)狀及特點(diǎn)進(jìn)行分析，然后提出對(duì)如何建立合適我國(guó)國(guó)情的路線信息查詢系統(tǒng)的一些觀點(diǎn)和看法。5.1我國(guó)路線查詢形狀和特點(diǎn)分析改革開(kāi)放十幾年來(lái)，我國(guó)的經(jīng)濟(jì)發(fā)展取得了舉世矚目的成就。與此同時(shí)，我國(guó)的城市和交通建設(shè)也獲得了很大的發(fā)展。國(guó)家投入巨資于市政建設(shè)、建設(shè)公路、鐵路等交通基礎(chǔ)設(shè)施，使路線查詢系統(tǒng)為人們所需。同時(shí)，在各大中城市，由于各種機(jī)動(dòng)車輛迅速增加，尤