ナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置
【課題】出発地の出発時刻と目的地への到着時刻を設定し、その時刻条件を満足する最適経路や候補経路を探索する。
【解決手段】ナビゲーションシステム１０は、最早出発時刻および最遅到着時刻を含む経路探索条件を入力する操作入力手段２６と、時刻条件シフト手段３７と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段３６と、案内経路ソート手段３３と、を備え、時刻条件シフト手段３７は、予め定められた条件に従って、時刻条件を順次異なる時刻条件に変更し、経路探索手段３９は時刻条件シフト手段３７が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、到着時刻判別手段３６は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として案内経路ソート手段３３に記憶し、該案内経路ソート手段３３は、候補経路を経路探索条件により指定された順にソートして出力する。
【解決手段】ナビゲーションシステム１０は、最早出発時刻および最遅到着時刻を含む経路探索条件を入力する操作入力手段２６と、時刻条件シフト手段３７と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段３６と、案内経路ソート手段３３と、を備え、時刻条件シフト手段３７は、予め定められた条件に従って、時刻条件を順次異なる時刻条件に変更し、経路探索手段３９は時刻条件シフト手段３７が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、到着時刻判別手段３６は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として案内経路ソート手段３３に記憶し、該案内経路ソート手段３３は、候補経路を経路探索条件により指定された順にソートして出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、徒歩や自動車あるいは公共交通機関を利用して、任意の出発地から目的地に至る候補経路を探索して案内するナビゲーションシステムに関するものであり、特に、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、出発地を出発する最早出発時刻および目的地に到着する最遅到着時刻を指定して経路探索できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
徒歩経路に加えて交通機関を用いた経路を探索するナビゲーションシステムは、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に開示されている。この特許文献２に開示されたナビゲーションシステムは、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法を用いるものである。
【００１０】
そして、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するように構成されている。
【００１１】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのまま、あるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１２】
ナビゲーションシステムを用いて経路探索、経路の案内を受ける場合、出発地を出発する時刻を指定して目的地までの最適経路や複数の候補経路を探索するケースがある。また、目的地への到着時刻を設定し、出発地から目的地までの経路のうち、指定した時刻に目的地に到達できる最適経路や候補経路を探索するケースがある。後者においては、指定した時刻に目的地に到達するために出発地を何時に出発すればよいかがわかる。
【００１３】
また、出発地の出発時刻範囲または目的地への到着時刻範囲を指定して経路探索ができると、所望の時刻範囲を満足する最適経路や、候補経路の探索ができ、時刻条件を順次変えながら経路探索を繰り返す必要がなく、便利である。本願の出願人はこのような目的を達成する発明として、既に特願２００７−０６９４２６号の発明および特願２００７−１３０６５３号の発明についての特許出願を行っている。
【００１４】
この特願２００７−０６９４２６号（以下、「先願１」という。）に開示された発明は、目的地への到着時刻の範囲を含む経路探索条件を入力する操作入力手段と、到着時刻の範囲を判別する時刻範囲判別手段と、時刻条件をシフトする時刻条件シフト手段と、案内経路ソート手段と、を備え、時刻条件シフト手段は、予め定められた条件に従って到着時刻範囲内において、時刻条件を順次異なる時刻条件に変更し、経路探索手段は時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索して候補経路として案内経路ソート手段に記憶し、該案内経路ソート手段は、候補経路を経路探索条件により指定された順にソートして出力するように構成されたものである。
【００１５】
また、特願２００７−１３０６５３号（以下、「先願２」という。）に開示された発明は、出発地からの出発時刻の範囲を含む経路探索条件を入力する操作入力手段と、出発時刻の範囲を判別する時刻範囲判別手段と、時刻条件をシフトする時刻条件シフト手段と、案内経路ソート手段と、を備え、時刻条件シフト手段は、予め定められた条件に従って出発時刻範囲内において、時刻条件を順次異なる時刻条件に変更し、経路探索手段は時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索して候補経路として案内経路ソート手段に記憶し、該案内経路ソート手段は、候補経路を経路探索条件により指定された順にソートして出力するように構成されたものである。
【００１６】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図３、図３）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上記先願１や先願２の発明によれば、出発時刻に所望の時間幅を設定し、または、到着時刻に所望の時間幅を設定して、その時刻条件を満足する最適経路や候補経路を探索することができる。ところで、ナビゲーションシステムの利用者には、出発地を出発する時刻としておよその所望時刻を考慮し、同時に目的地に到着する時刻としておよその所望時刻を考慮して、両方の時刻条件を満足する最適経路や候補経路の有無を知りたいという要求もある。しかしながら、上記特許文献２や先願１あるいは先願２の発明においては、このような経路探索ができないという問題点があった。
【００１８】
従って、上記のような経路の有無を知るためには、ナビゲーションシステムの利用者は出発時刻と到着時刻を種々組み合わせて何度も経路探索を繰り返し、試行錯誤的に経路の有無を判断する手順を採る必要があり、手間がかかるという問題点があった。
【００１９】
上記先願１や先願２によれば、ユーザは大よその出発したい時刻または到着したい時刻を、時間幅を持った時刻入力を可能にすることによって経路探索を可能にするものである。しかしながら、出発時刻幅または到着時刻幅のいずれか一方のみを考慮した経路探索であるため、出力される結果について例えば出発時刻が思いのほか早くなってしまったり、到着時刻が思いのほか遅くなってしまったりということが起きていた。
【００２０】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、出発地を出発する最早出発時刻および目的地に到着する最遅到着時刻を指定して経路探索できるようになせば上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００２１】
すなわち、本発明は、上記の問題点を解消することを課題とし、出発地の出発時刻と目的地への到着時刻を設定し、その時刻条件を満足する最適経路や候補経路を探索することができるナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２２】
前記課題を解決するために、本願の請求項１にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする。
【００２３】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００２４】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする。
【００２５】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする。
【００２６】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００２７】
本願の請求項６にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００２８】
また、本願の請求項７にかかる発明は、
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、前記端末装置から受信した経路探索条件に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索サーバにおいて、
前記端末装置から送信される経路探索要求は、出発地からの最早出発時刻および目的地への最遅到着時刻を含み、
前記経路探索サーバは、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする。
【００２９】
本願の請求項８にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記端末装置から送信される経路探索要求は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００３０】
本願の請求項９にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする。
【００３１】
本願の請求項１０にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする。
【００３２】
本願の請求項１１にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００３３】
本願の請求項１２にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００３４】
また、本願の請求項１３にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段が、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更するステップと、前記経路探索手段が、前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し、到着予想時刻を算出するステップと、前記到着時刻判別手段が、前記到着予想時刻が前記最遅到着時刻より早いか否かを判別するステップと、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶するステップと、該案内経路ソート手段が、前記候補経路を前記経路探索条件により指定された順にソートして出力するステップと、を有することを特徴とする。
【００３５】
本願の請求項１４にかかる発明は、請求項１３にかかる経路探索方法において、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００３６】
本願の請求項１５にかかる発明は、請求項１３にかかる経路探索方法において、前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する処理を含むことを特徴とする。
【００３７】
本願の請求項１６にかかる発明は、請求項１３にかかる経路探索方法において、前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する処理を含むことを特徴とする。
【００３８】
本願の請求項１７にかかる発明は、請求項１３にかかる経路探索方法において、前記到着時刻判別手段が、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００３９】
本願の請求項１８にかかる発明は、請求項１３にかかる経路探索方法において、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００４０】
また、本願の請求項１９にかかる発明は、
時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、出発地と目的地を含む経路探索条件を入力する操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により、出発地からの最早出発時刻および目的地への最遅到着時刻を入力するようになしたことを特徴とする。
【００４１】
本願の・請求項２０にかかる発明は、請求項１９にかかる端末装置において、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、到着時刻範囲を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【発明の効果】
【００４２】
請求項１にかかる発明においては、ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する。
【００４３】
このような構成によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。従って、利用者はその候補経路の中から自身の要求にあった経路を容易に選択することができるようになる。
【００４４】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含む。
【００４５】
このような構成によれば、経路探索条件として交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を指定して、目的地への到着時刻の範囲を設定した経路探索が行えるようになる。
【００４６】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する。
【００４７】
このような構成によれば、経路探索手段は、時刻条件シフト手段が、指定された最早出発時刻から所定の時間間隔で変更した到着時刻に基づいて、最遅到着時刻より前に目的地に到着できる候補経路を探索することができるようになる。
【００４８】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する。
【００４９】
このような構成によれば、経路探索手段は、時刻条件シフト手段が、指定された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして、最遅到着時刻より前に目的地に到着できる候補経路を探索することができるようになる。また、出発地の最寄り駅を出発する便数が少ない場合には、経路探索手段が候補経路を探索する回数を少なくすることができるようになる。
【００５０】
また、請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了する。
【００５１】
このような構成によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。
【００５２】
また、請求項６にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加される。
【００５３】
このような構成によれば、利用者はこの表示結果から、所望の条件に合致する経路を容易に選択することができるようになる。また、候補経路を選択することにより該当する候補経路の詳細情報を容易に知ることができるようになる。
【００５４】
また、請求項７ないし請求項１２にかかる発明においては、それぞれ請求項１ないし請求項６にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになり、請求項１３ないし請求項１８にかかる発明においては、それぞれ請求項１ないし請求項６にかかるナビゲーションシステムを実現するための経路探索方法を提供することができるようになる。また、請求項１９、請求項２０にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００５５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００５６】
図１は、本発明にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、音楽や各種画像などのコンテンツその他の情報を提供する各種の情報配信サーバ５１などを備えて構成されている。
【００５７】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００５８】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。
【００５９】
図１に示す経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５を備え、端末装置２０から経路探索要求があると、探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た案内経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。
【００６０】
一方、端末装置２０は、経路探索サーバ３０に出発地の出発時刻と目的地への到着時刻を経路探索条件として経路探索を要求する出発時刻・到着時刻指定経路探索モードを設定することができる。この出発時刻・到着時刻指定経路探索モードが設定されない場合は、通常の経路探索の要求になる。出発時刻・到着時刻指定経路探索モードにおける出発時刻は、出発地を出発する最早の時刻を設定し、到着時刻は目的地に到着する最遅の時刻を設定する。すなわちこの時刻条件は、利用者が出発時刻として許容しようとする最も早い時刻と到着時刻として許容しようとする最も遅い時刻を設定するものである。
【００６１】
経路探索サーバ３０は、端末装置２０から、出発時刻・到着時刻指定経路探索モードを設定した経路探索要求があると、指定された最早出発時刻から所定の時間間隔で出発時刻をシフトしながら候補経路を探索する。候補経路が探索されると、その目的地到着時刻を算出し、設定された最遅到着時刻より前に到着できる経路であるか否かを判別する。設定された最遅到着時刻より前に到着できる経路が得られない場合には経路探索を終了し、各経路探索で得られた候補経路を指定された条件でソートして出力する。この時の経路探索は一般的なナビゲーションシステムで行われる出発時刻指定の経路探索の手法で行うことができる。
【００６２】
このような経路探索を行えば、所望の最早出発時刻以降に出発し、最遅到着時刻前に目的地に到着するための候補経路を得ることができ、端末装置２０の利用者は案内された複数の候補経路のうちから好みの経路を選択することができるようになる。なお、到着時刻条件を満足する候補経路が提示されない場合には、最早出発時刻または最遅到着時刻の何れか一方または両方を再設定するよう促す案内を行えば、ナビゲーションシステムの利用者は容易に再探索の要求を行うことができるようになる。
【００６３】
以下、具体例に基づいて本発明を説明するが、その前に本発明にかかるナビゲーションシステム１０の詳細な構成を説明する。図２は、図１のナビゲーションシステム１０の詳細な構成を示す図である。端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、探索要求手段２３、案内経路データ記憶手段２４、表示手段２５、操作入力手段２６を備えて構成される。
【００６４】
操作入力手段２６は、出発地、目的地、その他の経路探索条件を入力する第１入力手段２６１と、最早出発時刻（出発地を出発する所望の最も早い時刻）および最遅到着時刻（目的地に到着する所望の最も遅い時刻）を入力する第２入力手段２６２を含んでいる。第１入力手段２６１、第２入力手段２６２は数値キーを用いることができるが、後述する条件入力画面に設けたプルダウンメニューにより表示される数値を用いることもできる。第１入力手段２６１により入力されるその他の経路探索条件とは、例えば、交通機関を利用した経路の運賃、乗り換え回数、所要時間などである。
【００６５】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、案内経路データ編集手段３２、案内経路ソート手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、到着時刻判別手段３６、時刻条件シフト手段３７、探索要求記憶手段３８、経路探索手段３９を備えて構成される。時刻条件シフト手段３７は、出発時刻・到着時刻指定経路探索モードの経路探索要求が端末装置２０から送信された場合に、経路探索条件として指定された最早出発時刻から、所定の時間間隔で出発地の出発時刻を順次シフトする。経路探索手段３９はシフトされた出発時刻を条件として出発地から目的地までの候補経路（最適経路）を探索し、目的地への到着予想時刻を算出する。
【００６６】
到着時刻判別手段３６は、時刻条件シフト手段３７が順次シフトした時刻条件のそれぞれを用いて経路探索手段３９が探索した候補経路（案内経路候補）における到着時刻が到着時刻条件を満足するかを判別する。到着時刻条件を満足する候補経路とは、経路探索条件として指定された最遅到着時刻より前に目的地に到着できる経路である。候補経路の到着時刻が最遅到着時刻より前であれば、その経路は端末装置２０に回答する候補経路（案内経路）とされる。端末装置２０に候補経路（案内経路）を送信する際、案内経路ソート手段３３は、出発時刻をシフトして経路探索した結果として得られる候補経路であって、到着時刻判別手段が到着時刻条件を満足すると判別した候補経路を一時記憶し、指定された条件に応じてソートする。ソートされた候補経路は端末装置２０に送信され、端末装置２０の表示手段２５に表示される。
【００６７】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００６８】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２６は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの入力機能としても用いられる。表示手段２５は液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２５はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。
【００６９】
経路探索サーバ３０から端末装置２０に送信される最適経路や候補経路などの案内経路データは地図データとともに案内経路データ記憶手段２４に記憶され、案内経路データ記憶手段２４に記憶された候補経路などの案内データや地図データは、必要に応じて読み出され、表示手段２５に表示される。
【００７０】
図３は、端末装置２０の外観の一例を示す図であり、図３に示す端末装置２０は携帯電話を端末装置としたものである。端末装置２０は、液晶表示ユニットなどからなる表示手段２５、テンキーやダイヤル、ボタンなどを有する操作入力手段２６を備えている。経路探索サーバ３０から送信された地図データや案内経路データは案内経路データ記憶手段２４に記憶され、必要に応じて案内経路データ記憶手段２４から読み出され、表示手段２５の表示画面２５１に表示される。
【００７１】
図４は、表示画面２５１に表示される経路探索条件入力画面の一例を示す図である。端末装置２０は、操作入力手段２６により入力された条件や操作に基づいて経路探索要求を経路探索サーバ３０に送信する。経路探索サーバ３０に経路探索要求する場合には、図４に示すように表示手段２５に表示されたメニューから、あるいは、操作入力手段２６から所望の出発地、目的地を設定して経路探索サーバ３０に送信する。
【００７２】
図４は、端末装置２０が到着時刻範囲指定経路探索モードに設定された場合に表示される経路探索条件入力画面の例を示している。この経路探索条件入力画面には、出発地入力欄２５２、目的地入力欄２５３、最早出発時刻入力欄２５４、最遅到着時刻入力欄２５５、出力順（ソート条件）入力欄２５６、探索開始ボタン２５７が設けられている。
【００７３】
出発地と目的地の設定は、出発地入力欄２５２、目的地入力欄２５３に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。また、出発地の入力には、ＧＰＳ受信手段２２で測位した端末装置２０の現在位置を用いるようにすることもできる。
【００７４】
また、プルダウンボタンを操作して、これまでに端末装置２０に登録した経路探索履歴や登録地点を呼び出して設定することもできる。最早出発時刻入力欄２５４には出発地を出発する所望の最も早い時刻「ＸＸ時ＹＹ分」を入力し、次いで、最遅到着時刻入力欄２５５に、目的地へ到着する所望の最も遅い時刻「ＷＷ時ＺＺ分」を入力する。必要な条件設定を終え、探索開始ボタン２５７を操作すると、経路探索要求が端末装置２０から経路探索サーバ３０に送信される。
【００７５】
出力順は、その他の経路探索条件として交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れかが指定された場合には、指定された条件に適合するように決定することができる。例えば、経路探索条件として乗り換え回数が指定された場合には、複数の候補経路を乗り換え回数の少ない順にソートする。複数の条件が設定されている場合には出力順（ソート条件）入力欄２５６で出力順を指定することもできる。
【００７６】
経路探索サーバ３０は、端末装置２０から経路探索要求があると、これを探索要求記憶手段３８に一時記憶する。そして経路探索手段３９は、探索要求記憶手段３８に記憶した経路探索要求に従って経路探索用ネットワークデータベース３５を参照して出発地から目的地までの複数の候補経路を探索する。経路探索要求が通常の経路探索の要求である場合、経路探索の結果得られた案内経路のデータを地図データベース３４から読み出した地図データとともに端末装置２０に送信する。この経路探索の方法は通常のナビゲーションシステムにおける経路探索サーバと同様の方法である。
【００７７】
一方、経路探索要求が出発時刻・到着時刻指定経路探索モードの経路探索の要求である場合、時刻条件シフト手段３７は経路探索条件に指定された最早出発時刻に基づいて、指定された最早出発時刻を経路探索手段３９に送り、以後は、出発時刻を所定の時間間隔（例えば、５分間隔）で順次シフトして経路探索手段３９に送る。経路探索手段３９は、時刻条件シフト手段３７から出発時刻を受取るごとに出発地から目的地までの最適経路を探索する。ここで探索する経路は所要時間の最も短い最適経路であってもよい。ここでは、最適経路を含めて候補経路ということとする。
【００７８】
なお、時刻条件シフト手段３７による出発時刻のシフトは、前述のように所定の時間間隔で行ってもよく、また、交通機関を用いた経路区間がある場合には、入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更するように構成することもできる。このように構成すれば、出発地の最寄り駅を出発する便数が少ない場合には、経路探索手段が候補経路を探索する回数を少なくすることができるようになる。
【００７９】
到着時刻判別手段３６は、経路探索手段３９が探索した最適経路における目的地への到着予想時刻が到着時刻の条件、すなわち、指定された最遅到着時刻を満足するか否かを判別する。探索した経路の目的地到着時刻が指定された最遅到着時刻より前であれば、到着時刻の条件を満足するので、到着時刻判別手段３６は、探索された経路を候補経路とする。到着時刻条件を満足する経路の情報は、案内経路ソート手段３３に一時記憶される。
【００８０】
時刻条件シフト手段３７による出発時刻のシフト処理、経路探索手段３９による最適経路探索処理は、経路探索手段３９が時刻条件シフト手段３７から得た出発時刻による探索した候補経路について、到着時刻判別手段３６において到着時刻条件を満足しない、すなわち、経路の目的地到着時刻が、指定された最遅到着時刻よりも後の時刻になるまで行われる。
【００８１】
案内経路ソート手段３３には上記の経路探索によって得られた複数の候補経路が記憶されている。端末装置２０への候補経路（探索結果）の出力は、端末装置２０が設定したソート順に従ってソートして行われる。例えば、図４の条件入力画面に示したように出力順として「所要時間の短い順」が指定されている場合、案内経路ソート手段３３は、一時記憶している複数の候補経路を出発地から目的地までの所要時間が短い順にソートする。
【００８２】
案内経路ソート手段３３がソートした候補経路のデータは案内経路データ編集手段３２により端末装置２０に送信するためのデータに編集され通信手段３１を介して端末装置２０に送信される。端末装置２０は経路探索サーバ３０から受信した案内経路のデータ（ソート済の候補経路のデータ）を案内経路データ記憶手段２４に記憶し、必要により表示手段２５に表示する。
【００８３】
最早出発時刻に基づいて探索した経路の目的地到着時刻が最遅到着時刻より遅い経路であった場合、最早出発時刻の条件、最遅到着時刻の条件を同時に満足する候補経路が存在しないことを意味する。すなわち、最早出発時刻〜最遅到着時刻までを所要時間として出発地から目的地まで移動できる経路が存在しないことを意味し、出発時刻・到着時刻の設定に無理があったことになる。その場合、経路探索サーバ３０は、時刻条件を再設定するよう促すメッセージを回答する
【００８４】
図５は、端末装置２０において表示画面２５１に表示される出発時刻・到着時刻指定経路探索モードの経路探索結果を示す出力画面の一例を示す画面構成図である。図５に示す例は、出発地として「自宅」が、目的地として「ＹＹＹランド」が設定され、最早出発時刻が「８；００」、最遅到着時刻が「１１：００」と設定された場合の候補経路を表示した例を示している。候補経路は出発時刻順にソートして表示され、各候補経路にはその所要時間が表示される。
【００８５】
第１経路は、出発地を出発する時刻が「８：０５」、目的地到着時刻が「９：０５」、所要時間が「所要時間 １時間０分」と表示される。候補経路を選択すると、経路の詳細情報を見ることができる。また、「次へ」をクリックすると、５番目以降の候補経路を表示でき、「所要時間でソート」を選択すると、候補経路のソート順序が変更され、出発地から目的地までの所要時間の短い順に候補経路が表示される。「条件を変更して再探索」を選択すると、条件設定画面に切り替わり、経路探索条件、例えば、最早出発時刻や最遅到着時刻などの時刻条件や、その他の条件を変更して経路探索サーバ３０に探索要求することができる。
【００８６】
図６は、端末装置２０において表示画面２５１に表示される出発時刻・到着時刻指定経路探索モードの経路探索結果を示す出力画面の一例を示す画面構成図である。図６に示す例は、図５と同様に、出発地として「自宅」が、目的地として「ＹＹＹランド」が設定され、最早出発時刻が「８；００」、最遅到着時刻が「１１：００」と設定された場合の候補経路を表示した例を示している。図６においては、候補経路が経路の所要時間の順にソートして表示されたものである。
【００８７】
第１経路は、出発地を出発する時刻が「８：２０」、目的地到着時刻が「１０：１５」、所要時間が「所要時間 ５５分」と表示される。候補経路を選択すると、経路の詳細情報を見ることができる。また、「次へ」をクリックすると、５番目以降の候補経路を表示でき、「出発時間でソート」を選択すると、候補経路のソート順序が変更され、出発地を出発する時刻の早い順に候補経路が表示される（図５の画面表示に戻る）。「条件を変更して再探索」を選択すると、条件設定画面に切り替わり、経路探索条件、例えば、最早出発時刻や最遅到着時刻などの時刻条件や、その他の条件を変更して経路探索サーバ３０に探索要求することができる。
【００８８】
利用者はこの表示結果から、所望の経路を選択することができる。所要時間は余分にかかるとしても出発地時刻を遅くしたい場合は、所望の出発時刻の経路、例えば、第４経路以降の経路を選択することができる。途中立ち寄りたい中継地点がある場合には、経路探索条件に経由地を指定し、経由地における必要時間を考慮して目的地への到着時刻範囲を指定すればよい。
【００８９】
候補経路の出力順を、図５、図６に示すように探索結果の表示画面において切り替えることにより、様々なソート結果を閲覧できる。一覧に表示された経路情報は、選択することによって詳細な経路情報画面を表示するようにしてもよい。例えば、図５や図６において表示画面２５１に表示する各経路にそれぞれ詳細な経路情報にリンクするためのリンク情報を関連付けておき、特定の候補経路がカーソルなどの選択手段で選択されると、その候補経路の詳細情報が表示されるようにすると便利である。
【００９０】
候補経路の詳細情報を表示した後、地図表示キー（図示せず）が操作されたら該当する候補経路を含む地図表示を行う。詳細情報とは、経路が交通機関を利用した経路区間を含む場合、出発駅や乗車する電車の出発時刻、乗換え駅や乗換える電車の出発時刻、目的地の最寄り駅への到着時刻など、通常の徒歩と交通機関を用いた経路の探索結果と同様であり、徒歩経路を確認する場合には該当エリア地図を表示させることもできる。
【００９１】
次に、経路探索サーバ３０における経路探索の概念について説明する。経路探索用ネットワークデータベース３５には、徒歩や自動車による移動経路を探索するための道路ネットワークデータと公共交通機関を利用した移動経路を探索するための交通ネットワークデータが蓄積されている。経路探索手段３９は、この経路探索用ネットワークデータベース３５を参照して、徒歩や自動車による経路あるいは徒歩と交通機関を併用した経路を探索する。
【００９２】
道路ネットワークデータは、以下のように構成されている。例えば、道路が図７に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００９３】
すなわち、図７において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９４】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図７において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００９５】
図７ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００９６】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図８に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図８において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図８では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９７】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図８に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００９８】
図８に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。
【００９９】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【０１００】
例えば、図８において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【０１０１】
このようなネットワークデータを利用して経路探索サーバ３０は経路探索条件に従って、出発地から目的地までの複数の候補経路を探索し、その結果を案内経路データとして端末装置２０に送信する。経路探索条件に出発地の出発時刻が指定されている場合には目的地への到着時刻が、また、目的地への到着時刻が指定されている場合には、目的地に指定時刻に到着するための出発地の出発時刻が案内経路データに含まれ、端末装置２０はこれらを表示手段２５に経路の詳細とともに表示することができる。案内経路に乗換え駅が含まれる場合には、当該乗換え駅で乗り換えるべき電車やその出発時刻も同様にして表示することができる。
【０１０２】
次に、本発明の実施例にかかる経路探索サーバ３０における経路探索の動作手順を、図９に示すフローチャートに基づいて説明する。端末装置２０において図示していないモード設定手段により出発時刻・到着時刻指定経路探索モードが設定され、図４に示す経路探索条件の入力画面に従って、所要の経路探索条件が設定されているものとする。
【０１０３】
先ず、経路探索サーバ３０は、ステップＳ１の処理で端末装置２０から経路探索条件、経路探索要求を受信する。ステップＳ２の処理で経路探索手段３９は、最早出発時刻を出発時刻として、経路探索用ネットワークデータベース３５を参照して、出発地から目的地までの最適経路を探索し、目的地への到着予想時刻を算出する。
【０１０４】
ステップＳ３の処理で、到着時刻判別手段３６は、経路探索手段３９が探索した最適経路の目的地への到着時刻が到着時刻条件を満足するか否か、すなわち、最適経路の目的地到着時刻が指定された最遅到着時刻よりも前（早い）か否かを判別する。到着時刻条件を満足する経路であると、ステップＳ４の処理に進み、経路探索結果（探索された最適経路）を案内経路ソート手段３３の探索結果リストに格納し、ステップＳ５の処理に進む。
【０１０５】
ステップＳ５の処理では、時刻条件シフト手段３７は、出発時刻を所定の時間シフトし、ステップＳ２の処理に戻り、経路探索手段３９による経路探索を繰り返す。探索された経路が到着時刻条件を満足しなくなったら経路探索は終了し、ステップＳ６の処理に進む。ステップＳ６の処理では、案内経路ソート手段３３は探索結果リストに格納された候補経路を指定された順にソートし、ステップＳ７の処理で、案内経路データ編集手段３２により端末装置２０への送信データに編集された経路情報が端末装置２０に送信される。
【０１０６】
ここで、経路探索条件に従って経路探索を行った結果、候補経路情報が１つも得られなかった場合には、利用者（端末装置２０）にその旨を表示すると共に経路探索条件の再入力を促してもよいし、最早出発時刻または最遅到着時刻の少なくともいずれか一方をその範囲外の時刻にシフトして再探索した結果をユーザに提示してもよい。
【０１０７】
以上、詳細に説明したように本発明によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。従って、利用者はその候補経路の中から自身の要求にあった経路を容易に選択することができるようになる。
【図面の簡単な説明】
【０１０８】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】端末装置として用いられる携帯電話の外観を示す図である。
【図４】到着時刻範囲指定経路探索モードにおける経路探索条件の入力画面の一例を示す画面構成図である。
【図５】端末装置に表示される到着時刻範囲の経路探索結果を示す出力画面の一例を示す画面構成図である。
【図６】端末装置に表示される到着時刻範囲の経路探索結果を示す出力画面の一例を示す画面構成図である。
【図７】道路ネットワークのデータの概念を示す模式図である。
【図８】交通ネットワークのデータの概念を示す模式図である。
【図９】本発明の出発時刻・到着時刻指定経路探索モードにおける経路探索の処理手順を示すフローチャートである。
【符号の説明】
【０１０９】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・探索要求手段
２４・・・・案内経路データ記憶手段
２５・・・・表示手段
２６・・・・操作入力手段
２６１・・・第１入力手段
２６２・・・第２入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・案内経路データ編集手段
３３・・・・案内経路ソート手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・到着時刻判別手段
３７・・・・時刻条件シフト手段
３８・・・・探索要求記憶手段
３９・・・・経路探索手段
【技術分野】
【０００１】
本発明は、徒歩や自動車あるいは公共交通機関を利用して、任意の出発地から目的地に至る候補経路を探索して案内するナビゲーションシステムに関するものであり、特に、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、出発地を出発する最早出発時刻および目的地に到着する最遅到着時刻を指定して経路探索できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
徒歩経路に加えて交通機関を用いた経路を探索するナビゲーションシステムは、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に開示されている。この特許文献２に開示されたナビゲーションシステムは、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法を用いるものである。
【００１０】
そして、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するように構成されている。
【００１１】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのまま、あるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１２】
ナビゲーションシステムを用いて経路探索、経路の案内を受ける場合、出発地を出発する時刻を指定して目的地までの最適経路や複数の候補経路を探索するケースがある。また、目的地への到着時刻を設定し、出発地から目的地までの経路のうち、指定した時刻に目的地に到達できる最適経路や候補経路を探索するケースがある。後者においては、指定した時刻に目的地に到達するために出発地を何時に出発すればよいかがわかる。
【００１３】
また、出発地の出発時刻範囲または目的地への到着時刻範囲を指定して経路探索ができると、所望の時刻範囲を満足する最適経路や、候補経路の探索ができ、時刻条件を順次変えながら経路探索を繰り返す必要がなく、便利である。本願の出願人はこのような目的を達成する発明として、既に特願２００７−０６９４２６号の発明および特願２００７−１３０６５３号の発明についての特許出願を行っている。
【００１４】
この特願２００７−０６９４２６号（以下、「先願１」という。）に開示された発明は、目的地への到着時刻の範囲を含む経路探索条件を入力する操作入力手段と、到着時刻の範囲を判別する時刻範囲判別手段と、時刻条件をシフトする時刻条件シフト手段と、案内経路ソート手段と、を備え、時刻条件シフト手段は、予め定められた条件に従って到着時刻範囲内において、時刻条件を順次異なる時刻条件に変更し、経路探索手段は時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索して候補経路として案内経路ソート手段に記憶し、該案内経路ソート手段は、候補経路を経路探索条件により指定された順にソートして出力するように構成されたものである。
【００１５】
また、特願２００７−１３０６５３号（以下、「先願２」という。）に開示された発明は、出発地からの出発時刻の範囲を含む経路探索条件を入力する操作入力手段と、出発時刻の範囲を判別する時刻範囲判別手段と、時刻条件をシフトする時刻条件シフト手段と、案内経路ソート手段と、を備え、時刻条件シフト手段は、予め定められた条件に従って出発時刻範囲内において、時刻条件を順次異なる時刻条件に変更し、経路探索手段は時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索して候補経路として案内経路ソート手段に記憶し、該案内経路ソート手段は、候補経路を経路探索条件により指定された順にソートして出力するように構成されたものである。
【００１６】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図３、図３）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上記先願１や先願２の発明によれば、出発時刻に所望の時間幅を設定し、または、到着時刻に所望の時間幅を設定して、その時刻条件を満足する最適経路や候補経路を探索することができる。ところで、ナビゲーションシステムの利用者には、出発地を出発する時刻としておよその所望時刻を考慮し、同時に目的地に到着する時刻としておよその所望時刻を考慮して、両方の時刻条件を満足する最適経路や候補経路の有無を知りたいという要求もある。しかしながら、上記特許文献２や先願１あるいは先願２の発明においては、このような経路探索ができないという問題点があった。
【００１８】
従って、上記のような経路の有無を知るためには、ナビゲーションシステムの利用者は出発時刻と到着時刻を種々組み合わせて何度も経路探索を繰り返し、試行錯誤的に経路の有無を判断する手順を採る必要があり、手間がかかるという問題点があった。
【００１９】
上記先願１や先願２によれば、ユーザは大よその出発したい時刻または到着したい時刻を、時間幅を持った時刻入力を可能にすることによって経路探索を可能にするものである。しかしながら、出発時刻幅または到着時刻幅のいずれか一方のみを考慮した経路探索であるため、出力される結果について例えば出発時刻が思いのほか早くなってしまったり、到着時刻が思いのほか遅くなってしまったりということが起きていた。
【００２０】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、出発地を出発する最早出発時刻および目的地に到着する最遅到着時刻を指定して経路探索できるようになせば上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００２１】
すなわち、本発明は、上記の問題点を解消することを課題とし、出発地の出発時刻と目的地への到着時刻を設定し、その時刻条件を満足する最適経路や候補経路を探索することができるナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２２】
前記課題を解決するために、本願の請求項１にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする。
【００２３】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００２４】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする。
【００２５】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする。
【００２６】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００２７】
本願の請求項６にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００２８】
また、本願の請求項７にかかる発明は、
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、前記端末装置から受信した経路探索条件に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索サーバにおいて、
前記端末装置から送信される経路探索要求は、出発地からの最早出発時刻および目的地への最遅到着時刻を含み、
前記経路探索サーバは、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする。
【００２９】
本願の請求項８にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記端末装置から送信される経路探索要求は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００３０】
本願の請求項９にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする。
【００３１】
本願の請求項１０にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする。
【００３２】
本願の請求項１１にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００３３】
本願の請求項１２にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００３４】
また、本願の請求項１３にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段が、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更するステップと、前記経路探索手段が、前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し、到着予想時刻を算出するステップと、前記到着時刻判別手段が、前記到着予想時刻が前記最遅到着時刻より早いか否かを判別するステップと、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶するステップと、該案内経路ソート手段が、前記候補経路を前記経路探索条件により指定された順にソートして出力するステップと、を有することを特徴とする。
【００３５】
本願の請求項１４にかかる発明は、請求項１３にかかる経路探索方法において、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【００３６】
本願の請求項１５にかかる発明は、請求項１３にかかる経路探索方法において、前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する処理を含むことを特徴とする。
【００３７】
本願の請求項１６にかかる発明は、請求項１３にかかる経路探索方法において、前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する処理を含むことを特徴とする。
【００３８】
本願の請求項１７にかかる発明は、請求項１３にかかる経路探索方法において、前記到着時刻判別手段が、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする。
【００３９】
本願の請求項１８にかかる発明は、請求項１３にかかる経路探索方法において、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする。
【００４０】
また、本願の請求項１９にかかる発明は、
時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、出発地と目的地を含む経路探索条件を入力する操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により、出発地からの最早出発時刻および目的地への最遅到着時刻を入力するようになしたことを特徴とする。
【００４１】
本願の・請求項２０にかかる発明は、請求項１９にかかる端末装置において、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、到着時刻範囲を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする。
【発明の効果】
【００４２】
請求項１にかかる発明においては、ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する。
【００４３】
このような構成によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。従って、利用者はその候補経路の中から自身の要求にあった経路を容易に選択することができるようになる。
【００４４】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含む。
【００４５】
このような構成によれば、経路探索条件として交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を指定して、目的地への到着時刻の範囲を設定した経路探索が行えるようになる。
【００４６】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する。
【００４７】
このような構成によれば、経路探索手段は、時刻条件シフト手段が、指定された最早出発時刻から所定の時間間隔で変更した到着時刻に基づいて、最遅到着時刻より前に目的地に到着できる候補経路を探索することができるようになる。
【００４８】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する。
【００４９】
このような構成によれば、経路探索手段は、時刻条件シフト手段が、指定された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして、最遅到着時刻より前に目的地に到着できる候補経路を探索することができるようになる。また、出発地の最寄り駅を出発する便数が少ない場合には、経路探索手段が候補経路を探索する回数を少なくすることができるようになる。
【００５０】
また、請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了する。
【００５１】
このような構成によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。
【００５２】
また、請求項６にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加される。
【００５３】
このような構成によれば、利用者はこの表示結果から、所望の条件に合致する経路を容易に選択することができるようになる。また、候補経路を選択することにより該当する候補経路の詳細情報を容易に知ることができるようになる。
【００５４】
また、請求項７ないし請求項１２にかかる発明においては、それぞれ請求項１ないし請求項６にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになり、請求項１３ないし請求項１８にかかる発明においては、それぞれ請求項１ないし請求項６にかかるナビゲーションシステムを実現するための経路探索方法を提供することができるようになる。また、請求項１９、請求項２０にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００５５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００５６】
図１は、本発明にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、音楽や各種画像などのコンテンツその他の情報を提供する各種の情報配信サーバ５１などを備えて構成されている。
【００５７】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００５８】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。
【００５９】
図１に示す経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５を備え、端末装置２０から経路探索要求があると、探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た案内経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。
【００６０】
一方、端末装置２０は、経路探索サーバ３０に出発地の出発時刻と目的地への到着時刻を経路探索条件として経路探索を要求する出発時刻・到着時刻指定経路探索モードを設定することができる。この出発時刻・到着時刻指定経路探索モードが設定されない場合は、通常の経路探索の要求になる。出発時刻・到着時刻指定経路探索モードにおける出発時刻は、出発地を出発する最早の時刻を設定し、到着時刻は目的地に到着する最遅の時刻を設定する。すなわちこの時刻条件は、利用者が出発時刻として許容しようとする最も早い時刻と到着時刻として許容しようとする最も遅い時刻を設定するものである。
【００６１】
経路探索サーバ３０は、端末装置２０から、出発時刻・到着時刻指定経路探索モードを設定した経路探索要求があると、指定された最早出発時刻から所定の時間間隔で出発時刻をシフトしながら候補経路を探索する。候補経路が探索されると、その目的地到着時刻を算出し、設定された最遅到着時刻より前に到着できる経路であるか否かを判別する。設定された最遅到着時刻より前に到着できる経路が得られない場合には経路探索を終了し、各経路探索で得られた候補経路を指定された条件でソートして出力する。この時の経路探索は一般的なナビゲーションシステムで行われる出発時刻指定の経路探索の手法で行うことができる。
【００６２】
このような経路探索を行えば、所望の最早出発時刻以降に出発し、最遅到着時刻前に目的地に到着するための候補経路を得ることができ、端末装置２０の利用者は案内された複数の候補経路のうちから好みの経路を選択することができるようになる。なお、到着時刻条件を満足する候補経路が提示されない場合には、最早出発時刻または最遅到着時刻の何れか一方または両方を再設定するよう促す案内を行えば、ナビゲーションシステムの利用者は容易に再探索の要求を行うことができるようになる。
【００６３】
以下、具体例に基づいて本発明を説明するが、その前に本発明にかかるナビゲーションシステム１０の詳細な構成を説明する。図２は、図１のナビゲーションシステム１０の詳細な構成を示す図である。端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、探索要求手段２３、案内経路データ記憶手段２４、表示手段２５、操作入力手段２６を備えて構成される。
【００６４】
操作入力手段２６は、出発地、目的地、その他の経路探索条件を入力する第１入力手段２６１と、最早出発時刻（出発地を出発する所望の最も早い時刻）および最遅到着時刻（目的地に到着する所望の最も遅い時刻）を入力する第２入力手段２６２を含んでいる。第１入力手段２６１、第２入力手段２６２は数値キーを用いることができるが、後述する条件入力画面に設けたプルダウンメニューにより表示される数値を用いることもできる。第１入力手段２６１により入力されるその他の経路探索条件とは、例えば、交通機関を利用した経路の運賃、乗り換え回数、所要時間などである。
【００６５】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、案内経路データ編集手段３２、案内経路ソート手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、到着時刻判別手段３６、時刻条件シフト手段３７、探索要求記憶手段３８、経路探索手段３９を備えて構成される。時刻条件シフト手段３７は、出発時刻・到着時刻指定経路探索モードの経路探索要求が端末装置２０から送信された場合に、経路探索条件として指定された最早出発時刻から、所定の時間間隔で出発地の出発時刻を順次シフトする。経路探索手段３９はシフトされた出発時刻を条件として出発地から目的地までの候補経路（最適経路）を探索し、目的地への到着予想時刻を算出する。
【００６６】
到着時刻判別手段３６は、時刻条件シフト手段３７が順次シフトした時刻条件のそれぞれを用いて経路探索手段３９が探索した候補経路（案内経路候補）における到着時刻が到着時刻条件を満足するかを判別する。到着時刻条件を満足する候補経路とは、経路探索条件として指定された最遅到着時刻より前に目的地に到着できる経路である。候補経路の到着時刻が最遅到着時刻より前であれば、その経路は端末装置２０に回答する候補経路（案内経路）とされる。端末装置２０に候補経路（案内経路）を送信する際、案内経路ソート手段３３は、出発時刻をシフトして経路探索した結果として得られる候補経路であって、到着時刻判別手段が到着時刻条件を満足すると判別した候補経路を一時記憶し、指定された条件に応じてソートする。ソートされた候補経路は端末装置２０に送信され、端末装置２０の表示手段２５に表示される。
【００６７】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００６８】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２６は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの入力機能としても用いられる。表示手段２５は液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２５はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。
【００６９】
経路探索サーバ３０から端末装置２０に送信される最適経路や候補経路などの案内経路データは地図データとともに案内経路データ記憶手段２４に記憶され、案内経路データ記憶手段２４に記憶された候補経路などの案内データや地図データは、必要に応じて読み出され、表示手段２５に表示される。
【００７０】
図３は、端末装置２０の外観の一例を示す図であり、図３に示す端末装置２０は携帯電話を端末装置としたものである。端末装置２０は、液晶表示ユニットなどからなる表示手段２５、テンキーやダイヤル、ボタンなどを有する操作入力手段２６を備えている。経路探索サーバ３０から送信された地図データや案内経路データは案内経路データ記憶手段２４に記憶され、必要に応じて案内経路データ記憶手段２４から読み出され、表示手段２５の表示画面２５１に表示される。
【００７１】
図４は、表示画面２５１に表示される経路探索条件入力画面の一例を示す図である。端末装置２０は、操作入力手段２６により入力された条件や操作に基づいて経路探索要求を経路探索サーバ３０に送信する。経路探索サーバ３０に経路探索要求する場合には、図４に示すように表示手段２５に表示されたメニューから、あるいは、操作入力手段２６から所望の出発地、目的地を設定して経路探索サーバ３０に送信する。
【００７２】
図４は、端末装置２０が到着時刻範囲指定経路探索モードに設定された場合に表示される経路探索条件入力画面の例を示している。この経路探索条件入力画面には、出発地入力欄２５２、目的地入力欄２５３、最早出発時刻入力欄２５４、最遅到着時刻入力欄２５５、出力順（ソート条件）入力欄２５６、探索開始ボタン２５７が設けられている。
【００７３】
出発地と目的地の設定は、出発地入力欄２５２、目的地入力欄２５３に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。また、出発地の入力には、ＧＰＳ受信手段２２で測位した端末装置２０の現在位置を用いるようにすることもできる。
【００７４】
また、プルダウンボタンを操作して、これまでに端末装置２０に登録した経路探索履歴や登録地点を呼び出して設定することもできる。最早出発時刻入力欄２５４には出発地を出発する所望の最も早い時刻「ＸＸ時ＹＹ分」を入力し、次いで、最遅到着時刻入力欄２５５に、目的地へ到着する所望の最も遅い時刻「ＷＷ時ＺＺ分」を入力する。必要な条件設定を終え、探索開始ボタン２５７を操作すると、経路探索要求が端末装置２０から経路探索サーバ３０に送信される。
【００７５】
出力順は、その他の経路探索条件として交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れかが指定された場合には、指定された条件に適合するように決定することができる。例えば、経路探索条件として乗り換え回数が指定された場合には、複数の候補経路を乗り換え回数の少ない順にソートする。複数の条件が設定されている場合には出力順（ソート条件）入力欄２５６で出力順を指定することもできる。
【００７６】
経路探索サーバ３０は、端末装置２０から経路探索要求があると、これを探索要求記憶手段３８に一時記憶する。そして経路探索手段３９は、探索要求記憶手段３８に記憶した経路探索要求に従って経路探索用ネットワークデータベース３５を参照して出発地から目的地までの複数の候補経路を探索する。経路探索要求が通常の経路探索の要求である場合、経路探索の結果得られた案内経路のデータを地図データベース３４から読み出した地図データとともに端末装置２０に送信する。この経路探索の方法は通常のナビゲーションシステムにおける経路探索サーバと同様の方法である。
【００７７】
一方、経路探索要求が出発時刻・到着時刻指定経路探索モードの経路探索の要求である場合、時刻条件シフト手段３７は経路探索条件に指定された最早出発時刻に基づいて、指定された最早出発時刻を経路探索手段３９に送り、以後は、出発時刻を所定の時間間隔（例えば、５分間隔）で順次シフトして経路探索手段３９に送る。経路探索手段３９は、時刻条件シフト手段３７から出発時刻を受取るごとに出発地から目的地までの最適経路を探索する。ここで探索する経路は所要時間の最も短い最適経路であってもよい。ここでは、最適経路を含めて候補経路ということとする。
【００７８】
なお、時刻条件シフト手段３７による出発時刻のシフトは、前述のように所定の時間間隔で行ってもよく、また、交通機関を用いた経路区間がある場合には、入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更するように構成することもできる。このように構成すれば、出発地の最寄り駅を出発する便数が少ない場合には、経路探索手段が候補経路を探索する回数を少なくすることができるようになる。
【００７９】
到着時刻判別手段３６は、経路探索手段３９が探索した最適経路における目的地への到着予想時刻が到着時刻の条件、すなわち、指定された最遅到着時刻を満足するか否かを判別する。探索した経路の目的地到着時刻が指定された最遅到着時刻より前であれば、到着時刻の条件を満足するので、到着時刻判別手段３６は、探索された経路を候補経路とする。到着時刻条件を満足する経路の情報は、案内経路ソート手段３３に一時記憶される。
【００８０】
時刻条件シフト手段３７による出発時刻のシフト処理、経路探索手段３９による最適経路探索処理は、経路探索手段３９が時刻条件シフト手段３７から得た出発時刻による探索した候補経路について、到着時刻判別手段３６において到着時刻条件を満足しない、すなわち、経路の目的地到着時刻が、指定された最遅到着時刻よりも後の時刻になるまで行われる。
【００８１】
案内経路ソート手段３３には上記の経路探索によって得られた複数の候補経路が記憶されている。端末装置２０への候補経路（探索結果）の出力は、端末装置２０が設定したソート順に従ってソートして行われる。例えば、図４の条件入力画面に示したように出力順として「所要時間の短い順」が指定されている場合、案内経路ソート手段３３は、一時記憶している複数の候補経路を出発地から目的地までの所要時間が短い順にソートする。
【００８２】
案内経路ソート手段３３がソートした候補経路のデータは案内経路データ編集手段３２により端末装置２０に送信するためのデータに編集され通信手段３１を介して端末装置２０に送信される。端末装置２０は経路探索サーバ３０から受信した案内経路のデータ（ソート済の候補経路のデータ）を案内経路データ記憶手段２４に記憶し、必要により表示手段２５に表示する。
【００８３】
最早出発時刻に基づいて探索した経路の目的地到着時刻が最遅到着時刻より遅い経路であった場合、最早出発時刻の条件、最遅到着時刻の条件を同時に満足する候補経路が存在しないことを意味する。すなわち、最早出発時刻〜最遅到着時刻までを所要時間として出発地から目的地まで移動できる経路が存在しないことを意味し、出発時刻・到着時刻の設定に無理があったことになる。その場合、経路探索サーバ３０は、時刻条件を再設定するよう促すメッセージを回答する
【００８４】
図５は、端末装置２０において表示画面２５１に表示される出発時刻・到着時刻指定経路探索モードの経路探索結果を示す出力画面の一例を示す画面構成図である。図５に示す例は、出発地として「自宅」が、目的地として「ＹＹＹランド」が設定され、最早出発時刻が「８；００」、最遅到着時刻が「１１：００」と設定された場合の候補経路を表示した例を示している。候補経路は出発時刻順にソートして表示され、各候補経路にはその所要時間が表示される。
【００８５】
第１経路は、出発地を出発する時刻が「８：０５」、目的地到着時刻が「９：０５」、所要時間が「所要時間 １時間０分」と表示される。候補経路を選択すると、経路の詳細情報を見ることができる。また、「次へ」をクリックすると、５番目以降の候補経路を表示でき、「所要時間でソート」を選択すると、候補経路のソート順序が変更され、出発地から目的地までの所要時間の短い順に候補経路が表示される。「条件を変更して再探索」を選択すると、条件設定画面に切り替わり、経路探索条件、例えば、最早出発時刻や最遅到着時刻などの時刻条件や、その他の条件を変更して経路探索サーバ３０に探索要求することができる。
【００８６】
図６は、端末装置２０において表示画面２５１に表示される出発時刻・到着時刻指定経路探索モードの経路探索結果を示す出力画面の一例を示す画面構成図である。図６に示す例は、図５と同様に、出発地として「自宅」が、目的地として「ＹＹＹランド」が設定され、最早出発時刻が「８；００」、最遅到着時刻が「１１：００」と設定された場合の候補経路を表示した例を示している。図６においては、候補経路が経路の所要時間の順にソートして表示されたものである。
【００８７】
第１経路は、出発地を出発する時刻が「８：２０」、目的地到着時刻が「１０：１５」、所要時間が「所要時間 ５５分」と表示される。候補経路を選択すると、経路の詳細情報を見ることができる。また、「次へ」をクリックすると、５番目以降の候補経路を表示でき、「出発時間でソート」を選択すると、候補経路のソート順序が変更され、出発地を出発する時刻の早い順に候補経路が表示される（図５の画面表示に戻る）。「条件を変更して再探索」を選択すると、条件設定画面に切り替わり、経路探索条件、例えば、最早出発時刻や最遅到着時刻などの時刻条件や、その他の条件を変更して経路探索サーバ３０に探索要求することができる。
【００８８】
利用者はこの表示結果から、所望の経路を選択することができる。所要時間は余分にかかるとしても出発地時刻を遅くしたい場合は、所望の出発時刻の経路、例えば、第４経路以降の経路を選択することができる。途中立ち寄りたい中継地点がある場合には、経路探索条件に経由地を指定し、経由地における必要時間を考慮して目的地への到着時刻範囲を指定すればよい。
【００８９】
候補経路の出力順を、図５、図６に示すように探索結果の表示画面において切り替えることにより、様々なソート結果を閲覧できる。一覧に表示された経路情報は、選択することによって詳細な経路情報画面を表示するようにしてもよい。例えば、図５や図６において表示画面２５１に表示する各経路にそれぞれ詳細な経路情報にリンクするためのリンク情報を関連付けておき、特定の候補経路がカーソルなどの選択手段で選択されると、その候補経路の詳細情報が表示されるようにすると便利である。
【００９０】
候補経路の詳細情報を表示した後、地図表示キー（図示せず）が操作されたら該当する候補経路を含む地図表示を行う。詳細情報とは、経路が交通機関を利用した経路区間を含む場合、出発駅や乗車する電車の出発時刻、乗換え駅や乗換える電車の出発時刻、目的地の最寄り駅への到着時刻など、通常の徒歩と交通機関を用いた経路の探索結果と同様であり、徒歩経路を確認する場合には該当エリア地図を表示させることもできる。
【００９１】
次に、経路探索サーバ３０における経路探索の概念について説明する。経路探索用ネットワークデータベース３５には、徒歩や自動車による移動経路を探索するための道路ネットワークデータと公共交通機関を利用した移動経路を探索するための交通ネットワークデータが蓄積されている。経路探索手段３９は、この経路探索用ネットワークデータベース３５を参照して、徒歩や自動車による経路あるいは徒歩と交通機関を併用した経路を探索する。
【００９２】
道路ネットワークデータは、以下のように構成されている。例えば、道路が図７に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００９３】
すなわち、図７において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９４】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図７において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００９５】
図７ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００９６】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図８に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図８において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図８では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９７】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図８に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００９８】
図８に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。
【００９９】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【０１００】
例えば、図８において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【０１０１】
このようなネットワークデータを利用して経路探索サーバ３０は経路探索条件に従って、出発地から目的地までの複数の候補経路を探索し、その結果を案内経路データとして端末装置２０に送信する。経路探索条件に出発地の出発時刻が指定されている場合には目的地への到着時刻が、また、目的地への到着時刻が指定されている場合には、目的地に指定時刻に到着するための出発地の出発時刻が案内経路データに含まれ、端末装置２０はこれらを表示手段２５に経路の詳細とともに表示することができる。案内経路に乗換え駅が含まれる場合には、当該乗換え駅で乗り換えるべき電車やその出発時刻も同様にして表示することができる。
【０１０２】
次に、本発明の実施例にかかる経路探索サーバ３０における経路探索の動作手順を、図９に示すフローチャートに基づいて説明する。端末装置２０において図示していないモード設定手段により出発時刻・到着時刻指定経路探索モードが設定され、図４に示す経路探索条件の入力画面に従って、所要の経路探索条件が設定されているものとする。
【０１０３】
先ず、経路探索サーバ３０は、ステップＳ１の処理で端末装置２０から経路探索条件、経路探索要求を受信する。ステップＳ２の処理で経路探索手段３９は、最早出発時刻を出発時刻として、経路探索用ネットワークデータベース３５を参照して、出発地から目的地までの最適経路を探索し、目的地への到着予想時刻を算出する。
【０１０４】
ステップＳ３の処理で、到着時刻判別手段３６は、経路探索手段３９が探索した最適経路の目的地への到着時刻が到着時刻条件を満足するか否か、すなわち、最適経路の目的地到着時刻が指定された最遅到着時刻よりも前（早い）か否かを判別する。到着時刻条件を満足する経路であると、ステップＳ４の処理に進み、経路探索結果（探索された最適経路）を案内経路ソート手段３３の探索結果リストに格納し、ステップＳ５の処理に進む。
【０１０５】
ステップＳ５の処理では、時刻条件シフト手段３７は、出発時刻を所定の時間シフトし、ステップＳ２の処理に戻り、経路探索手段３９による経路探索を繰り返す。探索された経路が到着時刻条件を満足しなくなったら経路探索は終了し、ステップＳ６の処理に進む。ステップＳ６の処理では、案内経路ソート手段３３は探索結果リストに格納された候補経路を指定された順にソートし、ステップＳ７の処理で、案内経路データ編集手段３２により端末装置２０への送信データに編集された経路情報が端末装置２０に送信される。
【０１０６】
ここで、経路探索条件に従って経路探索を行った結果、候補経路情報が１つも得られなかった場合には、利用者（端末装置２０）にその旨を表示すると共に経路探索条件の再入力を促してもよいし、最早出発時刻または最遅到着時刻の少なくともいずれか一方をその範囲外の時刻にシフトして再探索した結果をユーザに提示してもよい。
【０１０７】
以上、詳細に説明したように本発明によれば、出発地を出発する所望の最も早い最早出発時刻と、目的地へ到着する所望の最も遅い最遅到着時刻を指定するだけで、指定した出発時刻と到着時刻を満足する複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになる。従って、利用者はその候補経路の中から自身の要求にあった経路を容易に選択することができるようになる。
【図面の簡単な説明】
【０１０８】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】端末装置として用いられる携帯電話の外観を示す図である。
【図４】到着時刻範囲指定経路探索モードにおける経路探索条件の入力画面の一例を示す画面構成図である。
【図５】端末装置に表示される到着時刻範囲の経路探索結果を示す出力画面の一例を示す画面構成図である。
【図６】端末装置に表示される到着時刻範囲の経路探索結果を示す出力画面の一例を示す画面構成図である。
【図７】道路ネットワークのデータの概念を示す模式図である。
【図８】交通ネットワークのデータの概念を示す模式図である。
【図９】本発明の出発時刻・到着時刻指定経路探索モードにおける経路探索の処理手順を示すフローチャートである。
【符号の説明】
【０１０９】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・探索要求手段
２４・・・・案内経路データ記憶手段
２５・・・・表示手段
２６・・・・操作入力手段
２６１・・・第１入力手段
２６２・・・第２入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・案内経路データ編集手段
３３・・・・案内経路ソート手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・到着時刻判別手段
３７・・・・時刻条件シフト手段
３８・・・・探索要求記憶手段
３９・・・・経路探索手段
【特許請求の範囲】
【請求項１】
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とするナビゲーションシステム。
【請求項２】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項７】
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、前記端末装置から受信した経路探索条件に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索サーバにおいて、
前記端末装置から送信される経路探索要求は、出発地からの最早出発時刻および目的地への最遅到着時刻を含み、
前記経路探索サーバは、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする経路探索サーバ。
【請求項８】
前記端末装置から送信される経路探索要求は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１０】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１１】
前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１２】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項７に記載の経路探索サーバ。
【請求項１３】
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段が、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更するステップと、前記経路探索手段が、前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し、到着予想時刻を算出するステップと、前記到着時刻判別手段が、前記到着予想時刻が前記最遅到着時刻より早いか否かを判別するステップと、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶するステップと、該案内経路ソート手段が、前記候補経路を前記経路探索条件により指定された順にソートして出力するステップと、を有することを特徴とする経路探索方法。
【請求項１４】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する処理を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１６】
前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する処理を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１７】
前記到着時刻判別手段が、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項１３に記載の経路探索方法。
【請求項１８】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項１３に記載の経路探索方法。
【請求項１９】
時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、出発地と目的地を含む経路探索条件を入力する操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により、出発地からの最早出発時刻および目的地への最遅到着時刻を入力するようになしたことを特徴とする端末装置。
【請求項２０】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、到着時刻範囲を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１９に記載の端末装置。
【請求項１】
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とするナビゲーションシステム。
【請求項２】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項７】
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、前記端末装置から受信した経路探索条件に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索サーバにおいて、
前記端末装置から送信される経路探索要求は、出発地からの最早出発時刻および目的地への最遅到着時刻を含み、
前記経路探索サーバは、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力することを特徴とする経路探索サーバ。
【請求項８】
前記端末装置から送信される経路探索要求は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１０】
前記時刻条件シフト手段は、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１１】
前記到着時刻判別手段は、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１２】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項７に記載の経路探索サーバ。
【請求項１３】
出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する操作入力手段と、時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段が、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更するステップと、前記経路探索手段が、前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し、到着予想時刻を算出するステップと、前記到着時刻判別手段が、前記到着予想時刻が前記最遅到着時刻より早いか否かを判別するステップと、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶するステップと、該案内経路ソート手段が、前記候補経路を前記経路探索条件により指定された順にソートして出力するステップと、を有することを特徴とする経路探索方法。
【請求項１４】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、出発地からの最早出発時刻および目的地への最遅到着時刻を含む経路探索条件を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻から所定の時間間隔で出発時刻をシフトして時刻条件を変更する処理を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１６】
前記時刻条件シフト手段が時刻条件を変更するステップは、前記第２入力手段により入力された最早出発時刻に前記出発地の最寄り駅から出発する移動手段の便を順次シフトして時刻条件を変更する処理を含むことを特徴とする請求項１３に記載の経路探索方法。
【請求項１７】
前記到着時刻判別手段が、変更した時刻条件に基づいて最適経路から算出される到着予想時刻が最遅到着時刻より遅い時刻であると判別すると経路探索を終了することを特徴とする請求項１３に記載の経路探索方法。
【請求項１８】
前記案内経路ソート手段が出力する複数の案内経路のデータは、少なくとも出発時刻と前記その他の経路探索条件のうち指定されたソート条件でソートされた一覧データであり、それぞれの案内経路には詳細経路表示へのリンク情報が付加されることを特徴とする請求項１３に記載の経路探索方法。
【請求項１９】
時刻条件をシフトする時刻条件シフト手段と、到着時刻が最遅到着時刻より早いか否かを判別する到着時刻判別手段と、案内経路ソート手段と、を備え、
前記時刻条件シフト手段は、予め定められた条件に従って、前記時刻条件を順次異なる時刻条件に変更し、前記経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索し到着予想時刻を算出し、前記到着時刻判別手段は到着予想時刻が最遅到着時刻より早いか否かを判別し、最遅到着時刻より早いと判別された経路を候補経路として前記案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、出発地と目的地を含む経路探索条件を入力する操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により、出発地からの最早出発時刻および目的地への最遅到着時刻を入力するようになしたことを特徴とする端末装置。
【請求項２０】
前記操作入力手段は、出発地、目的地、その他の経路探索条件を入力する第１入力手段と、到着時刻範囲を入力する第２入力手段とからなり、前記第１入力手段により入力するその他の経路探索条件は、少なくとも交通機関を利用した経路の運賃、乗り換え回数、所要時間の何れか１つまたは複数を含むことを特徴とする請求項１９に記載の端末装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−８３３７（Ｐ２０１０−８３３７Ａ）
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願番号】特願２００８−１７０４９６（Ｐ２００８−１７０４９６）
【出願日】平成２０年６月３０日（２００８．６．３０）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願日】平成２０年６月３０日（２００８．６．３０）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]