(57)【要約】【課題】  特定の時間帯で通行止めになるなどの規制条件を考慮して、実用的な経路探索を行う。【解決手段】  経路探索に用いるデータとして、地図ＤＢ２５０、時刻表ＤＢ２５２、ユーザＤＢ２５４を設ける。地図ＤＢ２５０は、通路をノード、リンクで表すネットワークデータを格納している。時刻表ＤＢ２５２は、交通機関の発車時間、特定の時間帯での通行止めなど、リンクを通行するための規制条件を格納している。サーバ２００は、規制条件を考慮して探索を行う。規制条件に応じて待ち時間が生じる場合には、好適な待合場所を求め、その待合場所を経由する経由経路を探索、案内する。待合場所の選択時には、規制箇所からの距離または所要時間と、待合場所としての好適度の双方を考慮する。こうすることで、快適な待合場所をユーザに提供可能となり、実用性、利便性に優れた経路案内を実現することができる。【選択図】  図１２
2007093229.tif 000002
【特許請求の範囲】
【請求項１】
経路案内システムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力部と、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照部と、
前記ネットワークデータに基づいて、前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断部と、
前記いずれかのノードにおいて待ち時間有りと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経路探索部とを備える経路案内システム。
【請求項２】
請求項１記載の経路案内システムであって、
前記ネットワークデータは、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報とを含んでおり、
前記ネットワークデータを参照して、前記待ち時間が要求される規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する待合場所選択部を有し、
前記経路探索部は、前記出発地から前記待合ノードを経由して前記規制ノードに至る経由経路を探索する経由経路探索部を備える経路案内システム。
【請求項３】
請求項２記載の経路案内システムであって、
前記経由経路探索部は、前記経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて該経由経路の評価値を算出し、
前記待合ノードが複数存在する場合に、前記評価値に基づいていずれか一つの経由経路を選択する経由経路選択部を備える経路案内システム。
【請求項４】
請求項３記載の経路案内システムであって、
前記待合場所適性情報は、前記利用の適否を複数段階の指標値で表すデータを含み、
前記経由経路選択部は、更に、前記指標値も用いて前記選択を行う経路案内システム。
【請求項５】
請求項３または４記載の経路案内システムであって、
前記待合場所適性情報は、前記待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含んでおり、
前記待合場所選択部は、待合ノードでの待ち時間と、前記上限値および下限値の少なくとも一方との大小関係を考慮して前記選択を行う経路案内システム。
【請求項６】
請求項３〜５いずれか記載の経路案内システムであって、
前記規制条件は、前記ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類され、
前記待合場所選択部は、前記規制ノードに付されている規制条件が、前記時刻規制条件である場合と前記時間帯規制条件である場合とで、前記選択の方法を切り換える経路案内システム。
【請求項７】
請求項１〜６いずれか記載の経路案内システムであって、
前記ネットワークデータを参照して、前記出発地から前記規制ノードを回避して前記目的地に至る迂回経路を探索する迂回経路探索部と、
前記迂回経路および前記経由経路それぞれの距離および所要時間の少なくとも一方に基づいて、前記迂回経路および経由経路のいずれかを前記出発地から目的地に至る経路として推奨する経路推奨部とを備える経路案内システム。
【請求項８】
請求項１〜７いずれか記載の経路案内システムであって、
地図上に、前記経由経路とその他の経路とを異なる表示態様で表示する経路案内部を備える経路案内システム。
【請求項９】
請求項２〜８いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を表示する場合には、前記規制条件に基づき、前記待合ノードを出発すべき時刻をユーザに報知する経路案内システム。
【請求項１０】
請求項１〜９いずれか記載の経路案内システムであって、
前記経路案内部は、前記経由経路を案内する場合には、前記規制ノードに到達すべき到達時刻または該到達時刻までの余裕時間をユーザに提示する経路案内システム。
【請求項１１】
コンピュータによって、経路を案内するためのコンピュータプログラムであって、
出発地、出発時刻および目的地の指定を受け付ける指定入力サブプログラムと、
通路をノードおよびリンクで表すとともに、前記ノードおよびリンクの少なくとも一部に対し、採りうる通行態様を時刻に応じて規制する規制条件が付されたネットワークデータを参照するネットワークデータ参照サブプログラムと、
前記ネットワークデータに基づいて、前記規制条件を考慮せずに前記出発地から目的地に至る経路を探索した上で、該経路上の各ノードへの到着予測時刻に基づいて前記規制条件に基づく待ち時間の有無を判断する待合要否判断サブプログラムと、
前記いずれかのノードにおいて待ち時間ありと判断された場合に、前記出発地と該待ち時間が生じる規制ノードとの間で、前記待合要否判断部が探索した経路よりも前記待ち時間が短くなる経由経路を探索する経由経路探索サブプログラムとを備えるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間によって通行可否や通行の方向が異なる規制箇所が存在する場合における経路探索、案内技術に関する。
【背景技術】
【０００２】
車両または歩行者用に、指定された出発地から目的地に至る最適な経路を探索、案内する経路案内装置が提案されている。経路案内装置は、通路をノード、リンクで表したネットワークデータを参照し、各リンクに付された評価値、即ちコストの総和が最小となる経路を探索する。歩行者用の経路案内システムでは、電車やフェリーなどの公共交通機関を通路に含めて経路探索を行う技術も提案されている（特許文献１〜３参照）。
【０００３】
公共交通機関を含む場合には、所要時間に基づいてコストを設定することにより、所要時間が最短となる経路の探索が行われる。公共交通機関は、出発時刻が予め定められているため、公共交通機関を利用する際には、この出発時刻との関係で無駄な待ち時間が生じる場合もある。特許文献１〜３は、公共交通機関の時刻表をデータベースとして備えることにより、各公共交通機関の待ち時間も考慮して最短時間の到達経路を探索する技術を開示している。
【０００４】
【特許文献１】特開平８−１６６２４８号公報
【特許文献２】特開２００１−１６５６８３号公報
【特許文献３】特開２００１−２８０９９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術では、経路探索時に、待ち時間は考慮されているものの、待合場所については考慮されていなかった。つまり、従来技術では、規制が付されたノード（以下、「規制ノード」と称する）で待つことを前提として経路探索が行われているが、必ずしも規制ノードは待合いに適しているとは限らなかった。待ち時間によっては、ユーザは喫茶店やコンビニエンスストアなどでの待機を望む場合もある。従来、これらの待合場所はユーザ自身が探す必要があった。また、待合場所への往復の経路を考慮すると、当初予定されていた公共交通機関ではなく、徒歩その他の移動手段を利用する方が好ましい経路が得られる場合もあった。このように従来の経路探索は、実用性、利便性という観点で、更に改善の余地が残されていた。
【０００６】
かかる課題は、交通機関を利用する場合に限られるものではない。例えば、時間によって通行禁止となる道路、一方通行の規制方向が変わる道路、及び右左折禁止などの規制が解除される交差点、時間帯によって通行止めが解除される有料道路などについても同様に、規制が切り替わる直前に規制箇所に到達するか否かによって探索結果が大きく影響を受ける可能性がある。時間帯によって通行可能となる経路が探索されたとしても、車両の場合には、通行規制が付された交差点等で規制が解除されるまで待つことはできないことがあり、現実には探索された経路を走行することができなかったり、ユーザ自身で待機場所を探したりする必要があった。本発明は、こうした課題に鑑み、探索された経路の途中で待ち時間が生じる場合における経路案内の実用性、利便性を向上することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、出発地および目的地の指定を受け付けて両者間の経路を探索する経路案内システムとして構成することができる。車両および歩行者のいずれを対象とするものであってもよい。経路探索には、通路をノードおよびリンクで表したネットワークデータを用いる。ネットワークデータに含まれるノードおよびリンクの少なくとも一部には、規制条件が付されており、ノードやリンクを通行する際に採りうる通行態様が時刻に応じて規制される。規制条件としては、例えば、交通機関のように所定の出発時刻にならないと利用できないという規制や、時間に応じて変化する通行禁止、一方通行、右左折禁止などの通行規制等が挙げられる。
【０００８】
経路案内システムは、ネットワークデータに基づいて、まず、出発地から目的地に至る経路を探索した上で、経路上の各ノードへの到着予測時刻に基づいて規制条件に基づく待ち時間の有無を判断する。経路探索は、ノード、リンクに付されたコストが最小となる経路を求めるダイクストラ法など種々の方法を採ることができる。ダイクストラ法を用いる場合、リンクの距離に基づいてコストを設定することによって最短距離の経路を求めるようにしてもよいし、リンク間の移動の所要時間に基づいてコストを設定することによって最短時間の経路を求めるようにしてもよい。上述の経路探索は、規制条件を無視して行っても良いし、規制条件を考慮して行っても良い。後者の方法では、例えば、規制条件に基づいて待ち時間が発生する場合には、その待ち時間を所定の演算式でコストに反映させた上で経路探索する方法を採ることができる。後者の方法では、規制条件が付されたノード、リンクを通過する経路と、回避する迂回経路とを、規制ノードでの待ち時間も考慮した上で比較して経路を求めることができる利点がある。
【０００９】
経路案内システムは、こうして探索された経路において待ち時間が要求される規制ノードが存在する場合には、出発地と規制ノードとの間で、最初に探索された経路よりも待ち時間が短くなる経路を探索する。この経路は、主として最初に探索された経路と異なる点を経由する経路となることが多いため、以下、説明の便宜上、経由経路と称するものとする。かかる経由経路は、例えば、最初に探索された経路のみを除外して、ダイクストラ法で経路探索をすることにより求めることができる。また、最初に探索された経路上にないいずれかのノードまたはリンクを経由地に指定し、この経由地を通る経路を求めるようにしてもよい。また、規制ノードでの待ち時間が短くなる経路であればよいから、最初に探索された経路上に存在するノードのうち、規制ノード以外のノードで待ち時間を費やすようにしてもよい。
【００１０】
本発明によれば、規制ノードで待ち時間が生じた場合に、そこでの待ち時間を短縮させる代替経路を提示することができる。従って、規制ノードが待合いに適していない場合でも、実用的な経路を提示することが可能となる。
【００１１】
ネットワークデータには、少なくとも一部の地点について、その場に留まって時間の経過を待つ待合場所としての利用の適否を直接または間接に示す待合場所適性情報を付しても良い。待合場所適性情報は、例えば、ノードまたはリンクの属性として設定することができる。待合場所適性情報は、例えば、待合場所としての利用の「適」または「否」を表すフラグとしてもよいし、待合場所としての好適度を複数段階で表す指標値としてもよい。
【００１２】
また、待合場所適性情報は、この好適度を間接的に表す情報とすることもできる。かかる情報としては、例えば、「フェリー乗り場」、「駅」など、ある程度の時間の待合いが前提とされている施設であることを示す属性情報、「喫茶店」や「レストラン」など、ある程度の時間を過ごすことが前提とされている施設であることを示す属性情報などを用いることができる。このような情報を用いる場合には、更に、上述の属性情報と、好適度を表す指標値との対応関係をテーブル等の形式で記憶した変換データベースを用意しておき、経路探索時には、この変換データベースに基づいて求まる指標値を用いるようにしてもよい。  
【００１３】
待合場所適性情報が用意されている場合、経路案内システムは待ち時間が要求される場合には、待合場所適性情報を利用して、規制ノードから所定範囲内で待合場所に適した待合ノードを少なくとも一つ選択する。待合ノードを選択する範囲は、任意に設定可能であり、例えば、規制ノードから所定の直線距離内にある範囲、規制ノードから所定の道のり内にある範囲、規制ノードから所定時間内で到達できる範囲、探索された経路上の各ノードから所定の直線距離内や所定の道のり内にある範囲、経路探索時に候補の経路として挙げられたノードの範囲内などとすることができる。
【００１４】
経路案内システムは、こうして選択された待合ノードのそれぞれにつき、待合ノードを経由して規制ノードに至る経由経路を探索する。規制ノードが一カ所の場合には、経由経路は、出発地から待合ノードを経由して規制ノードに至る経路となる。規制ノードが複数ある場合は、出発地または直前の規制ノード通過後のいずれかのノードからの経由経路を求めるようにしてもよい。こうすれば、待合場所の経由経路を探索することにより、待ち時間が要求される時の経路案内の実用性、利便性を向上させることができる。
【００１５】
上述の待合場所適性情報は、予めネットワークデータの一部として格納されるようにしてもよいし、ユーザがカスタマイズ可能としてもよい。ユーザが設定した待合場所適性情報は、例えば、予め用意されたネットワークデータとは分けて、ユーザ固有のユーザデータベースとして格納するようにしてもよい。ユーザがカスタマイズ可能とすることにより、ユーザの好みや要望に応じた待合場所を提示することが可能となる。例えば、時間に余裕があれば銀行や郵便局で所用を済ませようと考えているユーザは、予め銀行や郵便局に対して待合場所適性情報を設定しておくことにより、これらの所用を効率的に済ませられる経路を得ることが可能となる。
【００１６】
こうした実用性をより向上させるため、待合場所適性情報をユーザがカスタマイズする際には、銀行等の位置を支点単位で個別具体的に指定するのではなく、「○○銀行」という単位での指定や、単に「銀行」という一般的な指定を許容してもよい。経路案内システムは、規制ノードから所定範囲内で、この一般的な指定の条件に該当する店舗等を検索し、そこを待合い場所に選択して経由経路を求めればよい。
【００１７】
待合ノードが複数選択されている時、利用する待合ノードは、ユーザに選択させてもよいし、経路案内システムが自動的に決定してもよい。前者の態様では、例えば、待合ノードを地図上などに一覧表示し、ポインティングデバイス等でユーザに指定させる方法を採ることができる。待合ノードを地図上に表示する際には、経由経路の距離、所要時間、待合ノードでの待ち時間などを判断の際の目安としてユーザに提示するようにしても良い。
【００１８】
待合ノードを自動的に決定する方法としては、例えば、経由経路の距離、所要時間、および待合ノードでの待ち時間の少なくとも一部を用いて所定の演算により経由経路の評価値を算出し、この評価値に基づいていずれか一つの経由経路を選択する方法を採ることができる。評価値の算出式は任意に設定可能である。
【００１９】
先に説明した通り、本発明では、少なくとも一部のノードに対して待合場所適性情報を付されている。この待合場所適性情報は、単に利用可否を表すデータとすることもできるし、利用の適否を複数段階の指標値で表すデータとすることができる。指標値は、任意に設定可能であるが、例えば、指標値が大きいほど待ち時間としての利用に適していることを表すものと定義してもよい。指標値は、待ち時間に関わらず一定値としてもよいし、待ち時間に応じて変化させるようにしてもよい。例えば、コンビニエンスストアは、待ち時間が短い場合には高い指標値とし、待ち時間が長くなるほど低い指標値に設定することができる。コンビニエンスストアは、気楽に利用でき、空調も整っている点で短時間の待合いには適しているが、座ることができないため長時間の待ち時間に対しては適しているとは言えないからである。
【００２０】
このように複数段階の指標値が設定されている場合には、この指標値も用いて上述の評価値を算出し、待合ノードの選択を行うようにしてもよい。例えば、「評価値＝所要時間＋（待合ノードでの待ち時間／指標値）」のように、指標値は待合ノードでの待ち時間の重み係数として用いることができる。指標値を考慮することにより、より快適な環境で時間を過ごすことができる待合場所を提示することができ、経路案内システムの利便性を向上させることができる。
【００２１】
待合場所適性情報には、待合場所で待つことが許容される待ち時間の上限値および下限値の少なくとも一方を含めてもよい。例えば、上述のコンビニエンスストアに対しては、座ることができないという点を考慮し、待ち時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待ち時間の下限値を設定することができる。このように待ち時間の上限値、下限値等が設定されている場合には、経路案内システムは、待合ノードでの待ち時間と、上限値および下限値の少なくとも一方との大小関係を考慮して待合ノードの選択を行ってもよい。こうすることにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【００２２】
本発明の対象となる規制条件は、例えば、ノードまたはリンクを通行可能となる時刻を規制する時刻規制条件と、通行可能となる時間帯を規制する時間帯規制条件とを含む複数種類の条件に分類することができる。例えば、交通機関の発車時刻は時刻規制条件に相当し、所定時間帯のみ通行止めが解除される規制などは時間帯規制条件に相当する。このように複数種類の規制条件が付されている場合、経路案内システムは、規制ノードに付されている規制条件が、時刻規制条件である場合と時間帯規制条件である場合とで、待合ノードの選択の方法を切り換えてもよい。例えば、時刻規制条件の場合、規制ノードへの到達時刻が予定時刻から遅れることは許されないため、規制ノードの近くに位置する待合ノードを優先して選択することが好ましい。一方、時間規制条件の場合については、規制ノードへの到達時刻に対する制約は比較的緩やかであるため、規制ノードからの距離よりも待ち時間を過ごす際の快適さを優先して待合ノードを選択することが好ましい。もっとも、ここで示したのは、待合ノードの選択方法の切り換えの一例に過ぎず、ここに例示した他、種々の選択方法を使い分けることが可能である。
【００２３】
経路案内システムは、更に、出発地から規制ノードを回避して目的地に至る迂回経路を探索し、この迂回経路および経由経路のいずれかを出発地から目的地に至る経路として推奨するようにしてもよい。迂回経路および経由経路の選択は、それぞれの距離および所要時間の少なくとも一方に基づいて行うことができる。例えば、経路探索時に用いられるコストに換算し、迂回経路および経由経路のうちコストの小さい方を選択するようにすることができる。こうすることにより、待合場所への経由経路を採ることで目的地までの距離が迂回経路よりも長くなり、結果として不利な経路を選択したことになるという弊害を回避することが可能となる。
【００２４】
経路案内システムは探索された経路を地図上に表示してユーザに案内するようにしてもよい。この場合には、経由経路とその他の経路とを異なる表示態様で表示する方法を採っても良い。こうすることにより、待合場所に向かうために目的地からそれた経路を案内されたとしても、ユーザはその意味を理解することができる利点がある。
【００２５】
経由経路を表示する場合には、規制条件に基づき、待合ノードを出発すべき時刻をユーザに報知するようにしてもよい。報知は、画面上の表示や音声出力など、種々の方法で行うことができる。かかる報知により、ユーザは待合場所で安心して時間を過ごすことが可能となる。
【００２６】
また、経由経路を案内する場合には、規制ノードに到達すべき到達時刻、または到達時刻までの余裕時間をユーザに提示するようにしてもよい。こうすることで、ユーザは規制ノードでの規制条件を考慮して、移動速度を調整することができ、規制条件による制約を無理なく回避して経路を通行することが可能となる。
【００２７】
本発明は、上述の特徴を必ずしも全て備えている必要はない。上述の特徴は、適宜、一部を省略したり、組み合わせたりすることが可能である。また、本発明は、上述した経路案内システムとしての構成の他、コンピュータによって経路探索や経路案内を行う経路探索方法、経路案内方法の態様を採ることもできる。本発明は、更に、これらの機能を実現するためのコンピュータプログラム、かかるコンピュータプログラムを記録した記録媒体の態様を採ることもできる。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００２８】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｃ．経路探索：
Ｃ１．経路探索処理例：
Ｃ２．経路探索処理：
Ｃ３．経由経路設定処理：
Ｃ４．変形例：
Ｄ．経路案内：
【００２９】
Ａ．システム構成：
図１は実施例としての経路案内システムの構成を示す説明図である。本実施例では、歩行者用の経路案内システムとしての構成例を示すが、車両用の経路案内システムとして構成することもできる。経路案内システムは、携帯電話を利用した端末１００とサーバ２００とをネットワークＩＮＴで接続して構成されている。ネットワークＩＮＴは無線通信を利用したネットワークであり、ＬＡＮやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。端末１００は、携帯電話の他、いわゆる車両用のナビゲーション装置やＰＤＡ、ネットワーク通信機能を有するパーソナルコンピュータなどを利用することができる。歩行者用の経路案内システムとして構成する場合、車両用のナビゲーション装置は、車両から取り外して携帯可能としておくことが望ましい。
【００３０】
端末１００は、ユーザの操作に応じて、経路探索および経路案内に必要な指示をサーバ２００に送信するための機能を奏する。図中には、端末１００の機能ブロックを併せて示した。端末１００は、ＣＰＵ、ＲＡＭ、ＲＯＭを備えたマイクロコンピュータを制御装置として内蔵しており、このＣＰＵはＲＯＭに記憶されたソフトウェアを実行することで、図示する各機能ブロックを構成する。これらの機能ブロックは、このようにソフトウェア的に構成する他、ハードウェア的に構成することも可能である。
【００３１】
通信部１２０は、ネットワークＩＮＴを介してサーバ２００と通信する機能を奏する。ＧＰＳ１４０は、全地球測位システム（Global Positioning System）を利用して、端末１００の現在位置の緯度、経度を検出する。コマンド入力部１３０は、スイッチ等に対するユーザ操作に基づいて、経路探索や経路案内に関するコマンドを入力する。コマンドとしては、図示した通り、経路探索の目的地の指定、案内経路の選択などが挙げられる。表示制御部１５０は、端末１００のディスプレイに、これらのコマンド入力用のメニューを表示したり、サーバ２００から受信した経路案内データに基づいて地図を表示させたりする。主制御部１１０は、上述した各機能ブロックを統括制御することで、端末１００の全体機能を制御する。
【００３２】
サーバ２００は、端末１００からのコマンドに基づいて、種々のデータベースを参照しながら、経路探索を行ったり、経路案内を行ったりする。図中には、これらの機能を実現するための機能ブロックおよびデータベースの例を示した。各機能ブロックは、サーバ２００のＣＰＵが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００３３】
サーバ２００が利用するデータベースは地図ＤＢ２５０、時刻表ＤＢ２５２、ユーザＤＢ２５４の３種類である。地図ＤＢ２５０は、通路をノード、リンクで表したネットワークデータ、および地図描画用のポリゴンや文字データからなる描画データを有している。本実施例では、ノードおよびリンクの少なくとも一部には、許容される通行態様が時刻によって変化するものが存在する。この規制条件としては、例えば、出発時刻が規定されている公共交通機関、所定時刻になると閉鎖される駅構内の通路などが挙げられる。時刻表ＤＢ２５２は、この規制条件を記録するデータベースである。地図ＤＢ２５０および時刻表ＤＢ２５２のデータ構造については後述する。
【００３４】
ユーザＤＢ２５４は、ユーザＩＤ、氏名などの書誌的な登録情報と共に、ユーザが歩行する際の移動速度に関する設定や、距離優先／時間優先などの経路探索に関する要望事項を格納している。図中にはユーザＤＢ２５４の内容として移動速度に関する登録内容を例示した。本実施例では、移動速度は、移動可能な距離と組み合わせて登録されている。図中の例では、通常利用される移動速度（以下、「通常速度」と呼ぶこともある）は「４ｋｍ／ｈ」であり、移動可能な距離には制約がないことを表している。やや早足の「５ｋｍ／ｈ」では、３ｋｍまで移動可能であり、駆け足の「１０ｋｍ／ｈ」では０．５ｋｍまで移動可能であることを表している。これらの情報は、ユーザが端末１００を操作して登録、変更可能である。図中の例では、３通りの移動速度が登録されているが、更に多くの移動速度を登録可能としてもよい。
【００３５】
通信部２２０は、端末１００とのネットワークＩＮＴ経由での通信を制御する。経路探索部２３０は、上述の３種類のデータベースを参照して、ユーザから指定された出発地、目的地間の経路を探索する。経路探索部２３０は、ユーザからの指示に応じて、移動速度などの探索条件を複数種類に変化させ、それぞれの条件に対応する経路を探索することが可能である。また、時刻表ＤＢ２５２を参照することにより、上述の規制条件も考慮して経路探索を行う。経路探索方法については後述する。
【００３６】
経路案内部２４０は、探索された経路を地図上に表示して案内するための経路案内データを生成し、端末１００に送信する。上述の通り、経路探索は、種々の探索条件に基づいて行われ、規制条件も考慮して行われている。経路案内部２４０は、これらの条件を反映した案内表示を実現する。経路案内方法については後述する。
【００３７】
Ｂ．データ構造：
図２は地図ＤＢ２５０および時刻表ＤＢ２５２のデータ構造を示す説明図である。地図ＤＢ２５０については、経路探索用のネットワークデータの構造のみを例示した。図の中央に例示するように、ネットワークデータは、ノードＮ１〜Ｎ８およびリンクＬ１〜Ｌ９等で構成される。リンクＬ１〜Ｌ９は歩行者が通行可能な通路を表しており、ノードＮ１〜Ｎ８はリンクＬ１〜Ｌ９の端点または接続点を表している。
【００３８】
地図ＤＢ２５０は、上述のノード、リンクに関するデータを、それぞれノードデータ２５０Ｎ、リンクデータ２５０Ｌとして格納している。図中に示す通り、リンクデータ２５０Ｌには、リンクＩＤ、形状、時刻表、速度規制、距離などの情報が記録される。形状は、リンクが通過する地点の座標（緯度、経路）を表した点列データである。座標には、高さを表す情報を含めても良い。図中の例では、リンクＬ９について、ノードＮ２、Ｎ７を含む４点が格納されている。本実施例では、ノードについてはノードＩＤを格納し、その位置はノードデータ２５０Ｎを参照することで得られるようにしたが、ノードについても他の通過地点と同じく座標を格納するようにしてもよい。時刻表とは、時刻表ＤＢに格納されている情報へのリンクを表している。図中の例Ｌ９では、時刻に応じて変化する規制条件が付されていないため、時刻表の項目には「無し」が登録されている。後述するように、リンクＬ３、Ｌ４、Ｌ６のように時刻に応じて変化する規制条件が付されている場合には、時刻表ＤＢ２５２に格納されているデータのインデックスである「時刻表ＩＤ」が格納されることになる。速度規制とは、そのリンクを通行する際の上限速度を表している。距離とは、そのリンクの区間距離である。
【００３９】
リンクデータ２５０Ｌの内容は、任意に設定可能であり、これらの情報の一部を省略してもよいし、ここに例示していない種々の属性情報を格納するようにしてもよい。例えば、階段や坂道などの経路種別や、ガードレールや街灯などの設備の有無等を属性情報として格納することができる。かかる属性情報が用意されている場合には、「階段を避けたい」、「ガードレールが整備されている経路を優先したい」などの経路に対する要望事項を反映した経路探索を実行することが可能となる。例えば、「階段を避けたい」という要望が出されている場合には、「階段」という属性情報が記録されているリンクのコストを増加させることによって、階段が選択される可能性を抑制することが可能となり、要望に沿った経路を探索することが可能となる。
【００４０】
ノードデータ２５０Ｎには、図示するようにノードＩＤ、位置、時刻表、通行規制、待合好適度、待合許容時間などの情報が記録される。「喫茶店」、「コンビニエンスストア」、「銀行」、「郵便局」などノードの種別を表す情報を含めてもよい。ノードの位置は、緯度、経度の座標で記録される。座標には、高さを表す情報を含めても良い。時刻表は、リンクデータ２５０Ｌと同様、時刻表ＤＢ２５２に格納されている情報へのリンクを表している。通行規制とは、右左折禁止など、時刻に応じて変化しない固定的な通行規制である。例えば、図中のノードＮ４について、Ｎ３方向から来てＮ６方向へ左折する通行が禁止される場合には、通行規制欄には、「Ｎ３→Ｎ４→Ｎ６」という形でデータを格納すればよい。通行規制情報の記録方法は、これに限らず、種々の形式を採用することができる。
【００４１】
待合好適度とは、探索された経路において規制条件による待ち時間が生じた場合、その時間経過を待つ待合場所としての適性を表す指標であり、後述する通り、複数の待合場所の中から、案内対象とすべき待合場所を選択する際に用いられる値である。本実施例では、適性を０〜５の６段階の整数値で表すものとした。待合好適度「０」は、待合場所として使用できない場所を表しており、値が大きくなるほど待合に適していることを表している。待合好適度「０」に該当し得る場所としては、例えば、自動車用の案内装置では交差点の中央などが当たり、歩行者用の案内では駅の改札口、エレベータ、エスカレータなどが当たり得る。
【００４２】
待合許容時間とは、待合場所としての使用が許容される下限値および上限値を表す。待合許容時間も、後述する通り、複数の待合場所の中から、案内対象とすべき場所を選択する際の基準として用いられる値であるから、ユーザの要望に添った選択結果となるよう任意に設定することができる。従って、待合許容時間は、必ずしも明確な規制条件である必要はなく、ユーザの体力的な限界や心理的な限界を考慮した一般的な許容範囲で構わない。例えば、コンビニエンスストアに対応するノードに対しては、座ることができないという点を考慮し、待合許容時間の上限値を設定することができる。逆に、喫茶店など、注文してサービスを受ける場所に対応するノードに対しては、利用時に一定限度以上の時間が要求されるという点を考慮し、待合許容時間の下限値を設定することができる。
【００４３】
待合好適度や待合許容時間は、ノードの属性として格納する他、リンクの属性として格納してもよい。また、本実施例では、上述のように待合好適度を直接に表す場合を例示しているが、「フェリー乗り場」や「駅」などのように待合場所としての適性を推測可能な情報を待合孔適度として用いるようにしてもよい。
【００４４】
また、待合好適度や待合許容時間は、予め地図ＤＢ２５０に組み込まれている情報の他、ユーザが任意に設定可能としてもよい。この情報は、地図ＤＢ２５０に直接登録可能としてもよいが、ユーザごとに設定内容を管理可能とするため、ユーザＤＢ２５４（図１参照）に登録可能とすることが好ましい。ユーザの設定内容には、ノードＩＤに代えて、「銀行」、「郵便局」などノードの種別を表す情報を用いるようにしてもよい。例えば、「銀行」に対し、「待合好適度＝５」、「待合許容時間＝２０〜３０分」などのように設定する方法を採ることができる。後述する経路探索処理時には、サーバ２００は、「銀行」に該当する種別情報を有するノードを検索することによって、ユーザが設定した内容を特定のノードに対する待合好適度、待合許容時間と同視して取り扱うことができる。
【００４５】
時刻表ＤＢ２５２には、時刻表ＩＤ、規制、時刻、開始遅れ、終了遅れなどの情報が格納されている。時刻表ＩＤは、登録されているそれぞれの情報を一義的に示すための識別データである。規制は、時刻表ＩＤが示す規制情報を表している。図中には、駅の入り口Ｇ１〜Ｇ３が午前０：３０〜午前４：３０の間で閉鎖され、駅構内のリンクＬ３，Ｌ４，Ｌ６が通行不能となる場合のデータを例示した。この場合、通行不能となるため、「規制」欄には、「通行止め」が格納され、時刻欄には、通行止めとなる時刻が格納される。複数の時間帯で通行止めとなる場合には、時刻欄に、複数の時間帯を格納することもできる。開始遅れは、この時間帯の開始時刻（図中の例では０：３０）が遅れる可能性を示し、終了遅れは終了時刻が遅れる可能性を示している。駅構内の通行止めについては、規定通りに閉鎖されるため、開始遅れ、終了遅れは「無し」と設定されている。「時刻表ＩＤ＝１」が付されたこのデータは、リンクＬ３、Ｌ４、Ｌ６に適用される。従って、リンクデータ２５０ＬのこれらのリンクＩＤに対応するデータの「時刻表」欄に「１」が格納されることになる。リンクデータの時刻表欄には、複数の時刻表ＩＤを格納可能としてもよい。
【００４６】
時刻表ＤＢ２５２には、上述のような「通行止め」の規制の他、種々の規制が格納可能である。例えば、本実施例では、電車などの交通機関の出発時刻も、その路線を通行可能な時間帯が限られているという意味で規制条件の一種とみなし、時刻表ＤＢ２５２で管理するものとした。この場合には、「規制」欄には、例えば、「電車発着」などと格納することで交通機関であることを示し、「時刻」欄に出発時刻および到着時刻からなる時刻表を格納することができる。出発時刻と途中の経過駅までの所要時間という形式で格納するようにしてもよい。交通機関の場合には、出発時間や到着時間が遅れる場合がある。出発時間の遅れは「開始遅れ」に記録し、到着時間の遅れは「終了遅れ」に記録することができる。これらの時間は、後述する通り、経路探索時に考慮される値であり、任意に設定可能であるが、一例として、過去所定期間内の平均遅れ時間や最大遅れ時間などに基づいて設定することができる。
【００４７】
Ｃ．経路探索：
本実施例における経路探索処理について説明する。まず、いくつかの具体例に基づいて処理概要を説明した後、経路探索処理を実現するためのフローチャートを説明する。
【００４８】
Ｃ１．経路探索処理例：
図３は経路探索処理例を示す説明図である。図中に経路探索の対象となるノード、リンクの構成を例示した。丸印はノードを表し、実線はリンクを表している。以後、ノードは丸印中の文字を用いて特定し、リンクはその両端のノードを用いて表す。例えば、ノードＳとノードＡとの間のリンクはリンクＳＡまたはリンクＡＳを表すものとする。各リンクに付された数字は、リンク間の移動に要する所要時間である。移動の所要時間は、ユーザの移動速度に応じて変化する。本実施例では、ユーザＤＢ２５４に登録された通常速度（図１では４ｋｍ／ｈ）を用いるものとした。経路探索時に用いる移動速度は、通常速度、最大速度などをユーザが選択可能としてもよいし、経路途中にある規制条件による制約を最も効率的に回避し得るようユーザＤＢ２５４を参照しながら経路案内システムが設定してもよい。
【００４９】
図示したネットワークデータを用いて、出発地Ｓを午前５：００に出発し、目的地Ｇに向かう所要時間最短の経路を探索する場合を考える。経路探索は、所要時間をコストとするダイクストラ法によって行うものとする。ダイクストラ法とは、各リンクに付されたコストの総和が最小となる経路を求める演算方法である。この例では、所要時間をコストとして用いるが、この他、リンクの距離をコストとして用いたり、所要時間や距離その他の情報を考慮して設定されたコストを用いたりすることも可能である。
【００５０】
ダイクストラ法の演算方法は周知であるため処理内容自体についての説明は省略し、結果概要のみを説明する。図の例で、出発地Ｓをスタートし、途中のノードＢまで至る経路とそのコストは、それぞれ次の通りとなる。
経路Ｓ→Ａ→Ｈ→Ｂ    …コスト＝４０；
経路Ｓ→Ａ→Ｂ        …コスト＝２２；
経路Ｓ→Ａ→Ｅ→Ｆ→Ｂ…コスト＝３０；
従って、ノードＢに至る最適経路は、経路Ｓ→Ａ→Ｂと求まる。この結果、ノードＣに至る最適経路は、経路Ｓ→Ａ→Ｂ→Ｃと求まる。この経路を採用した場合、ノードＣへの到達時刻は５：３０と予測される。
【００５１】
図中に示す通り、リンクＣＤには夜間２０：００〜６：００は通行止めとなる規制条件が付されている。従って、ノードＣに５：３０に到達した時点では、リンクＣＤを通行することはできない。以下、このように通行する時刻または時間帯が規制されているノードを規制ノードと称する。図の例では、リンクＣＤ間に規制条件が付されているが、出発地Ｓから目的地Ｇに向かう経路探索時にはノードＣにおいてのみ規制条件が問題となるため、ノードＣのみが規制ノードに該当する。
【００５２】
規制ノードＣから先の経路としては、「Ｃ→Ｉ→Ｄ」の迂回経路と、ノードＣで通行規制が解除されるまで待った上で「Ｃ→Ｄ」と通行する経路とがある。迂回経路のコストは７０である。ノードＣで待つ場合には、ノードＣでの待ち時間３０分を、リンクＣＤのコストに反映した上で、経路のコストを算出する。この結果、「Ｃ→Ｄ」のコストは５０となる。従って、ノードＣで３０分の待ち時間が生じたとしても、迂回経路よりは経路「Ｃ→Ｄ」の方がコスト小となることが分かる。
【００５３】
以上の探索処理の結果、図３の例によれば、「出発地Ｓ→Ａ→Ｂ→Ｃ→Ｄ→目的地Ｇ」という経路（図中、太線で示した経路）がコスト最小、即ち所要時間最短となる経路として求められる。この経路を採った場合には、ノードＣで３０分の待ち時間が生じることが分かる。本実施例では、このように待ち時間が生じた場合には、以下に示す処理によって、待合場所を特定し、待合場所を経由する経由経路を案内する。
【００５４】
図４は待合場所の抽出処理例を示す説明図である。リンクＣＤを通過するための待合場所であるから、待合場所は、出発地Ｓ〜ノードＣの間で探索される必要がある。以下では、図３に示した経路のうち、出発地Ｓ〜ノードＣ間のみを示す。この例では、規制ノードは、ノードＣの１カ所のみであるが、仮にリンクＤＧ上に、更に規制ノードＪ（図示せず）が存在する場合には、規制ノードＣと規制ノードＪとの間で、以下の処理と同様の処理によって待合場所が探索されることになる。
【００５５】
サーバ２００は、図示するように、規制ノードＣから所定範囲内で待合場所の候補となるノード（以下、待合ノードと称する）を抽出する。この抽出処理には、図２で示したノードデータ２５０Ｎの待合好適度が用いられる。待合好適度が所定値以上のノードを選択すればよい。値１以上を選択すれば広範に待合ノードが抽出されるし、更に高い待合好適度を要求すれば、候補となる待合ノード数は減少するものの待合いに快適な場所が抽出されることになる。
【００５６】
待合ノードを抽出する範囲は、種々の条件で規定することができる。例えば、１）図３に示した経路探索の過程で経路候補として挙げられたノードの範囲内、２）規制ノードから所定の所要時間内に到達可能な範囲、３）規定ノードから所定の道のり内、４）規定ノードから所定の直線距離内などの条件を用いることができる。図４では、条件１を用いた場合を例示した。この結果、待合ノードとして、図中に二重丸で示す４カ所、即ち出発地Ｓ、コンビニエンスストアＥ、喫茶店Ｈ、目的地Ｃが選択されたとする。次に、これらの各待合ノードを経由する経由経路を求め、待合場所としての適否を判断する処理例を示す。
【００５７】
図５は出発地Ｓを待合場所とした場合の経由経路を示す説明図である。経由経路を得るには、出発地から待合ノードまでの経路、待合ノードから規制ノードＣまでの経路をそれぞれダイクストラ法で求めればよい。図５の例では、出発地と待合ノードが同一であるため、経由経路は図３で得られる経路と同一の経路「Ｓ→Ａ→Ｂ→Ｃ」（図中の太線）となる。本実施例では、待合ノードを選択する際の第１の指標として、この経由経路の所要時間を求める。この例では３０分となる。
【００５８】
そして、第２の指標として、余裕時間、即ち待合ノードで過ごす時間を求める。余裕時間は次式によって求めることができる。
余裕時間＝規制ノードＣでの待ち時間−余剰時間；
余剰時間＝経由経路の所要時間−規制ノードＣまでの本来の経路の所要時間（図３で得られた経路の所要時間）；
図５の例では、余裕時間は３０分となる。
【００５９】
そして、所要時間、余裕時間、待合好適度を用いて次式により、待合ノードおよび経由経路の評価値を求める。
評価値＝所要時間＋（余裕時間／待合好適度）；
図５の例では、評価値は６０となる。この評価値は値が小さいほど好ましい経由経路であることを表している。評価値の内容は、経由経路を採ることによる所要時間の増大というデメリットと、快適な場所で待ち時間を過ごすことによるメリットとを加味した値となっている。待合好適度は、余裕時間を過ごす際の評価値の増加を抑制する因子として作用する。従って、この評価値を用いれば、待合好適度が高い快適な場所であれば、若干、所要時間が増大したとしても経由する価値があるという評価が得られることになる。評価値は任意に設定可能であり、所要時間に代えて、先に説明した余剰時間を用いても良い。また、所要時間や余剰時間にも重み係数を乗じるようにしてもよい。
【００６０】
図６はコンビニエンスストアＥを待合場所とした場合の経由経路を示す説明図である。図５の場合と同様の手順によって経由経路「Ｓ→Ａ→Ｅ→Ｆ→Ｂ→Ｃ」が得られる。この経由経路の所要時間は３８分であり、余裕時間は２２分となる。コンビニエンスストアの待合高適度は「２」と設定されているから、評価値は４９と求められる。
【００６１】
図７は喫茶店Ｈを待合場所とした場合の経由経路を示す説明図である。図５の場合と同様の手順によって経由経路「Ｓ→Ａ→Ｈ→Ｂ→Ｃ」が得られる。この経由経路の所要時間は４８分であり、余裕時間は１２分となる。喫茶店Ｈの待合高適度は「４」と設定されているから、評価値は５１と求められる。
【００６２】
図８は規制ノードＣを待合場所とした場合の経由経路を示す説明図である。図５の場合と同様の手順によって経由経路「Ｓ→Ａ→Ｂ→Ｃ」が得られる。この経由経路の所要時間は３０分であり、余裕時間は３０分となる。規制ノードＣの待合高適度は「１」と設定されているから、評価値は６０と求められる。
【００６３】
図５〜８で示した結果を比較すると、評価値は次の通りとなる。
（図５のケース）待合ノード＝Ｓ  …  評価値＝６０；
（図６のケース）待合ノード＝Ｅ  …  評価値＝４９；
（図７のケース）待合ノード＝Ｈ  …  評価値＝５１；
（図８のケース）待合ノード＝Ｃ  …  評価値＝６０；
従って、これらの中では、図６のケース、即ちコンビニエンスストアＥを待合場所とする経路が推奨経路となる。図７のケース、即ち喫茶店Ｈを待合場所とする場合が推奨経路とならないのは、待合好適度は大きいため、待ち時間の過ごしやすさという点では優れるものの、場所が遠く、喫茶店Ｈを経由する際の所要時間が増大することが原因と言える。当然、評価値の演算方法次第で、これらの結果は変動する。先に述べた通り、評価値の演算方法は、ユーザの要望に沿った実用性、利便性の高い待合場所が得られるよう、任意に設定すればよい。
【００６４】
Ｃ２．経路探索処理：
図９は経路探索処理のフローチャートである。図３〜８で具体的に示した経路探索を実現するための処理例である。この処理は、サーバ２００の経路探索部２３０（図１参照）が実行する処理であり、ハードウェア的にはサーバ２００のＣＰＵが実行する処理である。
【００６５】
ＣＰＵは最初に、端末１００からユーザＩＤ、出発地、目的地、出発時刻の指定を入力する（ステップＳ１０）。この他、経路探索に関するユーザの要望事項を入力するようにしてもよい。例えば、経路に対して、階段や坂道を回避するという移動負荷に関する要望や、ガードレールや街灯が整備されている通路を優先するというような安全性に関する要望を指定可能としてもよい。
【００６６】
次に、ＣＰＵは規制条件を考慮して経路探索を実施する（ステップＳ２１）。ダイクストラ法による具体的な処理方法は周知であるため、ここでは詳細な説明は省略し、図中に経路探索の主要な処理内容を示した。経路探索において、ＣＰＵはまず従前の処理で探索された経路候補の先端のノードから更に分岐して経路を延伸させる経路候補を設定する（ステップＳ２１）。次に、各ノードに至るまでのコストを算出して、そのコストおよび従前の経路を記録したラベルを設定していく。例えば、各リンクの距離を移動速度、即ちユーザの通常速度で割ることで所要時間を算出し、その所要時間をコストとして利用するという方法を採ることができる。コストは、この方法に限らず図３で説明したように種々の値を用いることができる。本実施例では、上述の処理で得られた所要時間を用いて各ノードへの到達時刻を予測する（ステップＳ２２）。
【００６７】
また、経路探索過程で、規制ノードが存在する場合には、時刻表ＤＢを読み出し、上述の到達時刻に基づいて規制ノードでの待ち時間を算出し、この規制が関連するリンクのコストへ反映させる（ステップＳ２３）。図中にこの処理の例を示した。図示するように、リンクＣＤに規制条件が付されており、ノードＣに規制が解除される３０分前に到達する場合には、待ち時間３０分がリンクＣＤに反映される。ノードＣから上述の規制とは無関係の迂回路が存在する場合には、この迂回路に対応するリンクには待ち時間分のコストは反映されない。所要時間をコストとして用いている場合には、待ち時間をリンクＣＤのコストに加えればよい。距離をコストとして用いている場合には、待ち時間に移動速度を乗じるなどの方法で距離に換算して加えることで、コストを反映させることができる。待ち時間の反映方法は、このようにコストの設定方法に応じて定められる。
【００６８】
ＣＰＵは以上で得られたコストを用いて最小コストとなる経路を求める（ステップＳ２４）。この処理を目的地に到達するまで繰り返し実行することで、図３に示したように、待合ノードの経由を考慮しない経路（以下、本来経路と称する）が得られる。
【００６９】
こうして本来経路が得られると、ＣＰＵは規制ノードでの待ち時間を過ごす待合場所を経由する経由経路を設定するための処理、経由経路設定処理を実行する（ステップＳ１００）。この処理は、先に図４〜８で示した処理である。具体的な処理のフローチャートは後で示す。この処理によって、種々の待合場所を経由する経路のうち、いずれか一つの待合場所を経由する経由経路が選択される。
【００７０】
ＣＰＵは、次に、規制ノードを通過しない迂回経路を求め、この迂回経路と選択された経由経路のコストを比較し、いずれか小さい方を案内対象として選択する（ステップＳ２００）。例えば、経由経路を採り本来経路よりも移動距離が過剰に長くなる場合などには、経由経路よりも迂回経路の方が好適と判断される逆転現象が生じる可能性もある。ただし、経路の所要時間をコストとして用いる場合には、かかる逆転現象は生じ得ない。経由経路を採る場合でも、規制ノードに到達する時刻は本来経路と一致するからである。ステップＳ２００は任意の処理であり、所要時間をコストとして用いる場合も含め、適宜、省略しても差し支えない。
【００７１】
Ｃ３．経由経路設定処理：
図１０は経由経路設定処理のフローチャートである。先に図４〜８で示した処理例を実現するための処理であり、図９のステップＳ１００に相当する処理である。
【００７２】
この処理が開始されると、ＣＰＵは規制ノード周辺の待合場所を抽出する（ステップＳ１０２）。この抽出は、先に図４で説明した手順で実行することができる。この抽出時には、予め地図ＤＢ２５０に設定されている待合好適度とともに、またはこの待合好適度に代えて、ユーザが設定した待合好適度を参照するようにしてもよい。こうすることで、先に図２で説明したように、ユーザが「銀行」に対して待合好適度および待合許容時間を設定している場合には、銀行を経由する経由経路を求めることが可能となる。この結果、空き時間ができたら銀行で所用を済ませたいと考えているユーザに対して、要望に沿った効率的な経路を提示することが可能となる。
【００７３】
次に、ＣＰＵは待合場所の選択モードに応じて、待合場所および経由経路を設定するための処理を実行する（ステップＳ１０４）。本実施例では、手動と自動の二つの選択モードを設けた。選択モードの指定は、ステップＳ１０４を実行する時点で、ユーザに問い合わせるようにしてもよいし、ユーザＤＢ２５４（図１参照）に予め登録しておくようにしてもよい。
【００７４】
自動選択モードが選択される場合には、ＣＰＵは、抽出されている各待合場所に対して、経由経路を探索し、所要時間、余裕時間を求め（ステップＳ１１２）、経由経路の評価値を算出する（ステップＳ１１４）。これらの処理は、図５〜８で説明した処理に相当する。
【００７５】
ＣＰＵは、こうして得られた評価値に基づき評価値が最小となるという第１の条件に基づき、待合場所および経由経路を選択し（ステップＳ１１６）、経由経路設定処理を終了する。この選択時には、更に余裕時間が待合許容時間内という第２の条件を付しても良い。例えば、図５〜８の例で、喫茶店Ｈは余裕時間１２分と求められている。喫茶店Ｈについて、仮に待合許容時間の下限値が１５分と設定されているとすれば、この余裕時間は待合許容時間の下限値を下回っていることになる。従って、第２の条件を考慮すると、喫茶店Ｈは評価値を考慮するまでなく、待合場所から除外されることになる。第２の条件を考慮することにより、待合場所で過度に長時間待たされたり、過度にあわてたりする必要が生じる事態を抑制できる。
【００７６】
手動選択モードが選択される場合には（ステップＳ１０４）、ＣＰＵは、待合場所を端末１００の画面上に地図とともに表示し、いずれかの待合場所を選択するユーザの指示を入力する（ステップＳ１２２）。この処理においても、自動選択モードの場合と同様、ユーザが設定した待合好適度を考慮して待合場所を提示するようにしてもよい。地図上の待合場所をクリッカブルにしておき、ユーザがポインティングデバイスでいずれかの待合場所をクリックすることで選択する方法を採ることができる。待合場所に番号を付し、キーボードでこの番号を指定するようにしてもよい。
【００７７】
次に、ＣＰＵは選択された待合場所を経由する経由経路を探索し、その所要時間、余裕時間を求め、ユーザが経由経路の適否を判断するための目安となる情報として、端末１００の画面上に提示する（ステップＳ１２４）。図中に画面例ＤＩＳＰ１を示した。一例として、図示するように、経由すべき待合場所の付近にウィンドウを設け、所要時間、余裕時間を表示する態様を採ることができる。ユーザが「待合場所選択」ボタンを押すと（ステップＳ１２６）、ＣＰＵは再び待合場所の表示処理を実行する（ステップＳ１２２）。ユーザが「ＯＫ」ボタンを押すと（ステップＳ１２６）、ＣＰＵは経由経路設定処理を終了する。手動選択モードでは、最適か否かの評価は行わず、ユーザが選択した経由経路を選択することになる。
【００７８】
Ｃ４．変形例：
図１０の例では、自動選択モードで経路を選択する際に、「評価値最小となる経由経路を選択」という第１の条件のみ、または第１の条件および「余裕時間が待合許容時間内」という第２の条件の双方を画一的に使用する場合を例示した。これに対し以下に示すように、規制条件の種類に応じて経路を選択するための条件を使い分けるようにしてもよい。
【００７９】
規制条件には、例えば、交通機関の発車時刻のように、通行するためには特定の時刻に規制ノードに到達していることが要求されるものがある。以下、かかる規制条件を時刻規制条件と呼ぶ。別の規制条件として、例えば、所定の時間帯のみ通行止めされる規制のように、通行するためには特定の時間帯に規制ノードに到達していれば足りるものがある。以下、かかる規制条件を時間規制と呼ぶ。規制ノードに到達する時刻に対する要求という点では、時刻規制の方が時間規制よりも厳しいと言える。
【００８０】
経由経路設定処理では、時刻規制と時間規制の差違を考慮し、両者でステップＳ１１６における選択の基準を変えても良い。例えば、規制ノードに時刻規制が付されている場合には、ステップＳ１１６において規制ノードに近いことを重視する選択条件とすることができる。規制ノードに近い待合場所の方が、規制ノードへの到達時刻に対する要求を満足しやすいからである。上述の条件としては、例えば、ステップＳ１１６に示した条件に加え、規制ノードからの所要時間、道のり、直線距離のいずれかを制限する条件を考慮する方法が挙げられる。または、評価値を算出する際に、所要時間を、待合場所に至るまでの所要時間、待合場所から規制ノードに至るまでの所要時間に分け、後者に１以上の重み値を乗じるようにしてもよい。
【００８１】
Ｄ．経路案内：
図１１は経路案内処理のフローチャートである。図９で説明した経路探索処理の結果をユーザに提示するための案内データを生成し、端末１００に送信する処理である。経路案内は、端末１００の画面表示や音声出力などで行うことができる。経路案内処理は、サーバ２００の経路案内部２４０が実行する処理であり、ハードウェア的にはサーバ２００のＣＰＵが実行する処理である。
【００８２】
この処理では、ＣＰＵは、経路案内データを読込む（ステップＳ２００）。経路探索処理では案内対象となる経路を一つに絞らずに、ステップＳ２００の時点で経路案内データを複数読み込み、その一覧をユーザに提示して、案内対象となる経路をユーザに選択させてもよい。
【００８３】
経路案内データが読み込まれると、ＣＰＵは端末１００から現在位置を入力し（ステップＳ２０２）、経路案内用の画面を表示する。まず、ＣＰＵは現在位置と待合場所との位置関係によって待合中か否かを判断し（ステップＳ２０４）、待合中と判断される場合には出発時刻報知処理を行う（ステップＳ２０６）。この処理は、規制条件に基づいて設定された予定時刻に規制ノードに到着するために、待合場所を出発すべき時刻をユーザに知らせる処理である。出発時刻は、予定時刻よりも、待合場所から規制ノードまでの所要時間だけ遡った時刻、または更に若干の余裕を見込んだ時刻とすることができる。出発時刻に至る前の時点では、ＣＰＵは、出発予定時刻を画面上に表示する。現在時刻が出発時刻になると、ＣＰＵはユーザに音声や画面表示で、出発すべき旨を報知する。待合中でない場合には（ステップＳ２０４）、出発時刻報知処理はスキップされる。
【００８４】
次に、ＣＰＵは経路途中に規制ノードがあるか否かを判断する（ステップＳ２０８）。規制ノードがある場合には、規制条件による制約を回避して通行するための残時間を表示する（ステップＳ２１０）。残時間の表示は、規制ノードに向かう際にユーザが移動速度を調整する際の目安として行うものである。残時間の表示は、待合場所を出発してから規制ノードに至るまでの間でのみ行うようにしてもよい。規制ノードがない場合には、この処理はスキップされる。
【００８５】
ＣＰＵは以上で設定された画面とともに、地図上に経路および現在位置を表示して、経路案内を行う（ステップＳ２１２）。ＣＰＵは以上の処理を目的地に到達するまで繰り返し実行する（ステップＳ２１４）。
【００８６】
図１２は経路案内の表示画面を例示する説明図である。案内画面ＤＩＳＰ２は端末１００のディスプレイ上に表示される。図中の黒丸が現在位置ＰＰである。案内画面ＤＩＳＰ２では、図示するように現在位置ＰＰを含む地図が表示され、そこに経路Ｒ１〜Ｒ３が表示される。本実施例では、経由経路、規制条件が付されている箇所、およびその他の経路で表示パターンを変化させるものとした。図中の経路Ｒ１は、クロスハッチにより、経由経路であることを表している。この表示により、ユーザは案内されている経路が経由経路であることを容易に認識できるため、本来の目的地と離れた方向に案内が行われている場合でも、安心して案内に従うことができる。
【００８７】
経由経路Ｒ２は、ハッチングによって、時刻によって通行止めになるなどの規制条件が付されている箇所であることを表している。この表示により、ユーザは経由経路が要求される理由を容易に把握することができる。矢印で示した経路Ｒ３は、通常速度での移動で足り、規制条件も付されていないことを表している。経路Ｒ１〜Ｒ３の表示態様は、ここに例示したものに限られず、任意に設定可能である。これらの表示パターンの使い分けの少なくとも一部を省略してもよいし、更に詳細な使い分けを行うようにしてもよい。
【００８８】
図中の例では、領域Ａは駅ＳＴＡの構内であり、２０：００〜６：００の時間帯で通行止めになるという規制条件が付されている。経由経路Ｒ１が要求されるのは、この規制条件が解除されるのを待って駅構内を通行するためである。経由経路Ｒ１上には、待合場所となるコンビニエンスストアが表示される。この待合場所をユーザがクリックすると、ポップアップウィンドウＷ４が表れ、待合場所での余裕時間と、待合場所を出発すべき出発時刻が表示される。ポップアップウィンドウＷ４は、ユーザが待合場所にいる場合には、出発時刻を報知するために（図１１のステップＳ２０６参照）ユーザの操作を行うまでなく表示させるようにしてもよい。
【００８９】
本実施例では、更に領域Ａのように規制条件が付されている箇所をクリッカブルとし、薄いハッチングを付すなど、通常の建造物とは異なる表示態様で表示させるものとした。ユーザが領域Ａをクリックすると、ポップアップウィンドウＷ２が表示され、図示するように規制条件が表示される。駅ＳＴＡについても同様に、ポップアップウィンドウＷ３を表示し、図示するように電車の時刻表を規制条件として表示可能としてもよい。ユーザはこれらの情報に基づき、待合場所での余裕時間や出発時刻の根拠を理解することができ、状況に応じて自身の判断で出発時刻を調整等することが可能となる。
【００９０】
本実施例では、規制条件が付された領域Ａに向かう過程では、サブウィンドウＷ１も表示するものとした。このサブウィンドウＷ１では、規制条件による制約を回避するために許される残時間を表示する（図１１のステップＳ２１０参照）。図の例では、６：００に領域Ａに到達すればよく、サブウィンドウＷ１の表示によれば、残り時間が４分２０秒あることが分かる。領域Ａのように通行止めが解除される場合には、残り時間４分２０秒以内に領域Ａに到達しても無用な待ち時間が生じるに過ぎない。この場合、残り時間は、ユーザに過度に急いでも無意味であることを表す情報となる。サブウィンドウＷ１では、亀のマークを表示させることによって、このような残り時間、即ちこの時間よりも早く到着しても有意義とは言えない時間が表示されていることを示している。
【００９１】
一方、ユーザが駅ＳＴＡに向かっている場合には、発車時刻に間に合うように駅ＳＴＡに到達する必要がある。かかる場合には、残り時間は、ユーザが駅ＳＴＡに到達するまでの所要時間の上限値を表す情報となる。かかる場合には、サブウィンドウＷ１に代えて、サブウィンドウＷ１ａに示すように、ハートマークを表示させ、ユーザに残り時間が限られていることを認識させるようにしてもよい。これらサブウィンドウＷ１、Ｗ１ａの表示によって、ユーザは自己の移動速度を適宜調整しながら、過度な負荷をかけずに移動することが可能となる。
【００９２】
サーバ２００は、ユーザの現在位置の履歴から移動速度を変化し、現在の移動速度を維持した場合の規制ノードへの到達時刻を予測することができる。サブウィンドウＷ１ａを表示する際には、この予測に基づき、ユーザに移動速度を速めたり、ゆっくりさせたりする指示を与えるようにしてもよい。例えば、ハートマークの点滅間隔を縮めることによりペースアップを指示し、点滅間隔をのばすことによりペースダウンを指示する方法を採ることができる。
【００９３】
経路Ｒ２は規制条件が付された箇所であることを表してはいるが、所定時刻までの通過が要求されている訳ではない。また、経路Ｒ３も通常速度での移動で足りる。従って、現在位置ＰＰが経路Ｒ２、Ｒ３上にある時には、サブウィンドウＷ１、Ｗ１ａは非表示となる。このように、規制条件が付された領域に向かう場合にのみサブウィンドウＷ１、Ｗ１ａを表示することによって、ユーザの注意をより確実に喚起することができる利点がある。
【００９４】
以上で説明した本実施例の経路案内システムによれば、規制条件によって待ち時間が生じた場合に、待合場所およびその待合場所を経由する経由経路を案内することができ、実用性、利便性に優れた経路案内を実現することができる。また、待ち時間を過ごす際の快適さと、経由経路の所要時間または距離の増加分とを考慮することにより、規制ノードから比較的近い範囲で快適な待合場所を探索することができる。
【００９５】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。本実施例は、歩行者用の経路案内システムに限らず、車両用の経路案内システムに適用することも可能である。また、本実施例では、サーバ２００と端末１００からなるシステムを例示したが、サーバ２００の機能を端末１００に組み込み、スタンドアロンの装置として構成することも可能である。
【図面の簡単な説明】
【００９６】
【図１】実施例としての経路案内システムの構成を示す説明図である。
【図２】地図ＤＢ２５０および時刻表ＤＢ２５２のデータ構造を示す説明図である。
【図３】経路探索処理例を示す説明図である。
【図４】待合場所の抽出処理例を示す説明図である。
【図５】出発地Ｓを待合場所とした場合の経由経路を示す説明図である。
【図６】コンビニエンスストアＥを待合場所とした場合の経由経路を示す説明図である。
【図７】喫茶店Ｈを待合場所とした場合の経由経路を示す説明図である。
【図８】目的地Ｇを待合場所とした場合の経由経路を示す説明図である。
【図９】経路探索処理のフローチャートである。
【図１０】経由経路設定処理のフローチャートである。
【図１１】経路案内処理のフローチャートである。
【図１２】経路案内の表示画面を例示する説明図である。
【符号の説明】
【００９７】
１００…端末
１１０…主制御部
１２０…通信部
１３０…コマンド入力部
１４０…ＧＰＳ
１５０…表示制御部
２００…サーバ
２２０…通信部
２３０…経路探索部
２４０…経路案内部
２５０…地図ＤＢ
２５０Ｌ…リンクデータ
２５０Ｎ…ノードデータ
２５２…時刻表ＤＢ
２５４…ユーザＤＢ
【図９】
2007093229.tif 000003
【図１】
2007093229.tif 000004
【図２】
2007093229.tif 000005
【図３】
2007093229.tif 000006
【図４】
2007093229.tif 000007
【図５】
2007093229.tif 000008
【図６】
2007093229.tif 000009
【図７】
2007093229.tif 000010
【図８】
2007093229.tif 000011
【図１０】
2007093229.tif 000012
【図１１】
2007093229.tif 000013
【図１２】
2007093229.tif 000014