JP4708323B2 - ナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置 - Google Patents

Description

本発明は、徒歩や自動車あるいは公共交通機関を利用して、任意の出発地から目的地に至る経路のうちから最適経路や候補経路を探索して案内するナビゲーションシステムに関するものであり、特に、公共交通機関を利用した移動区間について、事故や故障により通行不能な区間が発生しても、迂回経路を用いて目的地に所定の時刻に到着することができるように、推奨経路として迂回経路を含めて複数の経路を探索して案内できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。

従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。

特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。

一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。

情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。

交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。

また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。

交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。

徒歩経路に加えて交通機関を用いた経路を探索するナビゲーションシステムは、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に開示されている。この特許文献２に開示されたナビゲーションシステムは、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法を用いるものである。

そして、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するように構成されている。

従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのままあるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。

交通機関を利用した推奨経路を案内する場合、現在位置を出発し、目的地に所望の時間に到着するために、現在位置を何時に出発すればよいかを案内して欲しいという要求もある。このような要求の中には、例えば、勤務先などを現在位置として、現在位置を最も遅い時刻に出発して自宅（目的地）に終電で帰宅可能な推奨経路および勤務先を出発すべき時間（終電に乗車あるいは乗り継ぎするために勤務先を出発すべき時間）を案内して欲しいという、いわゆる終電探索の要求もある。

ある目的駅に、ある特定の時刻に到着するために現在位置を何時までに出発すればよいかを案内するナビゲーションシステムは、例えば、下記の特許文献３（特開２００３−５８６６３号公報）や特許文献４（特開２００３−２５４７７７号公報）に開示されている。

上記特許文献３に開示された乗り換え案内サービス提供システムは、終電を利用するためにユーザに現在位置を何時に出発すればよいかを案内するシステムであり、ユーザの携帯端末は、ＧＰＳ受信機等の現在位置検出手段を備えていて、得られた位置情報を用いて乗り換え案内情報の検索を行う。乗り換え案内サービスを提供するＷｅｂサーバは、その位置情報を用いて携帯端末の現在位置から出発駅までの移動時間を算出し、算出されたその移動時間を考慮して、指定された電車に乗車するためには現在位置を何時までに出発しなければならないかをユーザに提供するように構成されている。このような構成のため、ユーザは、終電等に乗り遅れたり、無駄な待ち時間を過ごしたりすること無く目的の電車に乗車できる。

また、上記特許文献４に開示された移動情報通知システムは、ある目的駅にある時刻に到着するために現在地を出発すべき時刻の通知サービスを自動で行うようにしたシステムであり、メインサーバが、外部接続されるＧＰＳシステムを用いて得られるユーザの現在位置に基づき当該ユーザの現在位置に近い最寄駅を調べ、かつ、外部接続される駅探索システムを用い、最寄駅からユーザ情報データベースにあらかじめ登録済みの目的駅までの経路と、その時刻表リストを検索する。そして、検索された時刻表リストに基づき、ある目的駅にある時刻に到着するために現在地を出発すべき時刻を算出し、目的駅までの経路と出発すべき時刻とを通知希望時刻に従いユーザ端末へ自動的に通知するように構成したものである。

特開２００１−１６５６８１号公報（図１、図２） 特開２０００−２５８１８４号公報（図３、図４） 特開２００３−５８６６３号公報（図２、図３） 特開２００３−２５４７７７号公報（図１、図３）

所望の出発地を出発して所定時刻にある目的地に到達する経路の探索（到着時刻指定探索）においては、上記特許文献３に開示された移動情報通知システムのように、経路探索の結果、最適経路や候補経路が示され、経路毎に出発地を何時に出発して移動すればよいかが示される。

しかしながら、このような案内方法では、案内された最適経路や候補経路において何らかの事故や支障が生じた場合、目的地に予定した時刻に到着できない恐れがある。特に、遅刻できないイベント、例えば、顧客との会議に出席する場合や、航空機に搭乗する空港を目的地とする場合、所定の時刻に目的地に到着できないと重大な結果を招くことがある。

このような場合、目的地への到着時刻に余裕を持たせた経路探索条件を設定して経路案内を受ける方法が一般的であるが、設定する到着時刻にどの程度の余裕を持たせれば安全かは、利用者の判断に委ねられ、安全性の程度は不確かであるという問題点があった。すなわち、従来は利用者の勘に頼って余裕度をみていたため、そもそも迂回したら遅刻する出発時刻を選択していることもあった。また、案内された経路に支障が生じた場合に、迂回できる経路があるかは、複数の推奨経路を探索して、利用者が判断するしかないという問題点があった。

本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、迂回できる経路は、出発駅から出発方向（最初の利用路線が同じあるいは最初の駅が同じ経路）の同じ複数の経路であり、かつ、所定の時刻に同じ目的地に到着することができる複数の経路であることから、経路探索において出発駅から出発して所定の時刻に目的地に到着できる複数の候補経路を探索し、次に、予め設定した余裕度の範囲内で出発駅を最も早く出発する候補経路の出発時刻に基づいて、所定の時刻に目的地に到着できる候補経路を再探索して、出発時刻の早い順に推奨経路と迂回経路として案内するようになせば、上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。

すなわち、本発明は上記の問題点を解消することを課題とし、公共交通機関を利用して、任意の出発地から目的地に至る経路を探索して案内するナビゲーションシステムにおいて、通行不能な区間が発生しても、迂回経路を用いて目的地に所定の時刻に到着することができるように迂回経路を含む複数の推奨経路を案内することができるナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置を提供することを目的とするものである。

前記課題を解決するために、本願の請求項１にかかる発明は、
経路探索用のネットワークデータを参照して出発地から目的地まで、交通機関を利用した経路を含む案内経路を探索する経路探索手段と、前記経路探索手段が探索した案内経路データを記憶する案内経路記憶手段と、前記案内経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、設定された出発地を出発して設定された時刻に設定された目的地に到着できる複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
前記候補経路グルーピング手段は、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段は、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする。

本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記迂回経路探索手段は、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Kに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索し、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする。

本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記迂回経路探索手段は、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行うことを特徴とする。

また、本願の請求項４にかかる発明は、
所望の出発地と目的地を設定する端末装置とネットワークを介して接続され、前記端末装置からの要求に基づき、設定された２地点間の複数の候補経路を探索する経路探索サーバにおいて、
前記経路探索サーバは、経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
前記候補経路グルーピング手段は、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段は、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする。

本願の請求項５にかかる発明は、請求項４にかかる経路探索サーバにおいて、前記迂回経路探索手段は、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索し、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする。

本願の請求項６にかかる発明は、請求項５にかかる経路探索サーバにおいて、前記迂回経路探索手段は、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行うことを特徴とする。

また、本願の請求項７にかかる発明は、
所望の出発地と目的地を設定する端末装置とネットワークを介して接続され、前記端末装置からの要求に基づき、設定された２地点間の複数の候補経路を探索する経路探索サーバにおける経路探索方法において、
前記経路探索サーバは、経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
前記候補経路グルーピング手段が、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングするステップと、前記迂回経路探索手段が、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力するステップを有することを特徴とする。

本願の請求項８にかかる発明は、請求項７にかかる経路探索方法において、前記迂回経路探索ステップは、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索する処理を含み、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする。

本願の請求項９にかかる発明は、請求項８にかかる経路探索方法において、前記迂回経路探索ステップは、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行う処理を含むことを特徴とする。

また、本願の請求項１０にかかる発明は、
経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
前記候補経路グルーピング手段が、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段が、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、少なくとも迂回経路の探索と、出発地と、目的地と、目的地に到着すべき時刻と、を経路探索条件として設定する操作入力手段を備えたことを特徴とする。

本願の請求項１１にかかる発明は、請求項１０にかかる端末装置において、前記端末装置は、表示手段を備え、前記推奨経路を示す情報と迂回経路を示す情報とを候補経路グループごとに前記表示手段に表示することを特徴とする。

請求項１にかかる発明においては、ナビゲーションシステムは、設定された出発地を出発して設定された時刻に設定された目的地に到着できる複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、前記候補経路グルーピング手段は、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段は、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力する。

このような構成によれば、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路が案内できるので、利用者は設定した余裕度に応じて案内された推奨経路に従って移動中に、何らかの障害が発生しても、案内された迂回経路に乗り換えて、所定の時刻までに目的地に到着できるようになる。

請求項２にかかる発明においては、請求項１にかかる発明において、前記迂回経路探索手段は、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索し、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力する。

このような構成によれば、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、予め設定されたＫ番目の候補経路の出発時刻を用いて、出発地の出発時刻を基準とした経路であって目的地への到着時刻を満足する経路が探索されるので、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路を案内することができるようになる。

請求項３にかかる発明においては、請求項２にかかる発明において、前記迂回経路探索手段は、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行う。

このような構成によれば、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、予め設定されたＫ番目の候補経路の出発時刻を用いて、出発地の出発時刻を基準とした経路であって目的地への到着時刻を満足する経路を探索する際、交通機関に関する制限条件を緩和して経路探索するから、探索される迂回経路の範囲を広げることができる。従って、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路が案内できるので、利用者は設定した余裕度に応じて案内された推奨経路に従って移動中に、何らかの障害が発生しても、所定の時刻までに目的地に到着できる迂回経路の選択肢を拡大することができるようになる。

請求項４ないし請求項６にかかる発明においては、それぞれ請求項１ないし請求項３にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになる。また、請求項７ないし請求項９にかかる発明においては、それぞれ請求項４ないし請求項６にかかる経路探索サーバにおける経路探索方法を提供することができ、請求項１０、請求項１１にかかる発明においては、請求項１ないし請求項３にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。

以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。

本発明の実施例にかかるナビゲーションシステム１０は、図１に示すように、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。なお、本実施例においては、通信型の経路探索、案内経路を提供するナビゲーションシステム１０を具体例として説明するが、本発明はこれに限ることなく、本発明を実現するためのアプリケーションを搭載すればスタンドアロンタイプのナビゲーション装置などにも適用可能である。本発明においては、交通機関の時刻表に基づく交通ネットワークデータを用いた探索も行うので、携帯電話を端末とし、常に最新の時刻表データを用いたサーバ・クライアント型のナビゲーションシステムとして構成すると好適である。

経路探索サーバ３０は、経路探索のため道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを交通ネットワークデータとして蓄積したデータベース（ＤＢ２）、交通機関の各電車等の運行ダイヤに基づく時刻表や運賃を蓄積した時刻表・運賃データのデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。時刻表・運賃データは、ネットワークを介して情報配信サーバ５０から取得することができる。

図２は、本発明の実施例にかかるナビゲーションシステム１０の詳細な構成を示すブロック図である。本発明の実施例にかかるナビゲーションシステム１０は、図２のブロック図に示すようにインターネットなどのネットワーク１２を介して通信する端末装置２０と、経路探索サーバ３０と、情報配信サーバ５０を備えて構成されている。
端末装置２０は、経路探索サーバ３０に出発地と目的地などの経路探索条件を設定して経路探索要求を送信し、経路探索サーバ３０は、経路探索条件に従って、道路ネットワークデータ３８、交通ネットワークデータ３９を参照して最適経路または複数の候補経路を探索し、その最適経路または複数の候補経路のデータを端末装置２０に配信する。

端末装置２０は、制御手段２１、通信手段２２、ＧＰＳ受信手段２３、表示手段２４、案内記憶手段２５、設定条件記憶手段２６、操作入力手段２７を備え構成される。制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２２はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。ＧＰＳ受信手段２３は、ＧＰＳ受信機を備えＧＰＳ衛星信号を受信、処理して端末装置２０の現在位置（緯度・経度）を測位する。

操作入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力、出発地、目的地などの入力操作などのために用いられる。表示手段２４は液晶表示パネル等からなり、経路探索サーバ３０から配信された経路データの表示および地図の表示に使用されるものである。また、表示手段２４はメニュー画面を表示し端末装置２０をメニュー画面操作によって端末装置２０の操作を行う。従って表示手段２４は、端末装置２０を操作するための操作入力の手段としても機能する。

設定条件記憶手段２６は、操作入力手段２７を使用して入力された出発地、目的地、あるいは、ＧＰＳ受信手段２３で測位した端末装置２０の現在位置を出発地として、その他の経路探索条件を記憶し、これらの情報に基づいて、経路探索サーバ３０に経路探索要求が送信される。

案内記憶手段２５は、経路探索サーバ３０から配信された経路探索結果である案内経路データ、地図データ、ガイダンスなどを記憶するものであり、これらのデータは必要に応じて案内記憶手段２５から読み出され、表示手段２４に表示される。一般的には、ＧＰＳ受信手段２３で測位した端末装置２０の現在位置を含む一定縮尺、一定範囲の地図に、案内経路と端末装置２０の現在位置を示すマークを重ね合わせて現在位置マークが表示画面の中心になるように表示する。

ＧＰＳ受信手段２３によりＧＰＳ衛星信号を受信して測位した現在位置情報（緯度・経度の情報）には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理や地図上の道路にマッチングするマップマッチング処理が行われる。また、経路探索サーバ３０から配信される案内経路データに音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力してユーザをガイドする。

本発明に基づく迂回経路探索の要求を経路探索サーバ３０に送信する場合には、後述する経路探索条件の入力メニュー画面を表示手段２４に表示し、迂回経路探索を選択して経路探索条件を設定する。迂回経路探索においては、目的地到着時刻と余裕度（出発地における出発時刻にどの程度の余裕を見込むか）が必須の設定項目となる。

一方、経路探索サーバ３０は、制御手段３１、案内データ編集手段３２、通信手段３３、経路探索手段３４、候補経路グルーピング手段３５、迂回経路探索手段３６、地図データ３７、道路ネットワークデータ３８、交通ネットワークデータ３９を備えて構成されている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御するものである。

通信手段３３はネットワーク１２を介して端末装置２０などと通信データを送受信するための通信インターフェースである。案内データ編集手段３２は、経路探索手段３３や迂回経路探索手段３６が探索した案内経路のデータや表示用の地図データ、ガイダンスデータを編集して端末装置２０に配信する。

経路探索手段３４は、端末装置２０から送信された経路探索条件に従って、道路ネットワークデータ３８、交通ネットワークデータ３９を参照して、経路探索条件で指定された出発地から目的地までの最適経路や候補経路を探索して端末装置２０に経路データを送信する。最適経路とは、出発地から目的地までの経路コスト（距離や所要時間）が最小になる経路であり、候補経路とは、最適経路を含む複数の経路を経路コスト順に所定数案内する経路である。

経路探索条件には、出発地を出発する日時や時刻を設定したり、目的地に到着する日時や時刻を設定したりすることができ、また、交通機関を用いた経路を含む経路探索を要求する場合には、航空機の利用有無、有料特急電車の利用有無あるいはグリーン車の利用有無、新幹線の利用有無など、移動手段を制約する条件を設定することもできる。

候補経路グルーピング手段３５、迂回経路探索手段３６は、端末装置２０から迂回経路の探索要求があった場合、後述する手順で迂回経路を探索し、出発地を最も早い時刻に出発する推奨経路を優先案内経路とし、その後の時刻に出発する経路を迂回経路として出力する。

次に、以上説明した本発明の実施例にかかる経路探索システム１０における迂回経路の探索について説明する。迂回経路の探索に先立って、端末装置２０において迂回経路の探索条件を設定する。図３は、経路探索条件を設定するための条件設定画面の構成を示す図である。

条件設定画面３０１には、図３に示すように、出発地入力欄３０２、目的地入力欄３０３、時刻条件入力欄３０４、迂回経路探索設定欄３０６、余裕度設定欄３０７、探索開始ボタン３０８が設けられている。経路探索サーバ３０に迂回経路探索を要求する場合には、迂回経路探索設定欄３０６の「する」のチェックボックスに参照符号３０５に示すチェックを入れる。迂回経路探索設定欄３０６の「しない」のチェックボックスにチェックを入れた場合は、通常の経路探索に要求となる。

出発地と目的地の設定は、出発地入力欄３０２、目的地入力欄３０３に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。また、プルダウンボタンを操作して、これまでに端末装置２０に登録した経路探索履歴や登録地点を呼び出して設定することもできる。

時刻条件入力欄３０４には出発日時や目的地到着日時などの時刻条件を入力する。迂回経路探索を指定した場合には、時刻条件入力欄３０４に目的地到着時刻を設定することが必須になる。この入力がなされない場合にはエラーが表示される。また、迂回経路探索が設定された場合には、余裕度設定欄３０７の表示から、所望の余裕度を設定することが必須になる。この設定がない場合にはエラーが表示される。必要な条件設定を終え、探索開始ボタン３０８を操作すると、迂回経路の探索要求が端末装置２０から経路探索サーバ３０に送信される。

余裕度とは、途中で何らかの障害があっても設定した到着時刻に目的地到着するためにどの程度の余裕を見込むかを設定するものである。例えば、到着すべき日の前日に目的地に到着していれば最も安心である。公共交通機関を利用する経路を対象とした場合でも同様であり、本発明においては、到着時刻を指定した通常の経路探索を行って得た候補経路（到着時刻条件を満足する複数の候補経路）のうち、出発地を出発する時刻をどの程度まで早く出発するかを設定する。本実施例においては、候補経路の出発時刻を時刻順にソートして何番目までの候補経路を余裕度として見込むかを設定する。この詳細については後に詳しく具体例で説明する。

本発明の実施例にかかる迂回経路探索の説明の前に、ナビゲーションシステム１０における通常の経路探索について説明する。ビゲーションシステム１０における経路探索のための道路ネットワークデータ３８は以下のように構成されている。例えば、道路が図４に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。

すなわち、図４において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。

このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図４において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。

図４ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。

これに対して、交通機関の経路探索のための交通ネットワークデータ３９は以下のように構成されている。例えば、図５に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図５において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図５では図示を簡略化するため矢印の向きのリンクのみを図示している。

しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図５に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。

図５に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。

このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図５において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。

次に、本発明の実施例にかかる迂回経路の探索手順について説明する。以下の説明において、迂回経路の探索条件は、出発地の最寄り駅（出発駅）がＡ駅、目的地の最寄り駅（目的駅）がＦ駅であり目的地駅（Ｆ駅）に到着すべき時刻が指定されているものとする。先ず、経路探索手段３４は、通常の目的地到着時刻指定の経路探索を行って、複数の候補経路を探索する。この経路探索においては、Ａ駅を出発してＦ駅に指定時刻に到着することが可能な全ての候補経路が探索される。理論上は多数の候補経路が探索されるが、出発駅であるＡ駅を経路探索の当日に出発する経路、あるいは、３０位までの候補経路を次の処理対象の候補経路とするなどの方法を採り、現実的な迂回経路探索をするようにできる。

次に、候補経路グルーピング手段３５は経路探索手段３４が探索した候補経路をグルーピングする。グルーピングの基準は、Ａ駅を出発する出発方向が同じ経路をグループとするものである。また、候補経路に乗り換え駅がある場合は、乗り換え駅から同じ方向に出発する経路をグループとする。迂回経路となり得る経路は出発駅や乗り換え駅から同じ方向に出発する経路であることが条件になるからこのような基準で候補経路をグルーピングする。なぜならば、同じ方向出発する経路でなければ、ある経路を出発した後、何らかの障害で他の経路に移る場合に移ることが不可能であるからである。

図６、図７は、経路探索手段３４が探索したＡ駅からＦ駅に至る複数の候補経路をグルーピングした例を示す模式図である。図６では、Ａ駅を出発してＢ駅に向かう出発方向が同じ候補経路ＲＴ１および候補経路ＲＴ３がグルーピングされ、図７では、Ａ駅を出発してＤ駅に向かう出発方向が同じ候補経路ＲＴ２および候補経路ＲＴ４がグルーピングされる。例えば、候補経路ＲＴ１でＡ駅を出発した後、Ｂ駅に到着するまでの間にＢ駅とＣ駅間の運行が不通になったことがわかれば、Ｂ駅で迂回経路となる候補経路ＲＴ３に移ることができる。

同様に、図７において、候補経路ＲＴ２でＡ駅を出発した後、Ｅ駅に到着するまでの間にＥ駅とＦ駅間の運行が不通になったことがわかれば、Ｄ駅またはＥ駅で迂回経路となる候補経路ＲＴ４に移ることができる。各候補経路ＲＴ１〜ＲＴ４は目的の駅Ｆに指定時刻に到着できる経路であるからこのような乗り換えをしてもＦ駅に指定時刻に到着することができる。また、このような乗り換えを可能にするためには、推奨する経路はＡ駅を出発する候補経路のうち、出発時刻が最も早い経路である必要がある。

すなわち、図６においては、候補経路ＲＴ１がＡ駅を出発する出発時刻が、候補経路ＲＴ３がＡ駅を出発する出発時刻がよりも早い必要がある。そうでなければ、候補経路ＲＴ１でＡ駅を出発した後、Ｂ駅に到着するまでの間にＢ駅とＣ駅間の運行が不通になったことがわかっても、Ｂ駅で迂回経路となる候補経路ＲＴ３に移ることができない。このように候補経路の出発時刻の時間関係を考慮して、推奨経路と迂回経路を区別して案内する必要がある。図７の場合も同様である。

すなわち、図６において、候補経路ＲＴ１がＡ駅を出発する出発時刻が、候補経路ＲＴ３がＡ駅を出発する出発時刻よりも早い場合は、候補経路ＲＴ１が推奨経路であり、候補経路ＲＴ３が迂回経路である。逆に、候補経路ＲＴ１がＡ駅を出発する出発時刻が、候補経路ＲＴ３がＡ駅を出発する出発時刻よりも遅い場合は、候補経路ＲＴ３が推奨経路であり、候補経路ＲＴ１が迂回経路である。従って、推奨経路が一般的なナビゲーションシステムにおける最適経路でないこともある。推奨経路は、Ａ駅を最も早く出発する経路であってＦ駅まで遠回りの経路であるが、他の候補経路に乗り換える選択肢の多い候補経路になる確率が高い。図７のようにグルーピングされた候補経路についても同様である。

本実施例においては、候補経路グルーピング手段３５がグルーピングした図６、図７の候補経路グループ毎に、迂回経路探索手段３６が次の手順によって推奨経路と迂回経路を区別する。すなわち、迂回経路探索手段３６は、グループ候補経路のうち、所定のＫ番目の候補経路の出発時刻を用いて候補経路グループ内の各候補経路を再度交通ネットワークデータを参照して経路探索を行って、（１）最も出発駅における出発時刻の早い候補経路を推奨経路として優先的に出力する経路とし、（２）出発時刻の遅い経路を迂回経路として出力する。

ここで、所定のＫ番目の候補経路の「Ｋ」は迂回経路探索の条件で設定した余裕度に基づいて決定される。すなわち、余裕度とは目的駅に指定の時刻に到着するためにどれだけ出発時刻に余裕を持たせるかを設定するものであり、時間単位で指定することもできるが、本実施例においては、図３に示す経路探索条件設定画面の余裕度３０７の数値を選択するようにしている。この数値は、迂回グルーピングされた候補経路グループに含まれる候補経路のうち出発時刻の最も遅い出発時刻を持つ経路から順に、出発時刻の早い候補経路の何番目までを迂回経路、推奨経路の対象とするかを意味するものである。

図６や図７ではそれぞれ２つの候補経路がグルーピングされたが、実際には候補経路は多数存在し、出発地時刻が最も遅い候補経路（最適経路）から順に、出発時刻の早い候補経路をいくつ遡って迂回経路を得たいか、すなわち、迂回経路をどれだけ用意するかという観点から決定する。通常は、Ｋを「３」程度とするが、出発地と目的地の距離が遠い場合はＫの値を増やすなどしても良い。

次に、迂回経路探索手段３６は、グルーピングされた候補経路の中で、Ｋ番目、すなわち、最適経路としての順位がＫ番目であって、そのグループの候補経路では出発時刻が遅い方からＫ番目の経路を着目経路とする。そして、この着目経路の出発時刻を参照して、その出発時刻から同一目的地に対して、同一出発方向に限定して、再度経路探索を行う。この迂回経路探索は、出発時刻基準を基準とした経路探索であり、Ｋ番目の候補経路の出発時刻以降で、最初の経路探索条件である当初の到着時刻条件を満たす経路を再探索するものである。迂回経路の探索結果として得られる各経路を、出発時刻の早い順にソートする。

ソートした結果、前述したように、出発駅を出発する時刻が最も早い経路を推奨経路とし、それ以降の出発時刻を有する経路を迂回経路とする。すなわち、図６において、候補経路ＲＴ１がＡ駅を出発する出発時刻が、候補経路ＲＴ３がＡ駅を出発する出発時刻よりも早い場合は、候補経路ＲＴ１が推奨経路であり、候補経路ＲＴ３が迂回経路である。候補経路がＲＴ１、ＲＴ３以外にもある場合も同様であり、最も早く出発駅を出発する候補経路が推奨経路であり、その他の候補経路が迂回経路になる。

迂回経路探索手段３６は、候補経路グルーピング手段３５がグルーピングした他のグループ候補経路についても同様の迂回経路探索を行い、図７に示す候補経路において、候補経路ＲＴ２がＡ駅を出発する出発時刻が、候補経路ＲＴ４がＡ駅を出発する出発時刻よりも早い場合は、候補経路ＲＴ２が推奨経路であり、候補経路ＲＴ４が迂回経路になる。

なお、図６において、候補経路ＲＴ３の出発時刻を基準に迂回経路の再探索を行った際に特に他の候補経路（運行ダイヤ）が見つからなければ、候補経路ＲＴ３、ＲＴ１が経路として残り、この場合、出発時刻が早い候補経路ＲＴ３であればこの経路が推奨経路になり、Ｂ駅からは候補経路ＲＴ１が迂回経路として出力される。

この組み合わせが有効なのは、迂回経路ＲＴ１で出発してＢ駅→Ｃ駅→Ｆ駅が障害で不通になることに先駆け、推奨経路ＲＴ３でＦ駅に到着するというシナリオである。もし、推奨経路ＲＴ３のＢ駅→Ｅ駅→Ｆ駅間に障害があることがわかれば、Ｂ駅で迂回経路ＲＴ１に切り替えることができる。両方の経路が不通になることは確率的により低いので、結果的に障害に強いプランになる。

また、図７においても同様であり、この候補経路グループでは候補経路ＲＴ２が通常の最適経路であるが、候補経路ＲＴ４も存在する。候補経路ＲＴ４は通常は選択されない経路であるが、それでも同じ路線を２回以上通らないので、経路探索上はありえる経路である。この候補経路グループでも、候補経路ＲＴ４を推奨経路として出発しておき、Ｅ駅→Ｆ駅間に障害が発生したとしても、Ｅ駅→Ｂ駅→Ｃ駅→Ｆ駅と迂回する余裕がまだ残っている。（Ｅ駅→Ｆ駅間が障害なく順調であれば、Ｄ駅→Ｅ駅→Ｆ駅と直行できる電車であれば、それがわかるように表示すると迂回判断時の判断材料になり好適である）

このように、本発明にかかる迂回経路探索によれば、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路が案内できるので、利用者は設定した余裕度に応じて案内された推奨経路に従って移動中に、何らかの障害が発生しても、案内された迂回経路に乗り換えて、所定の時刻までに目的地に到着できるようになる。

また、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、予め設定されたＫ番目の候補経路の出発時刻を用いて、出発地の出発時刻を基準とした経路であって目的地への到着時刻を満足する経路が探索されるので、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路を案内することができるようになる。

更に、出発駅や乗り換え駅において出発方向が同じ経路グループごとに、予め設定されたＫ番目の候補経路の出発時刻を用いて、出発地の出発時刻を基準とした経路であって目的地への到着時刻を満足する経路を探索する際、交通機関に関する制限条件を緩和して経路探索すれば、探索される迂回経路の範囲を広げることができる。従って、最も早く出発駅を出発する推奨経路と、その後に出発駅を出発する迂回経路が案内できるので、利用者は設定した余裕度に応じて案内された推奨経路に従って移動中に、何らかの障害が発生しても、所定の時刻までに目的地に到着できる迂回経路の選択肢を拡大することができるようになる。

これらの迂回経路探索の結果は、図８に示すような表示画面のように出力される。表示画面４０１には、迂回経路探索表示欄４０２に「ＯＮ」の表示があり、経路表示欄４０３に、出発方向別（グルーピングされた候補経路別）に、推奨経路と迂回経路１、迂回経路２のように経路案内が表示される。メッセージ欄４０４には、地図表示や迂回経路乗り換え案内に関するコメントが表示され、地図を表示したり、迂回経路を利用する状況が起こった場合の乗り換え案内を受けたりすることができる。

次に、本発明の実施例にかかる迂回経路探索の手順について、図９に示すフローチャートを参照して説明する。先ず、ステップＳ１０１の処理において経路探索サーバ３０は端末装置２０から、図３に示す入力画面を用いて設定された経路探索条件に基づく経路探索要求を受信する。経路探索サーバ３０は経路探索要求を受信すると、ステップＳ１０２の処理において迂回経路探索の要求であるか否かを判定する。

ステップＳ１０２の判定処理において、経路探索要求が迂回経路探索でなく通常の経路探索要求である場合はステップＳ１０７の処理に進み、通常の経路探索を実行して処理を終了する。経路探索要求が迂回経路探索の要求である場合にはステップＳ１０３の処理に進む。迂回経路探索の条件としては、まず、目的地への到着時刻指定の探索であることが必要で、次に交通機関を探索条件に含んでいることがチェックされる。自動車経路探索のみである場合は、本発明にはなじまないので、通常の経路探索へ処理を移す。

ステップ１０３の処理においては、経路探索手段は目的地への到着時刻指定の通常の経路探索を行う。この経路探索においては、最適経路探索のみでなく複数の候補経路を探索する。通常は第３経路〜第５経路まで求めることが一般的であるが、本発明はできるだけ多くの候補経路を求めることにする。経路探索方法は、例えば、上記特許文献２に示された方法で行うことができ、また、到着時刻指定の経路探索は、到着側から逆に経路探索を行うことで経路を得ることができる。

次に、ステップＳ１０４の処理において、候補経路グルーピング手段３５は、ステップＳ１０３で探索された候補経路をグルーピングする。グルーピングする候補経路は、出発方向が同じ候補経路をグループにまとめるものである。ここで、出発方向が同じという意味は、狭義には、出発駅からの最初の利用路線が同じということであるが、広義には、出発地から最初の利用駅が同じ経路とすることができる。特に、上記特許文献２に示された経路探索のシステムでは、周囲の複数の駅が出発駅になりうるので、まず駅ごとにグルーピングするということでも良い。

次に、グルーピングされた候補経路ごとに、迂回経路探索手段はステップＳ１０５の処理において、余裕度に応じた着目候補経路を選択して以下の経路探索を行う。前述したように、着目する候補経路は、１つの候補経路グループの中で、第Ｋ番目の候補経路である。第Ｋ番目の経路は、最適経路としての順位がＫ番目であって、そのグループでは出発時刻が遅い方からＫ番目の候補経路である。

そして、この着目経路の出発時刻を参照して、その出発時刻から同一目的地に対して、同一出発方向に限定して、再度経路探索を行う。この迂回経路探索は、出発時刻基準を基準とした経路探索であり、Ｋ番目の候補経路の出発時刻以降で、最初の経路探索条件である当初の到着時刻条件を満たす経路を再探索するものである。

次に、迂回経路探索手段３６は、上記のようにして再探索した経路をステップＳ１０６の処理において出発時刻の早い順にソートして推奨経路と迂回経路を出力する。出発時刻順にソートされた経路については、前述したように、出発駅を出発する時刻が最も早い経路を推奨経路とし、それ以降の出発時刻を有する経路を迂回経路として出力し、処理を終了する。例えば、図６において、候補経路ＲＴ１がＡ駅を出発する出発時刻が、候補経路ＲＴ３がＡ駅を出発する出発時刻よりも早い場合は、候補経路ＲＴ１が推奨経路であり、候補経路ＲＴ３が迂回経路である。

このようにして求めた候補経路グループ内の経路のうち、推奨経路（最適経路）は、それ以降出発する経路に迂回可能な経路であるから、グループ内の最適経路を迂回まで考慮した経路として出力し、迂回経路として分岐する地点に表示を付けておくと良い。また、経路データにハイパーリンクを付加しておき、リンク操作により迂回経路を参照できるようにして表示するようにしても良い。

なお、ステップＳ１０５の迂回経路探索において、候補経路グループの経路再探索をする場合は、交通機関の利用制限を緩和するようなオプションを付けても良い。例えば、通常は「有料特急を使用しない」という設定が有効であるとしても、グルーピングされた候補経路グループごとの再探索ではその設定を無効として、挽回可能な経路の可能性を多く提供するようにしても良い。

また、候補経路のグルーピングにおいては、最初の出発方向ごとにグループを分けたが、途中の乗換えポイント以降を同じルールで探索するようにして、可能性のある経路をさらに細分化し、抽出した経路の最も出発時刻の早い時刻から、再探索を行って、分岐可能な迂回経路のグループを形成するようにしても良い。

本発明にかかる迂回経路探索は、目的地に到着する時刻に対して遅刻しない完全な解（経路案内）を与えることができるものではないが、案内した推奨経路に障害があってもその影響をリカバーできる迂回経路を予め計画的に探索しておくことができるものとして、携帯ナビゲーションシステムや、ＰＣサイトの乗換え案内のサービス等で提供することが可能である。

本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。 本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。 迂回経路探索の条件を設定する条件設定画面の一例を示す図である。 道路ネットワークのデータの概念を示す模式図である。 交通ネットワークのデータの概念を示す模式図である。 迂回経路探索の手順の概念を説明するためのグルーピングされた候補経路の例を示す模式図である。 迂回経路探索の手順の概念を説明するためのグルーピングされた他の候補経路の例を示す模式図である。 迂回経路探索の結果を案内する表示画面の一例を示す図である。 迂回経路探索における経路探索サーバ３０の動作手順を示すフローチャートである。

符号の説明

１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・ＧＰＳ受信手段
２４・・・・表示手段
２５・・・・案内記憶手段
２６・・・・設定条件記憶手段
２７・・・・操作入力手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・案内データ編集手段
３３・・・・通信手段
３４・・・・経路探索手段
３５・・・・候補経路グルーピング手段
３６・・・・迂回経路探索手段
３７・・・・地図データ
３８・・・・道路ネットワークデータ
３９・・・・交通ネットワークデータ

Claims (11)

1. 経路探索用のネットワークデータを参照して出発地から目的地まで、交通機関を利用した経路を含む案内経路を探索する経路探索手段と、前記経路探索手段が探索した案内経路データを記憶する案内経路記憶手段と、前記案内経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
   前記ナビゲーションシステムは、設定された出発地を出発して設定された時刻に設定された目的地に到着できる複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
   前記候補経路グルーピング手段は、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段は、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とするナビゲーションシステム。
2. 前記迂回経路探索手段は、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索し、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする請求項１に記載のナビゲーションシステム。
3. 前記迂回経路探索手段は、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行うことを特徴とする請求項２に記載のナビゲーションシステム。
4. 所望の出発地と目的地を設定する端末装置とネットワークを介して接続され、前記端末装置からの要求に基づき、設定された２地点間の複数の候補経路を探索する経路探索サーバにおいて、
   前記経路探索サーバは、経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
   前記候補経路グルーピング手段は、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段は、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする経路探索サーバ。
5. 前記迂回経路探索手段は、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索し、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする請求項４に記載の経路探索サーバ。
6. 前記迂回経路探索手段は、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行うことを特徴とする請求項５に記載の経路探索サーバ。
7. 所望の出発地と目的地を設定する端末装置とネットワークを介して接続され、前記端末装置からの要求に基づき、設定された２地点間の複数の候補経路を探索する経路探索サーバにおける経路探索方法において、
   前記経路探索サーバは、経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
   前記候補経路グルーピング手段が、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングするステップと、前記迂回経路探索手段が、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力するステップを有することを特徴とする経路探索方法。
8. 前記迂回経路探索ステップは、前記候補経路グループについて、最も出発時刻の遅い候補経路から順に遡った場合に、設定された余裕度Ｋに基づいてＫ番目の候補経路を決定し、前記決定されたＫ番目の候補経路の出発時刻と前記目的地および目的地への到着時刻を条件として再度前記ネットワークデータに基づき複数の経路を探索する処理を含み、該探索された複数の経路の中で最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力することを特徴とする請求項７に記載の経路探索方法。
9. 前記迂回経路探索ステップは、前記候補経路グループについて、前記Ｋ番目の候補経路の出発時刻を用いて前記各候補経路を再度前記ネットワークデータに基づき探索する際、利用する交通機関に関して前記出発地と目的地および目的地への到着時刻とともに設定された利用する交通機関に関する制限条件を緩和して経路探索を行う処理を含むことを特徴とする請求項８に記載の経路探索方法。
10. 経路探索用のネットワークデータを参照し、設定された出発地を出発して設定された時刻に設定された目的地に到着できる交通機関を利用した経路を含む複数の候補経路を探索する経路探索手段と、候補経路グルーピング手段と、迂回経路探索手段と、を備え、
    前記候補経路グルーピング手段が、出発地点あるいは乗り換え地点からの出発方向が同じ候補経路をグルーピングし、前記迂回経路探索手段が、候補経路グループについて、最も出発時刻の早い候補経路を推奨経路とし、他の候補経路を迂回経路として出力する経路探索サーバにネットワークを介して接続される端末装置であって、
    前記端末装置は、少なくとも迂回経路の探索と、出発地と、目的地と、目的地に到着すべき時刻と、を経路探索条件として設定する操作入力手段を備えたことを特徴とする端末装置。
11. 前記端末装置は、表示手段を備え、前記推奨経路を示す情報と迂回経路を示す情報とを候補経路グループごとに前記表示手段に表示することを特徴とする請求項１０に記載の端末装置。

Images