経路案内システム
【課題】 特定の時間帯で通行止めになるなどの規制条件を考慮して、実用的な経路探索を行う。
【解決手段】 経路探索に用いるデータとして、地図DB250、時刻表DB252、ユーザDB254を設ける。地図DB250は、通路をノード、リンクで表すネットワークデータを格納している。時刻表DB252は、交通機関の発車時間、特定の時間帯での通行止めなど、リンクを通行するための規制条件を格納している。サーバ200は、規制条件を考慮して探索を行う。規制条件に応じて待ち時間が生じる場合には、好適な待合場所を求め、その待合場所を経由する経由経路を探索、案内する。待合場所の選択時には、規制箇所からの距離または所要時間と、待合場所としての好適度の双方を考慮する。こうすることで、快適な待合場所をユーザに提供可能となり、実用性、利便性に優れた経路案内を実現することができる。
【解決手段】 経路探索に用いるデータとして、地図DB250、時刻表DB252、ユーザDB254を設ける。地図DB250は、通路をノード、リンクで表すネットワークデータを格納している。時刻表DB252は、交通機関の発車時間、特定の時間帯での通行止めなど、リンクを通行するための規制条件を格納している。サーバ200は、規制条件を考慮して探索を行う。規制条件に応じて待ち時間が生じる場合には、好適な待合場所を求め、その待合場所を経由する経由経路を探索、案内する。待合場所の選択時には、規制箇所からの距離または所要時間と、待合場所としての好適度の双方を考慮する。こうすることで、快適な待合場所をユーザに提供可能となり、実用性、利便性に優れた経路案内を実現することができる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、時間によって通行可否や通行の方向が異なる規制箇所が存在する場合における経路探索、案内技術に関する。
【背景技術】
【0002】
車両または歩行者用に、指定された出発地から目的地に至る最適な経路を探索、案内する経路案内装置が提案されている。経路案内装置は、通路をノード、リンクで表したネットワークデータを参照し、各リンクに付された評価値、即ちコストの総和が最小となる経路を探索する。歩行者用の経路案内システムでは、電車やフェリーなどの公共交通機関を通路に含めて経路探索を行う技術も提案されている(特許文献1〜3参照)。
【0003】
公共交通機関を含む場合には、所要時間に基づいてコストを設定することにより、所要時間が最短となる経路の探索が行われる。公共交通機関は、出発時刻が予め定められているため、公共交通機関を利用する際には、この出発時刻との関係で無駄な待ち時間が生じる場合もある。特許文献1〜3は、公共交通機関の時刻表をデータベースとして備えることにより、各公共交通機関の待ち時間も考慮して最短時間の到達経路を探索する技術を開示している。
【0004】
【特許文献1】特開平8−166248号公報
【特許文献2】特開2001−165683号公報
【特許文献3】特開2001−280992号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
従来技術では、経路探索時に、待ち時間は考慮されているものの、待合場所については考慮されていなかった。つまり、従来技術では、規制が付されたノード(以下、「規制ノード」と称する)で待つことを前提として経路探索が行われているが、必ずしも規制ノードは待合いに適しているとは限らなかった。待ち時間によっては、ユーザは喫茶店やコンビニエンスストアなどでの待機を望む場合もある。従来、これらの待合場所はユーザ自身が探す必要があった。また、待合場所への往復の経路を考慮すると、当初予定されていた公共交通機関ではなく、徒歩その他の移動手段を利用する方が好ましい経路が得られる場合もあった。このように従来の経路探索は、実用性、利便性という観点で、更に改善の余地が残されていた。
【0006】
かかる課題は、交通機関を利用する場合に限られるものではない。例えば、時間によって通行禁止となる道路、一方通行の規制方向が変わる道路、及び右左折禁止などの規制が解除される交差点、時間帯によって通行止めが解除される有料道路などについても同様に、規制が切り替わる直前に規制箇所に到達するか否かによって探索結果が大きく影響を受ける可能性がある。時間帯によって通行可能となる経路が探索されたとしても、車両の場合には、通行規制が付された交差点等で規制が解除されるまで待つことはできないことがあり、現実には探索された経路を走行することができなかったり、ユーザ自身で待機場所を探したりする必要があった。本発明は、こうした課題に鑑み、探索された経路の途中で待ち時間が生じる場合における経路案内の実用性、利便性を向上することを目的とする。
【課題を解決するための手段】
【0007】
本発明は、出発地および目的地の指定を受け付けて両者間の経路を探索する経路案内システムとして構成することができる。車両および歩行者のいずれを対象とするものであってもよい。経路探索には、通路をノードおよびリンクで表したネットワークデータを用いる。ネットワークデータに含まれるノードおよびリンクの少なくとも一部には、規制条件が付されており、ノードやリンクを通行する際に採りうる通行態様が時刻に応じて規制される。規制条件としては、例えば、交通機関のように所定の出発時刻にならないと利用できないという規制や、時間に応じて変化する通行禁止、一方通行、右左折禁止などの通行規制等が挙げられる。
【0008】
経路案内システムは、ネットワークデータに基づいて、まず、出発地から目的地に至る経路を探索した上で、経路上の各ノードへの到着予測時刻に基づいて規制条件に基づく待ち時間の有無を判断する。経路探索は、ノード、リンクに付されたコストが最小となる経路を求めるダイクストラ法など種々の方法を採ることができる。ダイクストラ法を用いる場合、リンクの距離に基づいてコストを設定することによって最短距離の経路を求めるようにしてもよいし、リンク間の移動の所要時間に基づいてコストを設定することによって最短時間の経路を求めるようにしてもよい。上述の経路探索は、規制条件を無視して行っても良いし、規制条件を考慮して行っても良い。後者の方法では、例えば、規制条件に基づいて待ち時間が発生する場合には、その待ち時間を所定の演算式でコストに反映させた上で経路探索する方法を採ることができる。後者の方法では、規制条件が付されたノード、リンクを通過する経路と、回避する迂回経路とを、規制ノードでの待ち時間も考慮した上で比較して経路を求めることができる利点がある。
【0009】
経路案内システムは、こうして探索された経路において待ち時間が要求される規制ノードが存在する場合には、出発地と規制ノードとの間で、最初に探索された経路よりも待ち時間が短くなる経路を探索する。この経路は、主として最初に探索された経路と異なる点を経由する経路となることが多いため、以下、説明の便宜上、経由経路と称するものとする。かかる経由経路は、例えば、最初に探索された経路のみを除外して、ダイクストラ法で経路探索をすることにより求めることができる。また、最初に探索された経路上にないいずれかのノードまたはリンクを経由地に指定し、この経由地を通る経路を求めるようにしてもよい。また、規制ノードでの待ち時間が短くなる経路であればよいから、最初に探索された経路上に存在するノードのうち、規制ノード以外のノードで待ち時間を費やすようにしてもよい。
【0010】
本発明によれば、規制ノードで待ち時間が生じた場合に、そこでの待ち時間を短縮させる代替経路を提示することができる。従って、規制ノードが待合いに適していない場合でも、実用的な経路を提示することが可能となる。
【0011】
ネットワークデータには、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報を付しても良い。待合場所適性情報は、例えば、ノードまたはリンクの属性として設定することができる。待合場所適性情報は、例えば、待合場所としての利用の「適」または「否」を表すフラグとしてもよいし、待合場所としての好適度を複数段階で表す指標値としてもよい。
【0012】
また、待合場所適性情報は、この好適度を間接的に表す情報とすることもできる。かかる情報としては、例えば、「フェリー乗り場」、「駅」など、ある程度の時間の待合いが前提とされている施設であることを示す属性情報、「喫茶店」や「レストラン」など、ある程度の時間を過ごすことが前提とされている施設であることを示す属性情報などを用いることができる。このような情報を用いる場合には、更に、上述の属性情報と、好適度を表す指標値との対応関係をテーブル等の形式で記憶した変換データベースを用意しておき、経路探索時には、この変換データベースに基づいて求まる指標値を用いるようにしてもよい。
【0013】
待合場所適性情報が用意されている場合、経路案内システムは待ち時間が要求される場合には、待合場所適性情報を利用して、規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する。待合ノードを選択する範囲は、任意に設定可能であり、例えば、規制ノードから所定の直線距離内にある範囲、規制ノードから所定の道のり内にある範囲、規制ノードから所定時間内で到達できる範囲、探索された経路上の各ノードから所定の直線距離内や所定の道のり内にある範囲、経路探索時に候補の経路として挙げられたノードの範囲内などとすることができる。
【0014】
経路案内システムは、こうして選択された待合ノードのそれぞれにつき、待合ノードを経由して規制ノードに至る経由経路を探索する。規制ノードが一カ所の場合には、経由経路は、出発地から待合ノードを経由して規制ノードに至る経路となる。規制ノードが複数ある場合は、出発地または直前の規制ノード通過後のいずれかのノードからの経由経路を求めるようにしてもよい。こうすれば、待合場所の経由経路を探索することにより、待ち時間が要求される時の経路案内の実用性、利便性を向上させることができる。
【0015】
上述の待合場所適性情報は、予めネットワークデータの一部として格納されるようにしてもよいし、ユーザがカスタマイズ可能としてもよい。ユーザが設定した待合場所適性情報は、例えば、予め用意されたネットワークデータとは分けて、ユーザ固有のユーザデータベースとして格納するようにしてもよい。ユーザがカスタマイズ可能とすることにより、ユーザの好みや要望に応じた待合場所を提示することが可能となる。例えば、時間に余裕があれば銀行や郵便局で所用を済ませようと考えているユーザは、予め銀行や郵便局に対して待合場所適性情報を設定しておくことにより、これらの所用を効率的に済ませられる経路を得ることが可能となる。
【0016】
こうした実用性をより向上させるため、待合場所適性情報をユーザがカスタマイズする際には、銀行等の位置を支点単位で個別具体的に指定するのではなく、「○○銀行」という単位での指定や、単に「銀行」という一般的な指定を許容してもよい。経路案内システムは、規制ノードから所定範囲内で、この一般的な指定の条件に該当する店舗等を検索し、そこを待合い場所に選択して経由経路を求めればよい。
【0017】
待合ノードが複数選択されている時、利用する待合ノードは、ユーザに選択させてもよいし、経路案内システムが自動的に決定してもよい。前者の態様では、例えば、待合ノードを地図上などに一覧表示し、ポインティングデバイス等でユーザに指定させる方法を採ることができる。待合ノードを地図上に表示する際には、経由経路の距離、所要時間、待合ノードでの待ち時間などを判断の際の目安としてユーザに提示するようにしても良い。
【0018】
待合ノードを自動的に決定する方法としては、例えば、経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて所定の演算により経由経路の評価値を算出し、この評価値に基づいていずれか一つの経由経路を選択する方法を採ることができる。評価値の算出式は任意に設定可能である。
【0019】
先に説明した通り、本発明では、少なくとも一部のノードに対して待合場所適性情報を付されている。この待合場所適性情報は、単に利用可否を表すデータとすることもできるし、利用の適否を複数段階の指標値で表すデータとすることができる。指標値は、任意に設定可能であるが、例えば、指標値が大きいほど待ち時間としての利用に適していることを表すものと定義してもよい。指標値は、待ち時間に関わらず一定値としてもよいし、待ち時間に応じて変化させるようにしてもよい。例えば、コンビニエンスストアは、待ち時間が短い場合には高い指標値とし、待ち時間が長くなるほど低い指標値に設定することができる。コンビニエンスストアは、気楽に利用でき、空調も整っている点で短時間の待合いには適しているが、座ることができないため長時間の待ち時間に対しては適しているとは言えないからである。
【0020】
このように複数段階の指標値が設定されている場合には、この指標値も用いて上述の評価値を算出し、待合ノードの選択を行うようにしてもよい。例えば、「評価値=所要時間+(待合ノードでの待ち時間/指標値)」のように、指標値は待合ノードでの待ち時間の重み係数として用いることができる。指標値を考慮することにより、より快適な環境で時間を過ごすことができる待合場所を提示することができ、経路案内システムの利便性を向上させることができる。
【0021】
待合場所適性情報には、待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含めてもよい。例えば、上述のコンビニエンスストアに対しては、座ることができないという点を考慮し、待ち時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待ち時間の下限値を設定することができる。このように待ち時間の上限値、下限値等が設定されている場合には、経路案内システムは、待合ノードでの待ち時間と、上限値および下限値の少なくとも一方との大小関係を考慮して待合ノードの選択を行ってもよい。こうすることにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【0022】
本発明の対象となる規制条件は、例えば、ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類することができる。例えば、交通機関の発車時刻は時刻規制条件に相当し、所定時間帯のみ通行止めが解除される規制などは時間帯規制条件に相当する。このように複数種類の規制条件が付されている場合、経路案内システムは、規制ノードに付されている規制条件が、時刻規制条件である場合と時間帯規制条件である場合とで、待合ノードの選択の方法を切り換えてもよい。例えば、時刻規制条件の場合、規制ノードへの到達時刻が予定時刻から遅れることは許されないため、規制ノードの近くに位置する待合ノードを優先して選択することが好ましい。一方、時間規制条件の場合については、規制ノードへの到達時刻に対する制約は比較的緩やかであるため、規制ノードからの距離よりも待ち時間を過ごす際の快適さを優先して待合ノードを選択することが好ましい。もっとも、ここで示したのは、待合ノードの選択方法の切り換えの一例に過ぎず、ここに例示した他、種々の選択方法を使い分けることが可能である。
【0023】
経路案内システムは、更に、出発地から規制ノードを回避して目的地に至る迂回経路を探索し、この迂回経路および経由経路のいずれかを出発地から目的地に至る経路として推奨するようにしてもよい。迂回経路および経由経路の選択は、それぞれの距離および所要時間の少なくとも一方に基づいて行うことができる。例えば、経路探索時に用いられるコストに換算し、迂回経路および経由経路のうちコストの小さい方を選択するようにすることができる。こうすることにより、待合場所への経由経路を採ることで目的地までの距離が迂回経路よりも長くなり、結果として不利な経路を選択したことになるという弊害を回避することが可能となる。
【0024】
経路案内システムは探索された経路を地図上に表示してユーザに案内するようにしてもよい。この場合には、経由経路とその他の経路とを異なる表示態様で表示する方法を採っても良い。こうすることにより、待合場所に向かうために目的地からそれた経路を案内されたとしても、ユーザはその意味を理解することができる利点がある。
【0025】
経由経路を表示する場合には、規制条件に基づき、待合ノードを出発すべき時刻をユーザに報知するようにしてもよい。報知は、画面上の表示や音声出力など、種々の方法で行うことができる。かかる報知により、ユーザは待合場所で安心して時間を過ごすことが可能となる。
【0026】
また、経由経路を案内する場合には、規制ノードに到達すべき到達時刻、または到達時刻までの余裕時間をユーザに提示するようにしてもよい。こうすることで、ユーザは規制ノードでの規制条件を考慮して、移動速度を調整することができ、規制条件による制約を無理なく回避して経路を通行することが可能となる。
【0027】
本発明は、上述の特徴を必ずしも全て備えている必要はない。上述の特徴は、適宜、一部を省略したり、組み合わせたりすることが可能である。また、本発明は、上述した経路案内システムとしての構成の他、コンピュータによって経路探索や経路案内を行う経路探索方法、経路案内方法の態様を採ることもできる。本発明は、更に、これらの機能を実現するためのコンピュータプログラム、かかるコンピュータプログラムを記録した記録媒体の態様を採ることもできる。記録媒体としては、フレキシブルディスクやCD−ROM、光磁気ディスク、ICカード、ROMカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置(RAMやROMなどのメモリ)および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【0028】
本発明の実施例について以下の順序で説明する。
A.システム構成:
B.データ構造:
C.経路探索:
C1.経路探索処理例:
C2.経路探索処理:
C3.経由経路設定処理:
C4.変形例:
D.経路案内:
【0029】
A.システム構成:
図1は実施例としての経路案内システムの構成を示す説明図である。本実施例では、歩行者用の経路案内システムとしての構成例を示すが、車両用の経路案内システムとして構成することもできる。経路案内システムは、携帯電話を利用した端末100とサーバ200とをネットワークINTで接続して構成されている。ネットワークINTは無線通信を利用したネットワークであり、LANやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。端末100は、携帯電話の他、いわゆる車両用のナビゲーション装置やPDA、ネットワーク通信機能を有するパーソナルコンピュータなどを利用することができる。歩行者用の経路案内システムとして構成する場合、車両用のナビゲーション装置は、車両から取り外して携帯可能としておくことが望ましい。
【0030】
端末100は、ユーザの操作に応じて、経路探索および経路案内に必要な指示をサーバ200に送信するための機能を奏する。図中には、端末100の機能ブロックを併せて示した。端末100は、CPU、RAM、ROMを備えたマイクロコンピュータを制御装置として内蔵しており、このCPUはROMに記憶されたソフトウェアを実行することで、図示する各機能ブロックを構成する。これらの機能ブロックは、このようにソフトウェア的に構成する他、ハードウェア的に構成することも可能である。
【0031】
通信部120は、ネットワークINTを介してサーバ200と通信する機能を奏する。GPS140は、全地球測位システム(Global Positioning System)を利用して、端末100の現在位置の緯度、経度を検出する。コマンド入力部130は、スイッチ等に対するユーザ操作に基づいて、経路探索や経路案内に関するコマンドを入力する。コマンドとしては、図示した通り、経路探索の目的地の指定、案内経路の選択などが挙げられる。表示制御部150は、端末100のディスプレイに、これらのコマンド入力用のメニューを表示したり、サーバ200から受信した経路案内データに基づいて地図を表示させたりする。主制御部110は、上述した各機能ブロックを統括制御することで、端末100の全体機能を制御する。
【0032】
サーバ200は、端末100からのコマンドに基づいて、種々のデータベースを参照しながら、経路探索を行ったり、経路案内を行ったりする。図中には、これらの機能を実現するための機能ブロックおよびデータベースの例を示した。各機能ブロックは、サーバ200のCPUが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【0033】
サーバ200が利用するデータベースは地図DB250、時刻表DB252、ユーザDB254の3種類である。地図DB250は、通路をノード、リンクで表したネットワークデータ、および地図描画用のポリゴンや文字データからなる描画データを有している。本実施例では、ノードおよびリンクの少なくとも一部には、許容される通行態様が時刻によって変化するものが存在する。この規制条件としては、例えば、出発時刻が規定されている公共交通機関、所定時刻になると閉鎖される駅構内の通路などが挙げられる。時刻表DB252は、この規制条件を記録するデータベースである。地図DB250および時刻表DB252のデータ構造については後述する。
【0034】
ユーザDB254は、ユーザID、氏名などの書誌的な登録情報と共に、ユーザが歩行する際の移動速度に関する設定や、距離優先/時間優先などの経路探索に関する要望事項を格納している。図中にはユーザDB254の内容として移動速度に関する登録内容を例示した。本実施例では、移動速度は、移動可能な距離と組み合わせて登録されている。図中の例では、通常利用される移動速度(以下、「通常速度」と呼ぶこともある)は「4km/h」であり、移動可能な距離には制約がないことを表している。やや早足の「5km/h」では、3kmまで移動可能であり、駆け足の「10km/h」では0.5kmまで移動可能であることを表している。これらの情報は、ユーザが端末100を操作して登録、変更可能である。図中の例では、3通りの移動速度が登録されているが、更に多くの移動速度を登録可能としてもよい。
【0035】
通信部220は、端末100とのネットワークINT経由での通信を制御する。経路探索部230は、上述の3種類のデータベースを参照して、ユーザから指定された出発地、目的地間の経路を探索する。経路探索部230は、ユーザからの指示に応じて、移動速度などの探索条件を複数種類に変化させ、それぞれの条件に対応する経路を探索することが可能である。また、時刻表DB252を参照することにより、上述の規制条件も考慮して経路探索を行う。経路探索方法については後述する。
【0036】
経路案内部240は、探索された経路を地図上に表示して案内するための経路案内データを生成し、端末100に送信する。上述の通り、経路探索は、種々の探索条件に基づいて行われ、規制条件も考慮して行われている。経路案内部240は、これらの条件を反映した案内表示を実現する。経路案内方法については後述する。
【0037】
B.データ構造:
図2は地図DB250および時刻表DB252のデータ構造を示す説明図である。地図DB250については、経路探索用のネットワークデータの構造のみを例示した。図の中央に例示するように、ネットワークデータは、ノードN1〜N8およびリンクL1〜L9等で構成される。リンクL1〜L9は歩行者が通行可能な通路を表しており、ノードN1〜N8はリンクL1〜L9の端点または接続点を表している。
【0038】
地図DB250は、上述のノード、リンクに関するデータを、それぞれノードデータ250N、リンクデータ250Lとして格納している。図中に示す通り、リンクデータ250Lには、リンクID、形状、時刻表、速度規制、距離などの情報が記録される。形状は、リンクが通過する地点の座標(緯度、経路)を表した点列データである。座標には、高さを表す情報を含めても良い。図中の例では、リンクL9について、ノードN2、N7を含む4点が格納されている。本実施例では、ノードについてはノードIDを格納し、その位置はノードデータ250Nを参照することで得られるようにしたが、ノードについても他の通過地点と同じく座標を格納するようにしてもよい。時刻表とは、時刻表DBに格納されている情報へのリンクを表している。図中の例L9では、時刻に応じて変化する規制条件が付されていないため、時刻表の項目には「無し」が登録されている。後述するように、リンクL3、L4、L6のように時刻に応じて変化する規制条件が付されている場合には、時刻表DB252に格納されているデータのインデックスである「時刻表ID」が格納されることになる。速度規制とは、そのリンクを通行する際の上限速度を表している。距離とは、そのリンクの区間距離である。
【0039】
リンクデータ250Lの内容は、任意に設定可能であり、これらの情報の一部を省略してもよいし、ここに例示していない種々の属性情報を格納するようにしてもよい。例えば、階段や坂道などの経路種別や、ガードレールや街灯などの設備の有無等を属性情報として格納することができる。かかる属性情報が用意されている場合には、「階段を避けたい」、「ガードレールが整備されている経路を優先したい」などの経路に対する要望事項を反映した経路探索を実行することが可能となる。例えば、「階段を避けたい」という要望が出されている場合には、「階段」という属性情報が記録されているリンクのコストを増加させることによって、階段が選択される可能性を抑制することが可能となり、要望に沿った経路を探索することが可能となる。
【0040】
ノードデータ250Nには、図示するようにノードID、位置、時刻表、通行規制、待合好適度、待合許容時間などの情報が記録される。「喫茶店」、「コンビニエンスストア」、「銀行」、「郵便局」などノードの種別を表す情報を含めてもよい。ノードの位置は、緯度、経度の座標で記録される。座標には、高さを表す情報を含めても良い。時刻表は、リンクデータ250Lと同様、時刻表DB252に格納されている情報へのリンクを表している。通行規制とは、右左折禁止など、時刻に応じて変化しない固定的な通行規制である。例えば、図中のノードN4について、N3方向から来てN6方向へ左折する通行が禁止される場合には、通行規制欄には、「N3→N4→N6」という形でデータを格納すればよい。通行規制情報の記録方法は、これに限らず、種々の形式を採用することができる。
【0041】
待合好適度とは、探索された経路において規制条件による待ち時間が生じた場合、その時間経過を待つ待合場所としての適性を表す指標であり、後述する通り、複数の待合場所の中から、案内対象とすべき待合場所を選択する際に用いられる値である。本実施例では、適性を0〜5の6段階の整数値で表すものとした。待合好適度「0」は、待合場所として使用できない場所を表しており、値が大きくなるほど待合に適していることを表している。待合好適度「0」に該当し得る場所としては、例えば、自動車用の案内装置では交差点の中央などが当たり、歩行者用の案内では駅の改札口、エレベータ、エスカレータなどが当たり得る。
【0042】
待合許容時間とは、待合場所としての使用が許容される下限値および上限値を表す。待合許容時間も、後述する通り、複数の待合場所の中から、案内対象とすべき場所を選択する際の基準として用いられる値であるから、ユーザの要望に添った選択結果となるよう任意に設定することができる。従って、待合許容時間は、必ずしも明確な規制条件である必要はなく、ユーザの体力的な限界や心理的な限界を考慮した一般的な許容範囲で構わない。例えば、コンビニエンスストアに対応するノードに対しては、座ることができないという点を考慮し、待合許容時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対応するノードに対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待合許容時間の下限値を設定することができる。
【0043】
待合好適度や待合許容時間は、ノードの属性として格納する他、リンクの属性として格納してもよい。また、本実施例では、上述のように待合好適度を直接に表す場合を例示しているが、「フェリー乗り場」や「駅」などのように待合場所としての適性を推測可能な情報を待合孔適度として用いるようにしてもよい。
【0044】
また、待合好適度や待合許容時間は、予め地図DB250に組み込まれている情報の他、ユーザが任意に設定可能としてもよい。この情報は、地図DB250に直接登録可能としてもよいが、ユーザごとに設定内容を管理可能とするため、ユーザDB254(図1参照)に登録可能とすることが好ましい。ユーザの設定内容には、ノードIDに代えて、「銀行」、「郵便局」などノードの種別を表す情報を用いるようにしてもよい。例えば、「銀行」に対し、「待合好適度=5」、「待合許容時間=20〜30分」などのように設定する方法を採ることができる。後述する経路探索処理時には、サーバ200は、「銀行」に該当する種別情報を有するノードを検索することによって、ユーザが設定した内容を特定のノードに対する待合好適度、待合許容時間と同視して取り扱うことができる。
【0045】
時刻表DB252には、時刻表ID、規制、時刻、開始遅れ、終了遅れなどの情報が格納されている。時刻表IDは、登録されているそれぞれの情報を一義的に示すための識別データである。規制は、時刻表IDが示す規制情報を表している。図中には、駅の入り口G1〜G3が午前0:30〜午前4:30の間で閉鎖され、駅構内のリンクL3,L4,L6が通行不能となる場合のデータを例示した。この場合、通行不能となるため、「規制」欄には、「通行止め」が格納され、時刻欄には、通行止めとなる時刻が格納される。複数の時間帯で通行止めとなる場合には、時刻欄に、複数の時間帯を格納することもできる。開始遅れは、この時間帯の開始時刻(図中の例では0:30)が遅れる可能性を示し、終了遅れは終了時刻が遅れる可能性を示している。駅構内の通行止めについては、規定通りに閉鎖されるため、開始遅れ、終了遅れは「無し」と設定されている。「時刻表ID=1」が付されたこのデータは、リンクL3、L4、L6に適用される。従って、リンクデータ250LのこれらのリンクIDに対応するデータの「時刻表」欄に「1」が格納されることになる。リンクデータの時刻表欄には、複数の時刻表IDを格納可能としてもよい。
【0046】
時刻表DB252には、上述のような「通行止め」の規制の他、種々の規制が格納可能である。例えば、本実施例では、電車などの交通機関の出発時刻も、その路線を通行可能な時間帯が限られているという意味で規制条件の一種とみなし、時刻表DB252で管理するものとした。この場合には、「規制」欄には、例えば、「電車発着」などと格納することで交通機関であることを示し、「時刻」欄に出発時刻および到着時刻からなる時刻表を格納することができる。出発時刻と途中の経過駅までの所要時間という形式で格納するようにしてもよい。交通機関の場合には、出発時間や到着時間が遅れる場合がある。出発時間の遅れは「開始遅れ」に記録し、到着時間の遅れは「終了遅れ」に記録することができる。これらの時間は、後述する通り、経路探索時に考慮される値であり、任意に設定可能であるが、一例として、過去所定期間内の平均遅れ時間や最大遅れ時間などに基づいて設定することができる。
【0047】
C.経路探索:
本実施例における経路探索処理について説明する。まず、いくつかの具体例に基づいて処理概要を説明した後、経路探索処理を実現するためのフローチャートを説明する。
【0048】
C1.経路探索処理例:
図3は経路探索処理例を示す説明図である。図中に経路探索の対象となるノード、リンクの構成を例示した。丸印はノードを表し、実線はリンクを表している。以後、ノードは丸印中の文字を用いて特定し、リンクはその両端のノードを用いて表す。例えば、ノードSとノードAとの間のリンクはリンクSAまたはリンクASを表すものとする。各リンクに付された数字は、リンク間の移動に要する所要時間である。移動の所要時間は、ユーザの移動速度に応じて変化する。本実施例では、ユーザDB254に登録された通常速度(図1では4km/h)を用いるものとした。経路探索時に用いる移動速度は、通常速度、最大速度などをユーザが選択可能としてもよいし、経路途中にある規制条件による制約を最も効率的に回避し得るようユーザDB254を参照しながら経路案内システムが設定してもよい。
【0049】
図示したネットワークデータを用いて、出発地Sを午前5:00に出発し、目的地Gに向かう所要時間最短の経路を探索する場合を考える。経路探索は、所要時間をコストとするダイクストラ法によって行うものとする。ダイクストラ法とは、各リンクに付されたコストの総和が最小となる経路を求める演算方法である。この例では、所要時間をコストとして用いるが、この他、リンクの距離をコストとして用いたり、所要時間や距離その他の情報を考慮して設定されたコストを用いたりすることも可能である。
【0050】
ダイクストラ法の演算方法は周知であるため処理内容自体についての説明は省略し、結果概要のみを説明する。図の例で、出発地Sをスタートし、途中のノードBまで至る経路とそのコストは、それぞれ次の通りとなる。
経路S→A→H→B …コスト=40;
経路S→A→B …コスト=22;
経路S→A→E→F→B…コスト=30;
従って、ノードBに至る最適経路は、経路S→A→Bと求まる。この結果、ノードCに至る最適経路は、経路S→A→B→Cと求まる。この経路を採用した場合、ノードCへの到達時刻は5:30と予測される。
【0051】
図中に示す通り、リンクCDには夜間20:00〜6:00は通行止めとなる規制条件が付されている。従って、ノードCに5:30に到達した時点では、リンクCDを通行することはできない。以下、このように通行する時刻または時間帯が規制されているノードを規制ノードと称する。図の例では、リンクCD間に規制条件が付されているが、出発地Sから目的地Gに向かう経路探索時にはノードCにおいてのみ規制条件が問題となるため、ノードCのみが規制ノードに該当する。
【0052】
規制ノードCから先の経路としては、「C→I→D」の迂回経路と、ノードCで通行規制が解除されるまで待った上で「C→D」と通行する経路とがある。迂回経路のコストは70である。ノードCで待つ場合には、ノードCでの待ち時間30分を、リンクCDのコストに反映した上で、経路のコストを算出する。この結果、「C→D」のコストは50となる。従って、ノードCで30分の待ち時間が生じたとしても、迂回経路よりは経路「C→D」の方がコスト小となることが分かる。
【0053】
以上の探索処理の結果、図3の例によれば、「出発地S→A→B→C→D→目的地G」という経路(図中、太線で示した経路)がコスト最小、即ち所要時間最短となる経路として求められる。この経路を採った場合には、ノードCで30分の待ち時間が生じることが分かる。本実施例では、このように待ち時間が生じた場合には、以下に示す処理によって、待合場所を特定し、待合場所を経由する経由経路を案内する。
【0054】
図4は待合場所の抽出処理例を示す説明図である。リンクCDを通過するための待合場所であるから、待合場所は、出発地S〜ノードCの間で探索される必要がある。以下では、図3に示した経路のうち、出発地S〜ノードC間のみを示す。この例では、規制ノードは、ノードCの1カ所のみであるが、仮にリンクDG上に、更に規制ノードJ(図示せず)が存在する場合には、規制ノードCと規制ノードJとの間で、以下の処理と同様の処理によって待合場所が探索されることになる。
【0055】
サーバ200は、図示するように、規制ノードCから所定範囲内で待合場所の候補となるノード(以下、待合ノードと称する)を抽出する。この抽出処理には、図2で示したノードデータ250Nの待合好適度が用いられる。待合好適度が所定値以上のノードを選択すればよい。値1以上を選択すれば広範に待合ノードが抽出されるし、更に高い待合好適度を要求すれば、候補となる待合ノード数は減少するものの待合いに快適な場所が抽出されることになる。
【0056】
待合ノードを抽出する範囲は、種々の条件で規定することができる。例えば、1)図3に示した経路探索の過程で経路候補として挙げられたノードの範囲内、2)規制ノードから所定の所要時間内に到達可能な範囲、3)規定ノードから所定の道のり内、4)規定ノードから所定の直線距離内などの条件を用いることができる。図4では、条件1を用いた場合を例示した。この結果、待合ノードとして、図中に二重丸で示す4カ所、即ち出発地S、コンビニエンスストアE、喫茶店H、目的地Cが選択されたとする。次に、これらの各待合ノードを経由する経由経路を求め、待合場所としての適否を判断する処理例を示す。
【0057】
図5は出発地Sを待合場所とした場合の経由経路を示す説明図である。経由経路を得るには、出発地から待合ノードまでの経路、待合ノードから規制ノードCまでの経路をそれぞれダイクストラ法で求めればよい。図5の例では、出発地と待合ノードが同一であるため、経由経路は図3で得られる経路と同一の経路「S→A→B→C」(図中の太線)となる。本実施例では、待合ノードを選択する際の第1の指標として、この経由経路の所要時間を求める。この例では30分となる。
【0058】
そして、第2の指標として、余裕時間、即ち待合ノードで過ごす時間を求める。余裕時間は次式によって求めることができる。
余裕時間=規制ノードCでの待ち時間−余剰時間;
余剰時間=経由経路の所要時間−規制ノードCまでの本来の経路の所要時間(図3で得られた経路の所要時間);
図5の例では、余裕時間は30分となる。
【0059】
そして、所要時間、余裕時間、待合好適度を用いて次式により、待合ノードおよび経由経路の評価値を求める。
評価値=所要時間+(余裕時間/待合好適度);
図5の例では、評価値は60となる。この評価値は値が小さいほど好ましい経由経路であることを表している。評価値の内容は、経由経路を採ることによる所要時間の増大というデメリットと、快適な場所で待ち時間を過ごすことによるメリットとを加味した値となっている。待合好適度は、余裕時間を過ごす際の評価値の増加を抑制する因子として作用する。従って、この評価値を用いれば、待合好適度が高い快適な場所であれば、若干、所要時間が増大したとしても経由する価値があるという評価が得られることになる。評価値は任意に設定可能であり、所要時間に代えて、先に説明した余剰時間を用いても良い。また、所要時間や余剰時間にも重み係数を乗じるようにしてもよい。
【0060】
図6はコンビニエンスストアEを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→E→F→B→C」が得られる。この経由経路の所要時間は38分であり、余裕時間は22分となる。コンビニエンスストアの待合高適度は「2」と設定されているから、評価値は49と求められる。
【0061】
図7は喫茶店Hを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→H→B→C」が得られる。この経由経路の所要時間は48分であり、余裕時間は12分となる。喫茶店Hの待合高適度は「4」と設定されているから、評価値は51と求められる。
【0062】
図8は規制ノードCを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→B→C」が得られる。この経由経路の所要時間は30分であり、余裕時間は30分となる。規制ノードCの待合高適度は「1」と設定されているから、評価値は60と求められる。
【0063】
図5〜8で示した結果を比較すると、評価値は次の通りとなる。
(図5のケース)待合ノード=S … 評価値=60;
(図6のケース)待合ノード=E … 評価値=49;
(図7のケース)待合ノード=H … 評価値=51;
(図8のケース)待合ノード=C … 評価値=60;
従って、これらの中では、図6のケース、即ちコンビニエンスストアEを待合場所とする経路が推奨経路となる。図7のケース、即ち喫茶店Hを待合場所とする場合が推奨経路とならないのは、待合好適度は大きいため、待ち時間の過ごしやすさという点では優れるものの、場所が遠く、喫茶店Hを経由する際の所要時間が増大することが原因と言える。当然、評価値の演算方法次第で、これらの結果は変動する。先に述べた通り、評価値の演算方法は、ユーザの要望に沿った実用性、利便性の高い待合場所が得られるよう、任意に設定すればよい。
【0064】
C2.経路探索処理:
図9は経路探索処理のフローチャートである。図3〜8で具体的に示した経路探索を実現するための処理例である。この処理は、サーバ200の経路探索部230(図1参照)が実行する処理であり、ハードウェア的にはサーバ200のCPUが実行する処理である。
【0065】
CPUは最初に、端末100からユーザID、出発地、目的地、出発時刻の指定を入力する(ステップS10)。この他、経路探索に関するユーザの要望事項を入力するようにしてもよい。例えば、経路に対して、階段や坂道を回避するという移動負荷に関する要望や、ガードレールや街灯が整備されている通路を優先するというような安全性に関する要望を指定可能としてもよい。
【0066】
次に、CPUは規制条件を考慮して経路探索を実施する(ステップS21)。ダイクストラ法による具体的な処理方法は周知であるため、ここでは詳細な説明は省略し、図中に経路探索の主要な処理内容を示した。経路探索において、CPUはまず従前の処理で探索された経路候補の先端のノードから更に分岐して経路を延伸させる経路候補を設定する(ステップS21)。次に、各ノードに至るまでのコストを算出して、そのコストおよび従前の経路を記録したラベルを設定していく。例えば、各リンクの距離を移動速度、即ちユーザの通常速度で割ることで所要時間を算出し、その所要時間をコストとして利用するという方法を採ることができる。コストは、この方法に限らず図3で説明したように種々の値を用いることができる。本実施例では、上述の処理で得られた所要時間を用いて各ノードへの到達時刻を予測する(ステップS22)。
【0067】
また、経路探索過程で、規制ノードが存在する場合には、時刻表DBを読み出し、上述の到達時刻に基づいて規制ノードでの待ち時間を算出し、この規制が関連するリンクのコストへ反映させる(ステップS23)。図中にこの処理の例を示した。図示するように、リンクCDに規制条件が付されており、ノードCに規制が解除される30分前に到達する場合には、待ち時間30分がリンクCDに反映される。ノードCから上述の規制とは無関係の迂回路が存在する場合には、この迂回路に対応するリンクには待ち時間分のコストは反映されない。所要時間をコストとして用いている場合には、待ち時間をリンクCDのコストに加えればよい。距離をコストとして用いている場合には、待ち時間に移動速度を乗じるなどの方法で距離に換算して加えることで、コストを反映させることができる。待ち時間の反映方法は、このようにコストの設定方法に応じて定められる。
【0068】
CPUは以上で得られたコストを用いて最小コストとなる経路を求める(ステップS24)。この処理を目的地に到達するまで繰り返し実行することで、図3に示したように、待合ノードの経由を考慮しない経路(以下、本来経路と称する)が得られる。
【0069】
こうして本来経路が得られると、CPUは規制ノードでの待ち時間を過ごす待合場所を経由する経由経路を設定するための処理、経由経路設定処理を実行する(ステップS100)。この処理は、先に図4〜8で示した処理である。具体的な処理のフローチャートは後で示す。この処理によって、種々の待合場所を経由する経路のうち、いずれか一つの待合場所を経由する経由経路が選択される。
【0070】
CPUは、次に、規制ノードを通過しない迂回経路を求め、この迂回経路と選択された経由経路のコストを比較し、いずれか小さい方を案内対象として選択する(ステップS200)。例えば、経由経路を採り本来経路よりも移動距離が過剰に長くなる場合などには、経由経路よりも迂回経路の方が好適と判断される逆転現象が生じる可能性もある。ただし、経路の所要時間をコストとして用いる場合には、かかる逆転現象は生じ得ない。経由経路を採る場合でも、規制ノードに到達する時刻は本来経路と一致するからである。ステップS200は任意の処理であり、所要時間をコストとして用いる場合も含め、適宜、省略しても差し支えない。
【0071】
C3.経由経路設定処理:
図10は経由経路設定処理のフローチャートである。先に図4〜8で示した処理例を実現するための処理であり、図9のステップS100に相当する処理である。
【0072】
この処理が開始されると、CPUは規制ノード周辺の待合場所を抽出する(ステップS102)。この抽出は、先に図4で説明した手順で実行することができる。この抽出時には、予め地図DB250に設定されている待合好適度とともに、またはこの待合好適度に代えて、ユーザが設定した待合好適度を参照するようにしてもよい。こうすることで、先に図2で説明したように、ユーザが「銀行」に対して待合好適度および待合許容時間を設定している場合には、銀行を経由する経由経路を求めることが可能となる。この結果、空き時間ができたら銀行で所用を済ませたいと考えているユーザに対して、要望に沿った効率的な経路を提示することが可能となる。
【0073】
次に、CPUは待合場所の選択モードに応じて、待合場所および経由経路を設定するための処理を実行する(ステップS104)。本実施例では、手動と自動の二つの選択モードを設けた。選択モードの指定は、ステップS104を実行する時点で、ユーザに問い合わせるようにしてもよいし、ユーザDB254(図1参照)に予め登録しておくようにしてもよい。
【0074】
自動選択モードが選択される場合には、CPUは、抽出されている各待合場所に対して、経由経路を探索し、所要時間、余裕時間を求め(ステップS112)、経由経路の評価値を算出する(ステップS114)。これらの処理は、図5〜8で説明した処理に相当する。
【0075】
CPUは、こうして得られた評価値に基づき評価値が最小となるという第1の条件に基づき、待合場所および経由経路を選択し(ステップS116)、経由経路設定処理を終了する。この選択時には、更に余裕時間が待合許容時間内という第2の条件を付しても良い。例えば、図5〜8の例で、喫茶店Hは余裕時間12分と求められている。喫茶店Hについて、仮に待合許容時間の下限値が15分と設定されているとすれば、この余裕時間は待合許容時間の下限値を下回っていることになる。従って、第2の条件を考慮すると、喫茶店Hは評価値を考慮するまでなく、待合場所から除外されることになる。第2の条件を考慮することにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【0076】
手動選択モードが選択される場合には(ステップS104)、CPUは、待合場所を端末100の画面上に地図とともに表示し、いずれかの待合場所を選択するユーザの指示を入力する(ステップS122)。この処理においても、自動選択モードの場合と同様、ユーザが設定した待合好適度を考慮して待合場所を提示するようにしてもよい。地図上の待合場所をクリッカブルにしておき、ユーザがポインティングデバイスでいずれかの待合場所をクリックすることで選択する方法を採ることができる。待合場所に番号を付し、キーボードでこの番号を指定するようにしてもよい。
【0077】
次に、CPUは選択された待合場所を経由する経由経路を探索し、その所要時間、余裕時間を求め、ユーザが経由経路の適否を判断するための目安となる情報として、端末100の画面上に提示する(ステップS124)。図中に画面例DISP1を示した。一例として、図示するように、経由すべき待合場所の付近にウィンドウを設け、所要時間、余裕時間を表示する態様を採ることができる。ユーザが「待合場所選択」ボタンを押すと(ステップS126)、CPUは再び待合場所の表示処理を実行する(ステップS122)。ユーザが「OK」ボタンを押すと(ステップS126)、CPUは経由経路設定処理を終了する。手動選択モードでは、最適か否かの評価は行わず、ユーザが選択した経由経路を選択することになる。
【0078】
C4.変形例:
図10の例では、自動選択モードで経路を選択する際に、「評価値最小となる経由経路を選択」という第1の条件のみ、または第1の条件および「余裕時間が待合許容時間内」という第2の条件の双方を画一的に使用する場合を例示した。これに対し以下に示すように、規制条件の種類に応じて経路を選択するための条件を使い分けるようにしてもよい。
【0079】
規制条件には、例えば、交通機関の発車時刻のように、通行するためには特定の時刻に規制ノードに到達していることが要求されるものがある。以下、かかる規制条件を時刻規制条件と呼ぶ。別の規制条件として、例えば、所定の時間帯のみ通行止めされる規制のように、通行するためには特定の時間帯に規制ノードに到達していれば足りるものがある。以下、かかる規制条件を時間規制と呼ぶ。規制ノードに到達する時刻に対する要求という点では、時刻規制の方が時間規制よりも厳しいと言える。
【0080】
経由経路設定処理では、時刻規制と時間規制の差違を考慮し、両者でステップS116における選択の基準を変えても良い。例えば、規制ノードに時刻規制が付されている場合には、ステップS116において規制ノードに近いことを重視する選択条件とすることができる。規制ノードに近い待合場所の方が、規制ノードへの到達時刻に対する要求を満足しやすいからである。上述の条件としては、例えば、ステップS116に示した条件に加え、規制ノードからの所要時間、道のり、直線距離のいずれかを制限する条件を考慮する方法が挙げられる。または、評価値を算出する際に、所要時間を、待合場所に至るまでの所要時間、待合場所から規制ノードに至るまでの所要時間に分け、後者に1以上の重み値を乗じるようにしてもよい。
【0081】
D.経路案内:
図11は経路案内処理のフローチャートである。図9で説明した経路探索処理の結果をユーザに提示するための案内データを生成し、端末100に送信する処理である。経路案内は、端末100の画面表示や音声出力などで行うことができる。経路案内処理は、サーバ200の経路案内部240が実行する処理であり、ハードウェア的にはサーバ200のCPUが実行する処理である。
【0082】
この処理では、CPUは、経路案内データを読込む(ステップS200)。経路探索処理では案内対象となる経路を一つに絞らずに、ステップS200の時点で経路案内データを複数読み込み、その一覧をユーザに提示して、案内対象となる経路をユーザに選択させてもよい。
【0083】
経路案内データが読み込まれると、CPUは端末100から現在位置を入力し(ステップS202)、経路案内用の画面を表示する。まず、CPUは現在位置と待合場所との位置関係によって待合中か否かを判断し(ステップS204)、待合中と判断される場合には出発時刻報知処理を行う(ステップS206)。この処理は、規制条件に基づいて設定された予定時刻に規制ノードに到着するために、待合場所を出発すべき時刻をユーザに知らせる処理である。出発時刻は、予定時刻よりも、待合場所から規制ノードまでの所要時間だけ遡った時刻、または更に若干の余裕を見込んだ時刻とすることができる。出発時刻に至る前の時点では、CPUは、出発予定時刻を画面上に表示する。現在時刻が出発時刻になると、CPUはユーザに音声や画面表示で、出発すべき旨を報知する。待合中でない場合には(ステップS204)、出発時刻報知処理はスキップされる。
【0084】
次に、CPUは経路途中に規制ノードがあるか否かを判断する(ステップS208)。規制ノードがある場合には、規制条件による制約を回避して通行するための残時間を表示する(ステップS210)。残時間の表示は、規制ノードに向かう際にユーザが移動速度を調整する際の目安として行うものである。残時間の表示は、待合場所を出発してから規制ノードに至るまでの間でのみ行うようにしてもよい。規制ノードがない場合には、この処理はスキップされる。
【0085】
CPUは以上で設定された画面とともに、地図上に経路および現在位置を表示して、経路案内を行う(ステップS212)。CPUは以上の処理を目的地に到達するまで繰り返し実行する(ステップS214)。
【0086】
図12は経路案内の表示画面を例示する説明図である。案内画面DISP2は端末100のディスプレイ上に表示される。図中の黒丸が現在位置PPである。案内画面DISP2では、図示するように現在位置PPを含む地図が表示され、そこに経路R1〜R3が表示される。本実施例では、経由経路、規制条件が付されている箇所、およびその他の経路で表示パターンを変化させるものとした。図中の経路R1は、クロスハッチにより、経由経路であることを表している。この表示により、ユーザは案内されている経路が経由経路であることを容易に認識できるため、本来の目的地と離れた方向に案内が行われている場合でも、安心して案内に従うことができる。
【0087】
経由経路R2は、ハッチングによって、時刻によって通行止めになるなどの規制条件が付されている箇所であることを表している。この表示により、ユーザは経由経路が要求される理由を容易に把握することができる。矢印で示した経路R3は、通常速度での移動で足り、規制条件も付されていないことを表している。経路R1〜R3の表示態様は、ここに例示したものに限られず、任意に設定可能である。これらの表示パターンの使い分けの少なくとも一部を省略してもよいし、更に詳細な使い分けを行うようにしてもよい。
【0088】
図中の例では、領域Aは駅STAの構内であり、20:00〜6:00の時間帯で通行止めになるという規制条件が付されている。経由経路R1が要求されるのは、この規制条件が解除されるのを待って駅構内を通行するためである。経由経路R1上には、待合場所となるコンビニエンスストアが表示される。この待合場所をユーザがクリックすると、ポップアップウィンドウW4が表れ、待合場所での余裕時間と、待合場所を出発すべき出発時刻が表示される。ポップアップウィンドウW4は、ユーザが待合場所にいる場合には、出発時刻を報知するために(図11のステップS206参照)ユーザの操作を行うまでなく表示させるようにしてもよい。
【0089】
本実施例では、更に領域Aのように規制条件が付されている箇所をクリッカブルとし、薄いハッチングを付すなど、通常の建造物とは異なる表示態様で表示させるものとした。ユーザが領域Aをクリックすると、ポップアップウィンドウW2が表示され、図示するように規制条件が表示される。駅STAについても同様に、ポップアップウィンドウW3を表示し、図示するように電車の時刻表を規制条件として表示可能としてもよい。ユーザはこれらの情報に基づき、待合場所での余裕時間や出発時刻の根拠を理解することができ、状況に応じて自身の判断で出発時刻を調整等することが可能となる。
【0090】
本実施例では、規制条件が付された領域Aに向かう過程では、サブウィンドウW1も表示するものとした。このサブウィンドウW1では、規制条件による制約を回避するために許される残時間を表示する(図11のステップS210参照)。図の例では、6:00に領域Aに到達すればよく、サブウィンドウW1の表示によれば、残り時間が4分20秒あることが分かる。領域Aのように通行止めが解除される場合には、残り時間4分20秒以内に領域Aに到達しても無用な待ち時間が生じるに過ぎない。この場合、残り時間は、ユーザに過度に急いでも無意味であることを表す情報となる。サブウィンドウW1では、亀のマークを表示させることによって、このような残り時間、即ちこの時間よりも早く到着しても有意義とは言えない時間が表示されていることを示している。
【0091】
一方、ユーザが駅STAに向かっている場合には、発車時刻に間に合うように駅STAに到達する必要がある。かかる場合には、残り時間は、ユーザが駅STAに到達するまでの所要時間の上限値を表す情報となる。かかる場合には、サブウィンドウW1に代えて、サブウィンドウW1aに示すように、ハートマークを表示させ、ユーザに残り時間が限られていることを認識させるようにしてもよい。これらサブウィンドウW1、W1aの表示によって、ユーザは自己の移動速度を適宜調整しながら、過度な負荷をかけずに移動することが可能となる。
【0092】
サーバ200は、ユーザの現在位置の履歴から移動速度を変化し、現在の移動速度を維持した場合の規制ノードへの到達時刻を予測することができる。サブウィンドウW1aを表示する際には、この予測に基づき、ユーザに移動速度を速めたり、ゆっくりさせたりする指示を与えるようにしてもよい。例えば、ハートマークの点滅間隔を縮めることによりペースアップを指示し、点滅間隔をのばすことによりペースダウンを指示する方法を採ることができる。
【0093】
経路R2は規制条件が付された箇所であることを表してはいるが、所定時刻までの通過が要求されている訳ではない。また、経路R3も通常速度での移動で足りる。従って、現在位置PPが経路R2、R3上にある時には、サブウィンドウW1、W1aは非表示となる。このように、規制条件が付された領域に向かう場合にのみサブウィンドウW1、W1aを表示することによって、ユーザの注意をより確実に喚起することができる利点がある。
【0094】
以上で説明した本実施例の経路案内システムによれば、規制条件によって待ち時間が生じた場合に、待合場所およびその待合場所を経由する経由経路を案内することができ、実用性、利便性に優れた経路案内を実現することができる。また、待ち時間を過ごす際の快適さと、経由経路の所要時間または距離の増加分とを考慮することにより、規制ノードから比較的近い範囲で快適な待合場所を探索することができる。
【0095】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。本実施例は、歩行者用の経路案内システムに限らず、車両用の経路案内システムに適用することも可能である。また、本実施例では、サーバ200と端末100からなるシステムを例示したが、サーバ200の機能を端末100に組み込み、スタンドアロンの装置として構成することも可能である。
【図面の簡単な説明】
【0096】
【図1】実施例としての経路案内システムの構成を示す説明図である。
【図2】地図DB250および時刻表DB252のデータ構造を示す説明図である。
【図3】経路探索処理例を示す説明図である。
【図4】待合場所の抽出処理例を示す説明図である。
【図5】出発地Sを待合場所とした場合の経由経路を示す説明図である。
【図6】コンビニエンスストアEを待合場所とした場合の経由経路を示す説明図である。
【図7】喫茶店Hを待合場所とした場合の経由経路を示す説明図である。
【図8】目的地Gを待合場所とした場合の経由経路を示す説明図である。
【図9】経路探索処理のフローチャートである。
【図10】経由経路設定処理のフローチャートである。
【図11】経路案内処理のフローチャートである。
【図12】経路案内の表示画面を例示する説明図である。
【符号の説明】
【0097】
100…端末
110…主制御部
120…通信部
130…コマンド入力部
140…GPS
150…表示制御部
200…サーバ
220…通信部
230…経路探索部
240…経路案内部
250…地図DB
250L…リンクデータ
250N…ノードデータ
252…時刻表DB
254…ユーザDB
【技術分野】
【0001】
本発明は、時間によって通行可否や通行の方向が異なる規制箇所が存在する場合における経路探索、案内技術に関する。
【背景技術】
【0002】
車両または歩行者用に、指定された出発地から目的地に至る最適な経路を探索、案内する経路案内装置が提案されている。経路案内装置は、通路をノード、リンクで表したネットワークデータを参照し、各リンクに付された評価値、即ちコストの総和が最小となる経路を探索する。歩行者用の経路案内システムでは、電車やフェリーなどの公共交通機関を通路に含めて経路探索を行う技術も提案されている(特許文献1〜3参照)。
【0003】
公共交通機関を含む場合には、所要時間に基づいてコストを設定することにより、所要時間が最短となる経路の探索が行われる。公共交通機関は、出発時刻が予め定められているため、公共交通機関を利用する際には、この出発時刻との関係で無駄な待ち時間が生じる場合もある。特許文献1〜3は、公共交通機関の時刻表をデータベースとして備えることにより、各公共交通機関の待ち時間も考慮して最短時間の到達経路を探索する技術を開示している。
【0004】
【特許文献1】特開平8−166248号公報
【特許文献2】特開2001−165683号公報
【特許文献3】特開2001−280992号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
従来技術では、経路探索時に、待ち時間は考慮されているものの、待合場所については考慮されていなかった。つまり、従来技術では、規制が付されたノード(以下、「規制ノード」と称する)で待つことを前提として経路探索が行われているが、必ずしも規制ノードは待合いに適しているとは限らなかった。待ち時間によっては、ユーザは喫茶店やコンビニエンスストアなどでの待機を望む場合もある。従来、これらの待合場所はユーザ自身が探す必要があった。また、待合場所への往復の経路を考慮すると、当初予定されていた公共交通機関ではなく、徒歩その他の移動手段を利用する方が好ましい経路が得られる場合もあった。このように従来の経路探索は、実用性、利便性という観点で、更に改善の余地が残されていた。
【0006】
かかる課題は、交通機関を利用する場合に限られるものではない。例えば、時間によって通行禁止となる道路、一方通行の規制方向が変わる道路、及び右左折禁止などの規制が解除される交差点、時間帯によって通行止めが解除される有料道路などについても同様に、規制が切り替わる直前に規制箇所に到達するか否かによって探索結果が大きく影響を受ける可能性がある。時間帯によって通行可能となる経路が探索されたとしても、車両の場合には、通行規制が付された交差点等で規制が解除されるまで待つことはできないことがあり、現実には探索された経路を走行することができなかったり、ユーザ自身で待機場所を探したりする必要があった。本発明は、こうした課題に鑑み、探索された経路の途中で待ち時間が生じる場合における経路案内の実用性、利便性を向上することを目的とする。
【課題を解決するための手段】
【0007】
本発明は、出発地および目的地の指定を受け付けて両者間の経路を探索する経路案内システムとして構成することができる。車両および歩行者のいずれを対象とするものであってもよい。経路探索には、通路をノードおよびリンクで表したネットワークデータを用いる。ネットワークデータに含まれるノードおよびリンクの少なくとも一部には、規制条件が付されており、ノードやリンクを通行する際に採りうる通行態様が時刻に応じて規制される。規制条件としては、例えば、交通機関のように所定の出発時刻にならないと利用できないという規制や、時間に応じて変化する通行禁止、一方通行、右左折禁止などの通行規制等が挙げられる。
【0008】
経路案内システムは、ネットワークデータに基づいて、まず、出発地から目的地に至る経路を探索した上で、経路上の各ノードへの到着予測時刻に基づいて規制条件に基づく待ち時間の有無を判断する。経路探索は、ノード、リンクに付されたコストが最小となる経路を求めるダイクストラ法など種々の方法を採ることができる。ダイクストラ法を用いる場合、リンクの距離に基づいてコストを設定することによって最短距離の経路を求めるようにしてもよいし、リンク間の移動の所要時間に基づいてコストを設定することによって最短時間の経路を求めるようにしてもよい。上述の経路探索は、規制条件を無視して行っても良いし、規制条件を考慮して行っても良い。後者の方法では、例えば、規制条件に基づいて待ち時間が発生する場合には、その待ち時間を所定の演算式でコストに反映させた上で経路探索する方法を採ることができる。後者の方法では、規制条件が付されたノード、リンクを通過する経路と、回避する迂回経路とを、規制ノードでの待ち時間も考慮した上で比較して経路を求めることができる利点がある。
【0009】
経路案内システムは、こうして探索された経路において待ち時間が要求される規制ノードが存在する場合には、出発地と規制ノードとの間で、最初に探索された経路よりも待ち時間が短くなる経路を探索する。この経路は、主として最初に探索された経路と異なる点を経由する経路となることが多いため、以下、説明の便宜上、経由経路と称するものとする。かかる経由経路は、例えば、最初に探索された経路のみを除外して、ダイクストラ法で経路探索をすることにより求めることができる。また、最初に探索された経路上にないいずれかのノードまたはリンクを経由地に指定し、この経由地を通る経路を求めるようにしてもよい。また、規制ノードでの待ち時間が短くなる経路であればよいから、最初に探索された経路上に存在するノードのうち、規制ノード以外のノードで待ち時間を費やすようにしてもよい。
【0010】
本発明によれば、規制ノードで待ち時間が生じた場合に、そこでの待ち時間を短縮させる代替経路を提示することができる。従って、規制ノードが待合いに適していない場合でも、実用的な経路を提示することが可能となる。
【0011】
ネットワークデータには、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報を付しても良い。待合場所適性情報は、例えば、ノードまたはリンクの属性として設定することができる。待合場所適性情報は、例えば、待合場所としての利用の「適」または「否」を表すフラグとしてもよいし、待合場所としての好適度を複数段階で表す指標値としてもよい。
【0012】
また、待合場所適性情報は、この好適度を間接的に表す情報とすることもできる。かかる情報としては、例えば、「フェリー乗り場」、「駅」など、ある程度の時間の待合いが前提とされている施設であることを示す属性情報、「喫茶店」や「レストラン」など、ある程度の時間を過ごすことが前提とされている施設であることを示す属性情報などを用いることができる。このような情報を用いる場合には、更に、上述の属性情報と、好適度を表す指標値との対応関係をテーブル等の形式で記憶した変換データベースを用意しておき、経路探索時には、この変換データベースに基づいて求まる指標値を用いるようにしてもよい。
【0013】
待合場所適性情報が用意されている場合、経路案内システムは待ち時間が要求される場合には、待合場所適性情報を利用して、規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する。待合ノードを選択する範囲は、任意に設定可能であり、例えば、規制ノードから所定の直線距離内にある範囲、規制ノードから所定の道のり内にある範囲、規制ノードから所定時間内で到達できる範囲、探索された経路上の各ノードから所定の直線距離内や所定の道のり内にある範囲、経路探索時に候補の経路として挙げられたノードの範囲内などとすることができる。
【0014】
経路案内システムは、こうして選択された待合ノードのそれぞれにつき、待合ノードを経由して規制ノードに至る経由経路を探索する。規制ノードが一カ所の場合には、経由経路は、出発地から待合ノードを経由して規制ノードに至る経路となる。規制ノードが複数ある場合は、出発地または直前の規制ノード通過後のいずれかのノードからの経由経路を求めるようにしてもよい。こうすれば、待合場所の経由経路を探索することにより、待ち時間が要求される時の経路案内の実用性、利便性を向上させることができる。
【0015】
上述の待合場所適性情報は、予めネットワークデータの一部として格納されるようにしてもよいし、ユーザがカスタマイズ可能としてもよい。ユーザが設定した待合場所適性情報は、例えば、予め用意されたネットワークデータとは分けて、ユーザ固有のユーザデータベースとして格納するようにしてもよい。ユーザがカスタマイズ可能とすることにより、ユーザの好みや要望に応じた待合場所を提示することが可能となる。例えば、時間に余裕があれば銀行や郵便局で所用を済ませようと考えているユーザは、予め銀行や郵便局に対して待合場所適性情報を設定しておくことにより、これらの所用を効率的に済ませられる経路を得ることが可能となる。
【0016】
こうした実用性をより向上させるため、待合場所適性情報をユーザがカスタマイズする際には、銀行等の位置を支点単位で個別具体的に指定するのではなく、「○○銀行」という単位での指定や、単に「銀行」という一般的な指定を許容してもよい。経路案内システムは、規制ノードから所定範囲内で、この一般的な指定の条件に該当する店舗等を検索し、そこを待合い場所に選択して経由経路を求めればよい。
【0017】
待合ノードが複数選択されている時、利用する待合ノードは、ユーザに選択させてもよいし、経路案内システムが自動的に決定してもよい。前者の態様では、例えば、待合ノードを地図上などに一覧表示し、ポインティングデバイス等でユーザに指定させる方法を採ることができる。待合ノードを地図上に表示する際には、経由経路の距離、所要時間、待合ノードでの待ち時間などを判断の際の目安としてユーザに提示するようにしても良い。
【0018】
待合ノードを自動的に決定する方法としては、例えば、経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて所定の演算により経由経路の評価値を算出し、この評価値に基づいていずれか一つの経由経路を選択する方法を採ることができる。評価値の算出式は任意に設定可能である。
【0019】
先に説明した通り、本発明では、少なくとも一部のノードに対して待合場所適性情報を付されている。この待合場所適性情報は、単に利用可否を表すデータとすることもできるし、利用の適否を複数段階の指標値で表すデータとすることができる。指標値は、任意に設定可能であるが、例えば、指標値が大きいほど待ち時間としての利用に適していることを表すものと定義してもよい。指標値は、待ち時間に関わらず一定値としてもよいし、待ち時間に応じて変化させるようにしてもよい。例えば、コンビニエンスストアは、待ち時間が短い場合には高い指標値とし、待ち時間が長くなるほど低い指標値に設定することができる。コンビニエンスストアは、気楽に利用でき、空調も整っている点で短時間の待合いには適しているが、座ることができないため長時間の待ち時間に対しては適しているとは言えないからである。
【0020】
このように複数段階の指標値が設定されている場合には、この指標値も用いて上述の評価値を算出し、待合ノードの選択を行うようにしてもよい。例えば、「評価値=所要時間+(待合ノードでの待ち時間/指標値)」のように、指標値は待合ノードでの待ち時間の重み係数として用いることができる。指標値を考慮することにより、より快適な環境で時間を過ごすことができる待合場所を提示することができ、経路案内システムの利便性を向上させることができる。
【0021】
待合場所適性情報には、待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含めてもよい。例えば、上述のコンビニエンスストアに対しては、座ることができないという点を考慮し、待ち時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待ち時間の下限値を設定することができる。このように待ち時間の上限値、下限値等が設定されている場合には、経路案内システムは、待合ノードでの待ち時間と、上限値および下限値の少なくとも一方との大小関係を考慮して待合ノードの選択を行ってもよい。こうすることにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【0022】
本発明の対象となる規制条件は、例えば、ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類することができる。例えば、交通機関の発車時刻は時刻規制条件に相当し、所定時間帯のみ通行止めが解除される規制などは時間帯規制条件に相当する。このように複数種類の規制条件が付されている場合、経路案内システムは、規制ノードに付されている規制条件が、時刻規制条件である場合と時間帯規制条件である場合とで、待合ノードの選択の方法を切り換えてもよい。例えば、時刻規制条件の場合、規制ノードへの到達時刻が予定時刻から遅れることは許されないため、規制ノードの近くに位置する待合ノードを優先して選択することが好ましい。一方、時間規制条件の場合については、規制ノードへの到達時刻に対する制約は比較的緩やかであるため、規制ノードからの距離よりも待ち時間を過ごす際の快適さを優先して待合ノードを選択することが好ましい。もっとも、ここで示したのは、待合ノードの選択方法の切り換えの一例に過ぎず、ここに例示した他、種々の選択方法を使い分けることが可能である。
【0023】
経路案内システムは、更に、出発地から規制ノードを回避して目的地に至る迂回経路を探索し、この迂回経路および経由経路のいずれかを出発地から目的地に至る経路として推奨するようにしてもよい。迂回経路および経由経路の選択は、それぞれの距離および所要時間の少なくとも一方に基づいて行うことができる。例えば、経路探索時に用いられるコストに換算し、迂回経路および経由経路のうちコストの小さい方を選択するようにすることができる。こうすることにより、待合場所への経由経路を採ることで目的地までの距離が迂回経路よりも長くなり、結果として不利な経路を選択したことになるという弊害を回避することが可能となる。
【0024】
経路案内システムは探索された経路を地図上に表示してユーザに案内するようにしてもよい。この場合には、経由経路とその他の経路とを異なる表示態様で表示する方法を採っても良い。こうすることにより、待合場所に向かうために目的地からそれた経路を案内されたとしても、ユーザはその意味を理解することができる利点がある。
【0025】
経由経路を表示する場合には、規制条件に基づき、待合ノードを出発すべき時刻をユーザに報知するようにしてもよい。報知は、画面上の表示や音声出力など、種々の方法で行うことができる。かかる報知により、ユーザは待合場所で安心して時間を過ごすことが可能となる。
【0026】
また、経由経路を案内する場合には、規制ノードに到達すべき到達時刻、または到達時刻までの余裕時間をユーザに提示するようにしてもよい。こうすることで、ユーザは規制ノードでの規制条件を考慮して、移動速度を調整することができ、規制条件による制約を無理なく回避して経路を通行することが可能となる。
【0027】
本発明は、上述の特徴を必ずしも全て備えている必要はない。上述の特徴は、適宜、一部を省略したり、組み合わせたりすることが可能である。また、本発明は、上述した経路案内システムとしての構成の他、コンピュータによって経路探索や経路案内を行う経路探索方法、経路案内方法の態様を採ることもできる。本発明は、更に、これらの機能を実現するためのコンピュータプログラム、かかるコンピュータプログラムを記録した記録媒体の態様を採ることもできる。記録媒体としては、フレキシブルディスクやCD−ROM、光磁気ディスク、ICカード、ROMカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置(RAMやROMなどのメモリ)および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【0028】
本発明の実施例について以下の順序で説明する。
A.システム構成:
B.データ構造:
C.経路探索:
C1.経路探索処理例:
C2.経路探索処理:
C3.経由経路設定処理:
C4.変形例:
D.経路案内:
【0029】
A.システム構成:
図1は実施例としての経路案内システムの構成を示す説明図である。本実施例では、歩行者用の経路案内システムとしての構成例を示すが、車両用の経路案内システムとして構成することもできる。経路案内システムは、携帯電話を利用した端末100とサーバ200とをネットワークINTで接続して構成されている。ネットワークINTは無線通信を利用したネットワークであり、LANやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。端末100は、携帯電話の他、いわゆる車両用のナビゲーション装置やPDA、ネットワーク通信機能を有するパーソナルコンピュータなどを利用することができる。歩行者用の経路案内システムとして構成する場合、車両用のナビゲーション装置は、車両から取り外して携帯可能としておくことが望ましい。
【0030】
端末100は、ユーザの操作に応じて、経路探索および経路案内に必要な指示をサーバ200に送信するための機能を奏する。図中には、端末100の機能ブロックを併せて示した。端末100は、CPU、RAM、ROMを備えたマイクロコンピュータを制御装置として内蔵しており、このCPUはROMに記憶されたソフトウェアを実行することで、図示する各機能ブロックを構成する。これらの機能ブロックは、このようにソフトウェア的に構成する他、ハードウェア的に構成することも可能である。
【0031】
通信部120は、ネットワークINTを介してサーバ200と通信する機能を奏する。GPS140は、全地球測位システム(Global Positioning System)を利用して、端末100の現在位置の緯度、経度を検出する。コマンド入力部130は、スイッチ等に対するユーザ操作に基づいて、経路探索や経路案内に関するコマンドを入力する。コマンドとしては、図示した通り、経路探索の目的地の指定、案内経路の選択などが挙げられる。表示制御部150は、端末100のディスプレイに、これらのコマンド入力用のメニューを表示したり、サーバ200から受信した経路案内データに基づいて地図を表示させたりする。主制御部110は、上述した各機能ブロックを統括制御することで、端末100の全体機能を制御する。
【0032】
サーバ200は、端末100からのコマンドに基づいて、種々のデータベースを参照しながら、経路探索を行ったり、経路案内を行ったりする。図中には、これらの機能を実現するための機能ブロックおよびデータベースの例を示した。各機能ブロックは、サーバ200のCPUが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【0033】
サーバ200が利用するデータベースは地図DB250、時刻表DB252、ユーザDB254の3種類である。地図DB250は、通路をノード、リンクで表したネットワークデータ、および地図描画用のポリゴンや文字データからなる描画データを有している。本実施例では、ノードおよびリンクの少なくとも一部には、許容される通行態様が時刻によって変化するものが存在する。この規制条件としては、例えば、出発時刻が規定されている公共交通機関、所定時刻になると閉鎖される駅構内の通路などが挙げられる。時刻表DB252は、この規制条件を記録するデータベースである。地図DB250および時刻表DB252のデータ構造については後述する。
【0034】
ユーザDB254は、ユーザID、氏名などの書誌的な登録情報と共に、ユーザが歩行する際の移動速度に関する設定や、距離優先/時間優先などの経路探索に関する要望事項を格納している。図中にはユーザDB254の内容として移動速度に関する登録内容を例示した。本実施例では、移動速度は、移動可能な距離と組み合わせて登録されている。図中の例では、通常利用される移動速度(以下、「通常速度」と呼ぶこともある)は「4km/h」であり、移動可能な距離には制約がないことを表している。やや早足の「5km/h」では、3kmまで移動可能であり、駆け足の「10km/h」では0.5kmまで移動可能であることを表している。これらの情報は、ユーザが端末100を操作して登録、変更可能である。図中の例では、3通りの移動速度が登録されているが、更に多くの移動速度を登録可能としてもよい。
【0035】
通信部220は、端末100とのネットワークINT経由での通信を制御する。経路探索部230は、上述の3種類のデータベースを参照して、ユーザから指定された出発地、目的地間の経路を探索する。経路探索部230は、ユーザからの指示に応じて、移動速度などの探索条件を複数種類に変化させ、それぞれの条件に対応する経路を探索することが可能である。また、時刻表DB252を参照することにより、上述の規制条件も考慮して経路探索を行う。経路探索方法については後述する。
【0036】
経路案内部240は、探索された経路を地図上に表示して案内するための経路案内データを生成し、端末100に送信する。上述の通り、経路探索は、種々の探索条件に基づいて行われ、規制条件も考慮して行われている。経路案内部240は、これらの条件を反映した案内表示を実現する。経路案内方法については後述する。
【0037】
B.データ構造:
図2は地図DB250および時刻表DB252のデータ構造を示す説明図である。地図DB250については、経路探索用のネットワークデータの構造のみを例示した。図の中央に例示するように、ネットワークデータは、ノードN1〜N8およびリンクL1〜L9等で構成される。リンクL1〜L9は歩行者が通行可能な通路を表しており、ノードN1〜N8はリンクL1〜L9の端点または接続点を表している。
【0038】
地図DB250は、上述のノード、リンクに関するデータを、それぞれノードデータ250N、リンクデータ250Lとして格納している。図中に示す通り、リンクデータ250Lには、リンクID、形状、時刻表、速度規制、距離などの情報が記録される。形状は、リンクが通過する地点の座標(緯度、経路)を表した点列データである。座標には、高さを表す情報を含めても良い。図中の例では、リンクL9について、ノードN2、N7を含む4点が格納されている。本実施例では、ノードについてはノードIDを格納し、その位置はノードデータ250Nを参照することで得られるようにしたが、ノードについても他の通過地点と同じく座標を格納するようにしてもよい。時刻表とは、時刻表DBに格納されている情報へのリンクを表している。図中の例L9では、時刻に応じて変化する規制条件が付されていないため、時刻表の項目には「無し」が登録されている。後述するように、リンクL3、L4、L6のように時刻に応じて変化する規制条件が付されている場合には、時刻表DB252に格納されているデータのインデックスである「時刻表ID」が格納されることになる。速度規制とは、そのリンクを通行する際の上限速度を表している。距離とは、そのリンクの区間距離である。
【0039】
リンクデータ250Lの内容は、任意に設定可能であり、これらの情報の一部を省略してもよいし、ここに例示していない種々の属性情報を格納するようにしてもよい。例えば、階段や坂道などの経路種別や、ガードレールや街灯などの設備の有無等を属性情報として格納することができる。かかる属性情報が用意されている場合には、「階段を避けたい」、「ガードレールが整備されている経路を優先したい」などの経路に対する要望事項を反映した経路探索を実行することが可能となる。例えば、「階段を避けたい」という要望が出されている場合には、「階段」という属性情報が記録されているリンクのコストを増加させることによって、階段が選択される可能性を抑制することが可能となり、要望に沿った経路を探索することが可能となる。
【0040】
ノードデータ250Nには、図示するようにノードID、位置、時刻表、通行規制、待合好適度、待合許容時間などの情報が記録される。「喫茶店」、「コンビニエンスストア」、「銀行」、「郵便局」などノードの種別を表す情報を含めてもよい。ノードの位置は、緯度、経度の座標で記録される。座標には、高さを表す情報を含めても良い。時刻表は、リンクデータ250Lと同様、時刻表DB252に格納されている情報へのリンクを表している。通行規制とは、右左折禁止など、時刻に応じて変化しない固定的な通行規制である。例えば、図中のノードN4について、N3方向から来てN6方向へ左折する通行が禁止される場合には、通行規制欄には、「N3→N4→N6」という形でデータを格納すればよい。通行規制情報の記録方法は、これに限らず、種々の形式を採用することができる。
【0041】
待合好適度とは、探索された経路において規制条件による待ち時間が生じた場合、その時間経過を待つ待合場所としての適性を表す指標であり、後述する通り、複数の待合場所の中から、案内対象とすべき待合場所を選択する際に用いられる値である。本実施例では、適性を0〜5の6段階の整数値で表すものとした。待合好適度「0」は、待合場所として使用できない場所を表しており、値が大きくなるほど待合に適していることを表している。待合好適度「0」に該当し得る場所としては、例えば、自動車用の案内装置では交差点の中央などが当たり、歩行者用の案内では駅の改札口、エレベータ、エスカレータなどが当たり得る。
【0042】
待合許容時間とは、待合場所としての使用が許容される下限値および上限値を表す。待合許容時間も、後述する通り、複数の待合場所の中から、案内対象とすべき場所を選択する際の基準として用いられる値であるから、ユーザの要望に添った選択結果となるよう任意に設定することができる。従って、待合許容時間は、必ずしも明確な規制条件である必要はなく、ユーザの体力的な限界や心理的な限界を考慮した一般的な許容範囲で構わない。例えば、コンビニエンスストアに対応するノードに対しては、座ることができないという点を考慮し、待合許容時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対応するノードに対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待合許容時間の下限値を設定することができる。
【0043】
待合好適度や待合許容時間は、ノードの属性として格納する他、リンクの属性として格納してもよい。また、本実施例では、上述のように待合好適度を直接に表す場合を例示しているが、「フェリー乗り場」や「駅」などのように待合場所としての適性を推測可能な情報を待合孔適度として用いるようにしてもよい。
【0044】
また、待合好適度や待合許容時間は、予め地図DB250に組み込まれている情報の他、ユーザが任意に設定可能としてもよい。この情報は、地図DB250に直接登録可能としてもよいが、ユーザごとに設定内容を管理可能とするため、ユーザDB254(図1参照)に登録可能とすることが好ましい。ユーザの設定内容には、ノードIDに代えて、「銀行」、「郵便局」などノードの種別を表す情報を用いるようにしてもよい。例えば、「銀行」に対し、「待合好適度=5」、「待合許容時間=20〜30分」などのように設定する方法を採ることができる。後述する経路探索処理時には、サーバ200は、「銀行」に該当する種別情報を有するノードを検索することによって、ユーザが設定した内容を特定のノードに対する待合好適度、待合許容時間と同視して取り扱うことができる。
【0045】
時刻表DB252には、時刻表ID、規制、時刻、開始遅れ、終了遅れなどの情報が格納されている。時刻表IDは、登録されているそれぞれの情報を一義的に示すための識別データである。規制は、時刻表IDが示す規制情報を表している。図中には、駅の入り口G1〜G3が午前0:30〜午前4:30の間で閉鎖され、駅構内のリンクL3,L4,L6が通行不能となる場合のデータを例示した。この場合、通行不能となるため、「規制」欄には、「通行止め」が格納され、時刻欄には、通行止めとなる時刻が格納される。複数の時間帯で通行止めとなる場合には、時刻欄に、複数の時間帯を格納することもできる。開始遅れは、この時間帯の開始時刻(図中の例では0:30)が遅れる可能性を示し、終了遅れは終了時刻が遅れる可能性を示している。駅構内の通行止めについては、規定通りに閉鎖されるため、開始遅れ、終了遅れは「無し」と設定されている。「時刻表ID=1」が付されたこのデータは、リンクL3、L4、L6に適用される。従って、リンクデータ250LのこれらのリンクIDに対応するデータの「時刻表」欄に「1」が格納されることになる。リンクデータの時刻表欄には、複数の時刻表IDを格納可能としてもよい。
【0046】
時刻表DB252には、上述のような「通行止め」の規制の他、種々の規制が格納可能である。例えば、本実施例では、電車などの交通機関の出発時刻も、その路線を通行可能な時間帯が限られているという意味で規制条件の一種とみなし、時刻表DB252で管理するものとした。この場合には、「規制」欄には、例えば、「電車発着」などと格納することで交通機関であることを示し、「時刻」欄に出発時刻および到着時刻からなる時刻表を格納することができる。出発時刻と途中の経過駅までの所要時間という形式で格納するようにしてもよい。交通機関の場合には、出発時間や到着時間が遅れる場合がある。出発時間の遅れは「開始遅れ」に記録し、到着時間の遅れは「終了遅れ」に記録することができる。これらの時間は、後述する通り、経路探索時に考慮される値であり、任意に設定可能であるが、一例として、過去所定期間内の平均遅れ時間や最大遅れ時間などに基づいて設定することができる。
【0047】
C.経路探索:
本実施例における経路探索処理について説明する。まず、いくつかの具体例に基づいて処理概要を説明した後、経路探索処理を実現するためのフローチャートを説明する。
【0048】
C1.経路探索処理例:
図3は経路探索処理例を示す説明図である。図中に経路探索の対象となるノード、リンクの構成を例示した。丸印はノードを表し、実線はリンクを表している。以後、ノードは丸印中の文字を用いて特定し、リンクはその両端のノードを用いて表す。例えば、ノードSとノードAとの間のリンクはリンクSAまたはリンクASを表すものとする。各リンクに付された数字は、リンク間の移動に要する所要時間である。移動の所要時間は、ユーザの移動速度に応じて変化する。本実施例では、ユーザDB254に登録された通常速度(図1では4km/h)を用いるものとした。経路探索時に用いる移動速度は、通常速度、最大速度などをユーザが選択可能としてもよいし、経路途中にある規制条件による制約を最も効率的に回避し得るようユーザDB254を参照しながら経路案内システムが設定してもよい。
【0049】
図示したネットワークデータを用いて、出発地Sを午前5:00に出発し、目的地Gに向かう所要時間最短の経路を探索する場合を考える。経路探索は、所要時間をコストとするダイクストラ法によって行うものとする。ダイクストラ法とは、各リンクに付されたコストの総和が最小となる経路を求める演算方法である。この例では、所要時間をコストとして用いるが、この他、リンクの距離をコストとして用いたり、所要時間や距離その他の情報を考慮して設定されたコストを用いたりすることも可能である。
【0050】
ダイクストラ法の演算方法は周知であるため処理内容自体についての説明は省略し、結果概要のみを説明する。図の例で、出発地Sをスタートし、途中のノードBまで至る経路とそのコストは、それぞれ次の通りとなる。
経路S→A→H→B …コスト=40;
経路S→A→B …コスト=22;
経路S→A→E→F→B…コスト=30;
従って、ノードBに至る最適経路は、経路S→A→Bと求まる。この結果、ノードCに至る最適経路は、経路S→A→B→Cと求まる。この経路を採用した場合、ノードCへの到達時刻は5:30と予測される。
【0051】
図中に示す通り、リンクCDには夜間20:00〜6:00は通行止めとなる規制条件が付されている。従って、ノードCに5:30に到達した時点では、リンクCDを通行することはできない。以下、このように通行する時刻または時間帯が規制されているノードを規制ノードと称する。図の例では、リンクCD間に規制条件が付されているが、出発地Sから目的地Gに向かう経路探索時にはノードCにおいてのみ規制条件が問題となるため、ノードCのみが規制ノードに該当する。
【0052】
規制ノードCから先の経路としては、「C→I→D」の迂回経路と、ノードCで通行規制が解除されるまで待った上で「C→D」と通行する経路とがある。迂回経路のコストは70である。ノードCで待つ場合には、ノードCでの待ち時間30分を、リンクCDのコストに反映した上で、経路のコストを算出する。この結果、「C→D」のコストは50となる。従って、ノードCで30分の待ち時間が生じたとしても、迂回経路よりは経路「C→D」の方がコスト小となることが分かる。
【0053】
以上の探索処理の結果、図3の例によれば、「出発地S→A→B→C→D→目的地G」という経路(図中、太線で示した経路)がコスト最小、即ち所要時間最短となる経路として求められる。この経路を採った場合には、ノードCで30分の待ち時間が生じることが分かる。本実施例では、このように待ち時間が生じた場合には、以下に示す処理によって、待合場所を特定し、待合場所を経由する経由経路を案内する。
【0054】
図4は待合場所の抽出処理例を示す説明図である。リンクCDを通過するための待合場所であるから、待合場所は、出発地S〜ノードCの間で探索される必要がある。以下では、図3に示した経路のうち、出発地S〜ノードC間のみを示す。この例では、規制ノードは、ノードCの1カ所のみであるが、仮にリンクDG上に、更に規制ノードJ(図示せず)が存在する場合には、規制ノードCと規制ノードJとの間で、以下の処理と同様の処理によって待合場所が探索されることになる。
【0055】
サーバ200は、図示するように、規制ノードCから所定範囲内で待合場所の候補となるノード(以下、待合ノードと称する)を抽出する。この抽出処理には、図2で示したノードデータ250Nの待合好適度が用いられる。待合好適度が所定値以上のノードを選択すればよい。値1以上を選択すれば広範に待合ノードが抽出されるし、更に高い待合好適度を要求すれば、候補となる待合ノード数は減少するものの待合いに快適な場所が抽出されることになる。
【0056】
待合ノードを抽出する範囲は、種々の条件で規定することができる。例えば、1)図3に示した経路探索の過程で経路候補として挙げられたノードの範囲内、2)規制ノードから所定の所要時間内に到達可能な範囲、3)規定ノードから所定の道のり内、4)規定ノードから所定の直線距離内などの条件を用いることができる。図4では、条件1を用いた場合を例示した。この結果、待合ノードとして、図中に二重丸で示す4カ所、即ち出発地S、コンビニエンスストアE、喫茶店H、目的地Cが選択されたとする。次に、これらの各待合ノードを経由する経由経路を求め、待合場所としての適否を判断する処理例を示す。
【0057】
図5は出発地Sを待合場所とした場合の経由経路を示す説明図である。経由経路を得るには、出発地から待合ノードまでの経路、待合ノードから規制ノードCまでの経路をそれぞれダイクストラ法で求めればよい。図5の例では、出発地と待合ノードが同一であるため、経由経路は図3で得られる経路と同一の経路「S→A→B→C」(図中の太線)となる。本実施例では、待合ノードを選択する際の第1の指標として、この経由経路の所要時間を求める。この例では30分となる。
【0058】
そして、第2の指標として、余裕時間、即ち待合ノードで過ごす時間を求める。余裕時間は次式によって求めることができる。
余裕時間=規制ノードCでの待ち時間−余剰時間;
余剰時間=経由経路の所要時間−規制ノードCまでの本来の経路の所要時間(図3で得られた経路の所要時間);
図5の例では、余裕時間は30分となる。
【0059】
そして、所要時間、余裕時間、待合好適度を用いて次式により、待合ノードおよび経由経路の評価値を求める。
評価値=所要時間+(余裕時間/待合好適度);
図5の例では、評価値は60となる。この評価値は値が小さいほど好ましい経由経路であることを表している。評価値の内容は、経由経路を採ることによる所要時間の増大というデメリットと、快適な場所で待ち時間を過ごすことによるメリットとを加味した値となっている。待合好適度は、余裕時間を過ごす際の評価値の増加を抑制する因子として作用する。従って、この評価値を用いれば、待合好適度が高い快適な場所であれば、若干、所要時間が増大したとしても経由する価値があるという評価が得られることになる。評価値は任意に設定可能であり、所要時間に代えて、先に説明した余剰時間を用いても良い。また、所要時間や余剰時間にも重み係数を乗じるようにしてもよい。
【0060】
図6はコンビニエンスストアEを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→E→F→B→C」が得られる。この経由経路の所要時間は38分であり、余裕時間は22分となる。コンビニエンスストアの待合高適度は「2」と設定されているから、評価値は49と求められる。
【0061】
図7は喫茶店Hを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→H→B→C」が得られる。この経由経路の所要時間は48分であり、余裕時間は12分となる。喫茶店Hの待合高適度は「4」と設定されているから、評価値は51と求められる。
【0062】
図8は規制ノードCを待合場所とした場合の経由経路を示す説明図である。図5の場合と同様の手順によって経由経路「S→A→B→C」が得られる。この経由経路の所要時間は30分であり、余裕時間は30分となる。規制ノードCの待合高適度は「1」と設定されているから、評価値は60と求められる。
【0063】
図5〜8で示した結果を比較すると、評価値は次の通りとなる。
(図5のケース)待合ノード=S … 評価値=60;
(図6のケース)待合ノード=E … 評価値=49;
(図7のケース)待合ノード=H … 評価値=51;
(図8のケース)待合ノード=C … 評価値=60;
従って、これらの中では、図6のケース、即ちコンビニエンスストアEを待合場所とする経路が推奨経路となる。図7のケース、即ち喫茶店Hを待合場所とする場合が推奨経路とならないのは、待合好適度は大きいため、待ち時間の過ごしやすさという点では優れるものの、場所が遠く、喫茶店Hを経由する際の所要時間が増大することが原因と言える。当然、評価値の演算方法次第で、これらの結果は変動する。先に述べた通り、評価値の演算方法は、ユーザの要望に沿った実用性、利便性の高い待合場所が得られるよう、任意に設定すればよい。
【0064】
C2.経路探索処理:
図9は経路探索処理のフローチャートである。図3〜8で具体的に示した経路探索を実現するための処理例である。この処理は、サーバ200の経路探索部230(図1参照)が実行する処理であり、ハードウェア的にはサーバ200のCPUが実行する処理である。
【0065】
CPUは最初に、端末100からユーザID、出発地、目的地、出発時刻の指定を入力する(ステップS10)。この他、経路探索に関するユーザの要望事項を入力するようにしてもよい。例えば、経路に対して、階段や坂道を回避するという移動負荷に関する要望や、ガードレールや街灯が整備されている通路を優先するというような安全性に関する要望を指定可能としてもよい。
【0066】
次に、CPUは規制条件を考慮して経路探索を実施する(ステップS21)。ダイクストラ法による具体的な処理方法は周知であるため、ここでは詳細な説明は省略し、図中に経路探索の主要な処理内容を示した。経路探索において、CPUはまず従前の処理で探索された経路候補の先端のノードから更に分岐して経路を延伸させる経路候補を設定する(ステップS21)。次に、各ノードに至るまでのコストを算出して、そのコストおよび従前の経路を記録したラベルを設定していく。例えば、各リンクの距離を移動速度、即ちユーザの通常速度で割ることで所要時間を算出し、その所要時間をコストとして利用するという方法を採ることができる。コストは、この方法に限らず図3で説明したように種々の値を用いることができる。本実施例では、上述の処理で得られた所要時間を用いて各ノードへの到達時刻を予測する(ステップS22)。
【0067】
また、経路探索過程で、規制ノードが存在する場合には、時刻表DBを読み出し、上述の到達時刻に基づいて規制ノードでの待ち時間を算出し、この規制が関連するリンクのコストへ反映させる(ステップS23)。図中にこの処理の例を示した。図示するように、リンクCDに規制条件が付されており、ノードCに規制が解除される30分前に到達する場合には、待ち時間30分がリンクCDに反映される。ノードCから上述の規制とは無関係の迂回路が存在する場合には、この迂回路に対応するリンクには待ち時間分のコストは反映されない。所要時間をコストとして用いている場合には、待ち時間をリンクCDのコストに加えればよい。距離をコストとして用いている場合には、待ち時間に移動速度を乗じるなどの方法で距離に換算して加えることで、コストを反映させることができる。待ち時間の反映方法は、このようにコストの設定方法に応じて定められる。
【0068】
CPUは以上で得られたコストを用いて最小コストとなる経路を求める(ステップS24)。この処理を目的地に到達するまで繰り返し実行することで、図3に示したように、待合ノードの経由を考慮しない経路(以下、本来経路と称する)が得られる。
【0069】
こうして本来経路が得られると、CPUは規制ノードでの待ち時間を過ごす待合場所を経由する経由経路を設定するための処理、経由経路設定処理を実行する(ステップS100)。この処理は、先に図4〜8で示した処理である。具体的な処理のフローチャートは後で示す。この処理によって、種々の待合場所を経由する経路のうち、いずれか一つの待合場所を経由する経由経路が選択される。
【0070】
CPUは、次に、規制ノードを通過しない迂回経路を求め、この迂回経路と選択された経由経路のコストを比較し、いずれか小さい方を案内対象として選択する(ステップS200)。例えば、経由経路を採り本来経路よりも移動距離が過剰に長くなる場合などには、経由経路よりも迂回経路の方が好適と判断される逆転現象が生じる可能性もある。ただし、経路の所要時間をコストとして用いる場合には、かかる逆転現象は生じ得ない。経由経路を採る場合でも、規制ノードに到達する時刻は本来経路と一致するからである。ステップS200は任意の処理であり、所要時間をコストとして用いる場合も含め、適宜、省略しても差し支えない。
【0071】
C3.経由経路設定処理:
図10は経由経路設定処理のフローチャートである。先に図4〜8で示した処理例を実現するための処理であり、図9のステップS100に相当する処理である。
【0072】
この処理が開始されると、CPUは規制ノード周辺の待合場所を抽出する(ステップS102)。この抽出は、先に図4で説明した手順で実行することができる。この抽出時には、予め地図DB250に設定されている待合好適度とともに、またはこの待合好適度に代えて、ユーザが設定した待合好適度を参照するようにしてもよい。こうすることで、先に図2で説明したように、ユーザが「銀行」に対して待合好適度および待合許容時間を設定している場合には、銀行を経由する経由経路を求めることが可能となる。この結果、空き時間ができたら銀行で所用を済ませたいと考えているユーザに対して、要望に沿った効率的な経路を提示することが可能となる。
【0073】
次に、CPUは待合場所の選択モードに応じて、待合場所および経由経路を設定するための処理を実行する(ステップS104)。本実施例では、手動と自動の二つの選択モードを設けた。選択モードの指定は、ステップS104を実行する時点で、ユーザに問い合わせるようにしてもよいし、ユーザDB254(図1参照)に予め登録しておくようにしてもよい。
【0074】
自動選択モードが選択される場合には、CPUは、抽出されている各待合場所に対して、経由経路を探索し、所要時間、余裕時間を求め(ステップS112)、経由経路の評価値を算出する(ステップS114)。これらの処理は、図5〜8で説明した処理に相当する。
【0075】
CPUは、こうして得られた評価値に基づき評価値が最小となるという第1の条件に基づき、待合場所および経由経路を選択し(ステップS116)、経由経路設定処理を終了する。この選択時には、更に余裕時間が待合許容時間内という第2の条件を付しても良い。例えば、図5〜8の例で、喫茶店Hは余裕時間12分と求められている。喫茶店Hについて、仮に待合許容時間の下限値が15分と設定されているとすれば、この余裕時間は待合許容時間の下限値を下回っていることになる。従って、第2の条件を考慮すると、喫茶店Hは評価値を考慮するまでなく、待合場所から除外されることになる。第2の条件を考慮することにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【0076】
手動選択モードが選択される場合には(ステップS104)、CPUは、待合場所を端末100の画面上に地図とともに表示し、いずれかの待合場所を選択するユーザの指示を入力する(ステップS122)。この処理においても、自動選択モードの場合と同様、ユーザが設定した待合好適度を考慮して待合場所を提示するようにしてもよい。地図上の待合場所をクリッカブルにしておき、ユーザがポインティングデバイスでいずれかの待合場所をクリックすることで選択する方法を採ることができる。待合場所に番号を付し、キーボードでこの番号を指定するようにしてもよい。
【0077】
次に、CPUは選択された待合場所を経由する経由経路を探索し、その所要時間、余裕時間を求め、ユーザが経由経路の適否を判断するための目安となる情報として、端末100の画面上に提示する(ステップS124)。図中に画面例DISP1を示した。一例として、図示するように、経由すべき待合場所の付近にウィンドウを設け、所要時間、余裕時間を表示する態様を採ることができる。ユーザが「待合場所選択」ボタンを押すと(ステップS126)、CPUは再び待合場所の表示処理を実行する(ステップS122)。ユーザが「OK」ボタンを押すと(ステップS126)、CPUは経由経路設定処理を終了する。手動選択モードでは、最適か否かの評価は行わず、ユーザが選択した経由経路を選択することになる。
【0078】
C4.変形例:
図10の例では、自動選択モードで経路を選択する際に、「評価値最小となる経由経路を選択」という第1の条件のみ、または第1の条件および「余裕時間が待合許容時間内」という第2の条件の双方を画一的に使用する場合を例示した。これに対し以下に示すように、規制条件の種類に応じて経路を選択するための条件を使い分けるようにしてもよい。
【0079】
規制条件には、例えば、交通機関の発車時刻のように、通行するためには特定の時刻に規制ノードに到達していることが要求されるものがある。以下、かかる規制条件を時刻規制条件と呼ぶ。別の規制条件として、例えば、所定の時間帯のみ通行止めされる規制のように、通行するためには特定の時間帯に規制ノードに到達していれば足りるものがある。以下、かかる規制条件を時間規制と呼ぶ。規制ノードに到達する時刻に対する要求という点では、時刻規制の方が時間規制よりも厳しいと言える。
【0080】
経由経路設定処理では、時刻規制と時間規制の差違を考慮し、両者でステップS116における選択の基準を変えても良い。例えば、規制ノードに時刻規制が付されている場合には、ステップS116において規制ノードに近いことを重視する選択条件とすることができる。規制ノードに近い待合場所の方が、規制ノードへの到達時刻に対する要求を満足しやすいからである。上述の条件としては、例えば、ステップS116に示した条件に加え、規制ノードからの所要時間、道のり、直線距離のいずれかを制限する条件を考慮する方法が挙げられる。または、評価値を算出する際に、所要時間を、待合場所に至るまでの所要時間、待合場所から規制ノードに至るまでの所要時間に分け、後者に1以上の重み値を乗じるようにしてもよい。
【0081】
D.経路案内:
図11は経路案内処理のフローチャートである。図9で説明した経路探索処理の結果をユーザに提示するための案内データを生成し、端末100に送信する処理である。経路案内は、端末100の画面表示や音声出力などで行うことができる。経路案内処理は、サーバ200の経路案内部240が実行する処理であり、ハードウェア的にはサーバ200のCPUが実行する処理である。
【0082】
この処理では、CPUは、経路案内データを読込む(ステップS200)。経路探索処理では案内対象となる経路を一つに絞らずに、ステップS200の時点で経路案内データを複数読み込み、その一覧をユーザに提示して、案内対象となる経路をユーザに選択させてもよい。
【0083】
経路案内データが読み込まれると、CPUは端末100から現在位置を入力し(ステップS202)、経路案内用の画面を表示する。まず、CPUは現在位置と待合場所との位置関係によって待合中か否かを判断し(ステップS204)、待合中と判断される場合には出発時刻報知処理を行う(ステップS206)。この処理は、規制条件に基づいて設定された予定時刻に規制ノードに到着するために、待合場所を出発すべき時刻をユーザに知らせる処理である。出発時刻は、予定時刻よりも、待合場所から規制ノードまでの所要時間だけ遡った時刻、または更に若干の余裕を見込んだ時刻とすることができる。出発時刻に至る前の時点では、CPUは、出発予定時刻を画面上に表示する。現在時刻が出発時刻になると、CPUはユーザに音声や画面表示で、出発すべき旨を報知する。待合中でない場合には(ステップS204)、出発時刻報知処理はスキップされる。
【0084】
次に、CPUは経路途中に規制ノードがあるか否かを判断する(ステップS208)。規制ノードがある場合には、規制条件による制約を回避して通行するための残時間を表示する(ステップS210)。残時間の表示は、規制ノードに向かう際にユーザが移動速度を調整する際の目安として行うものである。残時間の表示は、待合場所を出発してから規制ノードに至るまでの間でのみ行うようにしてもよい。規制ノードがない場合には、この処理はスキップされる。
【0085】
CPUは以上で設定された画面とともに、地図上に経路および現在位置を表示して、経路案内を行う(ステップS212)。CPUは以上の処理を目的地に到達するまで繰り返し実行する(ステップS214)。
【0086】
図12は経路案内の表示画面を例示する説明図である。案内画面DISP2は端末100のディスプレイ上に表示される。図中の黒丸が現在位置PPである。案内画面DISP2では、図示するように現在位置PPを含む地図が表示され、そこに経路R1〜R3が表示される。本実施例では、経由経路、規制条件が付されている箇所、およびその他の経路で表示パターンを変化させるものとした。図中の経路R1は、クロスハッチにより、経由経路であることを表している。この表示により、ユーザは案内されている経路が経由経路であることを容易に認識できるため、本来の目的地と離れた方向に案内が行われている場合でも、安心して案内に従うことができる。
【0087】
経由経路R2は、ハッチングによって、時刻によって通行止めになるなどの規制条件が付されている箇所であることを表している。この表示により、ユーザは経由経路が要求される理由を容易に把握することができる。矢印で示した経路R3は、通常速度での移動で足り、規制条件も付されていないことを表している。経路R1〜R3の表示態様は、ここに例示したものに限られず、任意に設定可能である。これらの表示パターンの使い分けの少なくとも一部を省略してもよいし、更に詳細な使い分けを行うようにしてもよい。
【0088】
図中の例では、領域Aは駅STAの構内であり、20:00〜6:00の時間帯で通行止めになるという規制条件が付されている。経由経路R1が要求されるのは、この規制条件が解除されるのを待って駅構内を通行するためである。経由経路R1上には、待合場所となるコンビニエンスストアが表示される。この待合場所をユーザがクリックすると、ポップアップウィンドウW4が表れ、待合場所での余裕時間と、待合場所を出発すべき出発時刻が表示される。ポップアップウィンドウW4は、ユーザが待合場所にいる場合には、出発時刻を報知するために(図11のステップS206参照)ユーザの操作を行うまでなく表示させるようにしてもよい。
【0089】
本実施例では、更に領域Aのように規制条件が付されている箇所をクリッカブルとし、薄いハッチングを付すなど、通常の建造物とは異なる表示態様で表示させるものとした。ユーザが領域Aをクリックすると、ポップアップウィンドウW2が表示され、図示するように規制条件が表示される。駅STAについても同様に、ポップアップウィンドウW3を表示し、図示するように電車の時刻表を規制条件として表示可能としてもよい。ユーザはこれらの情報に基づき、待合場所での余裕時間や出発時刻の根拠を理解することができ、状況に応じて自身の判断で出発時刻を調整等することが可能となる。
【0090】
本実施例では、規制条件が付された領域Aに向かう過程では、サブウィンドウW1も表示するものとした。このサブウィンドウW1では、規制条件による制約を回避するために許される残時間を表示する(図11のステップS210参照)。図の例では、6:00に領域Aに到達すればよく、サブウィンドウW1の表示によれば、残り時間が4分20秒あることが分かる。領域Aのように通行止めが解除される場合には、残り時間4分20秒以内に領域Aに到達しても無用な待ち時間が生じるに過ぎない。この場合、残り時間は、ユーザに過度に急いでも無意味であることを表す情報となる。サブウィンドウW1では、亀のマークを表示させることによって、このような残り時間、即ちこの時間よりも早く到着しても有意義とは言えない時間が表示されていることを示している。
【0091】
一方、ユーザが駅STAに向かっている場合には、発車時刻に間に合うように駅STAに到達する必要がある。かかる場合には、残り時間は、ユーザが駅STAに到達するまでの所要時間の上限値を表す情報となる。かかる場合には、サブウィンドウW1に代えて、サブウィンドウW1aに示すように、ハートマークを表示させ、ユーザに残り時間が限られていることを認識させるようにしてもよい。これらサブウィンドウW1、W1aの表示によって、ユーザは自己の移動速度を適宜調整しながら、過度な負荷をかけずに移動することが可能となる。
【0092】
サーバ200は、ユーザの現在位置の履歴から移動速度を変化し、現在の移動速度を維持した場合の規制ノードへの到達時刻を予測することができる。サブウィンドウW1aを表示する際には、この予測に基づき、ユーザに移動速度を速めたり、ゆっくりさせたりする指示を与えるようにしてもよい。例えば、ハートマークの点滅間隔を縮めることによりペースアップを指示し、点滅間隔をのばすことによりペースダウンを指示する方法を採ることができる。
【0093】
経路R2は規制条件が付された箇所であることを表してはいるが、所定時刻までの通過が要求されている訳ではない。また、経路R3も通常速度での移動で足りる。従って、現在位置PPが経路R2、R3上にある時には、サブウィンドウW1、W1aは非表示となる。このように、規制条件が付された領域に向かう場合にのみサブウィンドウW1、W1aを表示することによって、ユーザの注意をより確実に喚起することができる利点がある。
【0094】
以上で説明した本実施例の経路案内システムによれば、規制条件によって待ち時間が生じた場合に、待合場所およびその待合場所を経由する経由経路を案内することができ、実用性、利便性に優れた経路案内を実現することができる。また、待ち時間を過ごす際の快適さと、経由経路の所要時間または距離の増加分とを考慮することにより、規制ノードから比較的近い範囲で快適な待合場所を探索することができる。
【0095】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。本実施例は、歩行者用の経路案内システムに限らず、車両用の経路案内システムに適用することも可能である。また、本実施例では、サーバ200と端末100からなるシステムを例示したが、サーバ200の機能を端末100に組み込み、スタンドアロンの装置として構成することも可能である。
【図面の簡単な説明】
【0096】
【図1】実施例としての経路案内システムの構成を示す説明図である。
【図2】地図DB250および時刻表DB252のデータ構造を示す説明図である。
【図3】経路探索処理例を示す説明図である。
【図4】待合場所の抽出処理例を示す説明図である。
【図5】出発地Sを待合場所とした場合の経由経路を示す説明図である。
【図6】コンビニエンスストアEを待合場所とした場合の経由経路を示す説明図である。
【図7】喫茶店Hを待合場所とした場合の経由経路を示す説明図である。
【図8】目的地Gを待合場所とした場合の経由経路を示す説明図である。
【図9】経路探索処理のフローチャートである。
【図10】経由経路設定処理のフローチャートである。
【図11】経路案内処理のフローチャートである。
【図12】経路案内の表示画面を例示する説明図である。
【符号の説明】
【0097】
100…端末
110…主制御部
120…通信部
130…コマンド入力部
140…GPS
150…表示制御部
200…サーバ
220…通信部
230…経路探索部
240…経路案内部
250…地図DB
250L…リンクデータ
250N…ノードデータ
252…時刻表DB
254…ユーザDB
【特許請求の範囲】
【請求項1】
経路案内システムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力部と、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照部と、
前記ネットワークデータに基づいて、前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断部と、
前記いずれかのノードにおいて待ち時間有りと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経路探索部とを備える経路案内システム。
【請求項2】
請求項1記載の経路案内システムであって、
前記ネットワークデータは、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報とを含んでおり、
前記ネットワークデータを参照して、前記待ち時間が要求される規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する待合場所選択部を有し、
前記経路探索部は、前記出発地から前記待合ノードを経由して前記規制ノードに至る経由経路を探索する経由経路探索部を備える経路案内システム。
【請求項3】
請求項2記載の経路案内システムであって、
前記経由経路探索部は、前記経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて該経由経路の評価値を算出し、
前記待合ノードが複数存在する場合に、前記評価値に基づいていずれか一つの経由経路を選択する経由経路選択部を備える経路案内システム。
【請求項4】
請求項3記載の経路案内システムであって、
前記待合場所適性情報は、前記利用の適否を複数段階の指標値で表すデータを含み、
前記経由経路選択部は、更に、前記指標値も用いて前記選択を行う経路案内システム。
【請求項5】
請求項3または4記載の経路案内システムであって、
前記待合場所適性情報は、前記待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含んでおり、
前記待合場所選択部は、待合ノードでの待ち時間と、前記上限値および下限値の少なくとも一方との大小関係を考慮して前記選択を行う経路案内システム。
【請求項6】
請求項3〜5いずれか記載の経路案内システムであって、
前記規制条件は、前記ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類され、
前記待合場所選択部は、前記規制ノードに付されている規制条件が、前記時刻規制条件である場合と前記時間帯規制条件である場合とで、前記選択の方法を切り換える経路案内システム。
【請求項7】
請求項1〜6いずれか記載の経路案内システムであって、
前記ネットワークデータを参照して、前記出発地から前記規制ノードを回避して前記目的地に至る迂回経路を探索する迂回経路探索部と、
前記迂回経路および前記経由経路それぞれの距離および所要時間の少なくとも一方に基づいて、前記迂回経路および経由経路のいずれかを前記出発地から目的地に至る経路として推奨する経路推奨部とを備える経路案内システム。
【請求項8】
請求項1〜7いずれか記載の経路案内システムであって、
地図上に、前記経由経路とその他の経路とを異なる表示態様で表示する経路案内部を備える経路案内システム。
【請求項9】
請求項2〜8いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を表示する場合には、前記規制条件に基づき、前記待合ノードを出発すべき時刻をユーザに報知する経路案内システム。
【請求項10】
請求項1〜9いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を案内する場合には、前記規制ノードに到達すべき到達時刻または該到達時刻までの余裕時間をユーザに提示する経路案内システム。
【請求項11】
コンピュータによって、経路を案内するためのコンピュータプログラムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力サブプログラムと、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照サブプログラムと、
前記ネットワークデータに基づいて、前記規制条件を考慮せずに前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断サブプログラムと、
前記いずれかのノードにおいて待ち時間ありと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経由経路探索サブプログラムとを備えるコンピュータプログラム。
【請求項1】
経路案内システムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力部と、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照部と、
前記ネットワークデータに基づいて、前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断部と、
前記いずれかのノードにおいて待ち時間有りと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経路探索部とを備える経路案内システム。
【請求項2】
請求項1記載の経路案内システムであって、
前記ネットワークデータは、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報とを含んでおり、
前記ネットワークデータを参照して、前記待ち時間が要求される規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する待合場所選択部を有し、
前記経路探索部は、前記出発地から前記待合ノードを経由して前記規制ノードに至る経由経路を探索する経由経路探索部を備える経路案内システム。
【請求項3】
請求項2記載の経路案内システムであって、
前記経由経路探索部は、前記経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて該経由経路の評価値を算出し、
前記待合ノードが複数存在する場合に、前記評価値に基づいていずれか一つの経由経路を選択する経由経路選択部を備える経路案内システム。
【請求項4】
請求項3記載の経路案内システムであって、
前記待合場所適性情報は、前記利用の適否を複数段階の指標値で表すデータを含み、
前記経由経路選択部は、更に、前記指標値も用いて前記選択を行う経路案内システム。
【請求項5】
請求項3または4記載の経路案内システムであって、
前記待合場所適性情報は、前記待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含んでおり、
前記待合場所選択部は、待合ノードでの待ち時間と、前記上限値および下限値の少なくとも一方との大小関係を考慮して前記選択を行う経路案内システム。
【請求項6】
請求項3〜5いずれか記載の経路案内システムであって、
前記規制条件は、前記ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類され、
前記待合場所選択部は、前記規制ノードに付されている規制条件が、前記時刻規制条件である場合と前記時間帯規制条件である場合とで、前記選択の方法を切り換える経路案内システム。
【請求項7】
請求項1〜6いずれか記載の経路案内システムであって、
前記ネットワークデータを参照して、前記出発地から前記規制ノードを回避して前記目的地に至る迂回経路を探索する迂回経路探索部と、
前記迂回経路および前記経由経路それぞれの距離および所要時間の少なくとも一方に基づいて、前記迂回経路および経由経路のいずれかを前記出発地から目的地に至る経路として推奨する経路推奨部とを備える経路案内システム。
【請求項8】
請求項1〜7いずれか記載の経路案内システムであって、
地図上に、前記経由経路とその他の経路とを異なる表示態様で表示する経路案内部を備える経路案内システム。
【請求項9】
請求項2〜8いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を表示する場合には、前記規制条件に基づき、前記待合ノードを出発すべき時刻をユーザに報知する経路案内システム。
【請求項10】
請求項1〜9いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を案内する場合には、前記規制ノードに到達すべき到達時刻または該到達時刻までの余裕時間をユーザに提示する経路案内システム。
【請求項11】
コンピュータによって、経路を案内するためのコンピュータプログラムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力サブプログラムと、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照サブプログラムと、
前記ネットワークデータに基づいて、前記規制条件を考慮せずに前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断サブプログラムと、
前記いずれかのノードにおいて待ち時間ありと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経由経路探索サブプログラムとを備えるコンピュータプログラム。
【図9】
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図10】
【図11】
【図12】
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図10】
【図11】
【図12】
【公開番号】特開2007−93229(P2007−93229A)
【公開日】平成19年4月12日(2007.4.12)
【国際特許分類】
【出願番号】特願2005−279176(P2005−279176)
【出願日】平成17年9月27日(2005.9.27)
【出願人】(597151563)株式会社ゼンリン (155)
【Fターム(参考)】
【公開日】平成19年4月12日(2007.4.12)
【国際特許分類】
【出願日】平成17年9月27日(2005.9.27)
【出願人】(597151563)株式会社ゼンリン (155)
【Fターム(参考)】
[ Back to top ]