ナビゲーションシステム、経路探索サーバ、端末装置および経路探索方法
【課題】通信型のナビゲーションシステムにおいて、経路探索サーバの再探索負荷を限界まで増加させること無く、多くの端末装置に最適な経路を繰り返し案内できるようにする。
【解決手段】端末装置３０と経路探索サーバ２０を備えたナビゲーションシステム１０において、経路探索サーバ２０は、当該経路探索サーバ２０の負荷を算出するアクセス監視手段２９と、アクセス監視手段２９が算出した負荷に基づいて各端末装置３０ごとに、各端末装置３０からの次回再探索要求までの設定時間を設定する再探索間隔設定手段４１と、を備え、経路探索サーバ２０は、再探索の結果得られた案内経路を端末装置３０に送信し、更に、再探索間隔設定手段４１が設定した設定時間を端末装置３０に送信し、端末装置３０は、経路探索サーバ２０から送信された設定時間に基づいて経路の再探索要求を送信する。
【解決手段】端末装置３０と経路探索サーバ２０を備えたナビゲーションシステム１０において、経路探索サーバ２０は、当該経路探索サーバ２０の負荷を算出するアクセス監視手段２９と、アクセス監視手段２９が算出した負荷に基づいて各端末装置３０ごとに、各端末装置３０からの次回再探索要求までの設定時間を設定する再探索間隔設定手段４１と、を備え、経路探索サーバ２０は、再探索の結果得られた案内経路を端末装置３０に送信し、更に、再探索間隔設定手段４１が設定した設定時間を端末装置３０に送信し、端末装置３０は、経路探索サーバ２０から送信された設定時間に基づいて経路の再探索要求を送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索サーバと端末装置とからなる通信型のナビゲーションシステムにおいて、端末装置が案内経路を取得して経路案内実行中に、渋滞状況を含む道路交通情報に基づいて経路の再探索を要求できるようにしたナビゲーションシステムに関するものであり、特に、端末装置から経路探索サーバに前記経路の再探索要求があった場合に、経路探索サーバは当該端末装置に対して次回以降の経路再探索要求を送信する時間間隔を規定する情報を付加して経路の再探索結果を送信するようにしたナビゲーションシステムに関するものである。
【背景技術】
【０００２】
従来から、地図データや道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
上記カーナビゲーション装置は、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ：全地球測位システム）を利用したものであり、地球上を周回している複数のＧＰＳ衛星から送信されるＧＰＳ信号をＧＰＳアンテナで受信し、該ＧＰＳ信号に含まれる衛星位置や時計情報等を解析して位置の特定化を行うものである。該複数のＧＰＳ衛星の個数は少なくとも４個以上必要である。ＧＰＳの単独測位精度は一般的に１０ｍ強であるが、ＤＧＰＳ（Ｄｉｆｆｅｒｅｎｔｉａｌ ＧＰＳ：ディファレンシャルＧＰＳ）を採用することにより５ｍ以下に向上する。特に、現在では測位ユニット、例えば、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信して測位するＧＰＳ受信機などを搭載した第三世代と称される携帯電話が主流になってきている。
【０００４】
近年、携帯電話、ＰＨＳ等の携帯通信端末機器の性能は飛躍的に向上し、また、多機能化が進んでいる。特に通話機能の他にデータ通信機能が強化され、利用者に対してインターネットを介した種々のデータ通信サービスが提供されている。測位機能を有する携帯電話も実現されており、その利用技術として車載用のナビゲーション装置（カーナビ）を発展させ、携帯電話を端末として地図・経路情報を経路探索サーバから配信する歩行者用の通信型ナビゲーションシステムも実用化されている。
【０００５】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を経路探索サーバに送り、経路探索サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００６】
車載用のナビゲーションシステムおいては、単に目的地までの静的な最適経路を案内するに止まらず、道路交通情報システムから渋滞状況を含む情報を取得して、案内経路に渋滞が発生している場合に、渋滞を回避した他の最適経路を動的に再探索して案内するシステムも考慮されている。
【０００７】
例えば、下記の特許文献２（特許第３４６５６６６号公報）や特許文献３（特許第３２６４２１３号公報）に開示された車載用のナビゲーション装置が知られている。特許文献２に開示されたナビゲーション装置は、交通情報から渋滞箇所を全て特定し、探索経路に渋滞箇所が含まれる時、車両が渋滞箇所に到達した際に、その渋滞箇所を回避するための最適経路の演算が終了している場合には、その渋滞箇所を回避するための最適経路を表示し、車両が渋滞箇所に到達したときに回避最適経路の演算が終了しておらず、かつ、到達した渋滞箇所を回避する経路の演算が終了している場合には、渋滞個所を回避する経路に基づいて、目的地までの間に存在する渋滞箇所を回避するための最適経路を再探索するように構成したものである。
【０００８】
また、特許文献３に開示されたナビゲーション装置は、現在位置から目的地までの経路を探索する第１探索手段と、交通情報が得られた時にこれらを考慮して前記目的地までの経路を再探索する第２探索手段と、前記経路と再探索経路が異なる場合に、前記経路と再探索経路の分岐点が前記現在位置から所定範囲内に存在する場合にのみ前記経路を再探索経路で更新するように構成したものであり、再探索経路を一律に採用して表示するのではなく、再探索経路との分岐点が現在位置から所定範囲内にあって比較的近い（時間的あるいは距離的に）と判定された場合にのみ採用することで、ユーザにとり必要でない経路の提示を防止できるようにしたものである。
【０００９】
渋滞を生じる交通状況は時々刻々変化するものであるから上記特許文献２や特許文献３に開示されたナビゲーション装置においては、車外から渋滞情報（交通情報）を受信するようになっている。例えばＦＭ放送などに含まれたＶＩＣＳ（登録商標）情報から、道路リンクの最新の通過コストを受信して渋滞を考慮した再探索を行うことが考案されている。さらに、再探索を行うということは、既に経路案内動作中であることを意味する。ナビゲーション装置において経路案内を行いながら再探索を行うということは非常に装置への負荷が大きくなる（案内が出来なくなってしまう）ので、できる限り再探索の頻度を減らす必要があった。従って、受信した交通情報が変化したことをトリガにして、再探索を行うというのが一般的に共通する設計思想であった。
【００１０】
一方、前述したようにスタンドアロン型のナビゲーション装置の他、経路探索を経路探索サーバで実行して、端末装置が経路案内を担当するいわゆる通信型のナビゲーション装置がある。このタイプのシステムであれば、ＶＩＣＳ情報は経路探索サーバで収集できるので端末装置が個別に交通情報を受信する必要も無く、また端末装置が経路案内中でも経路サーバが経路の再探索を実行することが出来ると考えられる。
【００１１】
このようなナビゲーションシステムは、例えば、下記の特許文献４（特表２００５−５２４０６１号公報）に開示されている。この特許文献４に開示されたナビゲーションシステムは、車載装置が無線により交通センタに運転目的地までのルート関連データを要求し、交通センタは、自動車の運転目的地までのルートを計算しかつ記憶し、無線により車載装置にルート関連データを送信する。そして、計算されたルートには位置しない、少なくとも１カ所の交通渋滞が交通センタ内で監視され、計算されたルートは、この交通渋滞が緩和した際、少なくとも該ルートの一部を再計算するように構成されたものである。
【００１２】
一般にナビゲーションシステムにおいて、経路の再探索は、上記特許文献２〜特許文献４に開示されたような渋滞を回避するための再探索の他、出発地から目的地までの最適経路を移動中に何らかの原因で、当該最適経路から所定の距離範囲外れた場合に、その位置から目的地までの最適経路を改めて探索して案内する場合に行われる。このような状況は、例えば、右折や左折すべき交差点でガイダンス通りに右折や左折できなかった場合や、ガイダンスされた交差点を見落とした場合などに生じる。経路の再探索は現在位置が案内経路から所定の距離範囲外れたことが検出された場合に自動的に行われ、あるいは、利用者が経路の再探索を要求した場合に行われるように構成される。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特許第３４６５６６６号公報
【特許文献３】特許第３２６４２１３号公報
【特許文献４】特表２００５−５２４０６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、通信型のナビゲーションシステムにおいて、経路探索サーバは多数の端末装置をクライアントとしてナビゲーションサービスを提供するものである。このような通信型のナビゲーションシステムにおいて、渋滞や天候の状況など、移動に影響を与える要因に基づいて時々刻々と多くの端末装置から経路の再探索の要求が経路探索サーバに送られた場合、経路探索サーバに対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達してしまう危険がある。
【００１５】
このような問題を解決する単純な方法は、経路探索サーバを構成するサーバ台数を増やして対処する方法があるが、この方法では、サービスコストが増大するという問題点があり、また、サービスに加入する端末装置の台数、すなわち、クライアント数が増える度にサーバ台数を増加しなければならず、本質的な解決方法になり得ないという問題点がある。
【００１６】
また、上記特許文献４に開示されたナビゲーションシステムにおいては、交通センタが車両を監視しながら、経路以外の渋滞が解消したときに再探索を行って経路を車両に送信するものであるが、このナビゲーションシステムでは、交通センタは全ての車両、すなわち、クライアントの端末を監視する必要があり、また、監視中の全ての車両の経路を記憶している必要があり、クライアント（車両）が増えると処理できなくなり現実的なサービスを提供できないという問題点があった。
【００１７】
通信型のナビゲーションシステムでは、経路探索サーバ側で端末装置を監視したり、各端末装置に提供した案内経路情報などを記憶したりすることなく、端末装置からの経路探索要求や再探索要求に対して経路探索して回答するだけの処理を経路探索サーバが行うというシンプルな構成にするほうが処理効率が良く望ましいといえる。
【００１８】
本発明者は上記の問題点を解消すべく種々検討を重ねた結果、通信型のナビゲーションシステムにおいて、経路探索の要求や再探索の要求は端末装置の自発性に委ねることとし、経路探索サーバ側が各端末装置からのアクセス数などに基づいて端末装置側の要求発生を制御するようになせば、上記問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００１９】
すなわち、本発明は上記の問題点を解消することを課題とし、通信型のナビゲーションシステムにおいて、経路探索サーバの再探索負荷を限界まで増加させること無く、多くの端末装置に最適な経路を繰り返し案内できるナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２０】
前記課題を解決するために、本願の請求項１にかかる発明は、
移動時間に影響を及ぼす要因に関するデータを取得し、端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバと、端末装置と、を備えたナビゲーションシステムにおいて、
前記経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、
前記端末装置は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする。
【００２１】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする。
【００２２】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする。
【００２３】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする。
【００２４】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信することを特徴とする。
【００２５】
また、本願の請求項６にかかる発明は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する端末装置に接続され、前記端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバであって、前記経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信することを特徴とする。
【００２６】
本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする。
【００２７】
本願の請求項８にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする。
【００２８】
本願の請求項９にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする。
【００２９】
また、本願の請求項１０にかかる発明は、
端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信する経路探索サーバに接続される端末装置であって、
前記端末装置は、前記経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする。
【００３０】
また、本願の請求項１１にかかる発明は、
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備えた端末装置と、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備えた、経路探索サーバと、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信するステップを備え、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信するステップを備えたことを特徴とする。
【００３１】
本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、更に、前記アクセス監視手段が、各端末装置からの経路探索要求および再探索要求の数から負荷を算出するステップを有することを特徴とする。
【００３２】
本願の請求項１３にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得するステップと、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定するステップと、当該エリアに位置する端末装置に前記設定時間を送信するステップと、を更に有することを特徴とする。
【００３３】
本願の請求項１４にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別するステップと、前記再探索間隔設定手段が、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定するステップと、を更に有することを特徴とする。
【００３４】
本願の請求項１５にかかる発明は、請求項１１にかかる経路探索方法において、前記端末装置は、更に、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信するステップを有することを特徴とする。
【発明の効果】
【００３５】
請求項１にかかる発明においては、経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、端末装置は、前記経路探索サーバから送信された設定時間に基づいて経路探索サーバに経路の再探索要求を送信する。
【００３６】
このような構成によれば、経路探索サーバは、渋滞など、移動に影響を与える要因に基づいて時々刻々と多くの端末装置から経路の再探索要求があった場合でも、経路探索サーバに対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ側で制御することができるようになる。
【００３７】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出する。このような構成によれば、経路探索サーバは、当該経路探索サーバにかかる負荷を算出することができるから、単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ側で端末装置からの再探索要求の間隔を制御することができるようになる。
【００３８】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信する。
このような構成によれば、経路探索サーバは移動時間に影響を及ぼす要因が発生しているエリアに位置する端末装置と、そうでないエリアに位置する端末装置に対して渋滞などの状況に応じた再探索要求の時間間隔を設定できるようになる。
【００３９】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定する。このような構成によれば、実際に端末装置が移動している移動速度に応じて各端末装置に対する再探索要求の設定時間を設定することができるようになる。
【００４０】
また、請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信する。
このような構成によれば、経路探索サーバが設定した再探索要求の設定時間の送信がない場合には端末装置に設定した時間間隔で再探索要求することができるようになる。
【００４１】
請求項６〜請求項９にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項１０にかかる発明においては、請求項１にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。また、請求項１１〜請求項１５にかかる発明においては、それぞれ請求項１〜請求項５にかかるナビゲーションシステムにおける経路探索方法を提供することができるようになる。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すブロック図である。
【図２】経路探索のための道路ネットワークのデータを説明する模式図である。
【図３】本発明の実施例にかかる経路探索サーバの動作手順を示すフローチャートである。
【図４】本発明の実施例にかかるナビゲーションシステムの動作シーケンスを示すシーケンス図である。
【発明を実施するための形態】
【００４３】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００４４】
本発明の実施例にかかるナビゲーションシステム１０は、図１に示すようにネットワーク１２を介して接続される携帯電話やＰＤＡや音楽プレイヤーなどからなる端末装置３０と経路探索サーバ２０とから構成されている。端末装置３０が携帯電話からなる場合は、移動体通信網などのネットワーク１２を介して移動体通信基地局、電話回線網を経由して所望の相手方（固定電話、携帯電話、ＰＨＳなど）と通話することができ、また、データ通信ネットワークを経由して経路探索サーバ２０に接続して後述するような経路探索、経路案内のナビゲーションサービスを受けることができる。
【００４５】
端末装置３０は例えばＧＰＳ処理手段を有する携帯電話に自動車用ナビゲーションアプリケーションや歩行者用ナビゲーションアプリケーションを搭載したものである。従来この種の端末装置３０を用いたナビゲーションシステムにおいては、出発地から目的地まで、１回の経路探索を行って、経路探索および経路の案内を行っていた。端末装置３０が案内経路から外れた場合、あるいは端末装置３０から再探索の要求操作があった場合にはリルート（経路の再探索）が出来た。
【００４６】
この種の携帯電話を利用したナビゲーションシステムでは、端末装置３０側でＶＩＣＳなどの交通情報を受信することができない。また端末装置３０自身は経路探索を行えないので、経路探索サーバ２０がＶＩＣＳ情報を収集して、リルート時には最新の交通情報を考慮した経路の再探索を行っていた。従って従来のナビゲーションシステムにおいてはリルート要因が発生しない限り、新たに発生した渋滞の回避ということは出来なかった。
【００４７】
本発明においては、端末装置３０が交通情報を直接受信できなくても、所定の間隔で経路探索サーバ３０に経路の再探索要求を送信して問い合わせることで、最新の交通情報に対応した経路（すなわち渋滞回避など）の提供を受けることができるようにしたものである。この場合、経路探索サーバ２０への負荷が増大するが、システム全体でオーバーロードにならないように制御している。
【００４８】
すなわち、本発明にかかるナビゲーションシステムにおいては、端末装置３０と経路探索サーバ２０とのやり取りは、本出願人により既に出願された特開２００４−２０５２３７号公報に開示されたナビゲーションシステムと同様の方式を採用する。つまり、端末装置３０が経路探索サーバ２０に経路の再探索要求を出すときに、前回の経路探索を行ったネットワークの時刻を指定することで、経路探索サーバ２０は、前回の経路を再生することが出来るので、端末装置３０から経路情報を全て経路探索サーバ２０に戻して経路比較をする必要が無い。以下に経路探索サーバ２０および端末装置３０の構成を説明する。
【００４９】
経路探索サーバ２０は、制御手段２１、送受信手段２２、経路探索手段２３、配信データ編集手段２４、操作・表示手段２５、経路探索用の地図データ２６、データ取得手段２７、エリア決定手段２８、アクセス監視手段２９、再探索間隔設定手段４１、端末移動速度判別手段４２などを備えて構成されている。
経路探索用の地図データ２６には、自動車用の経路探索のための道路ネットワークデータの他、歩行者専用道路や公園内の歩行通路を含む歩行者用のネットワークデータ、表示用の地図データ備えている。歩行者用の経路を探索する場合には道路ネットワークデータに歩行者用のネットワークデータを加えて経路探索が行われる。
【００５０】
例えば、自動車用の経路探索のための道路ネットワークデータは次のように構成されている。すなわち、例えば、道路が図２に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００５１】
図２において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図２では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５２】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図２において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００５３】
図２ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００５４】
従って、渋滞などによりリンクの通過に時間がかかる場合には、当該渋滞している道路のリンクコストを渋滞の状況に応じて一時的に変更して経路を再探索する。これにより道路の渋滞状況を反映した目的地までの経路を探索することができる。
【００５５】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。送受信手段２２はネットワーク１２を介して端末装置３０などと通信データを送受信するための通信インターフェースである。操作・表示手段２５は経路探索サーバ２０をモニタしたり、操作したりするためのものである。経路探索手段２３は端末装置３０から送信された経路探索要求に従って、地図データ２６を参照し、周知のダイクストラ法などの経路探索手法を用いて、出発地から目的地に至る最短経路やいくつかの推奨経路を探索する。
【００５６】
配信データ編集手段２４は、経路探索手段２３が探索した経路データを端末装置３０に配信するデータに編集する。また、端末装置３０の現在位置に基づいて、現在地周辺の所定範囲の地図データを地図データ２６から読み出して、端末装置３０に配信するデータに編集する。経路データの編集にあたっては、交差点などのガイダンスポイントと、当該ガイダンスポイントでの右左折、直進などのガイダンスデータが付加される。
【００５７】
データ取得手段２７は、ネットワーク１２を介して図示されていない他の各種情報配信サーバに接続して、端末装置３０の移動速度に影響を与える道路交通情報（渋滞情報）や気象情報（天気予報情報）などのデータを取得する。エリア決定手段２８はデータ取得手段２７が取得したデータに基づいて、移動速度に影響を及ぼすエリアを決定する。
【００５８】
すなわち、エリア決定手段２８は、例えば、渋滞情報に基づいて渋滞により端末装置３０の移動速度に影響を及ぼすエリアを決定し、地図データ２６に記憶されている経路探索用の道路ネットワークデータのリンクコストを、渋滞により影響されるリンクコストの値に一時的に変更する。これにより経路探索サーバ２０は渋滞を加味した経路探索を行うことができるようになる。雨天等により速度規制が行われているエリアがあった場合も同様である。
【００５９】
本発明において、端末装置３０は所定の時間間隔で経路探索サーバ２０に対して経路の再探索要求を行うことができる。これにより端末装置３０は定期的に渋滞などを加味した経路の再探索を経路探索サーバ２０に依頼して、最新の交通情報や天気予報に基づいた最適経路の案内を受けることができるようになる。端末装置３０の詳細な構成については後述する。
【００６０】
アクセス監視手段２９は、各端末装置３０から経路探索サーバ２０に対して要求される経路探索要求や経路の再探索要求などのアクセス負荷を算出する。アクセス負荷は単位時間あたりに各端末装置３０から経路探索サーバ２０に対して送信される各種の要求数、すなわち、アクセス数をアクセス負荷として算出する方法が最も単純である。また、アクセス負荷を算出する他の方法としては、各種の要求ごとに経路探索サーバ２０の負荷を計測する係数を定めておき、アクセス数にこの係数を乗じてアクセス負荷を算出するようにしてもよい。
【００６１】
再探索間隔設定手段４１は、アクセス監視手段２９が算出した経路探索サーバ２０のアクセス負荷に基づいて、各端末装置３０ごとに当該端末装置３０が経路探索サーバ２０に対して経路の再探索要求を行う時間間隔（設定時間）を設定する。再探索間隔設定手段４１が設定した各端末装置３０の設定時間は、経路探索サーバ２０から経路の再探索結果を端末装置３０に送信する際に、当該端末装置３０に対して設定した設定時間を送信する。端末装置３０は、経路探索サーバ２０から送信された設定時間に基づいて、次に経路探索サーバ２０に対して経路の再探索要求を送信する。
【００６２】
このようにすれば、経路探索サーバ２０は、各端末装置３０からのアクセス負荷を考慮して、各端末装置３０が経路の再探索要求を送信する時間間隔を設定して各端末装置３０に送信するから、移動に影響を与える要因に基づいて時々刻々と多くの端末装置３０から経路の再探索の要求が経路探索サーバ２０に送られるとしても、経路探索サーバ２０に対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ２０側で制御することができるようになる。
経路探索サーバ２０がアクセス負荷により各端末装置３０に対して再探索間隔を設定する詳細については、後に詳細に説明する。
【００６３】
端末移動速度判別手段４２は、各端末装置３０から所定間隔で送信される現在位置情報に基づいて各端末装置３０の移動速度を算出する。端末移動速度判別手段４２が算出した各端末装置３０の移動速度は、再探索間隔設定手段４１が各端末装置３０ごとに当該端末装置３０が経路探索サーバ２０に対して経路の再探索要求を行う時間間隔（設定時間）を設定する際に使用される。これについても後述する。
【００６４】
一方、本実施例における端末装置３０は、ＧＰＳ衛星信号を受信して現在位置（緯度・経度）を算出するＧＰＳ処理手段３５を備え、現在位置を測位することができ、この現在位置を使用して経路探索サーバ２０に経路探索を要求したり、現在位置を含む地図情報を要求したりすることができる。端末装置３０は利用者が徒歩移動する場合の徒歩経路の探索要求、自動車の助手席に同乗して運転者をガイドするために、自動車による経路の探索要求を行うことができる。
【００６５】
また、端末装置３０は、制御手段３１、経路探索要求手段３２、案内データ記憶手段３３、地図・経路記憶手段３４、操作・表示手段３６、描画手段３７、再探索時間間隔監視手段３８、再探索要求手段３９などを備えて構成されている。
【００６６】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。経路探索要求手段３２は、出発地や目的地などの経路探索条件に従った経路探索要求を編集し経路探索サーバ２０に送信するためのものである。出発地や目的地などの経路探索条件は操作・表示手段３６から設定あるいは入力される。ＧＰＳ処理手段３５はＧＰＳ衛星からの信号を受信、処理して端末装置３０の現在位置を測位する。
【００６７】
経路探索サーバ２０から端末装置３０に配信された最適経路や推奨経路、ガイダンスデータなどは案内データ記憶手段３３に記憶され、また、経路探索サーバ２０から配信された地図データや経路データは地図・経路記憶手段３４に記憶される。これらの記憶手段に記憶されたデータは、必要に応じて読み出され、操作・表示手段３６に表示される。ＧＰＳ処理手段３５で測位した現在位置に基づいて、当該現在位置を含む所定の範囲の地図データが地図・経路記憶手段３４から読み出され、描画手段３７により表示データに展開される。描画手段３７はＶＲＡＭなどにより構成され、画像データをＶＲＡＭに展開し、操作・表示手段３６に表示する。
【００６８】
再探索時間監視手段３８はタイマー手段を含んで構成され、所定の時間間隔を監視し、再探索要求手段３９は、再探索時間監視手段３８が監視する所定の時間間隔ごとに経路探索サーバ２０に送信する経路の再探索要求を生成する。再探索時間監視手段３８が監視する所定の時間間隔は、経路探索サーバ２０から送信された設定時間がある場合はその設定時間であり、経路探索サーバ２０から送信された設定時間がない場合は、端末装置３０に予め設定された時間間隔である。
【００６９】
従って、端末装置３０は、経路探索サーバ２０から設定時間が指定されていない場合には、予め端末装置３０に設定された時間間隔、例えば、１０分間に１度、経路探索サーバ２０に経路の再探索を要求する。経路探索サーバ２０から設定時間が指定されている場合には、当該設定時間ごとに１度、経路探索サーバ２０に経路の再探索を要求する。従って、経路探索サーバ２０は、各端末装置３０に対して、経路探索サーバ２０のアクセス負荷に基づいて、再探索要求の時間間隔を設定し、単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ２０側で制御することができるようになる。
【００７０】
次に、本発明の実施例にかかるナビゲーションシステム１０における経路探索サーバ２０の動作手順について、図３に示すフローチャートを参照して詳細に説明する。
経路探索サーバ２０は、先ず、ステップＳ１１の処理において、端末装置３０からの経路探索要求を受信する。
【００７１】
次いで、経路探索サーバ２０は、端末装置３０から受信した経路探索要求をチェックして再探索要求であるか否かを判定する。経路探索要求に前回探索時刻の情報が含まれていたら再探索要求である。前回の探索時刻の情報が含まれていなかったら、再探索要求でなく新規の経路探索要求なので、ステップＳ１４の処理に進み、当然に、経路探索要求に含まれている基本的な探索条件（出発地、目的地）に基づいて経路探索手段２３は、地図データ２６に記憶されている経路探索用のネットワークデータを参照して最初の経路探索を行う。
【００７２】
端末装置３０からの経路探索要求が再探索要求であると、ステップＳ１２の処理に進み、経路探索要求に含まれている前回の探索時刻の情報に基づいて前回出発地、前回目的地、探索時刻、前回の案内経路のデータを再現する。つまり、経路探索サーバ２０は端末装置３０のＩＤごとに案内経路を記憶しておく必要も無く、前回経路が再現できる。
そして、ステップＳ１３の処理において経路探索手段２３は、再探索要求に含まれる端末装置３０現在位置から前回探索における目的地と同一の目的地までの最適経路を再探索する。端末装置３０の現在位置から案内経路の前方に渋滞がある場合には、前述したようにリンクコストが渋滞の状況に応じて変更されるので、渋滞の状況を加味した経路が再探索される。
【００７３】
ステップＳ１３の処理において再探索の結果が得られると、ステップＳ１７の処理において、前回の案内経路と再探索の結果により得られた新たな案内経路を比較する。比較の結果、案内経路に変化があったらステップＳ１５の処理に進み、案内経路に変化がなかったらステップＳ１８の処理に進む。
【００７４】
ステップＳ１５の処理においては、ステップＳ１４の経路探索処理によって得られた案内経路またはステップＳ１７の再探索処理によって得られた案内経路（新たな案内経路）を該当する端末装置３０に送信する準備が行われる。この処理では、前述したように、交差点などのガイダンスポイント、当該ガイダンスポイントにおけるガイダンス（右左折の指示データ）などデータを端末装置３０に配信するデータ形式に編集する処理などが行われる。
【００７５】
ステップＳ１５の処理において、案内経路の送信準備が完了すると、新たな経路が求められたことになるので、ステップＳ１６の処理に進み、経路探索サーバ２０は当該端末装置３０に対する設定時間、すなわち、端末装置３０が次回に再探索要求を送信する時間間隔を一旦リセットして、デフォルトとして設定してある標準的な再探索要求の時間間隔としておく。デフォルト値は、例えば、１０分であり、これにより、端末装置３０は１０分間隔で経路探索サーバ２０に再探索要求を送信するようになる。
【００７６】
一方、ステップＳ１７の処理において、案内経路に変化が無かった場合は、新たな案内経路を送信する必要は無いが、次回探索までの時間を検討するためステップＳ１８の処理に進む。ステップＳ１８の処理においては、端末装置３０の現在位置周辺や案内経路の前方所定範囲に、交通渋滞に関係する交通情報が存在するか調べる。ここでは、交通情報とともに天候に関する情報の有無も同様に調べるように構成してもよい。
【００７７】
ここで、調べる情報やその条件を詳述すると、例えば、以下のようである。すなわち、案内経路上およびその周辺の道路交通情報であり、渋滞、事故、交通規制の情報である。また、案内経路上およびその周辺の気象情報であり、雨、雪、低温に関する情報である。
これらの情報は、端末装置３０の移動速度に影響する要因となる情報である。経路探索サーバ２０はこれらの情報が持つ値が平常値（リンクコストを設定した際の標準的な値）を越えている場合は、ステップＳ１９の処理に進み、端末装置３０に対して次回の再探索要求までの設定時間を標準より短めの値に設定する。エリア決定手段２８は、道路交通情報や天気予報に基づいて、端末装置３０の移動速度に影響を与える地理範囲を判定し、当該エリア内に現在位置がある端末装置３０に対してこのような設定時間の調整を行う。
【００７８】
例えば、デフォルトの値「１０分」に対し、一律８分というような設定にしてもよいし、端末装置３０から前回経路探索サーバ２０から送信された設定時間のデータを返すようにしてあれば、ステップＳ１８の処理を通過するごとに「−１分」するようにしても良い。ただしこの場合には、設定時間が最短でも５分を下回らないようにするなどの制限を用いることが必要である。
【００７９】
ステップＳ１８の処理において、交通情報が特に無い場合は、順調な走行が予想されるので、ステップＳ２０の処理に進み、標準の設定時間より長めの時間間隔を設定する。一律１５分としてもよいし、ステップＳ１９の処理と同様に、ステップＳ１８の処理を通過する毎に「＋５分」というようにしても良い。ただし上限は３０分程度にしておくことが必要である。
【００８０】
ステップＳ１９の処理またはステップＳ２０の処理の後、更に、ステップＳ２１の処理の処理に進み、端末装置３０の移動速度に基づいてさらに再探索要求までの設定時間の加減を行う。端末装置３０の移動速度の取得方法としては、伝えられた現在地に基づく道路リンクの属性種別で決定する方法、伝えられた現在地に基づく道路リンクのＶＩＣＳ情報で決定する方法、端末装置３０から平均速度をデータで伝える方法など、種々の方法により移動速度を取得するのが現実的である。
【００８１】
ステップＳ２１の移動速度の判別処理において、端末装置３０の移動速度が標準的な速度と比較して速い場合は、その後の交通情報の変化も比較的激しいので、ステップＳ２２の処理に進み、ステップＳ１９の処理と同様に設定時間を短くするように設定する。
【００８２】
一方、端末装置３０の移動速度が標準的な速度と比較して遅い場合は、その後の交通情報の変化も比較的穏やかなので、ステップＳ２３の処理に進み、ステップＳ２０の処理と同様に設定時間を長くするように設定する。例えば、渋滞に遭遇して身動きが取れなくなってしまったり、ナビゲーション機能を「オン」にしたままパーキングエリアで停車して休憩を取ったりした場合である。このような状況では、頻繁に再探索を行っても効果が上がらないので、ステップＳ２０と同様に長めの設定時間にするのが理にかなった方法である。移動速度が標準的な速度であれば、デフォルトの設定値をそのまま利用する。
【００８３】
以上のステップＳ１８〜ステップＳ２３の処理は個々の端末装置３０に対する次回の再探索要求に対する設定時間の調整であるが、上記の処理が完了した後、ステップＳ２４の処理において、経路探索サーバ２０は、当該経路探索サーバ２０に対するアクセス負荷に基づく設定時間の調整を更に行う。すなわち、ステップＳ２４の処理において、アクセス監視手段２９は過去の所定時間内における単位時間あたりの各端末装置３０からのアクセス数を算出し、経路探索サーバ２０の負荷を見積もる。そしてこの負荷見積もりに従って、各端末装置３０の次回の再探索要求までの設定時間を増減して調整する。
【００８４】
例えば、アクセス監視手段２９は、過去５分間の各端末装置３０からの経路探索要求のアクセス数をモニタリングしている。そして、アクセス数が設計の基準値を超えていたら、さらに長めの設定時間を各端末装置３０に対して設定するようにする。例えば、過去５分間のアクセス数が基準値を１０％超えていたら、設定時間を１０％かあるいはそれ以上に伸ばして負荷を制御する。
【００８５】
アクセス数が急増するのは、主に新規探索の増加であり、その場合でもステップＳ１６からの処理に続いてステップＳ２４の処理を行うので負荷制御が可能である。また、アクセス数が基準値に満たない場合は、設定時間を短くすることなく、その分はシステムの余裕分として温存してもよい。
【００８６】
ステップＳ２４の処理において、アクセス負荷に基づく再探索までの設定時間の調整が終了すると、ステップＳ２５の処理において、経路探索サーバ２０は端末装置３０に対して、新規または再探索による案内経路のデータと、次回の再探索までの設定時間のデータを送信する。
【００８７】
一方、端末装置３０は上記の手順により経路探索サーバ２０から伝えられた設定時間が経過したら、再探索要求を出すようにして、その結果新しい経路が得られたら、その経路に従って案内を継続する。すなわち、再探索時間監視手段３８は、経路探索サーバ２０から送られた設定時間に基づいて再探索要求手段３９を制御して、次回の再探索要求を生成するように動作する。
【００８８】
図４は、以上説明した経路探索サーバ２０と端末装置３０との間のデータ授受のシーケンスを示すシーケンス図である。図４のシーケンス図は、端末装置３０から経路探索サーバ２０に対して再探索要求が送信された状態からを図示している。
【００８９】
シーケンスＳＱ１において端末装置３０は経路探索サーバ２０に再探索要求を送信する。初回の経路探索要求によって端末装置３０は既に経路探索サーバ２０から案内経路を受信しているので、前回の探索要求時刻を持っている。シーケンスＳＱ１の再探索要求において、端末装置３０から経路探索サーバ２０に送信される再探索要求には、前回探索要求時刻、出発地、目的地、現在位置、端末移動速度、設定時間などのデータが含まれる。
【００９０】
これによって経路探索サーバ２０は、経路探索サーバ２０内に端末装置３０が持っている案内経路を再現できる。すなわち、端末装置３０からは現在地（これは原則として経路上にある。もし、現在地が経路上に存在しなければ、その前にリルートが発生し、そのリルート後の経路上にいることになる。）と、例えばＧＰＳの位置の履歴から平均的に求めた移動速度や、現在設定されている探索時間間隔がサーバに伝えられる。
【００９１】
経路探索サーバ２０は、図３のフローチャートで説明した処理を行い、シーケンスＳＱ２において探索結果回答を送信する。例えば、案内経路あるいは周辺の道路において車両が順調に流れており、その先にも特段の交通情報が無い場合には、端末装置３０の次回の再探索要求の設定時間が「５分」に設定され、端末装置３０に送信される。この場合渋滞等がないので、再探索により得られた案内経路に変更は無く「経路の変更無し」が端末装置３０に伝えられる。
【００９２】
端末装置３０は、経路探索サーバ２０から送信された新たな設定時間に従って、シーケンスＳＱ３において、次の再探索要求を経路探索サーバ２０に送信する。このように、端末装置３０と経路探索サーバ２０との間の通信およびその処理は、１回ごとに独立しており、経路探索サーバ２０は個々の端末装置３０ごとに監視情報を保持することもなく、与えられた条件で探索を行って結果を返すだけでよい。また、端末装置３０も、目的地に到着したり、または任意の場所で休憩をとったり、自己の都合で再探索要求を出さないのは自由である。そのような処理が行われてもシステム上の不都合も生じない。
【００９３】
なお、本実施例において、経路探索サーバ２０が端末装置３０に対して設定する設定時間は、端末装置３０が当該設定時間を受信してから、次回の再探索要求を送信する時間間隔である例を説明したが、これに限らず、端末装置３０が再探索要求を送信してから、次回の再探索要求を送信するまでの時間間隔を設定時間とするようにしてもよい。
【００９４】
以上、説明したように本発明によれば、端末装置３０に交通情報の収集や経路探索などの重い処理を行わせることが無いので、端末装置３０は通常の経路案内を継続することが出来て、最適な案内経路に変更があった場合のみ、それを通知して経路案内を継続することができるようになる。
【産業上の利用可能性】
【００９５】
本発明は、端末装置３０の稼動数や交通情報の変化があっても自律的に経路探索サーバ２０自身において負荷を制御することが出来る。さらに経路探索サーバ２０側の要因で一時的に処理能力が落ちることが分かっている場合（経路探索サーバ２０のメンテナンスなどでサーバ台数が半分になるなど）に経路探索サーバ２０の処理能力の基準値を下げるように設定することで、端末装置３０を制御し、破綻無くナビゲーションシステム１０を運営することが出来る。
【符号の説明】
【００９６】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・経路探索サーバ
２１・・・・制御手段
２２・・・・送受信手段
２３・・・・経路探索手段
２４・・・・配信データ編集手段
２５・・・・操作・表示手段
２６・・・・地図データ
２７・・・・データ取得手段
２８・・・・エリア決定手段
２９・・・・アクセス監視手段
４１・・・・再探索間隔設定手段
４２・・・・端末移動速度判別手段
３０・・・・端末装置
３１・・・・制御手段
３２・・・・経路探索要求手段
３３・・・・案内データ記憶手段
３４・・・・地図・経路記憶手段
３５・・・・ＧＰＳ処理手段
３６・・・・操作・表示手段
３７・・・・描画手段
３８・・・・再探索時間監視手段
３９・・・・再探索要求手段
【技術分野】
【０００１】
本発明は、経路探索サーバと端末装置とからなる通信型のナビゲーションシステムにおいて、端末装置が案内経路を取得して経路案内実行中に、渋滞状況を含む道路交通情報に基づいて経路の再探索を要求できるようにしたナビゲーションシステムに関するものであり、特に、端末装置から経路探索サーバに前記経路の再探索要求があった場合に、経路探索サーバは当該端末装置に対して次回以降の経路再探索要求を送信する時間間隔を規定する情報を付加して経路の再探索結果を送信するようにしたナビゲーションシステムに関するものである。
【背景技術】
【０００２】
従来から、地図データや道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
上記カーナビゲーション装置は、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ：全地球測位システム）を利用したものであり、地球上を周回している複数のＧＰＳ衛星から送信されるＧＰＳ信号をＧＰＳアンテナで受信し、該ＧＰＳ信号に含まれる衛星位置や時計情報等を解析して位置の特定化を行うものである。該複数のＧＰＳ衛星の個数は少なくとも４個以上必要である。ＧＰＳの単独測位精度は一般的に１０ｍ強であるが、ＤＧＰＳ（Ｄｉｆｆｅｒｅｎｔｉａｌ ＧＰＳ：ディファレンシャルＧＰＳ）を採用することにより５ｍ以下に向上する。特に、現在では測位ユニット、例えば、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信して測位するＧＰＳ受信機などを搭載した第三世代と称される携帯電話が主流になってきている。
【０００４】
近年、携帯電話、ＰＨＳ等の携帯通信端末機器の性能は飛躍的に向上し、また、多機能化が進んでいる。特に通話機能の他にデータ通信機能が強化され、利用者に対してインターネットを介した種々のデータ通信サービスが提供されている。測位機能を有する携帯電話も実現されており、その利用技術として車載用のナビゲーション装置（カーナビ）を発展させ、携帯電話を端末として地図・経路情報を経路探索サーバから配信する歩行者用の通信型ナビゲーションシステムも実用化されている。
【０００５】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を経路探索サーバに送り、経路探索サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００６】
車載用のナビゲーションシステムおいては、単に目的地までの静的な最適経路を案内するに止まらず、道路交通情報システムから渋滞状況を含む情報を取得して、案内経路に渋滞が発生している場合に、渋滞を回避した他の最適経路を動的に再探索して案内するシステムも考慮されている。
【０００７】
例えば、下記の特許文献２（特許第３４６５６６６号公報）や特許文献３（特許第３２６４２１３号公報）に開示された車載用のナビゲーション装置が知られている。特許文献２に開示されたナビゲーション装置は、交通情報から渋滞箇所を全て特定し、探索経路に渋滞箇所が含まれる時、車両が渋滞箇所に到達した際に、その渋滞箇所を回避するための最適経路の演算が終了している場合には、その渋滞箇所を回避するための最適経路を表示し、車両が渋滞箇所に到達したときに回避最適経路の演算が終了しておらず、かつ、到達した渋滞箇所を回避する経路の演算が終了している場合には、渋滞個所を回避する経路に基づいて、目的地までの間に存在する渋滞箇所を回避するための最適経路を再探索するように構成したものである。
【０００８】
また、特許文献３に開示されたナビゲーション装置は、現在位置から目的地までの経路を探索する第１探索手段と、交通情報が得られた時にこれらを考慮して前記目的地までの経路を再探索する第２探索手段と、前記経路と再探索経路が異なる場合に、前記経路と再探索経路の分岐点が前記現在位置から所定範囲内に存在する場合にのみ前記経路を再探索経路で更新するように構成したものであり、再探索経路を一律に採用して表示するのではなく、再探索経路との分岐点が現在位置から所定範囲内にあって比較的近い（時間的あるいは距離的に）と判定された場合にのみ採用することで、ユーザにとり必要でない経路の提示を防止できるようにしたものである。
【０００９】
渋滞を生じる交通状況は時々刻々変化するものであるから上記特許文献２や特許文献３に開示されたナビゲーション装置においては、車外から渋滞情報（交通情報）を受信するようになっている。例えばＦＭ放送などに含まれたＶＩＣＳ（登録商標）情報から、道路リンクの最新の通過コストを受信して渋滞を考慮した再探索を行うことが考案されている。さらに、再探索を行うということは、既に経路案内動作中であることを意味する。ナビゲーション装置において経路案内を行いながら再探索を行うということは非常に装置への負荷が大きくなる（案内が出来なくなってしまう）ので、できる限り再探索の頻度を減らす必要があった。従って、受信した交通情報が変化したことをトリガにして、再探索を行うというのが一般的に共通する設計思想であった。
【００１０】
一方、前述したようにスタンドアロン型のナビゲーション装置の他、経路探索を経路探索サーバで実行して、端末装置が経路案内を担当するいわゆる通信型のナビゲーション装置がある。このタイプのシステムであれば、ＶＩＣＳ情報は経路探索サーバで収集できるので端末装置が個別に交通情報を受信する必要も無く、また端末装置が経路案内中でも経路サーバが経路の再探索を実行することが出来ると考えられる。
【００１１】
このようなナビゲーションシステムは、例えば、下記の特許文献４（特表２００５−５２４０６１号公報）に開示されている。この特許文献４に開示されたナビゲーションシステムは、車載装置が無線により交通センタに運転目的地までのルート関連データを要求し、交通センタは、自動車の運転目的地までのルートを計算しかつ記憶し、無線により車載装置にルート関連データを送信する。そして、計算されたルートには位置しない、少なくとも１カ所の交通渋滞が交通センタ内で監視され、計算されたルートは、この交通渋滞が緩和した際、少なくとも該ルートの一部を再計算するように構成されたものである。
【００１２】
一般にナビゲーションシステムにおいて、経路の再探索は、上記特許文献２〜特許文献４に開示されたような渋滞を回避するための再探索の他、出発地から目的地までの最適経路を移動中に何らかの原因で、当該最適経路から所定の距離範囲外れた場合に、その位置から目的地までの最適経路を改めて探索して案内する場合に行われる。このような状況は、例えば、右折や左折すべき交差点でガイダンス通りに右折や左折できなかった場合や、ガイダンスされた交差点を見落とした場合などに生じる。経路の再探索は現在位置が案内経路から所定の距離範囲外れたことが検出された場合に自動的に行われ、あるいは、利用者が経路の再探索を要求した場合に行われるように構成される。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特許第３４６５６６６号公報
【特許文献３】特許第３２６４２１３号公報
【特許文献４】特表２００５−５２４０６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、通信型のナビゲーションシステムにおいて、経路探索サーバは多数の端末装置をクライアントとしてナビゲーションサービスを提供するものである。このような通信型のナビゲーションシステムにおいて、渋滞や天候の状況など、移動に影響を与える要因に基づいて時々刻々と多くの端末装置から経路の再探索の要求が経路探索サーバに送られた場合、経路探索サーバに対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達してしまう危険がある。
【００１５】
このような問題を解決する単純な方法は、経路探索サーバを構成するサーバ台数を増やして対処する方法があるが、この方法では、サービスコストが増大するという問題点があり、また、サービスに加入する端末装置の台数、すなわち、クライアント数が増える度にサーバ台数を増加しなければならず、本質的な解決方法になり得ないという問題点がある。
【００１６】
また、上記特許文献４に開示されたナビゲーションシステムにおいては、交通センタが車両を監視しながら、経路以外の渋滞が解消したときに再探索を行って経路を車両に送信するものであるが、このナビゲーションシステムでは、交通センタは全ての車両、すなわち、クライアントの端末を監視する必要があり、また、監視中の全ての車両の経路を記憶している必要があり、クライアント（車両）が増えると処理できなくなり現実的なサービスを提供できないという問題点があった。
【００１７】
通信型のナビゲーションシステムでは、経路探索サーバ側で端末装置を監視したり、各端末装置に提供した案内経路情報などを記憶したりすることなく、端末装置からの経路探索要求や再探索要求に対して経路探索して回答するだけの処理を経路探索サーバが行うというシンプルな構成にするほうが処理効率が良く望ましいといえる。
【００１８】
本発明者は上記の問題点を解消すべく種々検討を重ねた結果、通信型のナビゲーションシステムにおいて、経路探索の要求や再探索の要求は端末装置の自発性に委ねることとし、経路探索サーバ側が各端末装置からのアクセス数などに基づいて端末装置側の要求発生を制御するようになせば、上記問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００１９】
すなわち、本発明は上記の問題点を解消することを課題とし、通信型のナビゲーションシステムにおいて、経路探索サーバの再探索負荷を限界まで増加させること無く、多くの端末装置に最適な経路を繰り返し案内できるナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２０】
前記課題を解決するために、本願の請求項１にかかる発明は、
移動時間に影響を及ぼす要因に関するデータを取得し、端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバと、端末装置と、を備えたナビゲーションシステムにおいて、
前記経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、
前記端末装置は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする。
【００２１】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする。
【００２２】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする。
【００２３】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする。
【００２４】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信することを特徴とする。
【００２５】
また、本願の請求項６にかかる発明は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する端末装置に接続され、前記端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバであって、前記経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信することを特徴とする。
【００２６】
本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする。
【００２７】
本願の請求項８にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする。
【００２８】
本願の請求項９にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする。
【００２９】
また、本願の請求項１０にかかる発明は、
端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信する経路探索サーバに接続される端末装置であって、
前記端末装置は、前記経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする。
【００３０】
また、本願の請求項１１にかかる発明は、
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備えた端末装置と、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備えた、経路探索サーバと、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信するステップを備え、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信するステップを備えたことを特徴とする。
【００３１】
本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、更に、前記アクセス監視手段が、各端末装置からの経路探索要求および再探索要求の数から負荷を算出するステップを有することを特徴とする。
【００３２】
本願の請求項１３にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得するステップと、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定するステップと、当該エリアに位置する端末装置に前記設定時間を送信するステップと、を更に有することを特徴とする。
【００３３】
本願の請求項１４にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別するステップと、前記再探索間隔設定手段が、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定するステップと、を更に有することを特徴とする。
【００３４】
本願の請求項１５にかかる発明は、請求項１１にかかる経路探索方法において、前記端末装置は、更に、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信するステップを有することを特徴とする。
【発明の効果】
【００３５】
請求項１にかかる発明においては、経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、端末装置は、前記経路探索サーバから送信された設定時間に基づいて経路探索サーバに経路の再探索要求を送信する。
【００３６】
このような構成によれば、経路探索サーバは、渋滞など、移動に影響を与える要因に基づいて時々刻々と多くの端末装置から経路の再探索要求があった場合でも、経路探索サーバに対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ側で制御することができるようになる。
【００３７】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出する。このような構成によれば、経路探索サーバは、当該経路探索サーバにかかる負荷を算出することができるから、単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ側で端末装置からの再探索要求の間隔を制御することができるようになる。
【００３８】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信する。
このような構成によれば、経路探索サーバは移動時間に影響を及ぼす要因が発生しているエリアに位置する端末装置と、そうでないエリアに位置する端末装置に対して渋滞などの状況に応じた再探索要求の時間間隔を設定できるようになる。
【００３９】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定する。このような構成によれば、実際に端末装置が移動している移動速度に応じて各端末装置に対する再探索要求の設定時間を設定することができるようになる。
【００４０】
また、請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信する。
このような構成によれば、経路探索サーバが設定した再探索要求の設定時間の送信がない場合には端末装置に設定した時間間隔で再探索要求することができるようになる。
【００４１】
請求項６〜請求項９にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項１０にかかる発明においては、請求項１にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。また、請求項１１〜請求項１５にかかる発明においては、それぞれ請求項１〜請求項５にかかるナビゲーションシステムにおける経路探索方法を提供することができるようになる。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すブロック図である。
【図２】経路探索のための道路ネットワークのデータを説明する模式図である。
【図３】本発明の実施例にかかる経路探索サーバの動作手順を示すフローチャートである。
【図４】本発明の実施例にかかるナビゲーションシステムの動作シーケンスを示すシーケンス図である。
【発明を実施するための形態】
【００４３】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００４４】
本発明の実施例にかかるナビゲーションシステム１０は、図１に示すようにネットワーク１２を介して接続される携帯電話やＰＤＡや音楽プレイヤーなどからなる端末装置３０と経路探索サーバ２０とから構成されている。端末装置３０が携帯電話からなる場合は、移動体通信網などのネットワーク１２を介して移動体通信基地局、電話回線網を経由して所望の相手方（固定電話、携帯電話、ＰＨＳなど）と通話することができ、また、データ通信ネットワークを経由して経路探索サーバ２０に接続して後述するような経路探索、経路案内のナビゲーションサービスを受けることができる。
【００４５】
端末装置３０は例えばＧＰＳ処理手段を有する携帯電話に自動車用ナビゲーションアプリケーションや歩行者用ナビゲーションアプリケーションを搭載したものである。従来この種の端末装置３０を用いたナビゲーションシステムにおいては、出発地から目的地まで、１回の経路探索を行って、経路探索および経路の案内を行っていた。端末装置３０が案内経路から外れた場合、あるいは端末装置３０から再探索の要求操作があった場合にはリルート（経路の再探索）が出来た。
【００４６】
この種の携帯電話を利用したナビゲーションシステムでは、端末装置３０側でＶＩＣＳなどの交通情報を受信することができない。また端末装置３０自身は経路探索を行えないので、経路探索サーバ２０がＶＩＣＳ情報を収集して、リルート時には最新の交通情報を考慮した経路の再探索を行っていた。従って従来のナビゲーションシステムにおいてはリルート要因が発生しない限り、新たに発生した渋滞の回避ということは出来なかった。
【００４７】
本発明においては、端末装置３０が交通情報を直接受信できなくても、所定の間隔で経路探索サーバ３０に経路の再探索要求を送信して問い合わせることで、最新の交通情報に対応した経路（すなわち渋滞回避など）の提供を受けることができるようにしたものである。この場合、経路探索サーバ２０への負荷が増大するが、システム全体でオーバーロードにならないように制御している。
【００４８】
すなわち、本発明にかかるナビゲーションシステムにおいては、端末装置３０と経路探索サーバ２０とのやり取りは、本出願人により既に出願された特開２００４−２０５２３７号公報に開示されたナビゲーションシステムと同様の方式を採用する。つまり、端末装置３０が経路探索サーバ２０に経路の再探索要求を出すときに、前回の経路探索を行ったネットワークの時刻を指定することで、経路探索サーバ２０は、前回の経路を再生することが出来るので、端末装置３０から経路情報を全て経路探索サーバ２０に戻して経路比較をする必要が無い。以下に経路探索サーバ２０および端末装置３０の構成を説明する。
【００４９】
経路探索サーバ２０は、制御手段２１、送受信手段２２、経路探索手段２３、配信データ編集手段２４、操作・表示手段２５、経路探索用の地図データ２６、データ取得手段２７、エリア決定手段２８、アクセス監視手段２９、再探索間隔設定手段４１、端末移動速度判別手段４２などを備えて構成されている。
経路探索用の地図データ２６には、自動車用の経路探索のための道路ネットワークデータの他、歩行者専用道路や公園内の歩行通路を含む歩行者用のネットワークデータ、表示用の地図データ備えている。歩行者用の経路を探索する場合には道路ネットワークデータに歩行者用のネットワークデータを加えて経路探索が行われる。
【００５０】
例えば、自動車用の経路探索のための道路ネットワークデータは次のように構成されている。すなわち、例えば、道路が図２に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００５１】
図２において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図２では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５２】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図２において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００５３】
図２ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００５４】
従って、渋滞などによりリンクの通過に時間がかかる場合には、当該渋滞している道路のリンクコストを渋滞の状況に応じて一時的に変更して経路を再探索する。これにより道路の渋滞状況を反映した目的地までの経路を探索することができる。
【００５５】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。送受信手段２２はネットワーク１２を介して端末装置３０などと通信データを送受信するための通信インターフェースである。操作・表示手段２５は経路探索サーバ２０をモニタしたり、操作したりするためのものである。経路探索手段２３は端末装置３０から送信された経路探索要求に従って、地図データ２６を参照し、周知のダイクストラ法などの経路探索手法を用いて、出発地から目的地に至る最短経路やいくつかの推奨経路を探索する。
【００５６】
配信データ編集手段２４は、経路探索手段２３が探索した経路データを端末装置３０に配信するデータに編集する。また、端末装置３０の現在位置に基づいて、現在地周辺の所定範囲の地図データを地図データ２６から読み出して、端末装置３０に配信するデータに編集する。経路データの編集にあたっては、交差点などのガイダンスポイントと、当該ガイダンスポイントでの右左折、直進などのガイダンスデータが付加される。
【００５７】
データ取得手段２７は、ネットワーク１２を介して図示されていない他の各種情報配信サーバに接続して、端末装置３０の移動速度に影響を与える道路交通情報（渋滞情報）や気象情報（天気予報情報）などのデータを取得する。エリア決定手段２８はデータ取得手段２７が取得したデータに基づいて、移動速度に影響を及ぼすエリアを決定する。
【００５８】
すなわち、エリア決定手段２８は、例えば、渋滞情報に基づいて渋滞により端末装置３０の移動速度に影響を及ぼすエリアを決定し、地図データ２６に記憶されている経路探索用の道路ネットワークデータのリンクコストを、渋滞により影響されるリンクコストの値に一時的に変更する。これにより経路探索サーバ２０は渋滞を加味した経路探索を行うことができるようになる。雨天等により速度規制が行われているエリアがあった場合も同様である。
【００５９】
本発明において、端末装置３０は所定の時間間隔で経路探索サーバ２０に対して経路の再探索要求を行うことができる。これにより端末装置３０は定期的に渋滞などを加味した経路の再探索を経路探索サーバ２０に依頼して、最新の交通情報や天気予報に基づいた最適経路の案内を受けることができるようになる。端末装置３０の詳細な構成については後述する。
【００６０】
アクセス監視手段２９は、各端末装置３０から経路探索サーバ２０に対して要求される経路探索要求や経路の再探索要求などのアクセス負荷を算出する。アクセス負荷は単位時間あたりに各端末装置３０から経路探索サーバ２０に対して送信される各種の要求数、すなわち、アクセス数をアクセス負荷として算出する方法が最も単純である。また、アクセス負荷を算出する他の方法としては、各種の要求ごとに経路探索サーバ２０の負荷を計測する係数を定めておき、アクセス数にこの係数を乗じてアクセス負荷を算出するようにしてもよい。
【００６１】
再探索間隔設定手段４１は、アクセス監視手段２９が算出した経路探索サーバ２０のアクセス負荷に基づいて、各端末装置３０ごとに当該端末装置３０が経路探索サーバ２０に対して経路の再探索要求を行う時間間隔（設定時間）を設定する。再探索間隔設定手段４１が設定した各端末装置３０の設定時間は、経路探索サーバ２０から経路の再探索結果を端末装置３０に送信する際に、当該端末装置３０に対して設定した設定時間を送信する。端末装置３０は、経路探索サーバ２０から送信された設定時間に基づいて、次に経路探索サーバ２０に対して経路の再探索要求を送信する。
【００６２】
このようにすれば、経路探索サーバ２０は、各端末装置３０からのアクセス負荷を考慮して、各端末装置３０が経路の再探索要求を送信する時間間隔を設定して各端末装置３０に送信するから、移動に影響を与える要因に基づいて時々刻々と多くの端末装置３０から経路の再探索の要求が経路探索サーバ２０に送られるとしても、経路探索サーバ２０に対する単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ２０側で制御することができるようになる。
経路探索サーバ２０がアクセス負荷により各端末装置３０に対して再探索間隔を設定する詳細については、後に詳細に説明する。
【００６３】
端末移動速度判別手段４２は、各端末装置３０から所定間隔で送信される現在位置情報に基づいて各端末装置３０の移動速度を算出する。端末移動速度判別手段４２が算出した各端末装置３０の移動速度は、再探索間隔設定手段４１が各端末装置３０ごとに当該端末装置３０が経路探索サーバ２０に対して経路の再探索要求を行う時間間隔（設定時間）を設定する際に使用される。これについても後述する。
【００６４】
一方、本実施例における端末装置３０は、ＧＰＳ衛星信号を受信して現在位置（緯度・経度）を算出するＧＰＳ処理手段３５を備え、現在位置を測位することができ、この現在位置を使用して経路探索サーバ２０に経路探索を要求したり、現在位置を含む地図情報を要求したりすることができる。端末装置３０は利用者が徒歩移動する場合の徒歩経路の探索要求、自動車の助手席に同乗して運転者をガイドするために、自動車による経路の探索要求を行うことができる。
【００６５】
また、端末装置３０は、制御手段３１、経路探索要求手段３２、案内データ記憶手段３３、地図・経路記憶手段３４、操作・表示手段３６、描画手段３７、再探索時間間隔監視手段３８、再探索要求手段３９などを備えて構成されている。
【００６６】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。経路探索要求手段３２は、出発地や目的地などの経路探索条件に従った経路探索要求を編集し経路探索サーバ２０に送信するためのものである。出発地や目的地などの経路探索条件は操作・表示手段３６から設定あるいは入力される。ＧＰＳ処理手段３５はＧＰＳ衛星からの信号を受信、処理して端末装置３０の現在位置を測位する。
【００６７】
経路探索サーバ２０から端末装置３０に配信された最適経路や推奨経路、ガイダンスデータなどは案内データ記憶手段３３に記憶され、また、経路探索サーバ２０から配信された地図データや経路データは地図・経路記憶手段３４に記憶される。これらの記憶手段に記憶されたデータは、必要に応じて読み出され、操作・表示手段３６に表示される。ＧＰＳ処理手段３５で測位した現在位置に基づいて、当該現在位置を含む所定の範囲の地図データが地図・経路記憶手段３４から読み出され、描画手段３７により表示データに展開される。描画手段３７はＶＲＡＭなどにより構成され、画像データをＶＲＡＭに展開し、操作・表示手段３６に表示する。
【００６８】
再探索時間監視手段３８はタイマー手段を含んで構成され、所定の時間間隔を監視し、再探索要求手段３９は、再探索時間監視手段３８が監視する所定の時間間隔ごとに経路探索サーバ２０に送信する経路の再探索要求を生成する。再探索時間監視手段３８が監視する所定の時間間隔は、経路探索サーバ２０から送信された設定時間がある場合はその設定時間であり、経路探索サーバ２０から送信された設定時間がない場合は、端末装置３０に予め設定された時間間隔である。
【００６９】
従って、端末装置３０は、経路探索サーバ２０から設定時間が指定されていない場合には、予め端末装置３０に設定された時間間隔、例えば、１０分間に１度、経路探索サーバ２０に経路の再探索を要求する。経路探索サーバ２０から設定時間が指定されている場合には、当該設定時間ごとに１度、経路探索サーバ２０に経路の再探索を要求する。従って、経路探索サーバ２０は、各端末装置３０に対して、経路探索サーバ２０のアクセス負荷に基づいて、再探索要求の時間間隔を設定し、単位時間あたりのアクセス数（探索要求数）がサーバの処理能力の限界に達することがないように経路探索サーバ２０側で制御することができるようになる。
【００７０】
次に、本発明の実施例にかかるナビゲーションシステム１０における経路探索サーバ２０の動作手順について、図３に示すフローチャートを参照して詳細に説明する。
経路探索サーバ２０は、先ず、ステップＳ１１の処理において、端末装置３０からの経路探索要求を受信する。
【００７１】
次いで、経路探索サーバ２０は、端末装置３０から受信した経路探索要求をチェックして再探索要求であるか否かを判定する。経路探索要求に前回探索時刻の情報が含まれていたら再探索要求である。前回の探索時刻の情報が含まれていなかったら、再探索要求でなく新規の経路探索要求なので、ステップＳ１４の処理に進み、当然に、経路探索要求に含まれている基本的な探索条件（出発地、目的地）に基づいて経路探索手段２３は、地図データ２６に記憶されている経路探索用のネットワークデータを参照して最初の経路探索を行う。
【００７２】
端末装置３０からの経路探索要求が再探索要求であると、ステップＳ１２の処理に進み、経路探索要求に含まれている前回の探索時刻の情報に基づいて前回出発地、前回目的地、探索時刻、前回の案内経路のデータを再現する。つまり、経路探索サーバ２０は端末装置３０のＩＤごとに案内経路を記憶しておく必要も無く、前回経路が再現できる。
そして、ステップＳ１３の処理において経路探索手段２３は、再探索要求に含まれる端末装置３０現在位置から前回探索における目的地と同一の目的地までの最適経路を再探索する。端末装置３０の現在位置から案内経路の前方に渋滞がある場合には、前述したようにリンクコストが渋滞の状況に応じて変更されるので、渋滞の状況を加味した経路が再探索される。
【００７３】
ステップＳ１３の処理において再探索の結果が得られると、ステップＳ１７の処理において、前回の案内経路と再探索の結果により得られた新たな案内経路を比較する。比較の結果、案内経路に変化があったらステップＳ１５の処理に進み、案内経路に変化がなかったらステップＳ１８の処理に進む。
【００７４】
ステップＳ１５の処理においては、ステップＳ１４の経路探索処理によって得られた案内経路またはステップＳ１７の再探索処理によって得られた案内経路（新たな案内経路）を該当する端末装置３０に送信する準備が行われる。この処理では、前述したように、交差点などのガイダンスポイント、当該ガイダンスポイントにおけるガイダンス（右左折の指示データ）などデータを端末装置３０に配信するデータ形式に編集する処理などが行われる。
【００７５】
ステップＳ１５の処理において、案内経路の送信準備が完了すると、新たな経路が求められたことになるので、ステップＳ１６の処理に進み、経路探索サーバ２０は当該端末装置３０に対する設定時間、すなわち、端末装置３０が次回に再探索要求を送信する時間間隔を一旦リセットして、デフォルトとして設定してある標準的な再探索要求の時間間隔としておく。デフォルト値は、例えば、１０分であり、これにより、端末装置３０は１０分間隔で経路探索サーバ２０に再探索要求を送信するようになる。
【００７６】
一方、ステップＳ１７の処理において、案内経路に変化が無かった場合は、新たな案内経路を送信する必要は無いが、次回探索までの時間を検討するためステップＳ１８の処理に進む。ステップＳ１８の処理においては、端末装置３０の現在位置周辺や案内経路の前方所定範囲に、交通渋滞に関係する交通情報が存在するか調べる。ここでは、交通情報とともに天候に関する情報の有無も同様に調べるように構成してもよい。
【００７７】
ここで、調べる情報やその条件を詳述すると、例えば、以下のようである。すなわち、案内経路上およびその周辺の道路交通情報であり、渋滞、事故、交通規制の情報である。また、案内経路上およびその周辺の気象情報であり、雨、雪、低温に関する情報である。
これらの情報は、端末装置３０の移動速度に影響する要因となる情報である。経路探索サーバ２０はこれらの情報が持つ値が平常値（リンクコストを設定した際の標準的な値）を越えている場合は、ステップＳ１９の処理に進み、端末装置３０に対して次回の再探索要求までの設定時間を標準より短めの値に設定する。エリア決定手段２８は、道路交通情報や天気予報に基づいて、端末装置３０の移動速度に影響を与える地理範囲を判定し、当該エリア内に現在位置がある端末装置３０に対してこのような設定時間の調整を行う。
【００７８】
例えば、デフォルトの値「１０分」に対し、一律８分というような設定にしてもよいし、端末装置３０から前回経路探索サーバ２０から送信された設定時間のデータを返すようにしてあれば、ステップＳ１８の処理を通過するごとに「−１分」するようにしても良い。ただしこの場合には、設定時間が最短でも５分を下回らないようにするなどの制限を用いることが必要である。
【００７９】
ステップＳ１８の処理において、交通情報が特に無い場合は、順調な走行が予想されるので、ステップＳ２０の処理に進み、標準の設定時間より長めの時間間隔を設定する。一律１５分としてもよいし、ステップＳ１９の処理と同様に、ステップＳ１８の処理を通過する毎に「＋５分」というようにしても良い。ただし上限は３０分程度にしておくことが必要である。
【００８０】
ステップＳ１９の処理またはステップＳ２０の処理の後、更に、ステップＳ２１の処理の処理に進み、端末装置３０の移動速度に基づいてさらに再探索要求までの設定時間の加減を行う。端末装置３０の移動速度の取得方法としては、伝えられた現在地に基づく道路リンクの属性種別で決定する方法、伝えられた現在地に基づく道路リンクのＶＩＣＳ情報で決定する方法、端末装置３０から平均速度をデータで伝える方法など、種々の方法により移動速度を取得するのが現実的である。
【００８１】
ステップＳ２１の移動速度の判別処理において、端末装置３０の移動速度が標準的な速度と比較して速い場合は、その後の交通情報の変化も比較的激しいので、ステップＳ２２の処理に進み、ステップＳ１９の処理と同様に設定時間を短くするように設定する。
【００８２】
一方、端末装置３０の移動速度が標準的な速度と比較して遅い場合は、その後の交通情報の変化も比較的穏やかなので、ステップＳ２３の処理に進み、ステップＳ２０の処理と同様に設定時間を長くするように設定する。例えば、渋滞に遭遇して身動きが取れなくなってしまったり、ナビゲーション機能を「オン」にしたままパーキングエリアで停車して休憩を取ったりした場合である。このような状況では、頻繁に再探索を行っても効果が上がらないので、ステップＳ２０と同様に長めの設定時間にするのが理にかなった方法である。移動速度が標準的な速度であれば、デフォルトの設定値をそのまま利用する。
【００８３】
以上のステップＳ１８〜ステップＳ２３の処理は個々の端末装置３０に対する次回の再探索要求に対する設定時間の調整であるが、上記の処理が完了した後、ステップＳ２４の処理において、経路探索サーバ２０は、当該経路探索サーバ２０に対するアクセス負荷に基づく設定時間の調整を更に行う。すなわち、ステップＳ２４の処理において、アクセス監視手段２９は過去の所定時間内における単位時間あたりの各端末装置３０からのアクセス数を算出し、経路探索サーバ２０の負荷を見積もる。そしてこの負荷見積もりに従って、各端末装置３０の次回の再探索要求までの設定時間を増減して調整する。
【００８４】
例えば、アクセス監視手段２９は、過去５分間の各端末装置３０からの経路探索要求のアクセス数をモニタリングしている。そして、アクセス数が設計の基準値を超えていたら、さらに長めの設定時間を各端末装置３０に対して設定するようにする。例えば、過去５分間のアクセス数が基準値を１０％超えていたら、設定時間を１０％かあるいはそれ以上に伸ばして負荷を制御する。
【００８５】
アクセス数が急増するのは、主に新規探索の増加であり、その場合でもステップＳ１６からの処理に続いてステップＳ２４の処理を行うので負荷制御が可能である。また、アクセス数が基準値に満たない場合は、設定時間を短くすることなく、その分はシステムの余裕分として温存してもよい。
【００８６】
ステップＳ２４の処理において、アクセス負荷に基づく再探索までの設定時間の調整が終了すると、ステップＳ２５の処理において、経路探索サーバ２０は端末装置３０に対して、新規または再探索による案内経路のデータと、次回の再探索までの設定時間のデータを送信する。
【００８７】
一方、端末装置３０は上記の手順により経路探索サーバ２０から伝えられた設定時間が経過したら、再探索要求を出すようにして、その結果新しい経路が得られたら、その経路に従って案内を継続する。すなわち、再探索時間監視手段３８は、経路探索サーバ２０から送られた設定時間に基づいて再探索要求手段３９を制御して、次回の再探索要求を生成するように動作する。
【００８８】
図４は、以上説明した経路探索サーバ２０と端末装置３０との間のデータ授受のシーケンスを示すシーケンス図である。図４のシーケンス図は、端末装置３０から経路探索サーバ２０に対して再探索要求が送信された状態からを図示している。
【００８９】
シーケンスＳＱ１において端末装置３０は経路探索サーバ２０に再探索要求を送信する。初回の経路探索要求によって端末装置３０は既に経路探索サーバ２０から案内経路を受信しているので、前回の探索要求時刻を持っている。シーケンスＳＱ１の再探索要求において、端末装置３０から経路探索サーバ２０に送信される再探索要求には、前回探索要求時刻、出発地、目的地、現在位置、端末移動速度、設定時間などのデータが含まれる。
【００９０】
これによって経路探索サーバ２０は、経路探索サーバ２０内に端末装置３０が持っている案内経路を再現できる。すなわち、端末装置３０からは現在地（これは原則として経路上にある。もし、現在地が経路上に存在しなければ、その前にリルートが発生し、そのリルート後の経路上にいることになる。）と、例えばＧＰＳの位置の履歴から平均的に求めた移動速度や、現在設定されている探索時間間隔がサーバに伝えられる。
【００９１】
経路探索サーバ２０は、図３のフローチャートで説明した処理を行い、シーケンスＳＱ２において探索結果回答を送信する。例えば、案内経路あるいは周辺の道路において車両が順調に流れており、その先にも特段の交通情報が無い場合には、端末装置３０の次回の再探索要求の設定時間が「５分」に設定され、端末装置３０に送信される。この場合渋滞等がないので、再探索により得られた案内経路に変更は無く「経路の変更無し」が端末装置３０に伝えられる。
【００９２】
端末装置３０は、経路探索サーバ２０から送信された新たな設定時間に従って、シーケンスＳＱ３において、次の再探索要求を経路探索サーバ２０に送信する。このように、端末装置３０と経路探索サーバ２０との間の通信およびその処理は、１回ごとに独立しており、経路探索サーバ２０は個々の端末装置３０ごとに監視情報を保持することもなく、与えられた条件で探索を行って結果を返すだけでよい。また、端末装置３０も、目的地に到着したり、または任意の場所で休憩をとったり、自己の都合で再探索要求を出さないのは自由である。そのような処理が行われてもシステム上の不都合も生じない。
【００９３】
なお、本実施例において、経路探索サーバ２０が端末装置３０に対して設定する設定時間は、端末装置３０が当該設定時間を受信してから、次回の再探索要求を送信する時間間隔である例を説明したが、これに限らず、端末装置３０が再探索要求を送信してから、次回の再探索要求を送信するまでの時間間隔を設定時間とするようにしてもよい。
【００９４】
以上、説明したように本発明によれば、端末装置３０に交通情報の収集や経路探索などの重い処理を行わせることが無いので、端末装置３０は通常の経路案内を継続することが出来て、最適な案内経路に変更があった場合のみ、それを通知して経路案内を継続することができるようになる。
【産業上の利用可能性】
【００９５】
本発明は、端末装置３０の稼動数や交通情報の変化があっても自律的に経路探索サーバ２０自身において負荷を制御することが出来る。さらに経路探索サーバ２０側の要因で一時的に処理能力が落ちることが分かっている場合（経路探索サーバ２０のメンテナンスなどでサーバ台数が半分になるなど）に経路探索サーバ２０の処理能力の基準値を下げるように設定することで、端末装置３０を制御し、破綻無くナビゲーションシステム１０を運営することが出来る。
【符号の説明】
【００９６】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・経路探索サーバ
２１・・・・制御手段
２２・・・・送受信手段
２３・・・・経路探索手段
２４・・・・配信データ編集手段
２５・・・・操作・表示手段
２６・・・・地図データ
２７・・・・データ取得手段
２８・・・・エリア決定手段
２９・・・・アクセス監視手段
４１・・・・再探索間隔設定手段
４２・・・・端末移動速度判別手段
３０・・・・端末装置
３１・・・・制御手段
３２・・・・経路探索要求手段
３３・・・・案内データ記憶手段
３４・・・・地図・経路記憶手段
３５・・・・ＧＰＳ処理手段
３６・・・・操作・表示手段
３７・・・・描画手段
３８・・・・再探索時間監視手段
３９・・・・再探索要求手段
【特許請求の範囲】
【請求項１】
移動時間に影響を及ぼす要因に関するデータを取得し、端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバと、端末装置と、を備えたナビゲーションシステムにおいて、
前記経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、
前記端末装置は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とするナビゲーションシステム。
【請求項２】
前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する端末装置に接続され、前記端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバであって、
前記経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信することを特徴とする経路探索サーバ。
【請求項７】
前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする請求項６に記載の経路探索サーバ。
【請求項９】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする請求項６に記載の経路探索サーバ。
【請求項１０】
端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信する経路探索サーバに接続される端末装置であって、
前記端末装置は、前記経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする端末装置。
【請求項１１】
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備えた端末装置と、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備えた、経路探索サーバと、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信するステップを備え、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信するステップを備えたことを特徴とする経路探索方法。
【請求項１２】
前記経路探索サーバは、更に、前記アクセス監視手段が、各端末装置からの経路探索要求および再探索要求の数から負荷を算出するステップを有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得するステップと、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定するステップと、当該エリアに位置する端末装置に前記設定時間を送信するステップと、を更に有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１４】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別するステップと、前記再探索間隔設定手段が、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定するステップと、を更に有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１５】
前記端末装置は、更に、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信するステップを有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１】
移動時間に影響を及ぼす要因に関するデータを取得し、端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバと、端末装置と、を備えたナビゲーションシステムにおいて、
前記経路探索サーバは、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、
前記端末装置は、経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信し、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とするナビゲーションシステム。
【請求項２】
前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記端末装置は、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する端末装置に接続され、前記端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバであって、
前記経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信することを特徴とする経路探索サーバ。
【請求項７】
前記アクセス監視手段は、各端末装置からの経路探索要求および再探索要求の数から負荷を算出することを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得し、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定し、当該エリアに位置する端末装置に前記設定時間を送信することを特徴とする請求項６に記載の経路探索サーバ。
【請求項９】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別し、前記再探索間隔設定手段は、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定することを特徴とする請求項６に記載の経路探索サーバ。
【請求項１０】
端末装置から要求された経路の再探索要求に対する案内経路を探索して当該端末装置に送信する経路探索サーバは、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備え、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信する経路探索サーバに接続される端末装置であって、
前記端末装置は、前記経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備え、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信することを特徴とする端末装置。
【請求項１１】
経路探索サーバから案内経路を取得して経路案内中に所定の設定時間間隔で前記経路探索サーバに経路の再探索要求を送信する再探索要求手段と、前記設定時間間隔を監視し制御する再探索時間監視手段と、を備えた端末装置と、移動時間に影響を及ぼす要因に関するデータを取得するデータ取得手段と、当該経路探索サーバの負荷を算出するアクセス監視手段と、前記アクセス監視手段が算出した負荷に基づいて前記各端末装置ごとに、各端末装置からの次回再探索要求までの設定時間を設定する再探索間隔設定手段と、を備えた、経路探索サーバと、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索サーバは、再探索の結果得られた案内経路を前記端末装置に送信し、更に、前記再探索間隔設定手段が設定した設定時間を前記端末装置に送信するステップを備え、
前記端末装置は、前記経路探索サーバから送信された設定時間に基づいて、前記再探索時間監視手段により制御される設定時間間隔で前記経路探索サーバに経路の再探索要求を送信するステップを備えたことを特徴とする経路探索方法。
【請求項１２】
前記経路探索サーバは、更に、前記アクセス監視手段が、各端末装置からの経路探索要求および再探索要求の数から負荷を算出するステップを有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記経路探索サーバは、エリア決定手段を備え、移動時間に影響を及ぼす要因として、交通情報または天候情報あるいは交通情報および天候情報を対象とし、前記要因に関するデータを他の情報配信サーバから取得するステップと、当該要因に関するデータに基づいて前記エリア決定手段はエリアを決定するステップと、当該エリアに位置する端末装置に前記設定時間を送信するステップと、を更に有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１４】
前記経路探索サーバは、端末装置の移動速度を判別する端末移動速度判別手段を備え、端末装置から再探索要求を受信した際に当該端末装置の移動速度を判別するステップと、前記再探索間隔設定手段が、前記端末装置の移動速度に応じて当該端末装置に対する設定時間を設定するステップと、を更に有することを特徴とする請求項１１に記載の経路探索方法。
【請求項１５】
前記端末装置は、更に、前記経路探索サーバが設定した設定時間を受信しない場合、予め設定された所定の時間が経過した後に前記再探索要求を前記経路探索サーバに送信し、前記経路探索サーバが設定した設定時間を受信した場合、当該経路探索サーバが設定した設定時間間隔で再探索要求を前記経路探索サーバに送信するステップを有することを特徴とする請求項１１に記載の経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１３−１５５３５（Ｐ２０１３−１５５３５Ａ）
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願番号】特願２０１２−２０２７２４（Ｐ２０１２−２０２７２４）
【出願日】平成２４年９月１４日（２０１２．９．１４）
【分割の表示】特願２００６−１３２２２４（Ｐ２００６−１３２２２４）の分割
【原出願日】平成１８年５月１１日（２００６．５．１１）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願日】平成２４年９月１４日（２０１２．９．１４）
【分割の表示】特願２００６−１３２２２４（Ｐ２００６−１３２２２４）の分割
【原出願日】平成１８年５月１１日（２００６．５．１１）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]