用於提供公交線路的方法和系統的製作方法
2023-08-02 14:24:11 1
專利名稱：用於提供公交線路的方法和系統的製作方法
技術領域：
本發明涉及交通領域，具體而言，涉及一種用於提供公交線路的方法和系統。
背景技術：
現有的公交查詢一般是基於資料庫進行線路_站點關係的查詢，具體來說，將起 點站的所有線路中能去到終點站的公交線路列出來，或者將經過起點站的所有公交線路列 出，再從中找出能去到終點站的公交線路。在實現本發明過程中，發明人發現現有技術中公交查詢系統對數據獲取的效率較 低，導致用戶對公交線路查詢的速度較慢。
發明內容
本發明旨在提供一種用於提供公交線路的方法和系統，以解決現有技術中公交查 詢系統對數據獲取的效率較低，導致用戶對公交線路查詢的速度較慢問題。在本發明的實施例中，提供了一種用於提供公交線路的方法，包括以下步驟通過K維樹找出出發地和目的地附近的公交站點，其中，K維樹是公交站點的索 引，K等於2或3;根據公交站點給出出發地到目的地之間的公交線路。優選地，在上述方法中，2維樹是公交站點的索引具體包括根據地理位置的經度值和緯度值建立X軸-Y軸的2維空間；在2維樹的偶數層按X坐標將公交站點排序，將公交站點的X坐標上相鄰的公交 站點作為公交站點的左、右子樹；在2維樹的奇數層按Y坐標將公交站點排序，將公交站點的Y坐標上相鄰公交站 點作為公交站點的左、右子樹；其中，在2維樹中，設某個公交站點為根結點，其深度為0，將2維樹分為偶數層和
奇數層。優選地，在上述方法中，站點信息具體表示為(SPl，SP2，X，Y，NAME, ID)，其中SPl和SP2分別表示與公交站點相鄰的公交站點；X和Y分別表示公交站點的經度值和維度值；NAME表示公交站點的站點名；ID表示公交站點在2維樹的編號。優選地，在上述方法中，還包括以下步驟將能坐車到公交站點的其他公交站點用圖的方式緩存。優選地，在上述方法中，根據公交站點給出出發地到目的地之間的公交線路具體 包括計算目的地對應的公交站點與目的地之間的距離；如果距離小於等於設定值，根據用戶設定的權值給出出發地到目的地的公交線路。優選地，在上述方法中，計算目的地對應的公交站點與目的地之間的距離具體包 括計算目的地對應的公交站點A與目的地B之間的距離Distance的公式如下Distance = R^Arccos(C)*Pi/180 ；C = sin (LatA*Pi/180)*sin(LatB*Pi/180) +cos (LatA*Pi/180)*cos (LatB*Pi/180)*cos((MLonA-MLonB)*Pi/180)；其中，R為地球的平均半徑，MLonA和MLatA分別為公交站點A的經度值和緯度值， MLonB和MLatB分別為目的地B的經度值和緯度值，Pi為圓周率。在本發明的實施例中，還提供了一種用於提供公交線路的系統，包括索引模塊，用於將公交站點索引到K維樹；查詢模塊，用於根據用戶輸入的出發地和目的地查詢出發地和目的地附近的公交 站點；計算模塊，用於根據公交站點給出出發地到目的地之間的公交線路。優選地，在上述系統中，查詢模塊採用.NET Remoting作為中間數據傳遞協議。在本實施例中，通過將的公交站點索引到K維樹，完成了對存儲在介質上的公交 站點的數據信息的描述，從而可以根據輸入的出發地和目的地選擇K維樹中分支的方向， 提高了數據獲取的效率，使得用戶可以較快地查詢到所要乘坐的公交線路，克服了現有技 術中公交查詢系統對數據獲取的效率較低，導致用戶對公交線路查詢的速度較慢問題。
此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發 明的示意性實施例及其說明用於解釋本發明，並不構成對本發明的不當限定。在附圖中圖1示出了根據本發明一個實施例的用於提供公交線路的方法流程圖；圖2示出了根據本發明一個實施例的2維樹示意圖；圖3示出了根據本發明一個實施例的經過起點的所有公交線路圖；圖4示出了根據本發明一個實施例的用於提供公交線路的系統模塊圖；圖5示出了根據本發明一個實施例的R樹示意圖。
具體實施例方式下面將參考附圖並結合實施例，來詳細說明本發明。圖1示出了根據本發明一個實施例的用於提供公交線路的方法流程圖，包括以下 步驟S102，通過K維樹找出出發地和目的地附近的公交站點，其中，K維樹是公交站點 的索引，K等於2或3;S104,根據公交站點給出出發地到目的地之間的公交線路。在本實施例中，通過將的公交站點索引到K維樹，完成了對存儲在介質上的公交 站點的數據信息的描述，從而可以根據輸入的出發地和目的地選擇K維樹中分支的方向， 提高了數據獲取的效率，使得用戶可以較快地查詢到所要乘坐的公交線路，克服了現有技術中公交查詢系統對數據獲取的效率較低，導致用戶對公交線路查詢的速度較慢問題。例如，在上述實施例中，公交站點可以是公共汽車、地鐵、輕軌等站點。優選地，在上述方法中，2維樹是公交站點的索引具體包括根據地理位置的經度值和緯度值建立X軸-Y軸的2維空間；在2維樹的偶數層按X坐標將公交站點排序，將公交站點的X坐標上相鄰的公交 站點作為公交站點的左、右子樹；在2維樹的奇數層按Y坐標將公交站點排序，將公交站點的Y坐標相鄰的公交站 點作為公交站點的左、右子樹；其中，在2維樹中，設某個公交站點為根結點，其深度為0，將2維樹分為偶數層和
奇數層。在本實施中，通過構造2維的平衡樹，可以較快地對數據信息進行查找，提高了查 找效率。例如，2維樹可以這樣構建，開始時，定義站點集為S，樹的根為整個平面，然後確 定分割點P，P e S，過點P的平行於Y軸的直線把S分割成兩個集合Sl和S2，從中選取分 割點Pi、P2，分別過pi、p2作平行於X軸的直線分割，以此類推。圖2示出了根據本發明一個實施例的2維樹示意圖。優選地，在上述方法中，站點信息具體表示為(SPl，SP2，X，Y，NAME, ID)，其中SPl和SP2分別表示與公交站點相鄰的公交站點；X和Y分別表示公交站點的經度值和維度值；NAME表示公交站點的站點名；ID表示公交站點在2維樹的編號。每個公交站點用K維樹中一個結點來表示，通過結點中的6個域表現出來。開始 的兩個域是指向結點兩個子節點的指針，各自相對應方向是左和右；X和Y各自保存公交站 點經度和緯度值；NAME域用來保存站點名；ID域表示公交站點在資料庫對應的ID。當結點P是一個X識別器。那麼所有具有X坐標值小於P的結點將放在左樹中， 而X坐標值大於或等於P的結點將放到P的右子樹中。對於一個Y識別器的結點有同樣的 約定。優選地，在上述方法中，還包括以下步驟將能坐車到公交站點的其他公交站點用圖的方式緩存。在本實施例中，通過把每一個站點經過的所有線路能到達的所有公交站點以圖的 形式保存下來，在下次的公交線路查詢匯總，可以節省一步遍歷的步驟，節省了時間，提高 了查找公交線路的速度。圖3示出了根據本發明一個實施例的經過起點的所有公交線路圖，如圖3所示，不 帶箭頭的線表示經過起點的某一條線路，帶箭頭的線表示保存在圖中的邊記錄。圖用鄰接表保存，在鄰接表中，對圖中每個頂點建立一個單鍊表(並按建立的次 序編號)，第i個單鍊表中的結點表示依附於頂點vi的邊(對於有向圖是以頂點vi為尾的 弧)。每個結點由三個域組成鄰接點域(adjvex)，用以指示與vi鄰接的點在圖中的位置， 鏈域(nextarc)用以指向依附於頂點vi的下一條邊所對應的結點，存放數據的域(info) 用於記錄相關信息，例如乘坐線路和距離等。
優選地，在上述方法中，根據公交站點給出出發地到目的地之間的公交線路具體 包括計算目的地對應的公交站點與目的地之間的距離；如果距離小於等於設定值，根據用戶設定的權值給出出發地到目的地的公交線 路。例如，當用戶希望得到更省時間的方案，那麼速度的權重比例將會更高，最終在對各方 案分別計算分數進行排序時，速度較快的線路(例如地鐵)由於分數更高，它們在所有換乘 的方案中排名靠前的可能性就越大。優選地，在上述方法中，計算目的地對應的公交站點與目的地之間的距離具體包 括 計算目的地對應的公交站點A與目的地B之間的距離Distance的公式如下Distance = R^Arccos(C)*Pi/180 ；C = sin (LatA*Pi/180)*sin(LatB*Pi/180) +cos (LatA*Pi/180)*cos(LatB*Pi/180)*cos((MLonA-MLonB)*Pi/180)；其中，R為地球的平均半徑，MLonA和MLatA分別為公交站點A的經度值和緯度值， MLonB和MLatB分別為目的地B的經度值和緯度值，Pi為圓周率。地球是一個近乎標準的橢球體，它的赤道半徑為6378. 140千米，極半徑為 6356. 755千米，平均半徑6371. 004千米。如果我們假設地球是一個完美的球體，那麼它 的半徑就是地球的平均半徑，記為R。如果以O度經線為基準，那麼根據地球表面任意兩 點的經緯度就可以計算出這兩點間的地表距離(這裡忽略地球表面地形對計算帶來的誤 差，僅僅是理論上的估算值)。設第一點A的經緯度為(LonA，LatA)，第二點B的經緯度 為(LonB，LatB)，按照O度經線的基準，東經取經度的正值(Longitude)，西經取經度負值 (-Longitude)，北緯取 90-緯度值(90-Latitude)，南緯取 90+ 緯度值(90+Latitude)，則經 過上述處理過後的兩點被計為(MLonA，MLatA)和(MLonB，MLatB)。這裡，R和Distance單位是相同，如果是採用6371. 004千米作為半徑，那麼 Distance就是千米為單位，如果要使用其他單位，比如mile，還需要做單位換算，1千米= 0. 621371192mile如果僅對經度作正負的處理，而不對緯度作90-Latitude (假設都是北半球，南半 球只有澳洲具有應用意義)的處理，那麼公式將是C = sin (LatA)*sin (LatB) +cos (LatA)*cos(LatB)*cos(MLonA-MLonB)；Distance = R*Arccos(C)*Pi/180。如果三角函數的輸入和輸出都採用弧度值，那麼公式還可以寫作C = sin (LatA*Pi/180)*sin(LatB*Pi/180) +cos (LatA*Pi/180)*cos(LatB*Pi/180)*cos((MLonA-MLonB)*Pi/180)；Distance = R*Arccos(C)*Pi/180。由於起點和終點是由經緯度給出，而各站點的經緯度都已知，因此可以求出各步 行段的直線距離，以此來近似實際步行距離。圖4示出了根據本發明一個實施例的用於提供公交線路的系統模塊圖，包括索引模塊10，用於將公交站點索引到K維樹；
7
查詢模塊20，用於根據用戶輸入的出發地和目的地通過K維樹查詢出發地和目的 地附近的公交站點；計算模塊30，用於根據公交站點給出出發地到目的地之間的公交線路。在本實施例中，通過將的公交站點索引到K維樹，完成了對存儲在介質上的公交 站點的數據信息的描述，從而可以根據輸入的出發地和目的地選擇K維樹中分支的方向， 提高了數據獲取的效率，使得用戶可以較快地查詢到所要乘坐的公交線路，克服了現有技 術中公交查詢系統對數據獲取的效率較低，導致用戶對公交線路查詢的速度較慢問題。優選地，在上述系統中，查詢模塊採用.NET Remoting作為中間數據傳遞協議。. NET Remoting是微軟公司.NET編程框架自帶的一種遠程調用通信協議，遠程調 用又可稱為遠程過程調用。該協議允許運行於一臺計算機的程序調用另一臺計算機的子程 序，而程式設計師無需額外地為這個交互作用編程。由於處理全國的數據量非常大，本實施例採用.NET Remoting作為分布式計算的 中間數據傳遞協議，可將不同城市或地區的數據分布開，從而提高並發請求數。為了以經緯度判斷起點終點所在城市，本實施例採用R樹空間區域索引技方法。 R樹是一種高度平衡的樹，由中間節點和葉節點組成，實際數據對象的最小外接矩形存儲在 葉節點中，中間節點通過聚集其低層節點的外接矩形形成，包含所有這些外接矩形。其後， 人們在此基礎上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是目 前流行的空間索引。R樹是B樹向多維空間發展的另一種形式，它將空間對象按範圍劃分，每個結點都 對應一個區域和一個磁碟頁，非葉結點的磁碟頁中存儲其所有子結點的區域範圍，非葉結 點的所有子結點的區域都落在它的區域範圍之內；葉結點的磁碟頁中存儲其區域範圍之內 的所有空間對象的外接矩形。每個結點所能擁有的子結點數目有上、下限，下限保證對磁碟 空間的有效利用，上限保證每個結點對應一個磁碟頁，當插入新的結點導致某結點要求的 空間大於一個磁碟頁時，該結點一分為二。R樹是一種動態索引結構，即它的查詢可與插 入或刪除同時進行，而且不需要定期地對樹結構進行重新組織。R樹可以用來訪問二維或者更高維區域對象組成的空間數據。樹上有兩類結點 葉子結點和非葉子結點。每一個結點由若干個索引項構成。對於葉子結點，索引項形如 (Index, Ob j_ID)。其中，Index表示包圍空間數據對象的最小外接矩形MBR，0bj_ID標識一 個空間數據對象。對於一個非葉子結點，它的索引項形如(Index，Child_P0inter)。Child, Pointer指向該結點的子結點。Index仍指一個矩形區域，該矩形區域包圍了子結點上所有 索引項MBR的最小矩形區域。圖5示出了根據本發明一個實施例的R樹示意圖。R樹的插入與許多其他樹的操作一樣，可以歸納為一個遞歸過程。首先從根結點出 發，按照一定的標準，選擇其中一個孩子插入新的空間要素，然後再從以孩子為根的子樹的 根結點出發重複進行上面操作，直到葉子結點。設M和m(m<M)為R樹結點中單元個數的 上限和下限，當新的空間要素的插入使葉子結點中的單元個數超過M時，需要進行結點的 分裂操作。分裂操作是將溢出的結點按照一定的規則分為若干部分。在其父結點刪除原來 對應的單元，並加入由分裂產生的相應的單元。如果這樣引起父結點的溢出，則繼續對父結 點進行分裂操作。分裂操作也是一個遞歸過程，它保證了空間要素插入後R樹仍能保持平
從R樹中刪除一個空間要素與插入類似，首先從R樹中查找到記錄該空間要素所 在的葉子結點，這就是R樹的查找。從根結點開始，依次檢索包含空間要素的單元所對應孩 子結點為根結點的子樹。查詢方式利用了 R樹的結構特徵，減少了檢索的範圍，提高了檢索 的效率。查找到該空間要素所在的葉子結點後，刪除其對應的單元。如果刪除後該葉子結 點單元個數少於m，需要進行R樹的壓縮操作，將單元數過少的結點刪除。如果父結點因此 單元數也少於m，則繼續對父結點重複進行該操作。最後將因進行結點調整而被刪除的空 間要素重新插入到R樹中。這就是R樹的壓縮操作，它使得R樹的每個結點單元數不低於 m這個下限，從而保證了 R樹結點的平衡和利用率。從R樹的結構可以看出，讓空間上靠近的空間要素擁有儘可能近的共同祖先，能 提高R樹的查詢效率。在構造R樹的時候，儘可能讓空間要素的空間位置的遠近體現在其最 近的共同祖先的遠近上，形象的說就是讓聚集在一起的空間要素儘可能早的組合在一起。 插入中選擇子樹的標準，分裂操作、插入操作中選擇子樹的標準，分裂操作中的分裂方法， 都是為了體現這一目標。本實施例將每個城市或地區作為一個多邊形存儲在R樹中，查詢時由起點終點的 經緯度在R樹中查詢出相應的城市或地區，再調用對應的服務程序。本實施例的用於提供公交線路的系統採用負載均衡策略進行架構。負載均衡建立 在現有網絡結構之上，它提供了一種廉價有效的方法擴展伺服器帶寬和增加吞吐量，加強 網絡數據處理能力，提高網絡的靈活性和可用性。它主要完成以下任務解決網絡擁塞問 題，服務就近提供，實現地理位置無關性；為用戶提供更好的訪問質量；提高伺服器響應速 度；提高伺服器及其他資源的利用效率；避免了網絡關鍵部位出現單點失效。為了滿足高服務質量的需求，本發明採用反向代理技術實現負載均衡策略。代理 服務把客戶的連接請求以反向代理的方式動態地轉發給內部網絡上的多臺伺服器進行處 理，這樣可以避免單一伺服器失效而導致整個服務失效，從而達到負載均衡的目的。同時， 由於反向代理本身佔用系統資源極小，因此可以以低成本設置多個反向代理作為服務入 口，進而運用其他負載均衡策略如DNS負載均衡。在上述實施例中的用於提供公交線路的系統中，當第一次用戶傳入某個城市的起 點、終點經緯度，進行換乘，此城市的緩存機制開始觸發，首先進行站對站索引，同時，使用K 維樹，對各站建空間索引。接著，通過空間索引，得知客戶可以到達的站點，接著使用站對站 索引，採用上述實施例匯總的用於提供公交線路的方法進行調試，並且使用不同的權值，規 劃出最適合用戶的線路方案。顯然，本領域的技術人員應該明白，上述的本發明的各模塊或各步驟可以用通用 的計算裝置來實現，它們可以集中在單個的計算裝置上，或者分布在多個計算裝置所組成 的網絡上，可選地，它們可以用計算裝置可執行的程序代碼來實現，從而，可以將它們存儲 在存儲裝置中由計算裝置來執行，或者將它們分別製作成各個集成電路模塊，或者將它們 中的多個模塊或步驟製作成單個集成電路模塊來實現。這樣，本發明不限制於任何特定的 硬體和軟體結合。以上所述僅為本發明的優選實施例而已，並不用於限制本發明，對於本領域的技 術人員來說，本發明可以有各種更改和變化。凡在本發明的精神和原則之內，所作的任何修 改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
一種用於提供公交線路的方法，其特徵在於，包括以下步驟通過K維樹找出出發地和目的地附近的公交站點，其中，所述K維樹是所述公交站點的索引，K等於2或3；根據所述公交站點給出所述出發地到所述目的地之間的公交線路。
2.根據權利要求1所述的方法，其特徵在於，所述K維樹是所述公交站點的索引具體包括根據地理位置的經度值和緯度值建立X軸-Y軸的2維空間； 在所述2維樹的偶數層按X坐標將所述公交站點排序，將所述公交站點的X坐標上相 鄰的公交站點作為所述公交站點的左、右子樹；在所述2維樹的奇數層按Y坐標將所述公交站點排序，將所述公交站點的Y坐標上相 鄰的公交站點作為所述公交站點的左、右子樹；其中，在所述2維樹中，設某個公交站點為根結點，其深度為0，將所述2維樹分為偶數 層和奇數層。
3.根據權利要求2所述的方法，其特徵在於，所述站點信息具體表示為(SP1，SP2，X， Y, NAME, ID)，其中所述SPl和所述SP2分別表示與所述公交站點相鄰的公交站點； 所述X和所述Y分別表示所述公交站點的經度值和維度值； 所述NAME表示所述公交站點的站點名； 所述ID表示所述公交站點在所述2維樹的編號。
4.根據權利要求1所述的方法，其特徵在於，還包括以下步驟 將能坐車到所述公交站點的其他所述公交站點用圖的方式緩存。
5.根據權利要求1所述的方法，其特徵在於，根據所述公交站點給出所述出發地到所 述目的地之間的公交線路具體包括計算所述目的地對應的公交站點與所述目的地之間的距離；如果所述距離小於等於設定值，根據用戶設定的權值給出所述出發地到所述目的地的 公交線路。
6.根據權利要求5所述的方法，其特徵在於，計算所述目的地對應的公交站點與所述 目的地之間的距離具體包括計算所述目的地對應的公交站點A與所述目的地B之間的距離Distance的公式如下 Distance = R*Arccos (C)*Pi/180 ； C = sin(LatA*Pi/180)*sin(LatB*Pi/180)+cos(LatA*Pi/180)*cos(LatB*Pi/180)*cos((MLonA-MLonB)*Pi/180)； 其中，R為地球的平均半徑，MLonA和MLatA分別為所述公交站點A的經度值和緯度值， MLonB和MLatB分別為所述目的地B的經度值和緯度值，Pi為圓周率。
7.一種用於提供公交線路的系統，其特徵在於，包括 索引模塊，用於將公交站點索引到K維樹；查詢模塊，用於根據用戶輸入的出發地和目的地查詢所述出發地和所述目的地附近的 公交站點；計算模塊，用於根據所述公交站點給出所述出發地到所述目的地之間的公交線路。
8.根據權利要求7所述的系統，其特徵在於，所述查詢模塊採用.NET Remoting作為中 間數據傳遞協議。
全文摘要
本發明提供了一種用於提供公交線路的方法和系統，方法包括以下步驟通過K維樹找出出發地和目的地附近的公交站點，其中，K維樹是公交站點的索引，K等於2或3；根據公交站點給出出發地到目的地之間的公交線路。本發明克服了現有技術中公交查詢系統對數據獲取的效率較低，導致用戶對公交線路查詢的速度較慢問題。
文檔編號G06F17/30GK101944096SQ20091015893
公開日2011年1月12日 申請日期2009年7月8日 優先權日2009年7月8日
發明者柳宗偉 申請人:廣東融訊信息科技有限公司