プロ野球のスケジュール作成を題材に、定式化からpulpを使った実装まで。
実装編はこちら↓
定式化の流れ
目的を明確にする→解きたい問題が持つ制約条件を全列挙→数式に変換→適切な手法を用いて解く
目的を決める
この問題を解くことによって得たい結果を明確にします。
今回の問題を例にすると、移動距離の最小化や利益の最大化、コストの最小化などが考えられます。
どの問題を考えるのかによって、必要な制約が変わってくる場合もあるため、一番最初に決めた方が良いでしょう。
今回の問題では、移動距離の最小化を目指して定式化していきます。
制約条件を列挙
- チーム数はセ・リーグ、パ・リーグ共に6チーム
- 総試合数は144試合
- そのうち交流戦が18試合
- 月曜日は移動日のため、試合を行わない
- 火曜日〜木曜日、金曜日〜日曜日の三連戦
- 六連戦はしない
- ホームとビジターの試合数をなるべく同じにする
- ダブルヘッダーは行わない
- どのチームともなるべく同じ回数試合をする
数式に変換
今回は簡単のために交流戦を除いた全126試合について考えていきます。
数式に起こす前に、問題をより簡単にするために列挙した制約を少し変形します。
制約4から、火曜日と金曜日の対戦カードが決まれば1週間の対戦カードが確定することがわかります。
したがって、考えるべき試合数は$\frac{144}{3}=48(交流戦6)$試合だということがわかります。
これを踏まえてまずは定式化に必要な変数を定義していきます。
定数
$I=\{1,2,3,4,5,6\}$：チームを元に持つ集合
$W=\{1,2,\dots ,21\}$：シーズン開始を1週目として、現在何週目か
$DOF = \{火曜日 ,金曜日\}$：試合を行う曜日を表す。(DOF…day of the week)
$D=(D_{ij})$：球場iと球場jの間の距離を格納した行列
変数
$h_{ij}^{wd}\in\{0,1\}$：w週目d曜日にチームiがホームでチームjと試合をする/しない
$v_{ij}^{wd}\in\{0,1\}$：w週目d曜日にチームiがビジターでチームjと試合をする/しない
次に目的関数を設定します。
目的関数
今回は移動距離の最小化を達成したいため、各チームの総移動距離の総和を目的関数に設定します。
球場iから球場jへの移動が発生する場合は、以下の二通りです。
- ホーム(球場i)で試合をする→ビジター(球場j)で試合をする
- ビジター(球場i)で試合をする→ホーム(球場j)で試合をする
それぞれの場合について、数式で表現していきましょう。
1. w’週目のd’曜日にビジターiで試合をし、w週目のd曜日にホームjで試合をする
①w’週目のd’曜日にビジターiで試合をする$\Leftrightarrow v_{j,i}^{w^{‘}d^{‘}}=1$
②w週目のd曜日にホームjで試合をする$\Leftrightarrow \exists k\in I s.t.h_{jk}^{wd}=1\Leftrightarrow\sum_{k\in I}h_{jk}^{wd}=1$
①かつ②が成立するので、$v_{j,i}^{w^{‘}d^{‘}}\sum_{k\in I}h_{jk}^{wd}=1$
2.チームtが w’週目のd’曜日に球場iで試合をし、w週目のd曜日にビジターjで試合をする
③w’週目のd’曜日に球場iで試合をする$\Leftrightarrow v_{ti}^{w^{‘}d^{‘}}=1$
④w週目のd曜日にビジターjで試合をする$\Leftrightarrow v_{tj}^{wd}=1$
③かつ④が成立するので、$v_{ti}^{w^{‘}d^{‘}}v_{tj}^{wd}=1$
以上より目的関数は、$D_{ij}(v_{j,i}^{w^{‘}d^{‘}}\sum_{k\in I}h_{jk}^{wd}+v_{ti}^{w^{‘}d^{‘}}v_{tj}^{wd})$となります。
この目的関数は二次式のため、このままでは整数計画問題として解くことができません。そこで、あるテクニックをつかってこの目的関数を一次式で記述していきます。
テクニック：非線形関数を線形式に直す
今回は目的関数の$v_{j,i}^{w^{‘}d^{‘}}\sum_{k\in I}h_{jk}^{wd}+v_{ti}^{w^{‘}d^{‘}}v_{tj}^{wd}$の部分が二次式になっています。$h_{ij}^{wd},v_{ij}^{wd}$が0-1変数であることを利用して、この式を線形なものに置き換えていきましょう。
まず、新しい0-1変数$x_{ij}^{wd},y_{ij}^{wd}$を導入します。
$home_{ij}^{wd}=v_{j,i}^{w^{‘}d^{‘}}\sum_{k\in I}h_{jk}^{wd}$
$visitor_{ijt}^{wd}=v_{ti}^{w^{‘}d^{‘}}v_{tj}^{wd}$
と等価な条件を制約式として取り入れます。
以下の制約が所望の式です。
- $1-\sum_{j\in I}h_{to,j}^{wd}-v_{to, from}^{w^{‘}d^{‘}}+home_{to}^{wd}(from)\geq 0$
- $\sum_{j\in I}h_{to,j}^{wd}-home_{to}^{wd}(from)\geq 0$
- $v_{to, from}^{w^{‘}d^{‘}}-home_{to}^{wd}(from)\geq 0$
- $1-v_{team, to}^{wd}-\sum_{j\in I}v_{j,from}^{w^{‘}d^{‘}}+visitor_{team,to}^{wd}(from)\geq 0$
- $v_{team, to}^{wd}-visitor_{team,to}^{wd}(from)\geq 0$
- $\sum_{j\in I}v_{j,from}^{w^{‘}d^{‘}}-visitor_{team,to}^{wd}(from)\geq 0$
実際に手を動かしてみれば、この制約がきちんと機能していることがわかると思います。
参考：pdf
次に制約条件を数式の形で記述していきます。
制約条件
総試合数に関する制約
$\sum_{j\in I}\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}(h_{ij}^{wd}+v_{ij}^{wd})=42\quad\forall i\in I$
1日あたりの試合数に関する制約
$\sum_{j\in I}h_{ij}^{wd}+v_{ij}^{wd}=1\quad\forall i\in I,\forall w\in W,\forall d\in\ DOF$
六連戦禁止
$\sum_{j\in I}\sum_{d\in DOF}h_{ij}^{wd}+v_{ij}^{wd}\leq 1\quad\forall i\in I,\forall w\in W$
$\sum_{j\in I}h_{ij}^{wd}+v_{ij}^{wd}+h_{ij}^{w-1,d^{‘}}+v_{ij}^{w-1,d^{‘}}\leq 1\forall i\in I,\forall w\in W,\forall d,d^{‘}\in DOF(d\neq d^{‘},w\geq 1)$
ホーム＆ビジターの試合数を揃える
$\sum_{j\in I}\sum_{w\in W}\sum_{d\in DOF}(h_{ij}^{wd}-v_{ij}^{wd}) = 0\quad\forall i\in I$
$4\leq\sum_{w\in W}\sum_{d\in DOF}h_{ij}^{wd}\leq 5\quad\forall i\in I$
$4\leq\sum_{w\in W}\sum_{d\in DOF}v_{ij}^{wd}\leq 5\quad\forall i\in I$
どのチームとも均等に試合をする
$8\leq\sum_{w\in W}\sum_{d\in DOF}(h_{ij}^{wd}+v_{ij}^{wd})\leq 9\quad\forall i,j\in I$
まとめ
以上をまとめると、今回解きたい問題は、以下のように記述されます。
minimize :
$\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}\sum_{from,to\in I}D_{from, to}home_{to}^{wd}(from)\\$
$+\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}\sum_{from,to,tema\in I}D_{from, to}visitor_{team,to}^{wd}(from)$
subject to:
$i,j\in I=\{1,2,3,4,5,6\}$
$w\in W=\{1,2,\dots ,21\}$
$d\in\{火曜日,金曜日\}$
$D=(D_{ij})\in M_6(\mathbb{R})$
$h_{ij}^{wd} \in\{0,1\}$
$v_{ij}^{wd} \in\{0,1\}$
$home_{to}^{wd}(from)\in\{0,1\}$
$visitor_{team,to}^{wd}(from)\in\{0,1\}$
$\sum_{j\in I}\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}(h_{ij}^{wd}+v_{ij}^{wd})=42\quad\forall i\in I$
$\sum_{j\in I}h_{ij}^{wd}+v_{ij}^{wd}=1\quad\forall i\in I,\forall w\in W,\forall d\in\{火曜日,金曜日\}$
$\sum_{j\in I}\sum_{d\in\{火曜日,金曜日\}}h_{ij}^{wd}+v_{ij}^{wd}\leq 1\quad\forall i\in I,\forall w\in W$
$\sum_{j\in I}h_{ij}^{wd}+v_{ij}^{wd}+h_{ij}^{w-1,d^{‘}}+v_{ij}^{w-1,d^{‘}}\leq 1$
$\quad\forall i\in I,\forall w\in W,\forall d,d^{‘}\in\{火曜日,金曜日\}(d\neq d^{‘},w\geq 1)$
$\sum_{j\in I}\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}(h_{ij}^{wd}-v_{ij}^{wd}) = 0\quad\forall i\in I$
$8\leq\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}(h_{ij}^{wd}+v_{ij}^{wd})\leq 9\quad\forall i,j\in I$
$4\leq\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}h_{ij}^{wd}\leq 5\quad\forall i\in I$
$4\leq\sum_{w\in W}\sum_{d\in\{火曜日,金曜日\}}v_{ij}^{wd}\leq 5\quad\forall i\in I$
$1-\sum_{j\in I}h_{to,j}^{wd}-v_{to, from}^{w^{‘}d^{‘}}+home_{to}^{wd}(from)\geq 0$
$\sum_{j\in I}h_{to,j}^{wd}-home_{to}^{wd}(from)\geq 0$
$v_{to, from}^{w^{‘}d^{‘}}-home_{to}^{wd}(from)\geq 0$
$\quad\forall from,to\in I,\forall w,w^{‘}\in W,\forall d,d^{‘}\in \{火曜日,金曜日\}$
$1-v_{team, to}^{wd}-\sum_{j\in I}v_{j,from}^{w^{‘}d^{‘}}+visitor_{team,to}^{wd}(from)\geq 0$
$v_{team, to}^{wd}-visitor_{team,to}^{wd}(from)\geq 0$
$\sum_{j\in I}v_{j,from}^{w^{‘}d^{‘}}-visitor_{team,to}^{wd}(from)\geq 0$
$\quad\forall from,to,team\in I,\forall w,w^{‘}\in W,\forall d,d^{‘}\in \{火曜日,金曜日\}$
この記事は役に立ちましたか？
もし参考になりましたら、下記のボタンで教えてください。
コメント