コンサートツアースケジュールの最適化モデル
2017SS089 山田 奈都実 指導教員: 佐々木 美裕1
はじめに
コンサートツアーでは,アーティストまたはアーティ ストのグループが,さまざまな都市,国を巡ってコンサー トを行う. 全国のファンがアーティストの生公演を見 に行けることがコンサートツアーの醍醐味である. アー ティストにとっても,コンサートツアーは,ファンの目の 前でパフォーマンスを披露できる唯一の機会である. し かし,全国の会場を移動しながらコンサートを行うため, 多額の移動費用や移動時間がかかる. したがって, 効率 よく会場を ることが重要である. 本研究では, アーティストの移動効率を考慮しながら, なるべく多くの人がコンサートに行けるようなコンサー トツアーの日程を考える.2
問題の説明
なるべく多くの人がコンサートに行けるようなスケ ジュールを考えるために, コンサートに行ける人が多い と予想される日にコンサートを開催することが, 開催側 にとってもファンにとっても望ましい. 一般に,休日や 学生の長期休み期間であれば, 通常よりもコンサートに 行ける人が多いと考えられる. 反対に, 学生の長期休み 期間以外の平日は,コンサートに行ける人が少なくなる と考えられる. そのため, 観客動員数はコンサートの開 催日によって変動すると仮定し,所与とする. 目的は,観 客動員数の総和を最大化することとする. 拠点を出発し て, 適宜拠点に戻りながら会場を り最終日には拠点に 戻ることを1つのツアーのルーティンとする. 従って, コンサート対象期間の初日と最終日は必ず拠点にいるこ とを前提とし, 拠点を出発してから, ツアー途中で適宜 拠点に戻ることを想定したコンサートツアースケジュー ルを編成する. 移動効率を考慮するために, 会場間の移 動に必要な日数を決める. 例として, 会場間の日数が1 日であった場合, いずれかの会場でコンサートを開催し た翌日以降に次の会場で開催できる. 移動日数が2日の 場合, 2日後以降に次の会場で開催することができる. 会 場と拠点の距離についても同様に考える. また, 1つの 会場で1度しかコンサートを開催できないこととする. スケジュール対象期間の各日の状態は, コンサート開催 日か移動日か拠点に戻っているかのいずれかであるとす る. 以上の点を考慮し, 移動効率を考慮した観客動員数 最大化問題として, 最適なコンサートツアースケジュー ルを編成する.3
定式化
観客動員数最大化問題を定式化するために以下の記号 を定義する. n: ノード数. P+: ノードの集合. ノード1は拠点, P+={1, . . . , n} P : コンサート開催可能会場の集合, P = P+\{1} D: ツアー日数. T+: ツアー日数の集合, T+={1, . . . , D} T : コンサート開催可能日の集合, T = T+\{1, D} S: 拠点を出発した翌日から再度拠点に戻るまでの日数. aip: i日に会場pで開催する時の観客動員数 (i∈ T, p ∈ P ). rkl: ノードkからノードlへの移動に必要な最低日数 (k, l∈ P+). M : 大きな値. 次に以下の変数を定義する. xip= 1 :i∈ T+日にノードp∈ P+へ行くとき. 0 :上記以外. yi= 1 :i∈ T+日の状態が移動であるとき. 0 :上記以外. uikjl: 離接制約を導入するための0-1変数. 上記の記号を用いて定式化すると以下の通りになる. max. ∑ i∈T ∑ p∈P aipxip (1) s.t. ∑ i∈T xip≤ 1, p∈ P (2) ∑ p∈P+ xip+ yi= 1, i∈ T+ (3) i+S+1∑ j=i+1 xj1≥ xi1, i = 1, ..., D− S (4) xik+ xjl− 1 ≤ M(1 − uikjl), i = 1, ..., D− 1; j = i + 1, ..., D; k, l ∈ P+ (5) 1xik+ xjl− j + i + rkl− 2 ≤ Muikjl, i = 1, ..., D− 1; j = i + 1, ..., D; k, l ∈ P+ (6) x11= 1 (7) xD1= 1 (8) xip∈ {0, 1}, i∈ T+, p∈ P+ (9) yi∈ {0, 1}, i∈ T+ (10) uikjl∈ {0, 1}, i = 1, ..., D− 1; j = i + 1, ..., D; k, l ∈ P+ (11) (1)は,観客動員数の総和である. これの最大化を目的 とする. (2)は, 1つの会場で1回しかコンサートを開催 しないことを表す制約である. (3)は, アーティストの i∈ T+日の状態は, 拠点に滞在, いずれかのノード上で コンサートを開催,移動中のいずれかであることを表す 制約である. (4)は, S日の間に1回以上拠点に戻ること を表す制約である. (5)(6)は, i日にノードk∈ P+ で コンサートを開催したあと, j日にノードl ∈ P+ でコ ンサートを開催するには, 少なくともrkl 日以上空ける 必要があることを表す. (7)(8)は, ツアーの初日と最終 日は必ず拠点にいることを表す制約である. (9)(10)(11) は変数のバイナリ制約である.
4
データの作成
計算実験を行うにあたり, 次のようにデータを作成し た. 拠点を東京とし, コンサート開催会場を日本の5大 ドームとする. 各会場の名称と番号, 収容人数[1]をまと めたものを表1に示す. ツアーの開催時期を8月, 観客 の年齢層を10代から30代と想定した. 10代から30代 は,学生が多い層である. そのため,一般的に学生の長期 休み期間にあたる8月にコンサートを開催することで, 収容人数に対して,平日でも高い割合の観客動員数を見 込むことができる. 休日は, ほぼ満席にできることを想 定し, 各日における各会場の観客動員数を設定した. ま た, 各会場間と拠点間の直線距離に基づき, 会場間と拠 点間の移動に要する日数を設定した. 移動に要する日数 は表2に示す. 横軸と縦軸は表1に示した各会場の番号 を示している. 表中の値は, 各会場から各会場に何日後 に到着できるかを表す日数である.5
計算結果と考察
Gurobi Optimizer 9.1.0を用いて観客動員数最大化問 題を解いた. 計算に使用した PC に搭載されたプロセッサは, Intel(R) Core(TM) i5-7200U [email protected]
表1 各会場の番号と収容人数 番号 会場名 収容人数 (人) 1 東京ドーム 55,000 2 京セラドーム 55,000 3 札幌ドーム 53,796 4 ナゴヤドーム 49,427 5 福岡 paypay ドーム 38,561 表2 各会場間の移動に要する日数 拠点 1 2 3 4 5 拠点 - 1 1 2 1 3 1 1 - 1 2 1 3 2 1 1 - 3 1 2 3 2 2 3 - 3 3 4 1 1 1 3 - 2 5 3 3 2 3 2 -表3 コンサートツアー日程の最適解 1(金) 2(土) 3(日) 4(月) 5(火) 6(水) 7(木) 8(金) 9(土) 10(日) 拠点 1 4 拠点 移動日 3 移動日 移動日 2 拠点 2.70GHz, メモリは 8.00GB である. ツアー日数は10 日, 6日に1回は拠点に戻る設定とし,作成したデータを 使用した結果を表3に示す. ツアー日数や会場の数など 問題の規模に違いがあるが,いずれも0.5秒以内で最適 解を求めることができた. 横軸を日にち(曜日)とし,コ ンサートを行う場合は表1に示した会場の番号, 移動日 であれば「移動日」と示している. この例題を用いた場 合,総観客動員数は210,533.2人であった. 表3に示したように, 5つの会場のうち4つの会場で コンサートを開催するスケジュールを作ることができ た. 日数が10日と短いため,観客動員数が少なく, どの 会場からも遠い福岡paypayドームではコンサートを開 催しない結果となった. しかし,各会場の収容人数に対 して高い割合の観客動員数を見込めると予想した日にコ ンサートを開催するスケジュールが得られたため, 計算 結果として適切であると言える. 提案するモデルを用い ると各会場間の移動効率を考慮しながら, なるべく多く の人がコンサートに行けるようなコンサートツアーの日 程を編成できることが分かった.
