天気変化を考慮した観光スケジュール群の探索アルゴリズム  [in Japanese] Algorithm for Composing Satisfactory Tour Schedules for Fickle Weather  [in Japanese]

Search this Article

Author(s)

    • 武 兵 WU BING
    • 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology
    • 安本 慶一 YASUMOTO KEIICHI
    • 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology
    • 伊藤 実 ITO MINORU
    • 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology

Abstract

本論文では,天気が確率的にしか予測できない場合を想定した,任意の天気変化パターンに対応したスケジュール群を算出する問題を取り扱う.スケジュール群は,出発地点を根として目的地ごとに分岐する木 (スケジュール木と呼ぶ) で表現される.本問題の目的は,スケジュール木によって示された確率的なスケジュールの,ユーザ満足度の期待値の総和を最大化することである.本論文では,この問題を解くための欲張り法および局所探索法に基づいた近似アルゴリズムを提案する.このアルゴリズムは,まず欲張り法により初期のスケジュール木を作成し,部分木を単位とした目的地の置換を繰り返し行うことにより,期待ユーザ満足度が高いスケジュール木を生成する.提案手法により得られたスケジュール群を評価するため,シミュレーションにより従来手法との比較実験を行った.その結果,もっとも確率の高い天候ともっとも確率の低い天候を考慮して立てられたスケジュールに対し,4% から 58% 上回る期待値を持つスケジュールを得ることができた.In this paper, we consider the problem to compose schedules for probabilistically changing weather when the probability of future weather is given. In our algorithm, we represent the schedules as a scheduling tree consisting of ordered sequences of visiting spots. The objective of our problem is to find the schedule tree maximizing the expected value of total user satisfaction degree. To solve this problem, we propose an approximation algorithm based on the greedy search and the neighborhood search techniques. To evaluate the proposed method, we compare our method with an exiting method. As a result, the proposed method composed the schedule whose expected satisfaction was improved by 4% to 58%, for weather change patterns with highest and lowest probability.

Journal

  • 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告

    情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 75, C1-C6, 2009-09-10

    情報処理学会

References:  7

Codes

  • NII Article ID (NAID)
    110007993819
  • NII NACSIS-CAT ID (NCID)
    AN10505667
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09196072
  • NDL Article ID
    024775548
  • NDL Call No.
    YH247-911
  • Data Source
    CJP  NDL  NII-ELS 
Page Top