DEIM Forum 2016 H1-3

マイクロブログを利用した観光ルート推薦における移動効率の改善
智也†

中川

新妻

弘崇††

太田

学 †††

† 岡山大学工学部情報系学科 〒 700-8530 岡山県岡山市北区津島中 3-1-1†† ,††† 岡山大学大学院自然科学研究科 〒 700-8530 岡山県岡山市北区津島中 3-1-1
E-mail: †p6mi0tah@s.okayama-u.ac.jp, ††niitsuma@suri.cs.okayama-u.ac.jp, †††ohta@de.cs.okayama-u.ac.jp
あらまし 今日，Twitter などのマイクロブログの普及に伴い，マイクロブログユーザが自らの体験について気軽に発信できるようになった．その中には観光体験について発信された情報もあり，新井らはツイートされた時刻等に注目して観光ルートを推薦する手法を提案した．しかしその手法は観光スポット間の距離をあまり考慮しないため，非効率なルートを推薦することがある．そこで本稿では，その推薦された観光ルートの移動効率を改善する手法を提案する．
キーワード

マイクロブログ，Twitter，観光情報，ルート推薦
た．さらに，このツイートを収集したユーザのタイムラインか

1. は じ め にら観光スポット，観光ルートおよび観光の関連情報を抽出する

近年，マイクロブログと呼ばれる短い文章で，ユーザの身手法を提案した．しかし中嶋らの手法 [2] では，Twitter ユー

近で起こった出来事を発信するサービスの利用者が増えていザのタイムラインからのみ観光スポットを収集しているため，

る．Twitter（注 1） はマイクロブログの一種で，ツイートと呼ば得られる観光スポットが少ないという問題があった．

れる 140 文字以内の文章を発信できるサービスである．2016

この問題を解決するため，新井ら [3] は観光したい目的地の年 1 月現在，世界で 3 億 2000 万人が利用しており [1]，ツイー

周辺の施設一覧を Google Places API（注 4） を用いて取得する手

トの中には何気ない発言からニュース速報に至るまで幅広い情法を提案した．しかし，この方法では観光とは関係ない施設名（注 2）のように Twitter とも取得されるため，Yahoo!知恵袋の「地域，旅行，お出かけ」

連携して自分の位置情報を共有することができるサービスや，報が含まれている．また，Foursquare

カテゴリに出現する出現頻度の高い地名を観光スポットとして（注 3）

Instagramのような画像共有サービスも登場し，ユーザの位置情報や体験情報が発信されている．

選別する手法を提案した．この方法により，妥当なスポット名のみを選別することができることを新井らは示した．また，こ中嶋ら [2] は，Twitter のユーザが観光スポットを訪れた際のスポット名を手がかり語とすることで，観光に関連のあるツに，観光スポットの様子や景観の感想などを呟いているツイー

イートを収集することができる．本研究では，この手法で収集

トがあることに注目した．具体的には，ツイートされた時間やしたデータを実験に用いる．

ツイートした人のタイムラインに登場する観光スポット名，そさらに新井ら [3] は収集したツイートから各観光スポットにの観光スポットがどのような目的で訪れられているかなどをツついて 3 種類のスコアを求めて，これらのスコアの和が最大とイートから取得して観光に関連する情報を集める手法を提案しなるような観光ルートを決定する手法を提案した．このルート

た．新井ら [3] は，この収集された情報から，各観光スポット

探索問題は Travelling Salesman Problem(TSP) などと同様ののスコアを算出し，そのスコアを使って観光ルートを推薦する

複雑な組合せ最適化問題となる．しかし新井らの提案アルゴリ

手法を提案した．新井らの提案手法は，各観光スポットをそのズムは，複雑な組合せ最適化問題で生じる局所最適解を回避す

観光スポットのツイートが多い時間帯に訪れるようなルートをる問題を考慮していないため，移動効率の悪い推薦ルートが計推薦するため，おおむね良い時間帯に観光スポットを回ること算される問題があった．例えば，新井らのルート探索アルゴリができる．しかし，移動時間が非効率なルートを推薦するといズムには，局所最適解を避けてスコアがより良いルートを探す

う問題があった．そこで本研究では移動効率を改善する方法をためにバックトラックをするような仕組みがない．そのため本提案する．

稿では新井らのルート探索手法を Greedy な解法と呼ぶことと2. 関 連 研 究する．
倉島ら [4] は，写真共有サイトのジオタグ情報を人々の旅行

中嶋ら [2] は位置情報付きツイートと Foursquare や Insta-

履歴として利用した，トラベルルート推薦手法を提案した．倉gram のサービス，および旅行者のツイートに頻繁に現れる特島らの手法は，場所間の移動しやすさを考慮するマルコフモデ

徴語を用いて旅行情報を含むツイートを収集する手法を提案し

ルと，旅行者の興味を考慮するトピックモデルを，確率論的枠組みの中で結合して次に移動する場所を予測し，最良優先探索（注 1）：Twitter，http://twitter.com/に基づいて効率的に現在地からの推薦ルートを生成する．

（注 2）：Foursquare，https://ja.foursquare.com/（注 3）：Instagram，http://instagram.com/（注 4）：Google Places API，https://developers.google.com/places/藤坂ら [5] は，位置情報付きツイートを用いて観光情報の抽出を試みた．彼らは，K-means 法により分割した日本の各領を利用することで観光地の名称のみを選別することができる．
具体的には次のようにする．

域に対して，ツイート数，Twitter ユーザ数，Twitter ユーザ

Yahoo!知恵袋質問検索 API （注 5） を用いて，収集した施設のの移動量からノーマルパターンを規定し，ある時間におけるツ名称が Yahoo!知恵袋の「地域，旅行，おでかけ」のカテゴリ

イート数，Twitter ユーザ数，Twitter ユーザの移動量をそれ下の「国内」カテゴリに何回出現するかを数える．Yahoo!知恵ぞれのノーマルパターンと比較することで，地域イベントが行

袋質問検索 API はカテゴリを指定して質問を検索できる．そわれている領域を検知した．

こで，すべてのカテゴリで施設名で検索したときの質問数に対

石野ら [6] は， ANPI NLP [7] で提供される震災情報に関わする，「地域，旅行，おでかけ」のカテゴリ下の「国内」カテゴるツイートを利用して，被災時における避難経路を自動抽出すリにおいて施設名で検索したときの質問数の割合が，閾値以上る手法を提案した．石野らは機械学習を用いて，移動元，移動のものを観光スポットの名称と判定する．こうして例えば京都先，移動手段のタグを東日本大震災に関連するツイートに自動

駅を中心とした場合には，清水寺や金閣寺などが観光スポット

付与することによって，被災者の行動経路を抽出した．

の名称として選別される．

郡ら [8] は行動計画の立案支援として，ブログからユーザのさらに，こうして観光スポットと判定されたもの同士の移動

行動時の代表的な経路とその文脈を抽出し，地図上にマッピン

時間を Google Directions API（注 6） を用いて収集し，ルート探グして提示するシステムを提案した．郡らの手法では，ブログ

索に利用する．

内に出現する各地名に対して，旅行者が実際にその場所を訪れ

3. 2 観光ツイートの収集たかどうかを文脈から判定し，訪れたと判定した場合はその地

3. 1 節の手順で観光スポットの選別をすることで，各観光名をルート要素とする．その後，ルート要素に対して順序付け

スポット名を含むツイートを収集することが可能となる．そを行い，地名の系列パターンを抽出した．

こで，観光ツイートを以下のようにして収集する [3]．Twitter

Lee ら [9] は，電気自動車の充電待ち時間を目的関数として，

API（注 7） により各観光スポット名を含むツイートを収集する．

それを最小化する観光ルートを遺伝的アルゴリズムを用いて推この時に，位置情報共有サービスの URL を含んでいるか，画薦した．Lee らの手法は，旅行者の観光ルートにおいて代表的像が添付されているか，実際に訪れたとみなせる表現がされてな観光スポットを出発点として，推薦する観光ルートの突然変いるか，などの特徴も収集する．この情報を使うことで実際の異や進化を行う．

観光体験に基づくツイートかどうか判定する．またツイートの3. 観光スポットと観光ツイートの収集
ここでは Twitter から観光スポットと観光に関連するツイー
トを収集する手法について説明する．本研究では Twitter ユー
ザが観光地を訪れて，実際の観光体験に基づいてされたツイー

投稿時刻も記録する．この時刻情報は後述する各観光スポットの観光所要時間と時間帯スコアを算出するために必要となる．

3. 3 観光ツイートの集計
収集した観光ツイートを集計することでそれぞれの観光ス
ポットについて，次の情報を得ることができる．

トを観光ツイートと呼ぶ．観光ツイートの収集には注目していまず，それぞれの観光スポットの平均的な観光所要時間を，る観光スポットの情報が必要となる．まずこの観光スポットの実際の観光体験に基づくと判断されたツイートの投稿時刻，そ収集手順について述べる．

のユーザのタイムラインで次に訪れたスポットでされたと思わ

3. 1 観光スポットの収集れるツイートの投稿時刻及びそのスポット間の移動時間を使う

本研究では新井らの研究 [3] と同様に観光地の地名を手がかことで求めることができる．

り語として，その手がかり語を含むツイートを収集する．このさらに，それぞれの観光スポットの良さを評価するために次の３つのスコアを計算する [3]．

地名は以下の手順で収集する．
まず最初に注目する観光地の中心となる場所を決める．例えば京都を観光したいなら京都駅や清水寺，岡山を観光したい
なら岡山駅などの注目する観光地の中心地になるスポットを決（注 4）

める．次に，Google Places API•

時間帯スコア・・・全ツイート数に対する 3 時間ごとの各時間帯におけるツイート数の割合•

カテゴリスコア・・・ツイートを「食事」，
「景観」，
「土産」，

のプレイス検索を用いて， 「行動」の 4 つのカテゴリに分類した時の割合

選択した中心地，例えば京都駅の周辺の施設の情報を 20 件取得する．さらに，収集した施設の周辺の施設を新たに収集し，新しい施設が出現しなくなるまで施設の収集を繰り返す．

•

共起スコア・
・・ツイートした同じユーザのタイムラインに出てくる他の観光スポットの共起確率
時間帯スコアは各観光スポットをどの時刻に訪問すると良こうして収集した施設名の集合には観光地として適当ではな

いかを推薦するためのスコアである．時間帯スコアを以下でい地名も含まれている．例えば京都市立病院などがある．このは f T で表すこととする．カテゴリスコアは各観光スポットが，ような適当ではない施設名は Yahoo!知恵袋を使って除外できる．Yahoo!知恵袋の「地域，旅行，おでかけ」のカテゴリ下の「国内」カテゴリには，多くの観光地の名称が出現する．これ（注 5）：Yahoo!知 恵 袋 質 問 検 索 API，http://developer.yahoo.co.jp/

webapi/chiebukuro/chiebukuro/v1/questionsearch.html（注 6）：Google Direction API，https://developers.google.com/maps/

documentation/directions/（注 4）：Google Places API，https://developers.google.com/places/（注 7）：Twitter API，https://apps.twitter.com/

「食事」，「景観」，「土産」，「行動」のカテゴリの中のどの目的

ムについて説明する．この解法は 4. 節で説明した最適化問題

で訪れられているかの度合いを評価したスコアである．カテゴの局所最適解の問題を考慮しない Greedy な解法となっている．

リスコアを以下では f C で表すこととする．共起スコアは各観

しかし本研究で扱う問題設定を明確に説明できるため，詳細に光スポットがどのくらいの頻度で他のスポットと共に訪れられ説明する．

ているかの度合いを評価したスコアである．共起スコアを以下

5. 1 観光ルート推薦

では f O で表すこととする．本研究では，これらのスコアの和

まず観光ルートの被推薦者が，出発地，到着地，出発時刻，

Tf =f +fC+f

O

が大きくなるほど，良い観光スポットであ到着時刻を入力する．出発時刻を TS ，到着時刻を TG ，出発地
を PS ，到着地を PG とし，ルート R =< PS ，PG > とする．出るとみなす．

発地 PS からある観光スポット Si までの移動時間を MS,i ，観4. 観光ルート推薦の定式化

光スポット Si から到着地 PG までの移動時間を Mi,G ，ある3. 3 節でそれぞれの観光スポットの良さを評価するスコアとし

観光スポット Si での滞在時間を Vi で表す．

て，時間帯スコア，カテゴリスコア，共起スコアの３つを示した．
TC

観光スポットの時間帯スコアが最も高くなる時区間に，滞在O

時間の半分は被推薦者が滞在することを条件とし，出発時刻とが最大となるような観光ルートを求める最適化問題として，観到着時刻の間に訪れることができる観光スポットの一覧を被推

光ルート推薦の問題を扱う．この最適なルートの探索問題は薦者に提示する．提示した観光スポット一覧の中から被推薦者

TSP と類似した問題となり，TSP に使われる記法と同じ記法が訪れたい観光スポット SX を 1 つ選択すると，ルート R にを使って，次のように記述することができる．

SX を加え，R =< PS ，SX ，PG > とする．本稿ではこの観光本研究では，これら３つのスコアの単純な和 f = f + f + f

スポット SX を選択スポットと呼ぶ．これより先の観光ルート

maximize

x11 ,x12 ,...,xN N

subject tof (x11 , x12 , ..., xN N )N∑

推薦アルゴリズムについて，図 1 を用いて説明する．

(1)

xij <
= 1,

i = 1, ..., N

xij <
= 1,

j = 1, ..., N•

まず，図 1 に示すように，出発時刻 TS と到着時刻 TG の間(2)で，ユーザが選択した観光スポット SX の時間帯スコアが最も

j=1
N
∑

step 1

高くなる時間帯を求める．図 1 は，12 時から 15 時までの時間(3)

帯スコアが最大である場合を説明している．

i=1

g(x11 , x12 , ..., xN N ) <= gmax•(4)

step 2
推薦アルゴリズムでは，観光スポットの時間帯スコアが最も

xij ∈ {0, 1}

高くなる時区間に，滞在時間の半分はユーザが滞在すること

ここで xij は i から j への移動を表す変数である．スポット iを条件としている．図 1 に示した通り，SX における滞在時間

からスポット j への移動があるときに 1 となり，それ以外の場

VX は 60 分であるので，60 分のうちの 30 分は少なくとも 12

合は 0 となる 0, 1 の 2 値をとる変数である．不等式制約条件式

時から 15 時までの間に SX に滞在できるようにする．従って，(2) と式 (3) は同じスポットを 2 回訪問しないための制約条件でユーザは 11 時 30 分から 15 時 30 分までの時区間で 60 分 SX

ある．f は最大化したい目的関数であり，すなわち旅行者のスに滞在することになる．しかし，ユーザが設定した出発時刻 TS

O

は 11 時であり，PS から SX までにかかる移動時間 MS,X はとする．式 (4) はコストなどの制約条件である．例えば，観光

60 分 であるため， 11 時に PS を出発しても SX に到着できるに使える全時間の上限や，出発時刻，到着時刻，優先的に訪問のは 12 時である．そのため，観光スポット SX の推薦が可能

したいスポットなどを表す制約条件である．この様々な制約条

な時間は，図 1 の step 2 に矢印で示す 12 時から 15 時 30 分

件の詳細は 5. 節で説明する．

までの時区間である．

ポットに対する満足度である．本研究では f = f

T

+f

C

+f

この問題はコストの制約 (4) 式をとりのぞき，不等式制約
条件式 (2) と (3) を等式制約条件に変更すると TSP と等価となる．

•

step 3step 3 では，ユーザが，定めた時間内で SX に最も早く訪れる場合と最も遅く訪れる場合を考える．step 2 より，出発時

時間帯スコア以外の目的関数は変数 xij の線形な関数として

刻 TS から最も遅く SX に到着する時刻である 14 時 30 分ま

記述することができる．したがって時間帯スコア以外を目的関での間と，最も早く SX を出発する時刻である 13 時から到着数とするなら整数計画ソルバなどを使って，この最適化問題を

時刻 TG までの間で推薦すべき観光スポットを探す．TS から解くことができる．しかし時間帯スコアは複雑な関数であり，14 時 30 分までの時区間と 13 時から TG までの時区間で，時線形な関数として記述するのは困難である．そこで本研究では，

間帯スコア，カテゴリスコア，共起スコアの和が最も大きい観光

遺伝的アルゴリズムなどの非線形な問題を扱える解法を適用

スポットを導出し，それらを追加候補 SA ，SB とする．そして，する．

2 つの追加候補 SA と SB を比較してスコアがより大きい追加候

5. Greedy な解法
本節では新井ら [3] が提案した観光ルートの探索アルゴリズ

補を推薦ルートに加える．図 1 は，SA のスコアが SB より大きかった場合を説明している．SA は， TS から 14 時 30 分までの時区間で導出した観光スポットなので，推薦スポットの 1 つと

して SX の前に追加する．すなわち，R =< PS ，SA ，SX ，PG >とする．なお，SA をルートに追加したことによって生じる時間の制約については step 5 で述べる．

•

step 4step 4 では，新たに追加された観光スポット SA を導出した

時区間（TS から 14 時 30 分までの間）で，step 1 同様，SA の時間帯スコアが最も高くなる時間帯を求める．図 1 は，12 時から 15 時までの時間帯スコアが最大である場合を説明している．

•

step 5step 5 では滞在時間の半分はユーザが滞在するという条件をルート内の観光スポット全て（SX と SA ）に適用し，それぞれの推薦可能な時間帯を求める．図 1 に示すように，SA の滞在
時間 VA は 30 分なので，ユーザは 12 時から 15 時までの間に少なくとも 15 分は滞在する．従って，観光スポット SA の推薦が可能な時間は 11 時 45 分から 15 時 15 分となる．しかし，ユーザが設定した出発時刻 TS は 11 時であり，PS から SA までにかかる移動時間 MS,A は 60 分 であるため，11 時に PS を出発しても SA に到着できるのは 12 時である．さらに，step 2
で求めたように，ユーザは 12 時から 15 時 30 分までの時区間
で 60 分間 SX に滞在することになるため，SX に最も遅く到着する時刻は 14 時 30 分である．また，SA から SX までの移図 1 greedy な観光ルート推薦

動時間 MA,X が 30 分であるため，SA を推薦可能な時間帯は

12 時から 14 時までの間である．一方，SX を推薦可能な時間する．

帯は，step 2 の段階で 12 時から 15 時 30 分の間となっていた

5. 2 Greedy な解法の問題点

が，ユーザは 12 時から 14 時までの時区間で 30 分間 SA に

5. 1 節 で 示 し た よ う に ，新 井 ら の 提 案 し た Greedy な 解

滞在するため，SA を最も早く出発する時刻は 12 時 30 分であ法 は 出 発 地 ，到 着 地 ，出 発 時 刻 ，到 着 時 刻 ，被 推 薦 者 がる．そして，SA と SX 間は移動に 30 分かかるので，SX を推訪 れ た い 観 光 ス ポット SX ，と い う 5 つ の 制 約 条 件 の 元 で薦可能な時間帯は 13 時から 15 時 30 分である．以上のことか

f = 時間帯スコア + カテゴリスコア + 共起スコア を最大化

ら，観光スポット SA と SX を推薦可能な時間帯は，それぞれするルートを求める問題を解いていることがわかる．しかしア

図 1 の step 5 に矢印で示す範囲である．

ルゴリズムの途中で最適でないスポットが挿入されても，後か•ら修正することのできないアルゴリズムとなっているため，頻step 6
step 6 で推薦ルートに追加する観光スポットを決定する．ルート内の観光スポット全て（SA と SX ）について，step 5 で定めた時間内で，ユーザが最も早く訪れる場合と最も遅く訪れる場
合を考える．TS から SA に最も遅く到着する時刻 13 時 30 分
まで，SA を最も早く出発する時刻 12 時 30 分から SX に最も遅く到着する時刻 14 時 30 分まで，さらに，SX を最も早く

繁に局所最適解に陥ってしまう問題がある．

6. 移動効率の改善
ここでは，共起スコアの改良と遺伝的アルゴリズムによるルート推薦の 2 種類の移動効率改善案を提案する．

6. 1 共起スコアの改良出発する時刻 14 時から TG までの間で，それぞれ推薦すべき

新井らの Greedy な解法はルート探索の途中で局所最適なス

観光スポットを探す．TS から 13 時 30 分まで，12 時 30 分か

ポットが挿入されてしまうため，最終的に最適解から離れた解ら 14 時 30 分まで，14 時から TG までのそれぞれの時区間で，が計算される問題があった．そこで探索の途中で局所最適解に時間帯スコア，カテゴリスコア，共起スコアの和が最も大きい

向かわないように目的関数の修正を行う方法を提案する．具体

観光スポットを導出し，それらを追加候補 SC ，SD ，SE とす

的には，移動の順番に直接影響を与えられる共起スコアの定義

る．そして，SC ，SD ，SE を比較してスコアが最も大きい追を変更する．

加候補を推薦ルートに加える．図 1 では，SE のスコアが SC ，

新井らは，共起スコアを求めるスポットについてツイートしSD より大きかった場合を示している．SE は，14 時から TGているユーザのタイムラインに出てくる全てのスポットを，共までの間で導出した観光スポットなので，SX の次に追加し，起スポットとして定義した．それを，タイムラインに連続してR =< PS ，SA ，SX ，SE ，PG > となる．

出てくるスポットはある程度近いと仮定し，共起スコアを求め推薦ルートに追加できる観光スポットがなくなるまで step 4，

step 5，step 6 を再帰的に繰り返すことで，推薦ルートを決定

るスポットの前後 2 つ以内に出てくるスポットのみを共起ス
ポットと定義し直す．例えばユーザのタイムラインで，SA → SB → SC →共起スコアを求めるスポット→ SD → SE → SFと出現している場合，新井らの手法は SA ,SB ,SC ,SD ,SE ,SFのすべてを共起スポットとしていた．しかし提案手法では

SB ,SC ,SD ,SE のみを共起スポットとする．これにより，観光ルートに観光スポットを追加するときに参照する 3 つのスコアの和における時間帯スコアの重みを変えることなく，スポット間の距離を考慮することができる．このように，連続して訪れる確率の大きいスポットを選択すると共起スコアが大きくなる
よう調節することで，倉島ら [2] の手法における連続して訪れるスポットに対する尤度が大きくなる仕組みと類似した仕組みを導入することができる．

6. 2 遺伝的アルゴリズムによるルート推薦
6. 2. 1 ルート推薦アルゴリズム
観 光 ル ー ト 推 薦 の 問 題 は ，Travelling Salesman Prob-lem(TSP) とほぼ同様の目的関数を最大化するルート探索問
題として記述できる．ただし，TSP は全てのスポットを回る必要があるが，観光ルート推薦の問題では全てのスポットを回る必要がなく，また観光ルートの被推薦者が指定した時間内に推薦ルートを回ることができなければならない．この制約を従来の TSP の解法に導入して TSP と同様の解法で問題を解くことも考えられる．例えば，整数計画問題としてこの最適化問題が解けるなら，従来の TSP についての解法 [10] に，この TSPと異なる制約条件を導入するのは容易である．しかし，時間帯
スコアは線形な整数計画問題として記述するには困難で複雑な処理を含むため，整数計画問題としてこの最適化問題を解くのは困難である．そこで本節では，複雑な目的関数の最適化にも適用できる遺伝的アルゴリズムを用いて，移動効率を改善する方法を提案する．遺伝的アルゴリズムは，生物の進化をモデルとして，淘汰，交叉，突然変異という遺伝的操作を用いて問題を解く手法である．遺伝的アルゴリズムによって TSP を解く
手法としては [11] の研究などがある．本稿ではこの遺伝的アルゴリズムの考え方に基づいて以下の手順で移動効率のより良いルートを探索する．
（ 1 ） Greedy な解法でルートを生成して初期ルート r とし，推薦ルートの候補の集合 U に r を追加する．そして，推薦されたスポットを既に探索済みのスポット集合 L に追加する．
（ 2 ） ルート r から i 個のスポットを無作為に取り除いて短縮したルートを生成する．この短縮したルートを, 更新された
ルート r とする．ここで i は被推薦者の選択スポットを除く推薦スポットの数以下の乱数で決めるものとする．
（ 3 ） 更新されたルート r において取り除かれなかった各ス
ポットについて 5. 1 節の step 5 のようにして推薦可能な時間帯を求める．

集合 L に追加する．
（ 6 ） 5. 1 節の step 4 から step 6 を，新たに追加するスポットを既に推薦済みのスポット集合 L に追加しながら繰り返し適用することで，スポットをルートに追加して推薦ルート r を完
成させ，その r を推薦ルート候補集合 U に追加する．ただし追加するスポットは，既に探索済みなスポット集合 L を除外したスポット集合から探す．
（ 7 ） ルート r から i 個のスポットを無作為に取り除いて短縮したルートを生成する．この短縮したルートを, 更新された
ルート r とする．ここで i は被推薦者の選択スポットを除く推薦スポットの数以下の乱数で決めるものとする．
（ 8 ） 更新されたルート r において取り除かれなかった各ス
ポットについて 5. 1 節の step 5 のようにして推薦可能な時間帯を求める．
（ 9 ） ルート r の各時区間についてスコアの和が最も大きいスポットを，ルート r にない全てのスポット集合から探す．
（ 10 ） 各時区間において探したスポットの中でスコアの和が最も大きいスポットを追加スポットとし，探索済みのスポット
集合 L に追加する．
（ 11 ） 5. 1 節の step 4 から step 6 を，新たに追加するスポットを既に推薦済みのスポット集合 L に追加しながら繰り返し適用することで，スポットをルートに追加して推薦ルート r を完
成させ，その r を推薦ルート候補集合 U に追加する．ただし追加するスポットは，ルート r にない観光スポット全てのスポット集合から探す．
（ 12 ） 互いに異なる推薦ルート候補の集合 U の大きさが 100になるまで (2)〜(11) を繰り返す（ 13 ） 大きさ 100 の推薦ルート候補集合 U の中から 6. 2. 2 節
で説明する評価値 h1 または h2 が最も高いルートを推薦する．
ルート r にない全てのスポット集合のみから新たに追加するスポットを探索すると，削除されたスポットと同じスポットが推薦されやすく，互いに異なるルートを 100 種類作成するのが困難である．そこで既に探索済みのスポット集合 L を用意し，スポット集合 L を除いたスポット集合から新たに追加するス
ポットを探索する．これを交互に繰り返すことにより，互いに異なる 100 種類の推薦ルート候補を作成する．
なお，スポット選択に使用する共起スコアは 6. 1 節で説明したものではなく，新井らの共起スコアを用いる．

6. 2. 2 ルート選択に用いる評価値
本節では 6. 2. 1 節で説明したルート推薦アルゴリズムの (13)で用いる評価値について説明する．本研究では 2 つの評価値を用いてルート推薦を行う．

1 つ目は，追加スポットを探索するときに使う 3 つのスコアの合計を使うスコア h1 である．h1 は以下のように算出する．

（ 4 ） ルート r の各時区間についてスコアの和が最も大きいスポットを，それぞれ既に探索済みのスポット集合 L を除外したスポット集合から探す．
（ 5 ） 各時区間において探したスポットの中でスコアの和が最も大きいスポットを追加スポットとし，探索済みのスポット

h1 =

n
∑
i=1

ここで

fi

(5)

fi = fiT + fiC + fiO(6)

ただし n は推薦された観光スポットの数，fi は推薦された
ルートにおいて i 番目に訪れるスポットのスポット満足度，fiTは推薦されたルートにおいて i 番目に訪れるスポットの時間帯
スコア，fiC は推薦されたルートにおいて i 番目に訪れるスポットのカテゴリスコア，fiO は推薦されたルートにおいて i 番目に訪れるスポットの共起スコアを表す．
時間帯スコアは，推薦された観光スポットを適した時間に訪れることができているか，カテゴリスコアは，選択スポットと同じような観光目的で推薦された観光スポットを訪れられてい図 2 greedy な解法による推薦ルート

るか，共起スコアは，推薦された観光スポットが他のスポットと共にどれくらいの頻度で一緒に訪れられているかを表す．それらの和をとる式 (6) は推薦されたスポットの満足度と言える．

表 1 greedy な解法による推薦ルートのスポット満足度及び移動時間
マーカー

スポット名

滞在時間

満足度

移動時間

—

—

0h16m

1h00m 1.0903

0h14m

よって，スコア h1 は推薦されたスポットの満足度の合計が最A

御陵駅 (START)

も高いルートを推薦するものである．

B

二条城

C

哲学の道

0h30m 1.5088

0h34m

D

嵐山

1h39m 2.0723

0h42m

E

蹴上インクライン

0h47m 1.4874

0h36m

F

宝厳院

1h00m 1.9545

0h27m

G

ホテル秀峰閣 (GOAL)

2 つ目は，式 (5) の満足度の合計に加えて，総移動時間も見るスコア h2 である．h2 は以下のように算出する．

h2 =

h1
∑
MS,1 + n−1
i=1 Mi,i+1 + Mn,G

(7)

h1 は式 (5) で示したルートの合計満足度，S は被推薦者が入

合計

—

—

4h56m 8.1133

2h49m

力した出発地，G は被推薦者が入力した到着地，Mi,j は i 番目に訪れる推薦スポットから j 番目に訪れる推薦スポットへの移動にかかる時間 (h) を表す．
式 (7) の分子は推薦されたルートに登場する全ての観光ス
ポットの満足度の合計，分母は推薦されたルートの総移動時間を表している．スコア h2 は それらの商をとるため，観光ルー
トのスポット満足度と移動効率の両方を考慮するものである．

7. 評 価 実 験
ここでは 5. 節で説明した greedy な解法で求めた推薦ルートと，6. 節で説明した 2 種類の移動効率改善方法で求めた推薦ルートを，移動時間がどれ程短縮できたかの評価をするために，

図 3 改良した共起スコアによる推薦ルート

評価関数として 6. 2. 2 節で述べた h2 を用いて比較する．

7. 1 実 験 概 要
本実験では新井ら [3] が収集した京都の観光スポット 151 件を推薦スポット候補とし，2014 年 12 月 21 日から 2015 年 1 月

3 日にされたツイートを用いた．出発地を御陵駅，出発時刻を
11:00，到着地をホテル秀峰閣，到着時刻を 19:00，選択スポッ
トを二条城として観光ルート推薦を行った．

7. 2 greedy な解法による推薦ルートの評価
greedy な解法によって推薦されるルートを地図上に表示したものを図 2 に，図 2 のマーカーがどのスポットを表している
か，各スポットの滞在時間，各スポットのスポット満足度及び次のスポットへの移動時間を表 1 に示す．なお，このルート推
薦アルゴリズムは各観光スポットを訪れる時刻を指定するため，空き時間ができることがある．そのような余った時間が 15 分あった．
式 (5) のスポットの満足度の合計は h1 = 8.1133，総移動時間
は 2 時間 49 分，式 (7) のルートの評価関数の値は h2 = 2.8804となった．

7. 3 改良した共起スコアによる推薦ルートの評価
6. 1 節で提案した共起スコアによる推薦ルートを地図上に表示したものを図 3 に，図 3 のマーカーがどのスポットを表しているか，各スポットの滞在時間，各スポットのスポット満足度
及び次のスポットへの移動時間を表 2 に示す．なお，余った時間が 43 分あった．
式 (5) のスポットの満足度の合計は h1 = 9.6475，総移動時間
は 1 時間 40 分，式 (7) のルートの評価関数の値は h2 = 5.7885となった．

7. 4 遺伝的アルゴリズムによる推薦ルートの評価
7. 4. 1 ルート選択に h1 を使用した推薦ルートの評価
6. 2 節で提案した遺伝的アルゴリズムにより，h1 が最大となった推薦ルートを地図上に表示したものを図 4 に，図 4 のマーカーがどのスポットを表しているか，各スポットの滞在時

表 2 改良した共起スコアによる推薦ルートのスポット満足度及び移
動時間
マーカー

スポット名

滞在時間

満足度

移動時間

—

—

0h16m

二条城 (選択)

1h00m 1.0903

0h19m

C

渡月橋

1h10m 1.8739

0h10m

D

嵐山

1h39m 3.4781

0h18m

E

常寂光寺

0h48m 1.2508

0h10m

F

宝厳院

1h00m 1.9545

0h27m

G

ホテル秀峰閣 (GOAL)

A

御陵駅 (START)

B

—

合計

—

5h37m 9.6475

1h40m
図 5 遺伝的アルゴリズムにより h2 が最大となった推薦ルート
表 4 遺伝的アルゴリズムにより h2 が最大となった推薦ルートのス
ポット満足度及び移動時間
マーカー スポット名

図 4 遺伝的アルゴリズムにより h1 が最大となった推薦ルート

滞在時間

満足度

移動時間

—

—

0h07m

平安神宮

1h35m

2.33870h01m

C

京都市美術館

0h35m

1.62020h11m

D

二条城 (選択)

1h00m

1.09030h15m

E

蹴上インクライン

0h47m

1.5023

0h13m

F

東山慈照寺

1h40m

2.4088

0h04m

G

哲学の道

0h30m

1.8556

0h16m

H

二年坂

0h33m

0.7291

0h07m

I

ホテル秀峰閣 (GOAL)

—

—

A

御陵駅 (START)

B

表 3 遺伝的アルゴリズムにより h1 が最大となった推薦ルートのス

合計

6h40m 11.5450

1h14m

ポット満足度及び移動時間
マーカー スポット名

滞在時間

満足度

移動時間

—

—

0h10m

7. 5 考察A

御陵駅 (START)

B

四条大橋

0h40m

1.29890h09m

改良した共起スコアにより，greedy な解法に比べて，スポッC

蹴上インクライン

0h47m

1.50530h15m

ト満足度の合計が約 2 割増え，総移動時間は約 6 割に短縮され

D

二条城

1h00m

1.09030h12m

た．その結果，式 (7) の評価関数の値 h2 は約 2 倍になった．

E

八坂神社

1h10m

2.81640h14m

一方，遺伝的アルゴリズムにより，h1 が最大となった推薦

F

祇園

1h17m

3.72750h21m

ルートは，greedy な解法に比べて，スポット満足度の合計が約

G

哲学の道

0h30m

1.6481

0h17m

6 割増え，総移動時間は約 6 割に短縮された．その結果，式 (7)

H

三年坂

0h48m

0.98480h07m

I

ホテル秀峰閣 (GOAL)——の評価関数の値 h2 は約 2.6 倍になった．h2 が最大となった推

合計

6h12m 13.0712

1h45m

薦ルートは greedy な解法に比べて，スポット満足度の合計が約 4 割増え，総移動時間は約 4 割に短縮された．その結果，式(7) の評価関数の値 h2 は約 3.5 倍になった．遺伝的アルゴリズ
間，各スポットのスポット満足度及び移動時間を表 3 に示す．
なお，余った時間が 3 分あった．
式 (5) のスポットの満足度の合計は h1 = 13.0712，総移動時
間は 1 時間 45 分，式 (7) のルートの評価関数の値は h2 = 7.4693となった．

ムにおいて，h1 が最大となるルートを選択するアルゴリズムが推薦するルートの評価値 h2 は，h2 が最大となるルートを選択するアルゴリズムが推薦するルートの評価値 h2 よりは小さい．しかし，スポット満足度の合計 h1 は，h2 を基準に選択する場合よりもより大きいので，移動効率が多少悪くてもより良7. 4. 2 ルート選択に h2 を使用した推薦ルートの評価

いスポットを回りたいという旅行者のために使い分けることが6. 2 節で提案した遺伝的アルゴリズムで，h2 が最大となった

できる．

推薦ルートを地図上に表示したものを図 5 に，図 5 のマーカー
がどのスポットを表しているか，各スポットの滞在時間，各ス
ポットのスポット満足度及び移動時間を表 4 に示す．なお，余った時間が 6 分あった．
式 (5) のスポットの満足度の合計は h1 = 11.5450，総移動時
間は 1 時間 14 分，式 (7) のルートの評価関数の値は h2 = 9.3608となった．

8. ま と め
本研究では，新井らの提案した Twitter を利用した観光ルー
ト推薦における推薦ルートの移動効率の改善のため，共起スコ
アの改良と遺伝的アルゴリズムの 2 種類の手法を提案した．
共起スコアの改良では，共起スコアを求めるスポットについてツイートしている Twitter ユーザのタイムラインに出てくるスポット全てを共起スポットとしていたのを，共起スコアを求
めるスポットの前後 2 つ以内のスポットのみに変更した．遺伝的アルゴリズムによる推薦では，新井らの手法によって推薦されたルートの部分的な更新を繰り返し，100 種類のルートを作成して最も評価値の高いものを推薦ルートとした．また，推薦スポットの観光スポットとしての満足度と，推薦ルートの移動効率の両方を考慮するため，推薦スポットの時間帯スコア，カ
テゴリスコア，共起スコアの和を総移動時間で除して評価関数を定義した．
新井らの提案手法に相当する greedy な解法による推薦ルー
トの評価関数の値は h2 = 2.8804，共起スコアを改良した推薦
ルートの評価関数の値は h2 = 5.7885，遺伝的アルゴリズムによって h1 が最大となるルートを選択した場合の評価関数の値
は h2 = 7.4693，h2 が最大となるルートを選択した場合の評価関数の値は h2 = 9.3608 となった．特に遺伝的アルゴリズ
ムによって h2 が最大となるルートを選択し場合は，被推薦者が選択したスポットの近くにある魅力的なスポットを効率よく回るルートを推薦するようになったため，評価関数の値 h2 がgreedy な解法に比べて 3 倍以上となった．
本稿で改良したルート推薦手法は，ルート推薦に使用するツ
イートをツイートした者の属性を考慮していない．そこで，今後の課題として，ツイートからツイートした者の年齢，性別等の有用と考えられる属性を取得することが挙げられる．それにより，例えば若い女性の観光客には若い女性がよく訪れている
観光スポットを優先して推薦するというような個人化が可能になると考えている．

文

献[1] Twitter,Inc. に つ い て ， http//about.twitter.com/ja/
company[2] 中嶋勇人，新妻弘祟，太田学， 位置情報付きツイートを利用した観光ルート推薦 ，情報処理学会研究報告．データベース・
システム研究会報告，Vol．2013-DBS-158，No．28，pp．1-6，
2013．
[3] 新井晃平，新妻弘崇，太田学， Twitter を利用した観光ルート
推薦の一手法 ，第 7 回データ工学と情報マネジメントに関するフォーラム (DEIM2015)，G7-6，pp．1-8，2015．
[4] 倉島健，岩田具治，入江豪，藤村考， 写真共有サイトにおけるジオタグ情報を利用したトラベルルート推薦 ，電子情報通信学
会技術研究報告．LOIS, ライフインテリジェンスとオフィス情報システム，Vol．109，No．450，pp．55-60，2010．
[5] 藤坂達也，李龍，角谷和俊， 地域イベント発見のためのジオタ
グ付マイクロブログを用いたノーマルパターン検出手法 ，平成
22 年度情報処理学会関西支部大会，Vol．2010，2010．
[6] 石野亜耶，小田原周平，難波英嗣，竹澤寿幸， Twitter からの被災時の行動経路の自動抽出および可視化 ，言語処理学会 第18 回年次大会，pp．907-910，2012．
[7] Graham Neubig，Yuichiroh Matsubayashi，Masato Hagiwara，Koji Murakami， Safety Information Mining - What
can NLP do in a disaster - ，Proceedings of the 5th International Joint Conference on Natural Language Processing(IJCNLP)，pp. 965-973，2011.
[8] 郡宏志，服部峻，手塚太郎，田島敬史，田中克己， ブログからのビジターの代表的な行動経路とそのコンテキストの抽出 ，電子
情報通信学会技術研究報告，Vol．106，No．149，pp．29-34，
2006．

[9] Lee，j.，Kim，S.-W．and Park，G.-L， A tour recommendation service for electric vehicles based on a hybrid orienteering model ，Proceedings of the 28th Annual ACM
Symposium on Applied Computing，SAC ’13，New York，NY，USA，ACM，pp．1652-1654，2013．
[10] 藤江哲也， 整数計画法による定式化入門 ，オペレーションズ・
リサーチ : 経営の科学 57(4)，pp190-pp197, 2012．
[11] 永田祐一， 多点探索の最前線 -巡回セールスマン問題に対する
遺伝的アルゴリズムの適用- ，日本オペレーションズ・リサー
チ学会 2014 年秋季シンポジウム ，pp．1-24，2014．