(57)【要約】【課題】従来、高速かつ正確なルートの提案が困難であった。【解決手段】地点を識別する地点識別子と地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部と、地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、３以上の地点のうちの２つの地点間の距離を取得し、３以上の距離を用いて、３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定部と、巡回順序情報を経路探索エンジンに与え、３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得部と、経路取得部が取得した経路情報を出力する経路出力部とを具備するルート提案装置により、高速かつ正確なルートの提案ができる。【選択図】図２
2018072150.tif 000002
【特許請求の範囲】
【請求項１】
地点を識別する地点識別子と当該地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部と、
前記地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定部と、
前記巡回順序情報を経路探索エンジンに与え、前記３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得部と、
前記経路取得部が取得した経路情報を出力する経路出力部とを具備するルート提案装置。
【請求項２】
前記地点情報格納部に格納されている３以上の地点情報から、予め決められた条件を満たす３以上の地点情報を選択する訪問地点決定部をさらに具備し、
前記巡回順序決定部は、
前記訪問地点決定部が選択した３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の３以上の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得する請求項１記載のルート提案装置。
【請求項３】
前経路取得部は、
前記巡回順序情報を、外部の経路探索エンジンに送信し、前記３以上の地点を巡回順序に従った順序で経由する経路情報を前記外部の経路探索エンジンから受信する請求項１または請求項２記載のルート提案装置。
【請求項４】
前記巡回順序決定部が取得した巡回順路情報が満たすべき１以上の制約条件が格納される制約条件格納部と、
前記巡回順序決定部が取得した巡回順路情報が前記１以上の制約条件を満たすか否かを判断するルート妥当性判断部と、
前記巡回順序情報が前記１以上の制約条件を満たすと前記ルート妥当性判断部が判断するまで、前記巡回順序決定部に対して、先に取得した巡回順路情報と異なる巡回順路情報を取得するように指示する、または前記訪問地点決定部に先に選択した３以上の地点情報の組と異なる３以上の地点情報の組を選択するように指示する制御部とをさらに具備する請求項１から請求項３いずれか一項に記載のルート提案装置。
【請求項５】
前記地点情報は、地点の１以上の属性値を有し、
前記制約条件は、前記１以上の属性値を用いた条件である請求項４記載のルート提案装置。
【請求項６】
前記地点の１以上の属性値は、当該地点に対応付けられた時間を示す時間情報を含み、
前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の時間情報を用いた時間に関する時間条件ある請求項５記載のルート提案装置。
【請求項７】
前記地点の１以上の属性値は、当該地点に対応付けられた費用を示す費用情報を含み、
前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の費用情報を用いた費用に関する費用条件ある請求項５記載のルート提案装置。
【請求項８】
前記地点の１以上の属性値は、当該地点に対応付けられた満足度を示す満足度情報を含み、
前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の満足度情報を用いた満足度に関する満足度条件ある請求項５記載のルート提案装置。
【請求項９】
前記地点情報は、地点の２以上の属性値を有し、
前記制約条件は、前記２以上の属性値を用いて算出されたスコアを用いた条件である請求項５記載のルート提案装置。
【請求項１０】
記録媒体は、
地点を識別する地点識別子と当該地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部を具備し、
巡回順序決定部、経路取得部、および経路出力部により実現されるルート提案方法であって、
前記巡回順序決定部が、前記地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定ステップと、
前記経路取得部が、前記巡回順序情報を経路探索エンジンに与え、前記３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得ステップと、
前記経路出力部が、前記経路取得ステップで取得された経路情報を出力する経路出力ステップとを具備するルート提案方法。
【請求項１１】
コンピュータがアクセス可能な記録媒体は、
地点を識別する地点識別子と当該地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部を具備し、
コンピュータを、
前記地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定部と、
前記巡回順序情報を経路探索エンジンに与え、前記３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得部と、
前記経路取得部が取得した経路情報を出力する経路出力部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の地点の訪問順序を決定し、その経路を示す経路情報を出力するルート提案装置等に関するものである。
【背景技術】
【０００２】
従来、利用者の所望する条件を満たすような経由地を経由し、利用者の所望する条件を満たすようなドライブコースを作成し、経路案内を行うナビゲーション装置を提供することを目的とするナビゲーション装置があった（特許文献１参照）。
【０００３】
かかるナビゲーション装置は、名所を経由する経路を作成するナビゲーション装置であり、利用者より所定の選択条件を取得する条件取得手段と、少なくとも前記条件取得手段で取得した前記選択条件を満たすような名所を、地点の詳細情報を記憶するデータベースから経由地として選出する選出手段と、前記選出手段によって選出した経由地を前記選択条件に基づいて経由する経路を作成する作成手段とを備えることを特徴とするナビゲーション装置である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１７２０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術においては、高速なルートの提案が困難であった。さらに具体的には、従来技術のナビゲーション装置において、詳細な経路情報を保持しており、かかる詳細な経路情報を用いて、経路探索をナビゲーション装置内で行っていた。そのため、従来技術においては、高速なルートの提案が困難であった。
【課題を解決するための手段】
【０００６】
本第一の発明のルート提案装置は、地点を識別する地点識別子と地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部と、地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、３以上の地点のうちの２つの地点間の距離を取得し、３以上の距離を用いて、３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定部と、巡回順序情報を経路探索エンジンに与え、３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得部と、経路取得部が取得した経路情報を出力する経路出力部とを具備するルート提案装置である。
【０００７】
かかる構成により、高速かつ正確なルートの提案ができる。
【０００８】
また、本第二の発明のルート提案装置は、第一の発明に対して、地点情報格納部に格納されている３以上の地点情報から、予め決められた条件を満たす３以上の地点情報を選択する訪問地点決定部をさらに具備し、巡回順序決定部は、訪問地点決定部が選択した３以上の各地点情報に含まれる位置情報を用いて、３以上の地点のうちの２つの地点間の３以上の距離を取得し、３以上の距離を用いて、３以上の地点の巡回順序に関する情報である巡回順路情報を取得するルート提案装置である。
【０００９】
かかる構成により、高速かつ正確な訪問地点およびルートの提案ができる。
【００１０】
また、本第三の発明のルート提案装置は、第一または第二の発明に対して、前経路取得部は、巡回順序情報を、外部の経路探索エンジンに送信し、３以上の地点を巡回順序に従った順序で経由する経路情報を外部の経路探索エンジンから受信するルート提案装置である。
【００１１】
かかる構成により、外部の経路探索エンジンの資源を使用して、高速かつ正確なルートの提案ができる。
【００１２】
また、本第四の発明のルート提案装置は、第一から第三いずれか１つの発明に対して、巡回順序決定部が取得した巡回順路情報が満たすべき１以上の制約条件が格納される制約条件格納部と、巡回順序決定部が取得した巡回順路情報が１以上の制約条件を満たすか否かを判断するルート妥当性判断部と、巡回順序情報が１以上の制約条件を満たすとルート妥当性判断部が判断するまで、巡回順序決定部に対して、先に取得した巡回順路情報と異なる巡回順路情報を取得するように指示する、または訪問地点決定部に先に選択した３以上の地点情報の組と異なる３以上の地点情報の組を選択するように指示する制御部とをさらに具備するルート提案装置である。
【００１３】
かかる構成により、高速、正確、かつ制約を満たすルートの提案ができる。
【００１４】
また、本第五の発明のルート提案装置は、第四の発明に対して、地点情報は、地点の１以上の属性値を有し、制約条件は、１以上の属性値を用いた条件である、ルート提案装置である。
【００１５】
かかる構成により、高速、正確、かつ制約を満たすルートの提案ができる。
【００１６】
また、本第六の発明のルート提案装置は、第五の発明に対して、地点の１以上の属性値は、当該地点に対応付けられた時間を示す時間情報を含み、制約条件は、巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の時間情報を用いた時間に関する時間条件である、ルート提案装置である。
【００１７】
かかる構成により、高速、正確、かつ時間の制約を満たすルートの提案ができる。
【００１８】
また、本第七の発明のルート提案装置は、第五の発明に対して、地点の１以上の属性値は、当該地点に対応付けられた費用を示す費用情報を含み、制約条件は、巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の費用情報を用いた費用に関する費用条件である、ルート提案装置である。
【００１９】
かかる構成により、高速、正確、かつ費用の制約を満たすルートの提案ができる。
【００２０】
また、本第八の発明のルート提案装置は、第五の発明に対して、地点の１以上の属性値は、当該地点に対応付けられた満足度を示す満足度情報を含み、制約条件は、巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の満足度情報を用いた満足度に関する満足度条件である、ルート提案装置である。
【００２１】
かかる構成により、高速、正確、かつ満足度の制約を満たすルートの提案ができる。
【００２２】
また、本第九の発明のルート提案装置は、第五の発明に対して、地点情報は、地点の２以上の属性値を有し、制約条件は、２以上の属性値を用いて算出されたスコアを用いた条件である、ルート提案装置である。
【００２３】
かかる構成により、高速、正確、かつ複数の属性値に対する制約を満たすルートの提案ができる。
【発明の効果】
【００２４】
本発明によるルート提案装置によれば、高速かつ正確なルートの提案ができる。
【図面の簡単な説明】
【００２５】
【図１】実施の形態１におけるルート提案システムＡの概念図
【図２】同ルート提案システムＡのブロック図
【図３】同ルート提案装置１の動作例について説明するフローチャート
【図４】同訪問地点決定処理の例について説明するフローチャート
【図５】同巡回順路決定処理の例について説明するフローチャート
【図６】同ルート妥当性判断処理の例について説明するフローチャート
【図７】同地点情報管理表を示す図
【図８】同ジャンル・目的対応表を示す図
【図９】同観光のコースを提案してもらうための情報の入力画面を示す図
【図１０】同出力例を示す図
【図１１】同コンピュータシステムの概観図
【図１２】同コンピュータシステムのブロック図
【発明を実施するための形態】
【００２６】
以下、ルート提案装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
【００２７】
（実施の形態１）
【００２８】
本実施の形態において、３以上の各地点の位置情報を用いて取得した地点間の直線距離を用いて、３以上の地点の訪問順序を決定し、当該訪問順序に従って経路を取得し、経路を出力するルート提案システムについて説明する。
【００２９】
また、本実施の形態において、さらに訪問地点も決定し、当該訪問地点の各位置情報を用いて取得した地点間の直線距離を用いて、訪問地点の訪問順序を決定し、当該訪問順序に従って経路を取得し、経路を出力するルート提案システムについて説明する。
【００３０】
また、本実施の形態において、外部の経路探索エンジンを用いて、経路情報を取得し、出力するルート提案システムについて説明する。
【００３１】
また、本実施の形態において、１以上の制約を保持しており、当該制約に合致するか否かのルート妥当性判断を行い、制約に適合するルートを提案するルート提案システムについて説明する。なお、制約は、ルートの巡回時間に関する時間制約、費用に関する費用制約、地点の満足度に関する満足度制約等がある。
【００３２】
図１は、本実施の形態におけるルート提案システムＡの概念図である。ルート提案システムＡは、１または２以上のルート提案装置１、および１または２以上の経路探索エンジン２を備える。なお、ルート提案システムＡは、さらに端末装置３を具備しても良い。かかる場合、ユーザは、端末装置３を操作し、ルート提案装置１と端末装置３とが通信を行い、経路が端末装置３に表示される。また、ルート提案システムＡが端末装置３を有さない場合、ユーザは、ルート提案装置１を操作し、ルート提案装置１に経路が表示される。また、ルート提案装置１と経路探索エンジン２と端末装置３とは、例えば、インターネットやＬＡＮ等のネットワークにより、相互に通信可能である。
【００３３】
ルート提案装置１は、例えば、いわゆるパーソナルコンピュータ、スマートフォン、タブレット端末、サーバ装置（いわゆるクラウドサーバ、ＡＳＰサーバ等）等であり、その種類は問わない。
【００３４】
また、経路探索エンジン２は、ルート提案装置１からの指示により経路探索を行い、探索結果である経路情報をルート提案装置１に送信する装置である。経路探索エンジン２は、公知技術であるので詳細な説明は省略する。また、経路探索エンジン２における経路探索のアルゴリズムは、ダイクストラ法、Ａ＊等、問わない。
【００３５】
図２は、本実施の形態におけるルート提案システムＡのブロック図である。
【００３６】
ルート提案装置１は、格納部１０、受付部１１、処理部１２、および出力部１３を備える。格納部１０は、地点情報格納部１０１、および制約条件格納部１０２を備える。処理部１２は、訪問地点決定部１２１、巡回順序決定部１２２、ルート妥当性判断部１２３、制御部１２４、および経路取得部１２５を備える。出力部１３は、経路出力部１３１を備える。
【００３７】
ルート提案装置１を構成する格納部１０は、各種の情報を格納し得る。各種の情報とは、後述する地点情報、制約条件等である。
【００３８】
地点情報格納部１０１は、３以上の地点情報が格納される。地点情報は、地点識別子と位置情報とを含む。地点識別子は、地点を識別する情報である。地点識別子は、例えば、地点名、地点のＩＤ等である。位置情報は、地点の位置を示す情報である。位置情報は、通常、（緯度，経度）である。ただし、位置情報は、地図データ上の相対的な位置（（ｘ，ｙ）座標値など）等でも良い。また、地点情報は、位置情報を地点識別子として有しても良い。かかる場合、地点情報は、地点識別子と位置情報のいずれかを有する。かかる場合も、地点情報は、地点識別子と位置情報とを含む、と言っても良い。地点情報は、地点の１または２以上の属性値を有しても良い。属性値は、例えば、時間情報、費用情報、満足度情報、ジャンル、雨でも利用可能な否かを示すフラグ等である。時間情報は、地点に対応付けられた時間を示す情報である。時間情報は、例えば、地点の利用のために必要な時間を示す情報である。費用情報は、地点に対応付けられた費用を示す情報である。費用情報は、例えば、地点の利用のために必要な費用を示す情報である。満足度情報は、地点に対応付けられた満足度を示す情報である。満足度情報は、地点に対する満足度を示す情報である。ジャンルとは、地点の種類であり、例えば、レストラン、遊園地、コンビニ、寺院、神社などである。また、地点情報が有する属性値は、地点識別子に対応付いている属性値でも良い。例えば、地点情報はジャンルを有し、かつジャンルと対応付けられた時間情報が図示しない記憶手段で管理されている場合、地点情報は時間情報を有する、と考えても良い。
【００３９】
制約条件格納部１０２は、１以上の制約条件が格納される。制約条件は、巡回順序決定部１２２が取得した巡回順路情報が満たすべき条件である。制約条件は、経路情報が満たすべき条件と考えても良い。また、制約条件は、訪問地点決定部１２１が取得する地点識別子群が満たすべき条件と考えても良い。かかる条件も、巡回順路情報が満たすべき条件と言える。また、巡回順路情報が満たすべき条件とは、巡回順路情報に対応する３以上の地点情報が満たすべき条件と考えても良い。制約条件は、例えば、巡回順路情報に対応する３以上の地点情報に対応する地点間の距離の和が満たすべき条件でも良い。制約条件は、例えば、時間条件、費用条件、満足度条件、スコア条件などである。
【００４０】
時間条件とは、巡回順序決定部１２２が取得した巡回順路情報に対応する３以上の各地点の時間情報を用いた時間に関する時間条件である。時間条件は、３以上の各地点の時間情報のみではなく、経路の移動時間をも含む時間の条件であっても良い。時間条件は、例えば、「３時間以内」「１８時まで」等である。時間条件は、時間間隔の制約でも良いし、最終の時刻に関する制約でも良い。
【００４１】
費用条件とは、巡回順序決定部１２２が取得した巡回順路情報に対応する３以上の各地点の費用情報を用いた費用に関する条件である。時間条件は、３以上の各地点の費用情報のみではなく、経路の移動のための費用（例えば、移動距離に応じた燃料代、交通費等）をも含む費用の条件であっても良い。費用条件は、例えば、「１万円以内」「１０００円〜２０００円」等である。
【００４２】
満足度条件とは、巡回順序決定部１２２が取得した巡回順路情報に対応する３以上の各地点の満足度情報を用いた満足度に関する条件である。満足度条件は、例えば、巡回順路情報に対応する３以上の各地点が満たすべき満足度情報の条件（例えば、「満足度情報＞＝４」）であっても良いし、巡回順路情報に対応する３以上の各地点に対応する満足度情報の合計がすべき条件（例えば、「満足度情報の合計＞＝２０」）であっても良い。
【００４３】
スコア条件とは、２以上の属性値を用いて算出されたスコアを用いた条件である。スコア条件は、例えば、観光時間と移動時間とを用いたスコアの条件である。スコア条件は、例えば、「観光時間／移動時間＞＝１．０」等の、観光時間と移動時間とのバランスを考慮した条件でも良い。
【００４４】
受付部１１は、各種の情報や指示等を受け付ける。各種の情報や指示等とは、例えば、ユーザが訪問を希望する３以上の地点識別子、目的地点を識別する目的地点識別子、出発地点を識別する出発地点識別子、ルート提案装置１の動作の開始の指示である動作指示等である。動作指示は、例えば、出発地を識別する地点識別子である出発地識別子、目的地を識別する地点識別子である目的地識別子（到着地識別子と言っても良い）を有する。また、動作指示は、例えば、訪問するすべての地点の地点識別子である地点識別子群を有しても良い。さらに、動作指示は、例えば、出発地識別子および目的地識別子を含む地点識別子群を有しても良い。かかる場合、訪問地点決定部１２１は、１以上の中継地点の地点識別子からなる地点識別子群を取得しても良いし、１以上の中継地点の地点識別子と出発地識別子および目的地識別子からなる地点識別子群を取得しても良い。
【００４５】
処理部１２は、各種の処理を行う。各種の処理とは、例えば、訪問地点決定部１２１、巡回順序決定部１２２、ルート妥当性判断部１２３、制御部１２４、経路取得部１２５が行う処理である。
【００４６】
訪問地点決定部１２１は、地点情報格納部１０１に格納されている３以上の地点情報から、予め決められた条件を満たす３以上の地点情報を選択する。地点情報の選択とは、例えば、地点情報を構成する一部の情報（例えば、地点識別子）の取得でも良いし、地点情報へのポインタの取得等でも良い。
【００４７】
予め決められた条件とは、例えば、出発地点と目的地点との間にある地点であることである。出発地点と目的地点との間にある地点とは、例えば、出発地点の位置情報と目的地点の位置情報とを用いて取得される位置情報と対になる地点識別子である。出発地点の位置情報と目的地点の位置情報とを用いて取得される位置情報とは、通常、出発地点の位置情報が示す点、または目的地点の位置情報が示す点と、予め決められた関係を有するほど近い点の位置情報である。出発地点の位置情報と目的地点の位置情報とを用いて取得される位置情報とは、例えば、出発地点の位置情報が示す点と目的地点の位置情報が示す点とを対角線上の頂点とする矩形の領域内の位置情報である。出発地点の位置情報と目的地点の位置情報とを用いて取得される位置情報とは、例えば、出発地点の位置情報が示す点と目的地点の位置情報が示す点とを結ぶ線上および当該線への距離が閾値以内の距離の位置情報である。
【００４８】
また、予め決められた条件とは、例えば、予め決められた属性値（例えば、ジャンル）と対になる地点識別子で識別される地点であることである。
【００４９】
なお、訪問地点決定部１２１が訪問地点の候補を選択するアルゴリズムは問わない。訪問地点決定部１２１は、例えば、出発地点の位置情報と目的地点の位置情報とを用いて、出発地点または目的地点に予め決められた条件を満たすほど距離が近い地点であり、かつ予め決められた属性値と対になる地点識別子で識別される地点を、訪問地点として選択しても良い。
【００５０】
巡回順序情報が１以上の制約条件を満たすとルート妥当性判断部１２３が判断するまで、訪問地点決定部１２１は、先に選択した３以上の地点情報の組と異なる３以上の地点情報の組を選択する。先に選択した３以上の地点情報の組とは、当該ルート提案の動作指示を受け付けてから、既に選択した３以上の地点情報の組であり、制約条件を満たさなかった３以上の地点情報の組である。また、訪問地点決定部１２１は、選択した３以上の各地点情報に含まれる３以上の地点識別子を、少なくとも一時的に格納部１０に蓄積することは好適である。また、巡回順序情報が１以上の制約条件を満たさないとルート妥当性判断部１２３が判断した場合、例えば、直前に格納部１０に蓄積した３以上の地点識別子のうちの一つを他の地点識別子に置き換え、新しい３以上の地点情報の組を取得することは好適である。
【００５１】
巡回順序決定部１２２は、地点情報格納部１０１に格納されている３以上の各地点情報に含まれる位置情報を用いて、３以上の地点のうちの２つの地点間の距離を取得し、３以上の距離を用いて、３以上の地点の巡回順序に関する情報である巡回順路情報を取得する。
【００５２】
巡回順序決定部１２２は、訪問地点決定部１２１が選択した３以上の各地点情報に含まれる位置情報を用いて、３以上の地点のうちの２つの地点間の３以上の距離を取得し、３以上の距離を用いて、３以上の地点の巡回順序に関する情報である巡回順路情報を取得する。
【００５３】
巡回順序情報が１以上の制約条件を満たすとルート妥当性判断部１２３が判断するまで、巡回順序決定部１２２は、先に取得した巡回順路情報と異なる巡回順路情報を取得する。先に取得した巡回順路情報とは、当該ルート提案の動作指示を受け付けてから、既に取得した巡回順路情報であり、制約条件を満たさなかった巡回順路情報である。なお、巡回順序決定部１２２が取得する巡回順路情報は、ランダムでも良いし、何らかの条件に応じていても良い。何らかの条件とは、例えば、３以上の地点のうちの２つの地点間の３以上の距離である。また、何らかの条件とは、例えば、３以上の各地点に対応する属性値（例えば、時間など）に関する条件（例えば、時間が短い順など）である。
【００５４】
巡回順序決定部１２２が取得する地点間の距離は、通常、直線距離である。また、巡回順序決定部１２２が取得する地点間の距離は、３以上の距離である。巡回順序決定部１２２が取得する地点間の距離は、３以上の各地点間の距離である。
【００５５】
巡回順序決定部１２２が３以上の距離を用いて取得する巡回順路情報は、例えば、当該３以上の距離の合計が予め決められた条件を満たすほど少なくなる巡回順路を特定する情報である。予め決められた条件を満たすほど少なくなる巡回順路は、例えば、合計の距離が最短である巡回順路である。
【００５６】
巡回順路情報は、例えば、３以上の地点識別子の並びの情報、３以上の位置情報の並びの情報である。巡回順路情報は、３以上の地点の巡回順序を特定する情報と言っても良い。巡回順序情報は、例えば、「Ａ地点→Ｂ地点→Ｃ地点→Ｄ地点」、「Ａ地点，Ｂ地点，Ｃ地点，Ｄ地点」「（緯度１，経度１）→（緯度２，経度２）→（緯度３，経度３）」、「（緯度１，経度１）（緯度２，経度２→（緯度３，経度３）」等である。巡回順路情報等の情報のデータ構造は問わないことは言うまでもない。
【００５７】
ルート妥当性判断部１２３は、巡回順序決定部１２２が取得した巡回順路情報が１以上の制約条件を満たすか否かを判断する。なお、１以上の制約条件は、制約条件格納部１０２に格納されている条件である。
【００５８】
制御部１２４は、巡回順序情報が１以上の制約条件を満たすとルート妥当性判断部１２３が判断するまで、巡回順序決定部１２２に対して、先に取得した巡回順路情報と異なる巡回順路情報を取得するように指示する。または、制御部１２４は、巡回順序情報が１以上の制約条件を満たすとルート妥当性判断部１２３が判断するまで、訪問地点決定部１２１に先に選択した３以上の地点情報の組と異なる３以上の地点情報の組を選択するように指示しても良い。
【００５９】
ここで、巡回順序決定部１２２に対して指示することは、例えば、巡回順序決定部１２２に動作するように指示することである。指示することは、例えば、巡回順序決定部１２２に対応する関数またはメソッドを呼び出すことである。なお、かかる指示により、結果として、巡回順序決定部１２２が動作すれば良い。
【００６０】
また、訪問地点決定部１２１に対して指示することは、例えば、訪問地点決定部１２１に動作するように指示することである。指示することは、例えば、訪問地点決定部１２１に対応する関数またはメソッドを呼び出すことである。なお、かかる指示により、結果として、訪問地点決定部１２１が動作すれば良い。
【００６１】
経路取得部１２５は、巡回順序情報を経路探索エンジン２に与え、３以上の地点を巡回順序に従った順序で経由する経路情報を取得する。経路取得部１２５は、例えば、経路情報を含む地図情報をも取得しても良い。かかる地図情報は、通常、経路探索エンジン２から受信されたものである。ただし、かかる地図情報は、格納部１０に格納されていても良い。
【００６２】
経路取得部１２５は、例えば、巡回順序情報を経路探索エンジン２に送信する。そして、経路取得部１２５は、例えば、３以上の地点を巡回順序に従った順序で経由する経路情報を、経路探索エンジン２から受信する。経路情報は、経路を示す情報である。経路情報は、例えば、ノードとリンクの集合である。ここで、経路探索エンジン２は、通常、外部の装置である。ただし、経路探索エンジン２は、ルート提案装置１が保持していても良い。
【００６３】
出力部１３は、各種の情報を出力する。各種の情報とは、例えば、経路情報、地図情報、動作指示等の入力画面等である。ここで、出力とは、ディスプレイへの表示、プロジェクターを用いた投影、プリンタでの印字、音出力、外部の装置（例えば、図示しない端末装置）への送信、記録媒体への蓄積、他の処理装置や他のプログラムなどへの処理結果の引渡しなどを含む概念である。
【００６４】
経路出力部１３１は、経路取得部１２５が取得した経路情報を出力する。経路情報の出力態様は問わない。経路出力部１３１は、経路情報を地図上に経路を出力することは好適である。経路出力部１３１は、地図情報をも出力することは好適である。
【００６５】
格納部１０、地点情報格納部１０１、および制約条件格納部１０２は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。
【００６６】
格納部１０等に情報が記憶される過程は問わない。例えば、記録媒体を介して情報が格納部１０等で記憶されるようになってもよく、通信回線等を介して送信された情報が格納部１０等で記憶されるようになってもよく、あるいは、入力デバイスを介して入力された情報が格納部１０で記憶されるようになってもよい。
【００６７】
処理部１２、訪問地点決定部１２１、巡回順序決定部１２２、ルート妥当性判断部１２３、制御部１２４、および経路取得部１２５は、通常、ＭＰＵやメモリ等から実現され得る。処理部１２等の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００６８】
経路取得部１２５は、無線または有線の通信手段により実現されても良い。
【００６９】
出力部１３、および経路出力部１３１は、ディスプレイやスピーカー等の出力デバイスを含むと考えても含まないと考えても良い。出力部１３等は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。
【００７０】
次に、ルート提案システムＡを構成するルート提案装置１の動作例について、図３のフローチャートを用いて説明する。
【００７１】
（ステップＳ３０１）受付部１１は、動作指示を受け付けたか否かを判断する。動作指示を受け付けた場合はステップＳ３０２に行き、動作指示を受け付けない場合はステップＳ３０１に行く。
【００７２】
（ステップＳ３０２）処理部１２は、動作指示が地点識別子群を有するか否かを判断する。地点識別子群を有する場合はステップＳ３０４に行き、地点識別子群を有しない場合はステップＳ３０３に行く。
【００７３】
（ステップＳ３０３）訪問地点決定部１２１は、地点情報格納部１０１に格納されている３以上の地点情報から、予め決められた条件を満たす３以上の地点情報を選択する。かかる訪問地点決定処理について、図４のフローチャートを用いて説明する。
【００７４】
（ステップＳ３０４）巡回順序決定部１２２は、動作指示に含まれる地点情報群、またはステップＳ３０３で取得された地点情報を用いて、巡回順路情報を取得する。かかる巡回順路決定処理について、図５のフローチャートを用いて説明する。
【００７５】
（ステップＳ３０５）ルート妥当性判断部１２３は、制約条件格納部１０２に制約条件が存在するか否かを判断する。制約条件が存在する場合はステップＳ３０６に行き、制約条件が存在しない場合はステップＳ３０８に行く。
【００７６】
（ステップＳ３０６）ルート妥当性判断部１２３は、ステップＳ３０４で取得された巡回順路情報に対して、ルート妥当性の判断処理を行う。かかるルート妥当性判断処理について、図６のフローチャートを用いて説明する。
【００７７】
（ステップＳ３０７）制御部１２４は、ステップＳ３０６における判断結果が制約条件を満たすとの判断結果であったか否かを判断する。制御部１２４は、制約条件を満たすとの判断結果であった場合は、処理をステップＳ３０８に進め、制約条件を満たさないとの判断結果であった場合は、処理をステップＳ３０２に戻す。
【００７８】
（ステップＳ３０８）経路取得部１２５は、ステップＳ３０４で、最終的に取得された巡回順路情報を経路探索エンジン２に渡す。
【００７９】
（ステップＳ３０９）経路取得部１２５は、経路情報を経路探索エンジン２から取得したか否かを判断する。経路情報を取得した場合はステップＳ３１０に行き、経路情報を取得しなかった場合はステップＳ３０９に戻る。
【００８０】
（ステップＳ３１０）経路出力部１３１は、ステップＳ３０９で取得された経路情報を出力する。ステップＳ３０１に戻る。
【００８１】
なお、図３のフローチャートにおいて、動作指示が地点識別子群を有する場合でも、訪問地点決定部１２１は、かかる地点識別子群が有する地点識別子の地点を含み、かつ当該地点識別子群には無い地点識別子の地点をも選択しても良い。
【００８２】
また、図３のフローチャートにおいて、電源オフや処理終了の割り込みにより処理は終了する。
【００８３】
次に、ステップＳ３０３の訪問地点決定処理の例について、図４のフローチャートを用いて説明する。
【００８４】
（ステップＳ４０１）訪問地点決定部１２１は、出発地点の位置情報と目的地点の位置情報とを取得する。
【００８５】
（ステップＳ４０２）訪問地点決定部１２１は、出発地点および目的地点の２つのいずれか、または両方の地点に対して、予め決められた位置関係にある地点の地点識別子を地点情報格納部１０１から取得する。なお、訪問地点決定部１２１は、通常、２以上の地点識別子を取得する。また、訪問地点決定部１２１は、通常、出発地点および目的地点も含めて、３以上の地点の地点識別子を取得する。
【００８６】
また、訪問地点決定部１２１は、図４の処理のループ（Ｓ４０２〜Ｓ４０４）において、２度目以上のＳ４０２の処理の場合、その前までに取得した地点識別子の組である地点識別子群と完全同一の地点識別子群は取得しない。
【００８７】
（ステップＳ４０３）訪問地点決定部１２１は、各地点識別子と対になる１以上の属性値を地点情報格納部１０１から取得する。なお、各地点識別子とは、ステップＳ４０２で取得した地点識別子を含む。また、各地点識別子とは、出発地点および目的地点の地点識別子を含んでも良い。
【００８８】
（ステップＳ４０４）訪問地点決定部１２１は、ステップＳ４０３で取得された各地点識別子と対になる１以上の属性値が、予め決められた条件を満たすか否かを判断する。予め決められた条件を満たす場合は上位処理にリターンし、予め決められた条件を満たさない場合はＳ４０２に戻る。
【００８９】
次に、ステップＳ３０４の巡回順路決定処理の例について、図５のフローチャートを用いて説明する。
【００９０】
（ステップＳ５０１）巡回順序決定部１２２は、カウンタｉに１を代入する。
【００９１】
（ステップＳ５０２）巡回順序決定部１２２は、ｉ番目の巡回路の組み合わせ（ｉ番目の巡回順路情報の候補、と言っても良い。）が存在するか否かを判断する。ｉ番目の巡回路の組み合わせが存在する場合はステップＳ５０３に行き、ｉ番目の巡回路の組み合わせが存在しない場合はステップＳ５０６に行く。なお、例えば、出発地点と目的地点が決まっており、それらの間の地点がｎ個存在する場合、ｎＰｎ（ｎ×（ｎ−１）×・・・×２×１）通りの巡回路の組み合わせが存在することとなる。また、例えば、出発地点と目的地点が決まっておらず、地点がｎ個存在する場合、ｎＰｎ通りの巡回路の組み合わせが存在することとなる。
【００９２】
（ステップＳ５０３）巡回順序決定部１２２は、ｉ番目の巡回路の組み合わせに含まれる地点の位置情報を地点情報格納部１０１から取得する。そして、巡回順序決定部１２２は、当該各地点の位置情報を用いて、ｉ番目の巡回路に従って、各２地点間の直線距離を取得する。
【００９３】
（ステップＳ５０４）巡回順序決定部１２２は、ステップＳ５０３で取得された２以上の直線距離の合計を算出する。そして、ｉ番目の巡回路の組み合わせ（例えば、ｉ番目の巡回路に対応する、地点識別子の順序を有する集合）に対応付けて、直線距離の合計を図示しないバッファに一時蓄積する。
【００９４】
（ステップＳ５０５）巡回順序決定部１２２は、カウンタｉを１、インクリメントする。ステップＳ５０２に戻る。
【００９５】
（ステップＳ５０６）巡回順序決定部１２２は、直線距離の合計を用いて、一つの巡回路に対応する巡回順路情報を取得する。例えば、ステップＳ３０６で制約条件を満たすと判断されるまで、巡回順序決定部１２２は、直線距離の合計が短い順に、巡回順路情報を取得する。
【００９６】
次に、ステップＳ３０６のルート妥当性判断処理の例について、図６のフローチャートを用いて説明する。
【００９７】
（ステップＳ６０１）ルート妥当性判断部１２３は、カウンタｉに１を代入する。
【００９８】
（ステップＳ６０２）ルート妥当性判断部１２３は、ｉ番目の制約条件が制約条件格納部１０２に存在するか否かを判断する。ｉ番目の制約条件が存在する場合はステップＳ６０３に行き、ｉ番目の制約条件が存在しない場合はステップＳ６０７に行く。
【００９９】
（ステップＳ６０３）ルート妥当性判断部１２３は、ｉ番目の制約条件に対応する属性値であり、巡回順路情報に含まれるすべての地点識別子と対になる属性値を、地点情報格納部１０１から取得する。
【０１００】
（ステップＳ６０４）ルート妥当性判断部１２３は、ステップＳ６０３で取得した各地点の属性値を用いて、巡回順路情報がｉ番目の制約条件を満たすか否かを判断する。ｉ番目の制約条件を満たす場合はステップＳ６０５に行き、ｉ番目の制約条件を満たさない場合はステップＳ６０６に行く。
【０１０１】
（ステップＳ６０５）ルート妥当性判断部１２３は、カウンタｉを１、インクリメントする。ステップＳ６０２に戻る。
【０１０２】
（ステップＳ６０６）ルート妥当性判断部１２３は、変数「判断結果」に判断結果「満たさない」を代入する。上位処理にリターンする。
【０１０３】
（ステップＳ６０７）ルート妥当性判断部１２３は、変数「判断結果」に判断結果「満たす」を代入する。上位処理にリターンする。
【０１０４】
以下、本実施の形態におけるルート提案システムＡの具体的な動作について説明する。
【０１０５】
今、地点情報格納部１０１は、図７に示す地点情報管理表を格納している。地点情報管理表は、「ＩＤ」「地点識別子」「位置情報」「属性値群」を有するレコードを１以上格納している。「属性値群」は、ここでは「時間情報」「費用情報」「満足度情報」「ジャンル」を有する。「ＩＤ」はレコードを識別する情報である。
【０１０６】
また、格納部１０は、図８に示すジャンル・目的対応表を格納している。ジャンル・目的対応表は、ジャンルと目的との対応を示す情報である。
【０１０７】
かかる状況において、以下の２つの具体例について説明する。具体例１は、ユーザが地点情報群を与えない場合である。具体例２は、ユーザが地点情報群を与える場合である。
（具体例１）
【０１０８】
まず、ユーザは、ルート提案装置１を操作し、図９に示す画面を出力した、とする。図９は、観光のコースを提案してもらうための情報の入力画面である。そして、ユーザは、図９の画面に対して、出発地「Ａ地点」、到着地「Ａ地点」、出発時刻「２０１６年０６月０１日００時００分」、観光時間「２時間」を入力し（９０１、９０２、９０３、９０４参照）、「ルート検索」ボタン９０５を押下した、とする。
【０１０９】
次に、受付部１１は、９０１〜９０４で入力された情報を有する動作指示を受け付ける。つまり、動作指示は、出発地識別子「Ａ地点」、到着地識別子「Ａ地点」、出発時刻「２０１６年０６月０１日００時００分」、制約条件「２時間以内」を含む。そして、受付部１１は、制約条件「２時間以内」を制約条件格納部１０２に一時蓄積した、とする。
【０１１０】
次に、訪問地点決定部１２１は、出発地識別子「Ａ地点」、到着地識別子「Ａ地点」を用いて、訪問地点決定処理を行う。つまり、訪問地点決定部１２１は、「Ａ地点」の位置情報（ｘ１，ｙ１）を取得する。次に、訪問地点決定部１２１は、「Ａ地点」の位置情報（ｘ１，ｙ１）に対して、予め決められた位置関係（ここでは、位置情報（ｘ１，ｙ１）からの距離が閾値以内）にある地点の地点識別子であり、目的「観光」に対応する地点の地点識別子を取得する。
【０１１１】
つまり、訪問地点決定部１２１は、図８から目的「観光」に対応するジャンル「寺院，公園，神社，・・・」を取得する。そして、訪問地点決定部１２１は、位置情報（ｘ１，ｙ１）からの距離が閾値以内であり、ジャンル「寺院」または「公園」または「神社」等を属性値に有する地点識別子であり、出発地識別子「Ａ地点」および到着地識別子「Ａ地点」を除く地点識別子「Ｂ地点，Ｃ地点，Ｇ地点，Ｈ地点」を図７に示す地点情報管理表から取得する。そして、訪問地点決定部１２１は、かかる地点識別子群を図示しないバッファに一時蓄積する。
【０１１２】
次に、巡回順序決定部１２２は、出発地識別子「Ａ地点」、中継地点識別子「Ｂ地点，Ｃ地点，Ｇ地点，Ｈ地点」、到着地識別子「Ａ地点」を用いて、以下のような巡回順路決定処理を行う。つまり、巡回順序決定部１２２は、「Ａ地点」を出発し、中継地点識別子「Ｂ地点，Ｃ地点，Ｇ地点，Ｈ地点」をいずれかの順序で回り、到着地識別子「Ａ地点」に到着する各巡回路の組み合わせに対して、各地点の位置情報を用いて、直線距離の合計を算出する。なお、各地点の位置情報が与えられており、各地点の直線距離、直線距離の合計を算出する処理は公知技術であるので、詳細な説明は省略する。ここで、巡回順序決定部１２２は、直線距離の合計が最短の巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｈ地点→Ｇ地点→Ａ地点」を取得した、とする。
【０１１３】
次に、ルート妥当性判断部１２３は、制約条件格納部１０２に制約条件が存在する、と判断する。そして、ルート妥当性判断部１２３は、以下のようにルート妥当性判断処理を行う。つまり、ルート妥当性判断部１２３は、各地点識別子「Ａ地点，Ｂ地点，Ｃ地点，Ｈ地点，Ｇ地点」に対応する時間情報（３０分，１０分，３０分，１００分，３０分）を、地点情報管理表から取得する。そして、ルート妥当性判断部１２３は、かかる時間情報の合計「２００分」を取得する。なお、ルート妥当性判断部１２３は、各地点の直線距離を用いて、移動時間の概算（例えば、２０分）を取得し、時間「２２０分」を算出しても良い。次に、ルート妥当性判断部１２３は、取得した時間「２００分」または「２２０分」が、制約条件「２時間以内」を満たさない、と判断する。そして、ルート妥当性判断部１２３は、変数「判断結果」に判断結果「満たさない」を代入する。
【０１１４】
次に、制御部１２４は、訪問地点決定部１２１に、新しい地点識別子群を取得するように指示をする。なお、かかる指示には、制約条件を満たさなかった属性値に関する情報（例えば、「２２０分―２時間＝１００分  の超過」を示す情報、または時間情報であることを示す情報等）が含まれていることは好適である。
【０１１５】
そして、訪問地点決定部１２１は、先に取得した地点識別子群「Ｂ地点，Ｃ地点，Ｇ地点，Ｈ地点」から、制約条件を満たさなかった属性値に関する情報を用いて、「Ｈ地点」を除き、新しい地点識別子群「Ｂ地点，Ｃ地点，Ｇ地点」を取得した、とする。そして、訪問地点決定部１２１は、かかる地点識別子群を図示しないバッファに一時蓄積する。
【０１１６】
次に、巡回順序決定部１２２は、出発地識別子「Ａ地点」、中継地点識別子「Ｂ地点，Ｃ地点，Ｇ地点」、到着地識別子「Ａ地点」を用いて、直線距離の合計が最短の巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｇ地点→Ａ地点」を取得した、とする。
【０１１７】
次に、ルート妥当性判断部１２３は、制約条件格納部１０２に制約条件が存在する、と判断する。そして、ルート妥当性判断部１２３は、以下のようにルート妥当性判断処理を行う。つまり、ルート妥当性判断部１２３は、各地点識別子「Ａ地点，Ｂ地点，Ｃ地点，Ｇ地点」に対応する時間情報（３０分，１０分，３０分，３０分）を、地点情報管理表から取得する。そして、訪問地点決定部１２１は、かかる時間情報の合計「１００分」を取得する。なお、ルート妥当性判断部１２３は、各地点の直線距離を用いて、移動時間の概算（例えば、２０分）を取得し、時間「１２０分」を算出しても良い。次に、ルート妥当性判断部１２３は、取得した時間「１００分」または「１２０分」が、制約条件「２時間以内」を満たす、と判断する。そして、ルート妥当性判断部１２３は、変数「判断結果」に判断結果「満たす」を代入する。
【０１１８】
次に、経路取得部１２５は、巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｇ地点→Ａ地点」を経路探索エンジン２に送信する。なお、格納部１０には、経路探索エンジン２と通信するための情報（例えば、経路探索エンジン２のＩＰアドレス、ＵＲＬ等）が格納されている、とする。
【０１１９】
次に、経路探索エンジン２は、巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｇ地点→Ａ地点」を受信する。そして、経路探索エンジン２は、巡回順序情報が示す各地点間の経路探索を行い、経路情報を取得する。次に、経路探索エンジン２は、取得した経路情報を、ルート提案装置１に送信する。なお、ここで、経路探索エンジン２は、取得した経路情報を含む領域の地図情報も、経路情報とともにルート提案装置１に送信する、とする。
【０１２０】
次に、ルート提案装置１の経路取得部１２５は、経路情報を経路探索エンジン２から受信する。なお、ここで、経路取得部１２５は、経路情報を含む領域の地図情報も経路探索エンジン２から受信する、とする。
【０１２１】
次に、経路出力部１３１は、受信された経路情報、地図情報を出力する。かかる出力例は、図１０である。
（具体例２）
【０１２２】
まず、ユーザは、出発地「Ａ地点」、到着地「Ａ地点」、中継地点「Ｂ地点，Ｃ地点，Ｇ地点」、出発時刻「２０１６年０６月０１日００時００分」、観光時間「２時間」を、ルート提案装置１に入力した、とする。
【０１２３】
次に、受付部１１は、出発地「Ａ地点」、到着地「Ａ地点」、中継地点「Ｂ地点，Ｃ地点，Ｇ地点」、出発時刻「２０１６年０６月０１日００時００分」、観光時間「２時間」を含む動作指示を受け付ける。
【０１２４】
次に、巡回順序決定部１２２は、出発地識別子「Ａ地点」、中継地点識別子「Ｂ地点，Ｃ地点，Ｇ地点」、到着地識別子「Ａ地点」を用いて、以下のような巡回順路決定処理を行う。つまり、巡回順序決定部１２２は、「Ａ地点」を出発し、中継地点識別子「Ｂ地点，Ｃ地点，Ｇ地点」をいずれかの順序で回り、到着地識別子「Ａ地点」に到着する各巡回路の組み合わせに対して、各地点の位置情報を用いて、直線距離の合計を算出する。そして、巡回順序決定部１２２は、直線距離の合計が最短の巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｇ地点→Ａ地点」を取得した、とする。
【０１２５】
次に、ルート妥当性判断部１２３は、制約条件格納部１０２に制約条件が存在する、と判断する。そして、ルート妥当性判断部１２３は、各地点識別子「Ａ地点，Ｂ地点，Ｃ地点，Ｇ地点」に対応する時間情報（３０分，１０分，３０分，３０分）を、地点情報管理表から取得する。そして、訪問地点決定部１２１は、かかる時間情報の合計「１００分」を取得する。次に、ルート妥当性判断部１２３は、取得した時間「１００分」が、制約条件「２時間以内」を満たす、と判断する。そして、ルート妥当性判断部１２３は、変数「判断結果」に判断結果「満たす」を代入する。
【０１２６】
次に、経路取得部１２５は、巡回順序情報「Ａ地点→Ｂ地点→Ｃ地点→Ｇ地点→Ａ地点」を経路探索エンジン２に送信する。
【０１２７】
次に、経路探索エンジン２は、当該巡回順序情報を受信する。そして、経路探索エンジン２は、巡回順序情報が示す各地点間の経路探索を行い、経路情報を取得する。次に、経路探索エンジン２は、取得した経路情報を、ルート提案装置１に送信する。なお、ここで、経路探索エンジン２は、取得した経路情報を含む領域の地図情報も、経路情報とともにルート提案装置１に送信する、とする。
【０１２８】
次に、ルート提案装置１の経路取得部１２５は、経路情報を経路探索エンジン２から受信する。なお、ここで、経路取得部１２５は、経路情報を含む領域の地図情報も経路探索エンジン２から受信する、とする。
【０１２９】
次に、経路出力部１３１は、受信された経路情報、地図情報を出力する。かかる出力例は、図１０である。
【０１３０】
以上、本実施の形態によれば、高速かつ正確なルートの提案ができる。
【０１３１】
また、本実施の形態によれば、外部の経路探索エンジン２の資源を使用して、高速かつ正確なルートの提案ができる。
【０１３２】
また、本実施の形態によれば、高速、正確、かつ制約を満たすルートの提案ができる。なお、本実施の形態の具体例によれば、制約条件を用いて、ルート妥当性判断処理を行った。しかし、ルート妥当性判断処理は必須ではない。
【０１３３】
また、本実施の形態によれば、経路取得部１２５が取得した経路情報に対して、ルート妥当性判断処理を行わなかった。ルート妥当性判断部１２３は、経路取得部１２５が取得した経路情報に対して、ルート妥当性判断処理を行なっても良い。かかる場合、経路情報から、移動時間等の情報が取得できることが好適である。なお、経路情報から地点間の移動時間の情報を取得する技術は公知技術であるので、詳細な説明は省略する。
【０１３４】
また、本実施の形態において、ルート提案装置１は、ユーザが使用する端末装置（図示しない）から、動作指示を受信し、取得した経路情報を当該端末装置に送信しても良いことは言うまでもない。かかる場合、端末装置は、経路情報を受信し、出力する。そして、かかる場合、ルート提案装置１は、例えば、いわゆるクラウドサーバ等のサーバ装置である。
【０１３５】
さらに、本実施の形態における処理は、ソフトウェアで実現しても良い。そして、このソフトウェアをソフトウェアダウンロード等により配布しても良い。また、このソフトウェアをＣＤ−ＲＯＭなどの記録媒体に記録して流布しても良い。なお、このことは、本明細書における他の実施の形態においても該当する。なお、本実施の形態におけるルート提案装置１を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、コンピュータがアクセス可能な記録媒体は、地点を識別する地点識別子と当該地点の位置を示す位置情報を含む３以上の地点情報が格納される地点情報格納部を具備し、コンピュータを、前記地点情報格納部に格納されている３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得する巡回順序決定部と、前記巡回順序情報を経路探索エンジンに与え、前記３以上の地点を巡回順序に従った順序で経由する経路情報を取得する経路取得部と、前記経路取得部が取得した経路情報を出力する経路出力部として機能させるためのプログラムである。
【０１３６】
上記プログラムにおいて、コンピュータを、前記地点情報格納部に格納されている３以上の地点情報から、予め決められた条件を満たす３以上の地点情報を選択する訪問地点決定部としてさらに機能させ、前記巡回順序決定部は、前記訪問地点決定部が選択した３以上の各地点情報に含まれる位置情報を用いて、前記３以上の地点のうちの２つの地点間の３以上の距離を取得し、当該３以上の距離を用いて、前記３以上の地点の巡回順序に関する情報である巡回順路情報を取得するものとして、コンピュータを機能させるプログラムであることは好適である。
【０１３７】
上記プログラムにおいて、前経路取得部は、前記巡回順序情報を、外部の経路探索エンジンに送信し、前記３以上の地点を巡回順序に従った順序で経由する経路情報を前記外部の経路探索エンジンから受信するものとして、コンピュータを機能させるプログラムであることは好適である。
【０１３８】
上記プログラムにおいて、前記記録媒体は、前記巡回順序決定部が取得した巡回順路情報が満たすべき１以上の制約条件が格納される制約条件格納部をさらに具備し、
コンピュータを、前記巡回順序決定部が取得した巡回順路情報が前記１以上の制約条件を満たすか否かを判断するルート妥当性判断部と、前記巡回順序情報が前記１以上の制約条件を満たすと前記ルート妥当性判断部が判断するまで、前記巡回順序決定部に対して、先に取得した巡回順路情報と異なる巡回順路情報を取得するように指示する、または前記訪問地点決定部に先に選択した３以上の地点情報の組と異なる３以上の地点情報の組を選択するように指示する制御部としてさらに機能させるプログラムであることは好適である。
【０１３９】
上記プログラムにおいて、前記地点情報は、地点の１以上の属性値を有し、前記制約条件は、前記１以上の属性値を用いた条件であるものとして、コンピュータを機能させるプログラムであることは好適である。
【０１４０】
上記プログラムにおいて、前記地点の１以上の属性値は、当該地点に対応付けられた時間を示す時間情報を含み、前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の時間情報を用いた時間に関する時間条件あるものとして、コンピュータを機能させるプログラムであることは好適である。
【０１４１】
上記プログラムにおいて、前記地点の１以上の属性値は、当該地点に対応付けられた費用を示す費用情報を含み、前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の費用情報を用いた費用に関する費用条件あるものとして、コンピュータを機能させるプログラムであることは好適である。
【０１４２】
上記プログラムにおいて、前記地点の１以上の属性値は、当該地点に対応付けられた満足度を示す満足度情報を含み、前記制約条件は、前記巡回順序決定部が取得した巡回順路情報に対応する３以上の各地点の満足度情報を用いた満足度に関する満足度条件あるものとして、コンピュータを機能させるプログラムであることは好適である。
【０１４３】
上記プログラムにおいて、前記地点情報は、地点の２以上の属性値を有し、前記制約条件は、前記２以上の属性値を用いて算出されたスコアを用いた条件であるものとして、コンピュータを機能させるプログラムであることは好適である。
【０１４４】
また、図１１は、本明細書で述べたプログラムを実行して、上述した種々の実施の形態のルート提案装置１等を実現するコンピュータの外観を示す。上述の実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムで実現され得る。図１１は、このコンピュータシステム３００の概観図であり、図１２は、システム３００のブロック図である。
【０１４５】
図１１において、コンピュータシステム３００は、ＣＤ−ＲＯＭドライブを３０１２含むコンピュータ３０１と、キーボード３０２と、マウス３０３と、モニタ３０４とを含む。
【０１４６】
図１２において、コンピュータ３０１は、ＣＤ−ＲＯＭドライブ３０１２と、ＭＰＵ３０１３と、バス３０１４と、ＲＯＭ３０１５と、ＲＡＭ３０１６と、ハードディスク３０１７とを含む。ＲＯＭ３０１５は、ブートアッププログラム等のプログラムを記憶している。ＲＡＭ３０１６は、ＭＰＵ３０１３に接続され、アプリケーションプログラムの命令を一時的に記憶するとともに一時記憶空間を提供する。ハードディスク３０１７は、通常、アプリケーションプログラム、システムプログラム、及びデータを記憶している。ここでは、図示しないが、コンピュータ３０１は、さらに、ＬＡＮへの接続を提供するネットワークカードを含んでも良い。
【０１４７】
コンピュータシステム３００に、上述した実施の形態のルート提案装置１等の機能を実行させるプログラムは、ＣＤ−ＲＯＭ３１０１に記憶されて、ＣＤ−ＲＯＭドライブ３０１２に挿入され、さらにハードディスク３０１７に転送されても良い。また、プログラムは、図示しないネットワークを介してコンピュータ３０１に送信され、ハードディスク３０１７に記憶されても良い。プログラムは実行の際にＲＡＭ３０１６にロードされる。プログラムは、ＣＤ−ＲＯＭ３１０１またはネットワークから直接、ロードされても良い。
【０１４８】
プログラムは、コンピュータ３０１に、上述した実施の形態のルート提案装置１等の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティープログラム等は、必ずしも含まなくても良い。プログラムは、制御された態様で適切なモジュールを呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいれば良い。コンピュータシステム３００がどのように動作するかは周知であり、詳細な説明は省略する。
【０１４９】
なお、上記プログラムにおいて、情報を送信するステップや、情報を受信するステップなどでは、ハードウェアによって行われる処理、例えば、送信ステップにおけるモデムやインターフェースカードなどで行われる処理（ハードウェアでしか行われない処理）は含まれない。
【０１５０】
また、上記プログラムを実行するコンピュータは、単数であってもよく、複数であってもよい。すなわち、集中処理を行ってもよく、あるいは分散処理を行ってもよい。
【０１５１】
また、上記各実施の形態において、一の装置に存在する２以上の通信手段（端末情報送信部、端末情報受信部など）は、物理的に一の媒体で実現されても良いことは言うまでもない。
【０１５２】
また、上記各実施の形態において、各処理（各機能）は、単一の装置（システム）によって集中処理されることによって実現されてもよく、あるいは、複数の装置によって分散処理されることによって実現されてもよい。
【０１５３】
本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【０１５４】
以上のように、本発明にかかるルート提案装置は、高速かつ正確なルートの提案ができるという効果を有し、ルート提案装置等として有用である。
【符号の説明】
【０１５５】
１  ルート提案装置
２  経路探索エンジン
３  端末装置
１０  格納部
１１  受付部
１２  処理部
１３  出力部
１０１  地点情報格納部
１０２  制約条件格納部
１２１  訪問地点決定部
１２２  巡回順序決定部
１２３  ルート妥当性判断部
１２４  制御部
１２５  経路取得部
１３１  経路出力部
【図１】
2018072150.tif 000003
【図２】
2018072150.tif 000004
【図３】
2018072150.tif 000005
【図４】
2018072150.tif 000006
【図５】
2018072150.tif 000007
【図６】
2018072150.tif 000008
【図７】
2018072150.tif 000009
【図８】
2018072150.tif 000010
【図９】
2018072150.tif 000011
【図１０】
2018072150.tif 000012
【図１１】
2018072150.tif 000013
【図１２】
2018072150.tif 000014