"グラフにおける寄り道の最短経路を求める寄り道検索装置であって、ノードのID、名前、カテゴリ情報を持つノード情報と、2つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始終了時刻とサービス内容を格納したグラフデータベースと、ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOIPointOfInterestチェック手段と、前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザサービス条件チェック手段と、前記ユーザサービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、を有することを特徴とする寄り道検索装置。前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する請求項1記載の寄り道探索装置。グラフにおける寄り道の最短経路を求める寄り道検索方法であって、ノードのID、名前、カテゴリ情報を持つノード情報と、2つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始終了時刻とサービス内容を格納したグラフデータベースを有する装置において、ユーザインタフェース手段が、ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザ入力ステップと、POIPointOfInterestチェック手段が、前記ユーザ入力ステップで入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOIチェックステップと、ユーザサービス条件チェック手段が、前記POIチェックステップで取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザサービス条件チェックステップと、全体スケジュール算出手段が、前記ユーザサービス条件チェックにおいて排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出ステップと、を有することを特徴とする寄り道検索方法。前記POIチェックステップの実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限ステップを更に行う請求項3記載の寄り道探索方法。コンピュータを、請求項1または2に記載の寄り道検索装置の各手段として機能させるための寄り道検索プログラム。上記寄り道検索において、寄り道をするときに、寄り道する店が開店していないと意味がない。店の開店時間は12時~22時のように制限がある。この制限を満たすような店を寄り道して欲しい。例えば、夜遅めに出発するときには、閉店前に間に合うように出発点からなるべく近くの場所に寄り道する必要がある。これは開店時間だけでなく、12時~13時、ランチ2割引や17時以降、閉店前3割引のような時間限定のタイムセールのときに来店したいという要求と同じ課題であるといえる。このような、時間制約を持つような寄り道検索をタイムセール寄り道検索と呼ぶ。上記では、開店時間などのPOIの時間制約を例として挙げたが、その店で2時間ゆっくりしたい銀行でお金をおろすのでぎりぎりに間に合えばよいと言うような、ユーザにとっての時間的な制約を満たすような検索要求もあり、これらを満たす検索も同様にタイムセール寄り道検索と呼ぶ。タイムセール寄り道検索においては、基本的な時間制約をチェックする手順と条件が課題となる。通常の寄り道検索では全体所要時間は、出発点からPOIまでの所要時間と、POIから到達点までの所要時間を単純に足せばよいが、タイムセール寄り道検索の場合、待ち時間も許容することがサービス的に有効である。POIにサービス開始よりも5分早めに着いたとしても、待ち時間を含めればトータルの所要時間は小さい場合もある。このように、待ちも含めた全体スケジュールを提案できることが課題となる。寄り道検索の従来手法はダイクストラ法をベースとしているが、ダイクストラ法は貪欲的な特徴を持ち、近傍のノードをすべて展開していく。よって、従来の寄り道検索手法において、全体の所要時間に予め制約をかけることによって、探索の発散を抑止している。この探索範囲の増大と、不自然な制約は大規模で複雑なネットワークに適用する上での課題である。タイムセール寄り道検索においては、時間制約を利用して、探索の範囲を狭められる可能性がある。ダイクストラ法では、所要時間に相当するエッジに与えられる数値をコストと呼ぶことが多いため所要時間よりは広い意味、今後、所要時間をコストと呼ぶことがある。本発明は、上記の点に鑑みなされたもので、ユーザにとっての時間的な制約を満たすような検索要求に対応でき、かつ、待ち時間も含めたスケジューリングが可能な寄り道検索装置及び方法及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明請求項1は、グラフにおける寄り道の最短経路を求める寄り道検索装置であって、ノードのID、名前、カテゴリ情報を持つノード情報と、2つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始終了時刻とサービス内容を格納したグラフデータベースと、ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOIPointOfInterestチェック手段と、前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザサービス条件チェック手段と、前記ユーザサービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、を有する。また、本発明請求項2は、前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する本発明により、ユーザが求める寄り道要求に応えるナビゲーションサービスを実現できる。自分の好みの店を通る経路を求める、ATMの終了時間に間に合うような経路を求める、等のサービスを可能にする。また、探索制限の効果によって、探索範囲を限定し、レスポンスタイムを向上させることができる。但し、探索範囲の制限は、ユーザ指定条件に依存する。例えば、ユーザが非常に緩い条件を指定した場合極端な例はどんな時間でもよいからサービスを受けたい、探索範囲の制限の効果はなくなる。しかし、ランチタイム、宴会時間などのように時間が限定される場合、例えば、行きの探索範囲は、大まかにはスタート予定時刻から宴会開始までという範囲に限定され、無秩序な探索は抑制される効果がある。以下図面と共に、本発明の実施の形態を説明する。図3は、本発明の一実施の形態における寄り道検索装置の構成を示す。同図に示す寄り道検索装置は、コストテーブル101、グラフデータベース102、ユーザインタフェース部105、探索制御部110、POIチェック部120、コストテーブル更新部130、探索終了判定部140、ユーザサービス条件チェック部150、全体スケジュール算出部160、探索結果作成部170、探索制限部180、グラフDB制御部190から構成される。さらに、図示しないが、結果テーブルや候補テーブルを保持するメモリも具備する。コストテーブル101は、探索されたノード、そのノードに至るまでのその時点での最小コスト、そのノードに至る一つ前のエッジの情報を持つ。また、コストテーブル101は、出発点から探索されたコストテーブル、到着点から探索されたコストテーブルの2つがある図19,20。グラフデータベース102は、ノードのID、名前、カテゴリ情報からなるノード情報と、2つのノードIDの組で表現されるノード間の関係とノード間の移動所要時間からなるエッジ情報と、各ノードで実施されるサービスの開始終了時刻、開店時間やタイムセール等の時間制約情報を、グラフデータモデルの形で二次記憶に永続的に記憶する図18。ユーザインタフェース部105は、ユーザが指定する出発点、到着点、行きたい場所のカテゴリ、時間制約を入力する機能を持つ。詳しくは、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得する。探索制御部110は、ユーザインタフェース部105で指定された情報を元に、探索を実行し探索結果を作成するまでの全体の制御を行う。POIチェック部120は、探索の途中で、ユーザが現在いる地点が指定されたカテゴリを満たすかどうか判定する機能を持つ。ユーザサービス条件チェック部150、全体スケジュール算出部160に問い合わせることにより、寿司銀行のようなカテゴリと一致していることをチェックし、計算されたコスト情報から、その地点に寄り道したときに所望の条件と合致しているか開店時間やタイムセールに間に合ったか、2時間ゆっくりできるのか等を判定する。コストテーブル更新部130は、ユーザが現在いる点の隣の全てのエッジを求め、もし、そのエッジを経由するルートが最小コストであれば、コストテーブル101を更新する機能を持つ。探索終了判定部140は、探索を終了してよいのかの判定を行う。判定は、出発店からPOIまでの経路と到着点からPOIまでの両方の経路が求められていること;事前に設定された個数の経路を導出していること;これ以上よりよいコストの経路が求められないこと;コストの限界値以下であること;等を用いて判定を行う。ユーザサービス条件チェック部150は、POIチェック部120におけるPOIチェック時に、ユーザ条件とサービス条件を照らし合わせて、その矛盾があるかないのかの判定を行う機能を持つ。矛盾がある場合はPOIチェック部120にNGを返却する。全体スケジュール算出部160は、出発点~POIの道のり以降、出発路と呼ぶ、POI~到着点の道のり以降、到着路と呼ぶに掛かるコストと、サービス条件を満たすように補正されたユーザ条件を受け取り、全体のスケジュールを算出する機能を持ち、その結果をPOIチェック部120に返却する。探索結果作成部170は、探索終了後に、コストテーブル101の情報から、全経路を構成する機能を持つ。終了点のコストテーブルから、順に前のコストテーブル101を追っていけば全経路を見つけることができる。探索制限部180は、探索している位置とユーザ条件からそれ以上展開する必要があるかを判定し、不要であれば、コストテーブル101のノードのコストを無限大にすることでノードの展開を停止させ、探索を制限する機能を持つ。グラフDB制御部190は、グラフデータベース102への検索機能を提供する。提供される機能としては、あるノードから隣のノードを求める、あるエッジの両側のノードを求める、などの基本的なグラフ情報を検索する機能である。上記の構成のうち、ユーザサービス条件チェック部150、全体スケジュール算出部160は、単なる寄り道検索ではなく、タイムセール寄り道検索を実施するために必要な機能である。太線で示された探索制御部180とPOIチェック部120は、タイムセール寄り道検索を実施するにあたって、追加された上記のユーザサービス条件チェック部150、全体スケジュール算出部160の機能を呼び出すところが従来の技術と異なる点である。なお、タイムセール寄り道検索では当然グラフデータベース102にPOIのサービス条件が追加される点で異なる。太い二重線で示された探索制御部180は、タイムセール寄り道検索において探索を効率的に実行するために必要な機能である。<タイムセール寄り道検索>以下に、タイムセール寄り道検索の実現法について説明する。最初に実現するために必要となる情報の定義について説明する。この情報については、サービス提供側の情報とユーザ側の都合の情報の2種類がある。それぞれをサービス条件ユーザ条件と呼ぶことにする。最初にサービス条件について説明する。<サービス条件>タイムセールの開始時刻:servicestartタイムセールの終了時刻:serviceendタイムセールのサービス内容:sericecontentタイムセールの開始時刻、終了時刻はその名とおりの定義であり、ランチサービスならば、servicestart=11:30serviceend=14:00等となる。また、開店時刻、閉店時刻もこの値を使用することとする。また、以下の例では、電車網を意識した例で説明するが、電車の始発終電を考慮した検索が可能になっている。電車の始発時刻終電時刻は、駅を表すノードのserivestartとserviceendであると定義することにする。電車網を検索する場合、本来は時刻表と乗り継ぎの関係も考慮する必要があるが、それは容易であるため、単純化のために、ここでは考慮しないことにする。servicecontentはタイムセールのサービス内容であり、例えば、ランチ食べ放題や、残り商品全品3割引、等といった値をとり得る。ユーザが希望するサービス内容を指定することを考えると、例えば、ランチand3割引、等の組合せの指定がある。そのためには、serivcecontentを構造化し、検索可能にする必要があるが、その方法は容易であるため、ここでは、serivcecontentは一つの項目として構造化されていないと想定する。次に、ユーザ条件について定義する。<ユーザ条件>出発点を出発する時刻の最大値と最小値をそれぞれかstartmax、startmin;POI滞在時間の最大値と最小値を、posstaymax、posstaymin;POI到着時刻の最大値と最小値を、poistartmax、poistartmin;POI出発時刻の最大値と最小値を、poiendmax、poiendmin;到着点へ到着する時刻の最大値と最小値を、endmax、endminこれらの定義の意味を説明する。出発点の最大値はできるだけ遅く出発する時刻、最小値はできるだけ早く出発する時刻を意味する。以下にその例を示す。1POIの滞在時間:最低1時間はゆっくり食をしたい場合、poistaymin60とする。2時間で食事を切り上げたい場合、poistaymax120とする。チケット購入のように、窓口に滑り込みで間に合えばよいという場合、poistaymax0とすればよい。POI到着時刻は、食事を遅くとも1900から始めたい場合は、poistartmax1900とする。食事を1800より前には始めたくない場合は、poistartmin1800とする。2POI出発時刻:食事を22時には必ず切り上げる場合は、poiendmax2200とする。食事を2100までは必ず時間をかけて食べる場合は、poiendmin2100とする。3到着時刻到着する時刻の最大値は、遅くなっても2400には帰宅したい場合は、endmax2400とする。2300にならないと家の鍵が開かないので、それよりも遅く帰る必要があるという場合は、endmin2300とする。タイムセール寄り道検索を実現するためには、ユーザサービス条件チェック部150において、ユーザ条件とサービス条件が合致するかをチェックしながら探索を行う必要がある。そのチェックの仕方により2つの方式がある。一つはタイムセール条件を最後にチェックする方式であり、寄り道が完成するタイミングで、タイムセール条件を満たすかどうかチェックする方式である。請求項1,3に対応もう一つは、タイムセール条件を事前にチェックする方式であり、寄り道が完成していない時点でも、タイムセール条件を利用すると探索を停止できるケースがある。その条件を積極的に利用して、事前に探索範囲を狭める方式である。請求項2、4に対応以下に、上記の2つの方式について詳細に説明する。<方式1:タイムセール条件を最後にチェックする方式>寄り道が完成するのは、POIチェックの処理内であるので、その処理をタイムセールに対応するよう前述の図2のフローを図4のように変更する。以下に、変更箇所を説明する。なお、図2と同一処理には図2と同一のステップ番号を付与し、その説明を省略する。ステップ201両側からのルートが発見された後ステップ102、Yesに、ユーザサービス条件チェック部150は、そのルートがタイムセールに関するユーザ条件サービス条件を満たすかどうかをチェックする。ここで、ユーザ条件とサービス条件をチェックし矛盾する場合には排除される。もし、満足しない場合例:タイムセール時間内に寄り道できない場合は、POIチェックはNGとなり停止する。ここまでの処理で、行き帰りPOI滞在の時間の長さが決定される。ステップ202全体スケジュール算出部160は、全体スケジュールを算出し、結果テーブルに登録する。ここでは、待ち時間がある場合も考慮して、出発時刻、経由点出発時刻等の全体スケジュールを求めて、結果テーブルに登録する。通常の寄り道検索では、S側とE側のコストを単純に加えたものであるが、タイムセール寄り道検索の場合は、それでは不十分である。サービスが始まるまで、待たされる可能性があるからである。待ちのあるなしで、コストの順番が逆転する可能性がある。最終的なコストは、出発時刻と到着時刻の差となる。このステップで行きから帰りまでの全ての時刻が決定される。次に、ユーザサービス条件チェック150による突合せ比較について説明する。図5は、本発明の一実施の形態におけるユーザ条件とサービス条件の突合せ処理のフローチャートである。ステップ301最初に、POI滞在開始滞在終了条件とサービス条件に矛盾がないことをチェックする。図6にその状況を示す。poistart、poiendはそれぞれPOI開始終了時刻の候補となる区間であり、poistayはPOI滞在時間の長さを表している最大値がpoistaymax、最小値がpoistaymin。serviceはサービス条件を表す区間である。POIの滞在開始と滞在終了はサービス時間に含まれる必要があるため、以下の関係が成り立つ必要があるサービスは1区間で表現されると仮定している。servicestart≦poistartmaxpoiendmin≦serviceendステップ302次に、POI滞在開始区間とPOI滞在終了区間を補正する。サービス区間に含まれないPOI滞在開始終了区間は実質的に除外してよいので、POI滞在開始区間終了区間とサービス区間で交わりをとり、それを補正されたPOI滞在開始区間終了区間として今後の処理で使用する図6のpoistartとpoiend。ステップ303次に補正されたPOI滞在開始滞在終了条件とPOI滞在時間に矛盾がないことをチェックする。図7にPOI滞在時間と開始時間終了時間の関係を示す。図7に示すように、滞在時間の長さが滞在開始終了時間に対して短い場合ケース1は矛盾である。OKである条件は以下で表現される。前者がpoistayが短い場合の排除、後者がpoistayが長い場合の排除である。poiendminpoistartmaxpoistayminpoistartminpoistaymax≦poiendmaxステップ304次に、コストテーブル101とグラフデータベース102を参照して、POIまでのコスト情報とPOI滞在情報に矛盾がないかをチェックする。S側からのPOIまでのコストをcosts、E側からPOI案でのコストをcosteとする。図8にそれらの相対関係を示す。制約を満たさないケースとして、行くときのコストが大きすぎてPOI滞在開始に間に合わないケースケース1、帰るときのコストが大きすぎて目的地到着に間に合わないケースケース2がある。また、待ちを許容する場合は、ケース3のようにPOIに到着してからPOI滞在開始まで待ったり、POI滞在終了してから、移動するまで待つというケースは許容することができる。この条件で式を書くと以下のようになる。この条件をチェックする。startmincostspoistartmaxstartendmincosteendmaxまた、出発から到着までのトータルの長さが区間の最大幅を超えないようにする必要があるのでケース5、以下の条件をチェックする。costspoistaymincosteendmaxstartminこれでユーザ条件とサービス条件の付き合わせは完了である。ステップ202次に、全体スケジュール算出部160は、待ち時間を含めた全体スケジュールを算出し、結果テーブルに登録する。この前のステップ201のチェックによって、時間の長さについて矛盾するような条件は排除されているが、これまで与えられた制約では、いつ出発し、POIに滞在し、目的地に到着するという時刻は一意には決定されない全体コストは一意に決まらない。全体のプランを決定するためには、時間制約を持つ、寄り道検索に対す戦略の知識が必要である。ここでは、代表的な戦略例に基づいて全体プランを決定し、全体コストを求める方法を提示する。この戦略は単純化されており、現実のアプリケーション上必ずしも有効とは限らない。実際にはアプリケーションに適した戦略を実現する必要があるが、それは下記戦略の応用で容易に実現できる。まず、説明のために幾つかの用語を定義する。全体の出発と到着の時刻を、totalstart、totalendとする。総コスト出発してから到着するまでの時間をtotalcostとする。自明な関係として、totalcosttotalendtotalstartが成り立つ関係1実際にPOIに滞在する時間の開始時刻と終了時刻をそれぞれ、poistaystart、poistayendとする宴会の開始と終了時刻のイメージPOIに到着する時刻と出発する時刻をpoiarrive、poileaveとする。自明な関係として、poiarrivetotalstartcostsが成り立つ関係2。自明な関係として、totalendpoileavecosteが成り立つ関係3。やや用語が紛らわしいが、POIへの滞在とは、POIの店に入っていた時間のイメージであり、POIの到着出発時刻とは区別をしていることに注意されたい。POIへの滞在を比喩的に理解するために、今後、滞在を宴会の開始終了を例として表現することがある。これからの目標は、戦略に応じて、totalstart、poiarrive、poistaystart、poistayend、poileave、totalendの6つの値を決定することである実質的には関係2,3があるので4つ決定すればよい。また、これらが決めれば関係1によりtotalcostも決定する。以下の例では簡単のために、POIへの滞在時間宴会時間は固定であるとする。これは、POI滞在時間の最大値と最小値が等しいことを意味するこの値をpoistayとするので、式で表現すると以下が成り立つ。poistayminpoistaymax<戦略例>できるだけ待ちをなくし、かつ早く行動する:この戦略の特徴を以下に示す。できるだけ早く宴会を開始する;できるだけ早く帰宅しようとする;待ち時間はできるだけ発生させない→出発は宴会開始に近づける;スケジュールの算出は、個別値決定フェーズと調整フェーズの2つのフェーズによって構成される。個別値決定フェーズとは、まず、全体としてスケジュールの整合性は無視し、出発時刻Start、到着時刻End、経由地滞在開始POIの3つの値をそれぞれの制約条件を元に決定する。調整フェーズでは、前に決定された値から全体スケジュールとして矛盾しないような調整を行う。●個別値決定フェーズ:図9に個別値決定フェーズのイメージを示す。このフェーズでは、大きく、出発路の区間S区間。ケース1~3、到着路の区間E区間。ケース1,2、滞在地の区間P区間。ケース1,2の3つの区間を決める。この戦略における出発路区間は、costsの値が小さいときは、許容されるぎりぎりのstartmaxに出発し、POI到着後宴会開始まで待つことになるケース1。costsがだんだん大きくなり待ちが短くなり、poiarriveがpoistartminに到着すると、次にtotalstartが前倒しされるケース2。totalstartがstartminに到達した時点で、poiarriveが後ろにずれていくケース3。costsの最大値はpoistartmaxstartminで、これより大きくなることはない既にそのケースは事前に除外されている。到着路区間はcosteの値が小さいときは、許容されるぎりぎりendminに到着するようにPOIを出発する。宴会終了後POI出発まで待つことになるケース1。costeがだんだん大きくなり待ちが短くなり、poileaveがporendminに到達すると、次に、totalendが後ろにずれるケース2。costeの最大値はendmaxpoiendminで、これより大きくなることはない既にそのケースは事前に除外されている。滞在区間は、POI滞在時間poistayが小さいときは、許容されるぎりぎりのチェックを行う。チェックが満たされない場合はステップ502、No、当該ノードは候補テーブルにも、結果テーブルにも追加されることはない。よって、無駄な候補テーブル、結果テーブルの要素を作成する必要がないので、処理量を削減することができる。両側からPOIへのパスが見つかった後にステップ503、Yes、Step3POIへの両側からのパスが見つかる時点のチェックを行う。これは、前述した方式1のタイミングと同じであり、この条件を満たさない場合は、結果テーブルへの登録がキャンセルされる。次に、上記のStep1~3でそれぞれ可能なチェックについてまとめる。全部で7つのチェック条件がある以下の条件が満たされる場合にOKとなる。これらのチェックを実現するのが探索制限部180となる。条件1:S側から探索し、POIに到達する前にpoistart区間を過ぎないこと;条件2:E側から探索し、POIに到達する前にpoiend区間を過ぎないこと;条件3:S側から探索し、そのコストに滞在時間の最小値を加えたとき、poiend区間をすぎないこと;条件4:E側から探索し、そのコストに滞在時間の最小値を加えたとき、poistart区間をすぎないこと;条件5:図6に示した、POI滞在開始終了とサービス条件の制約チェック;条件6:図7に示した、POI滞在時間の制約チェック;条件7:図8に示した、S側からのコスト情報とPOI滞在終了の制約チェック;条件8:図8に示した、E側からのコスト情報とPOI滞在終了の制約チェック;条件9:図8に示した、全体のコスト情報の制約チェック;上記の条件1~4は、POIに到達する前にチェックできるので、Step1でのチェックが可能である。Step1での探索制限部180による処理は図15に示すとおりであり、Step1で修正された例を図16に示す。一方、条件5~8は、POIに到達しないとチェックができないが、両側からコストを要求していないので、Step2POIを発見する時点でのチェックが可能である。条件9は、両側からのコストが必要なので、Step3でのチェックが必要である条件5,6は複数の式、それ以外は一つの式で一つの条件としているが、ここでは、S側、E側、POIの単位で条件としている。上記の条件1~9を表す式を以下に示す。条件1:startmincosts≦posstartmax条件2:poiendomincoste≦endmax条件3:startmincostspoistaymin≦poiendmax条件4:poistartmin≦endmax条件5:servicestart≦poistartmaxpoiendmin≦serviceend条件6:poiendminpoistartmaxpoistayminpoistartminpoistaymax≦poiendmax条件7:startmincosts≦poistartmax条件8:poiendmincoste≦endmax条件9:costspoistaymincosteendmaxstartmin探索制限部180において、これらの条件をチェックすることにより、探索範囲の絞込みができ、同じ結果を効率よく得ることができる。<終了条件の修正>タイムセール寄り道検索では、POI滞在時間を考慮する必要があるため、通常の寄り道検索で使われた以下の終了条件をそのまま使うことができない。結果テーブルの最大コスト≦候補テーブルの最小コスト現在のノードのコスト修正された終了条件は以下のようになる。POI滞在含む結果の最大コスト≦候補テーブルの最小コスト現在ノードのコストpoistaymin以下に、本発明の実施例を説明する。<寄り道検索>以下に寄り道探索の実施例を説明する。例で用いるグラフを図17に示す。同図において、○と☆はノードであり、☆はPOIであり、○はそれ以外である。Sが出発地で、Eが目的地である。ノード間にはエッジが定義されており、その上の数字はノード間の移動コストを表す単純化のためにコストの単位は分時等ではなく何らかの単位時間とする。このグラフをグラフデータベース102として表現した例を図18に示す。同図の例では、グラフデータベース102は関係データベースのような表形式で表現しているが、ノードの関係をポインタで表現したり、関係データベース以外でも実装は可能である。グラフデータベース102の機能としては、ノード名を指定してノードidを取得、ノードidを取得してそれに繋がるエッジを取得等を仮定する。これらは例えば、関係データベースで容易に実装できる。寄り道検索を実行した場合のコストテーブル101のイメージを図19出発路側、図20到着路側に示す。それぞれ、S、Eを出発点としたダイクストラ探索の実行であり、前述の非特許文献1等に示されている方法と同じである。但し、POIに到達した場合に、候補テーブルにノードとそこまでのコストの登録を行う。例えば、出発路側コストテーブルにおいて、Step3でP1が確定しており、候補としてスタート側から,P1に到達,コストは3という情報が登録されている。図21に候補テーブルと結果テーブルを示す。例えば、同図中のStep7において、S側とE側に共通するP2というPOIが出現したので、それを結果テーブルに登録しているP2P12。同図の数値が足し算になっているのは、S側からのコストとE側からのコストを後での説明上明記しておくためである。同図に示す結果テーブルはトータルコストでソートされている。よってこの場合の求める寄り道経路は、P1を経由する経路であり、トータルのコストは18である。具体的な経路は、ダイクストラ法と同様の方法で求めることができる例:各ノードの前のノードを保存しておく。<タイムセール寄り道検索>次に、タイムセール寄り道検索の実施例を示す。対象となるグラフは上記と同じ例を利用する。各時間の指定例を図22に示す。数直線は時間を表し、単位はグラフ上のコストと同じ単位であると仮定する。例えば、startminの値は時刻0であり、poistartminは時刻13である。これから、時間に関する条件チェックの実施例を説明する。まず、POI滞在開始終了条件とサービス条件に矛盾がないチェック図6について述べる。図22中にP1~P5のサービス時間例を示した。この例では、P2の終了が矛盾となっており、候補から除外される。サービス条件を加味し、POI滞在開始終了条件は補正されるが、その例を同じ図中に示してあるP1の例。数直線としての交わりを求めている。このように補正された区間で以後の議論を続ける必要があるが、今後の議論では簡単のために、P1~P5のサービス条件を全て、13~28と仮定し、ここでは補正が発生しない、とする。<補正されたPOI滞在開始終了条件とPOI滞在時間に矛盾がないチェック>次に、補正されたPOI滞在開始終了条件とPOI滞在時間に矛盾がないチェック図7について述べる。この例では、POI滞在時間が5~15例:poistaymin5andpoistaymax15であれば、この制約は満たされる。今後は、poistayminpoistaymax10ちょうど10だけ滞在すると仮定して説明する。コスト情報とPOI滞在開始終了条件の矛盾チェック図8について述べる。条件式startmincostspoistartmaxstartendmincosteendmaxcostspoistaymincosteendmaxstartminが満たされるかどうかをチェックする。そのチェックの様子を図23に示す。例えば、P1において、startmincostsは、poistartmaxを超えるので条件を満たさない。この時点で、P5はPOIの候補から除外される。トータルのコストチェックについては、endmax-statminの値が38で、costspoistaymincosteの値が28~36なので満たされるP5は満たされないが既に除外されている。<待ち時間も含めた全体コストを求めるの処理>待ち時間も含めた全体コストを求める図14のS506の実施例を示す。個別値決定フェーズであるが、そのイメージを示した図9を本実施例に適用したものを図24に示す。ケース1、ケース2等に示した数直線と値は、それぞれの場合のスレッシュホールドとなっている。例えば、S区間のケース1は区間の先頭が時間0~5の場合であり、ケース2は区間の終点が13~18の場合である。実施例に従って、場合を決定して個別の値totalstartとpoileaveを決めた結果を図25に示す。また、P区間についても決定する必要があるが、本実施例では、poistay10であったから、場合はケース1であり、poistaystartは10となる。調整フェーズの例を図26に示す。P1,P2,P4は重なりがないので調整の必要がない。P1は出発路で待ちが生じるパターンとなっている。P3は重なりがあるので、後ろにずらして最終的な結果を得る。これらの最終結果から、全体のコストが求まる。図26の右端にその値を示す。最小となるのは、P2を経由するケースであることがわる。時間的な制約を考慮しない寄り道検索では、P1を経由する経路が最適解であったが、P1を経由する場合、P1の位置が出発点に近いためにPOIに早く到着してしまい、待ちが発生する。それでP2が逆転している。これは例えて言えば、宴会に丁度よい時間にPOIを訪れることができていないということである。つまり、このタイムセール寄り道検索を用いることによって、興味のある場所に最適な時間に訪れることが可能になる。<方式2:条件評価を先に行う場合>最後に方式2条件評価を先に行う場合について説明する。当該方式2を採用する場合、本実施例においては、図23でNGとなったP5を最終的なチェックではなく、出発路側の探索でP5に到達した時点で、それ以降の探索を停止することができる。本実施例の図19では、P5に到達する時点が、step11であるため、ステップ数の削減とはなっていないが、一般的には、展開数を削減することに貢献することができる。なお、上記の実施の形態における図3に示す寄り道検索装置の構成要素の動作をプログラムとして構築し、寄り道検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"