JP5802053B2 - 経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラム - Google Patents

Description

本発明は、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラムに関する。

従来、経路の途中の立寄り地を探索する技術がある。

例えば、特許文献１，２においては、出発地から目的地までの経路から、所定距離や所定時間の範囲内に存在する立寄り地を探索する技術が開示されている。

また、特許文献３においては、現在位置から立寄り地を経由して目的地に到達するまでにかかる迂回所要時間と、当該立寄り地を経由しない場合の所要時間を比較して、ロスタイムを算出する技術が開示されている。

特許第３２４２９６８号公報 特開２００２−２５７５６７号公報 特許第３１６１２７６号公報

しかしながら、従来の経由地（経路の途中の立寄り地）を探索する技術においては、適切な経由地を効率よく探索することができないという問題点を有していた。

例えば、特許文献１，２の技術においては、出発地から目的地までの経路から所定の範囲外となるものの、ロスタイムが短い経由地については探索されないという問題点を有していた。

また、特許文献３の技術においては、立寄り地ごとに目的地までの経路を探索するため、立寄り地の数に比例して処理時間が長くなるという問題点を有していた。より具体的には、特許文献３に例示されるように、ダイクストラ法を用いて経路探索を実行すると、立ち寄り地を基準地点として、リンクコストを計算しながら順次到達したノードやリンク等を広げていく拡散処理を行うことになる。そして、立寄り地ごとに目的地までの経路探索を実行すると、立ち寄り地の数だけ拡散処理を繰り返さなければならず、処理時間が増大するという問題点を有していた。

本発明は、上記問題点に鑑みてなされたもので、適切な経由地を効率よく探索することができる、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラムを提供することを目的とする。

このような目的を達成するため、本発明の記憶部と制御部とを少なくとも備えた経路探索装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記記憶部は、地点に関する地点情報を記憶する地点情報記憶手段、を更に備え、上記制御部は、上記地点情報記憶手段の上記地点情報から、上記複数の経由地候補を検索する経由地候補探索手段、を更に備え、上記経路探索手段は、上記ネットワークデータに基づいて、上記経由地候補検索手段により検索された上記複数の経由地候補について、上記経路探索条件の上記出発地から当該複数の経由地候補までの上記探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの上記探索経路を、それぞれ１回ずつ拡散させることを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記経由地候補検索手段は、上記経路探索手段により上記出発地からの上記探索経路および上記目的地からの上記探索経路が拡散される際に、上記地点情報記憶手段から当該拡散される上記探索経路付近の上記経由地候補を検索することを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記ネットワークデータ記憶手段は、上記交通網のうち、詳細な上記交通網を規定する下位階層の上記ネットワークデータと、主要な上記交通網を規定する上位階層の上記ネットワークデータと、を含む階層化された上記ネットワークデータを記憶し、上記経路探索手段は、上記出発地から上記複数の経由地候補までの上記探索経路および上記目的地から当該複数の経由地候補までの上記探索経路を拡散させる前に、上記複数の経由地候補から、上記下位階層の上記ネットワークデータに基づいて上記探索経路を拡散させることを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、上記探索結果情報生成手段は、上記経路探索手段により探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記制御部は、移動体の現在位置を示す現在位置情報を取得する現在位置情報取得手段、を更に備え、上記経路探索手段は、上記現在位置情報取得手段により取得された上記現在位置情報の上記現在位置を、上記経路探索条件の上記出発地として経路探索を行うことを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、上記制御部は、時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得する渋滞情報取得手段、を更に備え、上記経路探索手段は、探索した上記出発地から上記経由地候補までの上記経路および上記目的地から当該経由地候補までの上記経路に基づいて当該目的地への予想到達時刻を算出し、上記渋滞情報に基づいて上記予想到達時刻を修正することを特徴とする。

また、本発明の経路探索装置は、上記記載の経路探索装置において、出力部を更に備え、上記制御部は、上記出発地および上記目的地を少なくとも含む上記経路探索条件を設定する経路探索条件設定手段と、上記探索結果情報生成手段により生成された上記探索結果情報を上記出力部に出力する探索結果出力手段と、を更に備えたことを特徴とする。

また、本発明の経路探索システムは、記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記サーバ装置の上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信手段と、を備え、上記端末装置の上記制御部は、上記経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする。

また、本発明の経路探索システムは、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする。

また、本発明のサーバ装置は、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信手段と、を備えたことを特徴とする。

また、本発明の端末装置は、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする。

また、本発明の経路探索方法は、記憶部と制御部とを少なくとも備えた経路探索装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする。

また、本発明の経路探索方法は、記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて実行される経路探索方法であって、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記端末装置の上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置の上記制御部において実行される、上記端末装置から送信される、上記経路探索条件を受信する経路探索条件受信ステップと、上記サーバ装置の上記制御部において実行される、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記サーバ装置の上記制御部において実行される、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記サーバ装置の上記制御部において実行される、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信ステップと、上記端末装置の上記制御部において実行される、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信ステップと、上記端末装置の上記制御部において実行される、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする。

また、本発明の経路探索方法は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、経路探索手段と、探索結果情報生成手段と、を備えた経路探索システムにおいて実行される経路探索方法であって、上記経路探索手段が、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記探索結果情報生成手段が、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする。

また、本発明の経路探索方法は、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を含むことを特徴とする。

また、本発明の経路探索方法は、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする。

また、本発明のプログラムは、記憶部と制御部とを少なくとも備えた経路探索装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を実行させることを特徴とする。

また、本発明のプログラムは、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を実行させることを特徴とする。

また、本発明のプログラムは、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を実行させることを特徴とする。

この発明によれば、交通網を規定するネットワークデータを記憶し、ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索し、探索した、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する。これにより、本発明は、適切な経由地を効率よく探索することができるという効果を奏する。より具体的には、出発地から目的地までの経路から所定距離や所定時間の範囲内にない経路であっても、ロスタイムや追加の距離等が短い適切な経由地を探索することができる。また、経由地ごとに経路探索を実行するのではなく、１回の探索経路の拡散により纏めて複数の経由地の経路探索を実行することができるので、処理時間を短く効率的に探索することができる。

また、本発明によれば、上記において、地点に関する地点情報を更に記憶し、地点情報から、複数の経由地候補を検索し、ネットワークデータに基づいて、検索された複数の経由地候補について、経路探索条件の出発地から当該複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させる。これにより、本発明は、予め記憶した地点情報の中から、適切な経由地候補を選択することができるという効果を奏する。

また、本発明によれば、上記において、経路探索により出発地からの探索経路および目的地からの探索経路が拡散される際に、当該拡散される探索経路付近の経由地候補を地点情報から検索する。これにより、本発明は、出発地から目的地までの経路を探索しながら、探索経路に沿って好適な経由地候補を検索することができるという効果を奏する。

また、本発明によれば、上記において、交通網のうち、詳細な交通網を規定する下位階層のネットワークデータと、主要な交通網を規定する上位階層のネットワークデータと、を含む階層化されたネットワークデータを記憶し、出発地から複数の経由地候補までの探索経路および目的地から当該複数の経由地候補までの探索経路を拡散させる前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させる。これにより、本発明は、出発地周辺から目的地周辺までは上位階層のネットワークデータを用いて主要な交通網を利用した経路を探索するような場合に、経由地が主要な交通網と直接接続されていない場合であっても、経由地周辺の主要な交通網まで詳細な交通網を使って接続させることができるという効果を奏する。

また、本発明によれば、上記において、経路探索条件の出発地から目的地までの探索経路を拡散させて経路を更に探索し、探索した、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成する。これにより、本発明は、出発地から目的地までの経路において、経由地を経由する場合と経由しない場合とで、距離や所要時間等の比較結果を利用者に分かり易く提示することができるという効果を奏する。

また、本発明によれば、上記において、移動体の現在位置を示す現在位置情報を取得し、取得した現在位置情報の現在位置を、経路探索条件の出発地として経路探索を行うので、例えば、現在位置の更新に応じてリアルタイムに利用者に適切な経由地候補を提示することができるという効果を奏する。

また、本発明によれば、上記において、時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得し、探索した出発地から経由地候補までの経路および目的地から当該経由地候補までの経路に基づいて当該目的地への予想到達時刻を算出し、渋滞情報に基づいて予想到達時刻を修正する。これにより、本発明は、渋滞情報に基づいて渋滞を加味した予想到達時間を算出するために必要となる渋滞を加味しない予想到達時間を、出発地と目的地との双方向の探索経路の拡散によって求めることができ、予想到達時間を的確に算出することができるという効果を奏する。

また、本発明によれば、上記において、出発地および目的地を少なくとも含む経路探索条件を更に設定し、生成した探索結果情報を出力部に出力するので、利用者等に出発地と目的地を含む経路探索条件を設定させて、当該経路探索条件に基づいて生成された探索結果情報を出力することができるという効果を奏する。

図１は、第１の実施形態における経路探索システムの構成の一例を示すブロック図である。 図２は、第１の実施形態における経路探索システムの基本処理の一例を示すフローチャートである。 図３は、双方向拡散による経路探索結果と通常の経路探索結果とを模式的に示した図である。 図４は、階層化されたネットワークデータを用いて経路探索を行う例を模式的に示した図である。 図５は、第１の実施形態における経路探索システムの具体化処理の一例を示すフローチャートである。 図６は、経路探索条件設定部１０２ｂにより表示される、経由地の検索条件の入力画面の一例を示す図である。 図７は、経路探索条件設定部１０２ｂにより表示される経由地（ＰＯＩ）の検索条件（エリア検索条件）の入力画面の一例を示す図である。 図８は、経路探索条件設定部１０２ｂにより表示される経由地（ＰＯＩ）の検索条件（周辺検索条件）の入力画面の一例を示す図である。 図９は、双方向拡散による経路探索処理の一例を示すフローチャートである。 図１０は、探索結果情報生成部２０２ｄにより生成される表示画面の一例を示す図である。 図１１は、探索結果情報生成部２０２ｄにより生成される複数の経由地候補を重畳させた表示画面の一例を示す図である。 図１２は、第２の実施形態における経路探索装置４００の構成の一例を示すブロック図である。 図１３は、第２の実施形態における経路探索装置４００の処理の一例を示すフローチャートである。

以下に、本発明にかかる経路探索システム、サーバ装置、端末装置、経路探索装置、経路探索方法、および、プログラムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。

以下、本発明の構成および処理について、第１の実施形態（経路探索システム）、第２の実施形態（経路探索装置（スタンドアローン型））の順にて詳細に説明する。

［第１の実施形態］
最初に、本発明の第１の実施形態（経路探索システム）について、図１から図１１を参照して以下に説明する。但し、以下に示す第１の実施形態は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。例えば、第１の実施形態で例示する経路探索システムにおけるサーバ側と端末側の機能分散の形態は以下に限られず、同様の効果や機能を奏し得る範囲において、任意の単位で機能的または物理的に分散・統合して構成することができる。

［経路探索システムの構成］
まず、第１の実施形態における経路探索システムの構成の一例について、図１を参照して以下に説明する。ここで、図１は、第１の実施形態における経路探索システムの構成の一例を示すブロック図であり、該構成のうち本発明に関係する部分のみを概念的に示している。なお、本実施形態１においては、通信型のナビゲーションを提供する経路探索システムを具体例として説明するが、本発明はこれに限ることなく、スタンドアローンタイプの経路探索システムなどにも適用可能である。

図１に示すように、第１の実施形態の経路探索システムは、概略的に、サーバ装置２００、端末装置１００、および、外部機器６００を通信可能に接続して構成される。ここで、図１に示すように、通信には、一例として、ネットワーク３００を介した有線・無線通信等の遠隔通信等を含む。

図１に示すように、第１の実施形態の経路探索システムにおいて、サーバ装置２００は、概略的に、制御部２０２と記憶部２０６とを少なくとも備えており、端末装置１００は、位置取得部１１２と出力部１１４と入力部１１６と記憶部１０６と制御部１０２とを備える。また、これら経路探索システムの各部は任意の通信路を介して通信可能に接続されている。

［サーバ装置２００の構成］
ここで、図１において、サーバ装置２００は、端末装置１００から送信される、少なくとも出発地と目的地を含む経路探索条件を受信し、ネットワークデータに基づいて、受信した経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索し、探索した、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成し、生成した探索結果情報を端末装置１００に送信する等の機能を有する。サーバ装置２００は、通信制御インターフェース部２０４を介してネットワーク３００を経由し、端末装置１００や外部機器６００と相互に通信可能に接続されており、制御部２０２と記憶部２０６とを備える。また、ネットワーク３００は、端末装置１００、サーバ装置２００、および、外部機器６００等を相互に接続する機能を有し、例えば、インターネット、電話回線網（携帯端末回線網および一般電話回線網等）、イントラネット、または、電力線通信（ＰＬＣ）等であってもよい。

また、制御部２０２は、各種処理を行う制御手段である。通信制御インターフェース部２０４は、通信回線や電話回線等に接続されるアンテナやルータ等の通信装置（図示せず）に接続されるインターフェースであり、サーバ装置２００とネットワーク３００との間における通信制御を行う機能を有する。すなわち、通信制御インターフェース部２０４は、端末装置１００や外部機器６００等と通信回線を介してデータを通信する機能を有している。記憶部２０６は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の固定ディスク装置やＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）等のストレージ手段であり、各種のデータベースやテーブル（ネットワークデータベース２０６ａ、地図データベース２０６ｂ、ＰＯＩデータベース２０６ｃ、および、渋滞情報データベース２０６ｄ等）を格納する。

これら記憶部２０６の各構成要素のうち、ネットワークデータベース２０６ａは、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段である。ここで、ネットワークデータベース２０６ａに記憶されるネットワークデータは、道路ネットワークデータの他、路線網ネットワークデータ等の交通機関の交通ネットワークデータであってもよい。ここで、ネットワークデータベース２０６ａに記憶されるネットワークデータは、階層化されたネットワークデータであってもよく、例えば、交通網のうち、詳細な交通網を規定する下位階層のネットワークデータと、主要な交通網を規定する上位階層のネットワークデータと、を含んでもよい。一例として、ネットワークデータベース２０６ａにより記憶される階層化された道路ネットワークデータは、細い路地等を含む詳細な交通網を規定する下位階層のネットワークデータと、幹線道路等を含む主要な交通網を規定する上位階層のネットワークデータとを含んでもよい。なお、階層は、道路の太さ（幅員等）や制限速度等で分類してもよく、また、２つの階層とは限らず、３以上の複数の階層があってもよい。また、階層の上位と下位は、複数の階層の中の相対的なものであり、絶対的なものではない。すなわち、中位の階層は、上位階層から見れば下位階層であり、下位階層から見れば上位階層である。これらネットワークデータは、ネットワークデータベース２０６ａに予め記憶されており、サーバ装置２００の制御部２０２は、定期的に、および／または、制御部２０２による処理に応じて（例えば、制御部２０２においてデータが必要となる契機等）、ネットワーク３００を介して最新のデータを外部機器６００（例えば、ネットワークデータを提供するネットワークデータサーバなど）等からダウンロードしてネットワークデータベース２０６ａに記憶されたネットワークデータをアップデートしてもよい。

ここで、ネットワークデータベース２０６ａに記憶される道路ネットワークデータは、道路網を規定するネットワークデータであり、例えば、交差点や分岐点等の道路網表現上の結節点であるノードのノードデータと、ノード間の道路区間であるリンクのリンクデータとの組み合わせによって表現されるネットワークデータである。ノードデータには、ノード番号、緯度経度等の位置座標、ノード種別、接続するリンク本数、接続ノード番号、信号機や一時停止標識等の車両停止位置、および、交差点名称等を含んでいてもよい。また、リンクデータには、リンク番号、接続する道路の種別、国道や県道や市道等の路線番号、重用する路線情報、リンクの存在する行政区域の属性情報、リンク長、道路供用状況、異常気象時通行規制区間、車重制限、車両高さ制限、幅員、道路幅員区分、車線数、制限速度など交通規制、一時停止標識や踏切直前等の車両停止位置、高架やトンネルや橋等のリンク内属性、所要時間、および、名称等を含んでいてもよい。特に、リンクデータは、当該リンクのリンクコストを含んでいてもよく、例えば、当該道路リンクを通過するのに必要な時間や、距離や、利用料金データ等の料金に関するデータを含んでいてもよい。また、道路ネットワークデータは、交通規制データや利用料金データ等を含んでいてもよい。ここで、交通規制データは、各種の交通規制を定義するデータであり、例えば、道路の損壊や道路工事等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、および、私有地への接続路であることによる一般車の進入禁止等の情報などを含んでもよい。また、利用料金データは、自動車、オートバイ等で移動する場合に消費する燃料料金、高速自動車国道や自動車専用道路等の有料道路の通行料金等を表す情報等であってもよい。また、道路ネットワークデータは、自動車、オートバイ、自転車、徒歩等で移動する場合の経路上に存在する施設等の地点の緯度経度情報などの位置情報等を記憶してもよい。なお、ネットワークデータには、ノードとリンクで構成される各案内経路についての評価を行うために、ノード番号やリンク番号等に対応付けて評価用情報が格納されてもよい。一例として、評価用情報として交通規制データは、各種の交通規制を定義するデータであり、例えば、道路の損壊や道路工事等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、私有地への接続路であることによる一般車の進入禁止等の情報などを含む。

ネットワークデータベース２０６ａに記憶される交通ネットワークデータは、電車やバス等の交通機関の路線網等を規定したネットワークデータである。一例として、交通ネットワークデータは、電車の路線網を規定した路線網ネットワークデータであってもよく、バスの路線網を規定した路線網ネットワークデータであってもよい。例えば、ネットワークデータベース２０６ａに記憶される交通ネットワークデータは、電車、飛行機、バス、路面電車、ロープウェイ、モノレール、ケーブルカー、および、船等の各交通機関の路線網を規定するネットワークデータであり、例えば、駅、空港、港、および、停留所（バス停）等の停止位置などの路線網表現上の結節点であるノードのノードデータと、ノード間を接続する鉄道路線、航空路線、航路、および、バス路線等のリンクのリンクデータとの組み合わせによって表現されるネットワークデータである。なお、ノードデータには、ノード番号、緯度経度等の位置座標、ノード種別、接続するリンク本数、接続ノード番号、および、線路が交差する駅名等を含んでいてもよい。また、リンクデータには、リンク番号、接続する駅等の種別、列車等の路線番号、重用する路線情報、リンクの存在する行政区域の属性情報、リンク長、道路供用状況、異常気象時通行規制区間、車重制限、車両高さ制限、幅員、道路幅員区分、車線数、制限速度など交通規制、高架やトンネルや橋等のリンク内属性、および、名称等を含んでいてもよい。また、交通ネットワークデータは、交通機関の利用運賃料金データ、および、乗車位置データ等を含んでいてもよい。ここで、利用運賃料金データは、例えば、電車、飛行機、バス、路面電車、ロープウェイ、モノレール、ケーブルカー、および、船等の各交通機関を利用した場合に生じる利用料金等を表す情報等であってもよい。

また、地図データベース２０６ｂは、地図データを記憶する地図データ記憶手段である。一例として、地図データベース２０６ｂに記憶される地図データは、全国および各地方の道路地図等の地図データであってもよい。例えば、地図データベース２０６ｂに記憶される地図データは、地図上に表示される地物（例えば、ビルや住宅や駅等の建造物、道路、線路、橋、トンネル、等高線、海岸線や湖岸線等の水涯線、海、河川、湖、池、沼、公園や屋外施設等の地、行政界、行政区域、および、街区等）の形状についての形状データ、地図上に表示される注記（例えば、地名、住所、電話番号、店や公園や駅等の施設名称、名所や旧跡や河川や湖や湾や山や森林等の俗称を含む名称、道路や橋やトンネル等の名称、路線名称、地点情報、および、口コミ情報等）の注記データ、および、地図上に表示される記号（例えば、山、史跡、寺社、学校、病院、工場および墓地等の地図記号、ガソリンスタンド、コンビニエンスストア、スーパーマーケット、レストラン、銀行および郵便局等の店舗記号、道路上の信号、有料道路の出入口、料金所、サービスエリア、パーキングエリアおよびインターチェンジ等の記号、駐車場、駅、ホテル、美術館および博物館等の施設記号、ならびに、口コミ地点記号等）の記号データ等のデータを含んでいてもよい。なお、地図データは、道路地図等の地図データに限らず、路線図等の地図データであってもよい。ここで、地図データは、縮尺に従ってメッシュ化された地図データ（例えば、ＪＩＳ規格の第１〜３次地域区画メッシュデータ、および、１００ｍメッシュデータ等）等であってもよい。また、地図データは、ラスタ形式、ベクタ形式等の地図描画用の画像データであってもよい。これら地図データは、地図データベース２０６ｂに予め記憶されており、サーバ装置２００の制御部２０２は、定期的に、および／または、制御部２０２による処理に応じて（例えば、制御部２０２においてデータが必要となる契機等）、ネットワーク３００を介して最新のデータを、外部機器６００（地図データを提供する地図提供サーバ等の外部機器等）からダウンロードして地図データベース２０６ｂに記憶された地図データをアップデートしてもよい。

また、ＰＯＩデータベース２０６ｃは、ＰＯＩ等に関する地点情報を記憶する地点情報記憶手段である。ここで、本実施の形態において、ＰＯＩ（ｐｏｉｎｔ ｏｆ ｉｎｔｅｒｅｓｔ）は、便利な場所や興味のある場所などとして人が知覚する特定の地点や施設や領域等であって、建造物や、設備、店舗、会社、事務所、公共施設、娯楽施設、および、屋外施設、観光スポットや景勝地などの地点や地物や領域等であってもよい。すなわち、本実施形態において、ＰＯＩデータベース２０６ｃは、ＰＯＩの地点情報を含むＰＯＩ情報を記憶する。ＰＯＩ情報は、少なくともＰＯＩの地点情報（緯度経度等）のほか、ＰＯＩの名称（地点名称）、カテゴリ（種別）等の属性、住所、電話番号、ＵＲＬ、営業時間情報、取扱商品情報、写真データ、クーポン情報、口コミ情報、使用条件、使用可能性、施設規模情報、ＰＯＩの緯度経度高度、ＰＯＩ ＩＤ、および、当該ＰＯＩ情報の更新日時等の情報を含んでいてもよい。ここで、店舗は、例えば、飲食店、食料品店、酒店、タバコ店、百貨店、ショッピングセンター、スーパーマーケット、コンビニエンスストア、ガソリンスタンド、金融機関、郵便局、立体駐車場、および、ホテルや旅館等の宿泊施設等であってもよい。また、公共施設は、例えば、官庁、警察署、交番、消防署、駅、医療機関、美術館、博物館、および、学校等であってもよい。また、娯楽施設は、例えば、映画館、劇場、遊園地、パチンコ店、カジノ、競馬場等であってもよい。また、屋外施設は、バスターミナル、公園、遊園地、キャンプ場、連絡通路、屋外駐車場、および、動物園等であってもよい。これらＰＯＩ情報は、ＰＯＩデータベース２０６ｃに予め記憶されており、サーバ装置２００の制御部２０２は、定期的に、および／または、制御部２０２による処理に応じて（例えば、制御部２０２においてデータが必要となる契機等）、ネットワーク３００を介して最新のデータを外部機器６００（例えば、ＰＯＩ情報を提供する施設情報提供サーバなど）等からダウンロードしてＰＯＩデータベース２０６ｃに記憶されたＰＯＩ情報をアップデートしてもよい。

また、渋滞情報データベース２０６ｄは、渋滞情報を記憶する交通情報記憶手段である。ここで、渋滞情報は、時刻ごと地点ごとに予想される渋滞発生を示す情報である。一例として、渋滞情報は、道路上のリンクＩＤ等に対応づけて、渋滞が発生すると予測される時刻等を含んでもよい。また、渋滞情報は、渋滞発生地点や渋滞距離や道路上の二地点間の通過時間（すなわち、旅行時間など）等の渋滞情報を含んでいてもよい。ここで、渋滞情報は、交通障害情報や交通規制情報、鉄道等の交通機関の運行情報を含んでもよい。ここで、交通規制情報は、各種の交通規制を定義するデータであり、例えば、降水量規制、積雪・凍結規制、超波規制、風速規制、および視程規制等の異常気象時通行規制、高さ規制および重量規制等の車両通行規制、道路工事や作業、道路周辺の工事に伴う工事時規制、時間帯や車種により通行できる通行帯を規制している通行帯規制および道路の損壊等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、ならびに、私有地への接続路であることによる一般車の進入禁止等の情報などを含んでもよい。また、交通規制情報は、工事、事故、または、車両故障等により車両通行帯等が走行不能または走行困難となる通行規制情報であってもよい。また、これら渋滞情報は、渋滞情報データベース２０６ｄに予め記憶されており、サーバ装置２００の制御部２０２（後述する渋滞情報取得部２０２ｆ）は、定期的（例えば、５分毎等）にネットワーク３００を介して最新のデータを外部機器６００（例えば、警察庁、ＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）（登録商標）、および、ＡＴｉＳ（Ａｄｖａｎｃｅｄ Ｔｒａｆｆｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｒｖｉｃｅ）（登録商標）、日本道路交通情報センター（ＪＡＲＴＩＣ）（登録商標）、鉄道会社、および、渋滞情報配信サーバ（サービス）など）等からダウンロードして渋滞情報データベース２０６ｄに記憶された交通情報をアップデートしてもよい。

また、制御部２０２は、ＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部２０２は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部２０２は、機能概念的に、経路探索条件受信部２０２ａ、経由地候補検索部２０２ｂ、経路探索部２０２ｃ、探索結果情報生成部２０２ｄ、探索結果情報送信部２０２ｅ、および、渋滞情報取得部２０２ｆを備える。

このうち、経路探索条件受信部２０２ａは、端末装置１００から送信される、少なくとも出発地と目的地を含む経路探索条件を受信する経路探索条件受信手段である。なお、経路探索条件受信部２０２ａにより受信される経路探索条件は、現在位置情報を含んでもよい。例えば、経路探索条件受信部２０２ａは、現在位置情報受信部２０２ａにより受信される端末装置１００の現在位置情報による現在位置を、経路探索条件の出発地として取得してもよい。また、端末装置１００より送信される更新された現在位置情報を受信した場合等には、経路探索条件受信部２０２ａは、最新の現在位置情報による現在位置を、経路探索条件の出発地として再設定してもよい。

また、経由地候補検索部２０２ｂは、ＰＯＩデータベース２０６ｃに記憶されたＰＯＩの地点情報（ＰＯＩ情報）から、複数の経由地候補を検索する経由地候補探索手段である。ここで、経路探索部２０２ｃにより経路探索条件の出発地からの探索経路および目的地からの探索経路が拡散されると同時に、経由地候補検索部２０２ｂは、拡散される探索経路に基づいて、ＰＯＩデータベース２０６ｃから探索経路付近の複数のＰＯＩを、複数の経由地候補として検索してもよい。すなわち、経路探索部２０２ｃが探索経路を拡散させる場合に、経由地候補検索部２０２ｂは、ＰＯＩデータベース２０６ｃに記憶されたＰＯＩの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するＰＯＩを経由地候補として取得してもよい。なお、上記に限らず、経由地候補検索部２０２ｂは、経路探索条件の出発地や現在位置（所定時間後の予想現在位置でもよい。）や目的地等の周辺（例えば、所定の形状範囲内）に存在するＰＯＩを、ＰＯＩデータベース２０６ｃから検索してもよい。例えば、経由地候補検索部２０２ｂは、出発地および目的地の２点を焦点とする楕円の範囲内に位置するＰＯＩを経由地候補として検索してもよい。また、経由地候補検索部２０２ｂは、経路探索条件としてＰＯＩのカテゴリが指定されている場合に、当該カテゴリに該当するＰＯＩに絞込み検索を行ってもよい。

また、経路探索部２０２ｃは、ネットワークデータベース２０６ａに記憶されたネットワークデータに基づいて、経路探索を実行する経路探索手段である。例えば、経路探索部２０２ｃは、経路探索条件受信部２０２ａにより受信された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索してもよい（なお、ネットワークデータ等の木構造データにおいて、探索経路は探索木と呼ばれることがある）。出発地から目的地への方向から見れば、出発地から経由地へは順方向であり、目的地から経由地へは逆方向となるので、本実施の形態においては、当該経路探索方法を、「双方向拡散」による経路探索と呼ぶ。なお、経路探索部２０２ｃは、双方向拡散による経路探索に限らず、経路探索条件の出発地から目的地までの探索経路を拡散させて、通常の経路探索を行ってもよい。なお、上述したように、経路探索部２０２ｃは、双方向拡散による経路探索を行う際に、経由地候補検索部２０２ｂにより、拡散中の探索経路上または探索経路付近に存在するＰＯＩを経由地候補として検索させてもよい。

ここで、本実施形態において実行される、経路探索部２０２ｃによる「拡散」について説明する。本実施形態において、「拡散」とは、ダイクストラ法やＡ＊（エースター）探索アルゴリズム等の公知の経路探索手法において、順次到達したノードやリンク等が広がることをいう。例えば、ダイクストラ法においては、基準点（一般的には、出発地に近いノード）から、順次、接続されたリンクを辿って次のノードに到達し、辿ったリンクのリンクコスト（距離や通過所要時間等）を積算し、リンクコストが最小となるように次に辿るリンク群（探索経路）を管理しながら、目的の点（一般的には、目的地に近いノード）まで探索経路を広げていくものであるが、この探索経路を広げることを拡散と呼ぶ。なお、当然、分岐が存在し、一つのノードに３本以上のリンクが接続される場合があるので、探索経路は、通常一本のままではなく、積算リンクコストが同列（同程度）の複数の探索経路が拡散とともに増えていくことになる。なお、上述の説明では、一般的な探索手法として、出発地から目的地までの通常の拡散による経路探索を行う例を挙げて説明したが、本実施形態では、経路探索部２０２ｃは、双方向拡散による経路探索において、出発地（基準点）から複数の経由地候補（目的の点）までの１回の拡散と、目的地から（基準点）から当該複数の経由地候補までの１回の拡散を、それぞれ実行する点に特徴がある。なお、通常は、目的の点は１点であるので、当該１点に到達したときに拡散を終了させるが、経路探索部２０２ｃは、複数の経由地候補の全ての点に到達するまで探索経路を拡張させる。なお、拡散の終了条件は、これに限られず、拡散リンクが反対側の地点（例えば、出発地側からの拡散の場合は目的地、目的地側からの拡散の場合は出発地）に到達したことであってもよく、また、算出されるリンクコストに従って、目的地または出発地に到達してから拡散により、所定分多くのリンクコスト（時間、距離、料金等）が算出されたときであってもよい。これにより、より多くのＰＯＩ等を候補リンクとすることができる。

なお、ダイクストラ法等で経路探索を行う場合、拡散していく探索経路の１本毎にリンクコストを演算して求めていかなければならず、探索経路の数に応じて処理時間が長くなり、サーバ装置２００の処理負荷が大きくなってしまうという問題点がある。そのため、出発地や目的地や経由地候補等の地点周辺では、（細い路地まで詳細な道路網を規定した）下位階層のネットワークデータを用いて探索経路を拡張し、その後、地点間では、（主要な道路網のみを規定した）上位階層のネットワークデータを用いて探索経路を拡張して、経路探索を行ってもよい。特に、本実施の形態において双方向拡散による経路探索を行う場合、経路探索部２０２ｃは、双方向拡散を行う前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させてもよい。

また、経路探索部２０２ｃは、双方向拡散により算出した出発地から経由地までの所要時間と目的地から経由地までの所要時間を加算することにより、出発地から経由地（候補）を経由して目的地に到達するための所要時間を計算することができる。また、経路探索部２０２ｃは、経由地（候補）での滞在時間を考慮して所要時間を算出するようにしてもよい。例えば、経由地（候補）が飲食店の時は所要時間に１時間を加算することなどが考えられる。

また、経路探索部２０２ｃは、双方向探索により算出した出発地から目的地までの経路に対して、別途所要時間の再計算処理を行うようにしてもよい。双方向拡散のうち目的地側から拡散させる場合、各リンクにおける参照すべき渋滞情報の時刻が未知であり、それにより算出される所要時間の精度が低くなる。出発地から目的地までの経路を構成する全ノードに対し、出発地側から順に「出発地から対象ノードまでの所要時間」を再計算することで、各ノードにおける通過時刻が高い精度で求まる（出発時刻に「出発地から対象ノードまでの所要時間」を加算したものが対象ノードの通過時刻となる）。これにより、各リンクにおいて適切な時刻の渋滞情報を参照できるようになり、出発地から目的地までの所要時間および予想到達時刻の精度を高くすることができる。

また、経路探索部２０２ｃは、双方向拡散の目的地側から拡散させる場合に、各リンクの予測通過時刻を他の情報から予測するようにしてもよい。一例として、別途計算される目的地への仮の予測到着時刻から「目的地から拡散対象リンクまでの所要時間」を引くことで、拡散対象リンクの予測通過時刻を決定してもよい。目的地への仮の予測到着時刻の算出方法の一例として、別途出発地から目的地への経由地無しの経路探索を行い、これにより得られた到着時刻を仮の予測到着時刻とすることが考えられる。また、別の例として、出発地から目的地への直線距離を平均走行時速で割ることにより、出発地から目的地までの所要時間を計算し、そこから仮の予測到着時刻を算出することが考えられる。また、経路探索部２０２ｃは、経由地（候補）での滞在時間を考慮して仮の予測到着時刻を算出するようにしてもよい。例えば、経由地候補がすべて飲食店の時は仮の予測到着時刻に１時間を加算することなどが考えられる。

また、探索結果情報生成部２０２ｄは、経路探索部２０２ｃにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する探索結果情報生成手段である。例えば、探索結果情報生成部２０２ｄは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。ここで、探索結果情報生成部２０２ｄは、経路探索部２０２ｃにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、探索結果情報生成部２０２ｄは、両経路の所要時間の比較結果（経由地候補を経由しない場合と比べて増大する所要時間（すなわち、ロスタイム）等）のほか、両経路の距離や料金等の比較結果（差，比，割合等）を示す探索結果情報を生成してもよい。なお、探索結果情報生成部２０２ｄは、これら比較結果を降順や昇順にソート等を行って、決定した表示順序で表示されるように（例えば、ロスタイムが短い順にＰＯＩが表示されるように）探索結果情報を生成してもよい。また、探索結果情報生成部２０２ｄは、候補数が所定数以上の場合に、比較結果に従って上位のものだけ表示されるようにフィルタリング処理を行って、探索結果情報を生成してもよい。また、探索結果情報生成部２０２ｄは、地図データベース２０６ｂに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部２０２ｄは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させてもよい。

また、探索結果情報送信部２０２ｅは、探索結果情報生成部２０２ｄにより生成された探索結果情報を、端末装置１００に送信する探索結果情報送信手段である。

また、渋滞情報取得部２０２ｆは、渋滞情報を取得する渋滞情報取得手段である。例えば、渋滞情報取得部２０２ｆは、定期的（例えば、５分毎等）にネットワーク３００を介して最新のデータを外部機器６００（例えば、警察庁、ＶＩＣＳ（登録商標）などの渋滞情報配信サーバなど）等からダウンロードして渋滞情報データベース２０６ｄに記憶された交通情報をアップデートしてもよい。

［端末装置１００の構成］
また、図１において、端末装置１００は、経路探索条件をサーバ装置２００に送信し、サーバ装置２００から送信される、探索結果情報を受信し、受信した探索結果情報を出力部１１４に出力する等の機能を有する。端末装置１００は、例えば、一般に市販されるデスクトップ型またはノート型のパーソナルコンピュータ等の情報処理装置、携帯電話やＰＨＳやＰＤＡ等の携帯端末装置、および、走行経路案内等を行なうナビゲーション端末等である。ここで、端末装置１００は、インターネットブラウザ等を搭載していてもよく、経路案内アプリケーションや乗換案内アプリケーション等を搭載していてもよい。また、端末装置１００は、リアルタイムに現在位置取得が行えるよう、ＧＰＳ機能やＩＭＥＳ機能等を有する位置取得部１１２を備える。また、端末装置１００は、少なくとも出力部１１４と入力部１１６と制御部１０２を備える。ここで、出力部１１４は、表示案内データ等の表示画面を表示する表示手段（例えば、液晶や有機ＥＬ等から構成されるディスプレイやモニタ等）のほか、サーバ装置２００から受信した探索結果情報を音声として出力する音声出力手段（例えば、スピーカ等）であってもよい。また、入力部１１６としては、例えば、キー入力部、タッチパネル、キーボード、マイク等であってもよい。また、入出力制御インターフェース部１０８は、位置取得部１１２、出力部１１４、および、入力部１１６等の制御を行う。

ここで、位置取得部１１２は、例えば、位置発信装置５００から発信される位置情報信号を受信する位置取得手段であってもよい。ここで、位置発信装置５００は、位置情報信号（ＧＰＳ信号）を発信するＧＰＳ装置であってもよく、また、ＧＰＳ信号と類似した特徴を持つ位置情報信号を用いて屋内測位を可能とするＩＭＥＳ（Ｉｎｄｏｏｒ Ｍｅｓｓａｇｅ Ｓｙｓｔｅｍ）技術を実現するＩＭＥＳ装置であってもよい。なお、ＩＭＥＳ技術は測位衛星システムである準天頂衛星の枠組みから発案されたシステムである。また、位置発信装置５００は、屋外で受信したＧＰＳ信号を屋内で発信するＧＰＳリピータであってもよい。また、位置発信装置５００は、建物（例えば、立体駐車場等）内の各フロアや地下構造物（例えば、トンネル、地下駐車場等）の各所に任意に設置される小型発信装置であってもよい。なお、この小型発信装置には、設置場所に応じた自己位置情報（位置ＩＤ等）が割り振られている。そして、端末装置１００が通信可能範囲に入ると、端末装置１００は、小型発信装置から送信される自己位置情報を位置情報信号として受信する。この際の通信方式は、例えば、ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）タグシステムやＢｌｕｅｔｏｏｔｈ（登録商標）等の各種近距離無線方式や、赤外線通信方式等であってもよい。また、位置発信装置５００は、無線ＬＡＮのアクセスポイントであってもよい。本実施形態において、位置取得部１１２は、無線ＬＡＮ信号等を受信して、アクセスポイントの識別情報を取得してもよい。そして、制御部１０２は、位置取得部１１２にて取得したアクセスポイント固有の識別情報からアクセスポイントの位置を特定して位置情報を取得してもよい。また、本実施形態において、制御部１０２は、位置取得部１１２にて取得された位置情報信号から、緯度、経度、および、高さ情報を含む位置情報を算出してもよい。ここで、位置情報は、緯度および経度により特定される絶対位置の他、基準となる位置からの相対位置を示すものであってもよい。

また、位置取得部１１２は、例えば、位置取得部１１２の加速度センサにて検出した端末装置１００の加速度情報、方位センサにて検出した端末装置１００の進行方向等の方位情報、距離センサにて検出した距離情報、および、地図データに基づいて端末装置１００の利用者の現在位置を示す位置情報を取得してもよい。ここで、方位センサには、端末装置１００の絶対走行方位を検出する地磁気センサおよび端末装置１００の相対走行方位を検出する光ジャイロが使用されてもよい。また、方位センサは、地磁気センサと加速度センサを組み合わせることで方位や傾きに関する情報を取得できる電子コンパスであってもよい。

また、通信制御インターフェース部１０４は、通信回線や電話回線等に接続されるアンテナやルータ等の通信装置（図示せず）に接続されるインターフェースであり、端末装置１００とネットワーク３００との間における通信制御を行う機能を有する。すなわち、通信制御インターフェース部１０４は、サーバ装置２００等と通信回線を介してデータを通信する機能を有している。

また、記憶部１０６は、ＨＤＤやＳＳＤ等の大容量のストレージ手段、および／または、ＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）等を用いて構成される小容量高速メモリ（例えば、キャッシュメモリ）等のストレージ手段であり、各種のデータベースやファイルやテーブルを格納してもよい。ここで、記憶部１０６は、外部機器６００等から受信した地図情報や、サーバ装置２００から受信した探索結果情報などの各種のファイル等を一時的に記憶するものであってもよい。

また、案内データファイル１０６ａは、案内データを記憶する案内データ記憶手段である。案内データファイル１０６ａに記憶される案内データは、案内経路上において出力される音声案内データや表示案内データ等のデータである。ここで、音声案内データは、案内経路上の分岐点等における進行方向に対応付けられた「次の交差点を左に曲がります」や、現在位置が目的地に近づいた場合に対応付けられた「まもなく目的地周辺です」等の音声案内用のデータであってもよく、この音声案内データは、端末装置１００の探索結果情報出力部１０２ｅが、探索結果情報に記憶された経路の情報に基づいて、音声案内等の経路案内を実行する際に用いられてもよい。また、表示案内データは、案内経路上の分岐点等における進行方向に対応付けられたターンバイターン（ＴＢＴ）や、現在位置が選択施設に近づいた旨の案内等の表示案内用のデータであってもよく、この表示案内データは、端末装置１００の探索結果情報出力部１０２ｅが表示案内を実行する際に用いられる。ここで、ＴＢＴとは、右左折等の誘導を画面に表示する矢印ナビゲーションである。これら案内データは、探索結果情報として受信されてもよく、案内データファイル１０６ａに予め記憶されてもよい。端末装置１００の制御部１０２は、定期的に、および／または、制御部１０２による処理に応じて（例えば、制御部１０２においてデータが必要となる契機等）、ネットワーク３００を介して最新の案内データを外部機器６００（例えば、案内データを提供する案内データ提供サーバなど）等からダウンロードして案内データファイル１０６ａに記憶された案内データをアップデートしてもよい。

また、制御部１０２は、ＯＳ等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部１０２は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部１０２は、機能概念的に、現在位置情報取得部１０２ａ、経路探索条件設定部１０２ｂ、経路探索条件送信部１０２ｃ、探索結果情報受信部１０２ｄ、および、探索結果情報出力部１０２ｅを備える。

このうち、現在位置情報取得部１０２ａは、端末装置１００の利用者の現在位置情報を取得する現在位置情報取得手段である。ここで、現在位置情報取得部１０２ａは、端末装置１００の利用者の現在位置情報を所定周期ごと（例えば、１秒ごと等）に取得してもよい。ここで、現在位置情報取得部１０２ａは、定期的に、または、更新毎に、取得した現在位置情報をサーバ装置２００に送信してもよい。また、現在位置情報取得部１０２ａは、位置取得部１１２にて位置発信装置５００から受信した位置情報信号から算出した位置情報を、端末装置１００の利用者の現在位置情報として取得してもよい。更に、位置取得部１１２の方位センサ等にて検出した端末装置１００の進行方向等の方位情報や、位置取得部１１２の加速度センサにて検出した端末装置１００の加速度情報を、端末装置１００の利用者の現在位置情報として取得してもよい。また、現在位置情報取得部１０２ａは、利用者により入力部１１６を介して入力された現在位置についての位置座標等を端末装置１００の利用者の現在位置情報として取得してもよい。ここで、利用者により入力部１１６を介して入力された現在位置は、利用者が現実に存在する位置であってもよく、利用者により任意に選択された仮想の現在位置（一例として、東京にいる利用者により選択された大阪の駅や空港等の任意の地点）であってもよい。具体的には、現在位置情報取得部１０２ａは、入力部１１６を介して利用者に出力部１１４に表示された地図データの表示画面上で指定（例えば、タッチパネル式の表示部での指定操作等）させた座標を端末装置１００の利用者の現在位置情報として取得してもよい。更に、入力部１１６を介して利用者に出力部１１４に表示された地図データの表示画面上で指定させた方位情報を端末装置１００の利用者の現在位置情報として取得してもよい。ここで、現在位置情報取得部１０２ａは、利用者の現在位置情報とともに、当該現在位置情報を取得した日時情報を取得してもよい。

また、経路探索条件設定部１０２ｂは、出発地および目的地を少なくとも含む経路探索条件を設定する経路探索条件設定手段である。ここで、経路探索条件設定部１０２ｂは、入力部１１６を介して、利用者に出発地や目的地等の経路探索条件を入力させるよう制御してもよい。また、経路探索条件は、更に、出発時刻または到着時刻を含んでいてもよい。ここで、出発時刻は、現在時刻であってもよい。また、経路探索条件に、経由地の嗜好や経由時刻を加えてもよく、例えば、経路探索条件設定部１０２ｂは、利用者に入力部１１６を介して、経由地候補として検索されるＰＯＩのカテゴリ等を指定させるよう制御してもよい。また、経路探索条件設定部１０２ｂは、経路探索条件に、現在位置情報取得部１０２ａにより取得された現在位置情報の現在位置を追加してもよく、経路探索条件の目的地として当該現在位置を設定してもよい。

また、探索結果情報受信部１０２ｄは、サーバ装置２００から送信される、探索結果情報を受信する探索結果情報受信手段である。

また、探索結果情報出力部１０２ｅは、探索結果情報受信部１０２ｄにより受信された探索結果情報を、出力部１１４に出力する探索結果情報表示手段である。例えば、探索結果情報出力部１０２ｅは、探索結果情報をモニタ等の出力部１１４に表示させてもよく、探索結果情報に従ってスピーカ等に音声出力してもよい。なお、探索結果情報出力部１０２ｅは、探索結果情報に含まれる経路の情報に従って、案内データファイル１０６ａに記憶された案内データ等を参照して、音声案内等の経路案内を行ってもよい。

以上で、本実施形態における経路探索システムの構成の一例の説明を終える。

［経路探索システムの処理］
次に、このように構成された本実施形態における経路探索システムの基本処理の一例について、以下に図２から図４を参照して詳細に説明する。図２は、第１の実施形態における経路探索システムの基本処理の一例を示すフローチャートである。

図２に示すように、まず、端末装置１００の経路探索条件設定部１０２ｂは、利用者に入力部１１６を介して、少なくとも出発地と目的地を含む経路探索条件を設定させる（ステップＳＡ−１）。ここで、出発地は、現在位置情報取得部１０２ａにより取得される現在位置情報に基づく端末装置１００の利用者の現在位置であってもよく、経路探索条件に、出発地とは別に当該現在位置の条件を加えてもよい。なお、経路探索条件設定部１０２ｂは、経路探索条件として、経由地の嗜好（例えば、経由地候補として検索されるＰＯＩのカテゴリ等）を、利用者に指定させてもよい。

そして、端末装置１００の経路探索条件送信部１０２ｃは、経路探索条件設定部１０２ｂにより設定された経路探索条件を、サーバ装置２００に送信する（ステップＳＡ−２）。

そして、サーバ装置２００の経路探索条件受信部２０２ａは、端末装置１００から送信される、少なくとも出発地と目的地を含む経路探索条件を受信する（ステップＳＡ−３）。

そして、サーバ装置２００の経由地候補検索部２０２ｂは、ＰＯＩデータベース２０６ｃに記憶された地点情報（ＰＯＩ情報等）から、複数の経由地候補を検索する（ステップＳＡ−４）。ここで、経由地候補検索部２０２ｂは、経路探索条件受信部２０２ａにより受信された経路探索条件の出発地や現在位置（所定時間後の予想現在位置でもよい。）や目的地等を含む、所定の形状範囲内に存在するＰＯＩを、ＰＯＩデータベース２０６ｃから検索してもよい。所定の形状範囲の一例として、経由地候補検索部２０２ｂは、出発地および目的地の２点を焦点とする楕円の範囲内に位置するＰＯＩを経由地候補として検索してもよい。また、経由地候補検索部２０２ｂは、経路探索条件としてＰＯＩのカテゴリ等が指定されている場合に、当該指定されたカテゴリ等に該当するＰＯＩに絞込み検索を行ってもよい。

そして、サーバ装置２００の経路探索部２０２ｃは、ネットワークデータベース２０６ａに記憶されたネットワークデータに基づいて、経由地候補検索部２０２ｂにより検索された複数の経由地候補について双方向拡散による経路探索を実行する（ステップＳＡ−５）。具体的には、経路探索部２０２ｃは、経路探索条件受信部２０２ａにより受信された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて、双方向拡散による経路探索を行う。なお、双方向拡散による経路探索以外にも、経路探索部２０２ｃは、出発地から目的地まで探索経路を拡散させる、通常の経路探索を行ってもよい。ここで、図３は、双方向拡散による経路探索結果と通常の経路探索結果とを模式的に示した図である。図３において、Ｓは、出発地を示し、Ｇは、目的地を示し、星印は、経由地候補を示す。また、図中の矢印は、探索結果の経路を表し、実線の矢印は、出発地から目的地までの通常の経路探索による経路（例えば、最短経路）を示し、破線の矢印は、双方向拡散の経路探索による、出発地または目的地から、経由地候補までの経路を示している。

図３に示すように、経由地候補検索部２０２ｂにより３箇所の経由地候補（立ち寄り候補点Ａ〜Ｃ）が検索された場合、経路探索部２０２ｃは、出発地から３箇所の経由地候補まで、探索経路を１回拡散させて、経路探索を行う。すなわち、経路探索部２０２ｃは、探索経路が３箇所全ての経由地候補に到達するまで拡散処理を継続し、出発地から各経由地候補までの経路Ｒ１０〜Ｒ１２の探索を１度の拡散処理で完了する。同様に、経路探索部２０２ｃは、目的地から３箇所の経由地候補まで探索経路を１回拡散させて、目的地から各経由地候補までの経路Ｒ２０〜Ｒ２２を得る。なお、出発地から各経由地候補までの拡散処理と、目的地から各経由地候補までの拡散処理とは、いずれを先に実行してもよく、同時に並列処理を行ってもよい。図３に示すように、双方向拡散による経路探索に加えて通常の経路探索を行ってもよく、経路探索部２０２ｃは、出発地から目的地まで探索経路を拡散させて、経路Ｒ１を取得してもよい。なお、経路探索において計算するリンクコストを所要時間とした場合、図３の各経路に付した時間（分）に示すように、それぞれの最短時間経路を求めることができるが、これに限られず、求めるリンクコストは、距離や料金等であってもよい。

また、図３の吹き出しに記載のように、経路探索部２０２ｃは、双方向拡散の結果探索した、経路探索条件の出発地から経由地候補までの経路、および、目的地から当該経由地候補までの経路に基づいて（具体的には、両者の所要時間を加算して）、予測される当該目的地への到着時刻を算出してもよい。なお、経路探索部２０２ｃは、目的地から当該経由地候補までの経路を逆向きに探索する場合、参照すべき渋滞情報の時刻が未知であるため、そのままでは渋滞を加味した予想到達時刻の算出ができない。そのため、経路探索部２０２ｃは、得られた経路に対して、出発地から目的地までのノードに対して順に通過時刻を求めていくことで目的地への予想到達時刻を再計算するようにしてもよい。すなわち、出発時刻と「出発地から対象ノードまでの経路の所要時間」から対象ノードの通過時刻が算出できるため、渋滞情報データベース２０６ｄから正しい時刻の渋滞情報を取得することができ、その結果精度の高い予想到着時刻を計算することができる。

ここで、経路探索部２０２ｃは、処理時間を短縮するために、ネットワークデータベース２０６ａに記憶された、階層化されたネットワークデータを用いて経路探索を行ってもよい。すなわち、経路探索では、拡散していく探索経路の１本毎にリンクコストを演算して求めていかなければならないため、全ての詳細な道路網まで規定したネットワークデータを用いると、探索経路の数が爆発的に増えて膨大な処理時間がかかるという問題が発生する。そのため、経路探索部２０２ｃは、出発地や目的地や経由地候補等の地点周辺では、下位階層の（細い路地までの詳細な道路網を規定した）ネットワークデータを用いて探索経路を拡張し、地点間では、上位階層の（主要な道路網のみを規定した）ネットワークデータを用いて探索経路を拡張して、経路探索を実行してもよい。特に、双方向拡散による経路探索を実行する際、経路探索部２０２ｃは、双方向拡散を行う前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させてもよい。ここで、図４は、階層化されたネットワークデータを用いて経路探索を行う例を模式的に示した図である。図３と同様に、Ｓは出発地、Ｇは目的地、星印は経由地候補を示す。

図４は、出発地、目的地、および、３箇所の経由地候補の位置関係と、この位置空間において用いるネットワークデータの階層Ｌ１〜Ｌ３の関係を表している。Ｌ１は、比較的下位階層であり、Ｌ３は、比較的上位階層である。図４に示すように、経路探索部２０２ｃは、まず、出発地、目的地、経由地候補のそれぞれから、Ｌ１のネットワークデータを用いて、探索経路を拡散させる。つぎに、経路探索部２０２ｃは、Ｌ１で拡散させた探索経路に続けて、Ｌ２のネットワークデータを用いて、探索経路を拡散させる。そして、以上の下準備を終えると、経路探索部２０２ｃは、到達したリンク（探索経路を構成するリンク群）に「探索対象」のラベルを付しておく。そして、経路探索部２０２ｃは、双方向拡散による経路探索実行時に、主要な道路等のＬ３のネットワークデータに加えて、探索対象のネットワークデータを用いて、探索経路を拡散させる。これにより、特に、経由地候補が、Ｌ３のリンク近傍にない場合であっても、出発地または目的地からの探索経路を、Ｌ１やＬ２の比較的下位の階層のネットワークデータを用いて、各経由地候補まで辿り着かせることができる。換言すれば、経由地候補に接続される道路の階層が低いことにより、出発地または目的地から当該経由地候補までを探索できなくなる可能性を軽減させることができる。その一方で、出発地や経由地候補や目的地の地点周辺以外の地点間では、幹線道路などの主要な道路網のネットワークデータを用いて経路探索を行うので、所要時間や距離等が短い経由地候補を発見することができる。

再び図２に戻り、サーバ装置２００の探索結果情報生成部２０２ｄは、経路探索部２０２ｃにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する（ステップＳＡ−６）。例えば、探索結果情報生成部２０２ｄは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。また、探索結果情報生成部２０２ｄは、地図データベース２０６ｂに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部２０２ｄは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させた探索結果情報を生成してもよい。

ここで、探索結果情報生成部２０２ｄは、経路探索部２０２ｃにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、上述した図３に示したように、探索結果情報生成部２０２ｄは、両経路の所要時間の差、すなわち、経由しない場合と比べて各経由地候補を経由することで増加する所要時間（すなわち、ロスタイム）を、下記の式を用いて算出してもよい。そして、当該ロスタイムを図３のように表示する表示画面を含む探索結果情報を生成してもよい。
（ロスタイム）＝（出発地から経由地候補までの所要時間）＋（目的地から当該経由地候補までの所要時間）−（出発地から目的地までの所要時間）

このほか、探索結果情報生成部２０２ｄは、両経路の距離や料金等の比較結果（差，比，割合等）を示す探索結果情報を生成してもよい。なお、探索結果情報生成部２０２ｄは、これら比較結果を降順や昇順にソート等して、決定した表示順序で一覧表示されるように（例えば、ロスタイムが短い順にＰＯＩが表示されるように）探索結果情報を生成してもよい。なお、探索結果情報生成部２０２ｄは、出発地から目的地までの（経由地候補を経由しない）経路との比較結果に基づいて表示順序を決定することに限らず、出発地から目的地までの経路探索を行うことなく、出発地から各経由地候補を介した目的地までの経路を、経由地候補同士で所要時間や距離や料金等に基づいて、ソート等を行って表示順序を決定してもよい。また、ソートを行うことに限らず、探索結果情報生成部２０２ｄは、候補数が所定数以上の場合に、比較結果に従って上位のものだけ表示されるようにフィルタリング処理を行って、探索結果情報を生成してもよい。

そして、サーバ装置２００の探索結果情報送信部２０２ｅは、探索結果情報生成部２０２ｄにより生成された探索結果情報を端末装置１００に送信する（ステップＳＡ−７）。

そして、端末装置１００の探索結果情報受信部１０２ｄは、サーバ装置２００から送信された探索結果情報を受信する（ステップＳＡ−８）。

そして、端末装置１００の探索結果情報出力部１０２ｅは、探索結果情報受信部１０２ｄにより受信された探索結果情報を、出力部１１４に出力する（ステップＳＡ−９）。ここで、探索結果情報出力部１０２ｅは、探索結果情報に含まれる地図データや経路上に、現在位置情報取得部１０２ａにより更新される現在位置情報を重畳した表示画面を、出力部１１４に表示させてもよい。また、探索結果情報出力部１０２ｅは、現在位置情報取得部１０２ａにより更新される現在位置情報の現在位置が、探索結果情報に含まれる経由地候補の所定範囲内または経由地候補を介する経路への分岐点に近づいた場合に、当該経由地候補があることを音声や表示等により出力してもよい。ここで、利用者により入力部１１６を介して複数の経由地候補の中から一の経由地が選択された場合、探索結果情報出力部１０２ｅは、探索結果情報に基づいて、選択された経由地を経由する経路に従って経路案内を実行してもよい。なお、端末装置１００は、探索結果情報に当該経由地を経由する経路を示す情報が格納されていない場合、経路探索条件送信部１０２ｃにより、当該経路を示す情報の要求（選択された経由地を更に含む経路探索条件等）をサーバ装置２００に送信して、サーバ装置２００から当該経路を示す情報を含む探索結果情報を受信してもよい。その際、サーバ装置２００の経路探索部２０２ｃは、経路探索の精度を上げるため、選択された経由地について再度、経路探索を行ってもよい。すなわち、上述した双方向拡散による経路探索（ＳＡ−５）において上述のように、目的地から経由地候補に向けて本来と逆方向に経路探索を行っていたので、各経由地候補を介した経路について再計算を行っていなかった場合、精度に劣る。そこで、経路探索部２０２ｃは、出発地から選択された経由地を介して目的地に至るまでの探索経路について、出発地から目的地までのノードに対して順に通過時刻を求めていくことで、より精度の高い目的地への予想到達時刻を再計算してもよい。なお、その際、経由地での滞在時間を考慮してもよく、例えば、経由地が飲食店の場合は、所要時間に１時間を加算してもよい。

なお、本実施の形態において、上述したステップＳＡ−１〜ステップＳＡ−９の処理が繰り返されるよう制御してもよい。例えば、端末装置１００の経路探索条件送信部１０２ｃが、現在位置情報取得部１０２ａにより現在位置情報が更新される毎に、経路探索条件設定部１０２ｂにより再設定された現在位置情報を含む経路探索条件をサーバ装置２００に送信することにより、上述したステップＳＡ−１〜ステップＳＡ−９の処理が繰り返されるよう制御してもよい。これにより、現在位置情報の更新に応じて、探索結果情報出力部１０２ｅにより出力される探索結果情報がリアルタイムに更新されることになる。また、サーバ装置２００の渋滞情報取得部２０２ｆが、渋滞情報の更新を検出した場合（外部機器６００等から新たな渋滞情報を受信した場合など）あるいは一定間隔ごとに、既に取得した経路探索条件に基づいて、ステップＳＡ−４〜ステップＳＡ−９の処理を繰り返すよう処理を行ってもよい。

以上が、第１の実施形態における経路探索システムの基本処理の一例である。

［具体化処理］
つづいて、本実施形態における経路探索システムの具体化処理の一例について図５から図１１を参照して説明する。この具体化処理においては、上述した基本処理において特にサーバ装置２００側の処理の詳細について説明する。ここで、図５は、第１の実施形態における経路探索システムの具体化処理の一例を示すフローチャートである。

図５に示すように、端末装置１００は、経路探索条件設定部１０２ｂにより、少なくとも出発地と目的地を含む経路探索条件を設定し、経路探索条件送信部１０２ｃにより、経路探索条件をサーバ装置２００に送信すると、サーバ装置２００の経路探索条件受信部２０２ａは、端末装置１００から送信された経路探索条件を取得する（ステップＳＢ−１）。ここで、経路探索条件は、経由地の検索条件を含んでもよく、例えば、経由地の嗜好（ＰＯＩのカテゴリなど）等であってもよい。ここで、図６は、経路探索条件設定部１０２ｂにより表示される、経由地の検索条件の入力画面の一例を示す図である。なお、この例では、出発地と目的地の経路探索条件が入力されていることを前提としてもよい。

図６に示すように、経路探索条件設定部１０２ｂは、ＰＯＩデータベース２０６ｃからカテゴリ（種別）等の属性に基づいてＰＯＩを検索するための、検索条件を利用者に入力部１１６を介して入力させる入力画面を出力部１１４に表示してもよい。例えば、図６に示すように、入力画面は、利用者が予め設定しておいた利用者の嗜好に合うカテゴリ（この例では、ラーメンやガソリン）の中から選択させるための、Ｍｙジャンル選択ボタンＭＡ−１を含んでもよい。また、ＰＯＩの名称や属性等のＰＯＩ情報を検索するためのキーワードを入力させるための、フリーワード入力欄ＭＡ−２を入力画面に含んでもよい。また、利用者が複数の項目（この例では、評判、ロスタイム、到着時刻）について優先度をＧＵＩ（Ｇｒａｐｈｉｃａｌ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ）形式で入力させるための優先度レーダーチャートＭＡ−３を入力画面に含んでもよい。なお、図６に示すように、到着時刻の項目については、「今すぐ」、「１２：３０頃（３０分毎）」、「○○ＩＣまで」などの選択肢がドロップリストＭＡ−４（またはダイアログ）で選択できるよう入力画面に表示される。また、優先度レーダーチャートＭＡ−３の項目は、図の「一覧」を押下する等により表示される項目一覧の中から選択することが可能である。ここで、図７は、経路探索条件設定部１０２ｂにより表示される経由地（ＰＯＩ）の検索条件（エリア選択条件）の入力画面の一例を示す図である。

図７に示すように、この例では、端末装置１００は、ＰＯＩ検索を行うためのエリア選択画面ＭＢ−１を表示し、利用者にＰＯＩを検索するエリア（各都道府県または周辺）を、入力部１１６を介して選択するよう制御する。なお、この例では、利用者が都道府県名の最初の５０音の行（あ行〜わ行）を選択すると、端末装置１００は、選択された行に対応する都道府県名を表示するユーザーインターフェースを実現している。ここで、図８は、経路探索条件設定部１０２ｂにより表示される経由地（ＰＯＩ）の検索条件（周辺検索条件）の入力画面の一例を示す図である。

図８に示すように、端末装置１００は、現在位置周辺検索ボタンＭＢ−２１とルート途中検索ボタンＭＢ−２２を含む周辺検索選択画面ＭＢ−２を、出力部１１４に表示させてもよい。そして、利用者がルート途中検索ボタンＭＢ−２２をクリック等により押下すると、経路探索条件設定部１０２ｂは、探索される経路周辺でＰＯＩを検索する条件を設定し、一方、利用者が現在位置周辺検索ボタンＭＢ−２１をクリック等により押下すると、経路探索条件設定部１０２ｂは、現在位置周辺でＰＯＩを検索する条件を設定する。なお、検索するＰＯＩのカテゴリ等を更に利用者に選択させるため、端末装置１００は、図６で上述したような経由地の検索条件の入力画面を表示させてもよい。

再び図５に戻り、以上のように経路探索条件が取得されると（ステップＳＢ−１）、サーバ装置２００の経路探索部２０２ｃは、ネットワークデータベース２０６ａに記憶されたネットワークデータに基づいて、経路探索条件受信部２０２ａにより受信された経路探索条件の出発地から目的地までの経路探索を開始する（ステップＳＢ−２）。すなわち、経路探索部２０２ｃは、出発地を基点として目的地に到達するまで探索経路を拡散させる。なお、経路探索部２０２ｃは、後述する双方向拡散処理における目的地側からの拡散処理（ステップＳＢ−４３）に用いるため、探索経路にかかる予想到達時刻を算出してもよい。

そして、サーバ装置２００の経由地候補検索部２０２ｂは、ＰＯＩデータベース２０６ｃからＰＯＩを経由地候補として検索を開始する（ステップＳＢ−３）。例えば、経由地候補検索部２０２ｂは、ステップＳＡ−４で上述したように経路探索条件の出発地や現在位置（所定時間後の予想現在位置でもよい。）や目的地等の、所定の形状範囲内に存在するＰＯＩを、ＰＯＩデータベース２０６ｃから検索してもよい。なお、このように、双方向拡散処理（ステップＳＢ−４）を行う前に、経由地候補を検索することに限られず、当該双方向拡散処理（ステップＳＢ−４）と同時に、当該経由地候補の検索処理（ステップＳＢ−３）を行ってもよい。

すなわち、経由地候補検索部２０２ｂは、後述する双方向拡散による経路探索の処理（ステップＳＢ−４）と同時に、拡散される探索経路に応じて、ＰＯＩデータベース２０６ｃに記憶されたＰＯＩの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するＰＯＩを経由地候補として取得してもよい。より具体的には、経由地候補検索部２０２ｂは、ネットワークデータに基づいて経路探索部２０２ｃの処理により拡散されるリンクごとに、リンクに隣接するＰＯＩをＰＯＩデータベース２０６ｃから検索し、経由地候補に追加する。なお、図４を用いて上述したように階層化されたネットワークデータを用いる場合で経路探索部２０２ｃが比較的上位階層のリンクを用いて拡散を行っている場合であっても、経由地候補検索部２０２ｂは、上位階層リンクに隣接するＰＯＩのみではなく、当該上位階層リンク周辺の下位階層リンクに隣接するＰＯＩをも検索してもよい。すなわち、経由地候補検索部２０２ｂは、ＰＯＩと直接接続されていなくとも、上位階層のネットワークデータと関連付けがなされているＰＯＩであれば、経由地候補に含めてもよい。また、ＰＯＩ検索の際、経由地候補検索部２０２ｂは、経路探索条件に含まれるＰＯＩの検索条件（利用者に指定されたカテゴリ等）に基づいて、取得したＰＯＩを絞込んでもよい。

そして、サーバ装置２００の経路探索部２０２ｃは、双方向拡散による経路探索を実行する（ステップＳＢ−４）。ここで、双方向拡散による経路探索処理の詳細について以下に図９を参照して説明する。図９は、双方向拡散による経路探索処理の一例を示すフローチャートである。

図９に示すように、まず、経路探索部２０２ｃは、ダイクストラ法やＡ＊アルゴリズム等の公知の経路探索手法を用いて、出発地から目的地方向に順方向に、探索経路を拡散させて、順次リンクコストを積算等して確定させる（ステップＳＢ−４１）。

そして、経路探索部２０２ｃは、例えば新たなノードに到達する毎に、全ての複数の経由地候補までリンクコストを確定させたか否かを判定する（ステップＳＢ−４２）。なお、出発地側の拡散の終了条件は、これに限られず、拡散リンクが目的地に到達したことであってもよく、また、算出されるリンクコストに従って、反対側の地点（例えば、出発地側からの拡散の場合は目的地、目的地側からの拡散の場合は出発地）に到達してから拡散により、所定分多くのリンクコスト（時間、距離、料金等）が算出されたときであってもよい。

全ての経由地候補までリンクコストが確定されていない場合（ステップＳＢ−４２，Ｎｏ）、経路探索部２０２ｃは、探索経路の拡散とそれに伴うリンクコストの確定処理（ステップＳＢ−４１）を継続する。

一方、全ての経由地候補までリンクコストが確定されると（ステップＳＢ−４２，Ｙｅｓ）、経路探索部２０２ｃは、今度は目的地から出発地方向に順方向に（先ほどとは逆方向に）、探索経路を拡散させて、順次リンクコストを積算等して確定させる（ステップＳＢ−４３）。ここで、目的地側からの拡散を行う場合、出発地側からの拡散とは異なり、参照すべき渋滞情報の時刻が未知であるため予想到達時刻を算出できないという問題が生じる。そのため、経路探索部２０２ｃは、ステップＳＢ−２において算出した予想到達時刻を用いて、対応する時刻の渋滞情報を渋滞情報データベース２０６ｄから取得することによって予想到達時刻を算出してもよい。すなわち、経路探索部２０２ｃは、ステップＳＢ−２において別途計算された出発地から目的地までの仮の予測到着時刻から、ステップＳＢ−４における出発地から経由地候補を介した目的地までの経路を構成する対象ノードについての「目的地から拡散対象リンクまでの所要時間」を引くことで、拡散対象リンクの予測通過時刻を決定してもよい。目的地への仮の予測到着時刻の算出方法は、これに限られず、経路探索部２０２ｃは、出発地から目的地への直線距離を平均走行時速で割ることにより、出発地から目的地までの所要時間を計算し、そこから仮の予測到着時刻を算出してもよい。なお、経路探索部２０２ｃは、経由地候補での滞在時間を考慮して仮の予測到着時刻を算出するようにしてもよい。例えば、経由地候補がすべて飲食店の時は仮の予測到着時刻に１時間を加算してもよい。

そして、同様に、経路探索部２０２ｃは、全ての複数の経由地候補までリンクコストを確定させたか否かを判定する（ステップＳＢ−４４）。なお、目的地側の拡散の終了条件は、これに限られず、拡散リンクが目的地に到達したときであってもよく、また、算出されるリンクコストに従って、目的地に到達してから拡散により、所定分多くのリンクコスト（時間、距離、料金等）が算出されたときであってもよい。

全ての経由地候補までリンクコストが確定されていなければ（ステップＳＢ−４４，Ｎｏ）、探索経路の拡散とそれに伴うリンクコストの確定処理（ステップＳＢ−４３）を継続する。

そして、双方向とも全ての経由地候補までリンクコストが確定されると（ステップＳＢ−４４，Ｙｅｓ）、経路探索部２０２ｃは、ステップＳＢ−４１で求めた出発地から経由地候補までの経路の所要時間と、ステップＳＢ−４３で求めた目的地から当該経由地候補までの経路の所要時間とを加算する等により、各経由地候補を経由した場合の所要時間を算出する（ステップＳＢ−４５）。

再び図５に戻り、サーバ装置２００の探索結果情報生成部２０２ｄは、ステップＳＢ−４５で算出された各経由地候補を経由した場合の所要時間から、ステップＳＢ−２において算出された出発地から（経由地を経由せず）目的地までの経路の所要時間を、減算することにより、各経由地候補を経由した場合のロスタイムを算出する（ステップＳＢ−５）。

そして、サーバ装置２００の探索結果情報生成部２０２ｄは、ＰＯＩの検索条件（利用者の嗜好等）とのマッチ度順に、複数の経由地候補をソートする（ステップＳＢ−６）。例えば、探索結果情報生成部２０２ｄは、マッチ度に降順に（マッチ度が高い順に）経由地候補を並び替えてもよい。ここで、探索結果情報生成部２０２ｄは、マッチ度等に基づいてソートすることに限らず、経由地候補が所定以上の場合に出力する数を限定するフィルタリング処理を行ってもよい。例えば、探索結果情報生成部２０２ｄは、マッチ度が上位のものから順に所定数の経由地候補を選択し、残りを探索結果情報の生成対象から除外してもよい。なお、探索結果情報生成部２０２ｄは、ＰＯＩ情報に基づいて広告を出稿している店舗のＰＯＩを並び替え上位に配置してもよい。また、探索結果情報生成部２０２ｄは、同乗者のピックアップを支援する等の利用者の希望（検索条件）に合わせて、駅等の特定のカテゴリの順位を高めてもよい。なお、探索結果情報生成部２０２ｄは、渋滞情報や空席や在庫や価格等のリアルタイム情報と連携させてもよい。

そして、サーバ装置２００の探索結果情報生成部２０２ｄは、各経由地候補をＰＯＩの地点情報に基づいて、地図データベース２０６ｂの地図データ上に、重畳表示させた表示画面を含む探索結果情報を生成する（ステップＳＢ−７）。ここで、図１０は、探索結果情報生成部２０２ｄにより生成される表示画面の一例を示す図である。

図１０に示すように、経路探索条件に現在位置情報が含まれる場合、探索結果情報生成部２０２ｄは、当該現在位置情報の現在位置を示す現在地マーク（図中の三角印）を重畳させた地図表示領域ＭＣ−１を含む表示画面を生成してもよい。その際、探索結果情報生成部２０２ｄは、経由地候補の中から現在位置に近い経由地候補を抽出して、当該経由地候補のＰＯＩ情報（この例では、ジャンル：「ラーメン」、名称：「ＫＴ麺」、評価：４つ星）や当該経由地候補を経由した場合の目的地到着時刻「１２：３０着」やロスタイム「＋３分」を示すポップアップ表示領域ＭＣ−２を表示画面に含めてもよい。なお、この例では、端末装置１００が、更新される現在位置情報を含む経路探索条件を定期的に送信しており、現在位置情報の更新に応じてバックグラウンドでステップＳＢ−１〜ＳＢ−７の処理が繰り返し行われ、表示画面が遷移する（現時位置が一つの経由地候補に近づいたらポップアップ表示する）ことを前提としてもよい。また、ポップアップ表示させるタイミングは、現在位置情報の履歴等に基づいて、所定時間走行した後の予想位置等に基づいて判定してもよい。これにより、利用者にポップアップ表示された経由地候補に立ち寄るか否かを判断する時間を与えることができ、利用者は余裕をもって現在走行中の経路を外れることが可能となる。なお、お勧めのＰＯＩに到達するための経路から外れた場合、端末装置１００は、表示したポップアップを非表示にしてもよい。複数の経由地候補を表示させる場合、探索結果情報生成部２０２ｄは、ソートした先頭から強調表示されるように制御してもよく、例えば、経由地候補を示す星印の大きさをソート順に変更してもよい。ここで、図１１は、探索結果情報生成部２０２ｄにより生成される複数の経由地候補を重畳させた表示画面の一例を示す図である。図１１において、Ｓは出発地を示し、Ｇは目的地を示し、地図上の各黒丸印は経由地候補を示す。なお、ＰＯＩの検索条件（利用者の嗜好等）とのマッチ度が黒丸印の大きさで表現されている。また、図中の実線は、ステップＳＢ−２で経路探索された出発地から目的地までの経路を示し、破線は、ステップＳＢ−４で経路探索された、出発地から経由地候補を経由した目的地までの経路を示している。なお、吹き出し内の星印の数は、口コミ等に基づいた評判の高さを示している。

図１１に示すように、ステップＳＢ−７でソートした結果、上位のものは、大きな黒丸印で表し、かつ、吹き出しで、店名や評判や到着時刻（ロスタイム）を表示させてもよい。なお、ソート結果が下位のものは、小さな黒丸印で表される。そして、この表示画面を含む探索結果情報が端末装置１００の出力部１１４に表示され、利用者がタッチパネル等の入力部１１６を介してタッチ操作等により、一つの経由地を選択すると（この例では、店名「ＫＴ麺」のＰＯＩが選択されている。）、その吹き出しが最上位の階層で重畳されるとともに、探索結果情報に格納された当該経由地を経由した経路が表示されるように、探索結果情報生成部２０２ｄは、探索結果情報を生成してもよい。また、吹き出し内の「立ち寄る」ボタンをダブルタッチ等のタッチ操作により押下することにより、経路探索条件設定部１０２ｂは、選択された経由地候補を経由地とした経路探索条件を再設定してもよい。

そして、サーバ装置２００の経路探索部２０２ｃは、経由地候補を経由地として、再度、経路探索を実行する（ステップＳＢ−８）。なお、経由地とする経由地候補は、上記のように端末装置１００から再送された経由地を含む経路探索条件に基づいて設定してもよく、また、複数の経由地候補の全てについて、それぞれを経由地として再探索を行ってもよい。すなわち、上述した双方向拡散による経路探索（ステップＳＢ−４）では、目的地から経由地候補に向けて逆方向に経路探索を行っていたので、渋滞を加味していないか加味するとしても別途算出した予想到達時刻を参照するなど精度に劣る場合があるが、経路探索部２０２ｃは、出発地から選択された経由地までの探索経路、および、当該選択された経由地から目的地までの探索経路をそれぞれ拡散させることによって、出発地から目的地まで順方向に探索経路を拡散させて、渋滞情報データベース２０６ｄに記憶された渋滞情報等を考慮した精度の高い経路や所要時間等を算出してもよい。当該ステップＳＢ−８の処理は、正確な経路や所要時間等を算出するための処理であるので、処理を高速化するために省略してもよい。また、このように当該ステップＳＢ−８もしくはステップＳＢ−４で算出された予想到達時刻や所要時間等は、出力部１１４を介して利用者に通知されることとなる。また、上述のステップＳＢ−７およびステップＳＢ−８による表示画面や経路探索結果を含む探索結果情報は、端末装置１００に送信され出力されるが、上述のステップＳＡ−７〜ＳＡ−９の処理と同様であるので説明を省略した。また、上述したステップＳＢ−１〜ステップＳＢ−８の処理を、定期的に、または、検索条件や現在位置等の更新に応じて、繰り返し実行させてもよい。特に、図６に示した入力画面を介して利用者により再度、検索条件が入力された場合（例えば、利用者のカテゴリ等に対する優先度が変更された場合）、サーバ装置２００は、ステップＳＢ−６〜ステップＳＢ−８の処理のみを繰り返し実行してもよい。

以上が、第１の実施形態における経路探索システムの具体化処理の一例である。これにより、目的地の宿までの間で立ち寄る観光地を探したり、高速ＩＣまでの間でロスタイムなく入れる飲食店を探したり、利用履歴やジャンル指定や広告出稿に応じて、おすすめ立ち寄り地点を自動ポップ表示させる等のさまざまな需要に応えることができる。

［第２の実施形態］
続いて、本発明の第２の実施形態（経路探索装置４００（スタンドアローン型））について、図１２および図１３を参照して以下に説明する。ここで、図１２は、第２の実施形態における経路探索装置４００の構成の一例を示すブロック図であり、該構成のうち本発明に関係する部分のみを概念的に示している。

なお、第２の実施形態においては、全ての機能を経路探索装置４００に集約し、交通網を規定するネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて経路を探索し、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する。このように、第２の実施形態は、経路探索装置４００がスタンドアローン型に構成され単独で処理を行う点が第１の実施形態と異なる。

［経路探索装置４００（スタンドアローン型）の構成］
まず、第２の実施形態における経路探索装置４００（スタンドアローン型）の構成の一例について、図１２を参照して以下に説明する。

図１２に示すように、本発明の第２の実施形態の経路探索装置４００は、位置取得部４１２と出力部４１４と入力部４１６と制御部４０２と記憶部４０６とを少なくとも備える。これら経路探索装置４００の各部は任意の通信路を介して通信可能に接続されている。例えば、経路探索装置４００は、一般に市販されるデスクトップ型またはノート型のパーソナルコンピュータ等の情報処理装置、携帯電話やＰＨＳやＰＤＡ等の携帯端末装置、および、走行経路案内等を行なうＰＮＤ（Ｐｏｒｔａｂｌｅ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ）等のナビゲーション端末等である。

図１２において、入出力制御インターフェース部４０８、通信制御インターフェース部４０４、位置取得部４１２、出力部４１４、および、入力部４１６、並びに、ネットワーク３００、位置発信装置５００、および、外部機器６００の各機能は、第１の実施形態と同様であるため説明を省略する。また、記憶部４０６の各部（ネットワークデータベース４０６ａ、地図データベース４０６ｂ、ＰＯＩデータベース４０６ｃ、および、渋滞情報データベース４０６ｄ等）についても、サーバ装置２００ではなく経路探索装置４００に備えられている点を除き、各機能が第１の実施形態と同様であるため説明を省略する。なお、記憶部４０６は、更に、第１の実施形態における案内データファイル１０６ａに記憶された案内データを記憶してもよい。

また、制御部４０２の各部（経路探索条件設定部４０２ａ〜現在位置情報取得部４０２ｇ等）について、本実施形態の経路探索装置４００がスタンドアローン型であり、制御部４０２が各送受信部を備えていない点を除き、各機能は第１の実施形態の経路探索システムと基本的に同様である。

図１２において、制御部４０２は、ＯＳ等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部４０２は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部４０２は、機能概念的に、経路探索条件設定部４０２ａ、経由地候補検索部４０２ｂ、経路探索部４０２ｃ、探索結果情報生成部４０２ｄ、探索結果情報出力部４０２ｅ、渋滞情報取得部４０２ｆ、および、現在位置情報取得部４０２ｇを備える。これらの機能は、第１の実施形態における、経路探索条件設定部１０２ｂ、経由地候補検索部２０２ｂ、経路探索部２０２ｃ、探索結果情報生成部２０２ｄ、探索結果情報出力部１０２ｅ、渋滞情報取得部２０２ｆ、および、現在位置情報取得部１０２ａの機能と同様であるため説明を省略する。

以上で、第２の実施形態における経路探索装置４００の構成の一例の説明を終える。

［経路探索装置４００（スタンドアローン型）の処理］
次に、このように構成された第２の実施形態における経路探索装置４００の処理の一例について、以下に図１３を参照して詳細に説明する。ここで、図１３は、第２の実施形態における経路探索装置４００の処理の一例を示すフローチャートである。

図１３に示すように、まず、経路探索条件設定部４０２ａは、利用者に入力部４１６を介して、少なくとも出発地と目的地を含む経路探索条件を設定させる（ステップＳＣ−１）。ここで、出発地は、現在位置情報取得部４０２ｇにより取得される現在位置情報に基づく経路探索装置４００の利用者の現在位置であってもよく、経路探索条件に、出発地とは別に当該現在位置の条件を加えてもよい。なお、経路探索条件設定部４０２ａは、経路探索条件として、経由地の嗜好（例えば、経由地候補として検索されるＰＯＩのカテゴリ等）を、利用者に指定させてもよい。

そして、経由地候補検索部４０２ｂは、ＰＯＩデータベース４０６ｃに記憶された地点情報（ＰＯＩ情報等）から、複数の経由地候補を検索する（ステップＳＣ−２）。ここで、経由地候補検索部４０２ｂは、経路探索条件設定部４０２ａにより設定された経路探索条件の出発地や現在位置（所定時間後の予想現在位置でもよい。）や目的地等を含む、所定の形状範囲内に存在するＰＯＩを、ＰＯＩデータベース４０６ｃから検索してもよい。所定の形状範囲の一例として、経由地候補検索部４０２ｂは、出発地および目的地の２点を焦点とする楕円の範囲内に位置するＰＯＩを経由地候補として検索してもよい。また、経由地候補検索部４０２ｂは、経路探索条件としてＰＯＩのカテゴリ等が指定されている場合に、当該指定されたカテゴリ等に該当するＰＯＩに絞込み検索を行ってもよい。また、経由地候補検索部４０２ｂは、経路探索部４０２ｃにより以下に実行される双方向拡散より前に、経路探索部４０２ｃにより出発地から目的地まで探索経路を拡散させると同時に、拡散される当該出発地から当該目的地までの探索経路に基づいて、ＰＯＩデータベース４０６ｃから複数のＰＯＩを、複数の経由地候補として検索してもよい。すなわち、経路探索部４０２ｃにより出発地から目的地までの探索経路が拡散される際に、経由地候補検索部４０２ｂは、ＰＯＩデータベース４０６ｃに記憶されたＰＯＩの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するＰＯＩを経由地候補として取得してもよい。

そして、経路探索部４０２ｃは、ネットワークデータベース４０６ａに記憶されたネットワークデータに基づいて、経由地候補検索部４０２ｂにより検索された複数の経由地候補について双方向拡散による経路探索を実行する（ステップＳＣ−３）。具体的には、経路探索部４０２ｃは、経路探索条件設定部４０２ａにより設定された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ１回ずつ拡散させて、双方向拡散による経路探索を行う。このほか、双方向拡散による経路探索の詳細は、第１の実施の形態と同様である。例えば、経路探索部４０２ｃは、処理時間を短縮するために、ネットワークデータベース４０６ａに記憶された、階層化されたネットワークデータを用いて経路探索を行ってもよい。なお、ステップＳＣ−３で上述したように、双方向拡散による経路探索以外にも、経路探索部４０２ｃは、出発地から目的地まで探索経路を拡散させる、通常の経路探索を行ってもよい。

そして、探索結果情報生成部４０２ｄは、経路探索部４０２ｃにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する（ステップＳＣ−４）。例えば、探索結果情報生成部４０２ｄは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。また、探索結果情報生成部４０２ｄは、地図データベース４０６ｂに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部４０２ｄは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させた探索結果情報を生成してもよい。また、探索結果情報生成部４０２ｄは、経路探索部４０２ｃにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、探索結果情報生成部４０２ｄは、両経路の時間や距離や料金等の比較結果（差，比，割合等）を示す探索結果情報を生成してもよい。なお、探索結果情報生成部４０２ｄは、これら比較結果を降順や昇順にソート等して、決定した表示順序で一覧表示されるように（例えば、ロスタイムが短い順にＰＯＩが表示されるように）探索結果情報を生成してもよい。なお、探索結果情報生成部４０２ｄは、出発地から目的地までの（経由地候補を経由しない）経路との比較結果に基づいて表示順序を決定することに限らず、出発地から目的地までの経路探索を行うことなく、出発地から各経由地候補を介した目的地までの経路を、経由地候補同士で所要時間や距離や料金等に基づいて、表示順序を決定してもよい。

そして、探索結果情報出力部４０２ｅは、探索結果情報生成部４０２ｄにより生成された探索結果情報を、出力部４１４に出力する（ステップＳＣ−５）。ここで、探索結果情報出力部４０２ｅは、探索結果情報に応じた地図データや経路上に、現在位置情報取得部４０２ｇにより更新される現在位置情報を重畳して、出力部４１４に表示させてもよい。また、探索結果情報出力部４０２ｅは、現在位置情報取得部４０２ｇにより更新される現在位置情報の現在位置が、探索結果情報に含まれる経由地候補の所定範囲内または経由地候補を介する経路への分岐点に近づいた場合に、当該経由地候補があることを音声や表示等により出力してもよい。ここで、利用者により入力部４１６を介して複数の経由地候補の中から一の経由地が選択された場合、探索結果情報出力部４０２ｅは、探索結果情報に基づいて、選択された経由地を経由する経路に従って経路案内を実行してもよい。なお、経路探索部４０２ｃは、経路探索の精度を上げるため、選択された経由地について再度、経路探索を行ってもよい。

以上が、第２の実施形態における経路探索装置４００による処理の一例である。なお、本実施の形態において、上述したステップＳＣ−１〜ステップＳＣ−５の処理が繰り返されるよう制御してもよい。例えば、現在位置情報取得部４０２ｇにより現在位置情報が更新される毎に、経路探索条件設定部４０２ａにより再設定された現在位置情報を含む経路探索条件を設定することにより、上述したステップＳＣ−１〜ステップＳＣ−５の処理が繰り返されるよう制御してもよい。これにより、現在位置情報の更新に応じて、探索結果情報出力部４０２ｅにより出力される探索結果情報がリアルタイムに更新されることになる。このほか、経由地候補（ＰＯＩ）の検索条件（利用者により指定されたカテゴリ）が経路探索条件に追加された場合等に上述の処理を繰り返して、経由地候補の絞込みを行ってもよい。また、渋滞情報取得部４０２ｆが新たな渋滞情報を取得した場合や一定期間毎に、ステップＳＣ−２〜ステップＳＣ−５の処理を繰り返すよう処理を行ってもよい。

以上で、第２の実施形態における経路探索装置４００の処理の説明を終える。

［他の実施の形態］
さて、これまで本発明の実施の形態について説明したが、本発明は、上述した実施の形態以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施の形態にて実施されてよいものである。

例えば、経路探索装置４００がスタンドアローンの形態で処理を行う場合を一例に説明したが、経路探索装置４００は、クライアント端末からの要求に応じて処理を行い、その処理結果を当該クライアント端末に返却するようにしてもよい。

また、実施の形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。

このほか、上記文献中や図面中で示した処理手順、制御手順、具体的名称、各処理の登録データや検索条件等のパラメータを含む情報、画面例、データベース構成については、特記する場合を除いて任意に変更することができる。

また、端末装置１００、サーバ装置２００、および、経路探索装置４００に関して、図示の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。

例えば、端末装置１００、サーバ装置２００、および、経路探索装置４００の各装置が備える処理機能、特に制御部１０２，２０２，４０２にて行われる各処理機能については、その全部または任意の一部を、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）および当該ＣＰＵにて解釈実行されるプログラムにて実現してもよく、また、ワイヤードロジックによるハードウェアとして実現してもよい。尚、プログラムは、後述する記録媒体に記録されており、必要に応じて端末装置１００、サーバ装置２００、および、経路探索装置４００に機械的に読み取られる。すなわち、ＲＯＭまたはＨＤＤなどの記憶部１０６，２０６，４０６などには、ＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）として協働してＣＰＵに命令を与え、各種処理を行うためのコンピュータプログラムが記録されている。このコンピュータプログラムは、ＲＡＭにロードされることによって実行され、ＣＰＵと協働して制御部を構成する。

また、このコンピュータプログラムは、端末装置１００、サーバ装置２００、および、経路探索装置４００に対して任意のネットワーク３００を介して接続されたアプリケーションプログラムサーバに記憶されていてもよく、必要に応じてその全部または一部をダウンロードすることも可能である。

また、本発明に係るプログラムを、コンピュータ読み取り可能な記録媒体に格納してもよく、また、プログラム製品として構成することもできる。ここで、この「記録媒体」とは、メモリーカード、ＵＳＢメモリ、ＳＤカード、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ、および、Ｂｌｕ−ｒａｙ Ｄｉｓｃ等の任意の「可搬用の物理媒体」を含むものとする。

また、「プログラム」とは、任意の言語や記述方法にて記述されたデータ処理方法であり、ソースコードやバイナリコード等の形式を問わない。なお、「プログラム」は必ずしも単一的に構成されるものに限られず、複数のモジュールやライブラリとして分散構成されるものや、ＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）に代表される別個のプログラムと協働してその機能を達成するものをも含む。なお、実施の形態に示した各装置において記録媒体を読み取るための具体的な構成、読み取り手順、あるいは、読み取り後のインストール手順等については、周知の構成や手順を用いることができる。

記憶部１０６，２０６，４０６に格納される各種のデータベース等（案内データファイル１０６ａ、および、ネットワークデータベース２０６ａ，４０６ａ〜渋滞情報データベース２０６ｄ，４０６ｄ）は、ＲＡＭ、ＲＯＭ等のメモリ装置、ハードディスク等の固定ディスク装置、フレキシブルディスク、および、光ディスク等のストレージ手段であり、各種処理やウェブサイト提供に用いる各種のプログラム、テーブル、データベース、および、ウェブページ用ファイル等を格納する。

また、サーバ装置２００は、既知のパーソナルコンピュータ、ワークステーション等の情報処理装置として構成してもよく、また、該情報処理装置に任意の周辺装置を接続して構成してもよい。また、サーバ装置２００は、該情報処理装置に本発明の方法を実現させるソフトウェア（プログラム、データ等を含む）を実装することにより実現してもよい。

更に、装置の分散・統合の具体的形態は図示するものに限られず、その全部または一部を、各種の付加等に応じて、または、機能負荷に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。すなわち、上述した実施形態を任意に組み合わせて実施してもよく、実施形態を選択的に実施してもよい。

以上詳述に説明したように、本発明によれば、適切な経由地を効率よく探索することができる、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラム、並びに、記録媒体を提供することができる。

１００ 端末装置
１０２ 制御部
１０２ａ 現在位置情報取得部
１０２ｂ 経路探索条件設定部
１０２ｃ 経路探索条件送信部
１０２ｄ 探索結果情報受信部
１０２ｅ 探索結果情報出力部
１０４ 通信制御インターフェース部
１０６ 記憶部
１０６ａ 案内データファイル
１０８ 入出力制御インターフェース部
１１２ 位置取得部
１１４ 出力部
１１６ 入力部
２００ サーバ装置
２０２ 制御部
２０２ａ 経路探索条件受信部
２０２ｂ 経由地候補検索部
２０２ｃ 経路探索部
２０２ｄ 探索結果情報生成部
２０２ｅ 探索結果情報送信部
２０２ｆ 渋滞情報取得部
２０４ 通信制御インターフェース部
２０６ 記憶部
２０６ａ ネットワークデータベース
２０６ｂ 地図データベース
２０６ｃ ＰＯＩデータベース
２０６ｄ 渋滞情報データベース
３００ ネットワーク
４００ 経路探索装置
４０２ 制御部
４０２ａ 経路探索条件設定部
４０２ｂ 経由地候補検索部
４０２ｃ 経路探索部
４０２ｄ 探索結果情報生成部
４０２ｅ 探索結果情報出力部
４０２ｆ 渋滞情報取得部
４０２ｇ 現在位置情報取得部
４０４ 通信制御インターフェース部
４０６ 記憶部
４０６ａ ネットワークデータベース
４０６ｂ 地図データベース
４０６ｃ ＰＯＩデータベース
４０６ｄ 渋滞情報データベース
４０８ 入出力制御インターフェース部
４１２ 位置取得部
４１４ 出力部
４１６ 入力部
５００ 位置発信装置
６００ 外部機器

Claims (11)

1. 出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、上記目的地から当該複数の経由地候補までの探索経路を、それぞれ探索する経路探索手段と、
   上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、
   を備え、
   上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、
   上記探索結果情報生成手段は、上記更に探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする、経路探索システム。
2. 請求項１に記載の経路探索システムにおいて、
   地点に関する地点情報から、上記複数の経由地候補を探索する経由地候補探索手段、を更に備え、
   上記経路探索手段は、上記経由地候補探索手段により探索された上記複数の経由地候補について、上記経路探索条件の上記出発地から当該複数の経由地候補までの上記探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの上記探索経路を、それぞれ１回ずつ拡散させることを特徴とする、経路探索システム。
3. 請求項２に記載の経路探索システムにおいて、
   上記経由地候補探索手段は、上記経路探索手段により上記出発地からの上記探索経路および上記目的地からの上記探索経路が拡散される際に、当該拡散される上記探索経路付近の上記経由地候補を上記地点情報から探索することを特徴とする、経路探索システム。
4. 請求項１または２に記載の経路探索システムにおいて、
   上記経路探索手段は、上記出発地から上記複数の経由地候補までの上記探索経路および上記目的地から当該複数の経由地候補までの上記探索経路を拡散させる前に、上記複数の経由地候補から、詳細な交通網を規定するデータに基づいて上記探索経路を拡散させることを特徴とする、経路探索システム。
5. 請求項１乃至４のいずれか一つに記載の経路探索システムにおいて、
   移動体の現在位置を示す現在位置情報を取得する現在位置情報取得手段、を更に備え、 上記経路探索手段は、上記現在位置情報取得手段により取得された上記現在位置情報の上記現在位置を、上記経路探索条件の上記出発地として経路探索を行うことを特徴とする、経路探索システム。
6. 請求項１乃至５のいずれか一つに記載の経路探索システムにおいて、
   時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得する渋滞情報取得手段、を更に備え、
   上記経路探索手段は、探索した上記出発地から上記経由地候補までの上記経路および上記目的地から当該経由地候補までの上記経路に基づいて当該目的地への予想到達時刻を算出し、上記渋滞情報に基づいて上記予想到達時刻を修正することを特徴とする、経路探索システム。
7. 請求項１乃至６のいずれか一つに記載の経路探索システムにおいて、
   上記出発地および上記目的地を少なくとも含む上記経路探索条件を設定する経路探索条件設定手段と、
   上記探索結果情報生成手段により生成された上記探索結果情報を出力する探索結果出力手段と、を更に備えたことを特徴とする、経路探索システム。
8. 出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、上記目的地から当該複数の経由地候補までの探索経路を、それぞれ探索する経路探索ステップと、
   上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、
   を含み、
   上記経路探索ステップでは、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、
   上記探索結果情報生成ステップでは、上記更に探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする、経路探索方法。
9. コンピュータを、
   出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、上記目的地から当該複数の経由地候補までの探索経路を、それぞれ探索する経路探索手段、
   上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段、
   として機能させ、
   上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、
   上記探索結果情報生成手段は、上記更に探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする、プログラム。
10. 出力部を少なくとも備えた端末装置に通信可能に接続された、制御部を少なくとも備えたサーバ装置に実行させるためのプログラムであって、
    上記制御部を、
    上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、
    上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、上記目的地から当該複数の経由地候補までの探索経路を、それぞれ探索する経路探索手段と、
    上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、
    上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信手段と、
    として機能させ、
    上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、
    上記探索結果情報生成手段は、上記更に探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とするプログラム。
11. サーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置に実行させるためのプログラムであって、
    上記制御部を、
    出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信手段、
    上記サーバ装置から送信される、上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、上記目的地から当該複数の経由地候補までの探索経路がそれぞれ探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信手段、
    上記探索結果情報受信手段にて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段、
    として機能させ、
    上記探索結果情報は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路が拡散されて経路が更に探索され、当該更に探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含むことを特徴とする、プログラム。

Images