TWI277723B - Navigation system, route search server, route search method and recording medium - Google Patents

Description

-1277723 九、發明說明： 【發明所屬之技術領域】 本發明係關於一種探索並導引從出發地直到目的地爲 止之最適路徑的導航系統、路徑探索伺服器、路徑探索方法 與程式，尤其，關於一種存在數個目的地點或出發地點之情 形下，利用一次路徑探索處理而能探索最適路徑之導航系 統、路徑探索伺服器、路徑探索方法與程式。 所謂存在數個目的地點或出發地點之路徑探索，例如， 欲探索主體公園或典禮會場、交通機關之車站等、存在數個 出入口之路徑探索，或是從現在位置或目的地直到位於附近 範圍之便利商店或加油站等感興趣地點（POI : Point of I n t e r e s t )爲止路徑的情形等。 【先前技術】 到目前爲止，已知道利用地圖資料、道路資料，探索從 所期望之出發地直到目的爲止之路徑而導引利用者之導航 裝置、導航系統。 作爲如此之導航裝置、導航系統係一種搭載於汽車內， 對駕駛進行路徑導引之導航裝置，將行動電話作爲導航終端 利用而將路徑探索要求發送至路徑探索伺服器，收到此結果 之訊息後，接受路徑導引的通訊型導航系統等已被實用化。 尤其’通sJl型導航系統係一1種將行動電話等行動終端作 爲導航終端利用的系統，也可以作爲行人用導航系統。作爲 行人用導航系統較宜附加包含交通機關之路徑導引機能，增 加利用道路網路資料之汽車或徒步路徑之探索與導引，並將 -1277723 交通機關之路線或行駛時刻資料作爲交通網路資料而予以 累積儲存。 如此之行人用導航系統具有將從所期望之出發車站直 到所期望之目的車站爲止之路徑（乘車之列車選項）加入徒 步路徑之探索與導引的機能。另外，也存在一種交通導引系 統，其不隨著徒步路徑之路徑探索，而是接受來自資訊傳送 伺服器，收到顯示交通機關之路線或時刻表、可乘車之列車 等資訊傳送。 另外，利用飛機、列車、電車、汽車等交通手段而探索 並導引從出發地直到目的地爲止路徑之路徑探索系統已爲 人所習知。一般而言，如此之路徑探索系統係根據利用者所 指定的出發日期時間、出發地、目的地、到達時刻等路徑探 索條件而進行路徑探索。 亦即’參照已將各交通機關之路線資料或行駛時刻資料 予以資料化後的交通網路資料，包括換乘而將出發地與目的 地予以連結’將可利用之各交通手段作爲路徑而依序進行探 索’提示一個或數個符合路徑探索條件之導引路徑（列車等 交通手段）之選項。一般而言，路徑探索條件進一步作成能 指定如所需要之時間、換乘次數、車資等條件。 利用該道路網路資料，進行路徑探索而得到的從出發地 直到目的地爲止之路徑中，使路徑累計費用（距離或時間） 成爲最小的路徑作爲最佳導引路徑而加以決定，作成導引路 徑資料。於導引路徑資料中，除了最佳路徑資料之外，也包 含地圖資料、導引資料，必要的話，導引路徑資料係從導引 •1277723 . i 資料記憶手段予以讀出後顯示於顯示手段。 一般而言，於含有使用已具備導航裝置之GP S收訊機所 定位的導航裝置現在位置之一定比例尺、一定範圍之地圖 上，使導引路徑與顯示導航裝置現在位置之標記相重疊，並 使該現在位置標記成爲顯示畫面中心般之予以顯示。 由於使用GPS收訊機所定位的位置資訊中含有誤差，現 在位置偏離導引路徑之情形下，進行將現在位置修正於導引 路徑上的路徑匹配處理或是修正於地圖上最新道路上的匹 零配處理。 另外，於導引路徑資料中設定十字路口等導引點，於其 導引點上之簡介附加聲音導引（例如，「前方3 00m爲十字 路口，請左轉」等聲音訊息）資料之情形，利用擴音器，進 行聲音訊息之再生輸出而導引利用者。 如此之導航系統、路徑探索方法，例如，由本發明案申 請人等揭示於下列專利文獻1(日本專利特開2000-258 1 84 號公報）之「交通網路路徑探索方法與裝置」。 1 此路徑探索導航系統係一種將地點作爲節點、將地點間 作爲鏈路，再將從出發地直到目的地爲止之路徑表現成爲道 路網路、交通網路之資料，利用電腦並藉由水平確定法，於 最低費用之條件下，進行徒步區間、交通機關利用區間之探 索。 於此路徑探索方法中，從出發地點與目的地點直到所利 用之交通機關車站爲止之路徑係採用緯度經度資料而求出 從出發地點與目的地點直到所利用之交通機關車站爲止之 ‘1277723 直線距離，將該直線距離作爲變數而算出平均費用。 然後，該平均費用求出包含於所指定的費用範圍內之所 有利用交通機關的車站而決定步行路徑，將所求得的步行路 徑建構於交通機關之交通網路路徑後，顯現綜合交通網路， 利用電腦並藉由水平確定法所求得的費用條件下進行探索。 具有徒步與利用交通機關之路徑探索的情形、於車站存 在數個出入口之情形。習知考慮數個出入口，從出發地直到 最近車站之各出入口爲止的徒步路徑、或是從最近車站之各 ® 出入口直到目的地爲止的徒步路徑中，探索距離成爲最短路 徑的路徑探索方法。例如，由本發明案申請人等揭示於下列 專利文獻2 (日本專利特開2003- 1 82578號公報）之「最佳 路徑探索裝置、最佳路徑探索方法」。 一旦此最佳路徑探索裝置指定出發地、目的地、出發預 定日期時間之探索條件後進行探索指示時，最佳路徑探索部 利用道路資料與交通機關之時刻表資料決定出發地附近之 一個或數個出發車站選項與目的地附近之一個或數個目的 ® 車站選項。然後，於各出發車站選項與各目的車站選項之組 合中，藉由徒步與交通機關之組合，因應於指定探索條件而 進行從出發地直到目的地爲止之最短時間內可移動的最佳 路徑般之予以構成的。出發車站選項或目的車站選項具有數 個出入口時，將出發地附近之最近一個出入口作爲出發車站 選項或目的車站選項之車站位置，探索最佳路徑般之予以構 成的。 第9圖與第1 0圖係顯示揭示於該專利文獻2之最佳路 •1277723 , » 徑探索裝置的習知路徑探索槪念之說明圖，第9圖係顯示從 出發地（START)起，直到最近車站與其出入口爲止之路徑 探索槪念，第1 〇圖係顯示從最近車站與其出入口直到目的 地（GOAL )爲止之習知路徑探索槪念的說明圖。 一旦藉由利用交通機關之路徑探索而進行從出發地直 到目的地爲止之電車路徑、最近車站之探索時，接著，如第 9圖所示，最佳路徑探索裝置依序探索從出發地（START) 起，直到最近車站ST1、ST2與其各個出入口 A1〜A4、A5、 鲁 A6爲止之最短徒步路徑RT1〜RT4、RT5、RT6。因而，徒步 路徑之探索次數成爲相當於出入口數目之次數。 接著，如第1 0圖所示，依序探索從目的地側之各最近 車站3丁3、8丁4與其出入口81、82、83、34直到目的地（00八乙） 爲止之最短路RP1、RP2、RF1、RF2。因而，徒步路徑之探 索次數成爲相當於出入口數目之次數。還有，於第9圖、第 1 0圖，L 1〜L4表示電車路線，R0係顯示挑選從出發地 (START)起之最近車站ST1與ST2的範圍、目的地（GOAL) 1 側之最近車站ST3與ST4的範圍之半徑距離。 另外，於導航系統中，以特定之目的地、出發地爲路徑 探索條件而要求路徑探索伺服器進行路徑探索之情形以 外，不以特定地點爲目的，往往進行到達符合某條件之地點 的路徑探索要求。例如，以某設施爲目的地而利用車進行移 動之情形下，因爲無論如何必須停車，設施周邊之停車場往 往成爲實質之目的地。此情形下，若爲周邊之停車場的話， 因爲無論何處均可，總之，希望欲以停車場作爲目的地。 - 1 0 - 1277723 也有人提案一種可進行如此路徑探索之導航系統，例 如，揭示於下列專利文獻3 (日本專利特開2 0 0 3 · 0 5 7 0 5 7號 公報）之「停車場資訊檢索方法、停車場資訊檢索系統與程 式」。此停車場資訊檢索系統係根據來自終端裝置之路徑探 索條件，網路導航中心進行路徑探索之際，網路導航中心進 行目的地周邊數個停車場之檢索，除了探索直到各停車場爲 止之最短路徑以外，欲導引成爲最近路徑之停車場而予以構 成的。 另外，往往要求探索向特定主體公園或博覽會會場等特 定區域之路徑。第1 1圖係顯示如此之特定區域地圖的圖形。 如第1 1圖所示，於典禮會場之特定區域設置三處出入口 G 1 〜G3。如此之情形’利用者尙未辨別特定區域之數個出入 口，辨別以整個該區域爲目的地，其出入口之中，一般要求 從出發地直到最近的出入口爲止之路徑導引。 如此之路徑探索，也如習知之路徑探索伺服器中，揭示 於該專利文獻3之停車資訊檢索方法般之，個別地重複進行 從出發地直到各出入口 G1〜G3爲止之路徑探索，導引最短 出入口或導引按距離近的順序之幾個建議路徑。 【專利文獻1】日本專利特開2000-258184號公報（第 4圖） 【專利文獻2】日本專利特開2 0 0 3 - 1 8 2 5 7 8號公報（第 9圖、第10圖） 【專利文獻3】日本專利特開2003-057057號公報（第 3 圖、第 6 圖、段落〔0089〕、〔 0090〕） 1277723 【發明內容】 發明所欲解決之技術問顆 於導航系統中，具有希望含有如該停車場導引的情形， 希望最近車站數個出入口之中的最短徒步路徑之出入口導 引的情形。於如此之路徑探索中，如該專利文獻3所揭示的 導航系統，於網路導航中心（路徑探索伺服器）側，若根據 選取目的地周邊停車場而探索直到各停車場爲止路徑之構 造的話，則爲如下之程序。 亦即，若從出發地起的話，路徑探索伺服器重複進行直 到所選出的各停車場爲止之路徑探索，探索至各個停車場之 最短路徑，一旦探索至各個停車場之最短路徑時，路徑探索 伺服器係將從出發地起向最近停車場之路徑或是將從出發 地起按距離較近順序之數條路徑作爲導引路徑而傳送至終 端裝置。 第12圖係顯示探索從出發地（START)起，直到目的 地附近之最近POI爲止路徑的習知路徑探索槪念之示意 圖。於第1 2圖中，習知之路徑探索方法係選出目的地附近 之某區域（AR )內的感興趣地點（POI )，例如，感興趣地 點爲停車場之情形，選出G 1〜G5。然後，路徑探索伺服器 係探索從出發地（START)起，向停車場G1之最佳路徑。 圖中，從出發地（START)起之箭號係槪念地顯示路徑探索 的方向。 接著，路徑探索伺服器係探索從出發地（START)起， 向停車場G2之最佳路徑，進行同樣之方式，從出發地 1277723 (START )起，向停車場G3、停車場G4、停車場G5之最 佳路徑。亦即，此情形下，相對於各個停車場G1〜G5，路 徑探索伺服器進行5次路徑探索。其結果係將所得到的離出 發地（START )最近的停車場與直到最近停車場爲止之路 徑，或是從出發地（START)直到停車場爲止之按距離較近 的順序之2〜3條路徑選項而提供至終端裝置。 亦即，於專利文獻3所揭示的導航系統中，路徑探索伺 服器僅重複地選出向各停車場之路徑探索的停車場數目，將 ® 有路徑探索伺服器之探索處理負荷變得過大的問題點。 於通訊型導航系統中，由於向路徑探索伺服器之要求導 引係從各終端裝置起隨機進行的，要求導引將一時集中，若 對路徑探索伺服器之路徑探索處理負荷集中的話，伺服器將 當機，發生終端裝置側之待機時間將增大之不便的問題點。 即使以徒步方式從出發地走到最近車站之情形下，若車 站入口爲數個時，相同於該停車場之情形，由於僅設定路徑 探索伺服器側車站入口數目之目的地而重複進行路徑探 ^ 索，求得最近的入口，具有與上述同樣的問題點。 如此路徑探索要求具有各式各樣之情形，除了將該車站 出入口或停車場設爲探索條件之情形以外，例如，對具有數 個會場出入口之主體公園或萬國博覽會會場的資訊存取，因 而對目的地周邊之便利商店或加油站、餐廳或旅館等之利用 者感興趣地點（POI )的資訊存取之路徑探索要求等。 本申請案之發明人等爲了解決該問題點，不斷進行各種 探討之結果，來自數個POI所位置的節點，將利用鏈路費用 1277723 〇之鏈路所連接的假想節點（無緯度與經度之位置資訊）追 加於探索用網路資料中，若以一次路徑探索進行直到該假想 節點爲止路徑的路徑探索的話，基於找到能夠導引以離出發 地點最近的路徑即能到達的路徑之觀點，於是完成本發明。 亦即，本發明係以解決該問題點作爲課題，目的在於提 供一種導航系統、路徑探索伺服器、路徑探索方法與程式， 於存在數個目的地點或出發地點之情形下，利用一次路徑探 索處理而能探討最佳路徑。 • 解決問題之技術丰跺 爲了解決該課題，有關本申請案之申請專利範圍第1項 的發明’其係一種導航系統，利用探索用網路資料而探索從 出發節點直到目的節點爲止之路徑； 該導航系統具備··累積感興趣地點屬性資訊的P 01屬性 資訊資料庫、網路資料編輯手段與假想節點設定手段；其特 徵爲： 根據出發地與/或目的地，並參照P0I屬性資訊資料庫 ®而辨別於出發地與/或目的地是否存在數個P0I ; 於存在數個POI之情形下，該假想節點設定手段設定利 用與該數個POI各節點具有鏈路費用爲等値之鏈路而予以 連接的假想節點；及 該網路資料編輯手段將該假想節點追加於該探索用網 路資料中’路徑探索手段利用已追加該假想節點之探索用網 路資料而進行路徑探索。 另外’有關本申請案之申請專利範圍第2項的發明係於 1277723 有關申請專利範圍第1項之導航系統中’其特徵爲：從該 ροι直到假想節點爲止的鏈路費用値爲〇。 另外，有關本申請案之申請專利範圍第3項的發明係於 有關申請專利範圍第1項或第2項之導航系統中，其特徵 爲：該導航系統構造上具備：發送路徑探索條件訊息之導航 終端裝置與藉由網路而連接於該導航終端裝置之路徑探索 伺服器。 有關本申請案之申請專利範圍第4項的發明，其係一種 路徑探索伺服器，其係藉由網路而連接於發送路徑探索條件 訊息之導航終端裝置； 該路徑探索伺服器具備：累積感興趣地點屬性資訊的 P 〇1屬性資訊資料庫、網路資料編輯手段與假想節點設定手 段；其特徵爲： 根據出發地與/或目的地，並參照Ρ0Ι屬性資訊資料庫 而辨別於出發地與/或目的地是否存在數個Ρ0Ι ; 於存在數個Ρ0Ι之情形下，該假想節點設定手段設定利 用與該數個POI各節點具有鏈路費用爲等値之鏈路而予以 連接的假想節點；及 該網路資料編輯手段將該假想節點追加於該探索用網 路資料中，路徑探索手段利用已追加該假想節點之探索用網 路資料而進行路徑探索。 另外’有關本申請案之申請專利範圍第5項的發明係於 有關申請專利範圍第4項之路徑探索伺服器中，其特徵爲： 從該P 01直到假想節點爲止的鏈路費用値爲0。 1277723 有關本申請案之申請專利範圍第6項的發明，其係一種 路徑探索方法，其利用探索用網路資料而探索從出發節點直 到目的節點爲止之路徑； 該導航系統具備：累積感興趣地點屬性資訊的POI屬性 資訊資料庫、網路資料編輯手段與假想節點設定手段；其特 徵上包含： 根據出發地與/或目的地，並參照POI屬性資訊資料庫 而辨別於出發地與/或目的地是否存在數個POI之步驟； ® 於存在數個POI之情形下，該假想節點設定手段設定利 用與數個POI各節點具有鏈路費用爲等値之鏈路而予以連 接的假想節點之步驟；及 該網路資料編輯手段將該假想節點追加於該探索用網 路資料中，路徑探索手段利用已追加該假想節點之探索用網 路資料而進行路徑探索之步驟。 另外，有關本申請案之申請專利範圍第7項的發明係於 有關申請專利範圍第6項之路徑探索方法中，其特徵爲：包 ® 含從該POI直到假想節點爲止的鏈路費用値爲0之步驟。 有關本申請案之申請專利範圍第8項的發明，其係一種 路徑探索方法，其構造上具備：發送路徑探索條件訊息之導 航終端裝置與藉由網路而連接於該導航終端裝置之路徑探 索伺服器； 該路徑探索伺服器具備：累積感興趣地點屬性資訊的 P 01屬性資訊資料庫、網路資料編輯手段與假想節點設定手 段；其特徵上包含： -16- •1277723 根據出發地與/或目的地，並參照ρ〇ι屬性資訊資料庫 而辨別於出發地與/或目的地是否存在數個p〇l之步驟； 於存在數個p 01之情形下，該假想節點設定手段設定利 用與該數個Ρ0Ι各節點具有鏈路費用爲等値之鏈路而予以 連接的假想節點之步驟；及 該網路資料編輯手段將該假想節點追加於該探索用網 路資料中，路徑探索手段利用已追加該假想節點之探索用網 路資料而進行路徑探索之步驟。 另外’有關本申請案之申請專利範圍第9項的發明係於 有關申請專利範圍第8項之路徑探索方法中，其特徵爲··包 含從Ρ0Ι直到假想節點爲止的鏈路費用値設爲〇之步驟。 有關本申請案之申請專利範圍第1 0項的發明，其係程 式’其連接於發送路徑探索條件訊息之導航終端裝置與藉由 網路而連接於該導航終端裝置之路徑探索伺服器；其特徵 爲· 於構成具備：已累積感興趣地點屬性資訊的Ρ ο I屬性資 訊資料庫、網路資料編輯手段與假想節點設定手段之路徑探 索伺服器的電腦中， 實行根據出發地與/或目的地，並參照p 〇 I屬性資訊資 料庫而辨別於出發地與/或目的地是否存在數個P 〇 I之處理； 於存在數個Ρ0Ι之情形下，實行該假想節點設定手段設 定利用與該數個Ρ0Ι各節點具有鏈路費用爲等値之鏈路而 予以連接的假想節點之處理；及 實行該網路資料編輯手段將該假想節點追加於該探索 -1 7 - •1277723 j 1 用網路資料中，路徑探索手段利用已追加該假想節點之探索 用網路資料而進行路徑探索之處理。 另外，有關本申請案之申請專利範圍第1 1項的發明係 於有關申請專利範圍第1 〇項之程式中，其特徵爲：於構成 該路徑探索伺服器之電腦中，實行從POI直到假想節點爲止 的鏈路費用値設爲0之處理。 【發明之效果】 於有關申請專利範圍第1項之發明中，導航系統具備： ® 累積感興趣地點之屬性資訊的POI屬性資訊資料庫、網路資 料編輯手段與假想節點設定手段，根據出發地與/或目的 地’並參照POI屬性資訊資料庫而辨別於出發地與/或目的 地是否存在數個POI。 而且’於存在數個POI之情形下，該假想節點設定手段 設定利用與該數個P 0 I各節點、具有鏈路費用爲等値之鏈路 而予以連接的假想節點；及網路資料編輯手段將該假想節點 追加於該探索用網路資料中，路徑探索手段利用已追加該假 ® 想節點之探索用網路資料而進行路徑探索。 由於從假想節點PN連結各停車場G 1〜G5鏈路之鏈路 費用與實際距離無關，全部爲「〇」，假想節點PN與各p 〇 I 之距離假想爲等距離的。因而，若經由特定p 〇〗的路徑爲最 短距離的話’此路徑成爲從出發地（START )直到各POI 爲止路徑之中的最短路徑，便能夠利用一次路徑探索而提供 數個POI之中的最近POI與到達最近p〇I之路徑。 有關申請專利範圍第2項之發明中，於有關申請專利範 -18- 1277723 ] » 圍第1項發明的導航系統中，從POI直到假想節點爲止的鏈 路費用之値爲0。因而，於路徑探索中，不會發生向周邊之 探索擴散，便能夠進行有效率的路徑探索。 有關申請專利範圍第3項之發明中，於有關申請專利範 圍第1項或第2項發明的導航系統中，導航系統構造上具 備：發送路徑探索條件訊息之導航終端裝置與藉由網路而連 接於該導航終端裝置之路徑探索伺服器。因而，便能夠提供 一種通型導航系統，另外，路徑探索伺服器便能夠利用一次 ® 路徑探索而提供數個POI之中的最近POI與到達最近POI 之路徑。 有關申請專利範圍第4項、第5項之發明中，能夠提供 一種構成有關各個申請專利範圍第1項、第2項發明之導航 系統的路徑探索伺服器，路徑探索伺服器便能夠利用一次路 徑探索而提供數個POI之中的最近POI與到達最近P0I之 路徑。 有關申請專利範圍第6項、第7項之發明中，能夠提供 ® —種有關各個申請專利範圍第1項、第2項發明之導航系統 的路徑探索方法，便能夠利用一次路徑探索而提供數個P0I 之中的最近POI與到達最近P0I之路徑。 有關申請專利範圍第8項、第9項之發明中，能夠提供 一種有關各個申請專利範圍第4項、第5項發明之路徑探索 伺服器的路徑探索方法，路徑探索伺服器便能夠利用一次路 徑探索而提供數個P0I之中的最近P0I與到達最近P0I之 路徑。 -19- 1277723 有關申請專利範圍第1 0項、第1 1項之發明中，能夠提 供一種爲了實現有關各個申請專利範圍第4項、第5項發明 之路徑探索伺服器的程式，路徑探索伺服器便能夠利用一次 路徑探索而提供數個ΡΟΙ之中的最近ΡΟΙ與到達最近ΡΟΙ 之路徑。 【發明之實施形態】 以下，利用實施例與圖式詳細說明本發明之具體例。第 1圖係顯示本發明路徑探索槪念之示意圖，其探索從出發地 ® ( START)起，存在於目的地（GOAL)附近之某區域（AR) 的數個感興趣地點（POI ) G1〜G5之中，到達最近POI之路 【實施例】 還有，於下列本發明實施例之說明中，包含感興趣地 點、具有數個出入口之車站等、存在數個地點之出發地點或 目的地點而總稱爲感興趣地點（POI )，但是，明確表示爲 車站出入口或特定主體公園等之出入口的情形下，也稱爲出 •入口。 於第1圖中，若選出目的地周邊之停車場G1〜G5的 話，路徑探索伺服器係設定從各停車場G 1〜G5之節點位置 起，利用具有鏈路費用爲「0」之値的鏈路所連接的假想節 點PN。爲了路徑探索，此假想節點PN暫時連接於路徑探索 網路，由於僅用於鏈路費用累計之演算，並無必要具有如路 徑探索網路節點般之由緯度、經度而成的位置資訊。另外， 因爲假想節點僅於路徑探索上爲必要的，並無顯示之必要。 -20- -1277723 因而’將位置資訊之値設定於假想節點的處理則完全無其必 要。 若設定假想節點PN的話，路徑探索伺服器探索從出發 地（START )直到假想節點pn爲止之最佳路徑GR。於此路 徑探索中，由於從假想節點PN連結各停車場G1〜G5鏈路 之鏈路費用係與實際之距離無關，全部爲「〇」，假想節點 PN與各停車場G 1〜G5的距離假想爲等距離的。 因而’若經由停車場G3之路徑爲最短距離的話，此路 鲁徑便成爲從出發地（START)直到各停車場G1〜G5爲止路 徑之中的最短路徑，於是，能夠利用一次路徑探索而將數個 停車場G 1〜G5之中的最近停車場與到達此最近停車場爲止 之路徑提供至導航終端裝置20。 於此，從各停車場G1〜G5向假想節點PN的鏈路之鏈 路費用，理論上各値相等的話即可，經常數値並無爲「0」 之必要。然而，鏈路費用爲「0」以外之値的情形下，於路 徑探索時，Dykstra法之擴散將有僅向此値部分周邊推進的 ^ 可能性，將有路徑探索處理時間增大的情形。 此點上，若鏈路費用之値爲「〇」的話，探索到達假想 節點PN之時間點，路徑探索處理將結束。亦即，若假想節 點PN的鏈路費用之値爲「0」的話，能夠進行有效率的路徑 探索處理。 第2圖係顯示有關本發明實施例之導航系統構造的方塊 圖。有關本發明實施例之導航系統1 〇具備藉由如顯示於第2 圖之方塊圖的網際網路等網路1 1而進行通訊的導航終端裝 -21 - 1277723 置2 0與路徑探索伺服器30所構成的。 導航終端裝置20係設定出發地與目的地等路徑探索條 件而將路徑探索要求傳送至路徑探索伺服器3 0，路徑探索伺 服器3 0係遵循路徑探索條件，並參照由道路網路資料、交 通網路資料而成的探索用網路資料後進行最佳路徑之探 索，將此最佳路徑編輯於導引路徑資料中而傳送至導航終端 裝置2 0。 路徑探索伺服器30具備：道路網路資料36，含有爲了 ^ 行人導航系統或車導航系統之路徑探索的地圖資料之道路 網路資料3 6、爲了探索利用交通機關之路徑區間的交通網路 資料37之探索用網路資料35 (資料庫）與累積POI屬性資 訊之POI屬性資訊DB (資料庫）40。 累積於POI屬性資訊DB40之POI屬性資訊係如第3圖 所示，累積各感興趣地點（POI )之位置座標（緯度與經度） 與屬性資訊，於屬性資訊中，累計至該POI之鏈路端點的節 點數與各節點之位置資訊，另外，累積各POI之類別。 ® 例如，POI之A爲主體公園A，連接於該主體公園之鏈 路，亦即，出入口鏈路有三處，累積此三處鏈路端點節點之 位置。萬國博覽會等典禮會場、主體公園、交通機關之各車 站出入口也爲相同的。此等POI與其屬性資訊能夠藉由網路 12,路徑探索伺服器30從POI資訊提供伺服器50進行收集 (參照第2圖）。 導航終端裝置20進行以特定之主體公園或典禮會場爲 目的地之路徑探索要求的情形，路徑探索伺服器3 0係參照 -22- -1277723 , 1 POI屬性資訊DB40而辨別該主體公園是否具有數個典禮會 場之出入口。於利用交通機關之路徑探索中，探索目的地或 出發地之最近車站的情形，探索直到該最近車站爲止之徒步 路徑區間之際也是相同的，參照POI屬性資訊DB40而辨別 於最近車站是否具有數個出入口。具有數個出入口之情形， 路徑探索伺服器3 0設定該假想節點而進行路徑探索。 另外，針對停車場、加油站、便利商店、旅館等之POI， 將此類別資訊作爲屬性資訊而加以記錄。路徑探索條件係於 β 具有從導航終端裝置2 〇直到目的地或出發地附近之特定 Ρ 〇 I，例如，從加油站之中的最近加油站爲止的路徑要求之 情形下，路徑探索伺服器30參照ΡΟΙ屬性資訊DB 40而選 出目的地或出發地附近之該ΡΟΙ。然後，路徑探索伺服器30 係以所選出的ΡΟΙ作爲數個目的地，設定該假想節點後進行 路徑探索。 假想節點設定手段3 9 (參照第2圖）係於進行數個Ρ0Ι 之路徑探索的情形，或進行包含具有數個出入口之目的地或 ® 出發地的路徑探索之情形，如第1圖所說明的，設定從所選 出的各POI或出入口之節點起，利用鏈路費用「〇」所連接 的假想節點PN。網路資料編輯手段3 8進行將已設定假想節 點設定手段3 9之假想節點Ρ N暫時追加於探索用網路資料 3 5之資料中的處理。 然後，路徑探索手段3 3係藉由網路資料編輯手段3 8進 行將已追加於探索用網路資料3 5中之假想節點pn作爲目的 地或出發地的路徑探索。基於從導航終端裝置2〇之路徑探 -23- •1277723 索條件而要求從特定之出發地直到目的地爲止之 的一般情形下’當然使用尙未追加假想節點P N之 路資料3 5而進行路徑探索。 路徑導引手段3 2係一種爲了編輯路徑探索手 索的最佳路徑或數個推薦導引路徑資料後傳送至 裝置2 0的手段，通訊手段3 4係一種爲了收到來自 裝置20之各種要求的訊息，或是爲了將各種資訊 航終端裝置20的手段。 ® 用以行人導航系統或車導航系統之路徑探索 路資料3 6係如下所構成的。例如，道路爲由第4 道路A、B、C而成的情形，將道路A、B、C之端 路口、彎曲點等作爲節點，利用有方向性之鏈路表 節點間之道路，藉由將節點資料（節點之緯度與經 路資料（鏈路編號）與各鏈路之鏈路費用（鏈路之 駛鏈路必要所需的時間）作成資料的鏈路費用資 的。 ^ 亦即，於第4圖中，Nn (〇記號）、Nm ( ◎ 示節點，Nm (◎記號）表示道路之十字路口。利 (實線、點線、二點鏈線）表示連結各節點間的有 鏈路。雖然存在朝向道路之上行、下行各方向的鏈 於桌4圖爲了簡化圖不，僅圖示箭號方向之鏈路。 將如此之道路網路資料作爲路徑探索用資料 路徑探索之情形，循著從出發地節點直到目的地節 連結的鏈路，累積其鏈路費用，探索累積鏈路費用 路徑探索 探索用網 段3 3所探 導航終端 導航終端 傳送至導 的道路網 圖所示之 點、十字 示連結各 [度）、鏈 距離或行 料所構成 記號）表 用箭號線 方向性之 路，但是， > 庫而進行 i點爲止所 丨成爲最少 -24- -1277723 j 1 的路徑而進行導引。亦即，於第4圖中，將出發地作爲節點 AX，將目的地作爲節點CY而進行路徑探索之情形，依序循 著從節點AX行駛道路A而於第二個十字路口右轉進入道路 C而到達節點C Y的鏈路，累積鏈路費用，探索鏈路費用之 累積値成爲最少的路徑後進行導引。 於第4圖，雖然從節點AX到達節點C Y之其他路徑並 未予以圖示，實際上由於如此之路徑也存在其他路徑，進行 同樣方式，探索從節點AX至節點CY之可能的路徑，決定 ® 將此等路徑之中的鏈路費用成爲最少的路徑作爲最佳路 徑。此手法係藉由例如所謂Dykstra法之習知手法所進行的。 針對於此’用以交通機關路徑探索之交通網路資料3 7 係如下所構成的。如第5圖所示，例如由交通路線A、B、C 而成的情形，將設置於各交通路線A、B、C之各車站（於 飛機路線則爲各機場）作爲節點，利用有方向性的鏈路表示 連結各節點間之區間，將節點資料（緯度與經度）、鏈路資 料（鏈路編號）作爲網路資料。於第5圖中，Nn (〇記號）、 ® Nm (◎記號）表示節點，Nm (◎記號）表示交通路線之換 乘點（換乘車站等），利用箭號線（實線、點線、二點鏈線） 表示連結各節點間的有方向性鏈路。雖然存在向道路之上 行、下行各方向的鏈路，但是，於第5圖爲了簡化圖示，鏈 路僅圖示箭號方向。 然而，相較於道路網路，基本上交通網路之鏈路費用不 同。亦即，道路網路方面，鏈路費用爲固定的、靜態的，交 通網路方面，如第5圖所示，進行交通路線行駛的列車或飛 -25 - 1277723 機（以下，將各個列車或飛機等之各路徑稱爲交通手段）有 數個。決定各個交通手段之進行某節點出發的時刻與到達下 一個節點的時刻（利用時刻表資料、行駛資料加以規定）， 並且’各個路徑有不一定鏈接於相鄰接的節點之情形。例 如’如急行列車與各站停車之列車的情形。如此之情形下， 於相同的交通路線上便存在不同的數個鏈路，另外，也有視 交通手段而於節點間所需要之時間不同的情形。 於第5圖所例示之交通網路中，於交通路線A之相同鏈 ® 路上成爲存在數個交通手段（路徑）A a〜A c…、於交通路線 C上成爲存在數個交通手段（路徑）Ca〜cc···。因而，交通 機關之行駛網路不同於單純之道路網路，節點、鏈路、鏈路 費用之各資料成爲正比於交通手段（各飛機或列車等路徑） 總數的資料量。因此，相較於道路網路之資料量，交通網路 資料成爲龐大的資料量。因而，因應於此，路徑探索需要更 多的時間則成爲必要的。 利用如此之交通網路資料，爲了探索從某出發地直到某 ® 目的地爲止之路徑，探索從出發地直到目的地爲止到達之際 能使用（乘車）的所有交通手段而有必要特定符合探索條件 之交通手段。 例如，於第5圖中，將出發地作爲交通路線A之節點 AX而指定某特定之出發時刻，進行以交通路線C之節點CY 作爲目的地之路徑探索的情形，將行駛交通路線A上之交通 手段Aa〜Ac···之中的出發時刻以後的所有交通手段作爲依 序出發時之路徑而加以選擇。然後，根據向交通路線C之換 -26- -1277723 > » 乘節點的到達時刻，便於行駛交通路線C上之各交通路線 Ca〜Cc···之中的換乘節點，探索可乘車之時刻以後的交通手 I又之所有組合，累積各路徑所需時間或換乘次數等而進行導 另一方面，導航終端裝置20具備控制手段2 1、通訊手 段22、定位手段23、顯示手段24、導引路徑資料記憶手段 25、要求發送訊息之編輯手段26、操作與輸入手段27所構 成的。定位手段23具備GPS收訊機，接收並處理GPS衛星 β訊號後進行導航終端裝置2 〇現在位置（緯度與經度）之定 位。 通訊手段22包含無線通訊單元，此爲了與路徑探索伺 服器3進行通訊之物。操作與輸入手段27係由按鍵、轉盤 等而成的，爲了進行導航終端裝置20操作的輸入，作爲出 發地、目的地等輸入機能所使用的。顯示手段24係由液晶 顯示面板等而成的，使用於從路徑探索伺服器3 0所發送的 導引路徑資料之導引路徑、地圖顯示。另外，顯示手段24 1 係顯示選項畫面而發揮爲了操作導航終端裝置20之輸入手 段的機能。要求發送訊息之編輯手段26係以使用操作與輸 入手段27所輸入的出發地、目的地或是利用定位手段23所 定位的導航終端裝置20之現在位置作爲出發地，根據此等 資訊而作成傳送訊息至路徑探索伺服器3 0之路徑探索要求。 導引路徑資料記憶手段25記憶從路徑探索伺服器30所 傳送的路徑探索結果之導引路徑資料、地圖資料、簡介等， 必要的話，此等資料從導引路徑資料記憶手段25讀出而顯 -27- Ί277723 示於顯示手段24。一般而言，於含有利用定位手段23所定 位之導航終端裝置20現在位置之一定比例尺、一定範圍的 地圖上，使導引路徑與顯示導航終端裝置20之現在位置的 標記相重疊，使該現在位置標記成爲顯示畫面中心般之加以 顯示。 由於藉由定位手段23而收到GPS衛星訊號所定位之現 在位置資訊（緯度與經度之資訊）中含有誤差，現在位置偏 離導引路徑之情形下，於導引路徑上進行修正現在位置之匹 ^配處理。另外，從路徑探索伺服器3 0所發送訊息之導引路 徑資料上，附加聲音導引（例如，附加「前方3 00公尺爲十 字路口。請左轉」等聲音訊息）資料的情形係藉由擴音器而 進行聲音訊息之再生輸出後導引利用者。 接著，針對有關以上說明之本發明實施例的導航系統1 0 之路徑探索方法加以說明。針對根據於目的地側存在數個出 入口或POI之情形的本發明所得到的路徑探索槪念，參照第 1圖所說明的。同樣的路徑探索於出發地側也爲可能的。第 ^ 6圖係顯示針對目的地（GOAL)而於出發地側之車站ST1 存在數個出入口 A 1〜A5之情形的圖形。 若進行出發地最近車站ST1之探索的話，路徑探索伺服 器係參照車站ST1之POI屬性資訊DB40，辨別出入口是否 有數個。如第6圖所示，車站ST1有數個出入口 A1〜A5之 情形，設定利用具有從出入口 A 1〜A5節點位置之鏈路費用 爲「〇」之鏈路所連線的假想節點PN。此假想節點PN係爲 了路徑探索而連接於路徑探索網路，並無必要具有由緯度、 -28 - 1277723 經度而成的位置資訊。 一旦設定假想節點PN時，路徑探索伺服器探索從假想 節點PN直到目的地（GO AL )爲止之最佳路徑GR。於此路 徑探索中，由於從假想節點PN連結各出入口 A 1〜A5之鏈 路的鏈路費用係與實際距離無關而全部爲「0」，假想節點 PN與出入口 A1〜A5之距離假想爲等距離的。 因而，若經由出入口 A3之路徑RT1爲最短距離的話， 其路徑將成爲出發地側出入口 A 1〜A 5路徑之中的最短路 胃徑。因而，便能夠利用一次路徑探索而將從數個出入口 A 1 〜A5之中直到目的地（GOAL)爲止的最近出入口與直到目 的地（GOAL )爲止的路徑提供至導航終端裝置20。 進行同樣方式，於出發地側、目的地側均具有數個出入 口或POI之情形的路徑探索也爲可能的。第7圖係爲了說明 如此路徑槪念之說明圖。第7圖係從導航終端裝置20之路 徑探索中，於出發地側最近的車站等之POI存在數個出入口 A1〜A5，顯示於目的地側之主體公園等P0I，存在數個出入 ® 口 G1〜G5之情形。 如此之路徑探索要求，若從導航終端裝置20向路徑探 索伺服器3 0進行要求的話，路徑探索伺服器3 0首先參照POI 屬性資訊DB40而辨別於各個出發地側、目的地側是否分別 存在數個出入口。數個出入口存在之情形，選出各出入口 A1〜A5，G1〜G5。接著，假想節點設定手段39係從各個出 發地側出入口 A 1〜A5起，設定利用鏈路費用「0」之鏈路所 連接的假想節點PN1，並從各個目的地側之出入口 G1〜G5 -29- -1277723 » » 起’設定利用鏈路費用「〇」之鏈路所連接的假想節點ρΝ2。 接著，於路徑探索伺服器3 〇中，網路資料編輯手段3 8 將假想節點ΡΝ 1、ΡΝ2暫時追加於探索用網路資料3 5中。 於第7圖中，點線示意表示探索用之網路，追加假想節點 ΡΝ1、ΡΝ2。路徑探索手段33利此探索用網路資料35而探 索從假想節點ΡΝ 1至假想節點ΡΝ2之最佳路徑。 此探索能夠利用Dykstra法等、於一般路徑探索所用之 手法等進行。亦即，雖然實際上進行路徑探索之範圍成爲於 ^ 實際之探索用網路上，但是，藉由設置假想節點ΡΝ 1 (出發 地側）與假想節點ΡΝ2 (目的地側），其間所求出的最佳路 徑具有同時特定出發地與目的地之特徵。 由於假想節點Ρ Ν 1與各出入口 A 1〜A 5之間的鏈路費用 全部爲「0」且相等，假想節點PN2與各出入口 G1〜G5之 間的鏈路費用全部爲「0」且相等，路徑探索之結果，可以 得到從假想節點ΡΝ 1至假想節點PN2之最短路徑RT 1，此最 短路徑RT 1所經由的出發地側之出入口 A5與目的地側之出 ^ 入口 G1便分別成爲出發地側、目的地側之最佳出入口。 還有，第7圖之情形，由於出發地側係從出發地起一定 範圍內之交通機關的車站，路徑RT 1係以交通機關之路線路 徑爲中心。另外，探索包含目的地側之主體公園出入口 G1 的最近車站之導引路徑，探索從最近車站直到出入口 G1爲 止的徒步路徑，探索綜合的導引路徑RT1。從出發地至出發 地側之最近車站出入口’此情形下’ A5之間的路徑係作爲 徒步區間而進行路徑探索。 -30- -1277723 I » 以上，針對所說明的導航裝置之路徑探索順序，參 示於第8圖之流程圖而加以說明。於步驟S 1 0之處理上 徑探索伺服器3 0接收來自於導航終端裝置20之路徑探 件的訊息。 一旦路徑探索伺服器3 0收到路徑探索條件之訊息 首先於步驟S 1 1之處理中，調查出發地側之條件，於步驟 之處理中，參照POI屬性資訊DB40，辨別於出發地側 存在數個POI。於出發地側不存在數個POI的話，進行 ^ S 1 4之處理，以出發地作爲出發地節點而加以決定。 於步驟S12之處理中，於出發地側存在數個P0I 形，假想節點設定手段3 9係從數個P 〇1之各個節點起 定利用鏈路費用「〇」之鏈路所連接的假想節點（出發地f 進行步驟S 1 5之處理。於步驟s 1 5之處理中，路徑探索 器3 〇調查目的地側之條件，於步驟S 1 6之處理中，參照 屬性資訊DB4 0,辨別於目的地側是否存在數個P0I。於 地側，若不存在數個Ρ ΟI的話，進行步驟S 1 7之處理， ®的地作爲目的地節點而加以決定。 於步驟S 1 6之處理中，於目的地側存在數個ρ 〇丨之 係於步驟S 1 8之處理中，假想節點設定手段3 9係從數個 之各個節點起，設定利用鏈路費用「〇」之鏈路所連接 想節點（目的地側），進行步驟S 1 9之處理。於步驟S】 處理中，網路資料編輯手段3 8係將已設定假想節點設 段3 9之出發地側的假想節點與目的地側的假想節點暫 加於探索用網路資料中，路徑探索手段3 3係利用已追 照顯 ，路 索條 時， S12 是否 步驟 之情 ，設 U )， 伺服 POI 目的 以目 情形 POI 的假 丨9之 定手 時追 加假 -31- •1277723 1 、 想節點之探索用網路資料而探索從出發地側之假想節點直 到目的地側之假想節點爲止的最佳路徑。 還有，於出發地側或目的地側不存在數個POI，於步驟 S 1 4或步驟S 1 7之處理中，以出發地或目的地作爲出發地節 點或目的地節點而加以決定之情形，當然於步驟S 1 9之處理 中的節點並非假想節點，可使用於出發地節點或目的地節 點。 於步驟S 1 9之處理中，若藉由路徑探索手段3 3進行最 ® 佳路徑之探索的話，於步驟S20之處理中，路徑探索伺服器 3 0係將已探索的導引路徑資料，發送至導航終端裝置20後 結束處理。收到導引路徑資料之導航終端裝置20係將導引 路徑資料暫時記億於導引路徑資料記憶手段25中，將地圖、 導引路徑等顯示於顯示手段24。 還有，於該實施例中，針對具有數個出入口之主體公 園，說明參照POI屬性資訊DB40而設定假想節點之構造， 預先將假想節點之資料累積儲存於POI屬性資訊DB40中， ® 假想節點設定手段39也能夠作成從POI屬性資訊DB40取得 假想節點資料的構造。 【產業上利用之可能性】 以上說明有關本發明的路徑探索方法能利用於數個目 的地或數個出發地所想定的各種探索。有效於利用汽車導航 探索加油站之情形、利用行人導航探索便利商店之情形等。 由於探索本身可使用習知之演算法，即使車導航等之 STAND ARON裝置也無需大幅修正程式，便可能實施。 -32- -1277723 > ' 【圖式簡單說明】 第1圖係顯示本發明路徑探索槪念之示意圖，探索從出 發地（START )起，存在於目的地附近某區域（AR )的數個 感興趣地點（P〇I)Gl〜G5之中，到達最近POI爲止之路徑。 第2圖係顯示有關本發明實施例之導航系統構造的方塊 圖。 第3圖係顯示累積感興趣地點等Ρ〇ι屬性資訊之資料庫 的資料構造圖形。 ^ 第4圖係顯示道路網路資料槪念之示意圖。 第5圖係顯示交通網路資料槪念之示意圖。 第6圖係爲了說明於出發地側車站存在數個出入口之情 形的路徑探索槪念之說明圖。 第7圖係爲了說明於出發地側、目的地側二者存在數個 出入口或POI之情形的路徑探索槪念之說明圖。 第8圖係顯示本發明導航系統之路徑探索順序的流程 圖。 ^ 第9圖係爲了說明探索從出發地起，向具有數個出入口 之最近車站路徑的習知路徑探索方法槪念之說明圖。 第10圖係爲了說明探索從具有數個出入口之最近車站 起向目的地路徑的習知路徑探索方法槪念之說明圖。 第11圖係爲了說明向具有主體公園等數個出入口之特 定區域的路徑探索方法槪念之說明圖。 第1 2圖係爲了說明探索向數個目的地點路徑的習知路 徑探索方法槪念之說明圖。 -33- J277723 【元件符號說明】 10 導航系統 1 1、1 2 網路 2 0 導航終端裝置 2 1 控制手段 22 通訊手段 23 定位手段 2 4 顯示手段

25 導引路徑資料記億手段 26 要求發送訊息之編輯手段 27 操作與輸入手段 30 路徑探索伺服器 3 1 控制手段 32 路徑導引手段 33 路徑探索手段 34 通訊手段 35 探索用網路資料 36 道路網路資料 37 交通網路資料 38 網路資料編輯手段 39 假想節點設定手段 40 POI屬性資訊DB (資料庫） 50 POI資訊提供伺服器 -34-

Claims (1)

1277723 ^ f π替換霣 第95 1 008 30號「導航系統、路徑探索伺服器、路徑探索方法 及記錄媒體」專利案 (2006年11月14日修正） 十、申請專利範圍： 1 · 一種導航系統，係利用探索用網路資料以探索從出發節點直到 目的節點爲止之路徑，其特徵爲： 該導航系統具備累積有感興趣地點之屬性資訊的PQI屬性 資訊資料庫、網路資料編輯手段與假想節點設定手段， Φ 且根據出發地與/或目的地，並參照ΡΟΙ屬性資訊資料庫而 辨別在出發地與/或目的地是否存在有數個Ρ0Ι ; 於存在有數個P 01之情形下，該假想節點設定手段係設定是 利用與該數個POI各節點具有鏈路費用爲等値之鏈路而進行 連接的假想節點；及 該網路資料編輯手段將該假想節點追加於該探索用網路資 料中’路徑探索手段係利用已追加了該假想節點之探索用網路 資料而進行路徑探索。 修2 ·如申請專利範圍第1項之導航系統’其中從該p 〇〗直到假想節 點爲止的鏈路費用値爲0。 3.如申請專利範圍第1項或第2項之導航系統，其中該導航系統 係具備發送路徑探索條件之導航終端裝置與藉由網路而連接 於該導航終端裝置之路徑探索伺服器而構成。 4 · 一種路徑探索伺服器’係藉由網路而連接於發送路徑探索條件 之導航終端裝置，其特徵爲 該路徑探索伺服器具備累積有感興趣地點之屬性資訊的 POI屬性資訊資料庫、網路資料編輯手段與假想節點設定手 1277723 …· — —， , '. n v. 段， .. j ' 且根據出發地與/或目的地，並參照POI屬性資訊資料庫而 辨別在出發地與/或目的地是否存在有數個P〇J ; 於存在有數個POI之情形下，該假想節點設定手段係設定是 利用與該數個POI各節點具有鏈路費用爲等値之鏈路而進行 連接的假想節點；及 該網路資料編輯手段將該假想節點追加於該探索用網路資 料中’路徑探索手段係利用已追加了該假想節點之探索用網路 • 資料而進行路徑探索。 5·如申請專利範圍第4項之路徑探索伺服器，其中從該p0I直到 假想節點爲止的鏈路費用値爲〇。 6. —種路徑探索方法，係利用導航系統之探索用網路資料而探索 從出發節點直到目的節點爲止之路徑，其特徵爲： 該導航系統具備累積有感興趣地點之屬性資訊的p〇I屬性 資訊資料庫、網路資料編輯手段與假想節點設定手段， 且該路徑探索方法包含： ® 根據出發地與/或目的地，並參照POI屬性資訊資料庫而辨 別在出發地與/或目的地是否存在有數個P0I之步驟； 於存在有數個POI之情形下，該假想節點設定手段係設定是 利用與數個POI各節點具有鏈路費用爲等値之鏈路而進行連 接的假想節點之步驟；及 該網路資料編輯手段將該假想節點追加於該探索用網路資 料中’而路徑探索手段利用已追加了該假想節點之探索用網路 資料而進行路徑探索之步驟。 7 ·如申請專利範圍第6項之路徑探索方法，其中包含將從該p〇I 1277723

直到假想節點爲止的鏈路費用値設爲0之步驟。 8. —種導航系統中之路徑探索方法，該導航系統係具備發送路徑 探索條件之導航終端裝置與藉由網路而連接於該導航終端裝 置之路徑探索伺服器而構成者，其特徵爲： 該路徑探索伺服器具備累積有感興趣地點之屬性資訊的 ΡΟΙ屬性資訊資料庫、網路資料編輯手段與假想節點設定手 段， 該路徑探索方法包含： Φ 根據出發地與/或目的地，並參照ΡΟΙ屬性資訊資料庫而辨 別在出發地與/或目的地是否存在有數個ΡΟΙ之步驟； 於存在有數個ΡΟΙ之情形下，該假想節點設定手段係設定是 利用與該數個ΡΟΙ各節點具有鏈路費用爲等値之鏈路而進行 連接的假想節點之步驟；及 該網路資料編輯手段將該假想節點追加於該探索用網路資 料中，路徑探索手段係利用已追加了該假想節點之探索用網路 資料而進行路徑探索之步驟。 馨9.如申請專利範圍第8項之路徑探索方法，其中包含將從該ΡΟΙ 直到假想節點爲止的鏈路費用値設爲〇之步驟。 1 0.—種電腦可讀取之記錄媒體，係記錄有可在構成如下路徑探索 伺服器之電腦中進行以下處理之程式，該路徑探索伺服器係藉 由網路而與發送路徑探索條件之導航終端裝置相連接，且具備 已累積有感興趣地點之屬性資訊的ΡΟΙ屬性資訊資料庫、網路 資料編輯手段與假想節點設定手段，該程式在電腦中所進行之 處理爲· 實行根據出發地與/或目的地，並參照ΡΟΙ屬性資訊資料庫 1277723 γ ，替換· • - ' Λ 而辨別在出發地與/或目的地是否存在有數個Ρ〇Ι之處理； • 於存在有數個P 〇 I之情形下’實行該假想節點設定手段設定 ’ 利用與該數個POI各節點具有鏈路費用爲等値之鏈路而進行 連接的假想節點之處理；及 實行該網路資料編輯手段將該假想節點追加於該探索用網 路資料中，路徑探索手段利用已追加了該假想節點之探索用網 路資料而進行路徑探索之處理。 11 ·如申請專利範圍第1 〇項之電腦可讀取之記錄媒體，其中於構 Φ 成該路徑探索伺服器之電腦中，實行將從該POI直到假想節 點爲止的鏈路費用値設爲〇之處理。

-4 -