專利名稱：步行網建立方法及裝置、路徑搜索方法及裝置的制作方法
技術領域：
本發明涉及多種出行模式的路徑規劃技術，特別是一種步行網建立方法及 裝置，以及一種路徑搜索方法及裝置。
背景技術：
城市交通運輸網絡涵蓋公共汽車、地鐵、輕軌等公共交通模式以及出租車、 自駕車、自行車、步行等個體交通模式。公眾出行過程具有出行模式多樣化和 出行路線個性化的特點。目前普及的地圖網站和公眾出行信息平臺等應用系統 為用戶提供了公交換乘、自駕車路線規劃等服務，為公眾出行提供了便利。但
這些應用系統為公眾提供的出行路徑規劃方案存在下列問題 (1 ) 只支持單一交通模式路徑規劃
目前與公眾出行信息服務相關的商用系統只能提供靜態交通環境下的公 交/地鐵換乘或自駕車路徑規劃方案，路徑規劃只能在各自獨立的單一模式上 進行(將公交和地鐵混合為同一模式)，無法獲取滿足用戶特定出行標準的、 可能涉及多種交通模式的路徑規劃結果。
(2 ) 公交換乘的步行引導過程缺乏可行性
步行過程一般不受導航路網行車方向性限制，也不受路況變化的影響。同 時，步行過程只能在人行道、人行橫道、過街天橋、地下通道等步行設施上進 行。而目前與公眾出行信息服務相關的商用系統提供的公交換乘路徑規劃服務 中，缺少從出發點到乘車站、中間換乘車站之間、下車站到目的地之間精確的 步行路徑引導過程。目前的商用系統提供了兩種解決方法 一是簡單告知用戶 需要步行連接的兩點之間的直線距離和方位；二是在底層導航路網數據庫上建 立有向拓樸關系，類似車載導航形式提供可通達的步行路徑。這兩種方法提供
給用戶的步行指示都缺乏可行性。前者所提供的信息太模糊，不能用于精確的 步行引導過程，后者沒有考慮步行網與底層車載導航路網之間可能存在的差 異，往往得到不實際的步行^4圣。
發明內容
本發明一方面提供一種步行網建立方法及裝置，以解決現有技術中無法提 供步行網的問題。
本發明另 一方面提供一種路徑搜索方法及裝置，以解決現有技術中公共出 行服務平臺無法提供包含有效步行的多模式多標準路徑導航的問題，為公眾出 行信息服務提供更好的技術支持。
本發明提供一種步行網建立方法，包括 在導航路網線數據集中提取出步行道； 建立步行設施點與步行道之間的映射關系； 將步行設施由點抽象為弧段，生成跨街節點和跨街步行道； 利用所述^爭^"節點對所述^爭街節點所在的原步行道進行分割，生成新的步 行道；
根據所述跨街節點對提取出的步行道、生成的新的步行道和生成的跨街步 行道間的連通關系進行重建，構成拓樸完整的步行網，所述步行網為無向網絡。 優選地，所述在導航路網線數據集中提取步行道包括 獲取道路網車行道集尺；
通過屏蔽道路網車行道集R中不允許步行通過的車行道，得到步行道集合尺'。
優選地，所述建立步行設施點與步行道之間的映射關系包括 對每一個步行設施點i，根據步行設施的語義屬性，在步行道集合尺'中尋
找與之相匹配的步行道，建立映射關系(1 : m ), 記為
M(/) = (n,廠2,…，廠m I n,…，A"m e
對/W(/)中的每一個元素，根據反向車行道屬性，判斷其對向步行道，若
其對向步行道不在M(/)中，則將其對向步行道添加至A/f(/)中，記為/W'(/'); 對每一個步行設施點i，在M'(/)中利用空間臨近分析，得出最合適的步行
道待擴展對/ir(/)。
優選地，所述生成跨街節點和5爭街步行道包括
對每一個步行設施點i，對步行道待擴展對/W"(/')中的步行道對做垂線， 選取垂足在所做垂線的目標步行道上，并且垂線段之和最小的步行道對為待處理步行道對，垂足為新生成的跨街節點，將新生成的跨街節點存儲在跨街節點 集合A/r中，并從相關步行道繼承屬性值；
根據新生成的跨街節點，擴展步行設施點i，使點要素擴展成為線要素， 生成跨街步行道，加入步行道集合尺'中，并將步行設施點的屬性值繼承到跨 街步行道屬性中。
優選地，所述利用所述跨街節點對所述跨街節點所在的原步行道進行分
割，生成新的步行道包括
跨街節點集合/V,中的每一個跨街節點分割原步行道段，生成新的步行道， 所述新的步行道保持原步行道名稱、類型，并對所述跨街步行道賦予新的標識、 起始和終止節點；
將所述新的步行道加入步行道集合f '中。
優選地，所述根據所述跨街節點對提取出的步行道、生成的新的步行道和 生成的跨街步行道間的連通關系進行重建，構成拓樸完整的步行網包括
根據步行道集合尺'中的弧段生成無向拓樸，重建步行道間的連通關系， 構成拓樸完整的步行網。
優選地，所述方法還包括
在興趣點上完成所述步行網與道路網的模式轉換；和/或 通過公交站點完成所述步行網與公交網的才莫式轉換；和/或 通過軌道交通站點完成所述步行網與軌道交通網的模式轉換。 本發明提供一種步行網建立裝置，包括 步行道提取單元，用于在導航路網線數據集中提取出步行道； 映射關系建立單元，用于建立步行設施點與步行道之間的映射關系； ^爭街步行道生成單元，用于將步行設施由點抽象為弧段，生成跨街節點和 跨街步行道；
步行道分割生成單元，用于利用所述i 爭街節點對所述跨;街節點所在的原步 行道進行分割，生成新的步行道；
拓樸關系建立單元，用于根據所述跨街節點對提取出的步行道、生成的新 的步行道和生成的跨街步行道間的連通關系進行重建，構成拓樸完整的步行 網，所述步4亍網為無向網絡。優選地，所述步行道提取單元包括 獲取子單元，用于獲取道路網車行道集R;
屏蔽子單元，用于通過屏蔽道路網車行道集f 中不允許步行通過的車行 道，得到步行道尺'。
優選地，所述裝置還包括
第一轉換單元，用于在興趣點上完成所述步行網與道路網的模式轉換；和
/或
第二轉換單元，用于通過公交站點完成所述步行網與公交網的模式轉換； 和/或
第三轉換單元，用于通過軌道交通站點完成所述步行網與軌道交通網的模 式轉換。
本發明還提供一種路徑搜索方法，包括 根據用戶指定的出行路徑標準分配不同模式網絡的優先級； 依照優先級從高到低的順序依次從不同模式網絡上選擇路徑段； 按照出行順序，依次連接路徑行進過程中的不同模式網絡上選擇的路徑 段，生成候選出行^各徑。
優選地，所述方法還包括
根據所述用戶指定的出行路徑標準，對所有候選出行路徑進行排序并輸出。
可選地，所述用戶指定的出^f亍路徑標準包括以下一項或多項換乘最少、
距離最短、時間最短、費用最低。
可選地，所述不同才莫式網絡包括以下兩種或多種
道路網、公交網、軌道交通網、步行網、興趣點層、步行設施層。
優選地，所述依照優先級從高到低的順序依次從不同模式網絡上選擇路徑
段包括
(1) 以起點O為搜索中心，以預定范圍為半徑，在最高優先級網絡m上 搜索所有可能的出發點sr,存儲結果在m模式下的出發集0"HS尸,…，S77) 中；
(2) 以終點D為搜索中心，以預定范圍為半徑，在最高優先級網絡m上搜索所有可能的終點S獷，得到m模式下的終點集D" ={Sgm,...,Sr};
(3 )如果CT # 0并且D^" - 0 ，則執行步驟(4 );否則執行步驟(6 ); (4)以S。m和S^為起點和終點，在模式m上進行路徑搜索，將得到的路徑存 儲在LT(/J)中，其中，S。meOm, SdmeDm;
(5) 分別以0-S/", Sj"-D為起點和終點，在m-l模式中進行路徑搜索， 然后執行步驟(7);
(6) 以O-D為起點和終點，在m-l模式中進行路徑搜索；
(7) 重復步驟(1)至步驟(7),直至得到所有路徑段。
優選地，如果不同才莫式網絡具有相同的優先級，則分別在所述不同才莫式網 絡上選擇最佳路徑。
優選地，所述按照出行順序，依次連接路徑行進過程中的不同模式網絡上 選擇的路徑段，生成候選出行路徑包括
從輸入起點O開始至終點D結束，依次連接路徑行進過程中涉及到的出 行模式，組成出行路徑。
本發明還提供一種路徑搜索裝置，包括
優先級設定單元，用于根據用戶指定的出行路徑標準分配不同模式網絡的 優先級；
路徑段選擇單元，用于依照優先級從高到低的順序依次從不同模式網絡上
選擇路徑段；
路徑生成單元，用于按照出行順序，依次連接路徑行進過程中的不同模式 網絡上選擇的路徑段，生成候選出行路徑。
優選地，所述裝置還包括
選捧輸出單元，用于根據所述用戶指定的出行路徑標準，對所有候選出行 路徑進行排序并輸出。
可選地，所述不同模式網絡包括以下兩種或多種 道路網、公交網、軌道交通網、步行網、興趣點層、步行設施層。 本發明與現有技術相比的優點在于本發明改善了傳統公眾出行服務平臺 中，僅能提供單一模式單一標準出行服務的局面，能夠為用戶提供完善、詳細、 符合用戶認知習慣和出行體驗的出行方案，通過步行網絡的自動化構建，解決了公共出行服務平臺無法提供有效步行導航的缺陷，同時通過多模式交通網絡 連通關系的自動化構建，很大程度上提高了城市多模式交通網絡信息組織、存 儲、管理和維護的效率，為公眾出行信息服務提供了良好的技術支持。
圖1為本發明實施例步行網建立方法的流程圖。 圖2為本發明實施例中建立的步行網絡拓樸關系的示意圖。 圖3為本發明實施例步行網建立裝置的一種結構示意圖。 圖4為本發明實施例路徑搜索方法的流程圖。
圖5為本發明實施例中在中從不同模式網絡上選擇路徑段的流程圖。 圖6為本發明實施例中多模式路徑搜索結果示意圖。 圖7為本發明實施例路徑搜索裝置的一種結構示意圖。
具體實施例方式
為了使本技術領域的人員更好地理解本發明實施例的方案，下面結合附圖 和實施方式對本發明實施例作進一步的詳細說明。
發明實施例步行網建立方法及裝置，在城市道路網、公共交通、軌道交通 和各種人行天橋、地下通道等交通勤出設施數據庫J^出上，利用地理信息系統 空間分析技術，以自動化處理的方式，建立起步行網絡。進一步地，建立起多 模式交通網絡特征實體間的連通關系。
參照圖1,是本發明實施例步行網建立方法的實現流程圖，包括以下步驟
步驟IOI，在導航路網線數據集中提取出步行道。
也就是說，在導航路網線數據集中提取出允許步行的步行道。具體地，可 以根據交通規則，選擇屏蔽導航路網車行道集R中不允許步行通過的車行道， 如立交橋、城市快速路、高速公路、帶有過街護欄的主路等，提取出具有附屬 步行道的車行道，構造可供步行通過的步行道集合，記為尺'。
步驟102,健立步行設施點與步行道之間的映射關系。
也說是說，建立步行設施點數據集與步行道之間的映射關系，具體過程如
下a. 對每一個步行設施點/,根據步行設施的語義屬性，在步行道集合尺'中 尋找與之相匹配的步行道，建立映射關系(1 : m ), 記為
/V/(/')=(廠l,廠2,…，廠m | n,…，廠m e尺'};
b. 對/W(/')中的每一個元素，根據反向車行道屬性(標識與某車行道行車
方向相反的對向車行道)，判斷其對向步行道，若其對向步行道不在M(/)中，
則添加至/W(/')中，記為/VT(/');
c. 對每一個步行設施點, ，在/VT(/)中利用空間臨近分析，得出最合適的 步行道待擴展對/W"(/')。
步驟103,將步行設施由點抽象為弧段，生成跨街節點和跨街步行道。
首先，對每一個步行設施點/,對/vr(/)中的步行道對做垂線，選取垂足 在所做垂線的目標步行道上，并且垂線段之和最小的步行道對為待處理步行道
對，垂足為新生成的跨街節點，存儲在跨街節點集合A/r中，并從相關步行道 繼承屬性值；然后，根據新生成的跨街節點，擴展步行設施點/,使點要素擴 展成為線要素，生成跨街步行道，加入步行道集合f '中，同時，將步行設施 點的屬性值繼承到跨街步行道屬性中。
步驟104，利用所述跨街節點對所述跨街節點所在的原步行道進行分割， 生成新的步行道。
對于跨街節點集合A/r中的每一個跨街節點，原步行道段在此處被分割， 分割后的新步行道保持原有名稱、類型等屬性不變，并賦予新的標識、起始和 終止節點等屬性；并將以上新生成的步行道段加入步行道集合尺'中。
當然，本發明實施例并不僅限于上述這種方式，還可以采用其他方式生成 跨街節點和跨街步行道。
步驟105，根據所述跨街節點對提取出的步行道、生成的新的步行道和生 成的跨街步行道間的連通關系進行重建，構成拓樸完整的步行網絡，所述步行 網絡為無向網^^。
具體地，可以根據步行道集合f '中的弧段生成無向拓樸，重建步行道間 的連通關系廣構成拓樸完整的步行網絡。
本發明實施例步行網建立方法，通過在導航路網線數據集中提取出步行 道；建立步行設施點與步行道之間的映射關系；將步行設施由點抽象為弧段，生成跨街節點和跨街步行道；利用所述跨街節點對所述跨街節點所在的原步行
道進行分割，生成新的步行道；根據所述跨街節點對提取出的步行道、生成的 新的步行道和生成的跨街步行道間的連通關系重建，構成拓樸完整的步行網。 從而實現了步行網絡的自動化構建，為公共出行服務平臺實現步行導航提供了 有效的技術支持。
為了進一步為用戶提供多模式交通網絡服務，在本發明實施例中，還可進 一步包括以下步驟建立步行網與其他網絡的模式轉換。
具體地，步行網絡與道路網的才莫式轉換可以在興趣點(POI)上完成；與 公交網的模式轉換可以通過公交站點完成；與軌道交通網的模式轉換可以通過 軌道交通站點完成。
圖2所示為本發明實施例中建立的步行網絡拓樸關系的示意圖。
其中(a)中步行設施i幾何信息數字化正常，步行設施j幾何信息數字化 存在一定偏差，此類情況也經常出現；
(b)中步行道a與步行道b、 d同時構成對向關系，這時需要將a、 b和 d —同加入步行設施k的步行道匹配集中；經過進一步空間臨近分析后可以得 出a和d為合適的待擴展匹配對。生成跨街節點Ni和Nj，然后通過維度擴展 (即前面提到的將點抽象為弧段)生成跨街步行道如(c)所示，同時修改因 打斷原步行道而生成的新步行道數據，最后建立拓樸關系即可。
可見，本發明實施例步行網建立方法，通過多模式交通網絡連通關系的自 動化構建，很大程度上提高了城市多模式交通網絡信息組織、存儲、管理和維 護的效率，為公眾出行信息服務提供了良好的技術支持。
本發明實施例還提供一種步行網建立裝置，如圖3所示，是該裝置的結構 示意圖。
該裝置包括
步行道提取單元301 ，用于在導航路網線數據集中提取出步行道； 映射關系建立單元302,用于建立步行設施點與步行道之間的映射關系； —跨街步行道生成單元303，用于將步行設施由點抽象為弧段，生成跨雍f節 點、生成的步行道和^爭街步行道；
步行道分割生成單元304,用于利用所述跨街節點對所述跨街節點所在的原步行道進行分割，生成新的步行道；
拓樸關系建立單元305,用于根據所述跨街節點對提取出的步行道、生成 的新的步行道和生成的跨街步行道間的連通關系進行重建，構成拓樸完整的步 行網，所述步行網為無向網絡。
在本發明實施例中，所述提取單元301的一種優選結構包括獲取子單元 和屏蔽子單元(未圖示)。其中，所述獲取子單元，用于獲取道路網車行道集 R;所述屏蔽子單元，用于通過屏蔽道路網車行道集R中不允許步行通過的車 行道，得到步行道f '。
利用本發明實施例步行網建立裝置，可以自動建立步行網絡，其具體實現 過程可參照前面本發明方法實施例中的描述，在此不再贅述。
為了進一步為用戶提供多模式交通網絡服務，在本發明實施例中，還可進 一步包括以下一種或多種單元第一轉換單元、第二轉換單元、第三轉換單元。 其中，所述第一轉換單元，用于在興趣點上完成所述步行網與道路網的模式轉 換；所述第二轉換單元，用于通過公交站點完成所述步行網與公交網的模式轉 換；所述第三轉換單元，用于通過軌道交通站點完成所述步行網與軌道交通網 的模式轉換。
本發明實施例針對目前與公眾出行信息服務相關的地圖網站和個人導航 系統在數據建模階段采用"圖層"方式表達各種交通模式的幾何信息和語義信 息，導致各模式特征實體之間相互獨立，關系割裂。因此目前的商用系統，對 公交網絡數據采集往往采取簡單數字化獨立幾何形式，路徑搜索僅能在一個獨 立的交通模式圖層上進行(公交和地鐵也往往同等看待，合并為同一模式)， 不能解決模式間的無縫連接等問題。本發明實施例提供一種步行網的建立方法 和裝置，在城市道^各網、/>共交通、軌道交通和各種人4亍天橋、地下通道、人 行橫道等交通基礎設施數據庫基礎上，利用地理信息系統空間分析技術，以自 動化處理的方式生成步行網數據，并結合其他交通模式網建立多模式交通網絡 特征實體間的連通關系建立多模式交通網絡；進一步地，考慮到出行者的不同 f求，根據不同標準進行多模式路徑規劃，提供用戶透明的多模式組合方案， 并考慮精確步行引導，實現真正的多模式、多標準門到門的路徑規劃服務。 為了提供多模式交通網絡，在本發明實施例中，可以利用地理信息系統空間分析技術，對城市多模式交通的網絡連通關系進行自動化處理。主要包括
以下處理過程
(1) il^各網連通關系的建立
根據道路網的特點，參照《車載導航地理數據采集處理技術規程》中提出 的道3各網絡連通性處理要求和ISO GDF4.0國際標準，采用業界通用的導航數 據庫模型建立車行道連通關系。道路網中車行道的基本屬性包括標識、名稱、 對向車行道、類型、路面性質、車道數等等。
(2) 公交網和道路網連通關系的建立 公交網絡數據集包括公交線路(上行和下行)、邏輯站點和物理站點。邏
輯站點是每條公交線路中唯一標識的站點。物理站點為具有唯一地理坐標、唯 一名稱的公交站點。除非具有不同名稱，否則每個物理站點之間距離需大于 100米。物理站點和邏輯站點之間為一對多的關系。邏輯站點通過與物理站點 標識的映射獲取地理坐標，多條公交線路的不同邏輯站點可共享同一物理站 點。公交線路通過動態分段方式繼承下承路網的幾何信息，公交線路網絡本身 不是獨立圖層。
從公共交通要素的描述和表達中可知，公交系統的物理站點需要與道5^網 車行道建立依附關系，公交線路中鄰接兩個邏輯站點之間的線路段通過動態分 段建立和下承路網車行道的依附關系，以此將公交系統層和車行道層兩個獨立 的層進行關聯，以建立兩個層之間的連通關系。公交網與道路網的模式轉換依 靠公交站點進行。
a. 公交物理站點和道路網車行道連通關系的建立
由于公交物理站點在車行道上表示為上行和下行，在幾何上依附于兩個名 稱相同方向相反的車行道，因此需要將兩個具有不同方向的公交物理站點匹配 到相應車4亍道上，并計算出站點在所對應車行道上的偏移量。
b. 7>交系統連通關系的建立
公交系統是依附于道路網的，因此公交網絡更適合基于道路網建立邏輯網 絡。這里采用動態分段的方法描述與表達公交要素，即每個物理站點存儲其所 在車行道的標識和偏移量，/>交^各線由每個物理站點及站點間對應的車行道標 識串來表達。公交網與道路網的模式轉換依靠公交站點進行。站點間的公交線段通過存 儲所經過的車行道唯一標識串表達。公交站點層包括物理站點層和邏輯站點 層。 一個物理站點可能對應多個不同公交線路上的邏輯站點，邏輯站點通過唯 一標識和物理站點相關聯。邏輯站點位置通過繼承物理站點的二維笛卡爾坐標 表達，公交網繼承道路網的屬性信息，同時還有專屬于公交線路的屬性信息， 公交線路記錄所有經過的邏輯站點序列、公交線路名稱、公交路線屬性，包括 公交路線的早班車和末班車發車時間，發車間隔、計價方式等。
(3) 軌道交通網和道3各網連通關系的建立 軌道交通網絡數據集包括無向的軌道線路、邏輯站點和物理站點。邏輯站
點是每條軌道線路中唯一標識的站點。物理站點為具有唯一地理坐標、唯一名 稱的軌道站點。除軌道交通換乘站外，物理站點與邏輯站點——對應。軌道交 通線路的基本屬性與公交網絡類似。
與公交系統不同，軌道交通模式與地面道路網絡之間不存在依附關系。軌 道交通線路層是一個獨立的圖層。當道路網絡幾何數據、交通路況發生變化， 或者車行道上進行交通管制時，僅對相關車行道上行駛的公交線路產生影響， 對軌道交通線路沒有影響。因此在構建連通關系時，僅構建軌道交通站點與車 行道之間的連通關系即可。
a. 軌道交通站點和;洛網車行道連通關系的建立
軌道交通站點通常有2-8個出口 ，意味著軌道交通站點可依附于多個車行 道。因此需要將每個出口站點匹配到相應的車行道上，并計算出偏移量。
b. 軌道交通連通關系的建立
由于軌道交通不依附于道路網，且一般上行和下行路線一致，因此軌道線 路在幾何上采用單線存儲，邏輯上采用線性參考方法存儲兩條對向路線。通過 軌道線路的起始(終止)位置到所基于的線性參考實體的起點的距離占線性參 考實體的總長度的百分比來表示其對向關系。
軌道交通網與道路網的模式轉換依靠軌道交通站點進行；與公交網的模式 轉換通常需要借助其他交通模式(如步行模式)進行。
(4) 興趣點(POI)層和道路網連通關系的建立
在現實世界中，雖然有些POI占據較大面積，屬于地址區域元素，但是這些POI并不是連續可接近的，只有通過入口點才能進入。因此將POI層抽 象為點圖層表示。將每個點匹配到相應的車行道上，并計算出偏移量。 (5 )步行設施層和道路網連通關系的建立
步行設施包括人行橫道，人行天橋和地下通道，通過步行設施連接兩條車 行道，但步行設施不能改變原路網層車行道的連通關系，僅能在邏輯步行網絡 中起到連通兩個車行道的作用。因此步行設施與車行道連通關系的建立，僅需 將步行設施所連接的兩條車行道與其匹配，并計算出偏移量。
基于上述多模式交通網絡，本發明實施例提供一種路徑搜索方法，根據用 戶指定的出行路徑標準，進行模式透明的權重分配，也可根據用戶需要對模式 權重進行孩i調，進而進行路徑搜索。最后，對多條路徑結果進行對比分析，選 出最符合用戶出行需求的路徑搜索結果，反饋給用戶。
如圖4所示，是本發明實施例路徑搜索方法的實現流程圖，包括以下步驟 步驟401,根據用戶指定的出行路徑標準分配不同模式網絡的優先級。 具體地，可以根據用戶選擇的標準，為各種模式網絡分配優先級值l—m,
m為最高優先級，l為最低，m的取值視所涉及的交通網絡數據的模式種類而
定，各種模式網絡的優先級允許相同。
所述用戶指定的出行路徑標準包括以下一項或多項換乘最少、距離最
短、時間最短、費用最低。
下面對各標準進行簡單說明
(1) 換乘最少在所有可行方案中，為用戶提供換乘次數最少的換乘方 案。該標準下，默認為出租車、步行優先，軌道交通、公共汽車其次。
(2) 距離最短計算出每種可行方案所提供路徑的長度，為用戶提供長 度最短的換乘方案。
(3) 時間最短采用動態路徑搜索算法和顧及步行模式的"點到點"的路 徑搜索策略，為用戶提供出行時間最短的出行方案。若無特殊交通模式指定， 在該標準下，默認軌道交通模式優先級最高，出租車模式次之，公交模式再次， 步行模式優先級最低。依次從大到小賦權重值，進行"高優先級擴展搜索，低 優先級模式連接，，搜索。
(4) 費用最低在所有可行方案中，為用戶提供費用最低的換乘方案，用戶指定模式對優先級有微調作用。如在時間最短標準下，若用戶選擇 軌道交通+公交模式組合，則公交模式的優先級僅次于軌道交通模式；若用戶 選擇公交+出租模式組合，則先進行公交搜索后進行出租車模式連接。
所述不同模式網絡可以是前面提到的兩種或多種網絡，比如，道路網、公 交網、軌道交通網、步行網、興趣點層、步行設施層。
步驟402，依照優先級從高到低的順序依次在不同模式網絡上進行路徑規 劃，直至填補所有路徑段。
也說是說，首先在高優先級模式網絡上選擇路徑段，此時選擇的路徑段可 能只是需要搜索的路徑中的一部分，其他部分還需要在低優先級模式網絡上進 行搜索，直到得到所有路徑段。也就是說，依據以下原則進行搜索高優先級 擴展搜索，低優先級模式連接，具體過程將在后面詳細描述。
步驟403，按照出行順序，依次連接路徑行進過程中在不同模式網絡上選 擇的路徑段，生成候選出行路徑。
具體地，從輸入起點O開始，依次連接路徑行進過程中涉及到的出行模 式，并加入模式轉換的耗費(如等待時間)，組成最終的出行路徑，直至輸入 終點D結束。
在本發明實施例中，還可進一步包括以下步驟根據所述用戶指定的出行 路徑標準，對所有候選出行路徑進行排序并輸出。這樣，可以方便用戶對出行 路徑的選擇。
如圖5所示，是本發明實施例中從不同模式網絡上選擇路徑段的流程圖'， 包括以下步驟
步驟501 ，輸入起點O和終點D;
步驟502，獲得m模式網絡下的起點集CT和終點集Dm ;
具體地，以起點O為搜索中心，以一定范圍為半徑，在最高優先級網絡 m上搜索所有可能的起點S,m ，生成在m模式網絡下的出發集 m = {S/",...，S;m};同樣地，以終點D為搜索中心，以一定范圍為半徑，在最 高優先級網絡m上搜索所有可能的終點S獷，得到m模式網絡下的終點集
1Dm = {Sgm，...，Sf};步驟503,判斷是否(T^ 0并且^T # 0 ,如是是，則轉步 驟504;否則轉步驟509;
步驟504，以S。m ( S。m e Om )和Sdm ( Sdm e Dm )為起點和終點，在m模 式網絡上運行路徑搜索算法；
步驟505,得到合適路徑存儲在LT(/，y'),對于LT(/j')中的每一條路徑尺f ,
m模式中的起點S/"和終點S)"將最終路徑分割為多個部分，也就是說，m模式 網絡中的路徑完成了整體路徑中的一部分，因此，接下來需要分別以O-S尸， Sj"-D為起點和終點，在m-l模式中進行路徑搜索；
步驟506，判斷m是否為l，也就是說，是否還有未搜索過的網絡；如果 是m不為l，則轉步驟507;否則轉步驟512;
步驟507,將m-l賦值給m，也就是說，選擇下一優先級的網絡進行路徑 搜索；
步驟508,分別以0-S/", Sf-D為起點和終點，在m-l模式網絡中進行 路徑搜索；然后轉步驟502;
步驟509,判斷m是否為l,也就是說，是否還有未搜索過的網絡；如果 是m不為l,則轉步驟510;否則轉步驟512;
步驟510,將m-l賦值給m，也就是說，選擇下一優先級的網絡進行;洛徑
搜索；
步驟511,以O-D為起點和終點，在m-l模式網絡中進行路徑搜索； 重復上述過程，即可完成所有路徑段的搜索。
需要說明的是，在上述路徑搜索過程中，若出現不同模式網絡具有相同的 優先級時，可以分別在優先級相同的模式網絡上進行計算，最終輸出的結果由 出行評價標準確定。
圖6為以上搜索得到的路徑的示意圖。
在時間最短標準下，地鐵優先級最高，因此首先搜索得到地鐵路徑，該路 徑同時將整體路徑分為三部分，對其余兩部分，在下一優先級模式中進行路徑 搜索，循環此過程，直至得到完整路徑。
在本發明實施例中，對于不同的交通模式網絡，可以采用不同的路徑搜索 算法，比如(1) 出租車模式路徑搜索算法
在融合歷史數據統計、短時交通預測以及交叉口延遲模型的基礎上，利用
離散時間切片方法，將基于四叉堆優先級隊列的Dijkstra算法進行了動態改造， 實現了時間依賴的動態最優路徑搜索，從而實現基于預測的動態出行服務。其 基本思路如下
首先，利用實時獲取的車行道段車速和車行道段長度，獲取該車行道段的 行程時間，將車行道段行程時間建模為時間依賴的變量，然后將時間離散化， 選取5分鐘為一個周期，建立車行道段的分時段常量行程時間函數；當路徑規 劃算法擴展到某車行道段L時，根據規劃路徑中已有的行程時間累計，可獲取 當用戶進入路幅段L時的時刻t,并根據預測模型獲取t時刻車行道段L的預 計行程時間T ( L ),從而實現靜態Dijkstra算法的動態改造。
運行時，系統調用數據庫中根據當前時刻的實時路況和預測服務器提供的 路網各車行道段平均車速，完成基于預測的動態路徑規劃。若在當前預測周期
內不能完成的出行過程，則在運行中途根據精確時間重新調用最新的預測結 果，以保證出行過程中所得到的交通預測信息的實時性，自適應地完成動態最 優出行路線的重新規劃。
(2) 公交模式路徑搜索算法 公交路徑搜索采用深度優先的遍歷搜索算法，其步驟如下
首先，對公交站點進行預先處理，建立站點間的鄰接關系。l)對可直達 站點建立鄰接關系；2)將每個站點300米內的所有站點可直達的站點集合加 到此站點可直達站點集合中；3 )再把每個站點可直達站點300米內的所有站 點加到此站點可直達站點集合中。以上步驟在預處理階,殳完成，只需計算一次。
然后，進行公交路徑搜索。對輸入的起點和終點確定兩地之間的距離，若 距離小于400米，則轉入步行模式計算，否則進行直達路徑搜索。
i.直達路徑搜索
由于直達路徑在站點預處理時已經存儲可直達站點，因此只需遍歷查找到 可直達的方案，對該方案計算行車耗費，靜態情況下采用下列預設分段函數V (t)取值(可根據城市交通狀況調整)15 周一、周五吝峰時殺 20 周一、周五白天半時
km/h
25 Jt他日半時時殺 、30 夜間時殺
動態情況下采用所獲取的實時路況和預測路況信息取值，計算臨近站點間 的行駛時間、進出站與等待耗費等，并根據所選擇標準進行輸出即可。
ii. 一次換乘路徑搜索
除搜索兩點間直達線路外，還需要考慮兩點間換乘路徑搜索。對于一次換 乘路徑搜索過程，如果換乘線路預計耗時大于兩點間直達線路，或者兩點間無 直達線路時，換乘線路長度大于起終點馬氏距離的120%,此換乘方案不予保 留。換乘車站間距在步行可容忍距離內方案有效，否則無效。對該方案計算行 車耗費，方法同直達路徑搜索，需要計算換乘耗費，若無需步行路徑連接中間 換乘，則換乘時間和等待時間需要計入該模式時間花費；若需要步行路徑連接 中間換乘，則換乘時間即為步行時間，等待時間仍需計入該方案時間花費。
iii. 二次換乘路徑搜索
不存在直達和一次換乘線路時才尋找二次換乘線路，相同換乘方案只保留 一個，參考一次換乘進行搜索。
(3 )軌道交通模式路徑搜索算法
基于四叉堆優先級隊列的Dijkstra算法，依照軌道交通運行時間表進行路 徑搜索，需要計算換乘耗費，若無需步行路徑連接中間換乘，則換乘時間和等 待時間需要計入該模式時間花費；若需要步行路徑連接中間換乘，則換乘時間 即為步行時間，等待時間仍需計入該方案時間花費。 (4)步行模式路徑搜索算法
基于四叉堆優先級隊列的Dijkstra算法，按照步行平均速度5km/h計算， 需要考慮過街耗費等。
本發明實施例還提供一種路徑搜索裝置，如圖7所示，是該裝置的一種結 構示意圖，包括
優先級設定單元701,用于根據用戶指定的出行路徑標準分配不同模式網 絡的優先級；路徑段選擇單元702,用于依照優先級從高到低的順序依次從不同模式網 絡上選擇路徑段，具體過程可參照前面圖5所示流程中的描述；
路徑生成單元703,用于按照出行順序，依次連接路徑行進過程中的不同 模式網絡上選擇的路徑段，生成候選出行路徑。
在本發明實施例中，還可進一步包括選擇輸出單元704,用于根據所述 用戶指定的出行路徑標準，對所有候選出行路徑進行排序并輸出。
所述不同模式網絡包括以下兩種或多種公交網、軌道交通網、步行網、 興趣點層、步行設施層。
本發明實施例路徑搜索裝置，基于上述多模式交通網絡，對公眾出行路徑 規劃服務涉及的多個交通模式特征實體之間的幾何與語義關系進行處理，從數 據建模階段進行針對性設計；進一步地，考慮到動態變化的路況信息對自駕車、 公交等多個交通模式下的出行過程產生影響，采用動態算法為用戶提供動態變 化的路線與出行模式，實現真正的多模式、多標準動態路徑規劃服務。
本發明改善了傳統公眾出行服務平臺中，僅能提供單一模式單一標準出行 服務的局面，能夠為用戶提供完善、詳細、符合用戶認知習慣和出行體驗的出 行方案，解決了公共出行服務平臺無法提供有效步行導航的缺陷，同時通過多 模式交通網絡連通關系的自動化構建，很大程度上提高了城市多模式交通網絡 信息組織、存儲、管理和維護的效率，為公眾出行信息服務提供了良好的技術 支持。
以上對本發明實施例進行了詳細介紹，本文中應用了具體實施方式
對本發 明進行了闡述，以上實施例的說明只是用于幫助理解本發明的裝置及方法；同 時，對于本領域的一般技術人員，依據本發明的思想，在具體實施方式
及應用 范圍上均會有改變之處，綜上所述，本說明書內容不應理解為對本發明的限制。
權利要求
1.一種步行網建立方法，其特征在于，包括在導航路網線數據集中提取出步行道；建立步行設施點與步行道之間的映射關系；將步行設施由點抽象為弧段，生成跨街節點和跨街步行道；利用所述跨街節點對所述跨街節點所在的原步行道進行分割，生成新的步行道；根據所述跨街節點對提取出的步行道、生成的新的步行道和生成的跨街步行道間的連通關系進行重建，構成拓撲完整的步行網，所述步行網為無向網絡。
2. 根據權利要求1所述的方法，其特征在于，所述在導航路網線數據集中 提取步行道包括獲取道路網車行道集尺；通過屏蔽道路網車行道集f 中不允許步行通過的車行道，得到步行道集合f '。
3. 根據權利要求2所述的方法，其特征在于，所述建立步行設施點與步行 道之間的映射關系包括對每一個步行設施點i,才艮據步行設施的語義屬性，在步行道集合尺'中尋 找與之相匹商己的步行道，建立映射關系(1 : m )， 記為 M(/) = {n,/"2，...，A"m I n，...，廠m e尺'};對M(/)中的每一個元素，才艮據反向車行道屬性，判斷其對向步行道，若其對向步行道不在/W(/')中，則將其對向步行道添加至M(/)中，記為/W'(/); 對每一個步行設施點i,在M'(/)中利用空間臨近分析，得出最合適的步行道待擴展對/vr(/')。
4. 根據權利要求3所述的方法，其特征在于，所述生成跨街節點和跨街 步行道包括對每一個步行設施點i,對步行道待擴展對/vr(/)中的步行道對做垂線，選取垂足在所做垂線的目標步行道上，并且垂線段之和最小的步行道對為待處 理步行道對，垂足為新生成的跨街節點，將新生成的跨街節點存儲在跨街節點 集合A/r中，并從相關步行道繼承屬性值；根據新生成的跨街節點，擴展步行設施點i，使點要素擴展成為線要素，生成跨街步行道，加入步行道集合f '中，并將步行設施點的屬性值繼承到跨 街步行道屬性中。
5. 根據權利要求4所述的方法，其特征在于，所述利用所述跨街節點對 所述跨街節點所在的原步行道進行分割，生成新的步行道包括跨街節點集合A/r中的每一個跨街節點分割原步行道段，生成新的步行道， 所述新的步行道保持原步行道名稱、類型，并對所述跨街步行道賦予新的標識、 起始和終止節點；將所述新的步行道加入步行道集合f '中。
6. 根據權利要求2所述的方法，其特征在于，所述根據所述跨街節點對 提取出的步行道、生成的新的步行道和生成的跨街步行道間的連通關系進行重 建，構成拓樸完整的步行網包括根據步行道集合尺'中的弧段生成無向拓樸，重建步行道間的連通關系， 構成拓樸完整的步行網。
7. 根據權利要求1至6任一項所述的方法，其特征在于，還包括 在興趣點上完成所述步行網與道路網的模式轉換；和/或 通過公交站點完成所述步行網與公交網的模式轉換；和/或 通過軌道交通站點完成所述步行網與軌道交通網的模式轉換。
8. —種步行網建立裝置，其特征在于，包括 步行道提取單元，用于在導航路網線數據集中提取出步行道； 映射關系建立單元，用于建立步行設施點與步行道之間的映射關系； 跨街步行道生成單元，用于將步行設施由點抽象為弧段，生成跨街節點和跨街步行道；步行道分割生成單元，用于利用所述^爭街節點對所述跨街節點所在的原步 行道進行分割，生成新的步行道；拓樸關系建立單元，用于根據所述跨街節點對提取出的步行道、生成的新 的步行道和生成的跨街步行道間的連通關系進行重建，構成拓樸完整的步行 網，所述步行網為無向網絡。
9. 根據權利要求8所述的裝置，其特征在于，所述步行道提取單元包括 獲取子單元，用于獲取道路網車行道集R;屏蔽子單元，用于通過屏蔽道路網車行道集R中不允許步行通過的車行 道，得到步行道尺'。
10. 根據權利要求8或9所述的裝置，其特征在于，還包括 第一轉換單元，用于在興趣點上完成所述步行網與道路網的模式轉換；和/或第二轉換單元，用于通過公交站點完成所述步行網與公交網的模式轉換； 和/或第三轉換單元，用于通過軌道交通站點完成所述步行網與軌道交通網的模 式轉換。
11. 一種路徑搜索方法，其特征在于，包括根據用戶指定的出行路徑標準分配不同模式網絡的優先級； 依照優先級從高到低的順序依次從不同模式網絡上選擇路徑段； 按照出行順序，依次連接路徑行進過程中的不同模式網絡上選擇的路徑 段，生成候選出行路徑。
12. 4艮據權利要求11所述的方法，其特征在于，還包括 根據所述用戶指定的出行路徑標準，對所有候選出行路徑進行排序并輸出。
13. 根據權利要求ll或12所述的方法，其特征在于，所述用戶指定的出 行路徑標準包括以下一項或多項換乘最少、距離最短、時間最短、費用最低。
14. 根據權利要求11或12所述的方法，其特征在于，所述不同模式網絡 包括以下兩種或多種道路網、公交網、軌道交通網、步行網、興趣點層、步行設施層。
15. 根據權利要求11或12所述的方法，其特征在于，所述依照優先級從 高到低的順序依次從不同模式網絡上選擇路徑段包括(1) 以起點O為搜索中心，以預定范圍為半徑，在最高優先級網絡m上 搜索所有可能的出發點S尸，存儲結果在m模式下的出發集CT二(S/77，…,S]77} 中；(2) 以終點D為搜索中心，以預定范圍為半徑，在最高優先級網絡m上 搜索所有可能的終點S^，得到m模式下的終點集/T ={Sgm,...,Skm};(3 )如果CT # 0并且D"7 # 0 ,則執行步驟(4 );否則執行步驟(6 ); (4)以S。m和S^為起點和終點，在模式m上進行路徑搜索，將得到的路徑存 儲在LT(/，"中，其中，S。meOm, SdmeDm;(5)分別以0-Sr, Sf-D為起點和終點，在m-l模式中進行路徑搜索， 然后執行步驟(7 );(6 )以O-D為起點和終點，在m-l模式中進行路徑搜索；(7)重復步驟(1)至步驟(7),直至得到所有路徑段。
16. 根據權利要求15所述的方法，其特征在于，如果不同模式網絡具有相同的優先級，則分別在所述不同模式網絡上選擇 最佳路徑。
17. 根據權利要求15所述的方法，其特征在于，所述按照出行順序，依 次連接路徑行進過程中的不同模式網絡上選擇的路徑段，生成候選出行路徑包 括從輸入起點O開始至終點D結束，依次連接路徑行進過程中涉及到的出 行模式，組成出行路徑。
18. —種路徑搜索裝置，其特征在于，包括優先級設定單元，用于根據用戶指定的出行路徑標準分配不同模式網絡的 優先級；路徑段選擇單元，用于依照優先級從高到低的順序依次從不同模式網絡上 選擇路徑,殳；路徑生成單元，用于按照出行順序，依次連接路徑行進過程中的不同模式 網絡上選擇的路徑段，生成候選出行路徑。
19. 根據權利要求18所述的裝置，其特征在于，還包括 選擇輸出單元，用于根據所述用戶指定的出行路徑標準，對所有候選出行路徑進行排序并輸出。
20. 根據權利要求18或19所述的裝置，其特征在于，所述不同模式網絡 包括以下兩種或多種道路網、公交網、軌道交通網、步行網、興趣點層、步行設施層。
全文摘要
本發明公開了一種步行網建立方法及裝置，所述方法包括在導航路網線數據集中提取出步行道；建立步行設施點與步行道之間的映射關系；將步行設施由點抽象為弧段，生成跨街節點和跨街步行道；根據所述跨街節點對提取出的步行道和生成的跨街步行道間的連通關系進行重建，構成拓撲完整的步行網。本發明還公開了一種多模式多標準路徑搜索方法及裝置。利用本發明，可以依據現有交通網自動構建步行網，為公共出行服務平臺提供有效步行導航，進而建立多種交通模式間的連通關系，根據出行者選擇的不同標準，提供個性化的出行方案，為公眾出行信息服務提供更好的技術支持。
文檔編號G01C21/34GK101614551SQ20091008885
公開日2009年12月30日 申請日期2009年7月21日 優先權日2009年7月21日
發明者于海璁, 段瀅瀅, 鋒 陸 申請人:中國科學院地理科學與資源研究所
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
