資源描述：
《基于最短路徑查詢的城市公交網(wǎng)絡(luò)拓?fù)浣Ｑ芯俊酚蓵T上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、遙感信息理論研究$##$;"基于最短路徑查詢的城市公交網(wǎng)絡(luò)拓?fù)浣Ｑ芯筷懼?，錢翔東，張登榮（浙江大學(xué)地理科學(xué)系，杭州!"##$%）摘要：最短路徑分析是地理信息系統(tǒng)（&’(）中網(wǎng)絡(luò)分析的一項重要功能，等價于圖論中的節(jié)點間求解最短路徑問題。對地理網(wǎng)絡(luò)進行地理分析和建模，以實現(xiàn)最短路徑搜索已經(jīng)有大量論文討論，但是專門針對城市公交網(wǎng)絡(luò)的建模和路徑尋優(yōu)，則少鮮有研究，而且已有的一些網(wǎng)絡(luò)模型也不能直接應(yīng)用到公交網(wǎng)絡(luò)尋優(yōu)中。本文應(yīng)用圖論理論，討論公共交通網(wǎng)絡(luò)的拓?fù)浣?，實現(xiàn)公交網(wǎng)絡(luò)最優(yōu)路徑的查詢。關(guān)鍵詞：&’(網(wǎng)絡(luò)建模；公共交通網(wǎng)絡(luò)（公交網(wǎng)絡(luò)
2、）；網(wǎng)絡(luò)尋優(yōu)（最短路徑）中圖分類號：)$*"文獻標(biāo)識碼：+文章編號："###,!"%%（$##$）-.,##"",#/算法進行優(yōu)化，以提高運行效率。其中被廣泛采用"引言并且研究最多的是4256789:算法。第二類是對圖的對網(wǎng)絡(luò)進行地理分析和模型化是地理信息系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的研究［"#］，這些數(shù)據(jù)結(jié)構(gòu)都以邊和節(jié)點結(jié)（&’(）中網(wǎng)絡(luò)分析的一項重要內(nèi)容［"#］。網(wǎng)絡(luò)主要指構(gòu)為基礎(chǔ)。第三類是關(guān)于道路網(wǎng)絡(luò)、管道或管線網(wǎng)各種實際的道路（如鐵路、城際鄉(xiāng)間公路、城市道路絡(luò)圖的建模［.!%］。這些模型和算法研究針對特定的等）網(wǎng)絡(luò)和城市管線網(wǎng)（如點里網(wǎng)
3、、給排水管網(wǎng)、電話實際網(wǎng)絡(luò)，沒有可能直接應(yīng)用于公交網(wǎng)絡(luò)尋優(yōu)，因為網(wǎng)等）等［"］。網(wǎng)絡(luò)建模指把實際網(wǎng)絡(luò)抽象成圖論中公交網(wǎng)絡(luò)不同于道路網(wǎng)絡(luò)。具有拓?fù)湫再|(zhì)的網(wǎng)絡(luò)圖。&’(網(wǎng)絡(luò)分析中的實際應(yīng)$公交網(wǎng)絡(luò)的特點用，如道路交通網(wǎng)絡(luò)最短路徑查詢、電子導(dǎo)游圖、城市管線管理系統(tǒng)、""#電子報警系統(tǒng)等，其實都等價公交網(wǎng)絡(luò)有如下特點：于圖論中的節(jié)點間求解最短路徑問題［$!/］。（"）連通性一個圖!"（#，$）是由有窮而非空的頂點集城市道路網(wǎng)絡(luò)中的道路交叉點無差異地連接著#和邊集$所組成，如果邊是頂點的有序?qū)Γ?&，與該路口連通的多條路段，而兩路公交線路
4、的站點%’），（%&，%’）!$；%&，%’!#，則說這個圖是有向在同一點時，同路公交路段之間的連通性和不同公的［$，!］。交線路的連通性是有差別的，這是因為兩路不同公(，)是兩個非空集合，*，+分別是#到(，$到交線路在空間上的同一站點的連通，要換車而增加)的兩個映射，則稱有序四元組!"（#，$，(，)）了時間消耗。另外多條公交線路雖然可以相交于空為加權(quán)圖，(，)稱為頂點的權(quán)和邊的權(quán)。間上的同一個點，但是該點不一定是公交?？空军c，圖!的一個邊序列0，0，0，?，0，或者說一個或者不是同時有站點，因而不同公交線路在此是不#"$,
5、頂點序列%，%，%，?，%稱為圖從%到%的一條連通的。#"$,#,路經(jīng)；從%到%的所有路徑中，權(quán)-（%，%）最小（$）節(jié)點的特性#,#,的路徑稱為從%到%的最短路徑，記為（%，%）。雖然不同的公交線路在行程上有重疊，但是各#,#,其長度為：自的站點不可能是完全的幾何重疊，因而要做有效-（%#，%,）"123｛-&（%#，%,）.%#，%,!#；&""，$，?｝的站點間疊加分析。在實際通勤中必然要求在不同最短路徑問題已經(jīng)有大量的研究論文，這些論的公交線路之間實現(xiàn)換車以到達目的地，這就要求文大致可分為三類。第一類是最短路徑的算法研相
6、對應(yīng)的網(wǎng)絡(luò)圖上不同屬性的邊在節(jié)點上的連通，究［.!*］，討論最短路徑算法及根據(jù)實際問題對經(jīng)典這是公共交通網(wǎng)絡(luò)分析的意義。在公交網(wǎng)絡(luò)疊加分析時，要求把空間上相近的異線站點合理抽象成圖收稿日期：$##$,#","$作者簡介：陸忠（"*%"!），男，浙江大學(xué)地球科學(xué)系碩士研究生，主要從事&’(應(yīng)用開發(fā)、算法、圖形圖像處理等方面的研究。萬方數(shù)據(jù)"#)--)$%理論研究遙感信息上的相關(guān)節(jié)點，來模擬不同公交線之間的可換車情和道路通暢程度有差異，因而實際公交網(wǎng)絡(luò)抽象的況。節(jié)點抽象是公交網(wǎng)絡(luò)抽象的關(guān)鍵。拓?fù)淠Ｐ褪怯邢驇?quán)圖。（!）最短路徑的意義
7、!實際的公交網(wǎng)絡(luò)抽象成拓?fù)淠Ｐ头治龅缆肪W(wǎng)絡(luò)上的最短路徑和公交線路的最短路徑的意義也不相同。道路網(wǎng)絡(luò)的最短路徑值要求兩點!$%實際公交線站點空間關(guān)系分析之間路徑距離最短即可，或者改進為同時參考道路實際公交網(wǎng)絡(luò)抽象成拓?fù)湫再|(zhì)的網(wǎng)絡(luò)圖，路徑的速度權(quán)值，獲得最優(yōu)路徑。即使如文獻［"，#］所述，搜索時不同屬性的邊之間在節(jié)點處的連通對應(yīng)實際用層次空間模型來解決快速道路選擇問題，但它在通勤的換車。換車要在公交站點處進行，這就要求不同層次的道路間穿越，在不同等級的道路的交叉把適當(dāng)距離內(nèi)可能換車的多個站點抽象成一個節(jié)口上并不增加時間消耗，對應(yīng)于圖
8、上在邊界節(jié)點上點。把空間位置相鄰近的公交站點歸并，并抽象成不增加權(quán)值。公交網(wǎng)絡(luò)中每一條公交線路也可理圖的節(jié)點，是生成交通網(wǎng)絡(luò)圖的關(guān)鍵。解為一個層次，從一條公交線路到另一條公交線路在實際情況下，同一公交線路兩個方向上的同的換車活動是有時間消耗的，因而就不能為尋找簡
