経由地の指定を伴う経路探索
【課題】 経由地の指定を伴う経路探索において、経由地で中断のない連続的な経路を得る。
【解決手段】 経路探索装置は、経路探索に使用する地点として、出発地ＳＴ、経由地Ｖ１、目的地ＤＳＴの指定を入力する。リンクＬ１〜Ｌ７、およびノードＮ１〜Ｎ６上にない経由地Ｖ１については、リンク上に経路探索上の代替地点となる引込点Ｐ１１，Ｐ１２を設定する。かかる状態で出発地ＳＴ〜経由地Ｖ１、経由地Ｖ１〜目的地ＤＳＴという区間に分けて経路探索を実行する。この際、経路探索に使用される引込点は、引込点への進入時、引込点からの退出時の双方で経路探索が成功する点を用いる。こうすることにより経由地Ｖ１も含めた全経路にわたって移動可能であることが保証された連続的な経路Ｒ１、Ｒ２を得ることができる。
【解決手段】 経路探索装置は、経路探索に使用する地点として、出発地ＳＴ、経由地Ｖ１、目的地ＤＳＴの指定を入力する。リンクＬ１〜Ｌ７、およびノードＮ１〜Ｎ６上にない経由地Ｖ１については、リンク上に経路探索上の代替地点となる引込点Ｐ１１，Ｐ１２を設定する。かかる状態で出発地ＳＴ〜経由地Ｖ１、経由地Ｖ１〜目的地ＤＳＴという区間に分けて経路探索を実行する。この際、経路探索に使用される引込点は、引込点への進入時、引込点からの退出時の双方で経路探索が成功する点を用いる。こうすることにより経由地Ｖ１も含めた全経路にわたって移動可能であることが保証された連続的な経路Ｒ１、Ｒ２を得ることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地、目的地、および経由地の指定を伴う経路探索に関する。
【背景技術】
【０００２】
電子地図データを利用した経路探索技術が普及している。経路探索には、出発地、目的地の他、途中で通過すべき経由地を指定可能な技術も提案されている（例えば、特許文献１記載の技術）。一般には、出発地を探索開始点、経由地を探索終了点として第１段階の経路探索を行い、次に、経由地を探索開始点、目的地を探索終了点とする第２段階の経路探索を行って、全体として経由地を通過する経路を求める方法が採られる。経由地が複数存在する場合も、同様にして、ある経由地を探索開始点、その直後に通過すべき経由地を探索終了点とする経路探索を実行することで、経由地で分けられる区間ごとに経路を求める方法が採られる。
【０００３】
【特許文献１】特開平１０−１７０２９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、従来技術では、経由地を通過する経路の連続性が確保できない場合が生じる可能性があった。例えば、図３に示す道路について経路探索を行う場合を考える。道路は、それぞれノードＮ１〜Ｎ６、およびリンクＬ１〜Ｌ７によって表されている。リンクＬ４には、一方通行Ｔｒ１による通行規制が設定されている。
【０００５】
この状態で、ノードＮ１を出発地ＳＴ、ノードＮ５を目的地ＤＳＴとし、経由地Ｖ１を経由する経路を探索する場合を考える。経由地Ｖ１はノードおよびリンク上の点ではないため、経路探索時には、経由地Ｖ１の近傍のリンク上に「引込点」と呼ぶ経路探索上の代替地点を設定する必要がある。図の例では、リンクＬ４上の引込点Ｐ１１、リンクＬ５上の引込点Ｐ１２が設定される。引込点Ｐ１１の方が、引込点Ｐ１２よりも、経由地Ｖ１にとって最寄りである。
【０００６】
出発地ＳＴから経由地Ｖ１までの経路探索では、リンクＬ４に一方通行Ｔｒ１が設定されているため、引込点Ｐ１２を探索終了点とする経路Ｒ１が得られる。経由地Ｖ１から目的地ＤＳＴまでの経路探索では、経由地Ｖ１の最寄りの引込点Ｐ１１を探索開始点とする経路Ｒ３が得られる。この結果、経由地Ｖ１を経由する全体経路は、経路Ｒ１、Ｒ３となり、両者間が途切れた経路となってしまう。引込点Ｐ１２、Ｐ１１を連結する経路Ｒ４が存在しない場合には、得られた経路にそって移動することが不能となることもある。
【０００７】
本発明は、かかる課題を解決し、経由地の指定を伴う経路探索において、現実に移動可能な経路の探索を実現することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の経路探索装置は、リンク、ノード、及びこのリンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照して経路探索を行う。通行規制情報とは、一方通行、右折または左折禁止など、リンクまたはノードにおける進行方向を制限する情報を言う。経路探索装置は、経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する。また、リンクまたはノード上にない経由地については、経路探索用に、いずれかのリンクまたはノード上に経由地の代わりとなる引込点を複数箇所設定する。そして、道路ネットワークデータに基づき、出発地、いずれかの引込点、目的地を通過する経路を探索する。この経路探索は、経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件下で実行する。こうすることによって、経由地前後での経路の連続性が確保され、現実に移動可能な経路を得ることが可能となる。
【０００９】
上述の条件を満たす引込点は、経路探索に先立って、または経路探索と並行して、進入探索および退出探索の双方による評価を行うことで特定する。進入探索および退出探索の一方または双方が不成立の引込点は経路探索に使用することができないものとして評価され、他の引込点を候補として、再度、進入探索および退出探索が実行される。
【００１０】
ここで、探索開始点、探索終了点とは、経路探索条件として指定されるスタート地点、ゴール地点を意味しており、経路探索のアルゴリズムを規定するものではない。本発明では、例えば、探索開始点、探索終了点の双方から並行して経路を探索するアルゴリズムを適用しても構わない。
【００１１】
本発明では、経由地について進入時と退出時で異なる引込点を用いることを許容してもよい。本発明においては、各引込点は進入、退出共に可能であるため、異なる引込点を用いた場合でも、両者間で移動不能となることは回避される。また、同じ経由地に対して設けられた引込点であるため、案内された経路が一見して途切れている場合でも、引込点間の移動方法は、現地で比較的容易に見いだすことが可能であり、実用上の支障は生じない。
【００１２】
本発明では、経由地のそれぞれに対して、いずれか一カ所の引込点を使用するようにしてもよい。換言すれば、引込点が設定された経由地については、経由地と引込点が１対１の関係となるように引込点を使用して経路探索を行ってもよい。こうすることにより、外見上も連続した経路が案内されることになる。
【００１３】
経路探索に利用する引込点は、経由地に対して設定された複数の引込点から、ランダムに候補を挙げるようにしてもよいし、一定の選択規則に基づいて候補を挙げるようにしてもよい。後者の場合、例えば、経由地からの距離が短い位置にある引込点を優先的に候補にするという選択規則を適用してもよい。こうすることにより、経由地付近を経由する経路が得られるため、利便性が向上する。
【００１４】
経由地に対して複数の引込点を使用する場合、出発地または目的地に近い引込点を優先的に使用しても良い。こうすれば、経由地への進入、退出に適した経路を案内することができる。経由地から遠く離れた不便な引込点が用いられるのを避けるため、この選択は、経由地から所定距離範囲内の引込点の中から行うようにしてもよい。
【００１５】
他の選択規則として、例えば、通行規制情報が関連づけられていないリンクまたはノード上の引込点を優先的に候補にするという規則を用いても良い。かかる引込点は、出発地または直前の引込点から当該引込点に向かう経路、および当該引込点から次ぎの引込点または目的地に向かう経路の双方が支障なく得られる可能性が高い。従って、かかる引込点を優先的に候補にすることにより、経路探索の所要時間を短縮することが可能となる。
【００１６】
他の選択規則は、経由地からの距離、および通行規制情報の関連付けの有無の双方に基づいて定まる優先度に基づいて設定してもよい。優先度は、例えば、距離に基づく評価値、通行規制情報に基づく評価値を個別に求め、両評価値の加重和など、両評価値を用いた一定の算出式に基づき任意に設定することができる。算出式に依らず、両者の値に対して優先度を与えるテーブルを予め用意するようにしてもよい。こうすることにより、経由地付近を通過する経路を比較的短時間で探索することが可能となる。
【００１７】
進入探索、退出探索は、種々の態様で行うことができる。例えば、経由地が複数指定されている場合、進入探索は、評価対象となる経由地を探索終了点とし、（１）その直前の経由地を探索開始点とする方法、（２）全体の出発地を探索開始点とする方法のいずれを用いても良い。進入探索は経由地から出発地または直前の経由地に向けて逆方向に進めてもよい。退出探索についても、評価対象となる経由地を探索開始点とし、（１）その直後の経由地を探索終了点とする方法、（２）全体の目的地を探索終了点とする方法のいずれを用いても良い。
【００１８】
更に、進入探索、退出探索の少なくとも一方は、以下に示す局所的探索としてもよい。進入探索についての局所的探索は、経由地を含む所定範囲で、逆方向に進行した場合に通行規制情報に適合する経路となるという条件、即ち通行規制情報の逆解釈で、経由地側から行う経路探索とすることができる。退出探索についての局所的探索は、経由地を含む所定範囲で、通行規制情報に即して経由地から行う経路探索とすることができる。局所的探索を利用することにより、進入探索、退出探索の所要時間、ひいては経路探索全体の所要時間を短縮できる利点がある。
【００１９】
例えば、進入探索における局所的探索としては、経由地から出発地等に向けて逆探索を実行し、経路の先端が経由地から所定範囲外に出た時点で、進入探索成功と判断する方法を採ることができる。この逆探索は、得られた経路を逆走した場合に通行規制に抵触しないよう、通行規制を解釈しながら行うことになる。所定範囲は、例えば、経由地からの直線距離、道のり、リンク数、ノード数などで規定することができる。所定範囲を広げれば、出発地等から引込点に至る経路が存在する確実性が向上する一方、進入探索に要する所用時間が増大する。所定範囲は、確実性と所要時間の両者のバランスを考慮して、任意に設定可能である。
【００２０】
退出探索における局所的探索としては、経由地から目的地等に向けて順探索を実行し、経路の先端が経由地から所定範囲外に出た時点で、退出探索成功と判断する方法を採ることができる。所定範囲は、進入探索と同様の基準に基づき、任意に設定可能である。
【００２１】
進入探索についての局所的探索は、別の態様として、出発地または直前に通過すべき経由地から経由地に至る経路上のいずれかの地点を探索開始点とする経路探索を行っても良い。退出探索についての局所的探索は、別の態様として、経由地から目的地または直後に通過すべき経由地に至る経路上のいずれかの地点を探索終了点とする経路探索を行っても良い。
【００２２】
進入探索、退出探索による評価は、各引込点について必ずしも双方を行う必要はない。例えば、通行規制情報のないリンクまたはノード上の引込点に対しては、進入探索および退出探索の少なくとも一方を省略しても構わない。かかる引込点については、これらの経路探索は成功する可能性が高いからである。この省略によって、進入探索、退出探索の成否の見極めに要する時間の短縮を図ることができる。
【００２３】
本発明において、経路探索は上述した方法以外に種々の態様で行うことができる。例えば、従来技術と同様の条件で経路探索を行った上で、経由地と引込点について、１対１の関係が維持されているか否かを評価するようにしてもよい。そして、かかる関係が維持されていない経由地についてのみ、候補の引込点を順次変えながら、連続的な経路が得られるまで経路探索を繰り返し実行するようにしてもよい。
【００２４】
本発明は、上述した種々の特徴を全て備えている必要はなく、その一部を適宜省略したり組み合わせたりしても構わない。本発明は、経路探索装置、コンピュータを利用した経路探索方法、かかる経路探索を実現するコンピュータプログラム、および該コンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体など種々の態様で構成可能である。経路探索装置として構成する場合、スタンドアロンで稼働する装置としてもよいし、端末とサーバとをネットワークで接続して構成してもよい。記録媒体としては、フレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００２５】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｃ．経路探索（第１実施例）：
Ｃ１．探索方法の概要：
Ｃ２．経路探索処理：
Ｄ１．変形例１：
Ｄ２．変形例２：
Ｄ３．変形例３：
Ｄ４．変形例４：
Ｅ．経路探索（第２実施例）：
Ｆ．経路探索（第３実施例）：
【００２６】
Ａ．システム構成：
図１は実施例としての経路案内システムの全体構成を示す説明図である。実施例の経路案内システムは、経路探索装置として機能するサーバ２００と、ユーザが利用する案内装置１００をネットワークＮＥＴで接続することで構成される。ネットワークＮＥＴとしては、例えば、携帯電話回線などを利用することができる。案内装置１００は、図示した例に限らず、サーバ２００に対して複数台接続することが可能である。
【００２７】
案内装置１００は、車載のナビゲーション装置や携帯電話などを利用することができる。図中に案内装置１００の機能ブロックを併せて示した。これらの機能ブロックは、案内装置１００に搭載されたマイクロコンピュータに所定のプログラムを実行させることでソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００２８】
各機能ブロックは、主制御部１１０の制御下で、それぞれ次に示す機能を実現する。通信部１２０は、ネットワークＮＥＴを介した通信を制御する。ＧＰＳ１４０は、全地球測位システム（Global Positioning System）を利用して、案内装置１００の現在位置の緯度、経度を検出する。コマンド入力部１３０は、スイッチ等に対するユーザ操作に基づいて、経路探索、経路案内に関するコマンドを入力する。ユーザは、経路探索用のコマンドを利用して、経路探索の出発地、経由地、目的地を指定することができる。出発地は、ＧＰＳ１４０で検出される現在位置を利用してもよい。これらの指定は、サーバ２００に送信される。表示制御部１５０は、案内装置１００のディスプレイに、経路探索用のメニュー、経路案内用の地図などを表示させる。
【００２９】
サーバ２００は、案内装置１００からのコマンドに基づいて経路探索を行い、結果を案内装置１００に提供する。かかる機能を実現するための機能ブロックを図中に示した。これらの機能ブロックは、サーバ２００のＣＰＵが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００３０】
地図ＤＢ２２０は、経路探索および経路案内に使用される電子地図データベースである。本実施例では、地図ＤＢ２２０には、道路ネットワークＤＢ２２２と、描画ＤＢ２２１が含まれる。道路ネットワークＤＢ２２２は、経路探索に利用されるデータベースであり、道路の接続状態をリンクやノードで表したデータ、通行規制情報、およびリンクの評価値であるコストなどを記録している。描画ＤＢ２２１は、経路案内時に、地図情報を表示するためのデータである。地図ＤＢ２２０には、これらのデータベースに加えて、経路探索の出発地、目的地の設定を支援するための検索ＤＢを設けても良い。ＤＢ管理部２１２は、経路探索時、経路案内時に、それぞれ必要なデータを地図ＤＢ２２０から読み出す機能を奏する。
【００３１】
通信部２０２は、ネットワークＮＥＴ経由での案内装置１００との通信を制御する。通信される情報には、出発地、目的地、経由地の指定その他の経路探索用のコマンド、経路探索結果が含まれる。地点入力部２０４は、通信部２０２経由で、出発地、目的地、経由地の指定結果を受け取り、それぞれを引込点管理テーブル２０８に記録する。引込点管理テーブル２０８は、このように経路探索で使用すべき種々の地点情報を管理するためのテーブルである。その構成については、後述する。
【００３２】
引込点設定部２１０は、出発地、目的地、経由地のうち、リンクおよびノードからずれている点について、引込点を設定する。引込点とは、出発地等の各地点の周辺のリンクおよびノード上に設定される代替地点を言う。引込点の設定方法は任意であるが、本実施例では、出発地等の周辺に存在する各リンクにおろした垂線の足を引込点として設定するものとした。引込点は出発地等の各地点につき、複数設定される場合がある。
【００３３】
経路探索部２０６は、ユーザから指定されたコマンドに基づき、引込点管理テーブル２０８および地図ＤＢ２２０を参照して、経路探索を行う。経路探索には、例えば、ダイクストラ法など周知の方法を利用可能である。得られた経路は、探索結果出力部２１４に受け渡される。探索結果出力部２１４は、経路探索の結果、および地図ＤＢ２２０を参照して、経路案内に必要な地図および案内情報を、案内装置１００に出力する。
【００３４】
Ｂ．データ構造（道路ネットワークＤＢおよび引込点管理テーブル）：
図２は道路ネットワークＤＢ２２２および引込点管理テーブル２０８のデータ構造を示す説明図である。図の中央に、道路に対応するリンク、ノードの例を示し、上方に道路ネットワークＤＢ２２２の構造例を示し、下方に引込点管理テーブル２０８の例を示した。
【００３５】
図の中央の例では、道路の接続状態はリンクＬ１〜Ｌ７、ノードＮ１〜Ｎ６で表現される。ノードは、リンク同士の接続点に相当する。この例では、リンクＬ１〜Ｌ７は直線状であるが、リンクの通過点座標を複数指定することにより、折れ線状のリンクを設定することも可能である。リンクＬ４には、一方通行Ｔｒ１という通行規制が設定されている。この通行規制は、矢印ａ１に沿う通行、即ち「ノードＮ２→Ｎ３→Ｎ６」という通行、および矢印ａ２に沿う通行、即ち「ノードＮ４→Ｎ３→Ｎ６」という通行が禁止されていることと同義である。
【００３６】
道路ネットワークＤＢ２２２は、ノードデータ２２２ａとリンクデータ２２２ｂを有している。ノードデータ２２２ａは、各ノードについて緯度、経度の位置情報、および通行規制情報を記録する。例えば、ノードＮ３については、「（緯度、経度）＝（Ｌａｔ３、Ｌｏｎ３）」という位置情報が記録され、通行規制情報には、通行不能な通過方法、この例では、上述した「ノードＮ２→Ｎ３→Ｎ６」および「ノードＮ４→Ｎ３→Ｎ６」という通過方法が記録されている。
【００３７】
リンクデータ２２２ｂは、各リンクについて、位置情報およびコストを記録する。位置情報は、始点および終点のノードを記録するものとした。これらのノード間に、リンクが通過する地点の座標値を複数指定可能としてもよい。コストは、経路探索の一手法であるダイクストラ法において用いられる各リンクの評価値である。リンクデータ２２２ｂには、更に、各リンクに接続するリンクを指定する情報を含めても良い。
【００３８】
引込点管理テーブル２０８は、経路探索で使用される各地点の情報を管理するためのテーブルである。出発地ＳＴ、経由地Ｖ１その他の経由地、目的地ＤＳＴの各地点は、通過すべき順番に配列される。各地点の位置は、ノードの符号または緯度、経度の座標値で記録される。図の例では、出発地ＳＴおよび目的地ＤＳＴの位置は、ノードの符号で記録され、経由地の位置は座標で記録されている。
【００３９】
出発地、経由地、目的地がリンクまたはノード上から外れている場合には、引込点が設定される。引込点管理テーブル２０８の引込点情報（以下、「引込点リスト」と呼ぶこともある）は、各地点に対応づけられた引込点の位置座標、および経路探索での使用可否を記録する。図の例では、経由地Ｖ１に対して、引込点Ｐ１１、Ｐ１２が設定されている。但し、図中では各引込点の緯度、経度は図示を省略した。可否とは、経路探索への使用可否を表す。「ＮＡ」は使用不可（Not Available）、「Ａ」は使用可（Available）を表している。使用可否は、経路探索の過程で付されるものであり、引込点の設定後の初期状態では、いずれの情報も付されていない「Ｎｕｌｌ」か、使用可「Ａ」に統一されている。
【００４０】
道路ネットワークＤＢ２２２および引込点管理テーブル２０８は、上述の情報が記録されていればよく、データ構造自体は図２の例示に限らず、種々の構造を適用可能である。
【００４１】
Ｃ．経路探索（第１実施例）：
Ｃ１．経路探索方法の概要：
図３は経路探索方法の概要を示す説明図である。先に図２で示した道路の接続状態を例にとって説明する。まず、かかる道路構成において、出発地ＳＴから経由地Ｖ１までの経路探索を行う場合を考える。このように経由地に向かう経路探索を、以下、進入探索と呼ぶものとする。経由地Ｖ１は、リンク上にないため、引込点Ｐ１１またはＰ１２のいずれかを探索終了点として経路探索することになる。引込点Ｐ１１は、リンクＬ４の一方通行規制Ｔｒ１により、経路が得られない。従って、出発地ＳＴから経由地Ｖ１までの探索結果としては、引込点Ｐ１２を探索終了点とする経路Ｒ１が得られる。
【００４２】
次に、経由地Ｖ１から目的地ＤＳＴまでの経路探索を実行する。このように経由地から次の地点に向かう経路探索を、以下、退出探索と呼ぶものとする。この退出探索を、進入探索と独立に実行すると、退出探索においては、進入探索で使用された引込点Ｐ１２と異なる引込点Ｐ１１から目的地ＤＳＴに至る経路Ｒ３が解として得られる可能性がある。本実施例では、かかる結果を回避するため、進入探索と同一の引込点Ｐ１２を用いて退出探索を実行することにより、経路Ｒ２を得る。この結果、全体としては、出発地ＳＴから経路Ｒ１で引込点Ｐ１２に向かい、その後、引込点Ｐ１２から経路Ｒ２で目的地ＤＳＴに向かうという連続した経路が得られる。
【００４３】
上述の通り、本実施例では、各経由地について、一カ所の引込点が使用されるという条件、換言すれば、経由地と引込点が１対１に対応するという条件下で、経路探索を実行する。以下、かかる経路探索を実現するためのアルゴリズムについて説明する。
【００４４】
Ｃ２．経路探索処理：
図４は経路探索処理のフローチャートである。サーバ２００の各機能ブロックが連係して実現する処理であり、ハードウェア的には、サーバ２００のＣＰＵが実行する処理である。
【００４５】
処理が開始されると、サーバ２００は、案内装置１００に対するユーザの操作に基づいて、出発地、目的地、経由地の指定を入力する（ステップＳ１０）。そして、これらの指定された地点を引込点管理テーブル２０８に登録し、リンクまたはノード上に存在しない地点については引込点を設定し、引込点リストを作成する（ステップＳ１１）。
【００４６】
次に、サーバ２００は、各経由地について、経路探索に使用する引込点を決定するための処理を実行する（ステップＳ２０）。まず、処理対象となる経由地（以下、「対象経由地」と称する）に関連づけられている引込点から一つを候補として選択する（ステップＳ３０）。この選択は、ランダムに選択する方法、経由地からの距離が近い順に選択する方法、通行規制情報が無いリンクまたはノード上に設定された引込点から順に選択する方法など、種々の方法によって行うことができる。本実施例では、距離が近い順に優先的に候補として選択する方法を採用した。こうして選択された引込点を、以下、「候補引込点」と称する。
【００４７】
次に、サーバ２００は、候補引込点について、進入探索を実行する（ステップＳ４０）。進入探索では、出発地を探索開始点として設定し、候補引込点を探索終了点として設定して、経路探索を実行する。経路探索に失敗した場合は（ステップＳ５０）、引込点管理テーブル２０８において、候補引込点の情報を使用不可「ＮＡ」に更新して（ステップＳ５３）、他の候補引込点について再度、処理を繰り返す（ステップＳ３０〜Ｓ５０）。
【００４８】
探索に成功した場合には（ステップＳ５０）、同じ候補引込点について退出探索を実行する（ステップＳ５１）。退出探索では、候補引込点を探索開始点として設定し、目的地を探索終了点として設定して、経路探索を実行する。経路探索に失敗した場合は（ステップＳ５０）、引込点管理テーブル２０８において、候補引込点の情報を使用不可「ＮＡ」に更新して（ステップＳ５３）、他の候補引込点について再度、進入探索から、処理を繰り返す。退出探索に成功すれば、その候補引込点を、経路探索に使用可能な点として確定し（ステップＳ５４）、引込点管理テーブル２０８において、この候補引込点の情報を使用可「Ａ」に変更する。
【００４９】
以上の処理を各経由地について実行することにより（ステップＳ６０）、経路探索に使用すべき引込点が決定される。サーバ２００は、こうして設定された引込点を用いて、経路探索を実行する（ステップＳ６２）。この経路探索は、出発地から１番目の経由地、１番目の経由地から２番目の経由地、…と区間に分けて目的地に至るまでの経路を区間ごとに探索する。
【００５０】
本実施例によれば、各経由地については、ステップＳ６０までの処理で設定された引込点を使用するため、必ず連続した経路、現実に移動可能な経路が得られることになり、経路探索装置の利便性が向上する。
【００５１】
Ｄ１．変形例１：
図５は変形例としての引込選択処理のフローチャートである。実施例（図４）におけるステップＳ３０に代わる処理である。変形例では、引込点と経由地との距離、および通行規制情報の有無の双方を考慮して、候補引込点を選択する処理を示す。
【００５２】
変形例の処理では、全引込点について、まず引込点と経由地との距離Ｄを算出し（ステップＳ３３）、この距離に基づき評価値Ｖｄを算出する（ステップＳ３４）。評価値は、高いほど、候補引込点としての優先度が高くなることを意味する。図中に、距離Ｄと評価値Ｖｄとの関係を例示した。両者の関係は任意に設定可能であり、例えば、直線Ｃ１のように設定すれば、距離Ｄが遠くなるにつれて線形的に評価値Ｖｄは低下し、一定距離以上の引込点については「評価値Ｖｄ＝０」となる。曲線Ｃ２のように設定すれば、経由地に非常に近い引込点の評価値Ｖｄが非常に大きくなる。曲線Ｃ３のように設定すれば、経由地付近ではほぼ一定の評価値Ｖｄとしつつ、その範囲から少し外れると急激に評価値Ｖｄが下がる。曲線Ｃ２、Ｃ３では、経由地付近の引込点が比較的選ばれやすい傾向が生じる。
【００５３】
次に、サーバ２００は、通行規制に基づく評価値Ｖｒを算出する（ステップＳ３５）。この例では、規制有りの場合には「評価値Ｖｒ＝０．５」、規制無しの場合には「評価値Ｖｒ＝１．０」と設定するものとした。両者の値は、任意に設定可能である。規制有りの場合に、評価値Ｖｒを０としても構わない。
【００５４】
サーバ２００は、こうして得られた評価値Ｖｄ、Ｖｒに基づき、次式（１）によって、候補引込点の評価値Ｖｖを算出する（ステップＳ３６）。
Ｖｖ＝ｋ１×Ｖｄ＋ｋ２×Ｖｒ；
ｋ１，ｋ２は重み係数（実数） …（１）
【００５５】
重み係数の値は任意に設定可能である。いずれか一方を値０としても構わない。例えば、ｋ１を値０とすれば、通行規制の有無のみで評価値Ｖｖが決まることになる。ｋ２を値０とすれば、逆に、経由地からの距離のみで評価値Ｖｖが決まることになる。
【００５６】
サーバ２００は、全引込点について、上述の方法で評価値Ｖｖを求め（ステップＳ３７）、その評価値Ｖｖが最大の引込点を選択する（ステップＳ３８）。変形例の方法によれば、経由地からの距離、通行規制の双方を考慮して、候補引込点を選択することが可能となる。
【００５７】
Ｄ２．変形例２： 図６は変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ４０に代わる処理のみを示した。実施例では、出発地ＳＴと候補引込点との間で進入探索を行ったのに対し、変形例では、引込点から出発地ＳＴに向けて経路探索を行うとともに、出発地ＳＴに至る経路が完全に求められる前の時点で進入探索の成否を判断する局所的探索を実行する。
【００５８】
この処理が開始されると、サーバ２００は探索終了点として引込点を設定する（ステップＳ４０ａ）。そして、探索終了点側から逆向きに探索を実行する（ステップＳ４０ｂ）。この探索はダイクストラ法などによって行うことができる。逆向きの探索なので、通行規制については得られた経路を逆走した場合に違反とならないように考慮する。この検索は、無秩序に経路を延伸する態様で行ってもよいが、出発地ＳＴの方向を重視し、探索終了点側から出発地ＳＴに向けて経路が延伸するよう行うことがより好ましい。
【００５９】
サーバ２００は、探索された経路の長さが所定長Ｔｈ以上となった場合には（ステップＳ４０ｃ）、探索成功と判定し（ステップＳ４０ｄ）、進入探索処理を終了する。本変形例では、経路長さをリンク数で評価するものとし、「Ｔｈ＝１０」とした。即ち経路のリンク数が１０本以上に延伸した時点で探索成功と判定するものとした。判断基準値Ｔｈは任意に設定可能である。また、ステップＳ４０ｃの判断は、種々の態様を採ることが可能であり、例えば、探索された経路末端と引込点との直線距離や、引込点から経路末端までの道のりと、所定長Ｔｈとの比較を行うようにしてもよい。
【００６０】
探索された経路の長さが所定長Ｔｈに至らない場合には（ステップＳ４０ｃ）、探索の中止条件が成立しているか否かを判断する（ステップＳ４０ｅ）。中止条件としては、例えば、所要時間が所定値を超えること、延伸可能な経路が存在しなくなることなどを用いることができる。探索の中止条件が成立した場合には、サーバ２００は探索失敗と判定し（ステップＳ４０ｆ）、進入探索処理を終了する。探索中止条件が成立するまでは、再び経路探索を実行する（ステップＳ４０ｂ）。変形例では、このように局所的探索を利用するため、進入探索の成否を短時間で判定でき、ひいては経路探索の所要時間を短縮することができる。
【００６１】
同様に、退出探索に局所的探索を適用してもよい。この場合には、図６のステップＳ４０ａにおいて、探索開始点を引込点、探索終了点を目的地と設定し、ステップＳ４０ｂにおいて、探索開始点から棚策終了点に向けて順探索を行うようにすればよい。局所的探索は、進入探索、退出探索の双方に適用してもよいし、いずれか一方にのみ適用してもよい。
【００６２】
Ｄ３．変形例３：
図７は局所的探索の変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ３０〜Ｓ５０に代わる処理のみを示した。実施例では、出発地ＳＴと候補引込点との間で進入探索を行ったのに対し、変形例では、出発地ＳＴよりも経由地に近い地点を利用して進入探索を実行する。
【００６３】
この処理では、サーバ２００は、候補引込点に対する経路探索が初回か否かを判定する（ステップＳ４１）。初回である場合には、実施例と同様、探索開始点として出発地ＳＴを用い、探索終了点として候補引込点を用いて進入探索を実行する（ステップＳ４２、Ｓ４４）。２回目以降の処理では、探索開始点として、経由地からＮ個手前のノードを用いて進入探索を実行する（ステップＳ４３、Ｓ４４）。
【００６４】
図の下方に、この処理の一例を示した。経由地Ｖ１について引込点Ｐ１１、Ｐ１２が設定されている場合を考える。候補としての優先度は、引込点Ｐ１１の方が引込点Ｐ１２よりも高いものとする。
【００６５】
かかる状態において、初回の処理では、探索開始点を出発地ＳＴ、探索終了点を候補引込点Ｐ１１として経路探索を行い、太い実線の経路Ｒ１を得る。この候補引込点Ｐ１１について、例えば、退出探索が不成功に終わると、次は、候補引込点Ｐ１２について進入探索を実行することになる。この場合は、ステップＳ４３に示した通り、経由地からＮ個手前のノードを探索開始点として設定する。図の例では、既に求まっている経路Ｒ１に沿って３個手前のノードＮ３を探索開始点として使用する場合を示した。進入探索は、ノードＮ３と候補引込点Ｐ１２の間の局所的探索となり、経路Ｒ２が得られる。このように局所的探索を利用することにより、探索の所用時間が短縮されるため、各候補引込点について、進入探索の成否を速やかに判断することができる。ここでは、「３個手前」の例を示したが、局所的探索における探索開始点は、候補引込点を変更した場合でも出発地ＳＴから共通して通過する経路範囲内で、任意に設定可能である。
【００６６】
図７では、進入探索に局所的探索を利用した場合を例示した。同様にして、退出探索にも局所的探索を適用可能である。この場合、探索開始点として候補引込点を用い、探索終了点として、例えば、候補引込点から目的地に向けてＮ個移動したノードを用いることができる。局所的探索は、進入探索および退出探索の双方に適用してもよいし、いずれか一方にのみ適用しても構わない。
【００６７】
Ｄ４．変形例４：
図８は他の変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ１１以降のみを示した。実施例では、候補引込点について無条件に進入探索を実行したが、この変形例では、条件に応じて省略する。即ち、候補引込点が設定されているリンクまたはノードに対して、通行規制が有るか否かを判断する（ステップＳ４０ｐ）。通行規制がない場合には、進入探索および退出探索共に成功する可能性が高いと判断し、これらの処理を省略して、引込点を確定する（ステップＳ５４）。通行規制が設定されている場合には、経路探索が失敗する可能性があるため、実施例（図４）と同様の処理により、進入探索、退出探索を検査する。
【００６８】
本変形例の処理によれば、一定条件下で進入探索、退出探索を省略することができるため、経路探索に使用する引込点を速やかに確定することができる利点がある。
【００６９】
Ｅ．経路探索（第２実施例）：
図９は第２実施例としての経路探索処理のフローチャートである。第１実施例（図４）では、各経由地について、経路探索に使用する引込点を確定した後、改めて経路探索を行う例を示した。これに対し、第２実施例では、経路探索と引込点の決定を同時並行して行う例を、適宜、図３の道路構成を参照しながら説明する。
【００７０】
この処理では、出発地を経由地［０］、途中の経由地を経由地［１］、［２］…［ｎ−１］、目的地を経由地［ｎ］（ｎは自然数）と表すものとする。処理が開始されると、サーバ２００はこれらの地点の指定を入力する（ステップＳ１００）。そして、第１実施例（図４）と同様に、引込点リストを作成する（ステップＳ１０２）。
【００７１】
次に、経路探索の処理を実行に使用する制御変数に値１を代入する初期化処理を行い（ステップＳ１０４）、以下の手順で経路探索を実行する。まず、経由地［ｉ−１］について引込点［ｉ−１］を確定する（ステップＳ１０６）。初めてこの処理を実行する時（ｉ＝１の時）には、経由地［０］、即ち出発地に関連づけられた引込点［０］を確定することになる。出発地がノード上にある時には、「引込点［０］＝出発地［０］」と扱う。
【００７２】
次に、サーバは、経由地［ｉ］の候補引込点［ｉ］を選択する（ステップＳ１０８）。図３の例に即して説明すれば、経由地［１］の候補引込点［１］として、引込点Ｐ１１，Ｐ１２のいずれか一方を選択することになる。選択には、第１実施例と同様、種々の方法を適用できる。ここでは、経由地Ｖ１の最寄りの引込点Ｐ１１を選択したものとする。サーバ２００は、こうして設定された２つの引込点を用いて進入探索を行う（ステップＳ１１０）。
【００７３】
この進入探索は、探索開始点として引込点［ｉ−１］を設定し、探索終了点として引込点［ｉ］を用いる。この探索は、実質的には、引込点［ｉ−１］についての退出探索とみることもできる。第１実施例（図４）が探索開始点として出発地を固定的に使用していたのに対し、第２実施例では、探索開始点も変動する点で相違する。即ち、第２実施例では、経由地で区切られた区間ごとに進入探索を実行するのである。「ｉ＝１」の時、図３の例では、引込点［０］に相当する出発地ＳＴと、引込点［１］に相当する引込点Ｐ１１との間で進入探索を行うことになる。
【００７４】
この経路探索が不成功の場合において（ステップＳ１１２）、経由地［ｉ］について全引込点［ｉ］の検討が未了の場合は（ステップＳ１３０）、実施例と同様、引込点管理テーブル２０８の内容を更新し（ステップＳ１３２）、次の候補引込点について同様の処理を実行する。
【００７５】
例えば、図３の例では、出発地ＳＴと引込点Ｐ１１の間の経路探索は不成功に終わるが、経由地Ｖ１についてはまだ他の引込点Ｐ１２が残っている。従って、引込点管理テーブル２０８において、引込点Ｐ１１に対しては使用不可「ＮＡ」と記録し、次に引込点［１］として引込点Ｐ１２を選択して（ステップＳ１０８）、進入探索を再試行する。
【００７６】
経路探索に成功した場合には（ステップＳ１１２）、経由地［ｉ］に到達できることを意味するから、制御変数ｉを値１だけインクリメントし（ステップＳ１２０）、「ｉ＞ｎ」、即ち目的地に到達していないと判断される場合には（ステップＳ１２２）、再度、上述の処理を実行する。
【００７７】
図３の例では、制御変数を値２にインクリメントした後の処理として、経由地［１］についての引込点［１］をＰ１２に確定し（ステップＳ１０６）、経由地［２］の引込点、即ち目的地ＤＳＴを選択して（ステップＳ１０８）、これらの間で進入探索を行うことになる（ステップＳ１１０）。これらの経路探索が成功すれば（ステップＳ１１２、Ｓ１２０、Ｓ１２２）、出発地ＳＴから目的地ＤＳＴに至る経路が得られることになる。
【００７８】
上述の処理において、経由地［ｉ］に関連づけられた全引込点について進入探索が不成功となる場合が生じ得る（ステップＳ１３０）。かかる場合に、第２実施例では、経由地［ｉ−１］における引込点［ｉ−１］の設定まで遡って処理を再試行する。まず、引込点管理テーブル２０８において、経由地［ｉ］に関連づけられた引込点に付されている使用不可「ＮＡ」の情報を全てリセットするとともに、経由地［ｉ−１］について確定した引込点［ｉ−１］に対して使用不可「ＮＡ」を設定する（ステップＳ１３４）。その後、制御変数を値１だけデクリメントして、経路探索（ステップＳ１０６以降）を再試行するのである。
【００７９】
図３において、「ｉ＝２」、即ち引込点Ｐ１２と目的地との間で進入探索を行う場合を考える（ステップＳ１１０）。この経路探索が不成功に終わったとすると、引込点管理テーブル２０８において、経由地［ｉ］（即ち目的地）に関連づけられた引込点［ｉ］の情報を全てリセットする（ステップＳ１３４）。また、経由地［ｉ−１］の引込点［ｉ−１］（即ち引込点Ｐ１２）の情報を使用不可「ＮＡ」に設定する（ステップＳ１３４）。その後、制御変数を「ｉ＝１」に設定し、再度経路探索を実行する。即ち、出発地ＳＴと経由地Ｖ１との間の経路探索を再試行するのである。図３の例では、経由地Ｖ１について２カ所の引込点Ｐ１１、Ｐ１２しか示されていないが、他の引込点があれば、この引込点について進入探索が行われることになる。
【００８０】
第２実施例の経路探索によれば、各経由地の引込点が決定した時点で、改めて経路探索を行うまでなく、全体の経路が得られるため、処理時間を短縮することができる利点がある。第２実施例においても、ステップＳ１０８における引込点の選択には、第１実施例と同様、引込点と経由地の距離、通行規制の有無などを考慮した選択規則を適用することができる。
【００８１】
Ｆ．経路探索（第３実施例）：
図１０は第３実施例としての経路探索処理のフローチャートである。第３実施例では、各経由地について、複数の引込点を併用することを許容する例を示す。
【００８２】
この処理が開始されると、サーバ２００は、第１実施例（図４）と同様、出発地、目的地、経由地を設定し（ステップＳ２００）、引込点リストを作成する（ステップＳ２０２）。そして、全引込点について、進入探索および退出探索の成否を評価する（ステップＳ２０４〜Ｓ２１６）。進入探索および退出探索の一方が失敗した場合には、引込点管理テーブルに、使用不可「ＮＡ」と記録される（ステップＳ２１４）。これらの処理については、第１実施例（図４）と同様であるため、詳細な説明を省略する。第１実施例では、各経由地について、進入探索および退出探索の双方が成功する引込点が見つかった時点で、次の経由地の処理に移行したのに対し、第３実施例では、全引込点について進入探索および退出探索の評価を行う。進入探索および退出探索には、第１実施例および変形例で示した種々の手法を適用可能である。
【００８３】
全引込点について処理が完了すると、サーバ２００は使用可能と評価された引込点、即ち、進入探索および退出探索の双方が成功した引込点から、各経由地について経路探索時に使用する引込点を確定し（ステップＳ２２０）、経路探索を実行する（ステップＳ２４０）。
【００８４】
図１１は引込点確定処理のフローチャートである。図１０のステップＳ２２０に相当する処理である。この処理では、サーバ２００は、全経由地について（ステップＳ２２２）、以下の処理を実行する。まず、サーバ２００は、引込点管理テーブルを参照し（ステップＳ２２４）、利用可能な引込点の数を調べる。かかる引込点が１個の場合には（ステップＳ２２６）、この引込点を経路探索に使用する点として確定し（ステップＳ２２８）、次の経由地の処理に移行する（ステップＳ２３４）。
【００８５】
利用可能な引込点が複数存在する場合には（ステップＳ２２６）、その経由地に対応づけられた利用可能な全引込点について、現在の経由地からの距離Ｄ、直前の経由地からの距離Ｄｐ、直後の経由地までの距離Ｄｎを算出する（ステップＳ２３０）。そして、「Ｄ＋Ｄｐ」が最小となる引込点を、その経由地に進入する際の引込点として確定し、 「Ｄ＋Ｄｎ」が最小となる引込点を、その経由地から退出する際の引込点として確定し（ステップＳ２３２）、次の経由地の処理に移行する（ステップＳ２３４）。進入時と退出時で、使用する引込点は一致しても構わないし、異なっても構わない。
【００８６】
図中に、進入時の引込点の確定方法を例示した。経由地Ｖ２２について２つの引込点Ｐ２１、Ｐ２２が利用可能であるとする。経由地Ｖ２２の直前の経由地はＶ２１、直後の経由地はＶ２３とする。図中の太線はリンクを表し、黒丸はノードを表している。引込点Ｐ２１について、経由地との距離はＤ２１、直前の経由地Ｖ２１との距離はＤｐ２１である。引込点Ｐ２２について、経由地との距離はＤ２２、直前の経由地Ｖ２１との距離はＤｐ２２である。この場合、「Ｄ２１＋Ｄｐ２１＜Ｄ２２＋Ｄｐ２２」となるため、経由地Ｖ２２への進入時には、引込点Ｐ２１が使用されることになる。
【００８７】
同様にして、経由地Ｖ２２の直後の経由地Ｖ２３と引込点Ｐ２１、Ｐ２２の距離、および距離Ｄ２１、Ｄ２２を用いて、各引込Ｐ２１、Ｐ２２を評価すれば、経由地Ｖ２２からの退出時には、引込点Ｐ２２が使用されることになる。
【００８８】
第３実施例では、利用可能な全引込点について上述の評価を行うものとしたが、利用可能な引込点のうち経由地から所定距離内に存在するものについてのみ、上述の評価を行うようにしてもよい。第３実施例では、引込点Ｐ２１、Ｐ２２の評価を経由地Ｖ２１、Ｖ２３との直線距離に基づいて行う例を示したが、これらの経由地から引込点に至る所要時間、リンクコスト、道のりなどを単独、または組み合わせて用いて引込点の評価を行っても良い。
【００８９】
以上で説明した第３実施例の処理によれば、各経由地について複数の引込点を用いて経路案内することが許容される。但し、従来技術と異なり、経路案内には、進入および退出の双方が可能な引込点のみが用いられる。かかる場合には、経由地への進入時と退出時とで、異なる引込点が使用されたとしても、引込点間を移動可能であることが概ね保証される。案内された経路が一見して途切れている場合でも、これらの引込点間の移動方法は、現地で比較的容易に見いだすことが可能であり、実用上の支障は生じない。第３実施例によれば、例えば、駐車場を経由する場合、進入時の入口と異なる出口から退出するように案内可能となり、移動距離が短い効率的な経路を案内することが可能となる。
【００９０】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。上述の実施例では、案内装置１００とサーバ２００からなるシステムを例示したが、本発明はスタンドアロンの装置として構成することも可能である。
【図面の簡単な説明】
【００９１】
【図１】実施例としての経路案内システムの全体構成を示す説明図である。
【図２】道路ネットワークＤＢ２２２および引込点管理テーブル２０８のデータ構造を示す説明図である。
【図３】経路探索方法の概要を示す説明図である。
【図４】経路探索処理のフローチャートである。
【図５】変形例としての引込選択処理のフローチャートである。
【図６】変形例としての引込選択処理のフローチャートである。
【図７】変形例としての経路探索処理のフローチャートである。
【図８】他の変形例としての経路探索処理のフローチャートである。
【図９】第２実施例としての経路探索処理のフローチャートである。
【図１０】第３実施例としての経路探索処理のフローチャートである。
【図１１】引込点確定処理のフローチャートである。
【符号の説明】
【００９２】
１００…案内装置
１１０…主制御部
１２０…通信部
１３０…コマンド入力部
１４０…ＧＰＳ
１５０…表示制御部
２００…サーバ
２０２…通信部
２０４…地点入力部
２０６…経路探索部
２０８…引込点管理テーブル
２１０…引込点設定部
２１２…ＤＢ管理部
２１４…探索結果出力部
２２０…地図ＤＢ
２２１…描画ＤＢ
２２２…道路ネットワークＤＢ
２２２ａ…ノードデータ
２２２ｂ…リンクデータ
【技術分野】
【０００１】
本発明は、出発地、目的地、および経由地の指定を伴う経路探索に関する。
【背景技術】
【０００２】
電子地図データを利用した経路探索技術が普及している。経路探索には、出発地、目的地の他、途中で通過すべき経由地を指定可能な技術も提案されている（例えば、特許文献１記載の技術）。一般には、出発地を探索開始点、経由地を探索終了点として第１段階の経路探索を行い、次に、経由地を探索開始点、目的地を探索終了点とする第２段階の経路探索を行って、全体として経由地を通過する経路を求める方法が採られる。経由地が複数存在する場合も、同様にして、ある経由地を探索開始点、その直後に通過すべき経由地を探索終了点とする経路探索を実行することで、経由地で分けられる区間ごとに経路を求める方法が採られる。
【０００３】
【特許文献１】特開平１０−１７０２９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、従来技術では、経由地を通過する経路の連続性が確保できない場合が生じる可能性があった。例えば、図３に示す道路について経路探索を行う場合を考える。道路は、それぞれノードＮ１〜Ｎ６、およびリンクＬ１〜Ｌ７によって表されている。リンクＬ４には、一方通行Ｔｒ１による通行規制が設定されている。
【０００５】
この状態で、ノードＮ１を出発地ＳＴ、ノードＮ５を目的地ＤＳＴとし、経由地Ｖ１を経由する経路を探索する場合を考える。経由地Ｖ１はノードおよびリンク上の点ではないため、経路探索時には、経由地Ｖ１の近傍のリンク上に「引込点」と呼ぶ経路探索上の代替地点を設定する必要がある。図の例では、リンクＬ４上の引込点Ｐ１１、リンクＬ５上の引込点Ｐ１２が設定される。引込点Ｐ１１の方が、引込点Ｐ１２よりも、経由地Ｖ１にとって最寄りである。
【０００６】
出発地ＳＴから経由地Ｖ１までの経路探索では、リンクＬ４に一方通行Ｔｒ１が設定されているため、引込点Ｐ１２を探索終了点とする経路Ｒ１が得られる。経由地Ｖ１から目的地ＤＳＴまでの経路探索では、経由地Ｖ１の最寄りの引込点Ｐ１１を探索開始点とする経路Ｒ３が得られる。この結果、経由地Ｖ１を経由する全体経路は、経路Ｒ１、Ｒ３となり、両者間が途切れた経路となってしまう。引込点Ｐ１２、Ｐ１１を連結する経路Ｒ４が存在しない場合には、得られた経路にそって移動することが不能となることもある。
【０００７】
本発明は、かかる課題を解決し、経由地の指定を伴う経路探索において、現実に移動可能な経路の探索を実現することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の経路探索装置は、リンク、ノード、及びこのリンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照して経路探索を行う。通行規制情報とは、一方通行、右折または左折禁止など、リンクまたはノードにおける進行方向を制限する情報を言う。経路探索装置は、経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する。また、リンクまたはノード上にない経由地については、経路探索用に、いずれかのリンクまたはノード上に経由地の代わりとなる引込点を複数箇所設定する。そして、道路ネットワークデータに基づき、出発地、いずれかの引込点、目的地を通過する経路を探索する。この経路探索は、経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件下で実行する。こうすることによって、経由地前後での経路の連続性が確保され、現実に移動可能な経路を得ることが可能となる。
【０００９】
上述の条件を満たす引込点は、経路探索に先立って、または経路探索と並行して、進入探索および退出探索の双方による評価を行うことで特定する。進入探索および退出探索の一方または双方が不成立の引込点は経路探索に使用することができないものとして評価され、他の引込点を候補として、再度、進入探索および退出探索が実行される。
【００１０】
ここで、探索開始点、探索終了点とは、経路探索条件として指定されるスタート地点、ゴール地点を意味しており、経路探索のアルゴリズムを規定するものではない。本発明では、例えば、探索開始点、探索終了点の双方から並行して経路を探索するアルゴリズムを適用しても構わない。
【００１１】
本発明では、経由地について進入時と退出時で異なる引込点を用いることを許容してもよい。本発明においては、各引込点は進入、退出共に可能であるため、異なる引込点を用いた場合でも、両者間で移動不能となることは回避される。また、同じ経由地に対して設けられた引込点であるため、案内された経路が一見して途切れている場合でも、引込点間の移動方法は、現地で比較的容易に見いだすことが可能であり、実用上の支障は生じない。
【００１２】
本発明では、経由地のそれぞれに対して、いずれか一カ所の引込点を使用するようにしてもよい。換言すれば、引込点が設定された経由地については、経由地と引込点が１対１の関係となるように引込点を使用して経路探索を行ってもよい。こうすることにより、外見上も連続した経路が案内されることになる。
【００１３】
経路探索に利用する引込点は、経由地に対して設定された複数の引込点から、ランダムに候補を挙げるようにしてもよいし、一定の選択規則に基づいて候補を挙げるようにしてもよい。後者の場合、例えば、経由地からの距離が短い位置にある引込点を優先的に候補にするという選択規則を適用してもよい。こうすることにより、経由地付近を経由する経路が得られるため、利便性が向上する。
【００１４】
経由地に対して複数の引込点を使用する場合、出発地または目的地に近い引込点を優先的に使用しても良い。こうすれば、経由地への進入、退出に適した経路を案内することができる。経由地から遠く離れた不便な引込点が用いられるのを避けるため、この選択は、経由地から所定距離範囲内の引込点の中から行うようにしてもよい。
【００１５】
他の選択規則として、例えば、通行規制情報が関連づけられていないリンクまたはノード上の引込点を優先的に候補にするという規則を用いても良い。かかる引込点は、出発地または直前の引込点から当該引込点に向かう経路、および当該引込点から次ぎの引込点または目的地に向かう経路の双方が支障なく得られる可能性が高い。従って、かかる引込点を優先的に候補にすることにより、経路探索の所要時間を短縮することが可能となる。
【００１６】
他の選択規則は、経由地からの距離、および通行規制情報の関連付けの有無の双方に基づいて定まる優先度に基づいて設定してもよい。優先度は、例えば、距離に基づく評価値、通行規制情報に基づく評価値を個別に求め、両評価値の加重和など、両評価値を用いた一定の算出式に基づき任意に設定することができる。算出式に依らず、両者の値に対して優先度を与えるテーブルを予め用意するようにしてもよい。こうすることにより、経由地付近を通過する経路を比較的短時間で探索することが可能となる。
【００１７】
進入探索、退出探索は、種々の態様で行うことができる。例えば、経由地が複数指定されている場合、進入探索は、評価対象となる経由地を探索終了点とし、（１）その直前の経由地を探索開始点とする方法、（２）全体の出発地を探索開始点とする方法のいずれを用いても良い。進入探索は経由地から出発地または直前の経由地に向けて逆方向に進めてもよい。退出探索についても、評価対象となる経由地を探索開始点とし、（１）その直後の経由地を探索終了点とする方法、（２）全体の目的地を探索終了点とする方法のいずれを用いても良い。
【００１８】
更に、進入探索、退出探索の少なくとも一方は、以下に示す局所的探索としてもよい。進入探索についての局所的探索は、経由地を含む所定範囲で、逆方向に進行した場合に通行規制情報に適合する経路となるという条件、即ち通行規制情報の逆解釈で、経由地側から行う経路探索とすることができる。退出探索についての局所的探索は、経由地を含む所定範囲で、通行規制情報に即して経由地から行う経路探索とすることができる。局所的探索を利用することにより、進入探索、退出探索の所要時間、ひいては経路探索全体の所要時間を短縮できる利点がある。
【００１９】
例えば、進入探索における局所的探索としては、経由地から出発地等に向けて逆探索を実行し、経路の先端が経由地から所定範囲外に出た時点で、進入探索成功と判断する方法を採ることができる。この逆探索は、得られた経路を逆走した場合に通行規制に抵触しないよう、通行規制を解釈しながら行うことになる。所定範囲は、例えば、経由地からの直線距離、道のり、リンク数、ノード数などで規定することができる。所定範囲を広げれば、出発地等から引込点に至る経路が存在する確実性が向上する一方、進入探索に要する所用時間が増大する。所定範囲は、確実性と所要時間の両者のバランスを考慮して、任意に設定可能である。
【００２０】
退出探索における局所的探索としては、経由地から目的地等に向けて順探索を実行し、経路の先端が経由地から所定範囲外に出た時点で、退出探索成功と判断する方法を採ることができる。所定範囲は、進入探索と同様の基準に基づき、任意に設定可能である。
【００２１】
進入探索についての局所的探索は、別の態様として、出発地または直前に通過すべき経由地から経由地に至る経路上のいずれかの地点を探索開始点とする経路探索を行っても良い。退出探索についての局所的探索は、別の態様として、経由地から目的地または直後に通過すべき経由地に至る経路上のいずれかの地点を探索終了点とする経路探索を行っても良い。
【００２２】
進入探索、退出探索による評価は、各引込点について必ずしも双方を行う必要はない。例えば、通行規制情報のないリンクまたはノード上の引込点に対しては、進入探索および退出探索の少なくとも一方を省略しても構わない。かかる引込点については、これらの経路探索は成功する可能性が高いからである。この省略によって、進入探索、退出探索の成否の見極めに要する時間の短縮を図ることができる。
【００２３】
本発明において、経路探索は上述した方法以外に種々の態様で行うことができる。例えば、従来技術と同様の条件で経路探索を行った上で、経由地と引込点について、１対１の関係が維持されているか否かを評価するようにしてもよい。そして、かかる関係が維持されていない経由地についてのみ、候補の引込点を順次変えながら、連続的な経路が得られるまで経路探索を繰り返し実行するようにしてもよい。
【００２４】
本発明は、上述した種々の特徴を全て備えている必要はなく、その一部を適宜省略したり組み合わせたりしても構わない。本発明は、経路探索装置、コンピュータを利用した経路探索方法、かかる経路探索を実現するコンピュータプログラム、および該コンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体など種々の態様で構成可能である。経路探索装置として構成する場合、スタンドアロンで稼働する装置としてもよいし、端末とサーバとをネットワークで接続して構成してもよい。記録媒体としては、フレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００２５】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｃ．経路探索（第１実施例）：
Ｃ１．探索方法の概要：
Ｃ２．経路探索処理：
Ｄ１．変形例１：
Ｄ２．変形例２：
Ｄ３．変形例３：
Ｄ４．変形例４：
Ｅ．経路探索（第２実施例）：
Ｆ．経路探索（第３実施例）：
【００２６】
Ａ．システム構成：
図１は実施例としての経路案内システムの全体構成を示す説明図である。実施例の経路案内システムは、経路探索装置として機能するサーバ２００と、ユーザが利用する案内装置１００をネットワークＮＥＴで接続することで構成される。ネットワークＮＥＴとしては、例えば、携帯電話回線などを利用することができる。案内装置１００は、図示した例に限らず、サーバ２００に対して複数台接続することが可能である。
【００２７】
案内装置１００は、車載のナビゲーション装置や携帯電話などを利用することができる。図中に案内装置１００の機能ブロックを併せて示した。これらの機能ブロックは、案内装置１００に搭載されたマイクロコンピュータに所定のプログラムを実行させることでソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００２８】
各機能ブロックは、主制御部１１０の制御下で、それぞれ次に示す機能を実現する。通信部１２０は、ネットワークＮＥＴを介した通信を制御する。ＧＰＳ１４０は、全地球測位システム（Global Positioning System）を利用して、案内装置１００の現在位置の緯度、経度を検出する。コマンド入力部１３０は、スイッチ等に対するユーザ操作に基づいて、経路探索、経路案内に関するコマンドを入力する。ユーザは、経路探索用のコマンドを利用して、経路探索の出発地、経由地、目的地を指定することができる。出発地は、ＧＰＳ１４０で検出される現在位置を利用してもよい。これらの指定は、サーバ２００に送信される。表示制御部１５０は、案内装置１００のディスプレイに、経路探索用のメニュー、経路案内用の地図などを表示させる。
【００２９】
サーバ２００は、案内装置１００からのコマンドに基づいて経路探索を行い、結果を案内装置１００に提供する。かかる機能を実現するための機能ブロックを図中に示した。これらの機能ブロックは、サーバ２００のＣＰＵが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００３０】
地図ＤＢ２２０は、経路探索および経路案内に使用される電子地図データベースである。本実施例では、地図ＤＢ２２０には、道路ネットワークＤＢ２２２と、描画ＤＢ２２１が含まれる。道路ネットワークＤＢ２２２は、経路探索に利用されるデータベースであり、道路の接続状態をリンクやノードで表したデータ、通行規制情報、およびリンクの評価値であるコストなどを記録している。描画ＤＢ２２１は、経路案内時に、地図情報を表示するためのデータである。地図ＤＢ２２０には、これらのデータベースに加えて、経路探索の出発地、目的地の設定を支援するための検索ＤＢを設けても良い。ＤＢ管理部２１２は、経路探索時、経路案内時に、それぞれ必要なデータを地図ＤＢ２２０から読み出す機能を奏する。
【００３１】
通信部２０２は、ネットワークＮＥＴ経由での案内装置１００との通信を制御する。通信される情報には、出発地、目的地、経由地の指定その他の経路探索用のコマンド、経路探索結果が含まれる。地点入力部２０４は、通信部２０２経由で、出発地、目的地、経由地の指定結果を受け取り、それぞれを引込点管理テーブル２０８に記録する。引込点管理テーブル２０８は、このように経路探索で使用すべき種々の地点情報を管理するためのテーブルである。その構成については、後述する。
【００３２】
引込点設定部２１０は、出発地、目的地、経由地のうち、リンクおよびノードからずれている点について、引込点を設定する。引込点とは、出発地等の各地点の周辺のリンクおよびノード上に設定される代替地点を言う。引込点の設定方法は任意であるが、本実施例では、出発地等の周辺に存在する各リンクにおろした垂線の足を引込点として設定するものとした。引込点は出発地等の各地点につき、複数設定される場合がある。
【００３３】
経路探索部２０６は、ユーザから指定されたコマンドに基づき、引込点管理テーブル２０８および地図ＤＢ２２０を参照して、経路探索を行う。経路探索には、例えば、ダイクストラ法など周知の方法を利用可能である。得られた経路は、探索結果出力部２１４に受け渡される。探索結果出力部２１４は、経路探索の結果、および地図ＤＢ２２０を参照して、経路案内に必要な地図および案内情報を、案内装置１００に出力する。
【００３４】
Ｂ．データ構造（道路ネットワークＤＢおよび引込点管理テーブル）：
図２は道路ネットワークＤＢ２２２および引込点管理テーブル２０８のデータ構造を示す説明図である。図の中央に、道路に対応するリンク、ノードの例を示し、上方に道路ネットワークＤＢ２２２の構造例を示し、下方に引込点管理テーブル２０８の例を示した。
【００３５】
図の中央の例では、道路の接続状態はリンクＬ１〜Ｌ７、ノードＮ１〜Ｎ６で表現される。ノードは、リンク同士の接続点に相当する。この例では、リンクＬ１〜Ｌ７は直線状であるが、リンクの通過点座標を複数指定することにより、折れ線状のリンクを設定することも可能である。リンクＬ４には、一方通行Ｔｒ１という通行規制が設定されている。この通行規制は、矢印ａ１に沿う通行、即ち「ノードＮ２→Ｎ３→Ｎ６」という通行、および矢印ａ２に沿う通行、即ち「ノードＮ４→Ｎ３→Ｎ６」という通行が禁止されていることと同義である。
【００３６】
道路ネットワークＤＢ２２２は、ノードデータ２２２ａとリンクデータ２２２ｂを有している。ノードデータ２２２ａは、各ノードについて緯度、経度の位置情報、および通行規制情報を記録する。例えば、ノードＮ３については、「（緯度、経度）＝（Ｌａｔ３、Ｌｏｎ３）」という位置情報が記録され、通行規制情報には、通行不能な通過方法、この例では、上述した「ノードＮ２→Ｎ３→Ｎ６」および「ノードＮ４→Ｎ３→Ｎ６」という通過方法が記録されている。
【００３７】
リンクデータ２２２ｂは、各リンクについて、位置情報およびコストを記録する。位置情報は、始点および終点のノードを記録するものとした。これらのノード間に、リンクが通過する地点の座標値を複数指定可能としてもよい。コストは、経路探索の一手法であるダイクストラ法において用いられる各リンクの評価値である。リンクデータ２２２ｂには、更に、各リンクに接続するリンクを指定する情報を含めても良い。
【００３８】
引込点管理テーブル２０８は、経路探索で使用される各地点の情報を管理するためのテーブルである。出発地ＳＴ、経由地Ｖ１その他の経由地、目的地ＤＳＴの各地点は、通過すべき順番に配列される。各地点の位置は、ノードの符号または緯度、経度の座標値で記録される。図の例では、出発地ＳＴおよび目的地ＤＳＴの位置は、ノードの符号で記録され、経由地の位置は座標で記録されている。
【００３９】
出発地、経由地、目的地がリンクまたはノード上から外れている場合には、引込点が設定される。引込点管理テーブル２０８の引込点情報（以下、「引込点リスト」と呼ぶこともある）は、各地点に対応づけられた引込点の位置座標、および経路探索での使用可否を記録する。図の例では、経由地Ｖ１に対して、引込点Ｐ１１、Ｐ１２が設定されている。但し、図中では各引込点の緯度、経度は図示を省略した。可否とは、経路探索への使用可否を表す。「ＮＡ」は使用不可（Not Available）、「Ａ」は使用可（Available）を表している。使用可否は、経路探索の過程で付されるものであり、引込点の設定後の初期状態では、いずれの情報も付されていない「Ｎｕｌｌ」か、使用可「Ａ」に統一されている。
【００４０】
道路ネットワークＤＢ２２２および引込点管理テーブル２０８は、上述の情報が記録されていればよく、データ構造自体は図２の例示に限らず、種々の構造を適用可能である。
【００４１】
Ｃ．経路探索（第１実施例）：
Ｃ１．経路探索方法の概要：
図３は経路探索方法の概要を示す説明図である。先に図２で示した道路の接続状態を例にとって説明する。まず、かかる道路構成において、出発地ＳＴから経由地Ｖ１までの経路探索を行う場合を考える。このように経由地に向かう経路探索を、以下、進入探索と呼ぶものとする。経由地Ｖ１は、リンク上にないため、引込点Ｐ１１またはＰ１２のいずれかを探索終了点として経路探索することになる。引込点Ｐ１１は、リンクＬ４の一方通行規制Ｔｒ１により、経路が得られない。従って、出発地ＳＴから経由地Ｖ１までの探索結果としては、引込点Ｐ１２を探索終了点とする経路Ｒ１が得られる。
【００４２】
次に、経由地Ｖ１から目的地ＤＳＴまでの経路探索を実行する。このように経由地から次の地点に向かう経路探索を、以下、退出探索と呼ぶものとする。この退出探索を、進入探索と独立に実行すると、退出探索においては、進入探索で使用された引込点Ｐ１２と異なる引込点Ｐ１１から目的地ＤＳＴに至る経路Ｒ３が解として得られる可能性がある。本実施例では、かかる結果を回避するため、進入探索と同一の引込点Ｐ１２を用いて退出探索を実行することにより、経路Ｒ２を得る。この結果、全体としては、出発地ＳＴから経路Ｒ１で引込点Ｐ１２に向かい、その後、引込点Ｐ１２から経路Ｒ２で目的地ＤＳＴに向かうという連続した経路が得られる。
【００４３】
上述の通り、本実施例では、各経由地について、一カ所の引込点が使用されるという条件、換言すれば、経由地と引込点が１対１に対応するという条件下で、経路探索を実行する。以下、かかる経路探索を実現するためのアルゴリズムについて説明する。
【００４４】
Ｃ２．経路探索処理：
図４は経路探索処理のフローチャートである。サーバ２００の各機能ブロックが連係して実現する処理であり、ハードウェア的には、サーバ２００のＣＰＵが実行する処理である。
【００４５】
処理が開始されると、サーバ２００は、案内装置１００に対するユーザの操作に基づいて、出発地、目的地、経由地の指定を入力する（ステップＳ１０）。そして、これらの指定された地点を引込点管理テーブル２０８に登録し、リンクまたはノード上に存在しない地点については引込点を設定し、引込点リストを作成する（ステップＳ１１）。
【００４６】
次に、サーバ２００は、各経由地について、経路探索に使用する引込点を決定するための処理を実行する（ステップＳ２０）。まず、処理対象となる経由地（以下、「対象経由地」と称する）に関連づけられている引込点から一つを候補として選択する（ステップＳ３０）。この選択は、ランダムに選択する方法、経由地からの距離が近い順に選択する方法、通行規制情報が無いリンクまたはノード上に設定された引込点から順に選択する方法など、種々の方法によって行うことができる。本実施例では、距離が近い順に優先的に候補として選択する方法を採用した。こうして選択された引込点を、以下、「候補引込点」と称する。
【００４７】
次に、サーバ２００は、候補引込点について、進入探索を実行する（ステップＳ４０）。進入探索では、出発地を探索開始点として設定し、候補引込点を探索終了点として設定して、経路探索を実行する。経路探索に失敗した場合は（ステップＳ５０）、引込点管理テーブル２０８において、候補引込点の情報を使用不可「ＮＡ」に更新して（ステップＳ５３）、他の候補引込点について再度、処理を繰り返す（ステップＳ３０〜Ｓ５０）。
【００４８】
探索に成功した場合には（ステップＳ５０）、同じ候補引込点について退出探索を実行する（ステップＳ５１）。退出探索では、候補引込点を探索開始点として設定し、目的地を探索終了点として設定して、経路探索を実行する。経路探索に失敗した場合は（ステップＳ５０）、引込点管理テーブル２０８において、候補引込点の情報を使用不可「ＮＡ」に更新して（ステップＳ５３）、他の候補引込点について再度、進入探索から、処理を繰り返す。退出探索に成功すれば、その候補引込点を、経路探索に使用可能な点として確定し（ステップＳ５４）、引込点管理テーブル２０８において、この候補引込点の情報を使用可「Ａ」に変更する。
【００４９】
以上の処理を各経由地について実行することにより（ステップＳ６０）、経路探索に使用すべき引込点が決定される。サーバ２００は、こうして設定された引込点を用いて、経路探索を実行する（ステップＳ６２）。この経路探索は、出発地から１番目の経由地、１番目の経由地から２番目の経由地、…と区間に分けて目的地に至るまでの経路を区間ごとに探索する。
【００５０】
本実施例によれば、各経由地については、ステップＳ６０までの処理で設定された引込点を使用するため、必ず連続した経路、現実に移動可能な経路が得られることになり、経路探索装置の利便性が向上する。
【００５１】
Ｄ１．変形例１：
図５は変形例としての引込選択処理のフローチャートである。実施例（図４）におけるステップＳ３０に代わる処理である。変形例では、引込点と経由地との距離、および通行規制情報の有無の双方を考慮して、候補引込点を選択する処理を示す。
【００５２】
変形例の処理では、全引込点について、まず引込点と経由地との距離Ｄを算出し（ステップＳ３３）、この距離に基づき評価値Ｖｄを算出する（ステップＳ３４）。評価値は、高いほど、候補引込点としての優先度が高くなることを意味する。図中に、距離Ｄと評価値Ｖｄとの関係を例示した。両者の関係は任意に設定可能であり、例えば、直線Ｃ１のように設定すれば、距離Ｄが遠くなるにつれて線形的に評価値Ｖｄは低下し、一定距離以上の引込点については「評価値Ｖｄ＝０」となる。曲線Ｃ２のように設定すれば、経由地に非常に近い引込点の評価値Ｖｄが非常に大きくなる。曲線Ｃ３のように設定すれば、経由地付近ではほぼ一定の評価値Ｖｄとしつつ、その範囲から少し外れると急激に評価値Ｖｄが下がる。曲線Ｃ２、Ｃ３では、経由地付近の引込点が比較的選ばれやすい傾向が生じる。
【００５３】
次に、サーバ２００は、通行規制に基づく評価値Ｖｒを算出する（ステップＳ３５）。この例では、規制有りの場合には「評価値Ｖｒ＝０．５」、規制無しの場合には「評価値Ｖｒ＝１．０」と設定するものとした。両者の値は、任意に設定可能である。規制有りの場合に、評価値Ｖｒを０としても構わない。
【００５４】
サーバ２００は、こうして得られた評価値Ｖｄ、Ｖｒに基づき、次式（１）によって、候補引込点の評価値Ｖｖを算出する（ステップＳ３６）。
Ｖｖ＝ｋ１×Ｖｄ＋ｋ２×Ｖｒ；
ｋ１，ｋ２は重み係数（実数） …（１）
【００５５】
重み係数の値は任意に設定可能である。いずれか一方を値０としても構わない。例えば、ｋ１を値０とすれば、通行規制の有無のみで評価値Ｖｖが決まることになる。ｋ２を値０とすれば、逆に、経由地からの距離のみで評価値Ｖｖが決まることになる。
【００５６】
サーバ２００は、全引込点について、上述の方法で評価値Ｖｖを求め（ステップＳ３７）、その評価値Ｖｖが最大の引込点を選択する（ステップＳ３８）。変形例の方法によれば、経由地からの距離、通行規制の双方を考慮して、候補引込点を選択することが可能となる。
【００５７】
Ｄ２．変形例２： 図６は変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ４０に代わる処理のみを示した。実施例では、出発地ＳＴと候補引込点との間で進入探索を行ったのに対し、変形例では、引込点から出発地ＳＴに向けて経路探索を行うとともに、出発地ＳＴに至る経路が完全に求められる前の時点で進入探索の成否を判断する局所的探索を実行する。
【００５８】
この処理が開始されると、サーバ２００は探索終了点として引込点を設定する（ステップＳ４０ａ）。そして、探索終了点側から逆向きに探索を実行する（ステップＳ４０ｂ）。この探索はダイクストラ法などによって行うことができる。逆向きの探索なので、通行規制については得られた経路を逆走した場合に違反とならないように考慮する。この検索は、無秩序に経路を延伸する態様で行ってもよいが、出発地ＳＴの方向を重視し、探索終了点側から出発地ＳＴに向けて経路が延伸するよう行うことがより好ましい。
【００５９】
サーバ２００は、探索された経路の長さが所定長Ｔｈ以上となった場合には（ステップＳ４０ｃ）、探索成功と判定し（ステップＳ４０ｄ）、進入探索処理を終了する。本変形例では、経路長さをリンク数で評価するものとし、「Ｔｈ＝１０」とした。即ち経路のリンク数が１０本以上に延伸した時点で探索成功と判定するものとした。判断基準値Ｔｈは任意に設定可能である。また、ステップＳ４０ｃの判断は、種々の態様を採ることが可能であり、例えば、探索された経路末端と引込点との直線距離や、引込点から経路末端までの道のりと、所定長Ｔｈとの比較を行うようにしてもよい。
【００６０】
探索された経路の長さが所定長Ｔｈに至らない場合には（ステップＳ４０ｃ）、探索の中止条件が成立しているか否かを判断する（ステップＳ４０ｅ）。中止条件としては、例えば、所要時間が所定値を超えること、延伸可能な経路が存在しなくなることなどを用いることができる。探索の中止条件が成立した場合には、サーバ２００は探索失敗と判定し（ステップＳ４０ｆ）、進入探索処理を終了する。探索中止条件が成立するまでは、再び経路探索を実行する（ステップＳ４０ｂ）。変形例では、このように局所的探索を利用するため、進入探索の成否を短時間で判定でき、ひいては経路探索の所要時間を短縮することができる。
【００６１】
同様に、退出探索に局所的探索を適用してもよい。この場合には、図６のステップＳ４０ａにおいて、探索開始点を引込点、探索終了点を目的地と設定し、ステップＳ４０ｂにおいて、探索開始点から棚策終了点に向けて順探索を行うようにすればよい。局所的探索は、進入探索、退出探索の双方に適用してもよいし、いずれか一方にのみ適用してもよい。
【００６２】
Ｄ３．変形例３：
図７は局所的探索の変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ３０〜Ｓ５０に代わる処理のみを示した。実施例では、出発地ＳＴと候補引込点との間で進入探索を行ったのに対し、変形例では、出発地ＳＴよりも経由地に近い地点を利用して進入探索を実行する。
【００６３】
この処理では、サーバ２００は、候補引込点に対する経路探索が初回か否かを判定する（ステップＳ４１）。初回である場合には、実施例と同様、探索開始点として出発地ＳＴを用い、探索終了点として候補引込点を用いて進入探索を実行する（ステップＳ４２、Ｓ４４）。２回目以降の処理では、探索開始点として、経由地からＮ個手前のノードを用いて進入探索を実行する（ステップＳ４３、Ｓ４４）。
【００６４】
図の下方に、この処理の一例を示した。経由地Ｖ１について引込点Ｐ１１、Ｐ１２が設定されている場合を考える。候補としての優先度は、引込点Ｐ１１の方が引込点Ｐ１２よりも高いものとする。
【００６５】
かかる状態において、初回の処理では、探索開始点を出発地ＳＴ、探索終了点を候補引込点Ｐ１１として経路探索を行い、太い実線の経路Ｒ１を得る。この候補引込点Ｐ１１について、例えば、退出探索が不成功に終わると、次は、候補引込点Ｐ１２について進入探索を実行することになる。この場合は、ステップＳ４３に示した通り、経由地からＮ個手前のノードを探索開始点として設定する。図の例では、既に求まっている経路Ｒ１に沿って３個手前のノードＮ３を探索開始点として使用する場合を示した。進入探索は、ノードＮ３と候補引込点Ｐ１２の間の局所的探索となり、経路Ｒ２が得られる。このように局所的探索を利用することにより、探索の所用時間が短縮されるため、各候補引込点について、進入探索の成否を速やかに判断することができる。ここでは、「３個手前」の例を示したが、局所的探索における探索開始点は、候補引込点を変更した場合でも出発地ＳＴから共通して通過する経路範囲内で、任意に設定可能である。
【００６６】
図７では、進入探索に局所的探索を利用した場合を例示した。同様にして、退出探索にも局所的探索を適用可能である。この場合、探索開始点として候補引込点を用い、探索終了点として、例えば、候補引込点から目的地に向けてＮ個移動したノードを用いることができる。局所的探索は、進入探索および退出探索の双方に適用してもよいし、いずれか一方にのみ適用しても構わない。
【００６７】
Ｄ４．変形例４：
図８は他の変形例としての経路探索処理のフローチャートである。実施例（図４）のステップＳ１１以降のみを示した。実施例では、候補引込点について無条件に進入探索を実行したが、この変形例では、条件に応じて省略する。即ち、候補引込点が設定されているリンクまたはノードに対して、通行規制が有るか否かを判断する（ステップＳ４０ｐ）。通行規制がない場合には、進入探索および退出探索共に成功する可能性が高いと判断し、これらの処理を省略して、引込点を確定する（ステップＳ５４）。通行規制が設定されている場合には、経路探索が失敗する可能性があるため、実施例（図４）と同様の処理により、進入探索、退出探索を検査する。
【００６８】
本変形例の処理によれば、一定条件下で進入探索、退出探索を省略することができるため、経路探索に使用する引込点を速やかに確定することができる利点がある。
【００６９】
Ｅ．経路探索（第２実施例）：
図９は第２実施例としての経路探索処理のフローチャートである。第１実施例（図４）では、各経由地について、経路探索に使用する引込点を確定した後、改めて経路探索を行う例を示した。これに対し、第２実施例では、経路探索と引込点の決定を同時並行して行う例を、適宜、図３の道路構成を参照しながら説明する。
【００７０】
この処理では、出発地を経由地［０］、途中の経由地を経由地［１］、［２］…［ｎ−１］、目的地を経由地［ｎ］（ｎは自然数）と表すものとする。処理が開始されると、サーバ２００はこれらの地点の指定を入力する（ステップＳ１００）。そして、第１実施例（図４）と同様に、引込点リストを作成する（ステップＳ１０２）。
【００７１】
次に、経路探索の処理を実行に使用する制御変数に値１を代入する初期化処理を行い（ステップＳ１０４）、以下の手順で経路探索を実行する。まず、経由地［ｉ−１］について引込点［ｉ−１］を確定する（ステップＳ１０６）。初めてこの処理を実行する時（ｉ＝１の時）には、経由地［０］、即ち出発地に関連づけられた引込点［０］を確定することになる。出発地がノード上にある時には、「引込点［０］＝出発地［０］」と扱う。
【００７２】
次に、サーバは、経由地［ｉ］の候補引込点［ｉ］を選択する（ステップＳ１０８）。図３の例に即して説明すれば、経由地［１］の候補引込点［１］として、引込点Ｐ１１，Ｐ１２のいずれか一方を選択することになる。選択には、第１実施例と同様、種々の方法を適用できる。ここでは、経由地Ｖ１の最寄りの引込点Ｐ１１を選択したものとする。サーバ２００は、こうして設定された２つの引込点を用いて進入探索を行う（ステップＳ１１０）。
【００７３】
この進入探索は、探索開始点として引込点［ｉ−１］を設定し、探索終了点として引込点［ｉ］を用いる。この探索は、実質的には、引込点［ｉ−１］についての退出探索とみることもできる。第１実施例（図４）が探索開始点として出発地を固定的に使用していたのに対し、第２実施例では、探索開始点も変動する点で相違する。即ち、第２実施例では、経由地で区切られた区間ごとに進入探索を実行するのである。「ｉ＝１」の時、図３の例では、引込点［０］に相当する出発地ＳＴと、引込点［１］に相当する引込点Ｐ１１との間で進入探索を行うことになる。
【００７４】
この経路探索が不成功の場合において（ステップＳ１１２）、経由地［ｉ］について全引込点［ｉ］の検討が未了の場合は（ステップＳ１３０）、実施例と同様、引込点管理テーブル２０８の内容を更新し（ステップＳ１３２）、次の候補引込点について同様の処理を実行する。
【００７５】
例えば、図３の例では、出発地ＳＴと引込点Ｐ１１の間の経路探索は不成功に終わるが、経由地Ｖ１についてはまだ他の引込点Ｐ１２が残っている。従って、引込点管理テーブル２０８において、引込点Ｐ１１に対しては使用不可「ＮＡ」と記録し、次に引込点［１］として引込点Ｐ１２を選択して（ステップＳ１０８）、進入探索を再試行する。
【００７６】
経路探索に成功した場合には（ステップＳ１１２）、経由地［ｉ］に到達できることを意味するから、制御変数ｉを値１だけインクリメントし（ステップＳ１２０）、「ｉ＞ｎ」、即ち目的地に到達していないと判断される場合には（ステップＳ１２２）、再度、上述の処理を実行する。
【００７７】
図３の例では、制御変数を値２にインクリメントした後の処理として、経由地［１］についての引込点［１］をＰ１２に確定し（ステップＳ１０６）、経由地［２］の引込点、即ち目的地ＤＳＴを選択して（ステップＳ１０８）、これらの間で進入探索を行うことになる（ステップＳ１１０）。これらの経路探索が成功すれば（ステップＳ１１２、Ｓ１２０、Ｓ１２２）、出発地ＳＴから目的地ＤＳＴに至る経路が得られることになる。
【００７８】
上述の処理において、経由地［ｉ］に関連づけられた全引込点について進入探索が不成功となる場合が生じ得る（ステップＳ１３０）。かかる場合に、第２実施例では、経由地［ｉ−１］における引込点［ｉ−１］の設定まで遡って処理を再試行する。まず、引込点管理テーブル２０８において、経由地［ｉ］に関連づけられた引込点に付されている使用不可「ＮＡ」の情報を全てリセットするとともに、経由地［ｉ−１］について確定した引込点［ｉ−１］に対して使用不可「ＮＡ」を設定する（ステップＳ１３４）。その後、制御変数を値１だけデクリメントして、経路探索（ステップＳ１０６以降）を再試行するのである。
【００７９】
図３において、「ｉ＝２」、即ち引込点Ｐ１２と目的地との間で進入探索を行う場合を考える（ステップＳ１１０）。この経路探索が不成功に終わったとすると、引込点管理テーブル２０８において、経由地［ｉ］（即ち目的地）に関連づけられた引込点［ｉ］の情報を全てリセットする（ステップＳ１３４）。また、経由地［ｉ−１］の引込点［ｉ−１］（即ち引込点Ｐ１２）の情報を使用不可「ＮＡ」に設定する（ステップＳ１３４）。その後、制御変数を「ｉ＝１」に設定し、再度経路探索を実行する。即ち、出発地ＳＴと経由地Ｖ１との間の経路探索を再試行するのである。図３の例では、経由地Ｖ１について２カ所の引込点Ｐ１１、Ｐ１２しか示されていないが、他の引込点があれば、この引込点について進入探索が行われることになる。
【００８０】
第２実施例の経路探索によれば、各経由地の引込点が決定した時点で、改めて経路探索を行うまでなく、全体の経路が得られるため、処理時間を短縮することができる利点がある。第２実施例においても、ステップＳ１０８における引込点の選択には、第１実施例と同様、引込点と経由地の距離、通行規制の有無などを考慮した選択規則を適用することができる。
【００８１】
Ｆ．経路探索（第３実施例）：
図１０は第３実施例としての経路探索処理のフローチャートである。第３実施例では、各経由地について、複数の引込点を併用することを許容する例を示す。
【００８２】
この処理が開始されると、サーバ２００は、第１実施例（図４）と同様、出発地、目的地、経由地を設定し（ステップＳ２００）、引込点リストを作成する（ステップＳ２０２）。そして、全引込点について、進入探索および退出探索の成否を評価する（ステップＳ２０４〜Ｓ２１６）。進入探索および退出探索の一方が失敗した場合には、引込点管理テーブルに、使用不可「ＮＡ」と記録される（ステップＳ２１４）。これらの処理については、第１実施例（図４）と同様であるため、詳細な説明を省略する。第１実施例では、各経由地について、進入探索および退出探索の双方が成功する引込点が見つかった時点で、次の経由地の処理に移行したのに対し、第３実施例では、全引込点について進入探索および退出探索の評価を行う。進入探索および退出探索には、第１実施例および変形例で示した種々の手法を適用可能である。
【００８３】
全引込点について処理が完了すると、サーバ２００は使用可能と評価された引込点、即ち、進入探索および退出探索の双方が成功した引込点から、各経由地について経路探索時に使用する引込点を確定し（ステップＳ２２０）、経路探索を実行する（ステップＳ２４０）。
【００８４】
図１１は引込点確定処理のフローチャートである。図１０のステップＳ２２０に相当する処理である。この処理では、サーバ２００は、全経由地について（ステップＳ２２２）、以下の処理を実行する。まず、サーバ２００は、引込点管理テーブルを参照し（ステップＳ２２４）、利用可能な引込点の数を調べる。かかる引込点が１個の場合には（ステップＳ２２６）、この引込点を経路探索に使用する点として確定し（ステップＳ２２８）、次の経由地の処理に移行する（ステップＳ２３４）。
【００８５】
利用可能な引込点が複数存在する場合には（ステップＳ２２６）、その経由地に対応づけられた利用可能な全引込点について、現在の経由地からの距離Ｄ、直前の経由地からの距離Ｄｐ、直後の経由地までの距離Ｄｎを算出する（ステップＳ２３０）。そして、「Ｄ＋Ｄｐ」が最小となる引込点を、その経由地に進入する際の引込点として確定し、 「Ｄ＋Ｄｎ」が最小となる引込点を、その経由地から退出する際の引込点として確定し（ステップＳ２３２）、次の経由地の処理に移行する（ステップＳ２３４）。進入時と退出時で、使用する引込点は一致しても構わないし、異なっても構わない。
【００８６】
図中に、進入時の引込点の確定方法を例示した。経由地Ｖ２２について２つの引込点Ｐ２１、Ｐ２２が利用可能であるとする。経由地Ｖ２２の直前の経由地はＶ２１、直後の経由地はＶ２３とする。図中の太線はリンクを表し、黒丸はノードを表している。引込点Ｐ２１について、経由地との距離はＤ２１、直前の経由地Ｖ２１との距離はＤｐ２１である。引込点Ｐ２２について、経由地との距離はＤ２２、直前の経由地Ｖ２１との距離はＤｐ２２である。この場合、「Ｄ２１＋Ｄｐ２１＜Ｄ２２＋Ｄｐ２２」となるため、経由地Ｖ２２への進入時には、引込点Ｐ２１が使用されることになる。
【００８７】
同様にして、経由地Ｖ２２の直後の経由地Ｖ２３と引込点Ｐ２１、Ｐ２２の距離、および距離Ｄ２１、Ｄ２２を用いて、各引込Ｐ２１、Ｐ２２を評価すれば、経由地Ｖ２２からの退出時には、引込点Ｐ２２が使用されることになる。
【００８８】
第３実施例では、利用可能な全引込点について上述の評価を行うものとしたが、利用可能な引込点のうち経由地から所定距離内に存在するものについてのみ、上述の評価を行うようにしてもよい。第３実施例では、引込点Ｐ２１、Ｐ２２の評価を経由地Ｖ２１、Ｖ２３との直線距離に基づいて行う例を示したが、これらの経由地から引込点に至る所要時間、リンクコスト、道のりなどを単独、または組み合わせて用いて引込点の評価を行っても良い。
【００８９】
以上で説明した第３実施例の処理によれば、各経由地について複数の引込点を用いて経路案内することが許容される。但し、従来技術と異なり、経路案内には、進入および退出の双方が可能な引込点のみが用いられる。かかる場合には、経由地への進入時と退出時とで、異なる引込点が使用されたとしても、引込点間を移動可能であることが概ね保証される。案内された経路が一見して途切れている場合でも、これらの引込点間の移動方法は、現地で比較的容易に見いだすことが可能であり、実用上の支障は生じない。第３実施例によれば、例えば、駐車場を経由する場合、進入時の入口と異なる出口から退出するように案内可能となり、移動距離が短い効率的な経路を案内することが可能となる。
【００９０】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。上述の実施例では、案内装置１００とサーバ２００からなるシステムを例示したが、本発明はスタンドアロンの装置として構成することも可能である。
【図面の簡単な説明】
【００９１】
【図１】実施例としての経路案内システムの全体構成を示す説明図である。
【図２】道路ネットワークＤＢ２２２および引込点管理テーブル２０８のデータ構造を示す説明図である。
【図３】経路探索方法の概要を示す説明図である。
【図４】経路探索処理のフローチャートである。
【図５】変形例としての引込選択処理のフローチャートである。
【図６】変形例としての引込選択処理のフローチャートである。
【図７】変形例としての経路探索処理のフローチャートである。
【図８】他の変形例としての経路探索処理のフローチャートである。
【図９】第２実施例としての経路探索処理のフローチャートである。
【図１０】第３実施例としての経路探索処理のフローチャートである。
【図１１】引込点確定処理のフローチャートである。
【符号の説明】
【００９２】
１００…案内装置
１１０…主制御部
１２０…通信部
１３０…コマンド入力部
１４０…ＧＰＳ
１５０…表示制御部
２００…サーバ
２０２…通信部
２０４…地点入力部
２０６…経路探索部
２０８…引込点管理テーブル
２１０…引込点設定部
２１２…ＤＢ管理部
２１４…探索結果出力部
２２０…地図ＤＢ
２２１…描画ＤＢ
２２２…道路ネットワークＤＢ
２２２ａ…ノードデータ
２２２ｂ…リンクデータ
【特許請求の範囲】
【請求項１】
経路探索装置であって、
リンク、ノード、及び前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照部と、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力部と、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定部と、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索部とを備える経路探索装置。
【請求項２】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記経由地のそれぞれに対して、いずれか一カ所の引込点を使用する経路探索装置。
【請求項３】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記経由地からの距離が短い位置にある引込点を優先的に候補とする経路探索装置。
【請求項４】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記通行規制情報が関連づけられていないリンクまたはノード上の引込点を優先的に候補とする経路探索装置。
【請求項５】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記経由地からの距離、および前記通行規制情報の関連付けの有無の双方に基づいて定まる優先度が高い引込点を候補とする経路探索装置。
【請求項６】
請求項１〜５いずれか記載の経路探索装置であって、
前記進入探索および退出探索の少なくとも一方は、局所的探索によって行われ、
前記進入探索についての局所的探索は、前記経由地を含む所定範囲で、逆方向に進行した場合に前記通行規制情報に適合する経路となるという条件で、前記経由地側から行う経路探索であり、
前記退出探索についての局所的探索は、前記経由地を含む所定範囲で、前記通行規制情報に即して前記経由地から行う経路探索である経路探索装置。
【請求項７】
請求項６記載の経路探索装置であって、
前記経路探索部は、前記通行規制情報のないリンクまたはノード上の引込点に対し、前記進入探索および退出探索の少なくとも一方を省略する経路探索装置。
【請求項８】
経路探索方法であって、コンピュータが実行する工程として、
リンク、ノード、および前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照工程と、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力工程と、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定工程と、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索工程とを備える経路探索方法。
【請求項９】
コンピュータによって経路探索を実行するためのコンピュータプログラムであって、
リンク、ノード、および前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照用プログラムコードと、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力用プログラムコードと、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定用プログラムコードと、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索用プログラムコードとを備えるコンピュータプログラム。
【請求項１】
経路探索装置であって、
リンク、ノード、及び前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照部と、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力部と、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定部と、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索部とを備える経路探索装置。
【請求項２】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記経由地のそれぞれに対して、いずれか一カ所の引込点を使用する経路探索装置。
【請求項３】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記経由地からの距離が短い位置にある引込点を優先的に候補とする経路探索装置。
【請求項４】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記通行規制情報が関連づけられていないリンクまたはノード上の引込点を優先的に候補とする経路探索装置。
【請求項５】
請求項１記載の経路探索装置であって、
前記経路探索部は、前記複数箇所の引込点のうち、前記経由地からの距離、および前記通行規制情報の関連付けの有無の双方に基づいて定まる優先度が高い引込点を候補とする経路探索装置。
【請求項６】
請求項１〜５いずれか記載の経路探索装置であって、
前記進入探索および退出探索の少なくとも一方は、局所的探索によって行われ、
前記進入探索についての局所的探索は、前記経由地を含む所定範囲で、逆方向に進行した場合に前記通行規制情報に適合する経路となるという条件で、前記経由地側から行う経路探索であり、
前記退出探索についての局所的探索は、前記経由地を含む所定範囲で、前記通行規制情報に即して前記経由地から行う経路探索である経路探索装置。
【請求項７】
請求項６記載の経路探索装置であって、
前記経路探索部は、前記通行規制情報のないリンクまたはノード上の引込点に対し、前記進入探索および退出探索の少なくとも一方を省略する経路探索装置。
【請求項８】
経路探索方法であって、コンピュータが実行する工程として、
リンク、ノード、および前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照工程と、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力工程と、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定工程と、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索工程とを備える経路探索方法。
【請求項９】
コンピュータによって経路探索を実行するためのコンピュータプログラムであって、
リンク、ノード、および前記リンクまたはノードに関連づけられた通行規制情報を備えた道路ネットワークデータを参照するデータベース参照用プログラムコードと、
経路探索の出発地、目的地および少なくとも一カ所の経由地を入力する地点入力用プログラムコードと、
経路探索用に、前記リンクまたはノード上にない経由地について、いずれかのリンクまたはノード上に、前記経由地の代わりとなる引込点を複数箇所設定する引込点設定用プログラムコードと、
前記経由地のそれぞれに対して、引込点を探索終了点として経路を探索する進入探索、および該引込点を探索開始点として経路を探索する退出探索の双方が成立する引込点を使用するという条件を満足するよう、前記道路ネットワークデータに基づき、前記出発地、いずれかの引込点、目的地を通過する経路を探索する経路探索用プログラムコードとを備えるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００６−３２６４（Ｐ２００６−３２６４Ａ）
【公開日】平成１８年１月５日（２００６．１．５）
【国際特許分類】
【出願番号】特願２００４−１８１２４３（Ｐ２００４−１８１２４３）
【出願日】平成１６年６月１８日（２００４．６．１８）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成１８年１月５日（２００６．１．５）
【国際特許分類】
【出願日】平成１６年６月１８日（２００４．６．１８）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]