XML數(shù)據(jù)公交信息查詢優(yōu)化算法及實現(xiàn)

劉明珠++丁亦楠++鄭云非

摘要：針對公交線路規(guī)劃的問題，必須提供一個準確快捷的公交查詢系統(tǒng)以滿足人們?nèi)粘３鲂械男枨?研究了基于XML數(shù)據(jù)的公交查詢系統(tǒng)，該系統(tǒng)采用B/S模式，利用ASP.NET框架和C#語言，實現(xiàn)了公交運行查詢功能.在換乘查詢算法部分及在Dijkstra算法的基礎上，分析了路徑尋優(yōu)的原理，實現(xiàn)了路徑距離計算的具體方法.并通過減少臨時節(jié)點排序及數(shù)量的方式，改進了Dijk-stra算法，最終減少了尋找路徑的時間并簡化了路徑計算，最后，以天津市公交數(shù)據(jù)為例.用改進的Dijkstra算法對公交查詢系統(tǒng)進行了分析驗證，結(jié)果表明，利用改進的Dijkstra算法可以實現(xiàn)高效的公交信息查詢，節(jié)約查詢時間，節(jié)省內(nèi)存資源.

關鍵詞：公交查詢；Dijkstra算法；XML數(shù)據(jù)；路徑尋優(yōu)；最短路徑

DOI： 10.15938/j.jhust.2015.02.016

中圖分類號：TP319

文獻標志碼：A

文章編號：1007-2683（2015）02-0085-06

0 引 言

隨著現(xiàn)代城市規(guī)模發(fā)展，城市的公交線路也越來越復雜，準確又方便地查閱公交線路，已經(jīng)成為與人們生活息息相關的問題.傳統(tǒng)的公交查詢系統(tǒng)大多使用Sybase SQL Server、Oracle等傳統(tǒng)數(shù)據(jù)庫系統(tǒng)保存公交信息數(shù)據(jù)，并運用（structured querylanguage SQL）語言實現(xiàn)對這些數(shù)據(jù)庫的操作.SQL語法簡單，語言語句可嵌套，這使它具有極大的靈活性，但是，對于管理者的要求較高.目前，利用XML文件的結(jié)構(gòu)化標記數(shù)據(jù)和可移植性的特點，構(gòu)建公交查詢系統(tǒng)后臺數(shù)據(jù)結(jié)構(gòu)，以減輕系統(tǒng)管理者負擔，并提供準確、快捷的公交線路查詢系統(tǒng)成為智能公交系統(tǒng)的研究熱點之一.XML即可擴展標記語言，它使用表示起始和結(jié)束標簽的語法來描述和交換獨立于應用程序的結(jié)構(gòu)化數(shù)據(jù).使用XML存儲數(shù)據(jù)使得管理者不再需要使用傳統(tǒng)的soL語言來更新管理數(shù)據(jù)，減輕了管理人員的負擔.本文首先對Dijkstra算法進行改進，并在Visual Studio開發(fā)環(huán)境下，利用ASP.net框架，采用B/S模式，構(gòu)建XML數(shù)據(jù)，并將線路與站點數(shù)據(jù)相結(jié)合，同時融合拐點數(shù)據(jù)，使得線路查詢算法更加簡單，為公交查詢系統(tǒng)的數(shù)據(jù)管理提供了一種新方法.

1 系統(tǒng)需求描述

1.1 性能需求

一個好的公交查詢系統(tǒng)應具有準確性，快速性，易擴展性和易使用性.它保證系統(tǒng)輸出結(jié)果的準確性，避免出現(xiàn)重復或者錯誤的查詢結(jié)果給用戶造成誤導，并且在數(shù)據(jù)的導入、導出和查詢過程中數(shù)據(jù)的處理時間響應上不超過ls.系統(tǒng)利用的XML數(shù)據(jù)非常便于管理者在后臺隨時進行更新和修改，即可直接打開XML數(shù)據(jù)文件進行手動修改.同時查詢者無需進行登錄即可進行公交查詢，系統(tǒng)配備合理的人機交互界面，方便用戶查詢和使用，節(jié)約了用戶查詢時間.

1.2 功能需求

公交查詢系統(tǒng)功能需求結(jié)構(gòu)如圖1所示.

1）線路查詢：包含了線路的上、下行信息，并涵蓋了線路經(jīng)過的所有站點信息.當用戶輸入的信息不明確或不詳細時，系統(tǒng)自動進行模糊查詢，為用戶匹配需要的線路信息.

2）站點查詢：此功能在用戶進行查詢時，將包含此站點的所有公交線路反饋給用戶，若用戶輸入的站名不明確時，系統(tǒng)自動進行模糊查詢，為用戶反饋合適的公交線路信息.

3）乘車路線查詢：本系統(tǒng)以較少換乘次數(shù)作為設計依據(jù)設計了零換乘站點查詢和一次換乘查詢.首先輸出零換乘的查詢結(jié)果，其次輸出一次換乘的查詢結(jié)果，給查詢者帶來方便.

2 Dijkstra換乘算法描述及其優(yōu)化

Dijkstra算法以廣度優(yōu)先算法為基礎，主要解決從固定的單個點源，經(jīng)過若干點后，到其他固定頂點的最短路徑問題.本系統(tǒng)換乘查詢部分采用了改進的Dijkstra換乘算法.

2. 1 基于傳統(tǒng)Dijkstra算法的換乘查詢算法

在本文設計的公交查詢系統(tǒng)中，一次換乘查詢采用了Dijkstra算法，具體過程如下：

Stepl.設起點為站點A，設終點為站點C，其它的站點為站點B.設從站點A到站點B的集合為U（A，B）距離為AA，若站點B為中轉(zhuǎn)站，則設AA=0；若站點B非中轉(zhuǎn)站則AA=∞.

Step2.計算出AA的具體數(shù)值，對AA的值排序，并從AA最小值開始暫定其為AA的值，暫定該AA下的站點B為最佳中轉(zhuǎn)站點.

Step3.設從站點B到站點C的集合為U（B，C），距離為AB，則從站點A到站點C的距離為AC=AA+AB.對AC的值和對應的換乘數(shù)據(jù)進行保存.

Step4.重復step2和step3直到所有AA為最大值.

Step5.對所有已保存的AC的值進行排序找到從站點A到站點C的最短距離和相對應的換乘數(shù)據(jù)，

該過程基于傳統(tǒng)Dijkstra算法可以實現(xiàn)一次換乘查詢，提供準確結(jié)果.但由于遍歷計算節(jié)點較多，并產(chǎn)生大量中問數(shù)據(jù)，導致其效率不高，算法時問得不到優(yōu)化.

2.2傳統(tǒng)Dijkstra換乘算法優(yōu)化原理

基于傳統(tǒng)的Dijkstra換乘算法，對于一個公交查詢系統(tǒng)，一般來說有以下兩種常規(guī)優(yōu)化方案：

1）傳統(tǒng)優(yōu)化方案一：該Dijkstra算法優(yōu)化方案根據(jù)在查詢中轉(zhuǎn)站時，對中轉(zhuǎn)站設置一定的權值來實現(xiàn)，這樣做的好處是可以對換乘的次數(shù)進行排序，優(yōu)先選擇少換乘的路線，之后再對換乘路線的距離進行計算并排序.但是，這種方案當換乘次數(shù)增多時，會產(chǎn)生大量的查詢線路無用結(jié)果，并且由于權值的加入，最終導致運算結(jié)點的增加，使得運算次數(shù)增多，不具備一定的實用性，雖然針對于傳統(tǒng)的Dijk-stra算法進行工一定優(yōu)化，但并不是最佳優(yōu)化方案.

2）傳統(tǒng)優(yōu)化方案二：該Dijkstra算法優(yōu)化方案在計算起點A到中轉(zhuǎn)站B的距離AA時只計算站點B為中轉(zhuǎn)站的距離，然后直接計算站點B到站點C的距離AB，最后依據(jù)AC=AA+AB直接計算全程線路的距離AC的值后再對AC排序.這樣做減少了中途排序的過程，節(jié)約了大量計算機內(nèi)存.但是這種方案在查找同一組線路下的中轉(zhuǎn)站會出現(xiàn)中轉(zhuǎn)站重復的情況，進而增加中途結(jié)點，沒有實現(xiàn)算法完全優(yōu)化.

2.3 本系統(tǒng)Dijkstra換乘算法優(yōu)化原理

在本系統(tǒng)中，傳統(tǒng)的Dijkstra算法在計算過程中產(chǎn)生大量的0元素，∞元素以及中間數(shù)據(jù)，這樣做會占用較多計算資源，且該算法的時間復雜度為O（n2），當數(shù)據(jù)量過大時，中途的結(jié)點數(shù)據(jù)量會占據(jù)大量的計算機內(nèi)存單元，算法運行的時間將會不可接受，因此，需要對傳統(tǒng)的Dijkstra換乘算法進行優(yōu)化，使之減少資源占用，減輕計算復雜度，優(yōu)化實現(xiàn)的具體過程為：

Stcpl.設起點為站點A，終點為站點C.找出包含A的線路L（A）和包含站點C的線路/（C）.

Step2.分別求出線路/（A）和線路L（C）的所有站點，找出L（A）與L（C）線路站點中包含的相同站點，即為中轉(zhuǎn)站點1.若查找出的相同站點包含重復的，L（A）與L（C）線路，則停止重復查找，直接查詢下一條線路的相同站點.

Step3.直接計算站點B到站點C的距離AB.

Stcp4.依據(jù)AC=AA+△B直接計算AC的值，再對AC排序.

這樣做與傳統(tǒng)的Dijkstra算法過程相比，避免了巾途積累大量的結(jié)點數(shù)據(jù)，并減少了中途排序的過程，當算法在運算過程中產(chǎn)生n個結(jié)點數(shù)時，優(yōu)化算法的時間復雜度減少為0（n）這樣節(jié)約了大量計算機內(nèi)存并節(jié)省了大量運算時間，并提高了查詢速度.

2.4 Dijkstra換乘算法優(yōu)化實驗驗證結(jié)果

為了驗證本系統(tǒng)的Dijkstra換乘算法優(yōu)化的搜索效率，正確性以及優(yōu)化效率，本文對傳統(tǒng)Dijkstra算法，傳統(tǒng)Dijkstra算法優(yōu)化方案一，優(yōu)化方案二和本系統(tǒng)的Dijkstra優(yōu)化算法分別進行了實驗，并進行了算法的對比驗證.

在進行實驗驗證時，首先選取10組不同的起點和終點數(shù)據(jù)，然后使用這10組數(shù)據(jù)進行線路查詢，在換乘線路查找過程中，分別記錄使用這4種算法方案所產(chǎn)生的平均節(jié)點數(shù)及算法的搜索效率，并驗證輸出結(jié)果的正確性，最終分析說明優(yōu)化Dijkstra換乘算法相比其它3種算法方案的提升效率，各項比較結(jié)果如表1所示，

從表l中可以看出，使用優(yōu)化后的Dijkstra換乘算法過程中產(chǎn)生的節(jié)點數(shù)明顯減少，并且優(yōu)化提升明顯，相比其他3種算法方案，本系統(tǒng)使用的Dijk-stra優(yōu)化換乘算法很好的節(jié)省了內(nèi)存占用單元和查詢時間，滿足了用戶需求.

3 基于XML數(shù)據(jù)的公交信息查詢優(yōu)化算法的實現(xiàn)

3.1 XML數(shù)據(jù)模塊設計說明及程序?qū)崿F(xiàn)

XML數(shù)據(jù)設計直接影響系統(tǒng)的性能以及管理員的維護.XML數(shù)據(jù)將線路與站點數(shù)據(jù)相結(jié)合，并且融合了線路拐點數(shù)據(jù)，所謂拐點即公交按其線路行走時需要拐彎的點，融合拐點數(shù)據(jù)后，使站點距離計算更加精確，本系統(tǒng)的XMI。數(shù)據(jù)模塊如下所示：

由于XML文檔可以被表示為標簽在節(jié)點上的樹，則通過圖2表示出該XML文檔的數(shù)據(jù)模式圖.通過這些數(shù)據(jù)可以查詢乘車線路，并計算出兩站點之間的距離，并且非常便于管理員在后臺隨時更新和維護該XML數(shù)據(jù).

在此模塊中：

主要包含3個元素，分別為：station元素、line元素及l(fā)ines元素.

1）標簽中存儲了該條線路的所有站點和拐點.其中，元素name表示站點名稱，若該點為拐點，則name為空，元素longitude表示該站點（拐點）的經(jīng)度，元素latitude表示該站點（拐點）的緯度，用C#進行數(shù)據(jù)傳人時，首先建立XS-pot類，類中定義了用來存儲線路名稱的字符串變量和用來存儲坐標的坐標變量，用XSpot類定一個spot自定義類型，將每條線路的站點數(shù)據(jù)分別存人其中.

2）標簽中存儲了一條線路和該線路所包含的所有站點和拐點，其中，元素name表示線路名稱.

3）標簽中存儲著所有線路，在用C#進行數(shù)據(jù)傳人時，首先建立XLine類，類中定義了用來存儲線路名稱的字符串變量和用來存儲線路包含的站名名稱及站點信息的XSpot變量.用XSpot類定義一個spots自定義類型，將spot內(nèi)的每條線路站點信息全部存人其中，整合為全部線路的全部站點名稱，并用XLine類定義一個line自定義類型，將標簽內(nèi)的數(shù)據(jù)全部存人line中，其中包含每條線路名稱name和對應的站點及站點坐標spots.

3.2計算站點距離的數(shù)學模型描述

1）當用戶從站點A1到站點AM時，中途要經(jīng)過m-2個站點及拐點，分別設站點為A2，A3，…，Am-2，A—1·

2）設站點A1的經(jīng)度為x1，，站點A1緯度為y1；站點A2經(jīng)度為X2，站點A2緯度為Y2，則站點A1與站點A2的經(jīng)度差為

X1= X2 -Xl，

（1）

它們的緯度差為

3）由于地面上經(jīng)度或緯度相差1度以內(nèi)對應的地表弧長大約是S =lllkm，且站點與站點間的距離都小于1經(jīng)度或l緯度.因此，站點A.與站點A2之間的距離為

同理，站點A2與站點A3之間的距離為

站點Am一，與站點Am之間的距離為

4）由此可知，從站點A1到站點Am，即用戶的乘車所經(jīng)過的距離為

3.3基于優(yōu)化Dijkstra乘車查詢算法的實現(xiàn)

本系統(tǒng)乘車查詢實現(xiàn)分為零換乘與一次換乘兩部分.

3. 3.1零換乘

首先應用C#的List容器類以及System.Xml控件將XML后臺數(shù)據(jù)中的線路信息與站點拐點的信息傳人程序中，并使用List類構(gòu)建linesl和lines2兩個新容器，設用戶查詢的起點站為stationl，終點站為station2，查找包含stationl的所有線路并將其存入容器linesl中，同時將包含station2的所有線路存入lines2中.之后，使用List類構(gòu)建line容器來保存共同包含stationl與station2的線路，此線路即為用戶零換乘所需要的乘車線路，之后利用站點距離數(shù)學模型及C#語言實現(xiàn)可計算出stationl到sta-tion2的距離.在C#中，求兩個List的交集，可以通過調(diào)用List類中的Intersect方法”line=linesl.Inter-sect（lines2）. ToList（）”；利用C#容器類的這個特點可簡單有效的求出用戶所需的乘車線路，再通過索引找出stationl及station2分別在line中的位置，即可求出用戶乘坐該線路所要經(jīng)過的站點及距離.最后，利用C#語言提供的接口IComparer，建立內(nèi)部繼承類，并利用該接口中提供的CompareTo（）函數(shù)對類中的成員進行比較，通過這個方法，對line中的線路路徑長度進行比較后排序并將結(jié)果存人新容器lines中，可得出零換乘從路徑最短到路徑最長的查詢結(jié)果（流程圖如圖3左邊所示）.

3.3.2 一次換乘

用C#語言實現(xiàn)時，首先設起點站為stationl，終點站為station2，利用Find（）函數(shù)，找出所有包含stationl的線路liriel中以及所有包含station2的線路line2，并用索引標記出stationl，station2分別在lineI和line2中的位置.其次，利用判斷中轉(zhuǎn)站的方法”Linel.spots[i].GetName（）==line2.spots[j].GetName（）”來找出line1和line2中的共同站點，即換乘站點，其中，spots代表線路的站點，GetName（）用來獲取站點中的線路名稱.由于在相同linel與line2問一般會有多個換乘站點，因此，先通過對sta-tionl與station2到換乘站點距離分別進行計算，求出station1到station2的距離，再取出stationl到sta-Lion2存相同line1與line2下的最短距離，最終只保留相同linel，line2下stationl到station2的最短路徑結(jié)果，并保存在List容器path中，再進行下一組line1，line2的判斷.最終，將保留的換乘查詢結(jié)果排序并利用lines.Add（path）；全部保存在List容器liries中，即為一次換乘的乘車線路（流程如圖3右邊所示）.

3.4查詢結(jié)果的輸出

本系統(tǒng)通過使用天津市公交信息數(shù)據(jù)，最終實現(xiàn)了線路查詢、站點查詢、乘車線路查詢?nèi)蠊δ?

1）線路查詢：在該方面本系統(tǒng)以“101路”線路作為實驗數(shù)據(jù)，在進行線路查詢時，輸入“101”，通過模糊查詢來找到101路公交的上下行線路所有信息，查詢結(jié)果如圖4所示.

2）站點查詢：在站點查詢的方面，本系統(tǒng)以“天津站”為例，查詢了經(jīng)過天津火車站的所有公交線路，查詢結(jié)果如圖5所示.

3）乘車路線查詢：在乘車路線查詢結(jié)果輸出方面，系統(tǒng)根據(jù)人們出行時的乘車心理，首先選擇了輸出零換乘的查詢結(jié)果，當零換乘的查詢結(jié)果較少或沒有零換乘的乘車路線時，系統(tǒng)將繼續(xù)自動進行一次換乘查詢，并將結(jié)果輸出.同時，為了保證系統(tǒng)結(jié)果簡明扼要，在進行線路查找時，添加了限制語句，令輸出的乘車線路結(jié)果保持在5條以內(nèi)，既當容器lines中存儲的線路個數(shù)達到5條時，系統(tǒng)自動停止線路查詢，這樣既減少了搜索乘車線路所花費的時間，又給用戶提供了快捷方便的結(jié)果.系統(tǒng)以起點為“天津站”，終點為“天津西站”作為實驗依據(jù)，對該系統(tǒng)進行了實驗驗證，乘車線路的查詢結(jié)果如圖6所示.

4 結(jié) 語

本系統(tǒng)首先通過使用XML數(shù)據(jù)，進而實現(xiàn)對傳統(tǒng)Dijkstra換乘算法的改進，并將結(jié)果與傳統(tǒng)Dijk-stra換乘算法和傳統(tǒng)Dijkstra換乘優(yōu)化方案進行比較，驗證了本系統(tǒng)算法的優(yōu)越性，最終構(gòu)建了一個對于用戶方便使用，對于管理員方便管理的簡便實用的公交查詢系統(tǒng)，實驗表明了利用改進的Dijkstra算法可以實現(xiàn)高效的公交信息查詢，節(jié)約了查詢時間，節(jié)省了內(nèi)存資源.該系統(tǒng)對于傳統(tǒng)Dijkstra換乘算法的優(yōu)化為公交查詢系統(tǒng)提供了一種新的解決思路.