観光ルート推薦のための効率的な制約条件

• Item type: Trans(1)
• 公開日: 2016-06-29
• タイトル: 観光ルート推薦のための効率的な制約条件
• タイトル / 言語: en
• タイトル: Efficient Constraints for Tour Recommendation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] 観光ルート推薦，Twitter
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 岡山大学大学院自然科学研究科
• 著者所属: 株式会社両備システムソリューションズ
• 著者所属: 岡山大学大学院自然科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Natural Science and Technology, Okayama University
• 著者所属(英): en
• 著者所属(英): Ryobi System Solutions
• 著者所属(英): en
• 著者所属(英): Graduate School of Natural Science and Technology, Okayama University
• 著者名: 新妻, 弘崇; 新井, 晃平; 太田, 学
• 著者名(英): Hirotaka, Niitsuma; Kohei, Arai; Manabu, Ohta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 観光ルート推薦の問題は，なんらかの目的関数を最大化する最適化問題として定式化することができる．たとえば旅行者の興味や満足度をスコアとして表した関数の値を最大化する観光ルートを求める問題として定式化することができる．この最適なルートを求める問題はTravelling Salesman Problem（TSP）と類似した整数計画問題として記述することができる．しかしTSPと同様の定式化をすると不適切な解が頻繁に計算される問題が生じる．たとえば一筆書きにならない途切れたルートが頻繁に計算される問題が生じる．この問題を解決する制約条件を本研究では提案する．提案する制約条件には計算時間が大幅に増大する問題がある．そこで計算時間を短縮する制約条件をさらに追加する手法を提案する．提案手法の有効性を示すために2種類の目的関数を使った実験を行った．1つ目は訪問する観光スポットの人気度の総和，2つ目は旅行者をマルコフ遷移モデルで表した場合の対数尤度を目的関数として設定し実験を行った．どちらの目的関数を使用した実験でも，提案手法によって計算される観光ルートは，Greedyな解法で計算したルートと比べておおよそ2倍の目的関数の値を与えることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Tour recommendation can be formulated as finding an optimized tour that maximizes a given objective function. For example, tour recommendation can be formulated as maximizing the score that represents the degree of a user's interest as an objective function. The optimization problem can be solved as the integer programming problem using the similar formulation as used in Travelling Salesman Problem (TSP). However, the integer programming problem gives invalid solutions frequently. For example, the optimized tour frequently includes interrupted routes. This research proposes additional constraints for the integer programming problem that can resolve this problem. However, the integer programming problem including the proposed additional constraint requires huge computational time to solve. This research also proposes other additional constraints that can resolve this computational time problem. The proposed formulations are evaluated using two objective functions. The first objective function is the score which represents the popularity of each spot. The second objective function is the likelihood of a Markov chain model of tourists. We show the formulation using these additional constraints can compute better solutions that have almost a twice better score than a greedy method using these two objective functions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 9, 号 2, p. 34-45, 発行日 2016-06-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会