総当たりリーグ戦スケジューリングにおける重み付き残存影響度最小化問題に対する発見的解法

• Item type: Trans(1)
• 公開日: 2025-08-28
• タイトル / 言語: ja
• タイトル: 総当たりリーグ戦スケジューリングにおける重み付き残存影響度最小化問題に対する発見的解法
• タイトル / 言語: en
• タイトル: A Metaheuristic Algorithm for the Weighted Carry-Over Effect Value Minimization Problem in Round-Robin Tournaments
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] スポーツスケジューリング・メタヒューリスティクス・残存影響度
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 名古屋大学
• 著者所属: 静岡大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Shizuoka University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 曹,贇健; 呉,偉; 柳浦,睦憲
• 著者名(英): Yunjian Cao; Wei Wu; Mutsunori Yagiura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 総当たりリーグ戦は，サッカーや野球などのスポーツリーグで広く使用されており，総当たりリーグ戦の対戦表作成問題は，スポーツスケジューリングにおける代表的な問題の1つである．対戦表を評価する際には，移動距離や休憩など，様々な要素が考慮されている．これらの要素の中で，重み付き残存影響度は，対戦表の公平性を測る指標として用いられる．本論文では，重み付き残存影響度最小化問題に対し，整数計画法と反復局所探索法を組み合わせた発見的解法を提案する．提案手法は，ベースマッチングから総当たり戦の対戦表を生成する，回転法と呼ばれる手法に基づいており，まず，ベースマッチングを用いて解を表現する局所探索から始める．局所最適解が得られた後，ベースマッチングのどの頂点にどのチームを割り当てるかを二次割当問題を解くことによって最適化する．計算実験により，提案したアルゴリズムが3つの問題例の既知の最良解を更新することを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Round-robin tournaments are widely used in sports leagues such as football and baseball leagues. The round-robin tournament scheduling problem is one of the most well-known problems in sports scheduling. In the round-robin tournament scheduling problem, various factors, such as traveling distance and breaks, are often considered as criteria for evaluation. Among these criteria, the weighted carry-over effect value is used to evaluate the fairness of a schedule. In this paper, we propose a heuristic approach combining integer programming and an iterated local search algorithm for the weighted carry-over effect value minimization problem. The proposed approach is based on the well-known circle method, in which a round-robin tournament schedule can be generated from a so-called base matching. Our approach starts with a local search using a base matching to represent a solution. Whenever a locally optimal solution is obtained, a quadratic assignment problem is solved to obtain an optimal assignment between matched vertices and teams. We confirmed that our proposed algorithm successfully updated the best-known records for three instances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 18, 号 3, p. 17-31, 発行日 2025-08-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会