(57)【要約】【課題】ユーザが経路探索時に入力した時刻通りに移動を開始できなかった場合に、意味を失った経路の情報を削除し、有意な経路の情報をリアルタイムに表示する。【解決手段】指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段３３を有する経路探索サーバ３０と、前記候補経路を表示する表示手段２５を有する端末装置２０と、を備えたナビゲーションシステム１０において、ナビゲーションシステム１０は、前記経路探索手段３３が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する経路失効時刻設定手段３５を備え、端末装置２０は前記候補経路を前記表示手段２５に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示する。【選択図】図２
2010054390.tif 000002
【特許請求の範囲】
【請求項１】
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記端末装置は前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とするナビゲーションシステム。
【請求項２】
前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする請求項２に記載のナビゲーションシステム。
【請求項４】
前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする請求項３に記載のナビゲーションシステム。
【請求項５】
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムを構成する経路探索サーバにおいて、
前記経路探索サーバは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記端末装置は前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とする経路探索サーバ。
【請求項６】
前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする請求項５に記載の経路探索サーバ。
【請求項７】
前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムにおける経路表示方法において、
前記ナビゲーションシステムは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記経路探索手段が、前記端末装置によって指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索するステップと、
前記失効時刻設定手段が、前記候補経路の失効時刻を設定するステップと、
前記端末装置が、前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別するステップと、無効となった候補経路を削除して表示するステップと、を有することを特徴とする経路表示方法。
【請求項１０】
前記失効時刻を設定するステップは、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて、前記失効時刻を設定する処理を含むことを特徴とする請求項９に記載の経路表示方法。
【請求項１１】
前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、前記失効時刻を設定するステップは、該失効時刻設定手段が、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定する処理を含むことを特徴とする請求項１０に記載の経路表示方法。
【請求項１２】
前記失効時刻を設定するステップは、前記失効時刻設定手段が、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とする処理を含むことを特徴とする請求項１１に記載の経路表示方法。
【請求項１３】
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムを構成する端末装置において、
前記端末装置は、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定判別手段を備え、
前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とする端末装置。
【請求項１４】
前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする請求項１３に記載の端末装置。
【請求項１５】
前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする請求項１４に記載の端末装置。
【請求項１６】
前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする請求項１５に記載の端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、徒歩や自動車あるいは公共交通機関を利用して、任意の出発地から目的地に至る候補経路を探索して案内するナビゲーションシステムに関するものであり、特に、公共交通機関を利用した経路区間を含む複数の候補経路を端末装置に表示する際に、各候補経路が経路としての意味を失う失効時刻を対応付けておき、失効時刻を経過した候補経路を順次削除して、有意な候補経路のみをリアルタイムに表示するようにしたナビゲーションシステムに関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、徒歩経路や自動車による移動経路を探索するための道路ネットワークデータに加え、各交通機関の運行時刻データをデータベース化した運行時刻データベースとこれに基づいて交通ネットワークをデータベース化した交通ネットワークデータを備えている。経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
公共交通機関を用いた経路区間を含む経路探索を行うシステムは種々提案されており、例えば、公共交通機関の時刻表を表示するようにしたナビゲーション装置の発明が、下記の特許文献２（特開２００５−２４２７９号公報）に開示されている。このナビゲーション装置は、各種交通機関の乗降施設の時刻表に関する情報が記憶されたハードディスクドライブと、各種交通機関の乗降施設が地点として指定された場合、ハードディスクドライブに記憶された時刻表に関する情報に基づき、地点として指定された乗降施設の時刻表を示す情報を出力する制御回路と、制御回路から出力された時刻表を示す情報に応じて、時刻表を表示画面に表示する表示装置を備えて構成されている。
【００１０】
すなわち、この特許文献２に開示されたナビゲーション装置は、指定された地点が交通機関の乗降駅であった場合には、その駅の時刻表を表示することによって、乗車可能な時間帯の列車を容易に確認できるようにしたものである。
【００１１】
また、下記の特許文献３（特開２００７−２１６６９６号公報）には、現在時刻と現在位置の情報から最寄り駅までの到達時間を考慮し、最寄り駅への予定到着時刻を用いて目的地までの経路の検索を行うようにした鉄道乗換情報検索システムが開示されている。この鉄道乗換情報検索システムは、携帯電話機からの要求で交通情報に関する目的地検索を行う鉄道乗換情報検索システムである。
【００１２】
すなわち、このシステムにおいて、携帯電話機は、入力された目的地情報を保持する目的地取得手段と、ＧＰＳ情報を受信するＧＰＳ受信手段と、前記受信したＧＰＳ情報に基づき現在位置を取得する現在位置取得手段と、前記取得した現在位置を用いて最寄り駅を検索する最寄駅検索手段と、現在の時刻を取得する現在時刻取得手段と、前記取得した現在位置と、前記検索した最寄り駅と、前記取得した現在の時刻から最寄り駅へ到着する予定到着時刻を算出する最寄駅到着時刻算出手段と、前記ネットワークを介して交通情報管理サーバにアクセスし、前記算出された最寄り駅への予定到着時刻で、前記入力された目的地までの経路を検索する目的地検索手段と、を備えて構成されたものである。
【００１３】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特開２００５−２４２７９号公報
【特許文献３】特開２００７−２１６６９６号公報号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
先に述べたように、通常のナビゲーションシステムでは、ユーザが現在地から目的地まで経路探索を要求すると、現在時刻または時刻条件、その他登録された探索条件に基づいて最適経路や最適経路を含む複数の候補経路を提示する。例えば、ユーザが所有する携帯端末装置において、出発地、目的地、到着希望時刻等の経路探索条件を経路探索サーバに送信すると、経路探索サーバは最適経路を算出し経路案内情報を携帯端末装置へ送信する。携帯端末装置は、経路探索サーバから受信した最適経路や所望の候補経路に基づいて経路案内を受けることができる。
【００１５】
経路が交通機関を利用する経路区間を含む場合に、上記特許文献１に開示された技術によれば、出発地点や乗換え地点の乗降施設について、時刻表を表示することができ、ユーザは、乗降可能な時間帯の列車を知ることができる。また上記特許文献２に開示されている技術によれば、現在地から最寄り駅を算出し、現在地から最寄り駅までの所要時間を考慮して、交通機関を用いた経路区間を含む経路の探索を行うことができる。
【００１６】
しかしながら、ユーザが経路探索時に入力した時刻通りに移動を開始できるとは限らない。例えば、外出の支度に予想外に時間がかかったり、あるいは、出発間際に来客があったり、急用ができたりして予定の時間に出発できない場合がある。
【００１７】
上記特許文献２や特許文献３において、サーバから受信する経路情報等は、経路探索時に指定された出発時刻に基づいて探索されたものであるから、端末装置に表示された経路の情報も当然に指定された出発時刻に応じたものになる。従って、前述のようにユーザが予定した時刻に出発できなければ、端末装置に表示された経路の時刻情報に従って移動できないことになる。このような場合には、実際に移動を開始する現在時刻において、再度経路探索の要求を行って、新たな経路情報を取得し、利用する交通機関の乗り換え情報について確認しなければならないという問題点があった。
【００１８】
また、端末装置に複数の候補経路の情報が表示される場合、出発時間が遅れた場合にどの候補経路が、実際には移動不可能になった経路であるか、どの経路がまだ利用可能な経路であるかは、表示された経路の情報をユーザが詳細に把握して判断しなければならず、ユーザが簡単には認識できないという問題点があった。
【００１９】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、公共交通機関を利用した経路区間を含む複数の候補経路を端末装置に表示する際に、各候補経路が経路としての意味を失う失効時刻を対応付けておき、失効時刻を経過した候補経路を順次削除して、有意な候補経路のみをリアルタイムに表示するようになせば、上記問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００２０】
すなわち、本発明は、上記の問題点を解消することを課題とし、ユーザが経路探索時に入力した時刻通りに移動を開始できなかった場合に、意味を失った経路の情報を削除し、有意な経路の情報をリアルタイムに表示できるナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２１】
前記課題を解決するために、本願の請求項１にかかる発明は、
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記端末装置は前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とする。
【００２２】
また、本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする。
【００２３】
また、本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする。
【００２４】
また、本願の請求項４にかかる発明は、請求項３にかかるナビゲーションシステムにおいて、前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする。
【００２５】
また、本願の請求項５にかかる発明は、
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムを構成する経路探索サーバにおいて、
前記経路探索サーバは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記端末装置は前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とする。
【００２６】
また、本願の請求項６にかかる発明は、請求項５にかかる経路探索サーバにおいて、前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする。
【００２７】
また、本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする。
【００２８】
また、本願の請求項８にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする。
【００２９】
また、本願の請求項９にかかる発明は、
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムにおける経路表示方法において、
前記ナビゲーションシステムは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記経路探索手段が、前記端末装置によって指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索するステップと、
前記失効時刻設定手段が、前記候補経路の失効時刻を設定するステップと、
前記端末装置が、前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別するステップと、無効となった候補経路を削除して表示するステップと、を有することを特徴とする。
【００３０】
また、本願の請求項１０にかかる発明は、請求項９にかかる経路探索方法において、前記失効時刻を設定するステップは、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて、前記失効時刻を設定する処理を含むことを特徴とする。
【００３１】
また、本願の請求項１１にかかる発明は、請求項１０にかかる経路探索方法において、前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、前記失効時刻を設定するステップは、該失効時刻設定手段が、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定する処理を含むことを特徴とする。
【００３２】
また、本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記失効時刻を設定するステップは、前記失効時刻設定手段が、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とする処理を含むことを特徴とする。
【００３３】
また、本願の請求項１３にかかる発明は、
指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムを構成する端末装置において、
前記端末装置は、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定判別手段を備え、
前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示することを特徴とする。
【００３４】
また、本願の請求項１４にかかる発明は、請求項１３にかかる端末装置において、前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定されることを特徴とする。
【００３５】
また、本願の請求項１５にかかる発明は、請求項１４にかかる端末装置において、前記失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定することを特徴とする。
【００３６】
また、本願の請求項１６にかかる発明は、請求項１５にかかる端末装置において、前記失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とすることを特徴とする。
【発明の効果】
【００３７】
請求項１にかかる発明においては、指定された時刻条件および出発地と目的地とを含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した区間を含む候補経路を探索する経路探索手段を有する経路探索サーバと、前記候補経路を表示する表示手段を有する端末装置と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、前記経路探索手段が探索した候補経路について、当該候補経路が無効となる時刻を経路失効時刻として設定する失効時刻設定手段を備え、
前記端末装置は前記候補経路を前記表示手段に表示する際、現在時刻に基づいて、前記候補経路の失効時刻を判別し、無効となった候補経路を削除して表示する。
【００３８】
かかる構成によれば、公共交通機関を利用した経路区間を含む複数の候補経路を端末装置に表示する際に、各候補経路が経路としての意味を失う失効時刻を対応付けておき、失効時刻を経過した候補経路を順次削除して、有意な候補経路のみをリアルタイムに表示するものであるから、ユーザが経路探索時に入力した時刻通りに移動を開始できなかった場合に、有意な経路の情報を容易にしることができるようになり、また、表示される候補経路の数が減った場合に経路探索サーバにおいて、追加の候補経路を探索してユーザに提供することができるようになる。
【００３９】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記失効時刻は、各候補経路において、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻に基づいて設定される。
かかる構成によれば、経路探索手段により探索された候補経路について、最初に交通機関を利用する地点までの徒歩経路区間の出発地点における出発時刻をもとに、経路が意味をなさなくなる失効時間を設定することができるようになる。
【００４０】
請求項３にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、失効時刻設定手段には、候補経路の最大遅延許容時間を算出するための最大遅延許容係数を設定可能であり、該失効時刻設定手段は、前記徒歩経路区間の所要時間に前記最大遅延許容係数を積算して最大遅延許容時間を算出し、前記失効時刻を設定する。
かかる構成によれば、端末装置のユーザの歩行速度に応じて、候補経路の失効時刻を設定することができるようになる。
【００４１】
請求項４にかかる発明においては、請求項３にかかるナビゲーションシステムにおいて、失効時刻設定手段は、前記徒歩経路区間における交差点の数に基づいて、前記交差点における平均待ち時間を用いて、該徒歩経路区間の待ち時間を算出し、前記最大遅延許容時間から、前記待ち時間を差し引いて最大遅延許容時間とする。
かかる構成によれば、端末装置のユーザの歩行速度に応じて、候補経路の失効時刻を設定する際に、ユーザが歩行速度によって調整できない時間要素を除いて経路の失効時刻を設定することができるようになる。
【００４２】
請求項５〜請求項８にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項９〜請求項９〜請求項１２にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムにおける経路表示方法を提供することができるようになる。また、請求項１３〜請求項１６にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００４３】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００４４】
図１は、本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。本発明の実施例にかかるナビゲーションシステム１０は、図１に示すように、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。経路探索サーバ３０は、経路探索のための道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを交通ネットワークデータとして蓄積したデータベース（ＤＢ２）、交通機関の各電車等の運行ダイヤに基づく時刻表や運賃を蓄積した時刻表・運賃データのデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。時刻表・運賃データは、ネットワークを介して情報配信サーバ５０から取得することができる。
【００４５】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、ＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器であってもよい。
【００４６】
図２は、図１に示すナビゲーションシステム１０の詳細な構成を示すブロック図である。本発明の実施例１にかかるナビゲーションシステム１０は、図２のブロック図に示すようにインターネットなどのネットワーク１２を介して通信する端末装置２０と、経路探索サーバ３０と、情報配信サーバ５０を備えて構成されている。
【００４７】
端末装置２０は、経路探索サーバ３０に出発地と目的地などの経路探索条件を設定して経路探索要求を送信し、経路探索サーバ３０は、経路探索条件に従って、道路ネットワークデータ３６、交通ネットワークデータ３７を参照して最適経路あるいは最適経路を含む所定数の候補経路を探索し、最適経路または複数の候補経路の情報を案内経路データに編集して端末装置２０に配信する。
【００４８】
図２に示すように、端末装置２０は、制御手段２１、通信手段２２、位置検出手段２３、経路探索サーバ３０から受信した案内経路のデータを記憶する経路記憶手段２４、表示手段２５、表示制御手段２６、経路探索サーバから受信した地図データなどのダウンロードデータを一時記憶する一時記憶手段２７、失効時刻判別手段２８、操作入力手段２９などを備えて構成されている。失効時刻判別手段２８は、現在時刻をもとに経路探索サーバ３０から受信する候補経路の各々に付加されている失効時刻を過ぎたか否かを判別するものである。
【００４９】
経路の失効時刻とは、ユーザが経路の時刻条件、例えば、出発地の最寄り駅における乗車すべき電車（経路として探索された電車）の出発時刻を過ぎてしまい、その経路の情報に意味がなくなる時刻、すなわち、経路としての意味を失う時刻であり、失効時刻は、後述するようにして経路探索サーバ３０において、探索された候補経路毎に算出、設定され、経路データに付加される。
【００５０】
一方、経路探索サーバ３０は、図２に示すように、制御手段３１、案内経路データ編集手段３２、経路探索手段３３、通信手段３４、経路失効時刻設定手段３５、道路ネットワークデータ３６、交通ネットワークデータ３７、地図データ３８などを備えて構成されている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４はネットワーク１２を介して端末装置２０などと通信データを送受信するための通信インターフェースである。
【００５１】
端末装置２０において、制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２２はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。位置検出手段２３は、ＧＰＳ受信手段などから構成され、ＧＰＳ衛星信号を受信して現在位置および現在時刻を算出する。
【００５２】
また、位置検出手段２３は、地下鉄などＧＰＳ衛星信号を受信できない交通機関に乗車中は、停車駅における携帯電話基地局との通信あるいは加速度センサなどによる発車、停車検出などにより現在位置を特定するように構成してもよい。
【００５３】
図３は、端末装置２０の表示手段２５に表示される経路探索条件設定のメニュー画面を示す図である。図３に示す経路探索条件設定画面３１０には、出発地入力欄３０２、目的地入力３０３、時刻条件入力欄３０４、候補経路ソート条件を設定するソート条件入力欄３０５、探索開始ボタン３０８が設けられている。
【００５４】
出発地と目的地の設定は、出発地入力欄３０２、目的地入力欄３０３に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。
【００５５】
また、プルダウンボタンを操作して、これまでに端末装置２０に登録した経路探索履歴や登録地点を呼び出して設定することもできる。時刻条件入力欄３０４には出発日時や目的地到着日時などの時刻条件を入力する。時刻条件の設定が必要ない場合には設定を省略することができる。図３は、出発地として「＃＃ビル」が、目的地として「＊＊ホテル」が設定され、時刻条件として目的地到着時刻「１５：３５」が設定された例を示している。
必要な条件設定を終え、探索開始ボタン３０８を操作すると、経路探索要求が端末装置２０から経路探索サーバ３０に送信される。
【００５６】
複数の候補経路の探索を要求する場合には、ソート条件入力欄３０５に、探索された複数の候補経路をソートする条件、例えば、乗換え回数の少ない順、所要時間が短い順、運賃の安い順などの何れかを入力する。プルダウンメニューから前述のソート条件何れかを選択してもよい。候補経路のソート条件が設定されない場合には、最適経路（所要時間の最も短い経路）の探索要求になる。図３ではソート条件として乗換え回数の少ない順が設定されている。
【００５７】
経路探索サーバ３０は、端末装置２０から、出発地や目的地、目的地への到着時刻などの経路探索条件を指定して経路探索要求があると、経路探索手段３３が道路ネットワークデータ３６、交通ネットワークデータ３７を参照して現在位置から目的地までの最適経路または複数の候補を探索する。経路探索手段３３が探索した最適経路または候補経路の情報は案内データ編集手段３２で端末装置２０に配信するための案内データに編集され地図データとともに通信手段３４を介して端末装置２０に配信される。
【００５８】
端末装置２０は案内情報を経路探索サーバ３０から受信すると、候補経路または最適経路の情報を表示手段２５に表示する。複数の候補経路を受信した場合、端末装置２０の利用者は、候補経路を比較して所望の候補経路を案内経路として選択して経路探索サーバから該当する候補経路のデータを受信し、経路案内を行う。最適経路または案内経路は、地図画像とともに表示手段２５に表示され、経路案内が行われる。案内経路の情報は一時記憶手段２７に記憶され、必要に応じて読み出され、表示手段２５に地図画像とともに案内経路の画像として表示される。
【００５９】
案内経路に交通機関を利用した区間が含まれる場合、案内経路の情報には、出発地から最寄り駅までの徒歩経路、目的地の最寄り駅から目的地までの徒歩経路と、出発地の最寄り駅から目的地の最寄り駅までの交通機関の路線、乗車すべき電車やバスなどの交通手段の時刻、乗換え駅が含まれる場合には乗換え駅への到着時刻、乗換え駅で乗換えるべき電車やバスなどの交通手段の詳細な情報が含まれる。また、以下に述べる方法によって経路毎の失効時刻の情報が付加される。
【００６０】
すなわち、経路探索サーバ３０は、経路探索条件に従って交通機関を利用した経路区間を含む最適経路あるいは複数の候補経路を探索すると、経路失効時刻設定手段３５は、各経路毎にその経路が意味を失う失効時刻を算出し、経路データにその失効時刻の情報を付加する。経路が意味を失う時刻とは、例えば、ユーザの出発が予定した時刻（経路探索条件に指定した時刻）に間に合わず、経路として探索された電車の出発時刻を過ぎてしまった場合の時刻であり、すなわち、失効時刻を過ぎてしまった場合には、ユーザはその経路に従って移動することができなくなるので、経路としての意味が失われることになる。
【００６１】
経路失効時刻の算出、設定には種々の方法を用いることができる。以下、探索された経路の例を用いて、いくつかの方法を説明する。例えば、ユーザが指定した出発地、目的地、出発地の出発時刻や目的地への到着時刻などの経路探索条件に基づいて経路探索して得られた経路が、図４に示すような経路（経路１）であったとする。図４に示す経路例は、現在位地（出発地）から徒歩でＡ駅に移動し、Ａ駅から電車を用いて移動しＢ駅で乗換えてＣ駅に至り、Ｃ駅から徒歩で目的地に移動する経路であり、各地点の出発、到着時刻、各地点間の所要時間は、図４に示されているような経路である。
【００６２】
最も単純な方法は、探索された経路において指定された出発時刻そのものを経路の失効時刻として設定する方法（１）である。経路探索条件に従って探索された経路は、当然、経路として示された時刻とおりに行動すれば、目的地まで到達できるものである。従って、経路における出発地の出発時刻を過ぎてしまった場合には、Ａ駅で乗車すべき１２：２７発の電車に乗車できない可能性が生じる。経路として指定された電車に乗車できなければ、経路のとおりに移動できないことになり、この経路１の意味は失われる。従って、出発地の出発時刻を経路１の失効時刻として設定する方法を採ることができる。
【００６３】
他の方法は、最初に交通機関を利用する駅（図４の経路１の場合はＡ駅）において指定された電車の出発時刻（１２：２７）に間に合うように出発地を出発しなければならない限界の時刻を、その経路の失効時刻として設定する方法（２）である。このためには、電車の出発時刻に対して出発地からＡ駅までの経路区間（例えば、徒歩による経路区間）の所要時間（経路コスト）だけ遡った時刻を失効時刻として設定すればよいことになる。一般的には駅構内での所要時間を加味して駅への到着時刻が経路として指定され、駅までの所要時間を遡った時刻が出発地の出発時刻として指定されるから、図４の経路１の場合、Ａ駅への到着時刻（１２：２２）から徒歩経路の所要時間１５分遡った時刻（１２：０７）が出発地の出発時刻となり、この時刻を経路１の失効時刻とするものである。この方法（２）は実質的に上記の方法（１）と同じになるが、駅構内での移動時間としてその駅での乗換え平均時間などが用いられる場合は、幾分の余裕時間を考慮することも可能であり、例えば１分程度の余裕時間を加味して、１２：０８を経路１の失効時刻とすることもできる。
【００６４】
特に、徒歩区間における所要時間は、経路探索においては人の平均的な歩行速度により経路コストが設定されているため、平均より早い歩行速度で歩く人にとっては、経路で設定された所要時間よりも短い時間で駅までの経路を移動できる。その場合、経路で指定された出発時刻をその分だけ遅らせることができ、その時刻を経路失効時刻とする方法（３）を採ることもできる。例えば、図４の経路１においてＡ駅までの徒歩経路の所要時間は１５分であるが、この間を１２分で歩行できる人の場合、出発時刻を３分遅らせることが可能であり、経路１指定された出発地の出発時刻は１２：０７分ではなく、１２：１０まで遅らせることができる。従って、経路１の失効時刻を１２：１０と設定することができる。１２：１０分を過ぎると、経路１での移動は不可能になり、この経路１は意味を失う。
【００６５】
ここでは、出発時刻を遅らせることができる最大の時間を最大遅延許容時間ということとする。最大遅延許容時間は、これを求めるための係数を決めておき、経路の所要時間にその係数を掛けることで求めることができる。例えば、最大遅延許容時間を設定するための係数は、標準歩行速度の場合は０．１、標準よりも早く歩行する場合は０．２５、標準よりもゆっくり歩行する場合は０．０５のように決めておき、ユーザの歩行速度によって係数を選択できるようにしておくと好ましい。
【００６６】
例えば、図４の経路１において、Ａ駅までの徒歩経路の所要時間は１５分であり、標準歩行速度の場合の係数を０．１とすると最大遅延許容時間（分）＝１５×０．１＝１．５分（小数点以下切り上げで２分）となり、経路１の失効時刻は、経路で指定された出発時刻１２：０７に２分を加えて１２：０９となる。
【００６７】
更に、最大遅延許容時間を算出する際に、徒歩経路区間に信号が何箇所あるかなどの経路状況を加味して経路の失効時刻の設定をする方法（４）を採ることもできる。つまり徒歩経路上に交差点が多ければ多い程、信号待ちなどによる遅延が発生する可能性があるため、これを考慮した分、最大遅延許容時間を減じて経路の失効時刻を設定する。例えば、最大遅延許容時間係数を標準の０．１、駅までの標準所要時間を１５分とした場合、前述の方法（３）で述べたように最大遅延許容時間は１５分×０．１≒２分であったが、徒歩経路上に信号が４箇所存在した場合、信号での待ち時間（１箇所１５秒：青も含めた平均待ち時間）を考慮して、最大遅延許容時間は２分−（１５秒×４）＝１分とする。この場合、図４の経路１の失効時刻は、１２：０７＋１分の１２：０８になる。この方法（４）は、信号待ちにより利用者の努力（駅まで走るなど）では所要時間を縮めることが出来ない場合を考慮したものということができる。
【００６８】
端末装置２０は、経路探索サーバ３０から上記のようにして失効時刻が設定された経路の情報を受信すると、それらの候補経路の情報を表示手段２５に表示する。表示される候補経路の順番は、図３の経路探索条件設定画面において指定した候補経路ソート条件による。端末装置２０の利用者は、候補経路を比較して所望の候補経路を案内経路として選択して経路探索サーバから該当する候補経路の詳細なデータを受信し、経路案内を行う。最適経路または案内経路は、地図画像とともに表示手段２５に表示され、経路案内が行われる。案内経路の情報は一時記憶手段２７に記憶され、必要に応じて読み出され、表示手段２５に地図画像とともに案内経路の画像として表示される。
【００６９】
本実施例においては、経路探索サーバ３０から送信された候補経路を端末装置２０に表示する場合、現在時刻において有効な候補経路（失効時刻を経過していない候補経路）が一覧表示される。逆にいえば、現在時刻において意味を失った候補経路は表示されないので、ユーザは候補経路が時間的に間に合うものか否かなど考慮することなく、表示された候補経路の一覧から所望の経路を選択することができる。以下、具体的な表示画面の例を参照して詳細に説明する。
【００７０】
端末装置２０は、現在時刻１２：００に、出発地として「自宅」、目的地として「ＡＡタワー」という地点情報とを含む経路探索条件を経路探索サーバ３０に送信し、経路探索サーバ３０が複数の候補経路を探索し、その結果を端末装置２０が受信し、端末装置２０が表示手段２５に表示する例を説明する。ここでは、説明を簡単にするため、経路探索サーバ３０が各候補経路について算出した経路失効時刻は、各経路の出発時刻であるものとして説明する。
【００７１】
図５は、経路探索サーバ３０から受信した候補経路の一覧を表示する表示画面の一例を示す図であり、図５（ａ）はある時刻における候補経路一覧画面を示しており、図５（ｂ）は、ある時間経過後における候補経路一覧地面を示す図である。図５において、候補経路の表示順序は、乗換え回数の少ない順になっており、各候補経路の情報には、それぞれの経路の失効時刻が付加されているが、失効時刻そのものは一覧画面には表示される必要はない。
【００７２】
現在時刻が１２：００においては、図５（ａ）に示すように、第１経路から第３経路が画面に表示されており、画面をスクロールすることにより、第４経路以下の経路を参照することができる。第１経路は、図４に示す経路１である。時刻が経過し、現在の時刻が１２：０９になると、図５（ａ）の第１経路は失効時刻を経過（出発時刻１２：０７がこの経路の失効時刻として設定されたもの）して経路としての意味を失うので、図５（ｂ）においては、この経路は候補経路一覧から削除され、図５（ａ）の第２経路が第１経路、図５（ａ）の第３経路が第２経路に繰り上がり、図５（ａ）では表示画面のサイズの関係で表示されていなかった第４経路が第３経路として表示される。
【００７３】
図５を参照して説明したように、端末装置２０の表示手段２５に候補経路の一覧を表示する際、現在時刻が変化するたびに各候補経路のそれぞれが失効した時点で、候補経路一覧の表示を更新し、現在時刻において有効な候補経路（失効時刻を経過していない候補経路）のみが一覧表示される。従って、ユーザは候補経路が時間的に間に合うものか否かなど考慮することなく、表示された候補経路の一覧から所望の経路を選択することができるようになる。
【００７４】
なお、経路探索サーバ３０から受信した所定数の候補経路のうち、時刻が経過して失効時刻を経過した候補経路が増え、候補経路一覧に表示する有意な候補経路数が少なくなった場合、端末装置２０から経路探索サーバ３０に追加の候補経路探索の要求を送信し、自動的に新たな候補経路を取得するように構成することもできる。この場合、失効時刻を経過してしまった候補経路が１つ生じたら追加の候補経路探索を要求するようにしてもよく、経路探索サーバ３０から受信した候補経路のうち、失効した候補経路の割合が所定以上、例えば、半数を超えたら追加の候補経路探索を要求するようにしてもよい。
【００７５】
追加の候補経路探索要求の場合、経路探索サーバ３０は、現在時刻のみを変更し、出発地、目的地などのその他の経路探索条件は当初と同じものとして所定数の候補経路を探索し、各候補経路の失効時刻を設定して端末装置２０に提供する。このような構成によれば、ユーザが改めて経路探索条件を設定して、経路探索要求を送信する手間を必要としない。
【００７６】
また、端末装置２０から経路探索サーバ３０に追加の候補経路探索を要求する構成の場合、出発地である現在地を変更したい場合には、ユーザが再度現在位置の取得および経路探索サーバ３０への経路探索要求を行う操作を行うようにする。これによって、端末装置２０は、位置検出手段２３（ＧＰＳ受信機）を起動しておく必要がないので電力の消費を防ぐことも可能になる。
【００７７】
次に、経路探索サーバ３０における経路探索の概念について説明する。経路探索用のネットワークデータとしては、徒歩や自動車による移動経路を探索するための道路ネットワークデータ３６と公共交通機関を利用した移動経路を探索するための交通ネットワークデータ３７が蓄積されている。経路探索手段３３は、この経路探索用ネットワークデータを参照して、徒歩や自動車による経路あるいは徒歩と交通機関を併用した経路を探索する。
【００７８】
道路ネットワークデータ３６（図２参照）は、以下のように構成されている。例えば、道路が、図６に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００７９】
すなわち、図６において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図６では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００８０】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図６において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００８１】
図６ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００８２】
これに対して、交通機関の経路探索のための交通ネットワークデータ３７（図２参照）は以下のように構成されている。例えば、図７に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図７において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００８３】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図７に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００８４】
図７に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。
【００８５】
このような交通ネットワークデータ３７を用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００８６】
例えば、図７において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００８７】
このようなネットワークデータを利用して経路探索サーバ３０は経路探索条件に従って、出発地から目的地までの複数の候補経路を探索し、その結果を案内経路データとして端末装置２０に送信する。経路探索条件に出発地の出発時刻が指定されている場合には目的地への到着時刻が、また、目的地への到着時刻が指定されている場合には、目的地に指定時刻に到着するための出発地の出発時刻が案内経路データに含まれ、端末装置２０はこれらを表示手段２５に経路の詳細とともに表示することができる。案内経路に乗換え駅が含まれる場合には、当該乗換え駅で乗換えるべき電車やその出発時刻も同様にして表示することができる。
【００８８】
移動の手段として徒歩と交通機関を用いる場合の経路探索においては、道路ネットワークデータ３６と交通ネットワークデータ３７とを結合して総合的なネットワークデータを編集し経路探索を行う。徒歩経路区間は道路ネットワークデータ３６が参照され、交通機関を用いる経路区間は交通ネットワークデータ３７が参照される。最適経路の探索においては、トータルで経路コストが最小となる経路が探索される。この場合、徒歩経路区間が最小にならない経路が探索されることもある。
【００８９】
徒歩経路区間が最も小さい経路を要求する場合には、徒歩経路区間を最短とする条件を設定する。また、乗換え回数が最小になる経路探索を要求する場合は、乗換え回数を最小とする条件を設定する。更に、交通機関を利用した経路区間の運賃が最小になる条件を設定することもできる。これらの条件設定は、交通機関を用いた経路探索においては一般的なものである。
【００９０】
次に、本発明の実施例１にかかるナビゲーションシステム１０の動作手順について説明する。図８は、端末装置２０における動作手順を示すフローチャート、図９は経路探索サーバ３０における動作手順を示すフローチャートである。
【００９１】
端末装置２０は、図８に示すように、まず、ステップＳ１０１において操作入力手段２９がユーザからの経路探索条件の入力を受け付けると、ステップＳ１０２の処理に進み、現在時刻を取得する。現在時刻の取得は、位置検出手段２３が有するＧＰＳ受信機を用いて時刻を算出することによって行うことができる。もちろん、端末装置２０が備える時計手段などにより現在時刻を取得してもよい。
【００９２】
ステップＳ１０３の処理では、ステップＳ１０１で受け付けた地点情報と、ステップＳ１０２で取得した時刻情報とを、通信手段２２を介して経路探索サーバ３０へ送信し、ステップＳ１０４において経路探索サーバ３０から候補経路の情報と失効時刻を含む経路探索結果を受信する。続いて、ステップＳ１０５で受信した候補経路の情報を一時記憶手段２７に格納する。
【００９３】
ステップＳ１０６の処理では、ステップＳ１０５において一時記憶手段２７に格納した候補経路の情報を読み出して表示手段２５に表示し、処理はステップＳ１０７へ進む。ステップＳ１０７において、ユーザから表示終了の指示を操作入力手段２９が受け付けた場合には、処理は終了となる。
【００９４】
終了指示がない場合には、ステップＳ１０８において現在時刻を取得し、失効時刻判別手段２８は、ステップＳ１０９において現在時刻と、各候補経路の情報に付加されている失効時刻との比較を行い、現在時刻において失効した候補経路を判別する。現在時刻において、表示されている各候補経路のうち、失効時刻を経過した候補経路（経路としての意味を失なった候補経路）がない場合には、処理はステップＳ１０６へ進み、候補経路の一覧表示を続ける。
【００９５】
現在時刻において、表示されている各候補経路のうち、失効時刻を経過した候補経路（経路としての意味を失なった候補経路）があった場合には、処理はステップＳ１１０に進み、表示制御手段２６は、失効した候補経路を削除して候補経路一覧を表示する。そして、処理はステップＳ１０３に進み、端末装置２０は、経路探索サーバ３０に現在時刻を経路探索条件として、追加の候補経路探索要求を送信する。
【００９６】
一方、経路探索サーバ３０は、図９に示すように、ステップＳ２０１において、通信手段３４を介して探索条件と時刻情報を含む探索情報を端末装置２０から受信すると、ステップＳ２０２において探索条件に従い経路探索手段３３が道路ネットワークデータ３６、交通ネットワークデータ３７を参照して最適経路を含む複数の候補経路の探索を行う。
【００９７】
次いで、処理はステップＳ２０３に進み、経路失効時刻設定手段３５は、最大遅延許容時間として設定された係数を用い、出発地から最初に利用する交通機関の発着所までの所要時間に基づいて、最大遅延許容時間を算出し、ステップｓ２０４の処理に進み、経路失効時刻設定手段３５は、経路の出発時刻に最大遅延許容時間を加えてその経路の失効時刻として設定する。この方法に限らず、失効時刻の設定は先に説明した種々の方法によって行うことができる。続いて、ステップＳ２０５において、経路探索サーバ３０は、案内データ編集手段３２がステップＳ２０２で算出した候補経路の情報にステップＳ２０５で算出した失効時刻を付加する編集を行って端末装置２０に送信する。
【実施例２】
【００９８】
上記実施例１にかかるナビゲーションシステムにおいては、経路探索サーバ３０において探索した各候補経路の失効時刻を設定し、各候補経路のデータに失効時刻を付加して端末装置２０に送信する例を説明したが、経路探索サーバ３０は失効時刻を設定することなく、候補経路のデータを端末装置２０に送信し、端末装置２０側で、候補経路を表示する際に、各候補経路の失効時刻を設定して現在時刻において表示する候補経路を決定するようにしてもよい。図１０は、端末装置２０において失効時刻を設定して候補経路の一覧を表示するように構成した本発明の実施例２にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【００９９】
図１０に示すナビゲーションシステム１０の構成は、基本的に図２に示すナビゲーションシステム１０の構成と同様であり、図２と相違する点は、経路探索サーバ３０に、失効時刻設定手段３５を持たず、端末装置２０に失効時刻設定判別手段２８１を備え、経路探索サーバ３０から受信した候補経路について、失効時刻設定判別手段２８１において、各候補経路の失効時刻を設定もしくは判別するようにした点が異なる。図１０において、図２の構成要素と同一の構成要素は、図２の実施例１の参照番号と同一の参照番号を付しており、実施例１と重複する部分の説明は省略する。
【０１００】
本実施例２のように、端末装置２０側で候補経路の失効時刻を用いて表示手段２５に候補経路の一覧を表示する場合、失効時刻設定判別手段２８１は、経路探索サーバ３０から受信した候補経路の各々について予め各候補経路の失効時刻を算出して設定してもよく、現在時刻に基づいて候補経路の一覧を表示する際、後述する方法により失効した候補経路を特定し、表示する候補経路一覧からその候補経路を削除するようにしてもよい。前者の場合は、実施例１における経路失効時刻設定手段３５（図２参照）の処理が、端末装置２０の失効時刻設定判別手段２８１によって行われる点が実施例１の場合と異なるだけである。
【０１０１】
以下、現在時刻に基づいて候補経路の一覧を表示する際、失効した候補経路を特定し、表示する候補経路一覧からその候補経路を削除する手順について説明する。図１１は、図１０の端末装置に表示される候補経路の一覧画面の一例を示す図であり、図１１（ａ）はある時刻における候補経路一覧画面を示す図、図１１（ｂ）は、ある時間経過後における候補経路一覧地面を示す図である。
【０１０２】
図１１に示す候補経路一覧は、所望の時刻（例えば、１８：００）を出発時刻とし、出発地として「会社」、目的地として「ＡＡ海浜公園」という地点情報とを含む経路探索条件を経路探索サーバ３０に送信し、経路探索サーバ３０が探索した複数の候補経路を受信した際に、表示手段２５に表示される候補経路一覧を示している。
【０１０３】
端末装置２０は、候補経路一覧を表示手段２５に表示する際、現在時刻に基づいて、現在時刻に最も近い出発時刻を有する候補経路から順に候補経路一覧を表示する。現在時刻が１８：００の時点では、図１１（ａ）に示すように、経路探索サーバ３０から受信した候補経路の中で、出発時刻が１８：００の第１経路、１８：１０の第２経路、１８：１５の第３経路が表示される。
【０１０４】
図１１（ｂ）は、現在時刻が１８：０６の時点で表示手段２５に表示された候補経路一覧を示している。この時、失効時刻設定判別手段２８１は、現在時刻に最も近い出発時刻を持つ候補経路を特定し、現在時刻よりも前の時刻を出発時刻とする候補経路は、失効したものとて判別し、失効した候補経路がある場合、その候補経路は候補経路一覧から削除する。
【０１０５】
従って、図１１（ｂ）において、図１１（ａ）の第１経路は失効し、一覧表示からは削除され、図１１（ａ）の第２経路、第３経路が、図１１（ｂ）では第１経路、第２経路として表示され、図１１（ｂ）の第３経路には、表示画面のサイズの関係で表示されていなかった第４経路が、図１１（ａ）では第３経路として表示される。このように、失効時刻設定判別手段２８１は、現在時刻に最も近い出発時刻を持つ候補経路を特定し、現在時刻よりも前の時刻を出発時刻とする候補経路は、失効したものとて判別し、失効した候補経路がある場合、その候補経路は候補経路一覧から削除する。
【０１０６】
なお、失効によって、表示できる候補経路数が少なくなった場合、端末装置２０は経路探索サーバ３０に追加の候補経路探索を要求するように構成することも可能である。この点は、前述の実施例１の場合と同様である。また、候補経路一覧に表示される候補経路の出発時刻が同一時刻である場合、出発地から乗車駅までの所要時間の差により、各候補経路の最大遅延許容時間に差が生じ、失効時刻がそれぞれ異なる場合があるので、この場合には、失効時刻設定判別手段２８１は予め、各候補経路の失効時刻を算出しておくように構成することが好ましい。
【０１０７】
なお、上記のように、現在時刻に基づいて、最も現在時刻に近い出発時刻を持つ候補経路から順に、各候補経路の一覧を表示する際、失効時刻設定判別手段２８１は、出発時刻が現在時刻よりも前の、本来失効している候補経路を含めて表示順序を決定し、最も現在時刻に近い出発時刻を持つ候補経路を特定し、その候補経路よりも前の（古い）出発時刻を持つ候補経路を、失効した候補経路と判別して、表示する候補経路から削除するようにしてもよい。図１２は、図１１に示す候補経路の一覧について、このような方法で表示した場合の一例を示す図である。
【０１０８】
図１２は、現在時刻が１８：０４の時点で表示された候補経路一覧を示している。１８：０４の時点では、図１１（ａ）に示す出発時刻（１８：００）の第１経路が、現在時刻（１８：０４）との差が４分で、出発時刻が現在時刻に最も近い経路である（第２経路の出発時刻（１８：１０）は現在時刻との差が６分である）。従って、図１２に示すように１８：０４における候補経路一覧は、図１１（ａ）と比べて変化がない。現在時刻が１８：０６になると、最も近い出発時刻を持つ候補経路は、１８：１０の出発時刻を持つ候補経路（図１１（ａ）における第２経路）になるから、この時点で、失効時刻設定判別手段２８１は、この第２経路の出発時刻よりも前の（古い）出発時刻を持つ候補経路（図１１（ａ）の第１経路）を失効したものとして候補経路から削除する。この結果表示される候補経路一覧は図１１（ｂ）に表示されたものと同じになる。
【０１０９】
このような表示方法にすれば、図１２における第１経路は出発時刻が現在時刻よりも４分前の経路であるから、失効した経路である可能性が高い経路ではあるが、予め各候補経路の失効時刻を設定することなく、候補経路の表示の際に失効時刻設定判別手段２８１が候補経路の失効を簡単に判別することができるようになる。このような失効時刻設定判別手段２８１の態様も、広義の意味で失効時刻を設定し、失効時刻を過ぎた候補経路を判別する機能を果たすこととなるので、本発明においては、この態様を含め、候補経路の失効時刻を設定するということとする。
【０１１０】
以上、詳細に説明したように、本発明によれば、公共交通機関を利用した経路区間を含む複数の候補経路を端末装置に表示する際に、各候補経路が経路としての意味を失う失効時刻を対応付けておき、失効時刻を経過した候補経路を順次削除して、有意な候補経路のみをリアルタイムに表示するものであるから、ユーザが経路探索時に入力した時刻通りに移動を開始できなかった場合に、有意な経路の情報を容易にしることができるようになり、また、表示される候補経路の数が減った場合に経路探索サーバにおいて、追加の候補経路を探索してユーザに提供することができるようになる。
【産業上の利用可能性】
【０１１１】
本発明は、携帯端末を用いた通信型のナビゲーションシステムに限ることなく、パーソナルコンピュータを端末装置としたナビゲーションシステム、路線情報（経路情報）提供システムにも適用可能である。
【図面の簡単な説明】
【０１１２】
【図１】本発明の実施例１にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例１にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】経路探索条件の設定メニュー画面の一例を示す図である。
【図４】探索された経路の一例を示す図である。
【図５】端末装置に表示される候補経路の一覧画面の一例を示す図であり、図５（ａ）はある時刻における候補経路一覧画面を示す図、図５（ｂ）は、ある時間経過後における候補経路一覧地面を示す図である。
【図６】道路ネットワークのデータの概念を示す模式図である。
【図７】交通ネットワークのデータの概念を示す模式図である。
【図８】本発明の実施例１にかかるナビゲーションシステムを構成する端末装置の動作手順を示すフローチャートである。
【図９】本発明の実施例１にかかるナビゲーションシステムを構成する経路探索サーバの動作手順を示すフローチャートである。
【図１０】本発明の実施例２にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図１１】図１０の端末装置に表示される候補経路の一覧画面の一例を示す図であり、図１１（ａ）はある時刻における候補経路一覧画面を示す図、図１１（ｂ）は、ある時間経過後における候補経路一覧地面を示す図である。
【図１２】図１１に示す候補経路の一覧画面の他の表示例を示す図である。
【符号の説明】
【０１１３】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・位置検出手段
２４・・・・経路記憶手段
２５・・・・表示手段
２６・・・・表示制御手段
２７・・・・一時記憶手段
２８・・・・失効時刻判別手段
２９・・・・操作入力手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・案内データ編集手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・経路失効時刻設定手段
３６・・・・道路ネットワークデータ
３７・・・・交通ネットワークデータ
３８・・・・地図データ
５０・・・・情報配信サーバ
【図１】
2010054390.tif 000003
【図２】
2010054390.tif 000004
【図３】
2010054390.tif 000005
【図４】
2010054390.tif 000006
【図５】
2010054390.tif 000007
【図６】
2010054390.tif 000008
【図７】
2010054390.tif 000009
【図８】
2010054390.tif 000010
【図９】
2010054390.tif 000011
【図１０】
2010054390.tif 000012
【図１１】
2010054390.tif 000013
【図１２】
2010054390.tif 000014