多模式公交出行路徑尋優方法
2023-06-15 03:32:41
專利名稱：多模式公交出行路徑尋優方法
技術領域：
本發明屬於公交出行信息發布領域，專用於公交出行時的最優路線査詢。
背景技術：
智能信息發布系統作為智能交通系統ITS的應用之一，給出行者提供了 更好的出行信息服務，因此近年來得到了廣泛的應用。最佳路線優選是其
中一個重要的關鍵技術，但目前主要存在以下問題
1) 為提高搜索效率，以往有些公交路徑搜索主要通過站點名稱匹配的 方法尋找路徑，難以處理一站多名的情況。且因未考慮行駛及換乘時間， 難以給出合理路徑及出行時間信息。
2) 目前大城市的公交網絡是含有不同公交模式如地鐵、輕軌、公交專
用道、地面公交等多層次網絡，公交出行過程包括候車、上車、乘車車 輛行駛及換乘多個環節，不同模式的車輛行駛速度及換乘時間差異很 大，而以往考慮線路行駛時間的公交路徑搜索較少考慮換乘時間，難以 應用於大規模多模式公交網絡進行合理路線搜索。
3) 因實時信息不完備，目前，大多數的考慮線路行駛時間的路徑優化 方法是基於靜態信息計算的。但事實上，在阻塞常發的城市路網中，因 與社會車輛共享路權，且受自行車、行人幹擾，地面公交線路的行程時 間具有很大的不確定性，由此造成了到站時間及車內旅行時間的不確定 性，而由於大城市許多出行者的公交出行包括多個過程，當過程之間的 連接如換乘等出現問題時，出行時間不確定性的問題更為突出。因此， 基於靜態分析的路徑選擇與實際的動態最佳路徑常有較大偏離
發明內容
本發明根據大規模多層次公交線網存在的換乘延誤以及行駛時間及 換乘時間的隨機性，提供一種可用於觸控螢幕或網際網路的公交出行路徑尋優 方法，向用戶提供高效準確的出行路徑及換乘信息。
本發明所提出的方法的思路是以公交出行鏈各環節為邊，通過構建包 含不同公交模式如地鐵、輕軌、公交專用道、地面公交的多層次網絡鄰接 關係，並對各邊進行平均出行時間及時間可靠度的雙重賦權，建立考慮換
乘的多模式公交線網；在沒有實時信息條件下，以通行時間較短、延誤風 險較小為路徑尋優的雙重目標，通過在路徑尋優過程中對延誤高發線路及 換乘點進行啟發式規避，實現在出行時間許可範圍內有效減少延誤風險的 可靠路徑的快速搜索。在此方法基礎上，以觸控螢幕信息系統或網際網路為平 臺，搭建多模式公交路徑查詢系統並進行路徑及換乘信息的查詢及發布。
本發明的多模式公交出行路徑尋優方法，是以觸控螢幕信息系統或互聯 網為平臺，採用以下步驟完成多模式公交出行最佳路徑的查詢及發布
步驟1:構建多模式公交線網並建立多模式公交線網鄰接關係；
即將公交線網抽象為公交網絡，公交網絡中含有不同公交模式，如地 鐵、快速公交、普通公交、公交專用道、普通地面公交等公交模式；
之後進行初始化設定，將初始的各模式公交線網信息存入資料庫中， 再根據可接受步行距離的限制條件生成多模式公交線網拓撲所述的公交網絡由節點及邊構成，節點及邊統稱為公交網絡的單元； 其中所有的公交站點構成公交網絡中的節點單元，在路徑搜索中，出行者 的出發地及目的地可構成公交網絡的虛擬節點，稱為起始節點及目的地節 點，簡稱起點及終點；從出行者的角度出發，以公交出行鏈各環節，如候 車、乘車車輛行駛及換乘環節作為公交網絡邊單元節點間的連線構成公交 網絡的邊單元，邊單元中包括線路邊、換乘邊、及接駁邊三類，具體定義線路邊同一線路同向相鄰節點、即站點間的連線，此邊對應於乘車 環節；
換乘邊在300-500米換乘範圍內的不同線路節點間的連線，此邊對 應於換乘步行及候車環節，為虛擬邊；
接駁邊從起點到500米線路覆蓋範圍內的連線，此邊對應於步行接 駁及候車環節，也為虛擬邊；
所述的公交網絡節點鄰接關係採用以下關係式建立
—7 /與y在同一線路上，_/為/的下遊相鄰節點
_ 7 /與y不在同一線路上，但/與/相距M0米 5M米內 —)7 /為起點或終點，/與y相距M0米~ 5卯米內
0 否則
該關係式是根據以上節點與邊的定義生成多模式公交線網拓撲 圖後，以 表示公交網絡中任意節點i與j的鄰接關係，當i與j在多模 式網絡中鄰接時，""取值為l，否則取值為O，按該關係式原則判斷網絡中 所有i與j是否鄰接，並根據判斷結果建立公交網絡節點鄰接關係；
步驟2:標定公交網絡邊單元的雙參數
在本發明的多層次公交路徑査詢系統中，公交網絡正常條件，即無事 故或異常天氣下各邊的平均出行消耗時間參數(簡稱時間參數)和可靠度 參數作為邊單元屬性文件，存在中心控制計算機的資料庫裡，並以一定時 間為周期加以更新，以下為屬性文件參數標定及建立方法的詳細說明
1、邊單元的雙參數設定
在擁擠的城市路網，不同的時段擁擠程度及公交的發車頻率不同， 從而公交行駛時間、等候時間與一天的不同時段有很大關係。鑑於目前 實時信息獲取還有很大難度，根據城市交通時間分布特性，可將一天劃 分為早平峰、早高峰、中午平峰、晚高峰、夜平峰五個典型時段，並假設同一時段內的擁擠程度及公交的發車頻率近似相同；而上述行駛時 間、換乘時間、等候時間可用典型時段的歷史數據取均值來標定；
本方法將公交網絡在無事故或異常天氣的正常條件下，各邊的平均 出行消耗時間參數，簡稱時間參數和可靠度參數作為邊單元屬性文件進 行設定，
(1) 邊單元的時間參數標定，是將公交網絡的邊單元的出行消耗時間 參數，即時間權重進行如下規定
線路邊的時間權重為該邊兩端站點間的公交行駛時間；
換乘邊的時間權重為該邊兩端站點間的換乘時間，包括換乘步行時 間及等候時間。等候時間可取所銜接的線路的發車間隔的一半近似作為 候車時間，行走時間可由換乘距離除以平均步行速度確定；
接駁邊的時間權重為起點所銜接的站點、對應的線路的發車頻率間 隔的一半，加上起點到所銜接的站點的距離，除以平均步行速度；
(2) 邊單元可靠度參數標定，是將公交網絡的邊的可靠度參數定義為 一個0到1之間的數，該數表徵了公交出行各環節延誤在給定範圍的概 率，穩定性越好，可靠度參數越大；
根據公交出行的特點，對公交網絡的邊單元的可靠度參數取值進行如 下分類規定
線路邊的可靠度參數時間，為該邊兩端站點間的公交行駛時間可 靠度，將其定義為行駛延誤時間在典型時段、即早平峰、早高峰、中午 平峰、晚高峰、夜平峰給定範圍內的概率，給定範圍時間設定為5~10 分鐘內。這可基於歷史數據，根據線路對應交通模式、所經道路擁擠或 隔離程度等進行分類標定。換乘邊及接駁邊的可靠度參數標定可由其中等候時間可靠度標定， 本發明將其定義為等候時間在典型時段、即早平峰、早高峰、中午平峰、
晚高峰、夜平峰給定範圍內的概率，給定範圍時間設定為5 10分鐘內。
本發明中將可靠度低於或等於給定閾值取0.4~0.6的單元稱為高風 險單元。
具體描述為本發明是按線路對應交通模式、所經道路擁擠或隔離 程度等進行分類標定。 一般線路邊時間可靠度的按從大到小的順序排列 為地鐵〉輕軌〉BRT (快速公交) >公交專用道>常規地面公交。換乘邊及 接駁邊的可靠度定義為換乘或接駁時間在給定範圍內的概率。其標定可 根據換乘邊所銜接的線路的發車間隔及道路擁擠狀況而分類標定。 一般 來講，發車間隔越小，線路所經道路越暢通，等候時間可靠度越大。
本發明中將可靠度低於給定閾值的單元稱為高風險單元。 2、將設定好的邊單元文件的公交網絡各邊時間和可靠性參數、及邊單 元中的高風險單元一併存放於中心控制計算機的資料庫中，並以一定時 間為周期加以更新；
步驟3:進行用戶査詢信息輸入及多模式線網屬性參數調入；
用戶可實現兩種方式的查詢信息輸入。 一是通過觸控螢幕或滑鼠實現 起始點及目的地點的輸入；二是通過鍵盤的拼音輸入法輸入起始地及目 的地點的關鍵字進行模糊查詢；
當有用戶發出查詢請求時，即將網絡拓撲鄰接關係、資料庫或數據 文件中的邊單元屬性參數、用戶的起始點信息實時動態地裝載入系統參 與計算。
步驟4:以通行時間最短、延誤風險最小為雙重目標，進行路徑尋優；本發明利用對高風險單元加權的方法對延誤高發的線路邊、等候時間 較長的換乘邊及接駁邊進行規避，減少高風險單元在最佳線路中出現的可 能性，以提高基於靜態歷史信息的路徑搜索準確性。
本發明路徑尋優搜索過程包括兩個部分 一是運用最短路A+算法結 合權重增量方法計算可靠路徑，二是檢査路徑是否滿足繞行時間約束。 當找到滿足繞行長度或時間約束的高可靠路徑時，停止搜索； 所述的最佳路徑尋優搜索步驟如下
(1 ):初始化
令h0，以邊單元/的時間參數W,為權重，通過A+算法找到具有最
小權重，即最小出行時間的路徑i^， A力行程時間為^,o; (2):對公交網絡上具有較高風險的各邊的權重增加Aw,
W,， = "M^+ Aw,.= W,. + or*(/-y『。，0<a<l, 0〈n.化
指增加權重後的邊/的新權重； 當^=0時，《=0;&>=1時，『1. k為整數；"it + l;
(3):計算可靠路徑
即以W'為邊/的新權重，重新用八*算法計算權重最小的路徑A》 將其上面的邊/的權重恢復為^，計算丄4，也就是路徑戶a上的各邊邊 權W,總和； (4 ):檢查路徑約束條件
如果所得路徑滿足繞行長度限制(丄^6^,0)，則轉到前述5，否則回 到前述2; (5 ):終止
i^就是滿足繞行時間限制條件的出行時間可靠路徑； 其他參數符號的定義如下f^指加到W上的很大值、即正值，可取 旅程時間最長的公交線路對應的旅程時間，r,指邊/的可靠度，指平均出行時間最短的路徑，丄&。指A力平均出行時間，ySL^指繞行時間 限制，"為允許係數C6H)， />a指A次迭代所得的最短路徑，指i^. 權重、即平均出行時間； 在本搜索方法中，在第一次迭代中，^=0，公交網絡上具有較高風險 的各邊的權重開始都增加％，從而避免了這些高風險邊在規劃路徑中的出 現。可是如果違反了繞行長度的限制條件，就需重新規劃。為此，在隨後 的迭代中，較高風險路段己增加的權重被逐步降低，最短路徑在新的權重
下被重新計算，這意味著曾被規避的邊可能重新出現在推薦的路徑上。函 數W(1-r,)M呆證Aw,隨著迭代次數的增加而減小。同時為了儘可能避免高風
險邊出現在推薦路徑上，高風險邊的權重要比相對較低危險的邊減小得少。
步驟5.通過觸控螢幕或網際網路向用戶反饋時間最短路徑及時間可靠路徑建議 及相應的出行時間，並將換乘點及換乘線路發布給用戶。出行者可根據個 人喜好進行最終選擇。
上述路徑尋優方法中多次調用的八*算法(Hartetal.，1968)為目前兩 點間的最短路徑搜索算法中，比較有效的代表算法。Af算法屬於啟發式 算法，在最短路徑搜索中，A+算法只計算同其相鄰的節點，並且用每個 節點到目的點的估算距離來決定這個節點是否可能在最優路線上。在算法 搜索過程中，每個節點"被賦予權重/(^^g(^+A(^，這裡gf^指從起點到 節點n的最短路長，/z(")指節點n到目的地最短路長估計。因此/(;7)就是對所 有經過節點n的從起點到目的點的最短路長估計，我們也稱其為入*算法的 啟發式函數。啟發式函數/2(")可以控制A+算法的搜索範圍及效率。搜索過 程中每一個具有最低/f直的節點將被選擇作為下一個擴展點。如果/z^小於 或等於從節點n到目的地的實際最短路長，Af算法將會找到最優解。
由於本發明考慮了換乘、等候時間及延誤發生的可能性，提高了路
徑搜索的準確性及出行準點性，同時豐富了信息發布內容，多目標的路徑
選擇可滿足不同出行者的喜好。
圖1系統總框架圖2線路邊及換乘邊示意圖3接駁邊示意圖4本發明實施的總流程圖5最佳線路搜索流程圖6平均出行時間最短路展示圖7出行時間可靠路徑展示下面對前述附圖進行詳細說明
圖1為系統總構架圖，本發明的多模式公交路徑査詢系統包括資料庫、
多模式公交網絡構建及參數標定模塊及最佳路徑計算模塊，資料庫初始有
單模式公交線路數據，通過將單模式公交線路數據加載到多模式公交網絡
構建及參數標定模塊，在該模塊實現多模式公交虛擬網絡生成及鄰接關係
建立，並完成多模式公交網絡時間及可靠度參數標定，進而網絡鄰接關係
及標定後的網絡參數作為多模式公交網絡數據返回存儲至資料庫，遇査詢
請求時動態多模式公交網絡數據加載到最佳路徑計算模塊，實現最佳路徑
計算並發布。
圖2為線路邊及換乘邊示意圖，圖2中所示十字路口有兩條公交線路經 過，公交線路A和公交線路B。 Al， A2， A3…和B1， B2， B3…分別為公 交線路上的公交站點。A1到A2， A2到A3， A3到A4的連線分別對應四 條線路邊，同理，B1至UB2， B2到B3分別對應三條線路邊。
分別以線路A上的公交站點Al， A2， A3…為圓心，以可接受的換乘 距離為半徑畫圓，在該圓的範圍內搜索，可找出在該範圍內存在的其它線 路的公交站點。圖中A3站點搜索範圍內存在B3站點，連接A3、 B3，即為一條換乘虛擬邊，乘客可能利用此虛擬邊從線路A換乘線路B到達目的地。
圖3為接駁邊示意圖，假設乘客出發點為O點，以出發點O為圓心， 以一個可以接受的步行距離為半徑畫圓，出發點O與該範圍內的公交站點 連接將形成接駁虛擬邊。圖中線路A的站點A2和線路B的站點B2在乘 客出發點的步行範圍內，分別連接0和A2， 0和B2點，形成兩個接駁虛 擬邊。
圖4為發明實施總流程圖，包括五個步驟。其中第一步是構建多模式 公交線網並建立其鄰接關係，包括以下子步驟首先將初始的各單模式公 交線網信息存入資料庫，然後根據可接受步行距離的限制條件生成多模式 公交線網拓撲圖，進而建立地鐵、快速公交、普通公交等多模式公交線網 鄰接關係。
第二步是標定公交網絡邊單元的雙參數，包括以下子步驟首先劃分 典型時段並標定各典型時段內線路邊、換乘邊、接駁邊的時間及可靠度參 數，進而將公交線網鄰接關係及公交網絡各邊時間和可靠度參數(作為邊 單元屬性文件)存在中心控制計算機的資料庫裡，並以一定時間為周期加 以更新。
第三步是用戶查詢信息輸入及多模式線網相關屬性參數調入。系統 當沒有用戶發出査詢請求時處於等候狀態，當有用戶發出查詢請求時， 網絡拓撲鄰接關係、資料庫中的邊單元屬性參數、用戶起訖點信息將被 動態地裝載入系統。
第四步根據動態加載的數據，以通行時間最短、延誤風險最小為雙重目標，進行路徑尋優。
第五步路徑計算完畢，通過觸控螢幕或網際網路向用戶反饋路徑建議。 圖5是最佳路線搜索流程。首先是初始化令^0，以^為邊/的時 間權重，通過At算法找到具有最小權重，即最小出行時間的路徑A,。， A。
出行時間為厶,。，然後對多模式公交網絡上具有較高風險的各邊的權重增加 Aw,，得到新權重W,'。同時將A重新賦值即y^"l。進而以W,'為邊/的新 權重，重新用At算法計算權重最小的路徑^力即可靠路徑。把/^上面 的邊/的權重恢復為^，計算可靠路徑的實際路長&力也就是路徑Pw上 的各邊邊權W總和。檢査所得路徑是否滿足繞行時間限制(乙,t〈-乙,。)，是 則結束，否則減少加在較高風險的各邊的權重，重新計算可靠路徑。
圖6是平均出行時間最短路展示圖，該圖為在包含有地鐵、輕軌、BRT
及普通地面公交的北京市多模式公交線網中進行一次平均出行時間最短路 搜索的結果示意圖，地鐵線在圖中用中空線表示。出行起點為知春裡附近， 終點為體育館西路附近。圖中粗線顯示的是平均出行時間最短路徑，換乘 一次，涉及兩個地面普通公交線路，換乘點用圓圈表示。
圖7是出行時間可靠路徑展示圖，該圖為與圖6在同樣條件下搜索得到 的出行時間可靠路徑示意圖。圖中粗線顯示的是出行時間可靠的路徑，換 乘三次，換乘點用圓圈表示。
具體實施例方式
下面結合附圖對本發明的具體實施例加以說明-
根據圖1所示的系統總框架圖搭建本發明方法實施平臺，結合附圖4所 給出的本發明的方法所可實施的總流程圖、圖5所給出的本發明最佳線路 搜索流程圖、及圖2所示的線路邊及換乘邊示意圖和圖3所示的接駁邊示 意圖進行本發明具體實施方案的詳細說明第一步構建地鐵、快速公交、普通公交等多模式公交線網並建立其 鄰接關係；
首先將地鐵、快速公交、普通公交各單模式公交線網的相應信息存入 資料庫，信息包括站點及線路的地理信息、運行時間信息等。
按附圖2及附圖3的示例方法生成地鐵、快速公交、普通公交等多模 式公交線網的各條線路邊、換乘虛擬邊及接駁虛擬邊，生成拓撲圖。
圖2中有兩條公交線路，公交線路A和公交線路B。 Al， A2， A3... 禾口B1， B2， B3…分別為公交線路上的公交站點。Al到A2， A2至廿A3， A3 到A4的連線分別對應四條線路邊，同理，Bl到B2， B2到B3分別對應三 條線路邊。
分別以線路A上的公交站點A1， A2， A3…為圓心，以可接受的換乘 距離為半徑畫圓，換乘距離可取300米 500米，在該圓的範圍內搜索，找 出在該範圍內存在的其它線路的公交站點。如圖2所示，A3站點搜索範圍 內存在B3站點，連接A3、 B3,即為一條換乘虛擬邊，乘客可能利用此虛 擬邊從線路A換乘線路B到達目的地。
假設乘客出發點為O點，以出發點O為圓心，以一個可以接受的步行 距離為半徑畫圓，步行距離可取300 500米，出發點O與該範圍內的公交 站點連接形成接駁虛擬邊。如圖3所示，線路A的站點A2和線路B的站 點B2在乘客出發點的步行範圍內，分別連接0和A2， 0和B2點，形成 兩個接駁虛擬邊。
進而按以下公式的原則建立公交網絡節點鄰接關係，取值定義如前所 述，
'7 /與y在同一線路上，_/為/的下遊相鄰節點
_ / /與y不在同一線路上，但/與y湘距300米 500米內
—、 /為起點或終點，/與_/相距300米~ 500米內
0 否則第二步、標定公交網絡邊單元的雙參數 具體包括以下過程
(1) 將一天劃分為早平峰、早高峰、中午平峰、晚高峰、夜平峰五個 時段；
(2) 按前文發明內容中介紹方法標定各典型時段內線路邊、換乘邊、 接駁邊的時間參數。
(3) 按前文發明內容中介紹方法標定線路邊、換乘邊、接駁邊的可靠 度參數，可根據歷史數據統計，將行駛延誤時間在典型時段(早平峰、 早高峰、中午平峰、晚高峰、夜平峰給定範圍內的概率作為線路邊的可 靠度參數，給定範圍的時間取5 10分鐘內。將換乘或接駁等候時間在 典型時段早平峰、早高峰、中午平峰、晚高峰、夜平峰給定範圍內的概 率作為換乘邊或接駁邊的可靠度參數，給定範圍的時間取5~10分鐘內。
本發明中將可靠度低於或等於給定閾值的單元稱為高風險單元，給定 閾值取0.4 0.5。
簡化起見，可根據線路對應交通模式、發車頻率、所經道路擁擠或隔 離程度等進行分類標定。以早高峰為例，本發明建議採用如下分類及取值
方法
對地鐵、輕軌線路邊可靠度取l，對BRT線路邊可靠度取0.9，對公 交專用道線路邊可靠度取0.7，對經過非擁擠區域、即公交運行車速高於 12公裡/小時的普通地面公交線路邊可靠度取0.6，對經過擁擠區域、即公 交運行車速不高於12公裡/小時或車頭時距大於15分鐘的普通地面公交線 路邊可靠度取0.5。
對換乘或接駁地鐵、輕軌線路的換乘或接駁邊的可靠度取l，對換乘 或接駁BRT的換乘或接駁邊可靠度取0.9，對換乘或接駁公交專用道的換 乘或接駁邊可靠度取0.7，對換乘或接駁非擁擠區域的普通地面公交的換乘或接駁邊可靠度取0.6，對換乘或接駁擁擠區域或車頭時距大於15分鐘的 普通地面公交的換乘或接駁邊可靠度取0.5。
將公交網絡各邊時間參數和可靠度參數作為邊單元屬性文件，存在中 心控制計算機的資料庫裡。並以一定時間為周期加以更新。
第三步、用戶查詢信息輸入及多模式線網相關屬性參數調入；
當有用戶通過輸入起訖點發出査詢請求時，即將網絡拓撲鄰接關係、 資料庫或數據文件中的邊單元屬性參數實時動態地裝載入系統參與計算。
第四步、以通行時間最短、延誤風險最小為雙重目標，進行路徑尋優； 具體的路徑尋優流程圖見附圖5。圖中符號說明見前文發明內容。
第五步、通過觸控螢幕或網際網路向用戶反饋路徑建議、出行時間，並將換 乘點及換乘線路發布給用戶。
數值實驗
該方法在北京市的公交網絡上(見附圖6)進行了試驗，該網絡包含 有地鐵、輕軌、BRT及普通地面公交，高峰平均速度分別為35， 25， 20, 15 公裡/小時，高峰地鐵、輕軌及BRT的車頭時距分別為3， 5， 0.5分鐘， 普通地面公交車頭時距為3~20分鐘，行駛在擁擠路段或連接車頭時距大於 15分鐘的地面公交線路的換乘邊及等候邊被視為高風險邊。
在本試驗中，任取一起始點及目的地點，分別進行平均出行時間最短 路徑搜索及在繞行約束"取l. 05時，進行出行時間可靠路徑搜索。
附圖6中粗線顯示的是平均出行時間最短路徑，平均出行時間為91分 鍾。換乘一次，涉及兩個地面普通公交線路，換乘點用圓圈表示，附圖7 中粗線顯示的是出行時間可靠的路徑，平均出行時間為94分鐘。換乘三次， 換乘點用圓圈表示。
在該試驗中，平均出行時間最短路徑雖正常條件下平均出行時間最短， 但經過了5處高風險邊，出行時間可靠路徑僅經過l處高風險邊，雖換乘較多，但因主要是換乘地鐵，耗時較少，且地鐵的運行速度較快，時間可靠 度較高，因此也是合理路徑。
出行者可根據個人喜好進行最終選擇。
最後應說明的是以上實施例僅用以說明本發明而並非限制本發明所 描述的技術方案；因此，儘管本說明書參照上述的各個實施例對本發明已
進行了詳細的說明，但是，本領域的普通技術人員應當理解，仍然可以對
本發明進行修改或等同替換；而一切不脫離發明的精神和範圍的技術方案 及其改進，其均應涵蓋在本發明的權利要求範圍當中。
權利要求
1、多模式公交出行路徑尋優方法，其特徵在於該方法是以觸控螢幕信息系統或網際網路為平臺，採用以下步驟完成多模式公交出行最佳路徑的查詢及發布步驟1構建多模式公交線網並建立多模式公交線網鄰接關係即將公交線網抽象為公交網絡，公交網絡中含有不同公交模式，如地鐵、快速公交、普通公交、公交專用道、普通地面公交等公交模式；之後進行初始化設定，將初始的各模式公交線網信息存入資料庫中，再根據可接受步行距離的限制條件生成多模式公交線網拓撲圖；所述的公交網絡由節點及邊構成，節點及邊統稱為公交網絡的單元；其中所有的公交站點構成公交網絡中的節點單元，在路徑搜索中，出行者的出發地及目的地可構成公交網絡的虛擬節點，稱為起始節點及目的地節點，簡稱起點及終點；從出行者的角度出發，以公交出行鏈各環節，如候車、乘車車輛行駛及換乘環節作為公交網絡邊單元節點間的連線構成公交網絡的邊單元，邊單元中包括線路邊、換乘邊、及接駁邊三類，具體定義為線路邊同一線路同向相鄰節點、即站點間的連線，此邊對應於乘車環節；換乘邊在300-500米換乘範圍內的不同線路節點間的連線，此邊對應於換乘步行及候車環節，為虛擬邊；接駁邊從起點到500米線路覆蓋範圍內的連線，此邊對應於步行接駁及候車環節，也為虛擬邊；所述的公交網絡節點鄰接關係採用以下關係式建立該關係式是根據以上節點與邊的定義生成多模式公交線網拓撲圖後，以aij表示公交網絡中任意節點i與j的鄰接關係，當i與j在多模式網絡中鄰接時，aij取值為1，否則取值為0，按該關係式原則判斷網絡中所有i與j是否鄰接，並根據判斷結果從而建立公交網絡節點鄰接關係；步驟2標定公交網絡邊單元的雙參數1、邊單元的雙參數設定根據城市交通時間分布特性，可將一天劃分為早平峰、早高峰、中午平峰、晚高峰、夜平峰五個典型時段，並假設同一時段內的擁擠程度及公交的發車頻率近似相同；而上述行駛時間、換乘時間、等候時間可用典型時段的歷史數據取均值來標定；本方法將公交網絡在無事故或異常天氣的正常條件下，各邊的平均出行消耗時間參數，簡稱時間參數和可靠度參數作為邊單元屬性文件進行設定，(1)所述的邊單元的時間參數標定是將公交網絡的邊單元的的出行消耗時間參數，即時間權重進行如下規定線路邊的時間權重為該邊兩端站點間的公交行駛時間；換乘邊的時間權重為該邊兩端站點間的換乘時間，包括換乘步行時間及等候時間。等候時間可取所銜接的線路的發車間隔的一半近似作為候車時間，行走時間可由換乘距離除以平均步行速度確定；接駁邊的時間權重為起點所銜接的站點、對應的線路的發車頻率間隔的一半、加上起點到所銜接的站點的距離，除以平均步行速度；(2)所述的邊單元可靠度參數標定是將公交網絡的邊的可靠度參數定義為一個0到1之間的數，該數表徵了公交出行各環節延誤在給定範圍的概率，穩定性越好，可靠度參數越大；所述的公交網絡的邊單元的可靠度參數取值進行如下分類規定線路邊的可靠度參數時間，為該邊兩端站點間的公交行駛時間可靠度，將其定義為行駛延誤在給定範圍內的概率，線路邊的可靠度參數定義為行駛延誤時間在早平峰、早高峰、中午平峰、晚高峰、夜平峰時給定範圍內的概率；換乘邊及接駁邊的可靠度參數標定可由等候時間可靠度標定，等候時間定義為在早平峰、早高峰、中午平峰、晚高峰、夜平峰時給定範圍的概率；當可靠度低於或等於給定閾值的邊單元定義為高風險單元；
2、將設定好的邊單元文件的公交網絡各邊時間和可靠性參數、及邊單元 中的高風險單元一併存放於中心控制計算機的資料庫中，並以一定時間為 周期加以更新；步驟3:進行用戶查詢信息輸入及多模式線網屬性參數調入；用戶可實現兩種方式的査詢信息輸入。 一是通過觸控螢幕或滑鼠實現起 始點及目的地點的輸入；二是通過鍵盤的拼音輸入法輸入起始地及目的地點的關鍵字進行模糊査詢；當有用戶發出査詢請求時，即將網絡拓撲鄰接關係、資料庫或數據文 件中的邊單元屬性參數、用戶的起始點信息實時動態地裝載入系統參與計算。步驟4:，進行路徑尋優；以通行時間最短、延誤風險最小為雙重目標；利用對高風險單元加權 的方法對延誤高發的線路邊、等候時間較長的換乘邊及接駁邊進行規避， 減少高風險單元在最佳線路中出現的可能性，以提高基於靜態歷史信息的 路徑搜索準確性；路徑尋優搜索過程包括兩個部分 一是運用八*算法結合 權重增量方法計算可靠路徑，二是檢査路徑是否滿足繞行時間約束，當找 到滿足繞行長度或時間約束的高可靠路徑時，停止搜索；步驟5.用戶通過觸控螢幕或網際網路獲得反饋後的路徑建議、出行時間，及換乘點及換乘線路發布信息。2、根據權利要求1所述的多模式公交出行路徑尋優方法，其特徵在於 所述的最佳路徑尋優搜索步驟如下(1 ):初始化令h，以W為邊Z'的權重、指平均出行時間，通過八*算法找到具有最小權重，即最小出行時間的路徑A,e， P^行程時間為丄^; (2 ):對公交網絡上具有較高風險的各邊的權重增加Aw, 指增加權重後的邊/的新權重； 當h0日t，『0;^>=1時，『1. k為整數；h/t + l;(3) :計算可靠路徑即以W,'為邊/的新權重，重新用八*算法計算權重最小的路徑/^，將 其上面的邊/的權重恢復為W,.，計算Z,力也就是路徑i^上的各邊邊權^ 總和；(4) :檢査路徑約束條件 如果所得路徑滿足繞行長度限制(丄 6^,0指繞行時間限制， P為允許係數(^1)，屍a指A次迭代所得的最短路徑，Za指/^.權重、 即平均出行時間；
3、根據權利要求1所述的多模式公交出行路徑尋優方法，其特徵在於所述的線路邊的可靠度參數定義為行駛延誤時間在早平峰、早高峰、中午 平峰、晚高峰、夜平峰的給定範圍時間為5~10分鐘；所述的等候時間在早平峰、早高峰、中午平峰、晚高峰、夜平峰的給定範圍時間設定為5~10 分鐘；所述的高風險單元設定為可靠度低於或等於給定閾值取0.4~0.5的 邊單元文件。
全文摘要
多模式公交出行路徑尋優方法屬於公交出行信息發布領域，專用於公交出行時的最優路線查詢。本發明是以公交出行鏈各環節為邊，通過構建包含不同公交模式如地鐵、輕軌、公交專用道、地面公交的多層次網絡鄰接關係，並對各邊進行平均出行時間及時間可靠度的雙重賦權，建立考慮換乘的多模式公交線網；在沒有實時信息條件下，以通行時間較短、延誤風險較小為路徑尋優的雙重目標，通過在路徑尋優過程中對延誤高發線路及換乘點進行啟發式規避，實現在出行時間許可範圍內有效減少延誤風險的可靠路徑的快速搜索。在此方法基礎上，以觸控螢幕信息系統或網際網路為平臺，搭建多模式公交路徑查詢系統並進行路徑及換乘信息的查詢及發布。
文檔編號G06F17/30GK101308555SQ20081011572
公開日2008年11月19日 申請日期2008年6月27日 優先權日2008年6月27日
發明者王東柱, 陳豔豔 申請人:北京工業大學