経路案内装置、経路案内方法、経路案内プログラム、及び経路案内システム
【課題】出発地点から終着地点までの経路の探索を行った際に、探索された経路に含ませる拠点をコントロールすることで、拠点の広告主に対して広告への動機付けを与える。
【解決手段】入力受付部１０１は、ユーザから出発地点、到着地点、及び希望到着時刻の入力を受け付ける。拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルを参照し、１又は複数の拠点の評価の高さを示す拠点評価情報を取得する。経路探索部２０３は、拠点評価情報の高い拠点が多く含まれ、ユーザの移動距離が短く、拠点の個数が多く、かつ、時間的制約が満たされるほど高い評価値を算出し、評価値が高くなるように最適経路を探索する。表示部１０３は、サーバ２００による探索結果を地図画像に重畳して表示する。
【解決手段】入力受付部１０１は、ユーザから出発地点、到着地点、及び希望到着時刻の入力を受け付ける。拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルを参照し、１又は複数の拠点の評価の高さを示す拠点評価情報を取得する。経路探索部２０３は、拠点評価情報の高い拠点が多く含まれ、ユーザの移動距離が短く、拠点の個数が多く、かつ、時間的制約が満たされるほど高い評価値を算出し、評価値が高くなるように最適経路を探索する。表示部１０３は、サーバ２００による探索結果を地図画像に重畳して表示する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザから訪問を希望する終着地点を入力させ、その終着地点までの最適経路をユーザに案内する技術に関するものである。
【背景技術】
【０００２】
近年、スマートフォンの普及に伴い、スマートフォンにユーザを目的地点までナビゲートさせるナビゲーションシステムのニーズが高まっている。また、種々の制約条件の下、ユーザを目的地点まで効率良くナビゲートする経路探索アルゴリズムも開発されている。
【０００３】
例えば、特許文献１には、ユーザに訪問を希望する複数の目的地点及びこれらの目的地点への希望到着時刻等の時間的制約を入力させ、遺伝的アルゴリズムを用いてこれらの目的地点を通り、かつ、時間的制約を満たすような最短経路をユーザに報知する経路探索アルゴリズムが開示されている。
【０００４】
そこで、このような経路探索アルゴリズムとスマートフォンとを結びつけた新たなビジネスモデルが模索されている。特許文献２には、チケット販売時にイベント会場への推奨到着時刻と推奨経路とをユーザに報知するチケット販売支援機能を有するナビゲーションシステムが開示されている。
【０００５】
ところで、近年、スマートフォンやインターネット上で種々のサービスを提供するソフトウェア事業者は、ソフトウェア自体の収入ではなく、ユーザがソフトウェアを使用した際に広告を掲載し、広告主から広告費を募ることで収入を得るのが一般的である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第４２９２０６２号公報
【特許文献２】特開２００９−８５４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献２では、ユーザにとって便利な情報が提供されるかも知れないが、広告主に広告への動機付けを与えるような措置が何ら採用されていない。
【０００８】
本発明の目的は、出発地点から終着地点までの経路の探索を行った際に、探索された経路に含ませる拠点をコントロールすることで、拠点の広告主に対して広告への動機付けを与える経路案内装置等を提供することである。
【課題を解決するための手段】
【０００９】
（１）本発明による経路案内装置は、観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、任意の２拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する。
【００１０】
この構成によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報を設定することによって拠点を探索経路に含ませるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。なお、拠点としては、観光地の他、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、その他施設等を採用することができる。また、到着地点を、出発地点と同じに設定とすることで、到着地点の入力を省かせてもよい。また、本発明による経路案内方法、経路案内プログラム、及び経路案内システムは上記の経路案内装置と同様の構成を持っている。
【００１１】
（２）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得することが好ましい。
【００１２】
この構成によれば、広告費情報が高い拠点ほど拠点評価情報が上昇する。その結果、広告費の高い拠点ほど最適経路に含まれる確率を高くすることができる。
【００１３】
（３）前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得することが好ましい。
【００１４】
この構成によれば、関心度が高い拠点ほど拠点評価情報が高くなる結果、最適経路に含まれる確率を高くすることができる。
【００１５】
（４）前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得することが好ましい。
【００１６】
この構成によれば、ユーザが訪問を強く希望する拠点を最適経路に優先的に含ませることができる。
【００１７】
（５）前記入力受付部は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付け、前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出することが好ましい。
【００１８】
この構成によれば、出発地点及び終着地点とは別にユーザが訪問を希望する目的地点を考慮に入れて最適経路を探索することができる。
【００１９】
（６）前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付けることが好ましい。
【００２０】
この構成によれば、ユーザに対して出発地点及び出発時刻の入力を省かせることができる。なお、本構成において、到着時刻を、現在時刻から一定時間後の時刻とすることで、到着時刻の入力を省かせてもよい。
【００２１】
（７）前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備えることが好ましい。
【００２２】
この構成によれば、拠点が最適経路に含まれた実績に基づいた広告費を算出することができる。その結果、拠点が最適経路に含まれた実績がないないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。
【００２３】
（８）前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出することが好ましい。
【００２４】
広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなることもある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。
【００２５】
（９）前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示すことが好ましい。
【００２６】
この構成によれば、一定期間における広告費が上限広告費を超えた場合、対象となる広告主に対して上限広告費以上の広告費が請求されることを防止することができる。
【００２７】
（１０）前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記広告費情報を考慮せずに前記評価値を算出することが好ましい。
【００２８】
この構成によれば、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。
【００２９】
（１１）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う１回あたりの広告費の目安値に応じた値であることが好ましい。
【００３０】
この構成によれば、拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値を広告主に予め定めさせ、その目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができる。そのため、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。
【００３１】
（１２）前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知することが好ましい。
【００３２】
この構成によれば、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、広告主からより高い広告費を得ることができる。
【００３３】
（１３）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出することが好ましい。
【００３４】
この構成によれば、広告費情報を高く設定した拠点を含む探索経路の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。
【００３５】
（１４）前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、前記経路探索部は、前記広告費情報が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行することが好ましい。
【００３６】
この構成によれば、オフセット値を加えるか否かが抽選処理により決定されているため、広告費情報の低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。
【００３７】
（１５）前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させることが好ましい。
【００３８】
この構成によれば、ユーザが特典を行使するための情報を広告主の所持する端末装置に認識させ、行使が許可された場合にユーザに特典を行使させる構成を採用することができる。これにより、ユーザに対して特典を行使するための情報を拠点の広告主に提示しようとするインセンティブを働かせることができる。また、広告主は、実際にユーザが拠点を訪問したか否かを管理することができる。
【００３９】
（１６）前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。
【００４０】
この構成によれば、広告主が所持する端末装置から特典行使情報をサーバに送信させることで、各拠点対するユーザの訪問履歴をサーバ側で管理することが可能となる。
【００４１】
（１７）前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。
【００４２】
この構成によれば、ユーザ端末から特典行使情報をサーバに送信させることで、各ユーザの拠点の訪問履歴をサーバ側で管理することが可能となる。そのため、広告主は端末装置を準備することなく、ユーザの拠点への訪問回数を管理することができる。
【００４３】
（１８）前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信することが好ましい。
【００４４】
この構成によれば、ユーザは自己の履歴を閲覧することができるため、実際に訪れた拠点や各拠点の訪問回数を認識し、思い出を記録することができる。
【００４５】
（１９）前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信することが好ましい。
【００４６】
この構成によれば、広告が閲覧され、実際にユーザにより訪問された回数を認識することができる。
【００４７】
（２０）前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出することが好ましい。
【００４８】
この構成によれば、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとることができる。
【００４９】
（２１）前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信することが好ましい。
【００５０】
この構成によれば、ユーザが特典を行使した拠点が記録されているため、サーバはユーザが特典を行使した拠点、つまり訪問したことがある拠点についての情報（例えばサービス情報やプロモーション情報）をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。
【００５１】
（２２）前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理し、各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信するサーバを備えることが好ましい。
【００５２】
この構成によれば、ユーザが訪問を希望する拠点についての訪問の希望の高さを示す訪問希望度が記録されているため、サーバはユーザが訪問を希望する拠点についての情報（例えばサービス情報やプロモーション情報）をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。
【発明の効果】
【００５３】
本発明によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報によって拠点を探索経路に含まれるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施の形態による経路案内装置の全体構成図である。
【図２】本発明の実施の形態による経路案内装置の構成を示す機能ブロック図である。
【図３】本発明の実施の形態による経路案内装置の処理を示すフローチャートである。
【図４】（Ａ）は探索対象エリア周辺の地図画像であり、（Ｂ）は拠点に関するデータを示した表である。
【図５】（Ａ）は、関心度及び訪問希望度のみ考慮したときの探索結果を示している。（Ｂ）は、関心度及び訪問希望度に加えて広告費情報を考慮した場合の探索結果を示している。
【図６】テーブル記憶部に記憶された各種テーブルの一例を示した図である。
【図７】ユーザ端末と広告主端末との処理を示すフローチャートである。
【図８】ユーザ端末とサーバとがユーザによる特典の行使を管理するための処理を示すフローチャートである。
【発明を実施するための形態】
【００５５】
以下、本発明の実施の形態による経路案内装置について図面を参照して説明する。図１は、本発明の実施の形態による経路案内装置の全体構成図である。経路案内装置は、端末装置１００及びサーバ２００を含んでいる。端末装置１００は、例えば、スマートフォンやタブレット端末等の携帯型の情報端末装置により構成されている。サーバ２００は、一般的なコンピュータ或いはコンピュータ群（クラウドコンピュータ）により構成されている。
【００５６】
端末装置１００及びサーバ２００は通信網ＮＴを介して相互に通信可能に接続されている。通信網ＮＴとしては、携帯電話網、及びインターネット通信網により構成されている。端末装置１００及びサーバ２００には例えばＩＰアドレス等の固有の通信ＩＤが割り振られ、端末装置１００及びサーバ２００はこの通信ＩＤを用いて、例えばＴＣＰ／ＩＰ等の通信プロトコルを用いて相互に通信を行う。
【００５７】
端末装置１００は、ユーザから訪問を希望する目的地点、終着地点、及び終着地点の希望到着時刻等の入力を受け付け、通信網ＮＴを介してサーバ２００に送信する。サーバ２００は、端末装置１００から送信された目的地点、終着地点、及び終着地点の希望到着時刻を考慮に入れた最適経路の探索を行い、探索結果を端末装置１００に送信する。端末装置１００はサーバ２００により探索された最適経路を表示し、最適経路をユーザに報知する。
【００５８】
そして、本実施の形態では、サーバ２００は、各拠点を評価するための拠点評価情報が高い拠点ほど最短経路に加えられる回数が増大するように最適経路を探索することを特徴としている。拠点評価情報としては、広告費の高さを示す広告費情報、第三者による各拠点の関心の高さを示す関心度、及び、各ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を用いて算出される値が採用される。広告費情報としては広告主による広告費の目安値が採用され、目安値の一例としては広告費の希望単価があげられる。拠点としては、観光地、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、及びその他施設等が該当する。
【００５９】
以下、本実施の形態による経路案内装置の詳細について説明する。図２は、本発明の実施の形態による経路案内装置の構成を示す機能ブロック図である。端末装置１００は、入力受付部１０１、位置情報取得部１０２、表示部１０３（報知部の一例）、通信部１０４、及び地図情報記憶部１０５を備えている。
【００６０】
入力受付部１０１は、例えば、タッチパネル、及びタッチパネルにより検出されたデータを処理するＣＰＵ等により構成され、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける。また、入力受付部１０１は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付ける。ここで、入力受付部１０１は、位置情報取得部１０２により取得されたユーザの現在位置を中心として所定範囲内にある地図画像を地図情報記憶部１０５から読み出して表示部１０３に表示する。そして、入力受付部１０１は、表示部１０３に表示された地図画像において、出発地点、終着地点、及び目的地点をタッチさせ、出発地点、終着地点、及び目的地点を入力させる。以下、“出発地点”、“終着地点”、及び“目的地点”を総称する場合は、“入力地点”と記述する。
【００６１】
なお、入力受付部１０１は、位置情報取得部１０２により取得されたユーザの現在位置を出発地点として取得し、かつ、位置情報取得部１０２により取得された現在時刻を出発時刻として取得してもよい。この場合、ユーザは出発地点及び出発時刻を入力する手間が省かれる。
【００６２】
地図画像は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。
【００６３】
したがって、入力受付部１０１は、ユーザが表示部１０３をタッチしたときのタッチ位置に表示されている地図画像の場所の緯度及び経度を特定する。そして、入力受付部１０１は、特定した緯度及び経度に場所の名称が対応付けられている場合は、その名称をユーザが入力した入力地点として認識する。そして、入力受付部１０１は、特定した場所の緯度、経度、及び名称を示すデータ群を該当する入力地点の入力地点情報として生成する。
【００６４】
また、入力受付部１０１は、特定した緯度及び経度に場所の名称が対応付けられていない場合は、近傍に位置する名称が対応付けられている場所を特定し、“特定した場所の周辺”（例えば、“県立博物館の周辺”）をユーザが入力した入力地点として認識する。この場合、“緯度”、“経度”、及び“特定した場所の周辺”からなるデータ群が入力地点情報として生成される。
【００６５】
次に、入力受付部１０１は、ユーザが入力した入力地点のうち、どの入力地点が終着地点であるかをユーザに指定させるための入力画像を表示部１０３に表示させる。そして、入力受付部１０１は、その入力画像により指定された１の入力地点を終着地点として認識する。そして、入力受付部１０１は、認識した終着地点についての希望到着時刻の入力をユーザに促す入力画像を表示部１０３に表示させ、希望等着地点を入力させる。
【００６６】
位置情報取得部１０２は、ユーザの現在位置及び現在時刻を特定する。ここで、位置情報取得部１０２は、例えばＧＰＳセンサ、及びＧＰＳセンサにより検出されたデータを処理するＣＰＵ等を含み、ＧＰＳセンサにより検出された位置情報をユーザの現在位置として取得すればよい。ここで、現在位置としては、例えば緯度及び経度が採用される。
【００６７】
また、位置情報取得部１０２は、時計を含み、ユーザの現在位置を取得した時刻を現在時刻として取得すればよい。以下の説明では、位置情報取得部１０２が取得した現在位置及び現在時刻を出発地点及び出発時刻として採用するものとする。
【００６８】
通信部１０４は、例えば、通信回路、及び通信回路を制御するＣＰＵ等から構成され、入力受付部１０１により生成された入力地点情報及び端末装置１００を使用しているユーザのユーザＩＤを探索条件データとして生成し、サーバ２００に送信する。
【００６９】
例えば、入力受付部１０１が入力地点として、Ａ、Ｂ、Ｃを取得し、Ａが出発地点、Ｂが目的地点、及びＣが終着地点として指定された場合、Ａの入力地点情報は、（“ユーザの現在位置”，“Ａの名称”，“現在時刻”，出発地点）となり、Ｂの入力地点情報は（“Ｂの緯度及び経度”，“Ｂの名称”，目的地点）となり、Ｃの入力地点情報は、（“Ｃの緯度及び経度”，“Ｃの名称”，“希望到着時刻：００：００”，終着地点）となる。したがって、この場合に送信される探索条件データは、例えば（“Ａの入力地点情報”，“Ｂの入力地点情報”，“Ｃの入力地点情報”、“ユーザＩＤ”）となる。
【００７０】
表示部１０３は、例えばタッチパネル、及びタッチパネルを制御するＣＰＵ等により構成され、サーバ２００により探索された最適経路や、地図画像等を表示する。具体的には、表示部１０３は、サーバ２００から探索結果を示す探索結果データを受信すると、探索結果が示す最適経路を地図画像に重畳して表示する。
【００７１】
また、本実施の形態では、実際にユーザが本経路案内装置により探索された最適経路を使用して拠点を訪れたかどうかを拠点の広告主が確かめるために、そのようにして訪れたユーザに対して広告主が特典を付与することができる。この場合、ユーザは端末装置１００を所持して、端末装置１００によるナビゲーションに従って拠点を訪れる。このときに、ユーザの所持する端末装置１００に特典を意味するＱＲコードを表示させる。そして、広告主の所持する端末装置に備えられたカメラでこのＱＲコードを読み取らせる。広告主の所持する端末装置は、ユーザの提示したＱＲコードを解読することで、このＱＲコードが正規のものであることを確認する。これにより、広告主の所持する端末装置は、ユーザが本経路案内装置により実際に拠点を訪れたか否かを認識することできる。なお、広告主の所持する端末装置としては、スマートフォンでも良い。また、両者の端末間の通信方式としてＱＲコード以外の他の通信方式を利用してもよい。
【００７２】
サーバ２００は、各拠点のＱＲコードを予め後述するテーブル記憶部２０７に記憶させ、後述する探索結果データに最適経路に含まれる拠点のＱＲコードを含ませて、端末装置１００に送信すればよい。
【００７３】
サーバ２００は、データ取得部２０１、拠点評価情報取得部２０２、経路探索部２０３、報知制御部２０４（報知部の一例）、探索結果管理部２０５、広告費算出部２０６、テーブル記憶部２０７、地図情報記憶部２０８、探索履歴記憶部２０９、通信部２１０、及び距離取得部２１１を備えている。ここで、データ取得部２０１〜広告費算出部２０６、及び距離取得部２１１は主にＣＰＵにより構成され、テーブル記憶部２０７〜探索履歴記憶部２０９は主に記憶装置により構成され、通信部２１０は主に通信回路により構成されている。
【００７４】
データ取得部２０１は、１又は複数の拠点について広告主から支払われる広告費情報を取得する。本実施の形態では、広告費情報としては、例えばある拠点の広告主から当該拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値が採用される。具体的には、広告費情報としては、目安値の最大値を満点（例えば、５点）としたときの各拠点の目安値の割合が採用される。目安値としては、例えば１００円、２００円というように、探索経路に１回含まれた際に広告主が支払うことを希望する金額を採用すればよい。また、目安値の最大値が１０００円であり、ある拠点の目安値が１００円とすると、５×（１００／１０００）／５を目安値の割合として採用すればよい。
【００７５】
本実施の形態では、広告主の拠点が最適経路に含まれた実際の回数に応じて広告費を徴収する形態を採用している。この場合、拠点が最適経路に含まれた回数が広告主の意思に反して多かったり、少なかったりすることは好ましくない。そこで、本経路案内装置を運営する運営主は、拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値を広告主に予め定めさせている。これにより、広告費の目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができ、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。
【００７６】
したがって、データ取得部２０１は、広告主端末３００からアクセスされると、目安値の入力を促す入力画像を広告主端末３００に表示させ、この入力画像を通じて目安値を入力させ、サーバ２００に目安値を送信させることで、目安値を取得する。この際、データ取得部２０１は、目安値と併せて、広告主を識別するための広告主ＩＤ、拠点の名称、及び位置情報を送信させる。位置情報としては、拠点の場所を示す緯度及び経度を採用すればよい。
【００７７】
そして、データ取得部２０１は、その拠点に対してその拠点を一意的に識別するため拠点ＩＤを付与し、拠点ＩＤと拠点の名称と拠点の位置情報とを対応付けて図６に示す拠点情報テーブル（拠点情報記憶部の一例）に書き込む。また、データ取得部２０１は、取得した広告費情報を広告主ＩＤと拠点ＩＤと対応付けて図６に示す広告費情報テーブルに書き込む。
【００７８】
図６に示すように、拠点情報テーブルには、拠点ごとに１つのレコードが割り当てられ、各レコードに拠点ＩＤ、拠点の名称、及び位置情報が対応付けて格納されていることが分かる。また、広告費情報テーブルには、広告主ごとに１つのレコードが割り当てられ、各レコードに広告主ＩＤ、拠点ＩＤ、及び広告費情報が対応付けられて格納されていることが分かる。
【００７９】
なお、上記の広告費情報の取得方法は一例にすぎず、他の方法を用いても良い。例えば、運営主が広告主から広告主ＩＤ、拠点の名称、位置情報、及び広告費情報を直接聞き出し、入力装置を用いてサーバ２００に入力することで、データ取得部２０１にこれらの情報を取得させてもよい。
【００８０】
また、データ取得部２０１は、通信網ＮＴに存在するＷＥＢサーバにより運営されている口コミサイトにおいて、第三者がある拠点を紹介するために書き込んだ情報である口コミ情報を取得する。具体的には、データ取得部２０１は、通信網ＮＴ上の口コミサイトを探索し、探索した口コミサイトのＨＴＭＬデータを定期的に取得し、取得したＨＴＭＬデータを分析することで、口コミ情報を書き込んだユーザを特定し、当該ユーザにユーザＩＤを付与し、付与したユーザＩＤとそのユーザが書き込んだ口コミ情報とを対応付けて図６に示す口コミテーブルに書き込む。
【００８１】
そして、データ取得部２０１は、図６に示す口コミテーブルを分析し、各拠点の口コミ情報の平均評価点数（以下、“口コミ点数”と記述する。）を取得し、取得した口コミ点数を関心度とし、拠点ＩＤと対応付けて図６に示す関心度テーブルに書き込む。図６に示すように、関心度テーブルには、拠点ごとに１つのレコードが割り当てられ、拠点ＩＤ及び関心度が対応付けて格納されていることが分かる。
【００８２】
口コミ情報は、例えば、ある拠点に対する書き込み数が多いほど、その拠点に対する第三者の関心は高いと言える。
【００８３】
そこで、本実施の形態では、口コミサイトを監視し、監視結果から各拠点の口コミ情報の口コミ点数を取得し、取得した口コミ点数を各拠点の関心度として採用している。
【００８４】
なお、口コミ点数は、（口コミ情報の書き込みを行った各ユーザが付けた点数（例えば５点満点の点数）の全ユーザの和）／（書き込みを行ったユーザ数）で計算される。例えば、ある拠点に対して書き込みを行ったユーザがＡ，Ｂ，Ｃ，Ｄとして、それぞれが、その拠点に対して４点、５点、４点、３点をつけたとすると、口コミ点数は（４＋５＋４＋３）／４＝４点と算出される。
【００８５】
ここで、データ取得部２０１は、口コミ情報を分析して特定した拠点が拠点情報テーブルに格納されていない新規の拠点である場合、その拠点に拠点ＩＤを付与し、地図情報を参照し、その拠点の名称からその拠点の位置情報を取得し、拠点ＩＤと拠点の名称と位置情報とを対応付けて拠点情報テーブルにも書き込む。
【００８６】
なお、関心度として、口コミ点数を採用したが、本発明はこれに限定されず、第三者が拠点を評価する指標であれば、どのような指標を採用してもよい。例えば、テレビ、新聞等で紹介される拠点ランキングをオペレータが集計し、その集計結果に基づいて関心度を設定してもよい。
【００８７】
また、データ取得部２０１は、本経路案内装置を使用するユーザのユーザＩＤと、そのユーザが訪問を希望する拠点についての希望の度合いを示す訪問希望度とを取得し、拠点ＩＤとユーザＩＤと訪問希望度とを対応付けて図６に示す訪問希望テーブルに書き込む。
【００８８】
ここで、データ取得部２０１は、例えば、ユーザが本経路案内装置を初めて使用する場合にユーザ登録を行わせ、そのときにユーザＩＤと訪問希望度とを取得すればよい。なお、訪問希望度としては、ユーザが訪問を希望する拠点についての拠点別の希望度合いを例えば所定満点で点数表示したデータを採用すればよい。また、訪問希望度は、ユーザ登録後にユーザが適宜設定できるようにしてもよい。
【００８９】
図６に示す用に訪問希望テーブルは、拠点ＩＤのそれぞれについて各ユーザＩＤと訪問希望とを対応付けて格納している。例えば、拠点Ａにつき、ユーザＵ１，Ｕ２，Ｕ３がそれぞれ、１，２，３という訪問希望度を指定した場合、拠点Ａの拠点ＩＤのレコードには、ユーザＵ１，Ｕ２，Ｕ３の各ユーザＩＤと、それぞれの訪問希望度である１，２，３とが対応付けて格納される。
【００９０】
ここで、データ取得部２０１は、ユーザが訪問を希望した拠点が拠点情報テーブルに格納されていない場合、その拠点に対して拠点ＩＤを付与し、地図情報を参照して位置情報を取得し、その拠点の名称から拠点ＩＤと拠点の名称と位置情報とを対応付けて拠点情報テーブルに書き込めばよい。
【００９１】
また、データ取得部２０１は、ユーザ登録時にユーザのメールアドレスと名前とを取得し、ユーザＩＤと、メールアドレスと名前とを対応付けて図６に示すユーザ情報テーブルに書き込む。図６に示すようにユーザ情報テーブルにはユーザごとに１つのレコードが割り当てられ、各レコードにユーザＩＤ、メールアドレス、及び名前が対応付けて格納されていることが分かる。
【００９２】
拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルに記憶された情報から各拠点の評価の高さを示す拠点評価情報を取得する。
【００９３】
ここで、拠点評価情報は、広告費情報、関心度、及び訪問希望度を含み、各拠点を評価するための情報である。したがって、拠点評価情報取得部２０２は、本経路探索装置を使用しているユーザのユーザＩＤをキーとして、訪問希望度テーブルを参照し、当該ユーザの各拠点に対する訪問希望度を検索する。また、拠点評価情報取得部２０２は、拠点情報テーブルに記憶された各拠点の拠点ＩＤをキーとし、広告費情報テーブル、関心度テーブルを参照し、各拠点の広告費情報、関心度を検索する。
【００９４】
そして、拠点評価情報取得部２０２は、検索の結果得られた各拠点の広告費情報及び関心度と、ユーザが訪問希望度を設定している拠点については訪問希望度とを拠点評価情報として経路探索部２０３に供給する。
【００９５】
図２に戻り、距離取得部２１１は、任意の２拠点間の最短距離を地図情報記憶部２０８により記憶された地図情報より取得する。ここで、任意の２拠点間の距離とは、例えば、拠点としてＡ，Ｂ，Ｃがあったとすると、Ａ−Ｂ、Ａ−Ｃ、Ｂ−Ｃのそれぞれの最適距離が該当する。また、最短距離としては、２拠点間の直線距離を採用してもよいし、２拠点間を繋ぐ最短経路を例えば、Ａ＊アルゴリズムを用いて求め、その距離を採用してもよい。いずれにせよ、２拠点間の距離を評価する値を用いればよい。
【００９６】
地図情報は、道路交通網の地図情報である。具体的には、地図情報は、交差点や屈曲点等の道路上の所定の地点に対応するノードと、各ノードをつなぎ道路に対応するリンクとからなる有向グラフとが含まれている。また、地図情報は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。各ノード及び各リンクには、それぞれ固有の識別符号が割り当てられている。また、有向グラフＧは、Ｖをノードの集合とし、Ｅをリンクの集合とすると、Ｇ＝（Ｖ，Ｅ）で表される。
【００９７】
経路探索部２０３は、時間的制約に基づき到達可能な１又は複数の拠点を選択し、出発地点と目的地点と終着地点と拠点とを通る最適経路を、最短距離と、時間的制約を用いて探索する。
【００９８】
具体的には、経路探索部２０３は、少なくとも１つの拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、拠点の個数が多く、かつ、時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、評価値が高くなるように経路候補を変形させていくことで最適経路を探索する。そして、経路探索部２０３は、拠点評価情報の高い拠点が多く含まれるように、経路候補の評価値を算出する。
【００９９】
ここで、経路探索部２０３は、特許文献１に示す手法を利用して最適経路を探索すればよい。具体的には、経路探索部２０３は、ユーザにより入力された出発地点と到着地点との中間地点を求め、中間地点を基準として一定の領域を設定する。一定の領域としては、平均移動速度×（希望到着時刻−出発時刻）／２とする円や、楕円を採用すればよい。そして、経路探索部２０３は、設定した領域内に位置する拠点を全て抽出する。平均移動速度としては、徒歩、自転車、及び自動車等の移動手段のうちいずれの移動手段を使用するかをユーザに選択させ、選択させた移動手段の移動想定速度を採用すればよい。
【０１００】
この手法を採用する場合、経路探索部２０３は、抽出した拠点についての拠点評価情報を拠点評価情報取得部２０２に供給させればよい。
【０１０１】
そして、経路探索部２０３は、出発地点と、終着地点と、抽出した全ての拠点と、目的地点とを任意に組み合わせて、複数の個体（経路候補の一例）を現世代の個体として生成する。ここで、抽出した拠点を例えばＡ，Ｂ、ユーザが入力した目的地点をＣ、出発地点をＳ、及び到着地点をＥとすると、Ｓ−Ａ−Ｅ、Ｓ−Ａ−Ｂ−Ｅ、Ｓ−Ｂ−Ａ−Ｅ、Ｓ−Ａ−Ｂ−Ｃ−Ｅというように、Ａ，Ｂ，Ｃのうち少なくともＡ又はＢを含む全ての順列組み合わせのそれぞれが、１つの個体として生成される。なお、各個体は、可変長リストのデータ構造を持つ。以下、目的地点及び拠点を総称する場合は“巡回地点”と記述する。したがって、個体は、出発地点、巡回地点、及び終着地点から構成される。
【０１０２】
なお、上記の個体の生成手法は一例にすぎない。例えば、拠点情報テーブルに記憶された拠点と、ユーザが指定した目的地点とをランダムに抽出して個体を生成してもよい。この場合、拠点評価情報の高い拠点ほど抽出される確率が高くなるように拠点を抽出してもよい。こうすることで、拠点評価情報の高い拠点が個体に含まれる確率が高くなる結果、拠点評価情報の高い拠点が最適経路に含まれる可能性を高めることができる。また、拠点を抽出するにあたっては、ユーザが入力した目的地点又は終着地点に対して近くに位置する拠点が個体に含まれる確率が高くなるように拠点を抽出してもよい。また、ユーザが入力した目的地点、又は終着地点が拠点情報テーブルに登録された拠点でもあるために、同じ個体に同じ地点が複数含まれた場合、重複する地点を削除して１つにすればよい。
【０１０３】
そして、経路探索部２０３は、現世代の個体を遺伝的アルゴリズムで規定された手法（例えば、交叉、突然変異等）を用いて変形させる。次に、経路探索部２０３は、各個体の評価値を求める。評価値については後述する。次に、経路探索部２０３は、評価値が高い順に一定個数の個体を次世代の個体として残す。そして、経路探索部２０３は、この処理を一定回数繰り返し、最終的に残った個体のうち、評価値が最大の個体を求める。ここで、評価値は、特許文献１の評価値の算出式を下記の式（１）のように変更した算出式を用いて算出される。
【０１０４】
評価値＝α（経路候補中の拠点の拠点評価情報の重み値の合計）−β（総移動距離／巡回地点数）−γ（総移動時間／巡回地点数） （１）
なお、右辺の第２項から第３項は特許文献１の式（１）とほぼ同じであるが、第１項は特許文献１の式（１）の第１項と相違している。
【０１０５】
α、β、γは、各項の値を同程度の桁数の値に揃えるための係数である。以下、出発地点Ｓ、終着地点Ｅ、拠点Ａ、及び目的地点Ｂからなる個体Ｘ１（Ｓ−Ａ−Ｂ−Ｅ）を例に挙げて式（１）を説明する。
【０１０６】
第２項に示す総移動距離は個体Ｘ１の最短経路の距離である。この場合、経路探索部２０３は、まず、Ｓ−Ａ、Ａ−Ｂ、Ｂ−Ｅのそれぞれの最短距離の和を個体Ｘ１の総移動距離として算出すればよい。この場合、Ｓ−Ａ、Ａ−Ｂ、Ｂ−Ｅのそれぞれの最短距離が距離取得部２１１により取得されていればその距離を用い、取得されていなければ地図情報から算出することで求めればよい。
【０１０７】
第２項に示す巡回地点数は、個体に含まれる目的地点及び拠点の数を示している。個体Ｘ１には拠点Ａ及び目的地点Ｂの２つの巡回地点が含まれているため２が該当する。ここで、第２項は、総移動距離を巡回地点数で除したものである。したがって、総移動距離が長くなり、巡回地点数が少ないほど、第２項の値は増大する結果、評価値は小さくなる。なお、本実施の形態では、第２項に示す総移動距離をユーザのおよその移動距離と想定して評価値を算出している。但し、これは一例であり、個体に対する最短経路を例えばＡ＊アルゴリズムを用いて算出し、算出した最短経路をユーザの移動距離として採用してもよい。
【０１０８】
第３項に示す総移動時間は、個体Ｘ１の移動時間を示し、個体Ｘ１の総移動距離をユーザの平均移動速度で割ることで求められる。第３項に示す巡回地点数は、第２項のものと同じである。よって、総移動時間が長くなり、巡回地点数が少ないほど、第３項の値は増大する結果、評価値は増大する。
【０１０９】
第１項の拠点評価情報の重み値は、式（２）で表される。
【０１１０】
Ｋ（ｉ）＝Ｍｉｎ（ｗＭａｘ，ｇｗ（ｉ）＋Ｃ（ｉ）×Ａｄ（ｖ）） （２）
Ad(v)=if rand()%100≦v・100 then 1 else 0
v=aw(i)/awＭａｘ
ここで、ｉは拠点を特定するためのインデックスである。ｗＭａｘは予め定められた定数であり、例えば、ｇｗ（ｉ）の最高値（例えば５）と同じ値（例えば５）が採用されている。ｇｗ（ｉ）は拠点ｉに対する関心度（口コミ点数）と訪問希望度との合計値又は平均値である。Ｃ（ｉ）は拠点ｉに対して予め付与されたオフセット値である。ここで、オフセット値Ｃ（ｉ）は予め定められた値が採用され、全拠点について同じ値に設定してもよいし、広告費情報の高い拠点ほど高い値を付与してもよい。
【０１１１】
Ａｄ（ｖ）はｖが乱数値ｒａｎｄ（）以上の場合に１を返し、ｖが乱数値ｒａｎｄ（）未満の場合に０を返す関数である。
【０１１２】
ｖは広告費情報の最高値に対する拠点ｉの広告費情報の割合を示している。ａｗ（ｉ）は拠点ｉの広告費情報を示している。ａｗＭａｘは拠点情報テーブルに登録された各拠点の広告費情報の最高値を示し、例えば５が採用されている。
【０１１３】
ここで、拠点評価情報の重み値Ｋ（ｉ）はＭｉｎの括弧内の第１項と第２項との値を比較し、小さい方の値が採用される。これにより、Ｋ（ｉ）は少なくともｗＭａｘ以上の値が設定されることになり、広告費情報が低い拠点であっても最適経路に加えられる可能性を高めることができる。
【０１１４】
拠点評価情報の重み値Ｋ（ｉ）は、式（２）の“Ｃ（ｉ）×Ａｄ（ｖ）”に示すように、ｇｗ（ｉ）にオフセット値Ｃ（ｉ）を加えるか否かが抽選処理により決定されている。この抽選処理は、“Ad(v)=if rand()%100≦v・100 then 1 else 0”に示すように、広告費情報が高くなるにつれてＡｄ（ｖ）＝１となる確率が高められている。つまり、広告費情報が高いほど、ｇｗ（ｉ）にオフセット値Ｃ（ｉ）が加算される確率が高くされている。
【０１１５】
これにより、広告費情報を高く設定した拠点を含む個体の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。
【０１１６】
なお、拠点評価情報の重み値Ｋ（ｉ）は、式（２）を用いて算出したがこれは一例であり、他の手法を用いてもよい。例えば、拠点評価情報の重み値Ｋ（ｉ）を式（３）を用いて算出してもよい。
【０１１７】
Ｋ（ｉ）＝Ｍｉｎ（ｗＭａｘ，ｇｗ（ｉ）） （３）
このｇｗ（ｉ）の値が高いほど拠点ｉをより高い確率で最適経路に含ませることができる。但し、式（３）の手法を用いると、ｇｗ（ｉ）が高い拠点のみが最適経路に含まれ、ｇｗ（ｉ）が低い拠点が最適経路にほとんど含まれない事態も発生し得る。一方、式（２）では、オフセット値Ｃ（ｉ）を加えるか否かが抽選処理により決定されているため、ｇｗ（ｉ）の低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。
【０１１８】
上記の個体Ｘ１では、拠点Ａが含まれている。したがって、拠点Ａに対する拠点評価情報の重み値Ｋ（ｉ）が式（２）又は式（３）を用いて算出され、その拠点評価情報の重み値Ｋ（ｉ）が個体Ｘ１の評価値に加算される。なお、個体Ｘ１において、目的地点Ｂが拠点であるも場合、式（２）又は式（３）を用いて目的地点Ｂの拠点評価情報の重み値Ｋ（ｉ）が算出され、個体Ｘ１の評価値に加算される。
【０１１９】
そして、経路探索部２０３は、上記の処理により最終的に１つの個体を求め、その個体を繋ぐ最短経路を地図情報から求め、求めた最短経路を最適経路として算出する。なお、経路探索部２０３は、個体の最短経路を例えばＡ＊アルゴリズム等を用いて算出すればよい。なお、経路探索部２０３は、個体まで求め最短経路は端末装置１００に求めさせるようにしてもよい。この場合、経路探索部２０３は、求めた個体を示す情報を探索結果データに含ませて端末装置１００に送信すればよい。
【０１２０】
報知制御部２０４は、経路探索部２０３により算出された最適経路を示す情報と、最適経路に含まれている拠点に対する特典情報とを含む探索結果データを生成し、通信部２１０を介して端末装置１００に送信する。ここで、特典情報としては、拠点をユーザが訪問した際にユーザに付与される特典に関する情報が採用され、例えばクーポンが採用される。クーポンは、例えば拠点の入場料を割り引いたり、飲食費を割り引いたりするための引き替え券である。
【０１２１】
ユーザは、実際に拠点に訪れた際、クーポンを表した特典提示画像を表示部１０３に表示して拠点の管理人に特典提示画像を提示することにより拠点による特典が付与される。
【０１２２】
こうすることで、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、運営主はより高い広告費を得ることができる。
【０１２３】
また、報知制御部２０４は、最適経路に含まれる各拠点を広告するための広告情報を探索結果データに含ませても良い。これにより、探索結果データを受信した端末装置１００において最適経路が表示された際、最適経路に含まれる拠点の広告が表示され、ユーザに対して拠点を広告することができる。
【０１２４】
探索結果管理部２０５は、各拠点が経路探索部２０３により探索された最適経路に含まれた回数を管理する。具体的には、探索結果管理部２０５は、拠点情報テーブルに記憶された各拠点のそれぞれについて最適経路に含まれた履歴を保持するための探索履歴を生成し、探索履歴記憶部２０９に記憶させておく。そして、探索結果管理部２０５は、経路探索部２０３により最適経路が探索される都度、その最適経路に含まれた拠点を特定する。そして、探索結果管理部２０５は、特定した拠点の探索履歴にその拠点が最適経路に含まれた日時を書き込む。これにより、各拠点が最適経路に含まれた実際の回数及び日時を管理することができる。
【０１２５】
広告費算出部２０６は、最適経路に含まれた回数に応じて各拠点の広告費を算出する。具体的には、広告費算出部２０６は、例えば所定の料金徴収日が到来したとき、前回料金を徴収した日から現在までにおける各拠点が最適経路に含まれた回数を探索履歴を参照して特定し、特定した回数に１回あたりの広告単価を乗じることで各拠点の広告費を算出する。こうすることで、拠点が最適経路に含まれた実績に基づいた広告費を算出して請求することができる。その結果、拠点が最適経路に含まれていないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。
【０１２６】
ここで、１回あたりの広告単価としては、例えば、広告費情報、つまり、広告主が指定した目安値を採用してもよいし、拠点によらず一律に同じ値を採用してもよい。また、広告費算出部２０６は、広告費情報の規定値よりも高い拠点に対しては、最適経路に含まれた回数が増大するにつれて割引率が増大するように割引を行っても良い。
【０１２７】
また、広告費算出部２０６は、各拠点に対して算出した広告費が各拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を各拠点の広告費として算出してもよい。本実施の形態では、式（２）に示すように各拠点の拠点評価情報の重み値Ｋ（ｉ）を確率的に変動させているため、例えば、広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなる可能性がある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。
【０１２８】
ここで、上限広告費は、拠点を登録する際に広告主に申請させるようにしてもよいし、運営主が広告費情報に応じて予め定めた値を設定するようにしてもよい。なお、上限広告費は、料金徴収日が到来してから次の料金徴収日が到来するまでの一定期間（例えば１月、３０日、６０日等）における広告費の上限値を示している。
【０１２９】
テーブル記憶部２０７は、例えば記憶装置により構成され、図６に示す各種テーブルを記憶している。地図情報記憶部２０８は、最適経路を探索する際に用いられる地図情報を記憶している。探索履歴記憶部２０９は探索結果管理部２０５により生成される探索履歴を記憶している。
【０１３０】
通信部２１０は、通信回路及びＣＰＵ等により構成され、サーバ２００により生成される種々のデータ（探索結果データ等）を通信網ＮＴを介して端末装置１００に送信すると共に、端末装置１００から送信される探索条件データの他、広告主端末３００、口コミサイトが掲載されたＷＥＢサーバ等から送信される種々のデータを受信する。
【０１３１】
次に、本発明の実施の形態による経路案内装置の動作について説明する。図３は、本発明の実施の形態による経路案内装置の処理を示すフローチャートである。
【０１３２】
まず、入力受付部１０１は、ユーザから終着地点、終着地点に対する時間的制約、及び目的地点の入力を受け付け（Ｓ１でＹＥＳ）、入力された目的地点及び終着地点毎の入力地点情報を生成する（Ｓ２）。一方、入力受付部１０１は、これらのうち少なくとも終着地点及び終着地点に対する時間的制約を受け付けない場合（Ｓ１でＮＯ）、処理をＳ１に戻す。
【０１３３】
次に、位置情報取得部１０２は、現在位置及び現在時刻を取得する（Ｓ３）。次に、通信部１０４は、入力された目的地点、現在位置、及び現在時刻から出発地点、終着地点、及び各目的地点のそれぞれの入力地点情報を生成し、生成した入力地点情報とユーザＩＤとを含む探索条件データを生成しサーバ２００に送信する（Ｓ４）。
【０１３４】
次に、サーバ２００の通信部２１０が、探索条件データを受信すると（Ｓ１０でＹＥＳ）、拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルを参照し、関心度、広告費情報、及び訪問希望度を取得し、経路探索部２０３に供給する（Ｓ１１）。経路探索部２０３は、出発地点及び終着地点から一定の領域を設定し、この領域内に含まれる拠点を拠点情報テーブルから抽出し、式（２）又は式（３）に示すように、抽出した各拠点の拠点評価情報の重み値Ｋ（ｉ）を供給された関心度、広告費情報、及び訪問希望度を用いて算出する（Ｓ１２）。一方、通信部２１０は、探索条件データを受信しない場合（Ｓ１０でＮＯ）、処理をＳ１０に戻す。
【０１３５】
次に、経路探索部２０３は、抽出した拠点のうち少なくとも１つの拠点、必要に応じて少なくとも１つの目的地点を任意に組み合わせ、先端に出発地点、後端に終着地点を配置して複数の個体を生成し、各個体の評価値を算出し、所定のアルゴリズム（例えば遺伝的アルゴリズム）を一定回数繰り返し、評価値の高い最適経路を探索する（Ｓ１３）。
【０１３６】
次に、報知制御部２０４は、経路探索部２０３により探索された最適経路を示す情報と最適経路に含まれている拠点に対する特典情報及び広告情報とを含む探索結果データを生成し、端末装置１００に送信する（Ｓ１４）。
【０１３７】
次に、端末装置１００の通信部１０４が探索結果データを受信すると（Ｓ５でＹＥＳ）、表示部１０３は最適経路が重畳された地図画像を表示する（Ｓ６）。これにより、ユーザに探索結果が報知される。
【０１３８】
図４、図５は、本発明の実施の形態における経路案内装置において、広告費情報を考慮に入れて経路探索を行った場合と関心度と希望度の合計値又は平均値のみを考慮に入れて経路探索を行った場合との探索例を示した図である。
【０１３９】
図４（Ａ）は探索対象エリア周辺の地図画像であり、図４（Ｂ）はこの探索例で用いられた拠点に関するデータを示した表である。なお、図４（Ｂ）において広告費情報から計算される加算確率が書き込まれた拠点は、広告費情報が設定された拠点である。また、図４（Ｂ）において広告費情報から計算される加算確率が書き込まれていない拠点は、広告費情報が設定されておらず、関心度のみが設定された拠点である。広告費情報から計算される加算確率は、式（２）のＡｄ（ｖ）＝１になる確率である。
【０１４０】
この探索例では、図４（Ｂ）に示す“奈良公園”、“大仏殿”等の各拠点に対して図示する“関心度と訪問希望度との合計値又は平均値”、“広告費情報から計算される加算確率”、“拠点評価情報の重み値”が設定されているものとする。ここで、“拠点評価情報の重み値”は式（２）のＫ（ｉ）を示している。
【０１４１】
図４（Ｂ）において、“奈良公園”、“大仏殿”、“春日大社”、“浮見堂”は、広告費情報が登録されていないため、関心度と訪問希望度との合計値又は平均値のみが設定されている。また、図４（Ｂ）において、“国立博物館”、“宝物殿”は広告費情報が登録されているため、関心度と訪問希望度との合計値又は平均値に加えてオフセット値Ｃ（＝２）が加算された値も設定されている。“奈良公園”等の関心度と訪問希望度との合計値又は平均値のみ設定された拠点では、拠点評価情報の重み値は関心度と訪問希望度との合計値又は平均値と同じ値を採っていることが分かる。一方、“国立博物館”等の広告費情報が設定された拠点は拠点評価情報の重み値が２つの値を採っていることが分かる。
【０１４２】
具体的には、“国立博物館”は“３．５”又は“５．０”の拠点評価情報の重み値を採る。これは、式（２）において、オフセット値Ｃ（ｉ）が２．０に設定されているため、抽選処理によりＡｄ（ｖ）＝１の場合は関心度と訪問希望度との合計値又は平均値である３．５に２．０が加えられて５．０になるからである。一方、抽選処理によりＡｄ（ｖ）＝０の場合は関心度と訪問希望度との合計値又は平均値である３．５がそのまま拠点評価情報の重み値として使われる。
【０１４３】
“宝物殿”も同様に、拠点評価情報の重み値は“２．７”又は“４．７（＝２．７＋２．０）”の値を採る。なお、宝物殿の方が国立博物館よりも広告費情報から計算される加算確率が高いため、広告費情報が高くなる確率は、国立博物館よりも高い。
【０１４４】
図５（Ａ）は、関心度と訪問希望度との合計値又は平均値のみ考慮したときの探索結果を示している。図５（Ｂ）は、関心度と訪問希望度との合計値又は平均値に加えて広告費情報を考慮した場合の探索結果を示している。図５（Ａ）の場合、国立博物館及び宝物殿の広告費情報はそれぞれ、３．５、２．７と設定されて最適経路が探索されているため、両拠点とも最適経路に含まれていないことが分かる。
【０１４５】
一方、図５（Ｂ）では広告費情報が考慮され、国立博物館及び宝物殿の拠点評価情報の重み値がそれぞれ５．０、４．７と設定されて最適経路が探索されたため、両拠点が最適経路に含まれていることが分かる。
【０１４６】
このように、拠点評価情報の重み値を考慮に入れて最適経路を探索すると、広告費情報を支払った拠点が広告費情報を支払っていない拠点に比べて最適経路に含まれる可能性を高くすることができる。これにより、広告主に対して、広告費を支払う動機付けを付与することができる。
【０１４７】
なお、上記実施の形態では、広告費情報として、目安値を採用したが、本発明はこれに限定されず、広告主が実際に支払った広告費を広告費情報として採用してもよい。
【０１４８】
また、上記実施の形態では、遺伝的アルゴリズムを用いて最適経路を探索したが、これに限定されず、Lin-Kernighanアルゴリズム等を採用してもよい。
【０１４９】
また、上記実施の形態では、経路案内装置は端末装置１００とサーバ２００とで構成されていたがこれに限定されず、一台のコンピュータで構成してもよい。この場合、図２に示すサーバ２００の各ブロックを端末装置１００に設ければよい。
【０１５０】
また、上記実施の形態において、端末装置１００の各ブロックは経路案内装置としてコンピュータを機能させるための端末装置用のプログラムを実行することで実現され、サーバ２００の各ブロックは経路案内装置としてコンピュータを機能させるためのサーバ用のプログラムを実行することで実現される。
【０１５１】
この場合、端末装置用のプログラム及びサーバ用のプログラムをコンピュータ読み取り可能記録媒体（例えば、ＤＶＤ−ＲＯＭ）等に記録させてユーザに提供すればよい。
【０１５２】
また、上記実施の形態において、経路探索部２０３は、ある拠点の広告費が上限広告費を上回った場合、当該拠点については、次の料金徴収日が到来するまで、拠点評価情報を考慮することなく評価値を算出してもよい。この場合、広告費算出部２０６は、各拠点につき、最適経路に含まれる都度、最新の料金徴収日からの広告費の累積値を求める。そして、広告費の累積値が上限広告費以上になると、経路探索部２０３は、当該拠点について、次の料金徴収日が到来するまで、式（２）のＡｄ（ｖ）をＡｄ（ｖ）＝０にして拠点評価情報の重み値Ｋ（ｉ）を算出すればよい。つまり、経路探索部２０３は、当該拠点について、次の料金徴収日が到来するまで、関心度にオフセット値Ｃ（ｉ）を加算せずに拠点評価情報の重み値Ｋ（ｉ）を求めればよい。
【０１５３】
こうすることで、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。
【０１５４】
また、上記実施の形態では、出発地点と終着地点とが別の地点であるとして説明したが、ユーザが終着地点として出発地点と同じ地点を指定した場合、出発地点を終着地点として、最適経路を探索すればよい。これにより、目的地点の最寄りの駅から種々の拠点や目的地点を巡回し、最終的に最寄りの駅に戻るというような観光コースを最適経路として、ユーザに提供することができる。
【０１５５】
また、上記実施の形態において説明した特典を意味するＱＲコードを広告主の所持する携帯端末が読み取る際のフローチャートを示すと下記のようになる。以下の説明では、ユーザの所持する端末装置１００をユーザ端末と記述し、広告主の所持する端末装置を広告主端末と記述する。図７は、ユーザ端末と広告主端末との処理を示すフローチャートである。
【０１５６】
まず、ユーザ端末は、サーバ２００により探索された最適経路に従ったナビゲーションを開始する（Ｓ２０）。この場合、ユーザ端末はＧＰＳセンサにより検出される現在位置に従って地図画像上に表示されたユーザの現在位置を示すマークを随時更新し、ユーザに現在位置を報知する。
【０１５７】
次に、ユーザ端末は、最適経路に含まれるある拠点に到着すると（Ｓ２１でＹＥＳ）、特典提示画像を表示する（Ｓ２２）。ここで、特典提示画像には、広告主が自身の拠点についてのクーポンを表す画像に加えてＱＲコードが含まれている。なお、ＱＲコードに代えて、例えば１次元や２次元のバーコードを特典提示画像に含ませても良い。一方、ユーザ端末は、最適経路に含まれるある拠点に到着していない場合（Ｓ２１でＮＯ）、処理をＳ２３に進める。
【０１５８】
次に、広告主端末は、ユーザ端末に表示された特典提示画像に含まれるＱＲコードをカメラを用いて読み取る（Ｓ３０）。次に、広告主端末は、読み取ったＱＲコードが自己の拠点に対応するＱＲコードであるかを認証する（Ｓ３１）。
【０１５９】
Ｓ３１によってＱＲコードが認証されると、ユーザは拠点から特典を受けることができる。これにより、ユーザに対して特典提示画像を拠点の広告主に提示しようとするインセンティブを働かせることができる。
【０１６０】
次に、広告主端末は、ユーザが実際に広告主の拠点に訪問したことを示す訪問情報をサーバ２００に送信する（Ｓ３２）。これを受けたサーバ２００は、訪問情報にしたがって、該当する拠点についてのユーザの訪問数を１カウントアップし、図６に示すユーザ情報テーブルの訪問履歴を更新する。これにより、拠点を最適経路に含めたことによる集客効果を確認するための客観的なデータをサーバ２００に記録させることができる。
【０１６１】
次に、ユーザ端末は、終着地点に到着すると、ナビゲーションを終了させる（Ｓ２３でＹＥＳ）。一方、ユーザ端末は、終着地点に到着していない場合、ナビゲーションを継続させるために処理をＳ２１に戻す。つまり、ユーザ端末は、終着地点に到達するまで、最適経路に含まれる拠点に到達する毎にその拠点の特典提示画像を表示する。
【０１６２】
次に、広告主端末を介さずにユーザ端末とサーバ２００とがユーザによる特典の行使を管理する態様について説明する。図８は、ユーザ端末とサーバ２００とがユーザによる特典の行使を管理するための処理を示すフローチャートである。
【０１６３】
Ｓ４０、Ｓ４１、Ｓ４６は図７のＳ２０、Ｓ２１、Ｓ２３と同一であるため説明を省く。Ｓ４２において、ユーザ端末は、特典についての画像を表示する。この画像は、ユーザが拠点から受ける特典を閲覧する画像と、上記の特典提示画像とが含まれる。
【０１６４】
次に、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けると（Ｓ４３でＹＥＳ）、特典提示画像を画面に大きく表示する（Ｓ４４）。ここで、ユーザは例えば、特典についての画像において特典提示画像が表示された領域をタッチすることで特典を行使するための入力指令を入力すればよい。
【０１６５】
広告主はこの特典提示画像を確認すると、ユーザに対して特典を付与する。これにより、ユーザに対して特典提示画像を表示させて広告主に見せるインセンティブを与えることができる。なお、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けない場合（Ｓ４３でＮＯ）、処理をＳ４６に進める。
【０１６６】
次に、ユーザ端末は、ユーザが特典を行使したことを示す特典行使情報をサーバ２００に送信する（Ｓ４５）。次に、サーバ２００は特典行使情報を受信し（Ｓ５０）、ユーザが拠点を訪問したことを示す訪問履歴を更新する（Ｓ５１）。この場合、サーバ２００は、図６に示すユーザ情報テーブルに含まれる該当するユーザの訪問履歴を更新すればよい。図６の例においてユーザ拠点Ａを訪問したとすると、拠点Ａの訪問回数が１カウントアップされて訪問履歴が更新される。
【０１６７】
Ｓ５１において、例えばあるユーザのユーザ端末から拠点Ａについての特典行使情報を受信した場合、サーバ２００が該当するユーザの拠点Ａの訪問回数を１カウントアップすればよい。
【０１６８】
このように、ユーザ端末から特典行使情報を送信させて、各ユーザの拠点の訪問履歴を管理することで、広告主はＱＲコードを読み取るための広告主端末を準備する手間を省くことができる。これによりコストダウンを図ることができる。また、拠点においてＱＲコードを読み取る必要がなくなるため、広告主の時間や手間等を削減することができる。よって、広告主に自己の拠点を登録させようとする動機付けを与えることができる。
【０１６９】
次に、特典行使情報の活用方法について説明する。
【０１７０】
（Ａ）広告主は、広告主端末からサーバ２００にアクセスし、サーバ２００に閲覧要求を送信する。閲覧要求を受信したサーバ２００は当該広告主の拠点の訪問履歴を広告主端末に送信する。これによりこの広告主は自己の拠点の訪問履歴を閲覧することで、最適経路に自己の拠点が含まれてユーザにより広告が閲覧された回数と、ユーザが実際に自己の拠点に訪問したと考えられる回数とを認識することができる。よって、広告主は、広告費とその効果の検証を行い、広告費設定の検討に利用することができる。
【０１７１】
（Ｂ）広告費の課金に関して、ユーザが実際に拠点を訪れた回数に基づいて、運営主は広告主に広告費の請求を行ってもよい。この場合、広告費算出部２０６は、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとればよい。
【０１７２】
（Ｃ）ユーザが訪問した拠点と、各拠点の訪問回数とが記録されるため、ユーザが過去に訪問した拠点の履歴を残すことができる。そして、ユーザ端末等を介してユーザがサーバ２００にアクセスした際、広告主端末と同様にして、該当するユーザの訪問履歴をユーザ端末に送信し、ユーザに自己の訪問履歴を閲覧させることで、ユーザは、過去に訪問した拠点を認識することができ、思い出の記録にも繋がる。
【０１７３】
（Ｄ）サーバ２００において、ユーザ別に訪問履歴や訪問希望度が記録されているため、広告主は、過去に訪問したユーザや訪問希望度の高いユーザに対して、通信網ＮＴを経由してサービス情報やプロモーション情報等を含むメールを送信することができ、ダイレクトマーケティングが可能となる。この場合、ユーザに対して、そのようなメールを送る旨を、予めオプトインしておくことが好ましい。
【０１７４】
（Ｅ）上記（Ｄ）においてメールを送る際に、ユーザ情報を広告主に開示せずに、サーバ２００を経由してのみメールを送ることを許可することも可能となる。これによって、ユーザの個人情報が不用意に広告主に開示されることが防止される。
【０１７５】
（Ｆ）上記（Ｅ）に関して、サーバ２００がメールを送信する際に、広告主に課金を行うようにしてもよい。
【０１７６】
なお、図７、図８の方式を組み合わせた方式を採用してもよい。例えば図７の方式において、広告主がＱＲコードの読み取りを怠ることもある。この場合、上記（Ｂ）に関して、課金が行えなくなってしまう。よって、図７、図８の方式を組み合わせる双方の数を比較可能とすることで、バーコードの読み取り回数と、特典提示情報の表示回数との差を認識することが可能となる。その結果、両者が大きく乖離している場合に、広告主に対して警告するなどの対処を行うことが可能となる。
【０１７７】
図８の方式のみを採用した場合、特典提示を行わないユーザが存在するために、実際に拠点に行ったことが分からないユーザが発生したり、興味本位で特典提示画面を表示するユーザが発生したりして、実際に拠点に訪問していないにも関わらず、訪問したユーザとしとして認識されるデメリットが発生することが懸念される。しかしながら、図７と図８との方式を組み合わせることで、かかる事態の発生を防止することができる。
【０１７８】
上記実施の形態では、拠点評価情報取得部２０２は、広告費情報、関心度、及び訪問希望度を経路探索部２０３に供給したが、これらのうち少なくとも１つを経路探索部２０３に供給し、経路探索部２０３に最適経路を探索させてもよい。
【符号の説明】
【０１７９】
１００ 端末装置
１０１ 入力受付部
１０２ 位置情報取得部
１０３ 表示部
１０４ 通信部
１０５ 地図情報記憶部
２００ サーバ
２０１ データ取得部
２０２ 関心度取得部
２０３ 経路探索部
２０４ 報知制御部
２０５ 探索結果管理部
２０６ 広告費算出部
２０７ テーブル記憶部
２０８ 地図情報記憶部
２０９ 探索履歴記憶部
２１０ 通信部
２１１ 距離取得部
ＮＴ 通信網
【技術分野】
【０００１】
本発明は、ユーザから訪問を希望する終着地点を入力させ、その終着地点までの最適経路をユーザに案内する技術に関するものである。
【背景技術】
【０００２】
近年、スマートフォンの普及に伴い、スマートフォンにユーザを目的地点までナビゲートさせるナビゲーションシステムのニーズが高まっている。また、種々の制約条件の下、ユーザを目的地点まで効率良くナビゲートする経路探索アルゴリズムも開発されている。
【０００３】
例えば、特許文献１には、ユーザに訪問を希望する複数の目的地点及びこれらの目的地点への希望到着時刻等の時間的制約を入力させ、遺伝的アルゴリズムを用いてこれらの目的地点を通り、かつ、時間的制約を満たすような最短経路をユーザに報知する経路探索アルゴリズムが開示されている。
【０００４】
そこで、このような経路探索アルゴリズムとスマートフォンとを結びつけた新たなビジネスモデルが模索されている。特許文献２には、チケット販売時にイベント会場への推奨到着時刻と推奨経路とをユーザに報知するチケット販売支援機能を有するナビゲーションシステムが開示されている。
【０００５】
ところで、近年、スマートフォンやインターネット上で種々のサービスを提供するソフトウェア事業者は、ソフトウェア自体の収入ではなく、ユーザがソフトウェアを使用した際に広告を掲載し、広告主から広告費を募ることで収入を得るのが一般的である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第４２９２０６２号公報
【特許文献２】特開２００９−８５４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献２では、ユーザにとって便利な情報が提供されるかも知れないが、広告主に広告への動機付けを与えるような措置が何ら採用されていない。
【０００８】
本発明の目的は、出発地点から終着地点までの経路の探索を行った際に、探索された経路に含ませる拠点をコントロールすることで、拠点の広告主に対して広告への動機付けを与える経路案内装置等を提供することである。
【課題を解決するための手段】
【０００９】
（１）本発明による経路案内装置は、観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、任意の２拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する。
【００１０】
この構成によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報を設定することによって拠点を探索経路に含ませるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。なお、拠点としては、観光地の他、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、その他施設等を採用することができる。また、到着地点を、出発地点と同じに設定とすることで、到着地点の入力を省かせてもよい。また、本発明による経路案内方法、経路案内プログラム、及び経路案内システムは上記の経路案内装置と同様の構成を持っている。
【００１１】
（２）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得することが好ましい。
【００１２】
この構成によれば、広告費情報が高い拠点ほど拠点評価情報が上昇する。その結果、広告費の高い拠点ほど最適経路に含まれる確率を高くすることができる。
【００１３】
（３）前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得することが好ましい。
【００１４】
この構成によれば、関心度が高い拠点ほど拠点評価情報が高くなる結果、最適経路に含まれる確率を高くすることができる。
【００１５】
（４）前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得することが好ましい。
【００１６】
この構成によれば、ユーザが訪問を強く希望する拠点を最適経路に優先的に含ませることができる。
【００１７】
（５）前記入力受付部は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付け、前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出することが好ましい。
【００１８】
この構成によれば、出発地点及び終着地点とは別にユーザが訪問を希望する目的地点を考慮に入れて最適経路を探索することができる。
【００１９】
（６）前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付けることが好ましい。
【００２０】
この構成によれば、ユーザに対して出発地点及び出発時刻の入力を省かせることができる。なお、本構成において、到着時刻を、現在時刻から一定時間後の時刻とすることで、到着時刻の入力を省かせてもよい。
【００２１】
（７）前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備えることが好ましい。
【００２２】
この構成によれば、拠点が最適経路に含まれた実績に基づいた広告費を算出することができる。その結果、拠点が最適経路に含まれた実績がないないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。
【００２３】
（８）前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出することが好ましい。
【００２４】
広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなることもある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。
【００２５】
（９）前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示すことが好ましい。
【００２６】
この構成によれば、一定期間における広告費が上限広告費を超えた場合、対象となる広告主に対して上限広告費以上の広告費が請求されることを防止することができる。
【００２７】
（１０）前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記広告費情報を考慮せずに前記評価値を算出することが好ましい。
【００２８】
この構成によれば、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。
【００２９】
（１１）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う１回あたりの広告費の目安値に応じた値であることが好ましい。
【００３０】
この構成によれば、拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値を広告主に予め定めさせ、その目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができる。そのため、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。
【００３１】
（１２）前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知することが好ましい。
【００３２】
この構成によれば、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、広告主からより高い広告費を得ることができる。
【００３３】
（１３）前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出することが好ましい。
【００３４】
この構成によれば、広告費情報を高く設定した拠点を含む探索経路の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。
【００３５】
（１４）前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、前記経路探索部は、前記広告費情報が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行することが好ましい。
【００３６】
この構成によれば、オフセット値を加えるか否かが抽選処理により決定されているため、広告費情報の低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。
【００３７】
（１５）前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させることが好ましい。
【００３８】
この構成によれば、ユーザが特典を行使するための情報を広告主の所持する端末装置に認識させ、行使が許可された場合にユーザに特典を行使させる構成を採用することができる。これにより、ユーザに対して特典を行使するための情報を拠点の広告主に提示しようとするインセンティブを働かせることができる。また、広告主は、実際にユーザが拠点を訪問したか否かを管理することができる。
【００３９】
（１６）前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。
【００４０】
この構成によれば、広告主が所持する端末装置から特典行使情報をサーバに送信させることで、各拠点対するユーザの訪問履歴をサーバ側で管理することが可能となる。
【００４１】
（１７）前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。
【００４２】
この構成によれば、ユーザ端末から特典行使情報をサーバに送信させることで、各ユーザの拠点の訪問履歴をサーバ側で管理することが可能となる。そのため、広告主は端末装置を準備することなく、ユーザの拠点への訪問回数を管理することができる。
【００４３】
（１８）前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信することが好ましい。
【００４４】
この構成によれば、ユーザは自己の履歴を閲覧することができるため、実際に訪れた拠点や各拠点の訪問回数を認識し、思い出を記録することができる。
【００４５】
（１９）前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信することが好ましい。
【００４６】
この構成によれば、広告が閲覧され、実際にユーザにより訪問された回数を認識することができる。
【００４７】
（２０）前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出することが好ましい。
【００４８】
この構成によれば、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとることができる。
【００４９】
（２１）前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信することが好ましい。
【００５０】
この構成によれば、ユーザが特典を行使した拠点が記録されているため、サーバはユーザが特典を行使した拠点、つまり訪問したことがある拠点についての情報（例えばサービス情報やプロモーション情報）をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。
【００５１】
（２２）前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理し、各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信するサーバを備えることが好ましい。
【００５２】
この構成によれば、ユーザが訪問を希望する拠点についての訪問の希望の高さを示す訪問希望度が記録されているため、サーバはユーザが訪問を希望する拠点についての情報（例えばサービス情報やプロモーション情報）をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。
【発明の効果】
【００５３】
本発明によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報によって拠点を探索経路に含まれるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施の形態による経路案内装置の全体構成図である。
【図２】本発明の実施の形態による経路案内装置の構成を示す機能ブロック図である。
【図３】本発明の実施の形態による経路案内装置の処理を示すフローチャートである。
【図４】（Ａ）は探索対象エリア周辺の地図画像であり、（Ｂ）は拠点に関するデータを示した表である。
【図５】（Ａ）は、関心度及び訪問希望度のみ考慮したときの探索結果を示している。（Ｂ）は、関心度及び訪問希望度に加えて広告費情報を考慮した場合の探索結果を示している。
【図６】テーブル記憶部に記憶された各種テーブルの一例を示した図である。
【図７】ユーザ端末と広告主端末との処理を示すフローチャートである。
【図８】ユーザ端末とサーバとがユーザによる特典の行使を管理するための処理を示すフローチャートである。
【発明を実施するための形態】
【００５５】
以下、本発明の実施の形態による経路案内装置について図面を参照して説明する。図１は、本発明の実施の形態による経路案内装置の全体構成図である。経路案内装置は、端末装置１００及びサーバ２００を含んでいる。端末装置１００は、例えば、スマートフォンやタブレット端末等の携帯型の情報端末装置により構成されている。サーバ２００は、一般的なコンピュータ或いはコンピュータ群（クラウドコンピュータ）により構成されている。
【００５６】
端末装置１００及びサーバ２００は通信網ＮＴを介して相互に通信可能に接続されている。通信網ＮＴとしては、携帯電話網、及びインターネット通信網により構成されている。端末装置１００及びサーバ２００には例えばＩＰアドレス等の固有の通信ＩＤが割り振られ、端末装置１００及びサーバ２００はこの通信ＩＤを用いて、例えばＴＣＰ／ＩＰ等の通信プロトコルを用いて相互に通信を行う。
【００５７】
端末装置１００は、ユーザから訪問を希望する目的地点、終着地点、及び終着地点の希望到着時刻等の入力を受け付け、通信網ＮＴを介してサーバ２００に送信する。サーバ２００は、端末装置１００から送信された目的地点、終着地点、及び終着地点の希望到着時刻を考慮に入れた最適経路の探索を行い、探索結果を端末装置１００に送信する。端末装置１００はサーバ２００により探索された最適経路を表示し、最適経路をユーザに報知する。
【００５８】
そして、本実施の形態では、サーバ２００は、各拠点を評価するための拠点評価情報が高い拠点ほど最短経路に加えられる回数が増大するように最適経路を探索することを特徴としている。拠点評価情報としては、広告費の高さを示す広告費情報、第三者による各拠点の関心の高さを示す関心度、及び、各ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を用いて算出される値が採用される。広告費情報としては広告主による広告費の目安値が採用され、目安値の一例としては広告費の希望単価があげられる。拠点としては、観光地、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、及びその他施設等が該当する。
【００５９】
以下、本実施の形態による経路案内装置の詳細について説明する。図２は、本発明の実施の形態による経路案内装置の構成を示す機能ブロック図である。端末装置１００は、入力受付部１０１、位置情報取得部１０２、表示部１０３（報知部の一例）、通信部１０４、及び地図情報記憶部１０５を備えている。
【００６０】
入力受付部１０１は、例えば、タッチパネル、及びタッチパネルにより検出されたデータを処理するＣＰＵ等により構成され、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける。また、入力受付部１０１は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付ける。ここで、入力受付部１０１は、位置情報取得部１０２により取得されたユーザの現在位置を中心として所定範囲内にある地図画像を地図情報記憶部１０５から読み出して表示部１０３に表示する。そして、入力受付部１０１は、表示部１０３に表示された地図画像において、出発地点、終着地点、及び目的地点をタッチさせ、出発地点、終着地点、及び目的地点を入力させる。以下、“出発地点”、“終着地点”、及び“目的地点”を総称する場合は、“入力地点”と記述する。
【００６１】
なお、入力受付部１０１は、位置情報取得部１０２により取得されたユーザの現在位置を出発地点として取得し、かつ、位置情報取得部１０２により取得された現在時刻を出発時刻として取得してもよい。この場合、ユーザは出発地点及び出発時刻を入力する手間が省かれる。
【００６２】
地図画像は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。
【００６３】
したがって、入力受付部１０１は、ユーザが表示部１０３をタッチしたときのタッチ位置に表示されている地図画像の場所の緯度及び経度を特定する。そして、入力受付部１０１は、特定した緯度及び経度に場所の名称が対応付けられている場合は、その名称をユーザが入力した入力地点として認識する。そして、入力受付部１０１は、特定した場所の緯度、経度、及び名称を示すデータ群を該当する入力地点の入力地点情報として生成する。
【００６４】
また、入力受付部１０１は、特定した緯度及び経度に場所の名称が対応付けられていない場合は、近傍に位置する名称が対応付けられている場所を特定し、“特定した場所の周辺”（例えば、“県立博物館の周辺”）をユーザが入力した入力地点として認識する。この場合、“緯度”、“経度”、及び“特定した場所の周辺”からなるデータ群が入力地点情報として生成される。
【００６５】
次に、入力受付部１０１は、ユーザが入力した入力地点のうち、どの入力地点が終着地点であるかをユーザに指定させるための入力画像を表示部１０３に表示させる。そして、入力受付部１０１は、その入力画像により指定された１の入力地点を終着地点として認識する。そして、入力受付部１０１は、認識した終着地点についての希望到着時刻の入力をユーザに促す入力画像を表示部１０３に表示させ、希望等着地点を入力させる。
【００６６】
位置情報取得部１０２は、ユーザの現在位置及び現在時刻を特定する。ここで、位置情報取得部１０２は、例えばＧＰＳセンサ、及びＧＰＳセンサにより検出されたデータを処理するＣＰＵ等を含み、ＧＰＳセンサにより検出された位置情報をユーザの現在位置として取得すればよい。ここで、現在位置としては、例えば緯度及び経度が採用される。
【００６７】
また、位置情報取得部１０２は、時計を含み、ユーザの現在位置を取得した時刻を現在時刻として取得すればよい。以下の説明では、位置情報取得部１０２が取得した現在位置及び現在時刻を出発地点及び出発時刻として採用するものとする。
【００６８】
通信部１０４は、例えば、通信回路、及び通信回路を制御するＣＰＵ等から構成され、入力受付部１０１により生成された入力地点情報及び端末装置１００を使用しているユーザのユーザＩＤを探索条件データとして生成し、サーバ２００に送信する。
【００６９】
例えば、入力受付部１０１が入力地点として、Ａ、Ｂ、Ｃを取得し、Ａが出発地点、Ｂが目的地点、及びＣが終着地点として指定された場合、Ａの入力地点情報は、（“ユーザの現在位置”，“Ａの名称”，“現在時刻”，出発地点）となり、Ｂの入力地点情報は（“Ｂの緯度及び経度”，“Ｂの名称”，目的地点）となり、Ｃの入力地点情報は、（“Ｃの緯度及び経度”，“Ｃの名称”，“希望到着時刻：００：００”，終着地点）となる。したがって、この場合に送信される探索条件データは、例えば（“Ａの入力地点情報”，“Ｂの入力地点情報”，“Ｃの入力地点情報”、“ユーザＩＤ”）となる。
【００７０】
表示部１０３は、例えばタッチパネル、及びタッチパネルを制御するＣＰＵ等により構成され、サーバ２００により探索された最適経路や、地図画像等を表示する。具体的には、表示部１０３は、サーバ２００から探索結果を示す探索結果データを受信すると、探索結果が示す最適経路を地図画像に重畳して表示する。
【００７１】
また、本実施の形態では、実際にユーザが本経路案内装置により探索された最適経路を使用して拠点を訪れたかどうかを拠点の広告主が確かめるために、そのようにして訪れたユーザに対して広告主が特典を付与することができる。この場合、ユーザは端末装置１００を所持して、端末装置１００によるナビゲーションに従って拠点を訪れる。このときに、ユーザの所持する端末装置１００に特典を意味するＱＲコードを表示させる。そして、広告主の所持する端末装置に備えられたカメラでこのＱＲコードを読み取らせる。広告主の所持する端末装置は、ユーザの提示したＱＲコードを解読することで、このＱＲコードが正規のものであることを確認する。これにより、広告主の所持する端末装置は、ユーザが本経路案内装置により実際に拠点を訪れたか否かを認識することできる。なお、広告主の所持する端末装置としては、スマートフォンでも良い。また、両者の端末間の通信方式としてＱＲコード以外の他の通信方式を利用してもよい。
【００７２】
サーバ２００は、各拠点のＱＲコードを予め後述するテーブル記憶部２０７に記憶させ、後述する探索結果データに最適経路に含まれる拠点のＱＲコードを含ませて、端末装置１００に送信すればよい。
【００７３】
サーバ２００は、データ取得部２０１、拠点評価情報取得部２０２、経路探索部２０３、報知制御部２０４（報知部の一例）、探索結果管理部２０５、広告費算出部２０６、テーブル記憶部２０７、地図情報記憶部２０８、探索履歴記憶部２０９、通信部２１０、及び距離取得部２１１を備えている。ここで、データ取得部２０１〜広告費算出部２０６、及び距離取得部２１１は主にＣＰＵにより構成され、テーブル記憶部２０７〜探索履歴記憶部２０９は主に記憶装置により構成され、通信部２１０は主に通信回路により構成されている。
【００７４】
データ取得部２０１は、１又は複数の拠点について広告主から支払われる広告費情報を取得する。本実施の形態では、広告費情報としては、例えばある拠点の広告主から当該拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値が採用される。具体的には、広告費情報としては、目安値の最大値を満点（例えば、５点）としたときの各拠点の目安値の割合が採用される。目安値としては、例えば１００円、２００円というように、探索経路に１回含まれた際に広告主が支払うことを希望する金額を採用すればよい。また、目安値の最大値が１０００円であり、ある拠点の目安値が１００円とすると、５×（１００／１０００）／５を目安値の割合として採用すればよい。
【００７５】
本実施の形態では、広告主の拠点が最適経路に含まれた実際の回数に応じて広告費を徴収する形態を採用している。この場合、拠点が最適経路に含まれた回数が広告主の意思に反して多かったり、少なかったりすることは好ましくない。そこで、本経路案内装置を運営する運営主は、拠点が最適経路に含まれた場合に支払う１回あたりの広告費の目安値を広告主に予め定めさせている。これにより、広告費の目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができ、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。
【００７６】
したがって、データ取得部２０１は、広告主端末３００からアクセスされると、目安値の入力を促す入力画像を広告主端末３００に表示させ、この入力画像を通じて目安値を入力させ、サーバ２００に目安値を送信させることで、目安値を取得する。この際、データ取得部２０１は、目安値と併せて、広告主を識別するための広告主ＩＤ、拠点の名称、及び位置情報を送信させる。位置情報としては、拠点の場所を示す緯度及び経度を採用すればよい。
【００７７】
そして、データ取得部２０１は、その拠点に対してその拠点を一意的に識別するため拠点ＩＤを付与し、拠点ＩＤと拠点の名称と拠点の位置情報とを対応付けて図６に示す拠点情報テーブル（拠点情報記憶部の一例）に書き込む。また、データ取得部２０１は、取得した広告費情報を広告主ＩＤと拠点ＩＤと対応付けて図６に示す広告費情報テーブルに書き込む。
【００７８】
図６に示すように、拠点情報テーブルには、拠点ごとに１つのレコードが割り当てられ、各レコードに拠点ＩＤ、拠点の名称、及び位置情報が対応付けて格納されていることが分かる。また、広告費情報テーブルには、広告主ごとに１つのレコードが割り当てられ、各レコードに広告主ＩＤ、拠点ＩＤ、及び広告費情報が対応付けられて格納されていることが分かる。
【００７９】
なお、上記の広告費情報の取得方法は一例にすぎず、他の方法を用いても良い。例えば、運営主が広告主から広告主ＩＤ、拠点の名称、位置情報、及び広告費情報を直接聞き出し、入力装置を用いてサーバ２００に入力することで、データ取得部２０１にこれらの情報を取得させてもよい。
【００８０】
また、データ取得部２０１は、通信網ＮＴに存在するＷＥＢサーバにより運営されている口コミサイトにおいて、第三者がある拠点を紹介するために書き込んだ情報である口コミ情報を取得する。具体的には、データ取得部２０１は、通信網ＮＴ上の口コミサイトを探索し、探索した口コミサイトのＨＴＭＬデータを定期的に取得し、取得したＨＴＭＬデータを分析することで、口コミ情報を書き込んだユーザを特定し、当該ユーザにユーザＩＤを付与し、付与したユーザＩＤとそのユーザが書き込んだ口コミ情報とを対応付けて図６に示す口コミテーブルに書き込む。
【００８１】
そして、データ取得部２０１は、図６に示す口コミテーブルを分析し、各拠点の口コミ情報の平均評価点数（以下、“口コミ点数”と記述する。）を取得し、取得した口コミ点数を関心度とし、拠点ＩＤと対応付けて図６に示す関心度テーブルに書き込む。図６に示すように、関心度テーブルには、拠点ごとに１つのレコードが割り当てられ、拠点ＩＤ及び関心度が対応付けて格納されていることが分かる。
【００８２】
口コミ情報は、例えば、ある拠点に対する書き込み数が多いほど、その拠点に対する第三者の関心は高いと言える。
【００８３】
そこで、本実施の形態では、口コミサイトを監視し、監視結果から各拠点の口コミ情報の口コミ点数を取得し、取得した口コミ点数を各拠点の関心度として採用している。
【００８４】
なお、口コミ点数は、（口コミ情報の書き込みを行った各ユーザが付けた点数（例えば５点満点の点数）の全ユーザの和）／（書き込みを行ったユーザ数）で計算される。例えば、ある拠点に対して書き込みを行ったユーザがＡ，Ｂ，Ｃ，Ｄとして、それぞれが、その拠点に対して４点、５点、４点、３点をつけたとすると、口コミ点数は（４＋５＋４＋３）／４＝４点と算出される。
【００８５】
ここで、データ取得部２０１は、口コミ情報を分析して特定した拠点が拠点情報テーブルに格納されていない新規の拠点である場合、その拠点に拠点ＩＤを付与し、地図情報を参照し、その拠点の名称からその拠点の位置情報を取得し、拠点ＩＤと拠点の名称と位置情報とを対応付けて拠点情報テーブルにも書き込む。
【００８６】
なお、関心度として、口コミ点数を採用したが、本発明はこれに限定されず、第三者が拠点を評価する指標であれば、どのような指標を採用してもよい。例えば、テレビ、新聞等で紹介される拠点ランキングをオペレータが集計し、その集計結果に基づいて関心度を設定してもよい。
【００８７】
また、データ取得部２０１は、本経路案内装置を使用するユーザのユーザＩＤと、そのユーザが訪問を希望する拠点についての希望の度合いを示す訪問希望度とを取得し、拠点ＩＤとユーザＩＤと訪問希望度とを対応付けて図６に示す訪問希望テーブルに書き込む。
【００８８】
ここで、データ取得部２０１は、例えば、ユーザが本経路案内装置を初めて使用する場合にユーザ登録を行わせ、そのときにユーザＩＤと訪問希望度とを取得すればよい。なお、訪問希望度としては、ユーザが訪問を希望する拠点についての拠点別の希望度合いを例えば所定満点で点数表示したデータを採用すればよい。また、訪問希望度は、ユーザ登録後にユーザが適宜設定できるようにしてもよい。
【００８９】
図６に示す用に訪問希望テーブルは、拠点ＩＤのそれぞれについて各ユーザＩＤと訪問希望とを対応付けて格納している。例えば、拠点Ａにつき、ユーザＵ１，Ｕ２，Ｕ３がそれぞれ、１，２，３という訪問希望度を指定した場合、拠点Ａの拠点ＩＤのレコードには、ユーザＵ１，Ｕ２，Ｕ３の各ユーザＩＤと、それぞれの訪問希望度である１，２，３とが対応付けて格納される。
【００９０】
ここで、データ取得部２０１は、ユーザが訪問を希望した拠点が拠点情報テーブルに格納されていない場合、その拠点に対して拠点ＩＤを付与し、地図情報を参照して位置情報を取得し、その拠点の名称から拠点ＩＤと拠点の名称と位置情報とを対応付けて拠点情報テーブルに書き込めばよい。
【００９１】
また、データ取得部２０１は、ユーザ登録時にユーザのメールアドレスと名前とを取得し、ユーザＩＤと、メールアドレスと名前とを対応付けて図６に示すユーザ情報テーブルに書き込む。図６に示すようにユーザ情報テーブルにはユーザごとに１つのレコードが割り当てられ、各レコードにユーザＩＤ、メールアドレス、及び名前が対応付けて格納されていることが分かる。
【００９２】
拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルに記憶された情報から各拠点の評価の高さを示す拠点評価情報を取得する。
【００９３】
ここで、拠点評価情報は、広告費情報、関心度、及び訪問希望度を含み、各拠点を評価するための情報である。したがって、拠点評価情報取得部２０２は、本経路探索装置を使用しているユーザのユーザＩＤをキーとして、訪問希望度テーブルを参照し、当該ユーザの各拠点に対する訪問希望度を検索する。また、拠点評価情報取得部２０２は、拠点情報テーブルに記憶された各拠点の拠点ＩＤをキーとし、広告費情報テーブル、関心度テーブルを参照し、各拠点の広告費情報、関心度を検索する。
【００９４】
そして、拠点評価情報取得部２０２は、検索の結果得られた各拠点の広告費情報及び関心度と、ユーザが訪問希望度を設定している拠点については訪問希望度とを拠点評価情報として経路探索部２０３に供給する。
【００９５】
図２に戻り、距離取得部２１１は、任意の２拠点間の最短距離を地図情報記憶部２０８により記憶された地図情報より取得する。ここで、任意の２拠点間の距離とは、例えば、拠点としてＡ，Ｂ，Ｃがあったとすると、Ａ−Ｂ、Ａ−Ｃ、Ｂ−Ｃのそれぞれの最適距離が該当する。また、最短距離としては、２拠点間の直線距離を採用してもよいし、２拠点間を繋ぐ最短経路を例えば、Ａ＊アルゴリズムを用いて求め、その距離を採用してもよい。いずれにせよ、２拠点間の距離を評価する値を用いればよい。
【００９６】
地図情報は、道路交通網の地図情報である。具体的には、地図情報は、交差点や屈曲点等の道路上の所定の地点に対応するノードと、各ノードをつなぎ道路に対応するリンクとからなる有向グラフとが含まれている。また、地図情報は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。各ノード及び各リンクには、それぞれ固有の識別符号が割り当てられている。また、有向グラフＧは、Ｖをノードの集合とし、Ｅをリンクの集合とすると、Ｇ＝（Ｖ，Ｅ）で表される。
【００９７】
経路探索部２０３は、時間的制約に基づき到達可能な１又は複数の拠点を選択し、出発地点と目的地点と終着地点と拠点とを通る最適経路を、最短距離と、時間的制約を用いて探索する。
【００９８】
具体的には、経路探索部２０３は、少なくとも１つの拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、拠点の個数が多く、かつ、時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、評価値が高くなるように経路候補を変形させていくことで最適経路を探索する。そして、経路探索部２０３は、拠点評価情報の高い拠点が多く含まれるように、経路候補の評価値を算出する。
【００９９】
ここで、経路探索部２０３は、特許文献１に示す手法を利用して最適経路を探索すればよい。具体的には、経路探索部２０３は、ユーザにより入力された出発地点と到着地点との中間地点を求め、中間地点を基準として一定の領域を設定する。一定の領域としては、平均移動速度×（希望到着時刻−出発時刻）／２とする円や、楕円を採用すればよい。そして、経路探索部２０３は、設定した領域内に位置する拠点を全て抽出する。平均移動速度としては、徒歩、自転車、及び自動車等の移動手段のうちいずれの移動手段を使用するかをユーザに選択させ、選択させた移動手段の移動想定速度を採用すればよい。
【０１００】
この手法を採用する場合、経路探索部２０３は、抽出した拠点についての拠点評価情報を拠点評価情報取得部２０２に供給させればよい。
【０１０１】
そして、経路探索部２０３は、出発地点と、終着地点と、抽出した全ての拠点と、目的地点とを任意に組み合わせて、複数の個体（経路候補の一例）を現世代の個体として生成する。ここで、抽出した拠点を例えばＡ，Ｂ、ユーザが入力した目的地点をＣ、出発地点をＳ、及び到着地点をＥとすると、Ｓ−Ａ−Ｅ、Ｓ−Ａ−Ｂ−Ｅ、Ｓ−Ｂ−Ａ−Ｅ、Ｓ−Ａ−Ｂ−Ｃ−Ｅというように、Ａ，Ｂ，Ｃのうち少なくともＡ又はＢを含む全ての順列組み合わせのそれぞれが、１つの個体として生成される。なお、各個体は、可変長リストのデータ構造を持つ。以下、目的地点及び拠点を総称する場合は“巡回地点”と記述する。したがって、個体は、出発地点、巡回地点、及び終着地点から構成される。
【０１０２】
なお、上記の個体の生成手法は一例にすぎない。例えば、拠点情報テーブルに記憶された拠点と、ユーザが指定した目的地点とをランダムに抽出して個体を生成してもよい。この場合、拠点評価情報の高い拠点ほど抽出される確率が高くなるように拠点を抽出してもよい。こうすることで、拠点評価情報の高い拠点が個体に含まれる確率が高くなる結果、拠点評価情報の高い拠点が最適経路に含まれる可能性を高めることができる。また、拠点を抽出するにあたっては、ユーザが入力した目的地点又は終着地点に対して近くに位置する拠点が個体に含まれる確率が高くなるように拠点を抽出してもよい。また、ユーザが入力した目的地点、又は終着地点が拠点情報テーブルに登録された拠点でもあるために、同じ個体に同じ地点が複数含まれた場合、重複する地点を削除して１つにすればよい。
【０１０３】
そして、経路探索部２０３は、現世代の個体を遺伝的アルゴリズムで規定された手法（例えば、交叉、突然変異等）を用いて変形させる。次に、経路探索部２０３は、各個体の評価値を求める。評価値については後述する。次に、経路探索部２０３は、評価値が高い順に一定個数の個体を次世代の個体として残す。そして、経路探索部２０３は、この処理を一定回数繰り返し、最終的に残った個体のうち、評価値が最大の個体を求める。ここで、評価値は、特許文献１の評価値の算出式を下記の式（１）のように変更した算出式を用いて算出される。
【０１０４】
評価値＝α（経路候補中の拠点の拠点評価情報の重み値の合計）−β（総移動距離／巡回地点数）−γ（総移動時間／巡回地点数） （１）
なお、右辺の第２項から第３項は特許文献１の式（１）とほぼ同じであるが、第１項は特許文献１の式（１）の第１項と相違している。
【０１０５】
α、β、γは、各項の値を同程度の桁数の値に揃えるための係数である。以下、出発地点Ｓ、終着地点Ｅ、拠点Ａ、及び目的地点Ｂからなる個体Ｘ１（Ｓ−Ａ−Ｂ−Ｅ）を例に挙げて式（１）を説明する。
【０１０６】
第２項に示す総移動距離は個体Ｘ１の最短経路の距離である。この場合、経路探索部２０３は、まず、Ｓ−Ａ、Ａ−Ｂ、Ｂ−Ｅのそれぞれの最短距離の和を個体Ｘ１の総移動距離として算出すればよい。この場合、Ｓ−Ａ、Ａ−Ｂ、Ｂ−Ｅのそれぞれの最短距離が距離取得部２１１により取得されていればその距離を用い、取得されていなければ地図情報から算出することで求めればよい。
【０１０７】
第２項に示す巡回地点数は、個体に含まれる目的地点及び拠点の数を示している。個体Ｘ１には拠点Ａ及び目的地点Ｂの２つの巡回地点が含まれているため２が該当する。ここで、第２項は、総移動距離を巡回地点数で除したものである。したがって、総移動距離が長くなり、巡回地点数が少ないほど、第２項の値は増大する結果、評価値は小さくなる。なお、本実施の形態では、第２項に示す総移動距離をユーザのおよその移動距離と想定して評価値を算出している。但し、これは一例であり、個体に対する最短経路を例えばＡ＊アルゴリズムを用いて算出し、算出した最短経路をユーザの移動距離として採用してもよい。
【０１０８】
第３項に示す総移動時間は、個体Ｘ１の移動時間を示し、個体Ｘ１の総移動距離をユーザの平均移動速度で割ることで求められる。第３項に示す巡回地点数は、第２項のものと同じである。よって、総移動時間が長くなり、巡回地点数が少ないほど、第３項の値は増大する結果、評価値は増大する。
【０１０９】
第１項の拠点評価情報の重み値は、式（２）で表される。
【０１１０】
Ｋ（ｉ）＝Ｍｉｎ（ｗＭａｘ，ｇｗ（ｉ）＋Ｃ（ｉ）×Ａｄ（ｖ）） （２）
Ad(v)=if rand()%100≦v・100 then 1 else 0
v=aw(i)/awＭａｘ
ここで、ｉは拠点を特定するためのインデックスである。ｗＭａｘは予め定められた定数であり、例えば、ｇｗ（ｉ）の最高値（例えば５）と同じ値（例えば５）が採用されている。ｇｗ（ｉ）は拠点ｉに対する関心度（口コミ点数）と訪問希望度との合計値又は平均値である。Ｃ（ｉ）は拠点ｉに対して予め付与されたオフセット値である。ここで、オフセット値Ｃ（ｉ）は予め定められた値が採用され、全拠点について同じ値に設定してもよいし、広告費情報の高い拠点ほど高い値を付与してもよい。
【０１１１】
Ａｄ（ｖ）はｖが乱数値ｒａｎｄ（）以上の場合に１を返し、ｖが乱数値ｒａｎｄ（）未満の場合に０を返す関数である。
【０１１２】
ｖは広告費情報の最高値に対する拠点ｉの広告費情報の割合を示している。ａｗ（ｉ）は拠点ｉの広告費情報を示している。ａｗＭａｘは拠点情報テーブルに登録された各拠点の広告費情報の最高値を示し、例えば５が採用されている。
【０１１３】
ここで、拠点評価情報の重み値Ｋ（ｉ）はＭｉｎの括弧内の第１項と第２項との値を比較し、小さい方の値が採用される。これにより、Ｋ（ｉ）は少なくともｗＭａｘ以上の値が設定されることになり、広告費情報が低い拠点であっても最適経路に加えられる可能性を高めることができる。
【０１１４】
拠点評価情報の重み値Ｋ（ｉ）は、式（２）の“Ｃ（ｉ）×Ａｄ（ｖ）”に示すように、ｇｗ（ｉ）にオフセット値Ｃ（ｉ）を加えるか否かが抽選処理により決定されている。この抽選処理は、“Ad(v)=if rand()%100≦v・100 then 1 else 0”に示すように、広告費情報が高くなるにつれてＡｄ（ｖ）＝１となる確率が高められている。つまり、広告費情報が高いほど、ｇｗ（ｉ）にオフセット値Ｃ（ｉ）が加算される確率が高くされている。
【０１１５】
これにより、広告費情報を高く設定した拠点を含む個体の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。
【０１１６】
なお、拠点評価情報の重み値Ｋ（ｉ）は、式（２）を用いて算出したがこれは一例であり、他の手法を用いてもよい。例えば、拠点評価情報の重み値Ｋ（ｉ）を式（３）を用いて算出してもよい。
【０１１７】
Ｋ（ｉ）＝Ｍｉｎ（ｗＭａｘ，ｇｗ（ｉ）） （３）
このｇｗ（ｉ）の値が高いほど拠点ｉをより高い確率で最適経路に含ませることができる。但し、式（３）の手法を用いると、ｇｗ（ｉ）が高い拠点のみが最適経路に含まれ、ｇｗ（ｉ）が低い拠点が最適経路にほとんど含まれない事態も発生し得る。一方、式（２）では、オフセット値Ｃ（ｉ）を加えるか否かが抽選処理により決定されているため、ｇｗ（ｉ）の低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。
【０１１８】
上記の個体Ｘ１では、拠点Ａが含まれている。したがって、拠点Ａに対する拠点評価情報の重み値Ｋ（ｉ）が式（２）又は式（３）を用いて算出され、その拠点評価情報の重み値Ｋ（ｉ）が個体Ｘ１の評価値に加算される。なお、個体Ｘ１において、目的地点Ｂが拠点であるも場合、式（２）又は式（３）を用いて目的地点Ｂの拠点評価情報の重み値Ｋ（ｉ）が算出され、個体Ｘ１の評価値に加算される。
【０１１９】
そして、経路探索部２０３は、上記の処理により最終的に１つの個体を求め、その個体を繋ぐ最短経路を地図情報から求め、求めた最短経路を最適経路として算出する。なお、経路探索部２０３は、個体の最短経路を例えばＡ＊アルゴリズム等を用いて算出すればよい。なお、経路探索部２０３は、個体まで求め最短経路は端末装置１００に求めさせるようにしてもよい。この場合、経路探索部２０３は、求めた個体を示す情報を探索結果データに含ませて端末装置１００に送信すればよい。
【０１２０】
報知制御部２０４は、経路探索部２０３により算出された最適経路を示す情報と、最適経路に含まれている拠点に対する特典情報とを含む探索結果データを生成し、通信部２１０を介して端末装置１００に送信する。ここで、特典情報としては、拠点をユーザが訪問した際にユーザに付与される特典に関する情報が採用され、例えばクーポンが採用される。クーポンは、例えば拠点の入場料を割り引いたり、飲食費を割り引いたりするための引き替え券である。
【０１２１】
ユーザは、実際に拠点に訪れた際、クーポンを表した特典提示画像を表示部１０３に表示して拠点の管理人に特典提示画像を提示することにより拠点による特典が付与される。
【０１２２】
こうすることで、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、運営主はより高い広告費を得ることができる。
【０１２３】
また、報知制御部２０４は、最適経路に含まれる各拠点を広告するための広告情報を探索結果データに含ませても良い。これにより、探索結果データを受信した端末装置１００において最適経路が表示された際、最適経路に含まれる拠点の広告が表示され、ユーザに対して拠点を広告することができる。
【０１２４】
探索結果管理部２０５は、各拠点が経路探索部２０３により探索された最適経路に含まれた回数を管理する。具体的には、探索結果管理部２０５は、拠点情報テーブルに記憶された各拠点のそれぞれについて最適経路に含まれた履歴を保持するための探索履歴を生成し、探索履歴記憶部２０９に記憶させておく。そして、探索結果管理部２０５は、経路探索部２０３により最適経路が探索される都度、その最適経路に含まれた拠点を特定する。そして、探索結果管理部２０５は、特定した拠点の探索履歴にその拠点が最適経路に含まれた日時を書き込む。これにより、各拠点が最適経路に含まれた実際の回数及び日時を管理することができる。
【０１２５】
広告費算出部２０６は、最適経路に含まれた回数に応じて各拠点の広告費を算出する。具体的には、広告費算出部２０６は、例えば所定の料金徴収日が到来したとき、前回料金を徴収した日から現在までにおける各拠点が最適経路に含まれた回数を探索履歴を参照して特定し、特定した回数に１回あたりの広告単価を乗じることで各拠点の広告費を算出する。こうすることで、拠点が最適経路に含まれた実績に基づいた広告費を算出して請求することができる。その結果、拠点が最適経路に含まれていないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。
【０１２６】
ここで、１回あたりの広告単価としては、例えば、広告費情報、つまり、広告主が指定した目安値を採用してもよいし、拠点によらず一律に同じ値を採用してもよい。また、広告費算出部２０６は、広告費情報の規定値よりも高い拠点に対しては、最適経路に含まれた回数が増大するにつれて割引率が増大するように割引を行っても良い。
【０１２７】
また、広告費算出部２０６は、各拠点に対して算出した広告費が各拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を各拠点の広告費として算出してもよい。本実施の形態では、式（２）に示すように各拠点の拠点評価情報の重み値Ｋ（ｉ）を確率的に変動させているため、例えば、広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなる可能性がある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。
【０１２８】
ここで、上限広告費は、拠点を登録する際に広告主に申請させるようにしてもよいし、運営主が広告費情報に応じて予め定めた値を設定するようにしてもよい。なお、上限広告費は、料金徴収日が到来してから次の料金徴収日が到来するまでの一定期間（例えば１月、３０日、６０日等）における広告費の上限値を示している。
【０１２９】
テーブル記憶部２０７は、例えば記憶装置により構成され、図６に示す各種テーブルを記憶している。地図情報記憶部２０８は、最適経路を探索する際に用いられる地図情報を記憶している。探索履歴記憶部２０９は探索結果管理部２０５により生成される探索履歴を記憶している。
【０１３０】
通信部２１０は、通信回路及びＣＰＵ等により構成され、サーバ２００により生成される種々のデータ（探索結果データ等）を通信網ＮＴを介して端末装置１００に送信すると共に、端末装置１００から送信される探索条件データの他、広告主端末３００、口コミサイトが掲載されたＷＥＢサーバ等から送信される種々のデータを受信する。
【０１３１】
次に、本発明の実施の形態による経路案内装置の動作について説明する。図３は、本発明の実施の形態による経路案内装置の処理を示すフローチャートである。
【０１３２】
まず、入力受付部１０１は、ユーザから終着地点、終着地点に対する時間的制約、及び目的地点の入力を受け付け（Ｓ１でＹＥＳ）、入力された目的地点及び終着地点毎の入力地点情報を生成する（Ｓ２）。一方、入力受付部１０１は、これらのうち少なくとも終着地点及び終着地点に対する時間的制約を受け付けない場合（Ｓ１でＮＯ）、処理をＳ１に戻す。
【０１３３】
次に、位置情報取得部１０２は、現在位置及び現在時刻を取得する（Ｓ３）。次に、通信部１０４は、入力された目的地点、現在位置、及び現在時刻から出発地点、終着地点、及び各目的地点のそれぞれの入力地点情報を生成し、生成した入力地点情報とユーザＩＤとを含む探索条件データを生成しサーバ２００に送信する（Ｓ４）。
【０１３４】
次に、サーバ２００の通信部２１０が、探索条件データを受信すると（Ｓ１０でＹＥＳ）、拠点評価情報取得部２０２は、テーブル記憶部２０７に記憶された各種テーブルを参照し、関心度、広告費情報、及び訪問希望度を取得し、経路探索部２０３に供給する（Ｓ１１）。経路探索部２０３は、出発地点及び終着地点から一定の領域を設定し、この領域内に含まれる拠点を拠点情報テーブルから抽出し、式（２）又は式（３）に示すように、抽出した各拠点の拠点評価情報の重み値Ｋ（ｉ）を供給された関心度、広告費情報、及び訪問希望度を用いて算出する（Ｓ１２）。一方、通信部２１０は、探索条件データを受信しない場合（Ｓ１０でＮＯ）、処理をＳ１０に戻す。
【０１３５】
次に、経路探索部２０３は、抽出した拠点のうち少なくとも１つの拠点、必要に応じて少なくとも１つの目的地点を任意に組み合わせ、先端に出発地点、後端に終着地点を配置して複数の個体を生成し、各個体の評価値を算出し、所定のアルゴリズム（例えば遺伝的アルゴリズム）を一定回数繰り返し、評価値の高い最適経路を探索する（Ｓ１３）。
【０１３６】
次に、報知制御部２０４は、経路探索部２０３により探索された最適経路を示す情報と最適経路に含まれている拠点に対する特典情報及び広告情報とを含む探索結果データを生成し、端末装置１００に送信する（Ｓ１４）。
【０１３７】
次に、端末装置１００の通信部１０４が探索結果データを受信すると（Ｓ５でＹＥＳ）、表示部１０３は最適経路が重畳された地図画像を表示する（Ｓ６）。これにより、ユーザに探索結果が報知される。
【０１３８】
図４、図５は、本発明の実施の形態における経路案内装置において、広告費情報を考慮に入れて経路探索を行った場合と関心度と希望度の合計値又は平均値のみを考慮に入れて経路探索を行った場合との探索例を示した図である。
【０１３９】
図４（Ａ）は探索対象エリア周辺の地図画像であり、図４（Ｂ）はこの探索例で用いられた拠点に関するデータを示した表である。なお、図４（Ｂ）において広告費情報から計算される加算確率が書き込まれた拠点は、広告費情報が設定された拠点である。また、図４（Ｂ）において広告費情報から計算される加算確率が書き込まれていない拠点は、広告費情報が設定されておらず、関心度のみが設定された拠点である。広告費情報から計算される加算確率は、式（２）のＡｄ（ｖ）＝１になる確率である。
【０１４０】
この探索例では、図４（Ｂ）に示す“奈良公園”、“大仏殿”等の各拠点に対して図示する“関心度と訪問希望度との合計値又は平均値”、“広告費情報から計算される加算確率”、“拠点評価情報の重み値”が設定されているものとする。ここで、“拠点評価情報の重み値”は式（２）のＫ（ｉ）を示している。
【０１４１】
図４（Ｂ）において、“奈良公園”、“大仏殿”、“春日大社”、“浮見堂”は、広告費情報が登録されていないため、関心度と訪問希望度との合計値又は平均値のみが設定されている。また、図４（Ｂ）において、“国立博物館”、“宝物殿”は広告費情報が登録されているため、関心度と訪問希望度との合計値又は平均値に加えてオフセット値Ｃ（＝２）が加算された値も設定されている。“奈良公園”等の関心度と訪問希望度との合計値又は平均値のみ設定された拠点では、拠点評価情報の重み値は関心度と訪問希望度との合計値又は平均値と同じ値を採っていることが分かる。一方、“国立博物館”等の広告費情報が設定された拠点は拠点評価情報の重み値が２つの値を採っていることが分かる。
【０１４２】
具体的には、“国立博物館”は“３．５”又は“５．０”の拠点評価情報の重み値を採る。これは、式（２）において、オフセット値Ｃ（ｉ）が２．０に設定されているため、抽選処理によりＡｄ（ｖ）＝１の場合は関心度と訪問希望度との合計値又は平均値である３．５に２．０が加えられて５．０になるからである。一方、抽選処理によりＡｄ（ｖ）＝０の場合は関心度と訪問希望度との合計値又は平均値である３．５がそのまま拠点評価情報の重み値として使われる。
【０１４３】
“宝物殿”も同様に、拠点評価情報の重み値は“２．７”又は“４．７（＝２．７＋２．０）”の値を採る。なお、宝物殿の方が国立博物館よりも広告費情報から計算される加算確率が高いため、広告費情報が高くなる確率は、国立博物館よりも高い。
【０１４４】
図５（Ａ）は、関心度と訪問希望度との合計値又は平均値のみ考慮したときの探索結果を示している。図５（Ｂ）は、関心度と訪問希望度との合計値又は平均値に加えて広告費情報を考慮した場合の探索結果を示している。図５（Ａ）の場合、国立博物館及び宝物殿の広告費情報はそれぞれ、３．５、２．７と設定されて最適経路が探索されているため、両拠点とも最適経路に含まれていないことが分かる。
【０１４５】
一方、図５（Ｂ）では広告費情報が考慮され、国立博物館及び宝物殿の拠点評価情報の重み値がそれぞれ５．０、４．７と設定されて最適経路が探索されたため、両拠点が最適経路に含まれていることが分かる。
【０１４６】
このように、拠点評価情報の重み値を考慮に入れて最適経路を探索すると、広告費情報を支払った拠点が広告費情報を支払っていない拠点に比べて最適経路に含まれる可能性を高くすることができる。これにより、広告主に対して、広告費を支払う動機付けを付与することができる。
【０１４７】
なお、上記実施の形態では、広告費情報として、目安値を採用したが、本発明はこれに限定されず、広告主が実際に支払った広告費を広告費情報として採用してもよい。
【０１４８】
また、上記実施の形態では、遺伝的アルゴリズムを用いて最適経路を探索したが、これに限定されず、Lin-Kernighanアルゴリズム等を採用してもよい。
【０１４９】
また、上記実施の形態では、経路案内装置は端末装置１００とサーバ２００とで構成されていたがこれに限定されず、一台のコンピュータで構成してもよい。この場合、図２に示すサーバ２００の各ブロックを端末装置１００に設ければよい。
【０１５０】
また、上記実施の形態において、端末装置１００の各ブロックは経路案内装置としてコンピュータを機能させるための端末装置用のプログラムを実行することで実現され、サーバ２００の各ブロックは経路案内装置としてコンピュータを機能させるためのサーバ用のプログラムを実行することで実現される。
【０１５１】
この場合、端末装置用のプログラム及びサーバ用のプログラムをコンピュータ読み取り可能記録媒体（例えば、ＤＶＤ−ＲＯＭ）等に記録させてユーザに提供すればよい。
【０１５２】
また、上記実施の形態において、経路探索部２０３は、ある拠点の広告費が上限広告費を上回った場合、当該拠点については、次の料金徴収日が到来するまで、拠点評価情報を考慮することなく評価値を算出してもよい。この場合、広告費算出部２０６は、各拠点につき、最適経路に含まれる都度、最新の料金徴収日からの広告費の累積値を求める。そして、広告費の累積値が上限広告費以上になると、経路探索部２０３は、当該拠点について、次の料金徴収日が到来するまで、式（２）のＡｄ（ｖ）をＡｄ（ｖ）＝０にして拠点評価情報の重み値Ｋ（ｉ）を算出すればよい。つまり、経路探索部２０３は、当該拠点について、次の料金徴収日が到来するまで、関心度にオフセット値Ｃ（ｉ）を加算せずに拠点評価情報の重み値Ｋ（ｉ）を求めればよい。
【０１５３】
こうすることで、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。
【０１５４】
また、上記実施の形態では、出発地点と終着地点とが別の地点であるとして説明したが、ユーザが終着地点として出発地点と同じ地点を指定した場合、出発地点を終着地点として、最適経路を探索すればよい。これにより、目的地点の最寄りの駅から種々の拠点や目的地点を巡回し、最終的に最寄りの駅に戻るというような観光コースを最適経路として、ユーザに提供することができる。
【０１５５】
また、上記実施の形態において説明した特典を意味するＱＲコードを広告主の所持する携帯端末が読み取る際のフローチャートを示すと下記のようになる。以下の説明では、ユーザの所持する端末装置１００をユーザ端末と記述し、広告主の所持する端末装置を広告主端末と記述する。図７は、ユーザ端末と広告主端末との処理を示すフローチャートである。
【０１５６】
まず、ユーザ端末は、サーバ２００により探索された最適経路に従ったナビゲーションを開始する（Ｓ２０）。この場合、ユーザ端末はＧＰＳセンサにより検出される現在位置に従って地図画像上に表示されたユーザの現在位置を示すマークを随時更新し、ユーザに現在位置を報知する。
【０１５７】
次に、ユーザ端末は、最適経路に含まれるある拠点に到着すると（Ｓ２１でＹＥＳ）、特典提示画像を表示する（Ｓ２２）。ここで、特典提示画像には、広告主が自身の拠点についてのクーポンを表す画像に加えてＱＲコードが含まれている。なお、ＱＲコードに代えて、例えば１次元や２次元のバーコードを特典提示画像に含ませても良い。一方、ユーザ端末は、最適経路に含まれるある拠点に到着していない場合（Ｓ２１でＮＯ）、処理をＳ２３に進める。
【０１５８】
次に、広告主端末は、ユーザ端末に表示された特典提示画像に含まれるＱＲコードをカメラを用いて読み取る（Ｓ３０）。次に、広告主端末は、読み取ったＱＲコードが自己の拠点に対応するＱＲコードであるかを認証する（Ｓ３１）。
【０１５９】
Ｓ３１によってＱＲコードが認証されると、ユーザは拠点から特典を受けることができる。これにより、ユーザに対して特典提示画像を拠点の広告主に提示しようとするインセンティブを働かせることができる。
【０１６０】
次に、広告主端末は、ユーザが実際に広告主の拠点に訪問したことを示す訪問情報をサーバ２００に送信する（Ｓ３２）。これを受けたサーバ２００は、訪問情報にしたがって、該当する拠点についてのユーザの訪問数を１カウントアップし、図６に示すユーザ情報テーブルの訪問履歴を更新する。これにより、拠点を最適経路に含めたことによる集客効果を確認するための客観的なデータをサーバ２００に記録させることができる。
【０１６１】
次に、ユーザ端末は、終着地点に到着すると、ナビゲーションを終了させる（Ｓ２３でＹＥＳ）。一方、ユーザ端末は、終着地点に到着していない場合、ナビゲーションを継続させるために処理をＳ２１に戻す。つまり、ユーザ端末は、終着地点に到達するまで、最適経路に含まれる拠点に到達する毎にその拠点の特典提示画像を表示する。
【０１６２】
次に、広告主端末を介さずにユーザ端末とサーバ２００とがユーザによる特典の行使を管理する態様について説明する。図８は、ユーザ端末とサーバ２００とがユーザによる特典の行使を管理するための処理を示すフローチャートである。
【０１６３】
Ｓ４０、Ｓ４１、Ｓ４６は図７のＳ２０、Ｓ２１、Ｓ２３と同一であるため説明を省く。Ｓ４２において、ユーザ端末は、特典についての画像を表示する。この画像は、ユーザが拠点から受ける特典を閲覧する画像と、上記の特典提示画像とが含まれる。
【０１６４】
次に、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けると（Ｓ４３でＹＥＳ）、特典提示画像を画面に大きく表示する（Ｓ４４）。ここで、ユーザは例えば、特典についての画像において特典提示画像が表示された領域をタッチすることで特典を行使するための入力指令を入力すればよい。
【０１６５】
広告主はこの特典提示画像を確認すると、ユーザに対して特典を付与する。これにより、ユーザに対して特典提示画像を表示させて広告主に見せるインセンティブを与えることができる。なお、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けない場合（Ｓ４３でＮＯ）、処理をＳ４６に進める。
【０１６６】
次に、ユーザ端末は、ユーザが特典を行使したことを示す特典行使情報をサーバ２００に送信する（Ｓ４５）。次に、サーバ２００は特典行使情報を受信し（Ｓ５０）、ユーザが拠点を訪問したことを示す訪問履歴を更新する（Ｓ５１）。この場合、サーバ２００は、図６に示すユーザ情報テーブルに含まれる該当するユーザの訪問履歴を更新すればよい。図６の例においてユーザ拠点Ａを訪問したとすると、拠点Ａの訪問回数が１カウントアップされて訪問履歴が更新される。
【０１６７】
Ｓ５１において、例えばあるユーザのユーザ端末から拠点Ａについての特典行使情報を受信した場合、サーバ２００が該当するユーザの拠点Ａの訪問回数を１カウントアップすればよい。
【０１６８】
このように、ユーザ端末から特典行使情報を送信させて、各ユーザの拠点の訪問履歴を管理することで、広告主はＱＲコードを読み取るための広告主端末を準備する手間を省くことができる。これによりコストダウンを図ることができる。また、拠点においてＱＲコードを読み取る必要がなくなるため、広告主の時間や手間等を削減することができる。よって、広告主に自己の拠点を登録させようとする動機付けを与えることができる。
【０１６９】
次に、特典行使情報の活用方法について説明する。
【０１７０】
（Ａ）広告主は、広告主端末からサーバ２００にアクセスし、サーバ２００に閲覧要求を送信する。閲覧要求を受信したサーバ２００は当該広告主の拠点の訪問履歴を広告主端末に送信する。これによりこの広告主は自己の拠点の訪問履歴を閲覧することで、最適経路に自己の拠点が含まれてユーザにより広告が閲覧された回数と、ユーザが実際に自己の拠点に訪問したと考えられる回数とを認識することができる。よって、広告主は、広告費とその効果の検証を行い、広告費設定の検討に利用することができる。
【０１７１】
（Ｂ）広告費の課金に関して、ユーザが実際に拠点を訪れた回数に基づいて、運営主は広告主に広告費の請求を行ってもよい。この場合、広告費算出部２０６は、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとればよい。
【０１７２】
（Ｃ）ユーザが訪問した拠点と、各拠点の訪問回数とが記録されるため、ユーザが過去に訪問した拠点の履歴を残すことができる。そして、ユーザ端末等を介してユーザがサーバ２００にアクセスした際、広告主端末と同様にして、該当するユーザの訪問履歴をユーザ端末に送信し、ユーザに自己の訪問履歴を閲覧させることで、ユーザは、過去に訪問した拠点を認識することができ、思い出の記録にも繋がる。
【０１７３】
（Ｄ）サーバ２００において、ユーザ別に訪問履歴や訪問希望度が記録されているため、広告主は、過去に訪問したユーザや訪問希望度の高いユーザに対して、通信網ＮＴを経由してサービス情報やプロモーション情報等を含むメールを送信することができ、ダイレクトマーケティングが可能となる。この場合、ユーザに対して、そのようなメールを送る旨を、予めオプトインしておくことが好ましい。
【０１７４】
（Ｅ）上記（Ｄ）においてメールを送る際に、ユーザ情報を広告主に開示せずに、サーバ２００を経由してのみメールを送ることを許可することも可能となる。これによって、ユーザの個人情報が不用意に広告主に開示されることが防止される。
【０１７５】
（Ｆ）上記（Ｅ）に関して、サーバ２００がメールを送信する際に、広告主に課金を行うようにしてもよい。
【０１７６】
なお、図７、図８の方式を組み合わせた方式を採用してもよい。例えば図７の方式において、広告主がＱＲコードの読み取りを怠ることもある。この場合、上記（Ｂ）に関して、課金が行えなくなってしまう。よって、図７、図８の方式を組み合わせる双方の数を比較可能とすることで、バーコードの読み取り回数と、特典提示情報の表示回数との差を認識することが可能となる。その結果、両者が大きく乖離している場合に、広告主に対して警告するなどの対処を行うことが可能となる。
【０１７７】
図８の方式のみを採用した場合、特典提示を行わないユーザが存在するために、実際に拠点に行ったことが分からないユーザが発生したり、興味本位で特典提示画面を表示するユーザが発生したりして、実際に拠点に訪問していないにも関わらず、訪問したユーザとしとして認識されるデメリットが発生することが懸念される。しかしながら、図７と図８との方式を組み合わせることで、かかる事態の発生を防止することができる。
【０１７８】
上記実施の形態では、拠点評価情報取得部２０２は、広告費情報、関心度、及び訪問希望度を経路探索部２０３に供給したが、これらのうち少なくとも１つを経路探索部２０３に供給し、経路探索部２０３に最適経路を探索させてもよい。
【符号の説明】
【０１７９】
１００ 端末装置
１０１ 入力受付部
１０２ 位置情報取得部
１０３ 表示部
１０４ 通信部
１０５ 地図情報記憶部
２００ サーバ
２０１ データ取得部
２０２ 関心度取得部
２０３ 経路探索部
２０４ 報知制御部
２０５ 探索結果管理部
２０６ 広告費算出部
２０７ テーブル記憶部
２０８ 地図情報記憶部
２０９ 探索履歴記憶部
２１０ 通信部
２１１ 距離取得部
ＮＴ 通信網
【特許請求の範囲】
【請求項１】
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、
ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内装置。
【請求項２】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得する請求項１記載の経路案内装置。
【請求項３】
前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得する請求項１又は２記載の経路案内装置。
【請求項４】
前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得する請求項１〜３のいずれかに記載の経路案内装置。
【請求項５】
前記入力受付部は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付けけ、
前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出する請求項１〜４のいずれかに記載の経路案内装置。
【請求項６】
前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、
前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付ける請求項１〜５のいずれかに記載の経路案内装置。
【請求項７】
前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備える請求項１〜６のいずれかに記載の経路案内装置。
【請求項８】
前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出する請求項７記載の経路案内装置。
【請求項９】
前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示す請求項８記載の経路案内装置。
【請求項１０】
前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記拠点評価情報を考慮せずに前記評価値を算出する請求項８又は９記載の経路案内装置。
【請求項１１】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、
前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う１回あたりの広告費の目安値に応じた値である請求項１〜１０のいずれかに記載の経路案内装置。
【請求項１２】
前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知する請求項１〜１１のいずれかに記載の経路案内装置。
【請求項１３】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、
前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出する請求項１〜１２のいずれかに記載の経路案内装置。
【請求項１４】
前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、
前記経路探索部は、前記広告費情報の重み値が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行する請求項１３記載の経路案内装置。
【請求項１５】
前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、
前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させる請求項１２〜１４のいずれかに記載の経路案内装置。
【請求項１６】
前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、
前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項１２〜１５のいずれかに記載の経路案内装置。
【請求項１７】
前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、
前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、
前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項１２〜１６のいずれかに記載の経路案内装置。
【請求項１８】
前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信する請求項１６又は１７記載の経路案内装置。
【請求項１９】
前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信する請求項１６〜１８のいずれかに記載の経路案内装置。
【請求項２０】
前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出する請求項１６〜１９のいずれかに記載の経路案内装置。
【請求項２１】
前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信する請求項１６〜２０のいずれかに記載の経路案内装置。
【請求項２２】
前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、
各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理するサーバを備え、
各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信する請求項１〜２１のいずれかに記載の経路案内装置。
【請求項２３】
コンピュータが、ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付ステップと、
コンピュータが、任意の２拠点間の最短距離を地図情報より取得する距離取得ステップと、
コンピュータが、前記時間的制約に基づき到達可能な１又は複数の観光地を含む拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索ステップと、
コンピュータが、前記経路探索部により探索された最適経路を前記ユーザに報知する報知ステップとを備え、
前記経路探索ステップは、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
コンピュータが、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得ステップを更に備え、
前記経路探索ステップは、前記拠点評価情報の高い拠点が多くなるにつれて、前記経路候補の前記評価値を高く算出する経路案内方法。
【請求項２４】
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、
ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知する報知部としてコンピュータを機能させ、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部としてコンピュータを更に機能させ、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内プログラム。
【請求項２５】
所定の通信網を介して通信可能に接続された端末装置及びサーバを含む経路案内システムであって、
前記サーバは、
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部を備え、
前記端末装置は、
ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
前記入力受付部により受け付けられた出発地点、終着地点、及び前記時間的制約を探索条件データとして前記サーバに送信する端末側通信部とを備え、
前記サーバは、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知するための探索結果データを生成する報知制御部と、
前記探索結果データを前記端末装置に送信するサーバ側通信部とを更に備え、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記サーバは、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内システム。
【請求項１】
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、
ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内装置。
【請求項２】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得する請求項１記載の経路案内装置。
【請求項３】
前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得する請求項１又は２記載の経路案内装置。
【請求項４】
前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得する請求項１〜３のいずれかに記載の経路案内装置。
【請求項５】
前記入力受付部は、ユーザから訪問を希望する１又は複数の目的地点の入力を受け付けけ、
前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出する請求項１〜４のいずれかに記載の経路案内装置。
【請求項６】
前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、
前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付ける請求項１〜５のいずれかに記載の経路案内装置。
【請求項７】
前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備える請求項１〜６のいずれかに記載の経路案内装置。
【請求項８】
前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出する請求項７記載の経路案内装置。
【請求項９】
前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示す請求項８記載の経路案内装置。
【請求項１０】
前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記拠点評価情報を考慮せずに前記評価値を算出する請求項８又は９記載の経路案内装置。
【請求項１１】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、
前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う１回あたりの広告費の目安値に応じた値である請求項１〜１０のいずれかに記載の経路案内装置。
【請求項１２】
前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知する請求項１〜１１のいずれかに記載の経路案内装置。
【請求項１３】
前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、
前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出する請求項１〜１２のいずれかに記載の経路案内装置。
【請求項１４】
前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、
前記経路探索部は、前記広告費情報の重み値が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行する請求項１３記載の経路案内装置。
【請求項１５】
前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、
前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させる請求項１２〜１４のいずれかに記載の経路案内装置。
【請求項１６】
前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、
前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項１２〜１５のいずれかに記載の経路案内装置。
【請求項１７】
前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、
前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、
前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項１２〜１６のいずれかに記載の経路案内装置。
【請求項１８】
前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信する請求項１６又は１７記載の経路案内装置。
【請求項１９】
前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信する請求項１６〜１８のいずれかに記載の経路案内装置。
【請求項２０】
前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出する請求項１６〜１９のいずれかに記載の経路案内装置。
【請求項２１】
前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信する請求項１６〜２０のいずれかに記載の経路案内装置。
【請求項２２】
前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、
各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理するサーバを備え、
各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信する請求項１〜２１のいずれかに記載の経路案内装置。
【請求項２３】
コンピュータが、ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付ステップと、
コンピュータが、任意の２拠点間の最短距離を地図情報より取得する距離取得ステップと、
コンピュータが、前記時間的制約に基づき到達可能な１又は複数の観光地を含む拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索ステップと、
コンピュータが、前記経路探索部により探索された最適経路を前記ユーザに報知する報知ステップとを備え、
前記経路探索ステップは、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
コンピュータが、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得ステップを更に備え、
前記経路探索ステップは、前記拠点評価情報の高い拠点が多くなるにつれて、前記経路候補の前記評価値を高く算出する経路案内方法。
【請求項２４】
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、
ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知する報知部としてコンピュータを機能させ、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部としてコンピュータを更に機能させ、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内プログラム。
【請求項２５】
所定の通信網を介して通信可能に接続された端末装置及びサーバを含む経路案内システムであって、
前記サーバは、
観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部を備え、
前記端末装置は、
ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、
前記入力受付部により受け付けられた出発地点、終着地点、及び前記時間的制約を探索条件データとして前記サーバに送信する端末側通信部とを備え、
前記サーバは、
任意の２拠点間の最短距離を地図情報より取得する距離取得部と、
前記時間的制約に基づき到達可能な１又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、
前記経路探索部により探索された最適経路を前記ユーザに報知するための探索結果データを生成する報知制御部と、
前記探索結果データを前記端末装置に送信するサーバ側通信部とを更に備え、
前記経路探索部は、少なくとも１つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、
前記サーバは、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、
前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内システム。
【図１】
【図２】
【図３】
【図５】
【図６】
【図７】
【図８】
【図４】
【図２】
【図３】
【図５】
【図６】
【図７】
【図８】
【図４】
【公開番号】特開２０１２−２１５４０１（Ｐ２０１２−２１５４０１Ａ）
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１１−７９２６６（Ｐ２０１１−７９２６６）
【出願日】平成２３年３月３１日（２０１１．３．３１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＱＲコード
【出願人】（５０４１４３４４１）国立大学法人 奈良先端科学技術大学院大学 (226)
【出願人】（５１１０８２７６８）株式会社ソリューション・クルー (1)
【出願人】（５０５０２６６８６）国立大学法人滋賀大学 (4)
【Ｆターム（参考）】
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２３年３月３１日（２０１１．３．３１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＱＲコード
【出願人】（５０４１４３４４１）国立大学法人 奈良先端科学技術大学院大学 (226)
【出願人】（５１１０８２７６８）株式会社ソリューション・クルー (1)
【出願人】（５０５０２６６８６）国立大学法人滋賀大学 (4)
【Ｆターム（参考）】
[ Back to top ]