寄り道検索装置及び方法及びプログラム
【課題】 ユーザにとっての時間的な制約を満たすような検索要求や、待ち時間も含めたスケジューリングを可能とする。
【解決手段】 本発明は、ユーザから出発点、到達点、経由点を含むカテゴリ情報と、ユーザ指定時間条件を取得し、カテゴリ情報に合致する経由点をグラフデータベースを参照して取得し、経由点のうちユーザ指定の情報とサービス時間条件に合致しない経由点を排除し、排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、出発点から該経由点を経由し、到達点に至るルートを検索する。
【解決手段】 本発明は、ユーザから出発点、到達点、経由点を含むカテゴリ情報と、ユーザ指定時間条件を取得し、カテゴリ情報に合致する経由点をグラフデータベースを参照して取得し、経由点のうちユーザ指定の情報とサービス時間条件に合致しない経由点を排除し、排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、出発点から該経由点を経由し、到達点に至るルートを検索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、寄り道検索装置及び方法及びプログラムに係り、特に、交通やグルメ等のインターネット上の検索サービス、カーナビ等のナビゲーションシステム、旅行日程作成支援のような計画作成支援等において、所定の地点を通過する経路のうち、最短の経路を探索するための寄り道検索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフにおける最短経路を求める技術として、ダイクストラ法、A*法等のグラフ探索技術が確立している（例えば、非特許文献１参照）。これらの技術は、ノード間の移動コスト（例：所要時間）が与えられたグラフにおいて、合計コストが最小となる「最短の」経路を求める手法である。この技術は鉄道網や道路網から所望のルートを探索するサービスに活用されている。
【０００３】
一方、ユーザに対して、ユーザの希望や趣向等に応じて、行きたい場所を推薦するレコメンドサービスがある。レコメンドサービスとして、代表的な技術に以下の２つがある。
【０００４】
・位置情報を用いたグルメ情報等の推薦；
・経路探索時の経路の近辺の店・サービスの推薦；
前者は、ユーザがＧＰＳ機能を持つ携帯電話、スマートフォン等を持ち、その位置情報からその近くのユーザの希望や趣向にあった店を推薦するという技術である。
【０００５】
後者は、カーナビ等で、目的地までの経路を検索したときに、その経路沿いのガソリンスタンドやファーストフード店等を表示するような技術である。
【０００６】
グラフ情報を蓄積・検索する手段として、グラフデータベースが提案されている（例えば、非特許文献２参照）。
【０００７】
上記技術と関連するが目的が少し異なる、次のような要求がある。例えば、ユーザがどこかに出張するときに、必ずしも最短経路でなく、多少遠回りしてもよいから、その経路上で自分の好みの昼食をとってから目的地に到達したい、という要求である。この要求を満たす検索を「寄り道検索」と呼ぶことにする。このとき経由する経由地をPOI(Point Of Interest)と呼ぶ。ユーザからは、直接具体的なPOIを指定するのではなく、「寿司が食べたい」とか「銀行に行きたい」というような行きたい場所のカテゴリで指定されることを想定する。具体的なPOIが事前に決まっているのであれば、出発点−POI・POI−到達点の２つのルートを最短経路探索法で求めればよいので、技術的には既存の技術で解決できる。しかし、寄り道検索では、予めわからないPOIを探索しつつ、できるだけ最短経路に近いような経路を求めることが必要になる。寄り道検索については、ダイクストラ法をベースとした検索方式が提案されている。
【０００８】
以下に、具体的な寄り道検索の手法について説明する。
【０００９】
図１に、従来の寄り道検索しシステムの全体処理のフローチャートを示し、図２に従来のPOIチェック機能の処理のフローチャートを示す。
【００１０】
図２は、図１のＳ５，Ｓ６の「Ｓ側（Ｅ側）で確定したノードがPOIかチェック」の中のフローである。Ｓ側とＥ側のフローは共有される。
【００１１】
図１と図２のフローの基本的な考え方は以下の通りである。
【００１２】
・ダイクストラ法を出発点側（Ｓ側）と到着点側（Ｅ側）の両方から実行する；
・Ｓ側・Ｅ側からそれぞれスタートして、POIに到達したら、当該ノードへの経路を候補テーブルに登録する；
・候補テーブルにＳ側・Ｅ側から同じPOIに到達する経路があれば、それを結果テーブルに登録する；
・以上を終了条件を満たすまで繰り返す。
【００１３】
結果テーブルは、全体のコスト（＝Ｓ側からのコスト＋Ｅ側からのコスト）でソートされている。結果テーブルに含まれる要素の個数をｋ件と予め決めておき、最終的にそのｋ件の結果を返却することによって、最もコストの少ない上位ｋ件の寄り道検索結果を返却することができる。
【００１４】
探索終了条件は、ダイクストラ法で最短経路探索を行う場合はエンドコードが確定（コストが決定）すれば終了してかまわないが、寄り道検索の場合は、その判定法を用いることができない。寄り道検索の場合は、以下のように決定される。
【００１５】
・既にｋ個の解が求められ、以下の条件がＳ側・Ｅ側の両方で成立するとき終了（よりコストの小さいルートは得られない）。
【００１６】
条件：結果テーブルの最大コスト≦候補テーブルの最小コスト＋現在ノードのコスト
・上記条件だけでは、ｋ個の解が見つからないときに終了せずに延々と遠回りして解を探してしまう。よって、コストの現実的な値で上限を設け（例えば、１８０分以内のルートを求める）終了条件とする。
【００１７】
以下に図２の処理を説明する。
【００１８】
ステップ１０１） 当該ノードのカテゴリがユーザによって指定されたカテゴリに一致しているかを判定し、一致していない場合は当該処理を終了する。
【００１９】
ステップ１０２） カテゴリが一致している場合には、反対側（Ｅ側ならばＳ側、Ｓ側ならばＥ側）から当該ノードへの経路が候補テーブルに既に登録されているかを判定し、登録されている場合にはステップ１０３に移行し、登録されていない場合はステップ１０５に移行する。
【００２０】
ステップ１０３） 結果テーブルに当該ノードへの経路と反対側からの経路を組にして登録する。
【００２１】
ステップ１０４） 結果テーブルをコストでソートして当該処理を終了する。
【００２２】
ステップ１０５） 候補テーブルに未登録の場合は、候補テーブルに当該ノードを登録し、当該処理を終了する。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】五十嵐健夫「データ構造とアルゴリズム」（数理工学社,2007）．
【非特許文献２】Neo4j http://now4j.org/
【発明の概要】
【発明が解決しようとする課題】
【００２４】
上記寄り道検索において、寄り道をするときに、寄り道する店が開店していないと意味がない。店の開店時間は１２時〜２２時のように制限がある。この制限を満たすような店を寄り道して欲しい。例えば、夜遅めに出発するときには、閉店前に間に合うように出発点からなるべく近くの場所に寄り道する必要がある。これは開店時間だけでなく、「１２時〜１３時、ランチ２割引」や『１７時以降、閉店前３割引』のような時間限定のタイムセールのときに来店したいという要求と同じ課題であるといえる。このような、時間制約を持つような寄り道検索を「タイムセール寄り道検索」と呼ぶ。上記では、開店時間などのPOIの時間制約を例として挙げたが、「その店で２時間ゆっくりしたい」「銀行でお金をおろすのでぎりぎりに間に合えばよい」と言うような、ユーザにとっての時間的な制約を満たすような検索要求もあり、これらを満たす検索も同様に「タイムセール寄り道検索」と呼ぶ。
【００２５】
タイムセール寄り道検索においては、基本的な時間制約をチェックする手順と条件が課題となる。通常の寄り道検索では全体所要時間は、出発点からPOIまでの所要時間と、POIから到達点までの所要時間を単純に足せばよいが、タイムセール寄り道検索の場合、待ち時間も許容することがサービス的に有効である。POIにサービス開始よりも５分早めに着いたとしても、待ち時間を含めればトータルの所要時間は小さい場合もある。このように、待ちも含めた全体スケジュールを提案できることが課題となる。
【００２６】
寄り道検索の従来手法はダイクストラ法をベースとしているが、ダイクストラ法は貪欲的な特徴を持ち、近傍のノードをすべて展開していく。よって、従来の寄り道検索手法において、全体の所要時間に予め制約をかけることによって、探索の発散を抑止している。この探索範囲の増大と、不自然な制約は大規模で複雑なネットワークに適用する上での課題である。タイムセール寄り道検索においては、時間制約を利用して、探索の範囲を狭められる可能性がある。ダイクストラ法では、所要時間に相当するエッジに与えられる数値をコストと呼ぶことが多いため（所要時間よりは広い意味）、今後、所要時間をコストと呼ぶことがある。
【００２７】
本発明は、上記の点に鑑みなされたもので、ユーザにとっての時間的な制約を満たすような検索要求に対応でき、かつ、待ち時間も含めたスケジューリングが可能な寄り道検索装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２８】
上記の課題を解決するため、本発明（請求項１）は、グラフにおける寄り道の最短経路を求める寄り道検索装置であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースと、
ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、
前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOI（Point Of Interest）チェック手段と、
前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェック手段と、
前記ユーザ・サービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、
を有する。
【００２９】
また、本発明（請求項２）は、前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する・
【発明の効果】
【００３０】
本発明により、ユーザが求める寄り道要求に応えるナビゲーションサービスを実現できる。自分の好みの店を通る経路を求める、ATMの終了時間に間に合うような経路を求める、等のサービスを可能にする。また、探索制限の効果によって、探索範囲を限定し、レスポンスタイムを向上させることができる。但し、探索範囲の制限は、ユーザ指定条件に依存する。例えば、ユーザが非常に緩い条件を指定した場合（極端な例はどんな時間でもよいからサービスを受けたい）、探索範囲の制限の効果はなくなる。しかし、ランチタイム、宴会時間などのように時間が限定される場合、例えば、行きの探索範囲は、大まかにはスタート予定時刻から宴会開始までという範囲に限定され、無秩序な探索は抑制される効果がある。
【図面の簡単な説明】
【００３１】
【図１】従来の寄り道検索装置のフローチャートである。
【図２】従来の寄り道検索装置におけるPOIチェック機能のフローチャートである。
【図３】本発明の一実施の形態における寄り道検索装置の構成図である。
【図４】本発明の一実施の形態におけるタイムセール寄り道検索のフローチャート（方式１）である。
【図５】本発明の一実施の形態におけるユーザ条件とサービス条件の付き合わせ処理のフローチャートである。
【図６】本発明の一実施の形態におけるPOI滞在開始・終了とサービス条件の制約チェックの例である。
【図７】本発明の一実施の形態におけるPOI滞在時間の制約チェックの例である。
【図８】本発明の一実施の形態におけるコスト情報とPOI滞在開始・終了条件の制約チェックの例である。
【図９】本発明の一実施の形態の戦略例における個別値の決定イメージである。
【図１０】本発明の一実施の形態の戦略例における個別値の決定例である。
【図１１】本発明の一実施の形態における調製フェーズのイメージである。
【図１２】本発明の一実施の形態のすぐ出発する戦略における時刻の決定イメージである。
【図１３】本発明の一実施の形態におけるタイムセール寄り道検索のフローチャート（方式２）である。
【図１４】本発明の一実施の形態における方式２のタイムセール寄り道検索のS406の詳細動作のフローチャートである。
【図１５】本発明の一実施の形態における図１３のS404の詳細なフローチャートである。
【図１６】本発明の一実施の形態における条件１〜４のイメージである。
【図１７】本発明の一実施例のグラフの例である。
【図１８】本発明の一実施例のグラフデータベース例である。
【図１９】本発明の一実施例の出発路側のコストテーブルのイメージである。
【図２０】本発明の一実施例の到着路側のコストテーブルのイメージである。
【図２１】本発明の一実施例の候補テーブルと結果テーブルの例である。
【図２２】本発明の一実施例のタイムセール寄り道検索における値の指定例である。
【図２３】本発明の一実施例のコスト情報とPOI滞在開始・終了事件のチェックの例である。
【図２４】本発明の一実施例の全体コストを求めるときの個別値決定フェーズである。
【図２５】本発明の一実施例の決定された個別値である。
【図２６】本発明の一実施例の調整フェーズのイメージである。
【発明を実施するための形態】
【００３２】
以下図面と共に、本発明の実施の形態を説明する。
【００３３】
図３は、本発明の一実施の形態における寄り道検索装置の構成を示す。
【００３４】
同図に示す寄り道検索装置は、コストテーブル１０１、グラフデータベース１０２、ユーザインタフェース部１０５、探索制御部１１０、POIチェック部１２０、コストテーブル更新部１３０、探索終了判定部１４０、ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０、探索結果作成部１７０、探索制限部１８０、グラフＤＢ制御部１９０から構成される。さらに、図示しないが、結果テーブルや候補テーブルを保持するメモリも具備する。
【００３５】
コストテーブル１０１は、探索されたノード、そのノードに至るまでのその時点での最小コスト、そのノードに至る一つ前のエッジの情報を持つ。また、コストテーブル１０１は、出発点から探索されたコストテーブル、到着点から探索されたコストテーブルの２つがある（図１９，２０）。
【００３６】
グラフデータベース１０２は、ノードのID、名前、カテゴリ情報からなるノード情報と、２つのノードIDの組で表現されるノード間の関係とノード間の移動所要時間からなるエッジ情報と、各ノードで実施されるサービスの開始・終了時刻、開店時間やタイムセール等の時間制約情報を、グラフデータモデルの形で二次記憶に永続的に記憶する（図１８）。
【００３７】
ユーザインタフェース部１０５は、ユーザが指定する出発点、到着点、行きたい場所のカテゴリ、時間制約を入力する機能を持つ。詳しくは、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得する。
【００３８】
探索制御部１１０は、ユーザインタフェース部１０５で指定された情報を元に、探索を実行し探索結果を作成するまでの全体の制御を行う。
【００３９】
POIチェック部１２０は、探索の途中で、ユーザが現在いる地点が指定されたカテゴリを満たすかどうか判定する機能を持つ。ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０に問い合わせることにより、「寿司」「銀行」のようなカテゴリと一致していることをチェックし、計算されたコスト情報から、その地点に寄り道したときに所望の条件と合致しているか（開店時間やタイムセールに間に合ったか、２時間ゆっくりできるのか等）を判定する。
【００４０】
コストテーブル更新部１３０は、ユーザが現在いる点の隣の全てのエッジを求め、もし、そのエッジを経由するルートが最小コストであれば、コストテーブル１０１を更新する機能を持つ。
【００４１】
探索終了判定部１４０は、探索を終了してよいのかの判定を行う。判定は、
・出発店からPOIまでの経路と到着点からPOIまでの両方の経路が求められていること；
・事前に設定された個数の経路を導出していること；
・これ以上よりよいコストの経路が求められないこと；
・コストの限界値以下であること；
等を用いて判定を行う。
【００４２】
ユーザ・サービス条件チェック部１５０は、POIチェック部１２０におけるPOIチェック時に、ユーザ条件とサービス条件を照らし合わせて、その矛盾があるかないのかの判定を行う機能を持つ。矛盾がある場合はPOIチェック部１２０にＮＧを返却する。
【００４３】
全体スケジュール算出部１６０は、出発点〜POIの道のり（以降、「出発路」と呼ぶ）、POI〜到着点の道のり（以降、「到着路」と呼ぶ）に掛かるコストと、サービス条件を満たすように補正されたユーザ条件を受け取り、全体のスケジュールを算出する機能を持ち、その結果をPOIチェック部１２０に返却する。
【００４４】
探索結果作成部１７０は、探索終了後に、コストテーブル１０１の情報から、全経路を構成する機能を持つ。終了点のコストテーブルから、順に前のコストテーブル１０１を追っていけば全経路を見つけることができる。
【００４５】
探索制限部１８０は、探索している位置とユーザ条件からそれ以上展開する必要があるかを判定し、不要であれば、コストテーブル１０１のノードのコストを無限大にすることでノードの展開を停止させ、探索を制限する機能を持つ。
【００４６】
グラフＤＢ制御部１９０は、グラフデータベース１０２への検索機能を提供する。提供される機能としては、あるノードから隣のノードを求める、あるエッジの両側のノードを求める、などの基本的なグラフ情報を検索する機能である。
【００４７】
上記の構成のうち、ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０は、単なる寄り道検索ではなく、「タイムセール寄り道検索」を実施するために必要な機能である。太線で示された探索制御部１８０とPOIチェック部１２０は、タイムセール寄り道検索を実施するにあたって、追加された上記のユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０の機能を呼び出すところが従来の技術と異なる点である。なお、タイムセール寄り道検索では当然グラフデータベース１０２にPOIのサービス条件が追加される点で異なる。太い二重線で示された探索制御部１８０は、タイムセール寄り道検索において探索を効率的に実行するために必要な機能である。
【００４８】
＜タイムセール寄り道検索＞
以下に、タイムセール寄り道検索の実現法について説明する。
【００４９】
最初に実現するために必要となる情報の定義について説明する。この情報については、サービス提供側の情報とユーザ側の都合の情報の２種類がある。それぞれを「サービス条件」「ユーザ条件」と呼ぶことにする。最初にサービス条件について説明する。
【００５０】
＜サービス条件＞
・タイムセールの開始時刻：service_start
・タイムセールの終了時刻：service_end
・タイムセールのサービス内容：serice_content
タイムセールの開始時刻、終了時刻はその名とおりの定義であり、ランチサービスならば、"service_start ＝ 11：30・service_end ＝ 14：00"等となる。また、開店時刻、閉店時刻もこの値を使用することとする。
【００５１】
また、以下の例では、電車網を意識した例で説明するが、電車の始発・終電を考慮した検索が可能になっている。電車の始発時刻・終電時刻は、駅を表すノードの"serive_start"と"service_end"であると定義することにする。電車網を検索する場合、本来は時刻表と乗り継ぎの関係も考慮する必要があるが、それは容易であるため、単純化のために、ここでは考慮しないことにする。
【００５２】
"service_content"はタイムセールのサービス内容であり、例えば、『ランチ食べ放題』や、『残り商品全品３割引』、等といった値をとり得る。ユーザが希望するサービス内容を指定することを考えると、例えば、「ランチand ３割引」、等の組合せの指定がある。そのためには、"serivce_content"を構造化し、検索可能にする必要があるが、その方法は容易であるため、ここでは、"serivce_content"は一つの項目として構造化されていないと想定する。
【００５３】
次に、ユーザ条件について定義する。
【００５４】
＜ユーザ条件＞
・出発点を出発する時刻の最大値と最小値をそれぞれかstart_max、start_min；
・POI滞在時間の最大値と最小値を、pos_stay_max、pos_stay_min；
・POI到着時刻の最大値と最小値を、poi_start_max、poi_start_min；
・POI出発時刻の最大値と最小値を、poi_end_max、poi_end_min；
・到着点へ到着する時刻の最大値と最小値を、end_max、end_min;
これらの定義の意味を説明する。出発点の最大値は「できるだけ遅く出発する時刻」、最小値は「できるだけ早く出発する時刻」を意味する。以下にその例を示す。
【００５５】
（１）POIの滞在時間：
・最低１時間はゆっくり食をしたい場合、"poi_stay_min = 60"とする。
【００５６】
・２時間で食事を切り上げたい場合、"poi_stay_max = 120"とする。
【００５７】
・チケット購入のように、窓口に滑り込みで間に合えばよいという場合、"poi_stay_max( = poi_stay_min)= 0"とすればよい。
【００５８】
・POI到着時刻は、食事を遅くとも19:00から始めたい場合は、"poi_start_max = 19:00"とする。
【００５９】
・食事を18:00より前には始めたくない場合は、"poi_start_ min = 18:00"とする。
【００６０】
（２）POI出発時刻：
・食事を２２時には必ず切り上げる場合は、"poi_end_max = 22:00"とする。
【００６１】
・食事を21:00までは必ず時間をかけて食べる場合は、"poi_end_min = 21:00"とする。
【００６２】
（３）到着時刻
・到着する時刻の最大値は、遅くなっても24:00には帰宅したい場合は、"end_max = 24:00"とする。
【００６３】
・23:00にならないと家の鍵が開かないので、それよりも遅く帰る必要があるという場合は、"end_min = 23:00"とする。
【００６４】
タイムセール寄り道検索を実現するためには、ユーザ・サービス条件チェック部１５０において、ユーザ条件とサービス条件が合致するかをチェックしながら探索を行う必要がある。そのチェックの仕方により２つの方式がある。
【００６５】
一つはタイムセール条件を最後にチェックする方式であり、寄り道が完成するタイミングで、タイムセール条件を満たすかどうかチェックする方式である。（請求項１，３に対応）
もう一つは、タイムセール条件を事前にチェックする方式であり、寄り道が完成していない時点でも、タイムセール条件を利用すると探索を停止できるケースがある。その条件を積極的に利用して、事前に探索範囲を狭める方式である。（請求項２、４に対応）
以下に、上記の２つの方式について詳細に説明する。
【００６６】
＜方式１：タイムセール条件を最後にチェックする方式＞
寄り道が完成するのは、POIチェックの処理内であるので、その処理をタイムセールに対応するよう前述の図２のフローを図４のように変更する。
【００６７】
以下に、変更箇所を説明する。なお、図２と同一処理には図２と同一のステップ番号を付与し、その説明を省略する。
【００６８】
ステップ２０１） 両側からのルートが発見された後（ステップ１０２、Yes）に、ユーザ・サービス条件チェック部１５０は、そのルートがタイムセールに関するユーザ条件・サービス条件を満たすかどうかをチェックする。ここで、ユーザ条件とサービス条件をチェックし矛盾する場合には排除される。もし、満足しない場合（例：タイムセール時間内に寄り道できない場合）は、POIチェックはＮＧとなり停止する。ここまでの処理で、行き・帰り・POI滞在の「時間（の長さ）」が決定される。
【００６９】
ステップ２０２） 全体スケジュール算出部１６０は、全体スケジュールを算出し、結果テーブルに登録する。ここでは、待ち時間がある場合も考慮して、出発時刻、経由点出発時刻等の全体スケジュールを求めて、結果テーブルに登録する。通常の寄り道検索では、Ｓ側とＥ側のコストを単純に加えたものであるが、タイムセール寄り道検索の場合は、それでは不十分である。サービスが始まるまで、待たされる可能性があるからである。待ちのあるなしで、コストの順番が逆転する可能性がある。最終的なコストは、出発時刻と到着時刻の差となる。このステップで行きから帰りまでの全ての「時刻」が決定される。
【００７０】
次に、ユーザ・サービス条件チェック１５０による突合せ（比較）について説明する。
【００７１】
図５は、本発明の一実施の形態におけるユーザ条件とサービス条件の突合せ処理のフローチャートである。
【００７２】
ステップ３０１） 最初に、「POI滞在開始・滞在終了条件とサービス条件に矛盾がない」ことをチェックする。図６にその状況を示す。"poi_start"、"poi_end"はそれぞれPOI開始・終了時刻の候補となる「区間」であり、"poi_stay"はPOI滞在時間の「長さ」を表している（最大値がpoi_stay_max、最小値がpoi_stay_min）。"service"はサービス条件を表す区間である。POIの滞在開始と滞在終了はサービス時間に含まれる必要があるため、以下の関係が成り立つ必要がある（サービスは１区間で表現されると仮定している）。
【００７３】
service_start≦poi_start_max
poi_end_min≦service_end
ステップ３０２） 次に、POI滞在開始区間とPOI滞在終了区間を補正する。サービス区間に含まれないPOI滞在開始・終了区間は実質的に除外してよいので、POI滞在開始区間・終了区間とサービス区間で交わりをとり、それを補正されたPOI滞在開始区間・終了区間として今後の処理で使用する（図６の"poi_start'"と"poi_end'"）。
【００７４】
ステップ３０３） 次に「補正されたPOI滞在開始・滞在終了条件とPOI滞在時間に矛盾がない」ことをチェックする。図７にPOI滞在時間と開始時間・終了時間の関係を示す。図７に示すように、滞在時間の長さが滞在開始・終了時間に対して短い場合（ケース１）は矛盾である。OKである条件は以下で表現される。
【００７５】
前者が"poi_stay"が短い場合の排除、後者が"poi_stay"が長い場合の排除である。
【００７６】
poi_end'_min < poi_start'_max + poi_stay_min
poi_start'_min + poi_stay_max ≦ poi_end'_max
ステップ３０４） 次に、コストテーブル１０１とグラフデータベース１０２を参照して、POIまでのコスト情報とPOI滞在情報に矛盾がないかをチェックする。S側からのPOIまでのコストを"cost_s"、E側からPOI案でのコストを"cost_e"とする。図８にそれらの相対関係を示す。制約を満たさないケースとして、行くときのコストが大きすぎてPOI滞在開始に間に合わないケース（ケース１）、帰るときのコストが大きすぎて目的地到着に間に合わないケース（ケース２）がある。また、「待ち」を許容する場合は、ケース３のようにPOIに到着してからPOI滞在開始まで待ったり、POI滞在終了してから、移動するまで待つというケースは許容することができる。
【００７７】
この条件で式を書くと以下のようになる。この条件をチェックする。
【００７８】
start_min + cost_s < poi_start'_max
start_end'_min + cost_e < end_max
また、出発から到着までのトータルの長さが区間の最大幅を超えないようにする必要があるので（ケース５）、以下の条件をチェックする。
【００７９】
cost_s + poi_stay_min + cost_e < end_max - start_min
これでユーザ条件とサービス条件の付き合わせは完了である。
【００８０】
ステップ２０２） 次に、全体スケジュール算出部１６０は、待ち時間を含めた全体スケジュールを算出し、結果テーブルに登録する。この前のステップ２０１のチェックによって、「時間（の長さ）」について矛盾するような条件は排除されているが、これまで与えられた制約では、いつ出発し、POIに滞在し、目的地に到着するという「時刻」は一意には決定されない（全体コストは一意に決まらない）。全体のプランを決定するためには、時間制約を持つ、寄り道検索に対す戦略の知識が必要である。ここでは、代表的な戦略例に基づいて全体プランを決定し、全体コストを求める方法を提示する。この戦略は単純化されており、現実のアプリケーション上必ずしも有効とは限らない。実際にはアプリケーションに適した戦略を実現する必要があるが、それは下記戦略の応用で容易に実現できる。
【００８１】
まず、説明のために幾つかの用語を定義する。
【００８２】
・全体の出発と到着の時刻を、total_start、total_endとする。
【００８３】
・総コスト（出発してから到着するまでの時間をtotal_costとする。
【００８４】
・自明な関係として、total_cost = total_end - total_startが成り立つ（関係１）
・実際にPOIに滞在する時間の開始時刻と終了時刻をそれぞれ、poi_stay_start、poi_stay_endとする（宴会の開始と終了時刻のイメージ）
・POIに到着する時刻と出発する時刻をpoi_arrive、poi_leaveとする。
【００８５】
・自明な関係として、poi_arrive = total_start + cost_sが成り立つ（関係２）。
【００８６】
・自明な関係として、total_end = poi_leave + cost_eが成り立つ（関係３）。
【００８７】
やや用語が紛らわしいが、POIへの滞在とは、POIの店に入っていた時間のイメージであり、POIの到着・出発時刻とは区別をしていることに注意されたい。POIへの滞在を比喩的に理解するために、今後、滞在を「宴会」の開始・終了を例として表現することがある。これからの目標は、戦略に応じて、"total_start"、"poi_arrive"、"poi_stay_start"、"poi_stay_end"、"poi_leave"、"total_end"の６つの値を決定することである（実質的には関係２，３があるので４つ決定すればよい。また、これらが決めれば関係1により"total_cost"も決定する）。以下の例では簡単のために、POIへの滞在時間（宴会時間）は固定であるとする。これは、POI滞在時間の最大値と最小値が等しいことを意味する（この値を"poi_stay"とする）ので、式で表現すると以下が成り立つ。
【００８８】
poi_stay_min = poi_stay_max
＜戦略例＞できるだけ待ちをなくし、かつ早く行動する：
この戦略の特徴を以下に示す。
【００８９】
・できるだけ早く宴会を開始する；
・できるだけ早く帰宅しようとする；
・待ち時間はできるだけ発生させない→出発は宴会開始に近づける；
スケジュールの算出は、「個別値決定フェーズ」と「調整フェーズ」の２つのフェーズによって構成される。
【００９０】
個別値決定フェーズとは、まず、全体としてスケジュールの整合性は無視し、出発時刻（Start）、到着時刻（End）、経由地滞在開始（POI）の３つの値をそれぞれの制約条件を元に決定する。
【００９１】
調整フェーズでは、前に決定された値から全体スケジュールとして矛盾しないような調整を行う。
【００９２】
●個別値決定フェーズ：
図９に個別値決定フェーズのイメージを示す。このフェーズでは、大きく、出発路の区間（S区間。ケース１〜３）、到着路の区間（E区間。ケース１，２）、滞在地の区間（P区間。ケース１，２）の３つの区間を決める。この戦略における出発路区間は、cost_sの値が小さいときは、許容されるぎりぎりの（start_max）に出発し、POI到着後宴会開始まで待つことになる（ケース１）。"cost_s"がだんだん大きくなり待ちが短くなり、"poi_arrive"が"poi_start_min"に到着すると、次に"total_start"が前倒しされる（ケース２）。"total_start"が"start_min"に到達した時点で、"poi_arrive"が後ろにずれていく（ケース３）。"cost_s"の最大値は"poi_start_max - start_min"で、これより大きくなることはない（既にそのケースは事前に除外されている）。
【００９３】
到着路区間は"cost_e"の値が小さいときは、許容されるぎりぎり（end_min）に到着するようにPOIを出発する。宴会終了後POI出発まで待つことになる（ケース１）。"cost_e"がだんだん大きくなり待ちが短くなり、"poi_leave"が"por_end_min"に到達すると、次に、"total_end"が後ろにずれる（ケース２）。"cost_e"の最大値は"end_max - poi_end_min"で、これより大きくなることはない（既にそのケースは事前に除外されている）。
【００９４】
滞在区間は、POI滞在時間（poi_stay）が小さいときは、許容されるぎりぎり(poi_end_min）に収容するように宴会が行われる（ケース１）。POI滞在時間がだんだん大きくなり"poi_stay_start"が"por_start_min"に到達すると、次に"poi_stay_end"が後ろにずれる（ケース２）。POI滞在時間の最大値は"poi_end_max - poi_start_min"で、これより大きくなることはない。
【００９５】
上記の戦略例において決定された個別値を図１０に示す。
【００９６】
●調整フェーズ：
次に、調整フェーズについて説明する。上記のパターンの組合せによって全体が決定されるが、調整が必要な場合として、一般的には以下の２つがある。
【００９７】
・各区間の間に空きがある場合；
・各区間に重なりがある場合；
しかし、POI滞在時間を固定としたために、空きがある場合は、それは待ち時間となり、調整の余地はない。次に、重なりがある場合の解決法を図１１に示す。上記の個別値決定では可能な限り、前倒しになるようにスケジュールが決定されているので、重なりが発生した場合は、後ろの区間を後ろにずらすという対応をすればよい。S区間とP区間が重なったら、P区間を後ろにずらし（調整１後）、更にP区間とE区間が重なったらE区間を後ろにずらす（調整２後）。その結果、"total_end"が"end_max"を超えることがないように事前に除外されている。
【００９８】
上記の戦略例とやや違う戦略の例としては、すぐに出発したいというパターンがある。その場合の時刻決定イメージを図１２に示す。この場合、必ず"start_min"に出発し、早く着いたら待つ、という動きになる。P区間、E区間については上記戦略例をそのまま利用できる。調整フェーズについても同じである。
【００９９】
＜方式２：タイムセール条件を事前にチェックする方式＞
方式２は、タイムセール条件を積極的に利用して、事前に探索範囲を狭める方式である。アルゴリズムの中で、事前に探索範囲を狭められる箇所は、以下の３つの時点である。
【０１００】
・Step1：ノードへの最短距離が確定する時点；
・Step2：POIを発見する時点；
・Step3：POIへの両側からのパスが見つかる時点；
前述の方式１は、最後のチェックタイミングであるStep3で全てのチェックを行う方式であったといえる。上記のStep1〜3のチェックを加えた処理フローを図１３と図１４に示す。図１４は、図１３におけるステップ４０６の「S側（E側）で確定したノードがPOIかチェック」の中でフローである。（S側とE側ではフローは共有される）。
【０１０１】
図１３では、S側、E側それぞれのコスト確定後に（ステップ４０２，４０３の処理後）そのノードに対するチェックを行っている（ステップ４０４）。この時点で探索候補から排除できると、その後のノード展開数を大幅に減らすことができる。ステップ４０４におけるチェックの詳細を図１５に示す。当該処理は探索制限部１８０で行われる。ここでは、S側、E側それぞれの確定ノードに対して、条件チェックを行い、チェックが満たされない場合は（ステップ６０１，６０２、No）、当該ノードのコストを無限大にしている（ステップ６０３）。当該ノードのコストが無限大である場合、そのノードの先はコストが無限大になるので展開されることはない。
【０１０２】
図１４では、当該ノードがPOIであることがわかったら（ステップ５０１、Yes）、次に上記のStep2(POIを発見する時点)のチェックを行う。チェックが満たされない場合は（ステップ５０２、No）、当該ノードは候補テーブルにも、結果テーブルにも追加されることはない。よって、無駄な候補テーブル、結果テーブルの要素を作成する必要がないので、処理量を削減することができる。両側からPOIへのパスが見つかった後に（ステップ５０３、Yes）、Step3（POIへの両側からのパスが見つかる時点）のチェックを行う(ステップ５０５)。これは、前述した方式１のタイミングと同じであり、この条件を満たさない場合は(ステップ５０５、満足しない)、結果テーブルへの登録がキャンセルされる。
【０１０３】
次に、上記のStep1〜3でそれぞれ可能なチェックについてまとめる。全部で７つのチェック条件がある（以下の条件が満たされる場合にOKとなる）。これらのチェックを実現するのが探索制限部１８０となる。
【０１０４】
・条件１：S側から探索し、POIに到達する前に"poi_start"区間を過ぎないこと；
・条件２：E側から探索し、POIに到達する前に"poi_end"区間を過ぎないこと；
・条件３：S側から探索し、そのコストに滞在時間の最小値を加えたとき、"poi_end"区間をすぎないこと；
・条件４：E側から探索し、そのコストに滞在時間の最小値を加えたとき、"poi_start"区間をすぎないこと；
・条件５：図６に示した、POI滞在開始・終了とサービス条件の制約チェック；
・条件６：図７に示した、POI滞在時間の制約チェック；
・条件７：図８に示した、S側からのコスト情報とPOI滞在終了の制約チェック；
・条件８：図８に示した、E側からのコスト情報とPOI滞在終了の制約チェック；
・条件９：図８に示した、全体のコスト情報の制約チェック；
上記の条件１〜４は、POIに到達する前にチェックできるので、Step1でのチェックが可能である。Step1での探索制限部１８０による処理は図１５に示すとおりであり、Step1で修正された例を図１６に示す。一方、条件５〜８は、POIに到達しないとチェックができないが、両側からコストを要求していないので、Step2（POIを発見する時点)でのチェックが可能である。条件９は、両側からのコストが必要なので、Step3(POIへの両側からのパスが見つかる時点)でのチェックが必要である（条件５，６は複数の式、それ以外は一つの式で一つの条件としているが、ここでは、S側、E側、POIの単位で条件としている）。
【０１０５】
上記の条件１〜９を表す式を以下に示す。
【０１０６】
・条件１：start_min + cost_s ≦ pos_start_max
・条件２：poi_endo_min + cost_e ≦ end_max
・条件３：start_min + cost_s + poi_stay_min ≦ poi_end_max
・条件４：poi_start_min ≦ end_max - (cost_e + poi_stay_min)
・条件５：service_start ≦ poi_start_max, poi_end_min ≦ service_end
・条件６：poi_end'_min < poi_start'_max + poi_stay_min,
poi_start'_min +poi_stay_max ≦ poi_end'_max
・条件７：start_min + cost_s ≦ poi_start'_max
・条件８：poi_end'_min + coste ≦ end_max
・条件9：cost_s + poi_stay_min + cost_e < end_max - start_min
探索制限部１８０において、これらの条件をチェックすることにより、探索範囲の絞込みができ、同じ結果を効率よく得ることができる。
【０１０７】
＜終了条件の修正＞
タイムセール寄り道検索では、POI滞在時間を考慮する必要があるため、通常の寄り道検索で使われた以下の終了条件をそのまま使うことができない。
【０１０８】
結果テーブルの最大コスト≦候補テーブルの最小コスト＋現在のノードのコスト
修正された終了条件は以下のようになる。
【０１０９】
POI滞在含む結果の最大コスト≦候補テーブルの最小コスト＋現在ノードのコスト
＋ poi_stay_min
【実施例】
【０１１０】
以下に、本発明の実施例を説明する。
【０１１１】
＜寄り道検索＞
以下に寄り道探索の実施例を説明する。
【０１１２】
例で用いるグラフを図１７に示す。同図において、○と☆はノードであり、☆はPOIであり、○はそれ以外である。Sが出発地で、Eが目的地である。ノード間にはエッジが定義されており、その上の数字はノード間の移動コストを表す（単純化のためにコストの単位は分・時等ではなく何らかの単位時間とする）。このグラフをグラフデータベース１０２として表現した例を図１８に示す。同図の例では、グラフデータベース１０２は関係データベースのような表形式で表現しているが、ノードの関係をポインタで表現したり、関係データベース以外でも実装は可能である。グラフデータベース１０２の機能としては、「ノード名を指定してノードidを取得」、「ノードidを取得してそれに繋がるエッジを取得」等を仮定する。これらは例えば、関係データベースで容易に実装できる。
【０１１３】
寄り道検索を実行した場合のコストテーブル１０１のイメージを図１９（出発路側）、図２０（到着路側）に示す。それぞれ、S、Eを出発点としたダイクストラ探索の実行であり、前述の非特許文献１等に示されている方法と同じである。但し、POIに到達した場合に、候補テーブルにノード（とそこまでのコスト）の登録を行う。例えば、出発路側コストテーブルにおいて、Step３でP１が確定しており、候補として「スタート側から，P1に到達，コストは３」という情報が登録されている。
【０１１４】
図２１に候補テーブルと結果テーブルを示す。例えば、同図中のStep7において、S側とE側に共通するP2というPOIが出現したので、それを結果テーブルに登録している（P2,P+12）。同図の数値が足し算になっているのは、S側からのコストとE側からのコストを後での説明上明記しておくためである。同図に示す結果テーブルはトータルコストでソートされている。よってこの場合の求める寄り道経路は、P１を経由する経路であり、トータルのコストは"１８"である。具体的な経路は、ダイクストラ法と同様の方法で求めることができる（例：各ノードの前のノードを保存しておく）。
【０１１５】
＜タイムセール寄り道検索＞
次に、タイムセール寄り道検索の実施例を示す。
【０１１６】
対象となるグラフは上記と同じ例を利用する。
【０１１７】
各時間の指定例を図２２に示す。数直線は時間を表し、単位はグラフ上のコストと同じ単位であると仮定する。例えば、"start_min"の値は時刻０であり、"poi_start_min"は時刻１３である。これから、時間に関する条件チェックの実施例を説明する。
【０１１８】
まず、「POI滞在開始・終了条件とサービス条件に矛盾がない」チェック（図６）について述べる。
【０１１９】
図２２中にP1〜P5のサービス時間例を示した。この例では、P2の終了が矛盾となっており(poi_end_min ≦ service_endを満たさない)、候補から除外される。サービス条件を加味し、POI滞在開始・終了条件は補正されるが、その例を同じ図中に示してある（P１の例）。数直線としての交わりを求めている。このように補正された区間で以後の議論を続ける必要があるが、今後の議論では簡単のために、P1〜P5のサービス条件を全て、13〜28と仮定し、ここでは補正が発生しない、とする。
【０１２０】
＜「補正されたPOI滞在開始・終了条件とPOI滞在時間に矛盾がない」チェック＞
次に、「補正されたPOI滞在開始・終了条件とPOI滞在時間に矛盾がない」チェック（図７)について述べる。この例では、POI滞在時間が５〜１５（例："poi_stay_min = 5 and poi_stay_max = 15"）であれば、この制約は満たされる。今後は、"poi_stay_min = poi_stay_max = 10"（ちょうど10だけ滞在する）と仮定して説明する。
【０１２１】
「コスト情報とPOI滞在開始・終了条件の矛盾」チェック（図８）について述べる。条件式
start_min + cost_s < poi_start'_max
start_end'_min + cost_e < end_max
cost_s + poi_stay_min + cost_e < end_max - start_min
が満たされるかどうかをチェックする。そのチェックの様子を図２３に示す。例えば、P1において、"start_min + cost_s"は、"poi_start'_max"を超えるので条件を満たさない。この時点で、P5はPOIの候補から除外される。トータルのコストチェックについては、"end_max − stat_min"の値が３８で、"cost_s + poi_stay_min + cost_e"の値が２８〜３６なので満たされる（P5は満たされないが既に除外されている）。
【０１２２】
＜「待ち時間も含めた全体コストを求める」の処理＞
「待ち時間も含めた全体コストを求める」（図１４のS506）の実施例を示す。
【０１２３】
個別値決定フェーズであるが、そのイメージを示した図９を本実施例に適用したものを図２４に示す。ケース１、ケース２等に示した数直線と値は、それぞれの場合のスレッシュホールドとなっている。例えば、S区間のケース１は区間の先頭が時間０〜５の場合であり、ケース２は区間の終点が１３〜１８の場合である。
【０１２４】
実施例に従って、場合を決定して個別の値（total_startとpoi_leave）を決めた結果を図２５に示す。また、P区間についても決定する必要があるが、本実施例では、"poi_stay = 10"であったから、場合はケース１であり、"poi_stay_start"は１０となる。
【０１２５】
調整フェーズの例を図２６に示す。P1，P2，P4は重なりがないので調整の必要がない。P1は出発路で待ちが生じるパターンとなっている。P3は重なりがあるので、後ろにずらして最終的な結果を得る。これらの最終結果から、全体のコスト(total_end − total_start)が求まる。図２６の右端にその値を示す。最小となるのは、P2を経由するケースであることがわる。時間的な制約を考慮しない寄り道検索では、P1を経由する経路が最適解であったが、P1を経由する場合、P1の位置が出発点に近いためにPOIに早く到着してしまい、待ちが発生する。それでP2が逆転している。これは例えて言えば、宴会に丁度よい時間にPOIを訪れることができていないということである。つまり、このタイムセール寄り道検索を用いることによって、興味のある場所に最適な時間に訪れることが可能になる。
【０１２６】
＜方式２：条件評価を先に行う場合＞
最後に方式２（条件評価を先に行う場合）について説明する。
【０１２７】
当該方式２を採用する場合、本実施例においては、図２３でNGとなったP5を最終的なチェックではなく、出発路側の探索でP5に到達した時点で、それ以降の探索を停止することができる。本実施例の図１９では、P5に到達する時点が、step11であるため、ステップ数の削減とはなっていないが、一般的には、展開数を削減することに貢献することができる。
【０１２８】
なお、上記の実施の形態における図３に示す寄り道検索装置の構成要素の動作をプログラムとして構築し、寄り道検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１２９】
本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１３０】
１００ 寄り道検索装置
１０１ コストテーブル
１０２ グラフデータベース
１０５ ユーザインタフェース部
１１０ 探索制御部
１２０ POIチェック部
１３０ コストテーブル更新部
１４０ 探索終了判定部
１５０ ユーザ・サービス条件チェック部
１６０ 全体スケジュール算出部
１７０ 探索結果作成部
１８０ 探索制限部
１９０ グラフデータベース制御部
【技術分野】
【０００１】
本発明は、寄り道検索装置及び方法及びプログラムに係り、特に、交通やグルメ等のインターネット上の検索サービス、カーナビ等のナビゲーションシステム、旅行日程作成支援のような計画作成支援等において、所定の地点を通過する経路のうち、最短の経路を探索するための寄り道検索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフにおける最短経路を求める技術として、ダイクストラ法、A*法等のグラフ探索技術が確立している（例えば、非特許文献１参照）。これらの技術は、ノード間の移動コスト（例：所要時間）が与えられたグラフにおいて、合計コストが最小となる「最短の」経路を求める手法である。この技術は鉄道網や道路網から所望のルートを探索するサービスに活用されている。
【０００３】
一方、ユーザに対して、ユーザの希望や趣向等に応じて、行きたい場所を推薦するレコメンドサービスがある。レコメンドサービスとして、代表的な技術に以下の２つがある。
【０００４】
・位置情報を用いたグルメ情報等の推薦；
・経路探索時の経路の近辺の店・サービスの推薦；
前者は、ユーザがＧＰＳ機能を持つ携帯電話、スマートフォン等を持ち、その位置情報からその近くのユーザの希望や趣向にあった店を推薦するという技術である。
【０００５】
後者は、カーナビ等で、目的地までの経路を検索したときに、その経路沿いのガソリンスタンドやファーストフード店等を表示するような技術である。
【０００６】
グラフ情報を蓄積・検索する手段として、グラフデータベースが提案されている（例えば、非特許文献２参照）。
【０００７】
上記技術と関連するが目的が少し異なる、次のような要求がある。例えば、ユーザがどこかに出張するときに、必ずしも最短経路でなく、多少遠回りしてもよいから、その経路上で自分の好みの昼食をとってから目的地に到達したい、という要求である。この要求を満たす検索を「寄り道検索」と呼ぶことにする。このとき経由する経由地をPOI(Point Of Interest)と呼ぶ。ユーザからは、直接具体的なPOIを指定するのではなく、「寿司が食べたい」とか「銀行に行きたい」というような行きたい場所のカテゴリで指定されることを想定する。具体的なPOIが事前に決まっているのであれば、出発点−POI・POI−到達点の２つのルートを最短経路探索法で求めればよいので、技術的には既存の技術で解決できる。しかし、寄り道検索では、予めわからないPOIを探索しつつ、できるだけ最短経路に近いような経路を求めることが必要になる。寄り道検索については、ダイクストラ法をベースとした検索方式が提案されている。
【０００８】
以下に、具体的な寄り道検索の手法について説明する。
【０００９】
図１に、従来の寄り道検索しシステムの全体処理のフローチャートを示し、図２に従来のPOIチェック機能の処理のフローチャートを示す。
【００１０】
図２は、図１のＳ５，Ｓ６の「Ｓ側（Ｅ側）で確定したノードがPOIかチェック」の中のフローである。Ｓ側とＥ側のフローは共有される。
【００１１】
図１と図２のフローの基本的な考え方は以下の通りである。
【００１２】
・ダイクストラ法を出発点側（Ｓ側）と到着点側（Ｅ側）の両方から実行する；
・Ｓ側・Ｅ側からそれぞれスタートして、POIに到達したら、当該ノードへの経路を候補テーブルに登録する；
・候補テーブルにＳ側・Ｅ側から同じPOIに到達する経路があれば、それを結果テーブルに登録する；
・以上を終了条件を満たすまで繰り返す。
【００１３】
結果テーブルは、全体のコスト（＝Ｓ側からのコスト＋Ｅ側からのコスト）でソートされている。結果テーブルに含まれる要素の個数をｋ件と予め決めておき、最終的にそのｋ件の結果を返却することによって、最もコストの少ない上位ｋ件の寄り道検索結果を返却することができる。
【００１４】
探索終了条件は、ダイクストラ法で最短経路探索を行う場合はエンドコードが確定（コストが決定）すれば終了してかまわないが、寄り道検索の場合は、その判定法を用いることができない。寄り道検索の場合は、以下のように決定される。
【００１５】
・既にｋ個の解が求められ、以下の条件がＳ側・Ｅ側の両方で成立するとき終了（よりコストの小さいルートは得られない）。
【００１６】
条件：結果テーブルの最大コスト≦候補テーブルの最小コスト＋現在ノードのコスト
・上記条件だけでは、ｋ個の解が見つからないときに終了せずに延々と遠回りして解を探してしまう。よって、コストの現実的な値で上限を設け（例えば、１８０分以内のルートを求める）終了条件とする。
【００１７】
以下に図２の処理を説明する。
【００１８】
ステップ１０１） 当該ノードのカテゴリがユーザによって指定されたカテゴリに一致しているかを判定し、一致していない場合は当該処理を終了する。
【００１９】
ステップ１０２） カテゴリが一致している場合には、反対側（Ｅ側ならばＳ側、Ｓ側ならばＥ側）から当該ノードへの経路が候補テーブルに既に登録されているかを判定し、登録されている場合にはステップ１０３に移行し、登録されていない場合はステップ１０５に移行する。
【００２０】
ステップ１０３） 結果テーブルに当該ノードへの経路と反対側からの経路を組にして登録する。
【００２１】
ステップ１０４） 結果テーブルをコストでソートして当該処理を終了する。
【００２２】
ステップ１０５） 候補テーブルに未登録の場合は、候補テーブルに当該ノードを登録し、当該処理を終了する。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】五十嵐健夫「データ構造とアルゴリズム」（数理工学社,2007）．
【非特許文献２】Neo4j http://now4j.org/
【発明の概要】
【発明が解決しようとする課題】
【００２４】
上記寄り道検索において、寄り道をするときに、寄り道する店が開店していないと意味がない。店の開店時間は１２時〜２２時のように制限がある。この制限を満たすような店を寄り道して欲しい。例えば、夜遅めに出発するときには、閉店前に間に合うように出発点からなるべく近くの場所に寄り道する必要がある。これは開店時間だけでなく、「１２時〜１３時、ランチ２割引」や『１７時以降、閉店前３割引』のような時間限定のタイムセールのときに来店したいという要求と同じ課題であるといえる。このような、時間制約を持つような寄り道検索を「タイムセール寄り道検索」と呼ぶ。上記では、開店時間などのPOIの時間制約を例として挙げたが、「その店で２時間ゆっくりしたい」「銀行でお金をおろすのでぎりぎりに間に合えばよい」と言うような、ユーザにとっての時間的な制約を満たすような検索要求もあり、これらを満たす検索も同様に「タイムセール寄り道検索」と呼ぶ。
【００２５】
タイムセール寄り道検索においては、基本的な時間制約をチェックする手順と条件が課題となる。通常の寄り道検索では全体所要時間は、出発点からPOIまでの所要時間と、POIから到達点までの所要時間を単純に足せばよいが、タイムセール寄り道検索の場合、待ち時間も許容することがサービス的に有効である。POIにサービス開始よりも５分早めに着いたとしても、待ち時間を含めればトータルの所要時間は小さい場合もある。このように、待ちも含めた全体スケジュールを提案できることが課題となる。
【００２６】
寄り道検索の従来手法はダイクストラ法をベースとしているが、ダイクストラ法は貪欲的な特徴を持ち、近傍のノードをすべて展開していく。よって、従来の寄り道検索手法において、全体の所要時間に予め制約をかけることによって、探索の発散を抑止している。この探索範囲の増大と、不自然な制約は大規模で複雑なネットワークに適用する上での課題である。タイムセール寄り道検索においては、時間制約を利用して、探索の範囲を狭められる可能性がある。ダイクストラ法では、所要時間に相当するエッジに与えられる数値をコストと呼ぶことが多いため（所要時間よりは広い意味）、今後、所要時間をコストと呼ぶことがある。
【００２７】
本発明は、上記の点に鑑みなされたもので、ユーザにとっての時間的な制約を満たすような検索要求に対応でき、かつ、待ち時間も含めたスケジューリングが可能な寄り道検索装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２８】
上記の課題を解決するため、本発明（請求項１）は、グラフにおける寄り道の最短経路を求める寄り道検索装置であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースと、
ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、
前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOI（Point Of Interest）チェック手段と、
前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェック手段と、
前記ユーザ・サービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、
を有する。
【００２９】
また、本発明（請求項２）は、前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する・
【発明の効果】
【００３０】
本発明により、ユーザが求める寄り道要求に応えるナビゲーションサービスを実現できる。自分の好みの店を通る経路を求める、ATMの終了時間に間に合うような経路を求める、等のサービスを可能にする。また、探索制限の効果によって、探索範囲を限定し、レスポンスタイムを向上させることができる。但し、探索範囲の制限は、ユーザ指定条件に依存する。例えば、ユーザが非常に緩い条件を指定した場合（極端な例はどんな時間でもよいからサービスを受けたい）、探索範囲の制限の効果はなくなる。しかし、ランチタイム、宴会時間などのように時間が限定される場合、例えば、行きの探索範囲は、大まかにはスタート予定時刻から宴会開始までという範囲に限定され、無秩序な探索は抑制される効果がある。
【図面の簡単な説明】
【００３１】
【図１】従来の寄り道検索装置のフローチャートである。
【図２】従来の寄り道検索装置におけるPOIチェック機能のフローチャートである。
【図３】本発明の一実施の形態における寄り道検索装置の構成図である。
【図４】本発明の一実施の形態におけるタイムセール寄り道検索のフローチャート（方式１）である。
【図５】本発明の一実施の形態におけるユーザ条件とサービス条件の付き合わせ処理のフローチャートである。
【図６】本発明の一実施の形態におけるPOI滞在開始・終了とサービス条件の制約チェックの例である。
【図７】本発明の一実施の形態におけるPOI滞在時間の制約チェックの例である。
【図８】本発明の一実施の形態におけるコスト情報とPOI滞在開始・終了条件の制約チェックの例である。
【図９】本発明の一実施の形態の戦略例における個別値の決定イメージである。
【図１０】本発明の一実施の形態の戦略例における個別値の決定例である。
【図１１】本発明の一実施の形態における調製フェーズのイメージである。
【図１２】本発明の一実施の形態のすぐ出発する戦略における時刻の決定イメージである。
【図１３】本発明の一実施の形態におけるタイムセール寄り道検索のフローチャート（方式２）である。
【図１４】本発明の一実施の形態における方式２のタイムセール寄り道検索のS406の詳細動作のフローチャートである。
【図１５】本発明の一実施の形態における図１３のS404の詳細なフローチャートである。
【図１６】本発明の一実施の形態における条件１〜４のイメージである。
【図１７】本発明の一実施例のグラフの例である。
【図１８】本発明の一実施例のグラフデータベース例である。
【図１９】本発明の一実施例の出発路側のコストテーブルのイメージである。
【図２０】本発明の一実施例の到着路側のコストテーブルのイメージである。
【図２１】本発明の一実施例の候補テーブルと結果テーブルの例である。
【図２２】本発明の一実施例のタイムセール寄り道検索における値の指定例である。
【図２３】本発明の一実施例のコスト情報とPOI滞在開始・終了事件のチェックの例である。
【図２４】本発明の一実施例の全体コストを求めるときの個別値決定フェーズである。
【図２５】本発明の一実施例の決定された個別値である。
【図２６】本発明の一実施例の調整フェーズのイメージである。
【発明を実施するための形態】
【００３２】
以下図面と共に、本発明の実施の形態を説明する。
【００３３】
図３は、本発明の一実施の形態における寄り道検索装置の構成を示す。
【００３４】
同図に示す寄り道検索装置は、コストテーブル１０１、グラフデータベース１０２、ユーザインタフェース部１０５、探索制御部１１０、POIチェック部１２０、コストテーブル更新部１３０、探索終了判定部１４０、ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０、探索結果作成部１７０、探索制限部１８０、グラフＤＢ制御部１９０から構成される。さらに、図示しないが、結果テーブルや候補テーブルを保持するメモリも具備する。
【００３５】
コストテーブル１０１は、探索されたノード、そのノードに至るまでのその時点での最小コスト、そのノードに至る一つ前のエッジの情報を持つ。また、コストテーブル１０１は、出発点から探索されたコストテーブル、到着点から探索されたコストテーブルの２つがある（図１９，２０）。
【００３６】
グラフデータベース１０２は、ノードのID、名前、カテゴリ情報からなるノード情報と、２つのノードIDの組で表現されるノード間の関係とノード間の移動所要時間からなるエッジ情報と、各ノードで実施されるサービスの開始・終了時刻、開店時間やタイムセール等の時間制約情報を、グラフデータモデルの形で二次記憶に永続的に記憶する（図１８）。
【００３７】
ユーザインタフェース部１０５は、ユーザが指定する出発点、到着点、行きたい場所のカテゴリ、時間制約を入力する機能を持つ。詳しくは、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得する。
【００３８】
探索制御部１１０は、ユーザインタフェース部１０５で指定された情報を元に、探索を実行し探索結果を作成するまでの全体の制御を行う。
【００３９】
POIチェック部１２０は、探索の途中で、ユーザが現在いる地点が指定されたカテゴリを満たすかどうか判定する機能を持つ。ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０に問い合わせることにより、「寿司」「銀行」のようなカテゴリと一致していることをチェックし、計算されたコスト情報から、その地点に寄り道したときに所望の条件と合致しているか（開店時間やタイムセールに間に合ったか、２時間ゆっくりできるのか等）を判定する。
【００４０】
コストテーブル更新部１３０は、ユーザが現在いる点の隣の全てのエッジを求め、もし、そのエッジを経由するルートが最小コストであれば、コストテーブル１０１を更新する機能を持つ。
【００４１】
探索終了判定部１４０は、探索を終了してよいのかの判定を行う。判定は、
・出発店からPOIまでの経路と到着点からPOIまでの両方の経路が求められていること；
・事前に設定された個数の経路を導出していること；
・これ以上よりよいコストの経路が求められないこと；
・コストの限界値以下であること；
等を用いて判定を行う。
【００４２】
ユーザ・サービス条件チェック部１５０は、POIチェック部１２０におけるPOIチェック時に、ユーザ条件とサービス条件を照らし合わせて、その矛盾があるかないのかの判定を行う機能を持つ。矛盾がある場合はPOIチェック部１２０にＮＧを返却する。
【００４３】
全体スケジュール算出部１６０は、出発点〜POIの道のり（以降、「出発路」と呼ぶ）、POI〜到着点の道のり（以降、「到着路」と呼ぶ）に掛かるコストと、サービス条件を満たすように補正されたユーザ条件を受け取り、全体のスケジュールを算出する機能を持ち、その結果をPOIチェック部１２０に返却する。
【００４４】
探索結果作成部１７０は、探索終了後に、コストテーブル１０１の情報から、全経路を構成する機能を持つ。終了点のコストテーブルから、順に前のコストテーブル１０１を追っていけば全経路を見つけることができる。
【００４５】
探索制限部１８０は、探索している位置とユーザ条件からそれ以上展開する必要があるかを判定し、不要であれば、コストテーブル１０１のノードのコストを無限大にすることでノードの展開を停止させ、探索を制限する機能を持つ。
【００４６】
グラフＤＢ制御部１９０は、グラフデータベース１０２への検索機能を提供する。提供される機能としては、あるノードから隣のノードを求める、あるエッジの両側のノードを求める、などの基本的なグラフ情報を検索する機能である。
【００４７】
上記の構成のうち、ユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０は、単なる寄り道検索ではなく、「タイムセール寄り道検索」を実施するために必要な機能である。太線で示された探索制御部１８０とPOIチェック部１２０は、タイムセール寄り道検索を実施するにあたって、追加された上記のユーザ・サービス条件チェック部１５０、全体スケジュール算出部１６０の機能を呼び出すところが従来の技術と異なる点である。なお、タイムセール寄り道検索では当然グラフデータベース１０２にPOIのサービス条件が追加される点で異なる。太い二重線で示された探索制御部１８０は、タイムセール寄り道検索において探索を効率的に実行するために必要な機能である。
【００４８】
＜タイムセール寄り道検索＞
以下に、タイムセール寄り道検索の実現法について説明する。
【００４９】
最初に実現するために必要となる情報の定義について説明する。この情報については、サービス提供側の情報とユーザ側の都合の情報の２種類がある。それぞれを「サービス条件」「ユーザ条件」と呼ぶことにする。最初にサービス条件について説明する。
【００５０】
＜サービス条件＞
・タイムセールの開始時刻：service_start
・タイムセールの終了時刻：service_end
・タイムセールのサービス内容：serice_content
タイムセールの開始時刻、終了時刻はその名とおりの定義であり、ランチサービスならば、"service_start ＝ 11：30・service_end ＝ 14：00"等となる。また、開店時刻、閉店時刻もこの値を使用することとする。
【００５１】
また、以下の例では、電車網を意識した例で説明するが、電車の始発・終電を考慮した検索が可能になっている。電車の始発時刻・終電時刻は、駅を表すノードの"serive_start"と"service_end"であると定義することにする。電車網を検索する場合、本来は時刻表と乗り継ぎの関係も考慮する必要があるが、それは容易であるため、単純化のために、ここでは考慮しないことにする。
【００５２】
"service_content"はタイムセールのサービス内容であり、例えば、『ランチ食べ放題』や、『残り商品全品３割引』、等といった値をとり得る。ユーザが希望するサービス内容を指定することを考えると、例えば、「ランチand ３割引」、等の組合せの指定がある。そのためには、"serivce_content"を構造化し、検索可能にする必要があるが、その方法は容易であるため、ここでは、"serivce_content"は一つの項目として構造化されていないと想定する。
【００５３】
次に、ユーザ条件について定義する。
【００５４】
＜ユーザ条件＞
・出発点を出発する時刻の最大値と最小値をそれぞれかstart_max、start_min；
・POI滞在時間の最大値と最小値を、pos_stay_max、pos_stay_min；
・POI到着時刻の最大値と最小値を、poi_start_max、poi_start_min；
・POI出発時刻の最大値と最小値を、poi_end_max、poi_end_min；
・到着点へ到着する時刻の最大値と最小値を、end_max、end_min;
これらの定義の意味を説明する。出発点の最大値は「できるだけ遅く出発する時刻」、最小値は「できるだけ早く出発する時刻」を意味する。以下にその例を示す。
【００５５】
（１）POIの滞在時間：
・最低１時間はゆっくり食をしたい場合、"poi_stay_min = 60"とする。
【００５６】
・２時間で食事を切り上げたい場合、"poi_stay_max = 120"とする。
【００５７】
・チケット購入のように、窓口に滑り込みで間に合えばよいという場合、"poi_stay_max( = poi_stay_min)= 0"とすればよい。
【００５８】
・POI到着時刻は、食事を遅くとも19:00から始めたい場合は、"poi_start_max = 19:00"とする。
【００５９】
・食事を18:00より前には始めたくない場合は、"poi_start_ min = 18:00"とする。
【００６０】
（２）POI出発時刻：
・食事を２２時には必ず切り上げる場合は、"poi_end_max = 22:00"とする。
【００６１】
・食事を21:00までは必ず時間をかけて食べる場合は、"poi_end_min = 21:00"とする。
【００６２】
（３）到着時刻
・到着する時刻の最大値は、遅くなっても24:00には帰宅したい場合は、"end_max = 24:00"とする。
【００６３】
・23:00にならないと家の鍵が開かないので、それよりも遅く帰る必要があるという場合は、"end_min = 23:00"とする。
【００６４】
タイムセール寄り道検索を実現するためには、ユーザ・サービス条件チェック部１５０において、ユーザ条件とサービス条件が合致するかをチェックしながら探索を行う必要がある。そのチェックの仕方により２つの方式がある。
【００６５】
一つはタイムセール条件を最後にチェックする方式であり、寄り道が完成するタイミングで、タイムセール条件を満たすかどうかチェックする方式である。（請求項１，３に対応）
もう一つは、タイムセール条件を事前にチェックする方式であり、寄り道が完成していない時点でも、タイムセール条件を利用すると探索を停止できるケースがある。その条件を積極的に利用して、事前に探索範囲を狭める方式である。（請求項２、４に対応）
以下に、上記の２つの方式について詳細に説明する。
【００６６】
＜方式１：タイムセール条件を最後にチェックする方式＞
寄り道が完成するのは、POIチェックの処理内であるので、その処理をタイムセールに対応するよう前述の図２のフローを図４のように変更する。
【００６７】
以下に、変更箇所を説明する。なお、図２と同一処理には図２と同一のステップ番号を付与し、その説明を省略する。
【００６８】
ステップ２０１） 両側からのルートが発見された後（ステップ１０２、Yes）に、ユーザ・サービス条件チェック部１５０は、そのルートがタイムセールに関するユーザ条件・サービス条件を満たすかどうかをチェックする。ここで、ユーザ条件とサービス条件をチェックし矛盾する場合には排除される。もし、満足しない場合（例：タイムセール時間内に寄り道できない場合）は、POIチェックはＮＧとなり停止する。ここまでの処理で、行き・帰り・POI滞在の「時間（の長さ）」が決定される。
【００６９】
ステップ２０２） 全体スケジュール算出部１６０は、全体スケジュールを算出し、結果テーブルに登録する。ここでは、待ち時間がある場合も考慮して、出発時刻、経由点出発時刻等の全体スケジュールを求めて、結果テーブルに登録する。通常の寄り道検索では、Ｓ側とＥ側のコストを単純に加えたものであるが、タイムセール寄り道検索の場合は、それでは不十分である。サービスが始まるまで、待たされる可能性があるからである。待ちのあるなしで、コストの順番が逆転する可能性がある。最終的なコストは、出発時刻と到着時刻の差となる。このステップで行きから帰りまでの全ての「時刻」が決定される。
【００７０】
次に、ユーザ・サービス条件チェック１５０による突合せ（比較）について説明する。
【００７１】
図５は、本発明の一実施の形態におけるユーザ条件とサービス条件の突合せ処理のフローチャートである。
【００７２】
ステップ３０１） 最初に、「POI滞在開始・滞在終了条件とサービス条件に矛盾がない」ことをチェックする。図６にその状況を示す。"poi_start"、"poi_end"はそれぞれPOI開始・終了時刻の候補となる「区間」であり、"poi_stay"はPOI滞在時間の「長さ」を表している（最大値がpoi_stay_max、最小値がpoi_stay_min）。"service"はサービス条件を表す区間である。POIの滞在開始と滞在終了はサービス時間に含まれる必要があるため、以下の関係が成り立つ必要がある（サービスは１区間で表現されると仮定している）。
【００７３】
service_start≦poi_start_max
poi_end_min≦service_end
ステップ３０２） 次に、POI滞在開始区間とPOI滞在終了区間を補正する。サービス区間に含まれないPOI滞在開始・終了区間は実質的に除外してよいので、POI滞在開始区間・終了区間とサービス区間で交わりをとり、それを補正されたPOI滞在開始区間・終了区間として今後の処理で使用する（図６の"poi_start'"と"poi_end'"）。
【００７４】
ステップ３０３） 次に「補正されたPOI滞在開始・滞在終了条件とPOI滞在時間に矛盾がない」ことをチェックする。図７にPOI滞在時間と開始時間・終了時間の関係を示す。図７に示すように、滞在時間の長さが滞在開始・終了時間に対して短い場合（ケース１）は矛盾である。OKである条件は以下で表現される。
【００７５】
前者が"poi_stay"が短い場合の排除、後者が"poi_stay"が長い場合の排除である。
【００７６】
poi_end'_min < poi_start'_max + poi_stay_min
poi_start'_min + poi_stay_max ≦ poi_end'_max
ステップ３０４） 次に、コストテーブル１０１とグラフデータベース１０２を参照して、POIまでのコスト情報とPOI滞在情報に矛盾がないかをチェックする。S側からのPOIまでのコストを"cost_s"、E側からPOI案でのコストを"cost_e"とする。図８にそれらの相対関係を示す。制約を満たさないケースとして、行くときのコストが大きすぎてPOI滞在開始に間に合わないケース（ケース１）、帰るときのコストが大きすぎて目的地到着に間に合わないケース（ケース２）がある。また、「待ち」を許容する場合は、ケース３のようにPOIに到着してからPOI滞在開始まで待ったり、POI滞在終了してから、移動するまで待つというケースは許容することができる。
【００７７】
この条件で式を書くと以下のようになる。この条件をチェックする。
【００７８】
start_min + cost_s < poi_start'_max
start_end'_min + cost_e < end_max
また、出発から到着までのトータルの長さが区間の最大幅を超えないようにする必要があるので（ケース５）、以下の条件をチェックする。
【００７９】
cost_s + poi_stay_min + cost_e < end_max - start_min
これでユーザ条件とサービス条件の付き合わせは完了である。
【００８０】
ステップ２０２） 次に、全体スケジュール算出部１６０は、待ち時間を含めた全体スケジュールを算出し、結果テーブルに登録する。この前のステップ２０１のチェックによって、「時間（の長さ）」について矛盾するような条件は排除されているが、これまで与えられた制約では、いつ出発し、POIに滞在し、目的地に到着するという「時刻」は一意には決定されない（全体コストは一意に決まらない）。全体のプランを決定するためには、時間制約を持つ、寄り道検索に対す戦略の知識が必要である。ここでは、代表的な戦略例に基づいて全体プランを決定し、全体コストを求める方法を提示する。この戦略は単純化されており、現実のアプリケーション上必ずしも有効とは限らない。実際にはアプリケーションに適した戦略を実現する必要があるが、それは下記戦略の応用で容易に実現できる。
【００８１】
まず、説明のために幾つかの用語を定義する。
【００８２】
・全体の出発と到着の時刻を、total_start、total_endとする。
【００８３】
・総コスト（出発してから到着するまでの時間をtotal_costとする。
【００８４】
・自明な関係として、total_cost = total_end - total_startが成り立つ（関係１）
・実際にPOIに滞在する時間の開始時刻と終了時刻をそれぞれ、poi_stay_start、poi_stay_endとする（宴会の開始と終了時刻のイメージ）
・POIに到着する時刻と出発する時刻をpoi_arrive、poi_leaveとする。
【００８５】
・自明な関係として、poi_arrive = total_start + cost_sが成り立つ（関係２）。
【００８６】
・自明な関係として、total_end = poi_leave + cost_eが成り立つ（関係３）。
【００８７】
やや用語が紛らわしいが、POIへの滞在とは、POIの店に入っていた時間のイメージであり、POIの到着・出発時刻とは区別をしていることに注意されたい。POIへの滞在を比喩的に理解するために、今後、滞在を「宴会」の開始・終了を例として表現することがある。これからの目標は、戦略に応じて、"total_start"、"poi_arrive"、"poi_stay_start"、"poi_stay_end"、"poi_leave"、"total_end"の６つの値を決定することである（実質的には関係２，３があるので４つ決定すればよい。また、これらが決めれば関係1により"total_cost"も決定する）。以下の例では簡単のために、POIへの滞在時間（宴会時間）は固定であるとする。これは、POI滞在時間の最大値と最小値が等しいことを意味する（この値を"poi_stay"とする）ので、式で表現すると以下が成り立つ。
【００８８】
poi_stay_min = poi_stay_max
＜戦略例＞できるだけ待ちをなくし、かつ早く行動する：
この戦略の特徴を以下に示す。
【００８９】
・できるだけ早く宴会を開始する；
・できるだけ早く帰宅しようとする；
・待ち時間はできるだけ発生させない→出発は宴会開始に近づける；
スケジュールの算出は、「個別値決定フェーズ」と「調整フェーズ」の２つのフェーズによって構成される。
【００９０】
個別値決定フェーズとは、まず、全体としてスケジュールの整合性は無視し、出発時刻（Start）、到着時刻（End）、経由地滞在開始（POI）の３つの値をそれぞれの制約条件を元に決定する。
【００９１】
調整フェーズでは、前に決定された値から全体スケジュールとして矛盾しないような調整を行う。
【００９２】
●個別値決定フェーズ：
図９に個別値決定フェーズのイメージを示す。このフェーズでは、大きく、出発路の区間（S区間。ケース１〜３）、到着路の区間（E区間。ケース１，２）、滞在地の区間（P区間。ケース１，２）の３つの区間を決める。この戦略における出発路区間は、cost_sの値が小さいときは、許容されるぎりぎりの（start_max）に出発し、POI到着後宴会開始まで待つことになる（ケース１）。"cost_s"がだんだん大きくなり待ちが短くなり、"poi_arrive"が"poi_start_min"に到着すると、次に"total_start"が前倒しされる（ケース２）。"total_start"が"start_min"に到達した時点で、"poi_arrive"が後ろにずれていく（ケース３）。"cost_s"の最大値は"poi_start_max - start_min"で、これより大きくなることはない（既にそのケースは事前に除外されている）。
【００９３】
到着路区間は"cost_e"の値が小さいときは、許容されるぎりぎり（end_min）に到着するようにPOIを出発する。宴会終了後POI出発まで待つことになる（ケース１）。"cost_e"がだんだん大きくなり待ちが短くなり、"poi_leave"が"por_end_min"に到達すると、次に、"total_end"が後ろにずれる（ケース２）。"cost_e"の最大値は"end_max - poi_end_min"で、これより大きくなることはない（既にそのケースは事前に除外されている）。
【００９４】
滞在区間は、POI滞在時間（poi_stay）が小さいときは、許容されるぎりぎり(poi_end_min）に収容するように宴会が行われる（ケース１）。POI滞在時間がだんだん大きくなり"poi_stay_start"が"por_start_min"に到達すると、次に"poi_stay_end"が後ろにずれる（ケース２）。POI滞在時間の最大値は"poi_end_max - poi_start_min"で、これより大きくなることはない。
【００９５】
上記の戦略例において決定された個別値を図１０に示す。
【００９６】
●調整フェーズ：
次に、調整フェーズについて説明する。上記のパターンの組合せによって全体が決定されるが、調整が必要な場合として、一般的には以下の２つがある。
【００９７】
・各区間の間に空きがある場合；
・各区間に重なりがある場合；
しかし、POI滞在時間を固定としたために、空きがある場合は、それは待ち時間となり、調整の余地はない。次に、重なりがある場合の解決法を図１１に示す。上記の個別値決定では可能な限り、前倒しになるようにスケジュールが決定されているので、重なりが発生した場合は、後ろの区間を後ろにずらすという対応をすればよい。S区間とP区間が重なったら、P区間を後ろにずらし（調整１後）、更にP区間とE区間が重なったらE区間を後ろにずらす（調整２後）。その結果、"total_end"が"end_max"を超えることがないように事前に除外されている。
【００９８】
上記の戦略例とやや違う戦略の例としては、すぐに出発したいというパターンがある。その場合の時刻決定イメージを図１２に示す。この場合、必ず"start_min"に出発し、早く着いたら待つ、という動きになる。P区間、E区間については上記戦略例をそのまま利用できる。調整フェーズについても同じである。
【００９９】
＜方式２：タイムセール条件を事前にチェックする方式＞
方式２は、タイムセール条件を積極的に利用して、事前に探索範囲を狭める方式である。アルゴリズムの中で、事前に探索範囲を狭められる箇所は、以下の３つの時点である。
【０１００】
・Step1：ノードへの最短距離が確定する時点；
・Step2：POIを発見する時点；
・Step3：POIへの両側からのパスが見つかる時点；
前述の方式１は、最後のチェックタイミングであるStep3で全てのチェックを行う方式であったといえる。上記のStep1〜3のチェックを加えた処理フローを図１３と図１４に示す。図１４は、図１３におけるステップ４０６の「S側（E側）で確定したノードがPOIかチェック」の中でフローである。（S側とE側ではフローは共有される）。
【０１０１】
図１３では、S側、E側それぞれのコスト確定後に（ステップ４０２，４０３の処理後）そのノードに対するチェックを行っている（ステップ４０４）。この時点で探索候補から排除できると、その後のノード展開数を大幅に減らすことができる。ステップ４０４におけるチェックの詳細を図１５に示す。当該処理は探索制限部１８０で行われる。ここでは、S側、E側それぞれの確定ノードに対して、条件チェックを行い、チェックが満たされない場合は（ステップ６０１，６０２、No）、当該ノードのコストを無限大にしている（ステップ６０３）。当該ノードのコストが無限大である場合、そのノードの先はコストが無限大になるので展開されることはない。
【０１０２】
図１４では、当該ノードがPOIであることがわかったら（ステップ５０１、Yes）、次に上記のStep2(POIを発見する時点)のチェックを行う。チェックが満たされない場合は（ステップ５０２、No）、当該ノードは候補テーブルにも、結果テーブルにも追加されることはない。よって、無駄な候補テーブル、結果テーブルの要素を作成する必要がないので、処理量を削減することができる。両側からPOIへのパスが見つかった後に（ステップ５０３、Yes）、Step3（POIへの両側からのパスが見つかる時点）のチェックを行う(ステップ５０５)。これは、前述した方式１のタイミングと同じであり、この条件を満たさない場合は(ステップ５０５、満足しない)、結果テーブルへの登録がキャンセルされる。
【０１０３】
次に、上記のStep1〜3でそれぞれ可能なチェックについてまとめる。全部で７つのチェック条件がある（以下の条件が満たされる場合にOKとなる）。これらのチェックを実現するのが探索制限部１８０となる。
【０１０４】
・条件１：S側から探索し、POIに到達する前に"poi_start"区間を過ぎないこと；
・条件２：E側から探索し、POIに到達する前に"poi_end"区間を過ぎないこと；
・条件３：S側から探索し、そのコストに滞在時間の最小値を加えたとき、"poi_end"区間をすぎないこと；
・条件４：E側から探索し、そのコストに滞在時間の最小値を加えたとき、"poi_start"区間をすぎないこと；
・条件５：図６に示した、POI滞在開始・終了とサービス条件の制約チェック；
・条件６：図７に示した、POI滞在時間の制約チェック；
・条件７：図８に示した、S側からのコスト情報とPOI滞在終了の制約チェック；
・条件８：図８に示した、E側からのコスト情報とPOI滞在終了の制約チェック；
・条件９：図８に示した、全体のコスト情報の制約チェック；
上記の条件１〜４は、POIに到達する前にチェックできるので、Step1でのチェックが可能である。Step1での探索制限部１８０による処理は図１５に示すとおりであり、Step1で修正された例を図１６に示す。一方、条件５〜８は、POIに到達しないとチェックができないが、両側からコストを要求していないので、Step2（POIを発見する時点)でのチェックが可能である。条件９は、両側からのコストが必要なので、Step3(POIへの両側からのパスが見つかる時点)でのチェックが必要である（条件５，６は複数の式、それ以外は一つの式で一つの条件としているが、ここでは、S側、E側、POIの単位で条件としている）。
【０１０５】
上記の条件１〜９を表す式を以下に示す。
【０１０６】
・条件１：start_min + cost_s ≦ pos_start_max
・条件２：poi_endo_min + cost_e ≦ end_max
・条件３：start_min + cost_s + poi_stay_min ≦ poi_end_max
・条件４：poi_start_min ≦ end_max - (cost_e + poi_stay_min)
・条件５：service_start ≦ poi_start_max, poi_end_min ≦ service_end
・条件６：poi_end'_min < poi_start'_max + poi_stay_min,
poi_start'_min +poi_stay_max ≦ poi_end'_max
・条件７：start_min + cost_s ≦ poi_start'_max
・条件８：poi_end'_min + coste ≦ end_max
・条件9：cost_s + poi_stay_min + cost_e < end_max - start_min
探索制限部１８０において、これらの条件をチェックすることにより、探索範囲の絞込みができ、同じ結果を効率よく得ることができる。
【０１０７】
＜終了条件の修正＞
タイムセール寄り道検索では、POI滞在時間を考慮する必要があるため、通常の寄り道検索で使われた以下の終了条件をそのまま使うことができない。
【０１０８】
結果テーブルの最大コスト≦候補テーブルの最小コスト＋現在のノードのコスト
修正された終了条件は以下のようになる。
【０１０９】
POI滞在含む結果の最大コスト≦候補テーブルの最小コスト＋現在ノードのコスト
＋ poi_stay_min
【実施例】
【０１１０】
以下に、本発明の実施例を説明する。
【０１１１】
＜寄り道検索＞
以下に寄り道探索の実施例を説明する。
【０１１２】
例で用いるグラフを図１７に示す。同図において、○と☆はノードであり、☆はPOIであり、○はそれ以外である。Sが出発地で、Eが目的地である。ノード間にはエッジが定義されており、その上の数字はノード間の移動コストを表す（単純化のためにコストの単位は分・時等ではなく何らかの単位時間とする）。このグラフをグラフデータベース１０２として表現した例を図１８に示す。同図の例では、グラフデータベース１０２は関係データベースのような表形式で表現しているが、ノードの関係をポインタで表現したり、関係データベース以外でも実装は可能である。グラフデータベース１０２の機能としては、「ノード名を指定してノードidを取得」、「ノードidを取得してそれに繋がるエッジを取得」等を仮定する。これらは例えば、関係データベースで容易に実装できる。
【０１１３】
寄り道検索を実行した場合のコストテーブル１０１のイメージを図１９（出発路側）、図２０（到着路側）に示す。それぞれ、S、Eを出発点としたダイクストラ探索の実行であり、前述の非特許文献１等に示されている方法と同じである。但し、POIに到達した場合に、候補テーブルにノード（とそこまでのコスト）の登録を行う。例えば、出発路側コストテーブルにおいて、Step３でP１が確定しており、候補として「スタート側から，P1に到達，コストは３」という情報が登録されている。
【０１１４】
図２１に候補テーブルと結果テーブルを示す。例えば、同図中のStep7において、S側とE側に共通するP2というPOIが出現したので、それを結果テーブルに登録している（P2,P+12）。同図の数値が足し算になっているのは、S側からのコストとE側からのコストを後での説明上明記しておくためである。同図に示す結果テーブルはトータルコストでソートされている。よってこの場合の求める寄り道経路は、P１を経由する経路であり、トータルのコストは"１８"である。具体的な経路は、ダイクストラ法と同様の方法で求めることができる（例：各ノードの前のノードを保存しておく）。
【０１１５】
＜タイムセール寄り道検索＞
次に、タイムセール寄り道検索の実施例を示す。
【０１１６】
対象となるグラフは上記と同じ例を利用する。
【０１１７】
各時間の指定例を図２２に示す。数直線は時間を表し、単位はグラフ上のコストと同じ単位であると仮定する。例えば、"start_min"の値は時刻０であり、"poi_start_min"は時刻１３である。これから、時間に関する条件チェックの実施例を説明する。
【０１１８】
まず、「POI滞在開始・終了条件とサービス条件に矛盾がない」チェック（図６）について述べる。
【０１１９】
図２２中にP1〜P5のサービス時間例を示した。この例では、P2の終了が矛盾となっており(poi_end_min ≦ service_endを満たさない)、候補から除外される。サービス条件を加味し、POI滞在開始・終了条件は補正されるが、その例を同じ図中に示してある（P１の例）。数直線としての交わりを求めている。このように補正された区間で以後の議論を続ける必要があるが、今後の議論では簡単のために、P1〜P5のサービス条件を全て、13〜28と仮定し、ここでは補正が発生しない、とする。
【０１２０】
＜「補正されたPOI滞在開始・終了条件とPOI滞在時間に矛盾がない」チェック＞
次に、「補正されたPOI滞在開始・終了条件とPOI滞在時間に矛盾がない」チェック（図７)について述べる。この例では、POI滞在時間が５〜１５（例："poi_stay_min = 5 and poi_stay_max = 15"）であれば、この制約は満たされる。今後は、"poi_stay_min = poi_stay_max = 10"（ちょうど10だけ滞在する）と仮定して説明する。
【０１２１】
「コスト情報とPOI滞在開始・終了条件の矛盾」チェック（図８）について述べる。条件式
start_min + cost_s < poi_start'_max
start_end'_min + cost_e < end_max
cost_s + poi_stay_min + cost_e < end_max - start_min
が満たされるかどうかをチェックする。そのチェックの様子を図２３に示す。例えば、P1において、"start_min + cost_s"は、"poi_start'_max"を超えるので条件を満たさない。この時点で、P5はPOIの候補から除外される。トータルのコストチェックについては、"end_max − stat_min"の値が３８で、"cost_s + poi_stay_min + cost_e"の値が２８〜３６なので満たされる（P5は満たされないが既に除外されている）。
【０１２２】
＜「待ち時間も含めた全体コストを求める」の処理＞
「待ち時間も含めた全体コストを求める」（図１４のS506）の実施例を示す。
【０１２３】
個別値決定フェーズであるが、そのイメージを示した図９を本実施例に適用したものを図２４に示す。ケース１、ケース２等に示した数直線と値は、それぞれの場合のスレッシュホールドとなっている。例えば、S区間のケース１は区間の先頭が時間０〜５の場合であり、ケース２は区間の終点が１３〜１８の場合である。
【０１２４】
実施例に従って、場合を決定して個別の値（total_startとpoi_leave）を決めた結果を図２５に示す。また、P区間についても決定する必要があるが、本実施例では、"poi_stay = 10"であったから、場合はケース１であり、"poi_stay_start"は１０となる。
【０１２５】
調整フェーズの例を図２６に示す。P1，P2，P4は重なりがないので調整の必要がない。P1は出発路で待ちが生じるパターンとなっている。P3は重なりがあるので、後ろにずらして最終的な結果を得る。これらの最終結果から、全体のコスト(total_end − total_start)が求まる。図２６の右端にその値を示す。最小となるのは、P2を経由するケースであることがわる。時間的な制約を考慮しない寄り道検索では、P1を経由する経路が最適解であったが、P1を経由する場合、P1の位置が出発点に近いためにPOIに早く到着してしまい、待ちが発生する。それでP2が逆転している。これは例えて言えば、宴会に丁度よい時間にPOIを訪れることができていないということである。つまり、このタイムセール寄り道検索を用いることによって、興味のある場所に最適な時間に訪れることが可能になる。
【０１２６】
＜方式２：条件評価を先に行う場合＞
最後に方式２（条件評価を先に行う場合）について説明する。
【０１２７】
当該方式２を採用する場合、本実施例においては、図２３でNGとなったP5を最終的なチェックではなく、出発路側の探索でP5に到達した時点で、それ以降の探索を停止することができる。本実施例の図１９では、P5に到達する時点が、step11であるため、ステップ数の削減とはなっていないが、一般的には、展開数を削減することに貢献することができる。
【０１２８】
なお、上記の実施の形態における図３に示す寄り道検索装置の構成要素の動作をプログラムとして構築し、寄り道検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１２９】
本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１３０】
１００ 寄り道検索装置
１０１ コストテーブル
１０２ グラフデータベース
１０５ ユーザインタフェース部
１１０ 探索制御部
１２０ POIチェック部
１３０ コストテーブル更新部
１４０ 探索終了判定部
１５０ ユーザ・サービス条件チェック部
１６０ 全体スケジュール算出部
１７０ 探索結果作成部
１８０ 探索制限部
１９０ グラフデータベース制御部
【特許請求の範囲】
【請求項１】
グラフにおける寄り道の最短経路を求める寄り道検索装置であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースと、
ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、
前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOI（Point Of Interest）チェック手段と、
前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェック手段と、
前記ユーザ・サービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、
を有することを特徴とする寄り道検索装置。
【請求項２】
前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する
請求項１記載の寄り道探索装置。
【請求項３】
グラフにおける寄り道の最短経路を求める寄り道検索方法であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースを有する装置において、
ユーザインタフェース手段が、ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザ入力ステップと、
POI（Point Of Interest）チェック手段が、前記ユーザ入力ステップで入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOIチェックステップと、
ユーザ・サービス条件チェック手段が、前記POIチェックステップで取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェックステップと、
全体スケジュール算出手段が、前記ユーザ・サービス条件チェックにおいて排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出ステップと、
を有することを特徴とする寄り道検索方法。
【請求項４】
前記POIチェックステップの実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限ステップを更に行う
請求項３記載の寄り道探索方法。
【請求項５】
コンピュータを、
請求項１または２に記載の寄り道検索装置の各手段として機能させるための寄り道検索プログラム。
【請求項１】
グラフにおける寄り道の最短経路を求める寄り道検索装置であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースと、
ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザインタフェース手段と、
前記ユーザインタフェース手段で入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOI（Point Of Interest）チェック手段と、
前記POIチェック手段で取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェック手段と、
前記ユーザ・サービス条件チェック手段で排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出手段と、
を有することを特徴とする寄り道検索装置。
【請求項２】
前記POIチェック手段の実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限手段を更に有する
請求項１記載の寄り道探索装置。
【請求項３】
グラフにおける寄り道の最短経路を求める寄り道検索方法であって、
ノードのID、名前、カテゴリ情報を持つノード情報と、２つのノードIDの組で表現されるノード間の関係と該ノード間の移動所要時間を持つエッジ情報からなるグラフ情報と、ノードで実施されるサービスの開始・終了時刻とサービス内容を格納したグラフデータベースを有する装置において、
ユーザインタフェース手段が、ユーザから指定された、出発点、到達点、経由点を含むカテゴリ情報と、出発点での出発時刻の最大値及び最小値、該経由点での滞在時間の最大値及び最小値、該経由点での到着時刻の最大値及び最小値、該経由点での出発時刻の最大値及び最小値、該到達点での到着時刻の最大値及び最小値を含むユーザ指定時間条件を取得するユーザ入力ステップと、
POI（Point Of Interest）チェック手段が、前記ユーザ入力ステップで入力された前記カテゴリ情報に合致する経由点を、前記グラフデータベースを参照して取得するPOIチェックステップと、
ユーザ・サービス条件チェック手段が、前記POIチェックステップで取得した前記経由点のうち、前記ユーザから指定された情報とサービス時間条件に合致しない経由点を排除するユーザ・サービス条件チェックステップと、
全体スケジュール算出手段が、前記ユーザ・サービス条件チェックにおいて排除されていない経由点について、ユーザ指定時間条件を満たし、出発点出発時刻、経由点到着時刻、経由点滞在時刻、経由点滞在終了時刻、経由点出発時刻、到達点到着時刻、及び待ち時間を含むスケジュールを生成し、該経由点においてサービスを受け、全体として最小の所要時間で、前記出発点から該経由点を経由し、前記到達点に至るルートを検索する全体スケジュール算出ステップと、
を有することを特徴とする寄り道検索方法。
【請求項４】
前記POIチェックステップの実施前に、前記ユーザの指定する条件に合致しない経由点を処理対象から除外する探索制限ステップを更に行う
請求項３記載の寄り道探索方法。
【請求項５】
コンピュータを、
請求項１または２に記載の寄り道検索装置の各手段として機能させるための寄り道検索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１２−２４２１８３（Ｐ２０１２−２４２１８３Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１０８４５（Ｐ２０１１−１１０８４５）
【出願日】平成２３年５月１７日（２０１１．５．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月１７日（２０１１．５．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]