基于最短路徑查詢的城市公交網(wǎng)絡拓撲建模研究

《基于最短路徑查詢的城市公交網(wǎng)絡拓撲建模研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、遙感信息理論研究$##$;"基于最短路徑查詢的城市公交網(wǎng)絡拓撲建模研究陸忠，錢翔東，張登榮（浙江大學地理科學系，杭州!"##$%）摘要：最短路徑分析是地理信息系統(tǒng)（&’(）中網(wǎng)絡分析的一項重要功能，等價于圖論中的節(jié)點間求解最短路徑問題。對地理網(wǎng)絡進行地理分析和建模，以實現(xiàn)最短路徑搜索已經(jīng)有大量論文討論，但是專門針對城市公交網(wǎng)絡的建模和路徑尋優(yōu)，則少鮮有研究，而且已有的一些網(wǎng)絡模型也不能直接應用到公交網(wǎng)絡尋優(yōu)中。本文應用圖論理論，討論公共交通網(wǎng)絡的拓撲建模，實現(xiàn)公交網(wǎng)絡最優(yōu)路徑的查詢。關鍵詞：&’(網(wǎng)絡建模；公共交通網(wǎng)絡（公交網(wǎng)絡

2、）；網(wǎng)絡尋優(yōu)（最短路徑）中圖分類號：)$*"文獻標識碼：+文章編號："###,!"%%（$##$）-.,##"",#/算法進行優(yōu)化，以提高運行效率。其中被廣泛采用"引言并且研究最多的是4256789:算法。第二類是對圖的對網(wǎng)絡進行地理分析和模型化是地理信息系統(tǒng)數(shù)據(jù)結構的研究［"#］，這些數(shù)據(jù)結構都以邊和節(jié)點結（&’(）中網(wǎng)絡分析的一項重要內(nèi)容［"#］。網(wǎng)絡主要指構為基礎。第三類是關于道路網(wǎng)絡、管道或管線網(wǎng)各種實際的道路（如鐵路、城際鄉(xiāng)間公路、城市道路絡圖的建模［.!%］。這些模型和算法研究針對特定的等）網(wǎng)絡和城市管線網(wǎng)（如點里網(wǎng)

3、、給排水管網(wǎng)、電話實際網(wǎng)絡，沒有可能直接應用于公交網(wǎng)絡尋優(yōu)，因為網(wǎng)等）等［"］。網(wǎng)絡建模指把實際網(wǎng)絡抽象成圖論中公交網(wǎng)絡不同于道路網(wǎng)絡。具有拓撲性質(zhì)的網(wǎng)絡圖。&’(網(wǎng)絡分析中的實際應$公交網(wǎng)絡的特點用，如道路交通網(wǎng)絡最短路徑查詢、電子導游圖、城市管線管理系統(tǒng)、""#電子報警系統(tǒng)等，其實都等價公交網(wǎng)絡有如下特點：于圖論中的節(jié)點間求解最短路徑問題［$!/］。（"）連通性一個圖!"（#，$）是由有窮而非空的頂點集城市道路網(wǎng)絡中的道路交叉點無差異地連接著#和邊集$所組成，如果邊是頂點的有序?qū)Γ?&，與該路口連通的多條路段，而兩路公交線路

4、的站點%’），（%&，%’）!$；%&，%’!#，則說這個圖是有向在同一點時，同路公交路段之間的連通性和不同公的［$，!］。交線路的連通性是有差別的，這是因為兩路不同公(，)是兩個非空集合，*，+分別是#到(，$到交線路在空間上的同一站點的連通，要換車而增加)的兩個映射，則稱有序四元組!"（#，$，(，)）了時間消耗。另外多條公交線路雖然可以相交于空為加權圖，(，)稱為頂點的權和邊的權。間上的同一個點，但是該點不一定是公交?？空军c，圖!的一個邊序列0，0，0，?，0，或者說一個或者不是同時有站點，因而不同公交線路在此是不#"$,

5、頂點序列%，%，%，?，%稱為圖從%到%的一條連通的。#"$,#,路經(jīng)；從%到%的所有路徑中，權-（%，%）最?。?）節(jié)點的特性#,#,的路徑稱為從%到%的最短路徑，記為（%，%）。雖然不同的公交線路在行程上有重疊，但是各#,#,其長度為：自的站點不可能是完全的幾何重疊，因而要做有效-（%#，%,）"123｛-&（%#，%,）.%#，%,!#；&""，$，?｝的站點間疊加分析。在實際通勤中必然要求在不同最短路徑問題已經(jīng)有大量的研究論文，這些論的公交線路之間實現(xiàn)換車以到達目的地，這就要求文大致可分為三類。第一類是最短路徑的算法研相

6、對應的網(wǎng)絡圖上不同屬性的邊在節(jié)點上的連通，究［.!*］，討論最短路徑算法及根據(jù)實際問題對經(jīng)典這是公共交通網(wǎng)絡分析的意義。在公交網(wǎng)絡疊加分析時，要求把空間上相近的異線站點合理抽象成圖收稿日期：$##$,#","$作者簡介：陸忠（"*%"!），男，浙江大學地球科學系碩士研究生，主要從事&’(應用開發(fā)、算法、圖形圖像處理等方面的研究。萬方數(shù)據(jù)"#)--)$%理論研究遙感信息上的相關節(jié)點，來模擬不同公交線之間的可換車情和道路通暢程度有差異，因而實際公交網(wǎng)絡抽象的況。節(jié)點抽象是公交網(wǎng)絡抽象的關鍵。拓撲模型是有向帶權圖。（!）最短路徑的意義

7、!實際的公交網(wǎng)絡抽象成拓撲模型分析道路網(wǎng)絡上的最短路徑和公交線路的最短路徑的意義也不相同。道路網(wǎng)絡的最短路徑值要求兩點!$%實際公交線站點空間關系分析之間路徑距離最短即可，或者改進為同時參考道路實際公交網(wǎng)絡抽象成拓撲性質(zhì)的網(wǎng)絡圖，路徑的速度權值，獲得最優(yōu)路徑。即使如文獻［"，#］所述，搜索時不同屬性的邊之間在節(jié)點處的連通對應實際用層次空間模型來解決快速道路選擇問題，但它在通勤的換車。換車要在公交站點處進行，這就要求不同層次的道路間穿越，在不同等級的道路的交叉把適當距離內(nèi)可能換車的多個站點抽象成一個節(jié)口上并不增加時間消耗，對應于圖

8、上在邊界節(jié)點上點。把空間位置相鄰近的公交站點歸并，并抽象成不增加權值。公交網(wǎng)絡中每一條公交線路也可理圖的節(jié)點，是生成交通網(wǎng)絡圖的關鍵。解為一個層次，從一條公交線路到另一條公交線路在實際情況下，同一公交線路兩個方向上的同的換車活動是有時間消耗的，因而就不能為尋找簡