"観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、任意の2拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な1又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、前記経路探索部は、少なくとも1つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内装置。前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得する請求項1記載の経路案内装置。前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得する請求項1又は2記載の経路案内装置。前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得する請求項1~3のいずれかに記載の経路案内装置。前記入力受付部は、ユーザから訪問を希望する1又は複数の目的地点の入力を受け付けけ、前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出する請求項1~4のいずれかに記載の経路案内装置。前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付ける請求項1~5のいずれかに記載の経路案内装置。前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備える請求項1~6のいずれかに記載の経路案内装置。前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出する請求項7記載の経路案内装置。前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示す請求項8記載の経路案内装置。前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記拠点評価情報を考慮せずに前記評価値を算出する請求項8又は9記載の経路案内装置。前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う1回あたりの広告費の目安値に応じた値である請求項1~10のいずれかに記載の経路案内装置。前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知する請求項1~11のいずれかに記載の経路案内装置。前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出する請求項1~12のいずれかに記載の経路案内装置。前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、前記経路探索部は、前記広告費情報の重み値が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行する請求項13記載の経路案内装置。前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させる請求項12~14のいずれかに記載の経路案内装置。前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項12~15のいずれかに記載の経路案内装置。前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理する請求項12~16のいずれかに記載の経路案内装置。前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信する請求項16又は17記載の経路案内装置。前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信する請求項16~18のいずれかに記載の経路案内装置。前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出する請求項16~19のいずれかに記載の経路案内装置。前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信する請求項16~20のいずれかに記載の経路案内装置。前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理するサーバを備え、各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信する請求項1~21のいずれかに記載の経路案内装置。コンピュータが、ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付ステップと、コンピュータが、任意の2拠点間の最短距離を地図情報より取得する距離取得ステップと、コンピュータが、前記時間的制約に基づき到達可能な1又は複数の観光地を含む拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索ステップと、コンピュータが、前記経路探索部により探索された最適経路を前記ユーザに報知する報知ステップとを備え、前記経路探索ステップは、少なくとも1つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、コンピュータが、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得ステップを更に備え、前記経路探索ステップは、前記拠点評価情報の高い拠点が多くなるにつれて、前記経路候補の前記評価値を高く算出する経路案内方法。観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、ユーザから出発地点と終着地点の入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、任意の2拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な1又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知する報知部としてコンピュータを機能させ、前記経路探索部は、少なくとも1つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部としてコンピュータを更に機能させ、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内プログラム。所定の通信網を介して通信可能に接続された端末装置及びサーバを含む経路案内システムであって、前記サーバは、観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部を備え、前記端末装置は、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、前記入力受付部により受け付けられた出発地点、終着地点、及び前記時間的制約を探索条件データとして前記サーバに送信する端末側通信部とを備え、前記サーバは、任意の2拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な1又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約を用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知するための探索結果データを生成する報知制御部と、前記探索結果データを前記端末装置に送信するサーバ側通信部とを更に備え、前記経路探索部は、少なくとも1つの前記拠点を用いて複数の経路候補を生成し、前記ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記サーバは、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する経路案内システム。しかしながら、特許文献2では、ユーザにとって便利な情報が提供されるかも知れないが、広告主に広告への動機付けを与えるような措置が何ら採用されていない。本発明の目的は、出発地点から終着地点までの経路の探索を行った際に、探索された経路に含ませる拠点をコントロールすることで、拠点の広告主に対して広告への動機付けを与える経路案内装置等を提供することである。1本発明による経路案内装置は、観光地を含む拠点に関する拠点情報を記憶する拠点情報記憶部と、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける入力受付部と、任意の2拠点間の最短距離を地図情報より取得する距離取得部と、前記時間的制約に基づき到達可能な1又は複数の前記拠点を選択し、前記出発地点と前記終着地点と前記拠点とを通る最適経路を、前記最短距離と前記時間的制約とを用いて探索する経路探索部と、前記経路探索部により探索された最適経路を前記ユーザに報知する報知部とを備え、前記経路探索部は、少なくとも1つの前記拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、前記拠点の個数が多く、かつ、前記時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、前記評価値が高くなるように前記経路候補を変形させていくことで前記最適経路を探索し、前記拠点の評価の高さを示す拠点評価情報を取得する拠点評価情報取得部を更に備え、前記経路探索部は、前記拠点評価情報の高い拠点が多く含まれるにつれて、前記経路候補の前記評価値を高く算出する。この構成によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報を設定することによって拠点を探索経路に含ませるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。なお、拠点としては、観光地の他、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、その他施設等を採用することができる。また、到着地点を、出発地点と同じに設定とすることで、到着地点の入力を省かせてもよい。また、本発明による経路案内方法、経路案内プログラム、及び経路案内システムは上記の経路案内装置と同様の構成を持っている。2前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得することが好ましい。この構成によれば、広告費情報が高い拠点ほど拠点評価情報が上昇する。その結果、広告費の高い拠点ほど最適経路に含まれる確率を高くすることができる。3前記拠点評価情報取得部は、各拠点に対する第三者による関心の高さを示す関心度を前記拠点評価情報として取得することが好ましい。この構成によれば、関心度が高い拠点ほど拠点評価情報が高くなる結果、最適経路に含まれる確率を高くすることができる。4前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得することが好ましい。この構成によれば、ユーザが訪問を強く希望する拠点を最適経路に優先的に含ませることができる。5前記入力受付部は、ユーザから訪問を希望する1又は複数の目的地点の入力を受け付け、前記経路探索部は、前記目的地点が含まれるように前記経路候補を生成し、前記目的地点の個数が多いほど前記評価値を高く算出することが好ましい。この構成によれば、出発地点及び終着地点とは別にユーザが訪問を希望する目的地点を考慮に入れて最適経路を探索することができる。6前記ユーザの現在位置及び現在時刻を取得する位置情報取得部を更に備え、前記入力受付部は、前記現在位置及び前記現在時刻を前記出発地点及び前記出発時刻として受け付けることが好ましい。この構成によれば、ユーザに対して出発地点及び出発時刻の入力を省かせることができる。なお、本構成において、到着時刻を、現在時刻から一定時間後の時刻とすることで、到着時刻の入力を省かせてもよい。7前記最適経路に含まれた回数に応じて各拠点の広告費を算出する広告費算出部を更に備えることが好ましい。この構成によれば、拠点が最適経路に含まれた実績に基づいた広告費を算出することができる。その結果、拠点が最適経路に含まれた実績がないないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。8前記広告費算出部は、ある拠点に対して算出した前記広告費が当該拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を当該拠点の前記広告費として算出することが好ましい。広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなることもある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。9前記上限広告費は、予め定められた一定期間における前記広告費の上限値を示すことが好ましい。この構成によれば、一定期間における広告費が上限広告費を超えた場合、対象となる広告主に対して上限広告費以上の広告費が請求されることを防止することができる。10前記経路探索部は、前記広告費が前記上限広告費を超えた拠点については、前記広告費情報を考慮せずに前記評価値を算出することが好ましい。この構成によれば、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。11前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記広告費情報は、ある拠点の広告主から当該拠点が前記最適経路に含まれた場合に支払う1回あたりの広告費の目安値に応じた値であることが好ましい。この構成によれば、拠点が最適経路に含まれた場合に支払う1回あたりの広告費の目安値を広告主に予め定めさせ、その目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができる。そのため、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。12前記報知部は、ある拠点が前記最適経路に含まれた場合、当該拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を前記ユーザに報知することが好ましい。この構成によれば、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、広告主からより高い広告費を得ることができる。13前記拠点評価情報取得部は、前記拠点に対して広告主から支払われる広告費の高さを示す広告費情報を前記拠点評価情報として取得し、前記経路探索部は、前記広告費情報の高い拠点ほど前記拠点評価情報の重み値を高く算出し、算出した拠点評価情報の重み値を用いて前記評価値を算出することが好ましい。この構成によれば、広告費情報を高く設定した拠点を含む探索経路の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。14前記拠点評価情報の重み値は、各拠点に対する第三者による関心の高さを示す関心度に基づいて得られる値と、抽選処理により加算されるか否かが決定されるオフセット値との和により規定され、前記経路探索部は、前記広告費情報が高くなるにつれて前記オフセット値が加算される確率が高くなるように前記抽選処理を実行することが好ましい。この構成によれば、オフセット値を加えるか否かが抽選処理により決定されているため、広告費情報の低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。15前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際、当該ユーザが特典を行使するための情報を表示し、当該情報を前記拠点の広告主が所持する端末装置に認識させることが好ましい。この構成によれば、ユーザが特典を行使するための情報を広告主の所持する端末装置に認識させ、行使が許可された場合にユーザに特典を行使させる構成を採用することができる。これにより、ユーザに対して特典を行使するための情報を拠点の広告主に提示しようとするインセンティブを働かせることができる。また、広告主は、実際にユーザが拠点を訪問したか否かを管理することができる。16前記広告主が所持する端末装置は、前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を認識した場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。この構成によれば、広告主が所持する端末装置から特典行使情報をサーバに送信させることで、各拠点対するユーザの訪問履歴をサーバ側で管理することが可能となる。17前記報知部は、ユーザが所持する端末装置に前記最適経路及び前記最適経路に含まれた拠点をユーザが訪問した場合に当該ユーザに付与される特典に関する特典情報を通知し、前記ユーザが所持する端末装置は、前記最適経路に含まれる拠点にユーザが到着した際に、当該拠点において前記特典の行使を促す情報をユーザに報知し、ユーザから前記特典を行使する入力指示を受け付けた場合、特典行使情報をサーバに送信し、前記サーバは、前記特典行使情報に基づいて、各拠点において各ユーザが前記特典を行使した履歴を管理することが好ましい。この構成によれば、ユーザ端末から特典行使情報をサーバに送信させることで、各ユーザの拠点の訪問履歴をサーバ側で管理することが可能となる。そのため、広告主は端末装置を準備することなく、ユーザの拠点への訪問回数を管理することができる。18前記サーバは、前記ユーザが所持する端末装置から前記履歴の閲覧要求を受け付けると、前記ユーザの履歴を前記ユーザが所持する端末装置に送信することが好ましい。この構成によれば、ユーザは自己の履歴を閲覧することができるため、実際に訪れた拠点や各拠点の訪問回数を認識し、思い出を記録することができる。19前記サーバは、拠点の広告主が所持する端末装置から前記履歴の閲覧要求を受け付けると、前記広告主の拠点についての履歴を前記広告主が所持する端末装置に送信することが好ましい。この構成によれば、広告が閲覧され、実際にユーザにより訪問された回数を認識することができる。20前記サーバは、前記履歴から各拠点におけるユーザの訪問数をカウントし、カウントした結果に基づいて各拠点の広告費を算出することが好ましい。この構成によれば、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとることができる。21前記サーバは、各ユーザについて特典を行使した拠点と各ユーザのメールアドレスと対応付けて前記履歴を管理し、各ユーザが所持する携帯端末に対して、各ユーザが特典を行使した拠点についての情報を送信することが好ましい。この構成によれば、ユーザが特典を行使した拠点が記録されているため、サーバはユーザが特典を行使した拠点、つまり訪問したことがある拠点についての情報例えばサービス情報やプロモーション情報をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。22前記拠点評価情報取得部は、あるユーザに対して前記最適経路を探索する場合、当該ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を前記拠点評価情報として取得し、各ユーザについて訪問を希望する拠点について訪問の希望の高さを示す訪問希望度とメールアドレスとを対応付けて管理し、各ユーザが所持する携帯端末に対して、各ユーザが訪問を希望する拠点についての情報を送信するサーバを備えることが好ましい。この構成によれば、ユーザが訪問を希望する拠点についての訪問の希望の高さを示す訪問希望度が記録されているため、サーバはユーザが訪問を希望する拠点についての情報例えばサービス情報やプロモーション情報をユーザの端末装置に送信することで、ダイレクトマーケティングが可能となる。本発明によれば、ユーザは、出発地点及び終着地点と、出発時刻及び希望到着時刻等の時間的制約を入力すると、出発地点から終着地点までを拠点を巡りながら効率良く移動するための最適経路が探索される。ここで、拠点を評価するための拠点評価情報が高い拠点ほど最適経路に含まれる可能性が高くなる。そのため、拠点評価情報によって拠点を探索経路に含まれるか否かをコントロールすることができる。その結果、広告費を多く支払った拠点に対しては拠点評価情報を高く設定することで、その拠点を最適経路に含ませることができる。これにより、拠点の広告主に対して多くの広告費を支払う動機付けを与えることができる。以下、本発明の実施の形態による経路案内装置について図面を参照して説明する。図1は、本発明の実施の形態による経路案内装置の全体構成図である。経路案内装置は、端末装置100及びサーバ200を含んでいる。端末装置100は、例えば、スマートフォンやタブレット端末等の携帯型の情報端末装置により構成されている。サーバ200は、一般的なコンピュータ或いはコンピュータ群クラウドコンピュータにより構成されている。端末装置100及びサーバ200は通信網NTを介して相互に通信可能に接続されている。通信網NTとしては、携帯電話網、及びインターネット通信網により構成されている。端末装置100及びサーバ200には例えばIPアドレス等の固有の通信IDが割り振られ、端末装置100及びサーバ200はこの通信IDを用いて、例えばTCP/IP等の通信プロトコルを用いて相互に通信を行う。端末装置100は、ユーザから訪問を希望する目的地点、終着地点、及び終着地点の希望到着時刻等の入力を受け付け、通信網NTを介してサーバ200に送信する。サーバ200は、端末装置100から送信された目的地点、終着地点、及び終着地点の希望到着時刻を考慮に入れた最適経路の探索を行い、探索結果を端末装置100に送信する。端末装置100はサーバ200により探索された最適経路を表示し、最適経路をユーザに報知する。そして、本実施の形態では、サーバ200は、各拠点を評価するための拠点評価情報が高い拠点ほど最短経路に加えられる回数が増大するように最適経路を探索することを特徴としている。拠点評価情報としては、広告費の高さを示す広告費情報、第三者による各拠点の関心の高さを示す関心度、及び、各ユーザが訪問を希望する拠点について訪問の希望の高さを示す訪問希望度を用いて算出される値が採用される。広告費情報としては広告主による広告費の目安値が採用され、目安値の一例としては広告費の希望単価があげられる。拠点としては、観光地、景勝地、寺社、仏閣、テーマパーク、動物園、植物園、水族館、美術館、博物館、道の駅、及びその他施設等が該当する。以下、本実施の形態による経路案内装置の詳細について説明する。図2は、本発明の実施の形態による経路案内装置の構成を示す機能ブロック図である。端末装置100は、入力受付部101、位置情報取得部102、表示部103報知部の一例、通信部104、及び地図情報記憶部105を備えている。入力受付部101は、例えば、タッチパネル、及びタッチパネルにより検出されたデータを処理するCPU等により構成され、ユーザから出発地点と終着地点との入力を受け付けると共に、出発時刻と希望到着時刻との時間的制約の入力を受け付ける。また、入力受付部101は、ユーザから訪問を希望する1又は複数の目的地点の入力を受け付ける。ここで、入力受付部101は、位置情報取得部102により取得されたユーザの現在位置を中心として所定範囲内にある地図画像を地図情報記憶部105から読み出して表示部103に表示する。そして、入力受付部101は、表示部103に表示された地図画像において、出発地点、終着地点、及び目的地点をタッチさせ、出発地点、終着地点、及び目的地点を入力させる。以下、出発地点、終着地点、及び目的地点を総称する場合は、入力地点と記述する。なお、入力受付部101は、位置情報取得部102により取得されたユーザの現在位置を出発地点として取得し、かつ、位置情報取得部102により取得された現在時刻を出発時刻として取得してもよい。この場合、ユーザは出発地点及び出発時刻を入力する手間が省かれる。地図画像は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。したがって、入力受付部101は、ユーザが表示部103をタッチしたときのタッチ位置に表示されている地図画像の場所の緯度及び経度を特定する。そして、入力受付部101は、特定した緯度及び経度に場所の名称が対応付けられている場合は、その名称をユーザが入力した入力地点として認識する。そして、入力受付部101は、特定した場所の緯度、経度、及び名称を示すデータ群を該当する入力地点の入力地点情報として生成する。また、入力受付部101は、特定した緯度及び経度に場所の名称が対応付けられていない場合は、近傍に位置する名称が対応付けられている場所を特定し、特定した場所の周辺例えば、県立博物館の周辺をユーザが入力した入力地点として認識する。この場合、緯度、経度、及び特定した場所の周辺からなるデータ群が入力地点情報として生成される。次に、入力受付部101は、ユーザが入力した入力地点のうち、どの入力地点が終着地点であるかをユーザに指定させるための入力画像を表示部103に表示させる。そして、入力受付部101は、その入力画像により指定された1の入力地点を終着地点として認識する。そして、入力受付部101は、認識した終着地点についての希望到着時刻の入力をユーザに促す入力画像を表示部103に表示させ、希望等着地点を入力させる。位置情報取得部102は、ユーザの現在位置及び現在時刻を特定する。ここで、位置情報取得部102は、例えばGPSセンサ、及びGPSセンサにより検出されたデータを処理するCPU等を含み、GPSセンサにより検出された位置情報をユーザの現在位置として取得すればよい。ここで、現在位置としては、例えば緯度及び経度が採用される。また、位置情報取得部102は、時計を含み、ユーザの現在位置を取得した時刻を現在時刻として取得すればよい。以下の説明では、位置情報取得部102が取得した現在位置及び現在時刻を出発地点及び出発時刻として採用するものとする。通信部104は、例えば、通信回路、及び通信回路を制御するCPU等から構成され、入力受付部101により生成された入力地点情報及び端末装置100を使用しているユーザのユーザIDを探索条件データとして生成し、サーバ200に送信する。例えば、入力受付部101が入力地点として、A、B、Cを取得し、Aが出発地点、Bが目的地点、及びCが終着地点として指定された場合、Aの入力地点情報は、ユーザの現在位置,Aの名称,現在時刻,出発地点となり、Bの入力地点情報はBの緯度及び経度,Bの名称,目的地点となり、Cの入力地点情報は、Cの緯度及び経度,Cの名称,希望到着時刻:00:00,終着地点となる。したがって、この場合に送信される探索条件データは、例えばAの入力地点情報,Bの入力地点情報,Cの入力地点情報、ユーザIDとなる。表示部103は、例えばタッチパネル、及びタッチパネルを制御するCPU等により構成され、サーバ200により探索された最適経路や、地図画像等を表示する。具体的には、表示部103は、サーバ200から探索結果を示す探索結果データを受信すると、探索結果が示す最適経路を地図画像に重畳して表示する。また、本実施の形態では、実際にユーザが本経路案内装置により探索された最適経路を使用して拠点を訪れたかどうかを拠点の広告主が確かめるために、そのようにして訪れたユーザに対して広告主が特典を付与することができる。この場合、ユーザは端末装置100を所持して、端末装置100によるナビゲーションに従って拠点を訪れる。このときに、ユーザの所持する端末装置100に特典を意味するQRコードを表示させる。そして、広告主の所持する端末装置に備えられたカメラでこのQRコードを読み取らせる。広告主の所持する端末装置は、ユーザの提示したQRコードを解読することで、このQRコードが正規のものであることを確認する。これにより、広告主の所持する端末装置は、ユーザが本経路案内装置により実際に拠点を訪れたか否かを認識することできる。なお、広告主の所持する端末装置としては、スマートフォンでも良い。また、両者の端末間の通信方式としてQRコード以外の他の通信方式を利用してもよい。サーバ200は、各拠点のQRコードを予め後述するテーブル記憶部207に記憶させ、後述する探索結果データに最適経路に含まれる拠点のQRコードを含ませて、端末装置100に送信すればよい。サーバ200は、データ取得部201、拠点評価情報取得部202、経路探索部203、報知制御部204報知部の一例、探索結果管理部205、広告費算出部206、テーブル記憶部207、地図情報記憶部208、探索履歴記憶部209、通信部210、及び距離取得部211を備えている。ここで、データ取得部201~広告費算出部206、及び距離取得部211は主にCPUにより構成され、テーブル記憶部207~探索履歴記憶部209は主に記憶装置により構成され、通信部210は主に通信回路により構成されている。データ取得部201は、1又は複数の拠点について広告主から支払われる広告費情報を取得する。本実施の形態では、広告費情報としては、例えばある拠点の広告主から当該拠点が最適経路に含まれた場合に支払う1回あたりの広告費の目安値が採用される。具体的には、広告費情報としては、目安値の最大値を満点例えば、5点としたときの各拠点の目安値の割合が採用される。目安値としては、例えば100円、200円というように、探索経路に1回含まれた際に広告主が支払うことを希望する金額を採用すればよい。また、目安値の最大値が1000円であり、ある拠点の目安値が100円とすると、5×100/1000/5を目安値の割合として採用すればよい。本実施の形態では、広告主の拠点が最適経路に含まれた実際の回数に応じて広告費を徴収する形態を採用している。この場合、拠点が最適経路に含まれた回数が広告主の意思に反して多かったり、少なかったりすることは好ましくない。そこで、本経路案内装置を運営する運営主は、拠点が最適経路に含まれた場合に支払う1回あたりの広告費の目安値を広告主に予め定めさせている。これにより、広告費の目安値に応じて拠点が最適経路に含まれる回数をコントロールすることができ、広告主の想定する広告費と実際に請求する広告費との齟齬を抑制することができる。したがって、データ取得部201は、広告主端末300からアクセスされると、目安値の入力を促す入力画像を広告主端末300に表示させ、この入力画像を通じて目安値を入力させ、サーバ200に目安値を送信させることで、目安値を取得する。この際、データ取得部201は、目安値と併せて、広告主を識別するための広告主ID、拠点の名称、及び位置情報を送信させる。位置情報としては、拠点の場所を示す緯度及び経度を採用すればよい。そして、データ取得部201は、その拠点に対してその拠点を一意的に識別するため拠点IDを付与し、拠点IDと拠点の名称と拠点の位置情報とを対応付けて図6に示す拠点情報テーブル拠点情報記憶部の一例に書き込む。また、データ取得部201は、取得した広告費情報を広告主IDと拠点IDと対応付けて図6に示す広告費情報テーブルに書き込む。図6に示すように、拠点情報テーブルには、拠点ごとに1つのレコードが割り当てられ、各レコードに拠点ID、拠点の名称、及び位置情報が対応付けて格納されていることが分かる。また、広告費情報テーブルには、広告主ごとに1つのレコードが割り当てられ、各レコードに広告主ID、拠点ID、及び広告費情報が対応付けられて格納されていることが分かる。なお、上記の広告費情報の取得方法は一例にすぎず、他の方法を用いても良い。例えば、運営主が広告主から広告主ID、拠点の名称、位置情報、及び広告費情報を直接聞き出し、入力装置を用いてサーバ200に入力することで、データ取得部201にこれらの情報を取得させてもよい。また、データ取得部201は、通信網NTに存在するWEBサーバにより運営されている口コミサイトにおいて、第三者がある拠点を紹介するために書き込んだ情報である口コミ情報を取得する。具体的には、データ取得部201は、通信網NT上の口コミサイトを探索し、探索した口コミサイトのHTMLデータを定期的に取得し、取得したHTMLデータを分析することで、口コミ情報を書き込んだユーザを特定し、当該ユーザにユーザIDを付与し、付与したユーザIDとそのユーザが書き込んだ口コミ情報とを対応付けて図6に示す口コミテーブルに書き込む。そして、データ取得部201は、図6に示す口コミテーブルを分析し、各拠点の口コミ情報の平均評価点数以下、口コミ点数と記述する。を取得し、取得した口コミ点数を関心度とし、拠点IDと対応付けて図6に示す関心度テーブルに書き込む。図6に示すように、関心度テーブルには、拠点ごとに1つのレコードが割り当てられ、拠点ID及び関心度が対応付けて格納されていることが分かる。口コミ情報は、例えば、ある拠点に対する書き込み数が多いほど、その拠点に対する第三者の関心は高いと言える。そこで、本実施の形態では、口コミサイトを監視し、監視結果から各拠点の口コミ情報の口コミ点数を取得し、取得した口コミ点数を各拠点の関心度として採用している。なお、口コミ点数は、口コミ情報の書き込みを行った各ユーザが付けた点数例えば5点満点の点数の全ユーザの和/書き込みを行ったユーザ数で計算される。例えば、ある拠点に対して書き込みを行ったユーザがA,B,C,Dとして、それぞれが、その拠点に対して4点、5点、4点、3点をつけたとすると、口コミ点数は4543/4=4点と算出される。ここで、データ取得部201は、口コミ情報を分析して特定した拠点が拠点情報テーブルに格納されていない新規の拠点である場合、その拠点に拠点IDを付与し、地図情報を参照し、その拠点の名称からその拠点の位置情報を取得し、拠点IDと拠点の名称と位置情報とを対応付けて拠点情報テーブルにも書き込む。なお、関心度として、口コミ点数を採用したが、本発明はこれに限定されず、第三者が拠点を評価する指標であれば、どのような指標を採用してもよい。例えば、テレビ、新聞等で紹介される拠点ランキングをオペレータが集計し、その集計結果に基づいて関心度を設定してもよい。また、データ取得部201は、本経路案内装置を使用するユーザのユーザIDと、そのユーザが訪問を希望する拠点についての希望の度合いを示す訪問希望度とを取得し、拠点IDとユーザIDと訪問希望度とを対応付けて図6に示す訪問希望テーブルに書き込む。ここで、データ取得部201は、例えば、ユーザが本経路案内装置を初めて使用する場合にユーザ登録を行わせ、そのときにユーザIDと訪問希望度とを取得すればよい。なお、訪問希望度としては、ユーザが訪問を希望する拠点についての拠点別の希望度合いを例えば所定満点で点数表示したデータを採用すればよい。また、訪問希望度は、ユーザ登録後にユーザが適宜設定できるようにしてもよい。図6に示す用に訪問希望テーブルは、拠点IDのそれぞれについて各ユーザIDと訪問希望とを対応付けて格納している。例えば、拠点Aにつき、ユーザU1,U2,U3がそれぞれ、1,2,3という訪問希望度を指定した場合、拠点Aの拠点IDのレコードには、ユーザU1,U2,U3の各ユーザIDと、それぞれの訪問希望度である1,2,3とが対応付けて格納される。ここで、データ取得部201は、ユーザが訪問を希望した拠点が拠点情報テーブルに格納されていない場合、その拠点に対して拠点IDを付与し、地図情報を参照して位置情報を取得し、その拠点の名称から拠点IDと拠点の名称と位置情報とを対応付けて拠点情報テーブルに書き込めばよい。また、データ取得部201は、ユーザ登録時にユーザのメールアドレスと名前とを取得し、ユーザIDと、メールアドレスと名前とを対応付けて図6に示すユーザ情報テーブルに書き込む。図6に示すようにユーザ情報テーブルにはユーザごとに1つのレコードが割り当てられ、各レコードにユーザID、メールアドレス、及び名前が対応付けて格納されていることが分かる。拠点評価情報取得部202は、テーブル記憶部207に記憶された各種テーブルに記憶された情報から各拠点の評価の高さを示す拠点評価情報を取得する。ここで、拠点評価情報は、広告費情報、関心度、及び訪問希望度を含み、各拠点を評価するための情報である。したがって、拠点評価情報取得部202は、本経路探索装置を使用しているユーザのユーザIDをキーとして、訪問希望度テーブルを参照し、当該ユーザの各拠点に対する訪問希望度を検索する。また、拠点評価情報取得部202は、拠点情報テーブルに記憶された各拠点の拠点IDをキーとし、広告費情報テーブル、関心度テーブルを参照し、各拠点の広告費情報、関心度を検索する。そして、拠点評価情報取得部202は、検索の結果得られた各拠点の広告費情報及び関心度と、ユーザが訪問希望度を設定している拠点については訪問希望度とを拠点評価情報として経路探索部203に供給する。図2に戻り、距離取得部211は、任意の2拠点間の最短距離を地図情報記憶部208により記憶された地図情報より取得する。ここで、任意の2拠点間の距離とは、例えば、拠点としてA,B,Cがあったとすると、A-B、A-C、B-Cのそれぞれの最適距離が該当する。また、最短距離としては、2拠点間の直線距離を採用してもよいし、2拠点間を繋ぐ最短経路を例えば、Aアルゴリズムを用いて求め、その距離を採用してもよい。いずれにせよ、2拠点間の距離を評価する値を用いればよい。地図情報は、道路交通網の地図情報である。具体的には、地図情報は、交差点や屈曲点等の道路上の所定の地点に対応するノードと、各ノードをつなぎ道路に対応するリンクとからなる有向グラフとが含まれている。また、地図情報は、各場所に実際の緯度及び経度の情報が対応付けられていると共に、目的地点及び終着地点の候補となる場所にはその場所の名称が対応付けられている。各ノード及び各リンクには、それぞれ固有の識別符号が割り当てられている。また、有向グラフGは、Vをノードの集合とし、Eをリンクの集合とすると、G=V,Eで表される。経路探索部203は、時間的制約に基づき到達可能な1又は複数の拠点を選択し、出発地点と目的地点と終着地点と拠点とを通る最適経路を、最短距離と、時間的制約を用いて探索する。具体的には、経路探索部203は、少なくとも1つの拠点を用いて複数の経路候補を生成し、ユーザの移動距離が短く、拠点の個数が多く、かつ、時間的制約が満たされるほど値が高くなるように各経路候補の評価値を算出し、評価値が高くなるように経路候補を変形させていくことで最適経路を探索する。そして、経路探索部203は、拠点評価情報の高い拠点が多く含まれるように、経路候補の評価値を算出する。ここで、経路探索部203は、特許文献1に示す手法を利用して最適経路を探索すればよい。具体的には、経路探索部203は、ユーザにより入力された出発地点と到着地点との中間地点を求め、中間地点を基準として一定の領域を設定する。一定の領域としては、平均移動速度×希望到着時刻-出発時刻/2とする円や、楕円を採用すればよい。そして、経路探索部203は、設定した領域内に位置する拠点を全て抽出する。平均移動速度としては、徒歩、自転車、及び自動車等の移動手段のうちいずれの移動手段を使用するかをユーザに選択させ、選択させた移動手段の移動想定速度を採用すればよい。この手法を採用する場合、経路探索部203は、抽出した拠点についての拠点評価情報を拠点評価情報取得部202に供給させればよい。そして、経路探索部203は、出発地点と、終着地点と、抽出した全ての拠点と、目的地点とを任意に組み合わせて、複数の個体経路候補の一例を現世代の個体として生成する。ここで、抽出した拠点を例えばA,B、ユーザが入力した目的地点をC、出発地点をS、及び到着地点をEとすると、S-A-E、S-A-B-E、S-B-A-E、S-A-B-C-Eというように、A,B,Cのうち少なくともA又はBを含む全ての順列組み合わせのそれぞれが、1つの個体として生成される。なお、各個体は、可変長リストのデータ構造を持つ。以下、目的地点及び拠点を総称する場合は巡回地点と記述する。したがって、個体は、出発地点、巡回地点、及び終着地点から構成される。なお、上記の個体の生成手法は一例にすぎない。例えば、拠点情報テーブルに記憶された拠点と、ユーザが指定した目的地点とをランダムに抽出して個体を生成してもよい。この場合、拠点評価情報の高い拠点ほど抽出される確率が高くなるように拠点を抽出してもよい。こうすることで、拠点評価情報の高い拠点が個体に含まれる確率が高くなる結果、拠点評価情報の高い拠点が最適経路に含まれる可能性を高めることができる。また、拠点を抽出するにあたっては、ユーザが入力した目的地点又は終着地点に対して近くに位置する拠点が個体に含まれる確率が高くなるように拠点を抽出してもよい。また、ユーザが入力した目的地点、又は終着地点が拠点情報テーブルに登録された拠点でもあるために、同じ個体に同じ地点が複数含まれた場合、重複する地点を削除して1つにすればよい。そして、経路探索部203は、現世代の個体を遺伝的アルゴリズムで規定された手法例えば、交叉、突然変異等を用いて変形させる。次に、経路探索部203は、各個体の評価値を求める。評価値については後述する。次に、経路探索部203は、評価値が高い順に一定個数の個体を次世代の個体として残す。そして、経路探索部203は、この処理を一定回数繰り返し、最終的に残った個体のうち、評価値が最大の個体を求める。ここで、評価値は、特許文献1の評価値の算出式を下記の式1のように変更した算出式を用いて算出される。評価値=α経路候補中の拠点の拠点評価情報の重み値の合計-β総移動距離/巡回地点数-γ総移動時間/巡回地点数1なお、右辺の第2項から第3項は特許文献1の式1とほぼ同じであるが、第1項は特許文献1の式1の第1項と相違している。α、β、γは、各項の値を同程度の桁数の値に揃えるための係数である。以下、出発地点S、終着地点E、拠点A、及び目的地点Bからなる個体X1S-A-B-Eを例に挙げて式1を説明する。第2項に示す総移動距離は個体X1の最短経路の距離である。この場合、経路探索部203は、まず、S-A、A-B、B-Eのそれぞれの最短距離の和を個体X1の総移動距離として算出すればよい。この場合、S-A、A-B、B-Eのそれぞれの最短距離が距離取得部211により取得されていればその距離を用い、取得されていなければ地図情報から算出することで求めればよい。第2項に示す巡回地点数は、個体に含まれる目的地点及び拠点の数を示している。個体X1には拠点A及び目的地点Bの2つの巡回地点が含まれているため2が該当する。ここで、第2項は、総移動距離を巡回地点数で除したものである。したがって、総移動距離が長くなり、巡回地点数が少ないほど、第2項の値は増大する結果、評価値は小さくなる。なお、本実施の形態では、第2項に示す総移動距離をユーザのおよその移動距離と想定して評価値を算出している。但し、これは一例であり、個体に対する最短経路を例えばAアルゴリズムを用いて算出し、算出した最短経路をユーザの移動距離として採用してもよい。第3項に示す総移動時間は、個体X1の移動時間を示し、個体X1の総移動距離をユーザの平均移動速度で割ることで求められる。第3項に示す巡回地点数は、第2項のものと同じである。よって、総移動時間が長くなり、巡回地点数が少ないほど、第3項の値は増大する結果、評価値は増大する。第1項の拠点評価情報の重み値は、式2で表される。Ki=MinwMax,gwiCi×Adv2Adifrand100≦v100then1else0vawawMaxここで、iは拠点を特定するためのインデックスである。wMaxは予め定められた定数であり、例えば、gwiの最高値例えば5と同じ値例えば5が採用されている。gwiは拠点iに対する関心度口コミ点数と訪問希望度との合計値又は平均値である。Ciは拠点iに対して予め付与されたオフセット値である。ここで、オフセット値Ciは予め定められた値が採用され、全拠点について同じ値に設定してもよいし、広告費情報の高い拠点ほど高い値を付与してもよい。Advはvが乱数値rand以上の場合に1を返し、vが乱数値rand未満の場合に0を返す関数である。vは広告費情報の最高値に対する拠点iの広告費情報の割合を示している。awiは拠点iの広告費情報を示している。awMaxは拠点情報テーブルに登録された各拠点の広告費情報の最高値を示し、例えば5が採用されている。ここで、拠点評価情報の重み値KiはMinの括弧内の第1項と第2項との値を比較し、小さい方の値が採用される。これにより、Kiは少なくともwMax以上の値が設定されることになり、広告費情報が低い拠点であっても最適経路に加えられる可能性を高めることができる。拠点評価情報の重み値Kiは、式2のCi×Advに示すように、gwiにオフセット値Ciを加えるか否かが抽選処理により決定されている。この抽選処理は、Adifrand100≦v100then1else0に示すように、広告費情報が高くなるにつれてAdv=1となる確率が高められている。つまり、広告費情報が高いほど、gwiにオフセット値Ciが加算される確率が高くされている。これにより、広告費情報を高く設定した拠点を含む個体の評価値が高くなるため、広告費情報の高い拠点が最適経路に含まれる確率を高めることができる。その結果、広告主の意思に即した広告費を広告主に請求することができる。なお、拠点評価情報の重み値Kiは、式2を用いて算出したがこれは一例であり、他の手法を用いてもよい。例えば、拠点評価情報の重み値Kiを式3を用いて算出してもよい。Ki=MinwMax,gwi3このgwiの値が高いほど拠点iをより高い確率で最適経路に含ませることができる。但し、式3の手法を用いると、gwiが高い拠点のみが最適経路に含まれ、gwiが低い拠点が最適経路にほとんど含まれない事態も発生し得る。一方、式2では、オフセット値Ciを加えるか否かが抽選処理により決定されているため、gwiの低い拠点が最適経路にほとんど含まれなくなる事態を回避することができる。上記の個体X1では、拠点Aが含まれている。したがって、拠点Aに対する拠点評価情報の重み値Kiが式2又は式3を用いて算出され、その拠点評価情報の重み値Kiが個体X1の評価値に加算される。なお、個体X1において、目的地点Bが拠点であるも場合、式2又は式3を用いて目的地点Bの拠点評価情報の重み値Kiが算出され、個体X1の評価値に加算される。そして、経路探索部203は、上記の処理により最終的に1つの個体を求め、その個体を繋ぐ最短経路を地図情報から求め、求めた最短経路を最適経路として算出する。なお、経路探索部203は、個体の最短経路を例えばAアルゴリズム等を用いて算出すればよい。なお、経路探索部203は、個体まで求め最短経路は端末装置100に求めさせるようにしてもよい。この場合、経路探索部203は、求めた個体を示す情報を探索結果データに含ませて端末装置100に送信すればよい。報知制御部204は、経路探索部203により算出された最適経路を示す情報と、最適経路に含まれている拠点に対する特典情報とを含む探索結果データを生成し、通信部210を介して端末装置100に送信する。ここで、特典情報としては、拠点をユーザが訪問した際にユーザに付与される特典に関する情報が採用され、例えばクーポンが採用される。クーポンは、例えば拠点の入場料を割り引いたり、飲食費を割り引いたりするための引き替え券である。ユーザは、実際に拠点に訪れた際、クーポンを表した特典提示画像を表示部103に表示して拠点の管理人に特典提示画像を提示することにより拠点による特典が付与される。こうすることで、拠点に訪問するユーザ数を増大させることができ、広告主に広告費情報をより高く設定し、自身の拠点を最適経路に含ませようとする動機付けを付与することができる。その結果、運営主はより高い広告費を得ることができる。また、報知制御部204は、最適経路に含まれる各拠点を広告するための広告情報を探索結果データに含ませても良い。これにより、探索結果データを受信した端末装置100において最適経路が表示された際、最適経路に含まれる拠点の広告が表示され、ユーザに対して拠点を広告することができる。探索結果管理部205は、各拠点が経路探索部203により探索された最適経路に含まれた回数を管理する。具体的には、探索結果管理部205は、拠点情報テーブルに記憶された各拠点のそれぞれについて最適経路に含まれた履歴を保持するための探索履歴を生成し、探索履歴記憶部209に記憶させておく。そして、探索結果管理部205は、経路探索部203により最適経路が探索される都度、その最適経路に含まれた拠点を特定する。そして、探索結果管理部205は、特定した拠点の探索履歴にその拠点が最適経路に含まれた日時を書き込む。これにより、各拠点が最適経路に含まれた実際の回数及び日時を管理することができる。広告費算出部206は、最適経路に含まれた回数に応じて各拠点の広告費を算出する。具体的には、広告費算出部206は、例えば所定の料金徴収日が到来したとき、前回料金を徴収した日から現在までにおける各拠点が最適経路に含まれた回数を探索履歴を参照して特定し、特定した回数に1回あたりの広告単価を乗じることで各拠点の広告費を算出する。こうすることで、拠点が最適経路に含まれた実績に基づいた広告費を算出して請求することができる。その結果、拠点が最適経路に含まれていないにも関わらず、広告主に対して広告費が請求されることを防止することができ、広告主にとって満足のいく課金体系を提供することができる。ここで、1回あたりの広告単価としては、例えば、広告費情報、つまり、広告主が指定した目安値を採用してもよいし、拠点によらず一律に同じ値を採用してもよい。また、広告費算出部206は、広告費情報の規定値よりも高い拠点に対しては、最適経路に含まれた回数が増大するにつれて割引率が増大するように割引を行っても良い。また、広告費算出部206は、各拠点に対して算出した広告費が各拠点に対して予め定められた上限広告費を超えた場合、当該上限広告費を各拠点の広告費として算出してもよい。本実施の形態では、式2に示すように各拠点の拠点評価情報の重み値Kiを確率的に変動させているため、例えば、広告費情報が低く設定されている拠点にも関わらず、最適経路に含まれる回数が広告主の意図に反して多くなる可能性がある。この場合、広告主に対して広告単価に回数を乗じた値を広告費として請求すると、広告主の意思に反して広告費が膨大な金額になる虞がある。そこで、上限広告費を設けておくことで、このような事態の発生を回避することができる。ここで、上限広告費は、拠点を登録する際に広告主に申請させるようにしてもよいし、運営主が広告費情報に応じて予め定めた値を設定するようにしてもよい。なお、上限広告費は、料金徴収日が到来してから次の料金徴収日が到来するまでの一定期間例えば1月、30日、60日等における広告費の上限値を示している。テーブル記憶部207は、例えば記憶装置により構成され、図6に示す各種テーブルを記憶している。地図情報記憶部208は、最適経路を探索する際に用いられる地図情報を記憶している。探索履歴記憶部209は探索結果管理部205により生成される探索履歴を記憶している。通信部210は、通信回路及びCPU等により構成され、サーバ200により生成される種々のデータ探索結果データ等を通信網NTを介して端末装置100に送信すると共に、端末装置100から送信される探索条件データの他、広告主端末300、口コミサイトが掲載されたWEBサーバ等から送信される種々のデータを受信する。次に、本発明の実施の形態による経路案内装置の動作について説明する。図3は、本発明の実施の形態による経路案内装置の処理を示すフローチャートである。まず、入力受付部101は、ユーザから終着地点、終着地点に対する時間的制約、及び目的地点の入力を受け付けS1でYES、入力された目的地点及び終着地点毎の入力地点情報を生成するS2。一方、入力受付部101は、これらのうち少なくとも終着地点及び終着地点に対する時間的制約を受け付けない場合S1でNO、処理をS1に戻す。次に、位置情報取得部102は、現在位置及び現在時刻を取得するS3。次に、通信部104は、入力された目的地点、現在位置、及び現在時刻から出発地点、終着地点、及び各目的地点のそれぞれの入力地点情報を生成し、生成した入力地点情報とユーザIDとを含む探索条件データを生成しサーバ200に送信するS4。次に、サーバ200の通信部210が、探索条件データを受信するとS10でYES、拠点評価情報取得部202は、テーブル記憶部207に記憶された各種テーブルを参照し、関心度、広告費情報、及び訪問希望度を取得し、経路探索部203に供給するS11。経路探索部203は、出発地点及び終着地点から一定の領域を設定し、この領域内に含まれる拠点を拠点情報テーブルから抽出し、式2又は式3に示すように、抽出した各拠点の拠点評価情報の重み値Kiを供給された関心度、広告費情報、及び訪問希望度を用いて算出するS12。一方、通信部210は、探索条件データを受信しない場合S10でNO、処理をS10に戻す。次に、経路探索部203は、抽出した拠点のうち少なくとも1つの拠点、必要に応じて少なくとも1つの目的地点を任意に組み合わせ、先端に出発地点、後端に終着地点を配置して複数の個体を生成し、各個体の評価値を算出し、所定のアルゴリズム例えば遺伝的アルゴリズムを一定回数繰り返し、評価値の高い最適経路を探索するS13。次に、報知制御部204は、経路探索部203により探索された最適経路を示す情報と最適経路に含まれている拠点に対する特典情報及び広告情報とを含む探索結果データを生成し、端末装置100に送信するS14。次に、端末装置100の通信部104が探索結果データを受信するとS5でYES、表示部103は最適経路が重畳された地図画像を表示するS6。これにより、ユーザに探索結果が報知される。図4、図5は、本発明の実施の形態における経路案内装置において、広告費情報を考慮に入れて経路探索を行った場合と関心度と希望度の合計値又は平均値のみを考慮に入れて経路探索を行った場合との探索例を示した図である。図4Aは探索対象エリア周辺の地図画像であり、図4Bはこの探索例で用いられた拠点に関するデータを示した表である。なお、図4Bにおいて広告費情報から計算される加算確率が書き込まれた拠点は、広告費情報が設定された拠点である。また、図4Bにおいて広告費情報から計算される加算確率が書き込まれていない拠点は、広告費情報が設定されておらず、関心度のみが設定された拠点である。広告費情報から計算される加算確率は、式2のAdv=1になる確率である。この探索例では、図4Bに示す奈良公園、大仏殿等の各拠点に対して図示する関心度と訪問希望度との合計値又は平均値、広告費情報から計算される加算確率、拠点評価情報の重み値が設定されているものとする。ここで、拠点評価情報の重み値は式2のKiを示している。図4Bにおいて、奈良公園、大仏殿、春日大社、浮見堂は、広告費情報が登録されていないため、関心度と訪問希望度との合計値又は平均値のみが設定されている。また、図4Bにおいて、国立博物館、宝物殿は広告費情報が登録されているため、関心度と訪問希望度との合計値又は平均値に加えてオフセット値C=2が加算された値も設定されている。奈良公園等の関心度と訪問希望度との合計値又は平均値のみ設定された拠点では、拠点評価情報の重み値は関心度と訪問希望度との合計値又は平均値と同じ値を採っていることが分かる。一方、国立博物館等の広告費情報が設定された拠点は拠点評価情報の重み値が2つの値を採っていることが分かる。具体的には、国立博物館は3.5又は5.0の拠点評価情報の重み値を採る。これは、式2において、オフセット値Ciが2.0に設定されているため、抽選処理によりAdv=1の場合は関心度と訪問希望度との合計値又は平均値である3.5に2.0が加えられて5.0になるからである。一方、抽選処理によりAdv=0の場合は関心度と訪問希望度との合計値又は平均値である3.5がそのまま拠点評価情報の重み値として使われる。宝物殿も同様に、拠点評価情報の重み値は2.7又は4.7=2.72.0の値を採る。なお、宝物殿の方が国立博物館よりも広告費情報から計算される加算確率が高いため、広告費情報が高くなる確率は、国立博物館よりも高い。図5Aは、関心度と訪問希望度との合計値又は平均値のみ考慮したときの探索結果を示している。図5Bは、関心度と訪問希望度との合計値又は平均値に加えて広告費情報を考慮した場合の探索結果を示している。図5Aの場合、国立博物館及び宝物殿の広告費情報はそれぞれ、3.5、2.7と設定されて最適経路が探索されているため、両拠点とも最適経路に含まれていないことが分かる。一方、図5Bでは広告費情報が考慮され、国立博物館及び宝物殿の拠点評価情報の重み値がそれぞれ5.0、4.7と設定されて最適経路が探索されたため、両拠点が最適経路に含まれていることが分かる。このように、拠点評価情報の重み値を考慮に入れて最適経路を探索すると、広告費情報を支払った拠点が広告費情報を支払っていない拠点に比べて最適経路に含まれる可能性を高くすることができる。これにより、広告主に対して、広告費を支払う動機付けを付与することができる。なお、上記実施の形態では、広告費情報として、目安値を採用したが、本発明はこれに限定されず、広告主が実際に支払った広告費を広告費情報として採用してもよい。また、上記実施の形態では、遺伝的アルゴリズムを用いて最適経路を探索したが、これに限定されず、LinKernighanアルゴリズム等を採用してもよい。また、上記実施の形態では、経路案内装置は端末装置100とサーバ200とで構成されていたがこれに限定されず、一台のコンピュータで構成してもよい。この場合、図2に示すサーバ200の各ブロックを端末装置100に設ければよい。また、上記実施の形態において、端末装置100の各ブロックは経路案内装置としてコンピュータを機能させるための端末装置用のプログラムを実行することで実現され、サーバ200の各ブロックは経路案内装置としてコンピュータを機能させるためのサーバ用のプログラムを実行することで実現される。この場合、端末装置用のプログラム及びサーバ用のプログラムをコンピュータ読み取り可能記録媒体例えば、DVD-ROM等に記録させてユーザに提供すればよい。また、上記実施の形態において、経路探索部203は、ある拠点の広告費が上限広告費を上回った場合、当該拠点については、次の料金徴収日が到来するまで、拠点評価情報を考慮することなく評価値を算出してもよい。この場合、広告費算出部206は、各拠点につき、最適経路に含まれる都度、最新の料金徴収日からの広告費の累積値を求める。そして、広告費の累積値が上限広告費以上になると、経路探索部203は、当該拠点について、次の料金徴収日が到来するまで、式2のAdvをAdv=0にして拠点評価情報の重み値Kiを算出すればよい。つまり、経路探索部203は、当該拠点について、次の料金徴収日が到来するまで、関心度にオフセット値Ciを加算せずに拠点評価情報の重み値Kiを求めればよい。こうすることで、広告費が上限広告費を超えた拠点が最適経路に含まれることが防止され、この拠点に対して上限広告費以上のサービスが付与されることを防止することができる。また、上記実施の形態では、出発地点と終着地点とが別の地点であるとして説明したが、ユーザが終着地点として出発地点と同じ地点を指定した場合、出発地点を終着地点として、最適経路を探索すればよい。これにより、目的地点の最寄りの駅から種々の拠点や目的地点を巡回し、最終的に最寄りの駅に戻るというような観光コースを最適経路として、ユーザに提供することができる。また、上記実施の形態において説明した特典を意味するQRコードを広告主の所持する携帯端末が読み取る際のフローチャートを示すと下記のようになる。以下の説明では、ユーザの所持する端末装置100をユーザ端末と記述し、広告主の所持する端末装置を広告主端末と記述する。図7は、ユーザ端末と広告主端末との処理を示すフローチャートである。まず、ユーザ端末は、サーバ200により探索された最適経路に従ったナビゲーションを開始するS20。この場合、ユーザ端末はGPSセンサにより検出される現在位置に従って地図画像上に表示されたユーザの現在位置を示すマークを随時更新し、ユーザに現在位置を報知する。次に、ユーザ端末は、最適経路に含まれるある拠点に到着するとS21でYES、特典提示画像を表示するS22。ここで、特典提示画像には、広告主が自身の拠点についてのクーポンを表す画像に加えてQRコードが含まれている。なお、QRコードに代えて、例えば1次元や2次元のバーコードを特典提示画像に含ませても良い。一方、ユーザ端末は、最適経路に含まれるある拠点に到着していない場合S21でNO、処理をS23に進める。次に、広告主端末は、ユーザ端末に表示された特典提示画像に含まれるQRコードをカメラを用いて読み取るS30。次に、広告主端末は、読み取ったQRコードが自己の拠点に対応するQRコードであるかを認証するS31。S31によってQRコードが認証されると、ユーザは拠点から特典を受けることができる。これにより、ユーザに対して特典提示画像を拠点の広告主に提示しようとするインセンティブを働かせることができる。次に、広告主端末は、ユーザが実際に広告主の拠点に訪問したことを示す訪問情報をサーバ200に送信するS32。これを受けたサーバ200は、訪問情報にしたがって、該当する拠点についてのユーザの訪問数を1カウントアップし、図6に示すユーザ情報テーブルの訪問履歴を更新する。これにより、拠点を最適経路に含めたことによる集客効果を確認するための客観的なデータをサーバ200に記録させることができる。次に、ユーザ端末は、終着地点に到着すると、ナビゲーションを終了させるS23でYES。一方、ユーザ端末は、終着地点に到着していない場合、ナビゲーションを継続させるために処理をS21に戻す。つまり、ユーザ端末は、終着地点に到達するまで、最適経路に含まれる拠点に到達する毎にその拠点の特典提示画像を表示する。次に、広告主端末を介さずにユーザ端末とサーバ200とがユーザによる特典の行使を管理する態様について説明する。図8は、ユーザ端末とサーバ200とがユーザによる特典の行使を管理するための処理を示すフローチャートである。S40、S41、S46は図7のS20、S21、S23と同一であるため説明を省く。S42において、ユーザ端末は、特典についての画像を表示する。この画像は、ユーザが拠点から受ける特典を閲覧する画像と、上記の特典提示画像とが含まれる。次に、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けるとS43でYES、特典提示画像を画面に大きく表示するS44。ここで、ユーザは例えば、特典についての画像において特典提示画像が表示された領域をタッチすることで特典を行使するための入力指令を入力すればよい。広告主はこの特典提示画像を確認すると、ユーザに対して特典を付与する。これにより、ユーザに対して特典提示画像を表示させて広告主に見せるインセンティブを与えることができる。なお、ユーザ端末は、ユーザから特典を行使するための入力指令を受け付けない場合S43でNO、処理をS46に進める。次に、ユーザ端末は、ユーザが特典を行使したことを示す特典行使情報をサーバ200に送信するS45。次に、サーバ200は特典行使情報を受信しS50、ユーザが拠点を訪問したことを示す訪問履歴を更新するS51。この場合、サーバ200は、図6に示すユーザ情報テーブルに含まれる該当するユーザの訪問履歴を更新すればよい。図6の例においてユーザ拠点Aを訪問したとすると、拠点Aの訪問回数が1カウントアップされて訪問履歴が更新される。S51において、例えばあるユーザのユーザ端末から拠点Aについての特典行使情報を受信した場合、サーバ200が該当するユーザの拠点Aの訪問回数を1カウントアップすればよい。このように、ユーザ端末から特典行使情報を送信させて、各ユーザの拠点の訪問履歴を管理することで、広告主はQRコードを読み取るための広告主端末を準備する手間を省くことができる。これによりコストダウンを図ることができる。また、拠点においてQRコードを読み取る必要がなくなるため、広告主の時間や手間等を削減することができる。よって、広告主に自己の拠点を登録させようとする動機付けを与えることができる。次に、特典行使情報の活用方法について説明する。A広告主は、広告主端末からサーバ200にアクセスし、サーバ200に閲覧要求を送信する。閲覧要求を受信したサーバ200は当該広告主の拠点の訪問履歴を広告主端末に送信する。これによりこの広告主は自己の拠点の訪問履歴を閲覧することで、最適経路に自己の拠点が含まれてユーザにより広告が閲覧された回数と、ユーザが実際に自己の拠点に訪問したと考えられる回数とを認識することができる。よって、広告主は、広告費とその効果の検証を行い、広告費設定の検討に利用することができる。B広告費の課金に関して、ユーザが実際に拠点を訪れた回数に基づいて、運営主は広告主に広告費の請求を行ってもよい。この場合、広告費算出部206は、最適経路に含まれた回数に対してユーザが拠点を訪問した回数が少なければ広告単価を値下げする等の措置をとればよい。Cユーザが訪問した拠点と、各拠点の訪問回数とが記録されるため、ユーザが過去に訪問した拠点の履歴を残すことができる。そして、ユーザ端末等を介してユーザがサーバ200にアクセスした際、広告主端末と同様にして、該当するユーザの訪問履歴をユーザ端末に送信し、ユーザに自己の訪問履歴を閲覧させることで、ユーザは、過去に訪問した拠点を認識することができ、思い出の記録にも繋がる。Dサーバ200において、ユーザ別に訪問履歴や訪問希望度が記録されているため、広告主は、過去に訪問したユーザや訪問希望度の高いユーザに対して、通信網NTを経由してサービス情報やプロモーション情報等を含むメールを送信することができ、ダイレクトマーケティングが可能となる。この場合、ユーザに対して、そのようなメールを送る旨を、予めオプトインしておくことが好ましい。E上記Dにおいてメールを送る際に、ユーザ情報を広告主に開示せずに、サーバ200を経由してのみメールを送ることを許可することも可能となる。これによって、ユーザの個人情報が不用意に広告主に開示されることが防止される。F上記Eに関して、サーバ200がメールを送信する際に、広告主に課金を行うようにしてもよい。なお、図7、図8の方式を組み合わせた方式を採用してもよい。例えば図7の方式において、広告主がQRコードの読み取りを怠ることもある。この場合、上記Bに関して、課金が行えなくなってしまう。よって、図7、図8の方式を組み合わせる双方の数を比較可能とすることで、バーコードの読み取り回数と、特典提示情報の表示回数との差を認識することが可能となる。その結果、両者が大きく乖離している場合に、広告主に対して警告するなどの対処を行うことが可能となる。図8の方式のみを採用した場合、特典提示を行わないユーザが存在するために、実際に拠点に行ったことが分からないユーザが発生したり、興味本位で特典提示画面を表示するユーザが発生したりして、実際に拠点に訪問していないにも関わらず、訪問したユーザとしとして認識されるデメリットが発生することが懸念される。しかしながら、図7と図8との方式を組み合わせることで、かかる事態の発生を防止することができる。上記実施の形態では、拠点評価情報取得部202は、広告費情報、関心度、及び訪問希望度を経路探索部203に供給したが、これらのうち少なくとも1つを経路探索部203に供給し、経路探索部203に最適経路を探索させてもよい。"