はじめに

大学院生になった今、筆者の高校時代の野球部の練習メニューを振り返って、選手ごとの練習メニュー(スケジュール)を数理最適化の考え方で検討するプロセスを書いてみます。(舞台は北海道の公立高校を想定します)

練習メニューを考えるのに苦労している高校野球の監督や部員、別の分野で似たようなスケジューリング問題に取り組もうとしている方の参考になれば幸いです。

今回は特に、
・選手ごとの故障リスクを考慮すること
・選手ごとに重点項目(この選手はもっと筋力をつけたほうが良いなど)をうまく配置すること
の2点に注意して考えてみます。

最終的に、「足がいたいので走りたくなくて、打撃を冬で鍛えたい」「肩の調子が悪いので、ボールは投げずに筋トレを中心に練習したい」など、選手ごとの状況に合わせたスケジュールが組める感じです。

本記事ではPython+PuLPによるタダで仕事に使える数理最適化を参考にさせていただきました。上記のエントリー同様、PythonのPuLPを利用します。

スライド版のリンクです。
SlideShare - 無理しすぎない練習スケジュールを考える

※ 野球関係者にみてもらえればいいなと思っているので、もしよろしければたくさん拡散していただけると幸いです。

背景

冬季の練習は甲子園を目指す上で非常に重要です。しかし、北海道の公立高校においては以下の点で非常に制約条件が多く、人力で練習メニューのスケジュールを組むのが大変です。

・グラウンドに雪が積もるため、ビニールハウスや限られたスペースをうまく活用する必要がある
・選手ごとに重点項目(筋力向上・怪我の治療など)は異なるため、個別の練習メニューを考えていく必要がある

これらをうまく定式化で表現できるように考えてみます。
(全てをまとめたコードは記事末尾にあります！)

定式化 - 定数の設定

以下のように定数を設定します。

選手は20名
曜日は平日のみを考える
練習メニューは5種類(走・守・投・筋・打、1日の中で前半A・後半Bの2部構成)

scheduling.py


import string

# A選手からT選手まで(20人)のリスト
members=[chr(i)+"選手" for i in range(65, 65+20)]

# 曜日のリスト
days=["月", "火", "水", "木", "金"]

# 練習メニューのリスト
trainings=["走塁A", "守備A", "投球A", "筋力A", "打撃A",
           "走塁B", "守備B", "投球B", "筋力B", "打撃B"]

選手ごとの故障リスクを考慮する

選手ごとに、
「肩の調子が悪いので投球・守備練習は避けたい」
「手首が痛いので打撃練習をあまりやると故障しそう」
などといった故障リスクを考慮できるよう、以下のように定数をおきます。
(この部分は、選手一人一人に各練習に対する怪我リスク値を1~5で自己申告してもらうと良さそうです)

scheduling.py


# 走・守・投・筋・打に対する故障リスク値(1~5) 前半・後半で同じ値を設定
# 下記では、1行は選手一人を意味する
cc_day=[[1,1,4,1,1, 1,1,4,1,1],
        [2,1,1,3,1, 2,1,1,3,1],
        [3,1,1,1,1, 3,1,1,1,1],
        [3,2,1,4,1, 3,2,1,4,1],
        [4,3,3,1,1, 4,3,3,1,1],
        [1,1,1,1,1, 1,1,1,1,1],
        [1,2,4,3,1, 1,2,4,3,1],
        [1,1,1,2,4, 1,1,1,2,4],
        [3,3,3,3,3, 3,3,3,3,3],
        [1,2,4,1,1, 1,2,4,1,1],
        [2,1,4,3,1, 2,1,4,3,1],
        [3,2,1,1,1, 3,2,1,1,1],
        [3,2,1,4,1, 3,2,1,4,1],
        [2,1,5,2,1, 2,1,5,2,1],
        [1,4,2,2,4, 1,4,2,2,4],
        [1,2,1,3,1, 1,2,1,3,1],
        [1,3,1,2,4, 1,3,1,2,4],
        [3,3,1,3,3, 3,3,1,3,3],
        [1,3,1,2,4, 1,3,1,2,4],
        [3,3,1,3,3, 3,3,1,3,3]]

# 月・火・水・木・金 の数だけ用意する
cc = [cc_day, cc_day, cc_day, cc_day, cc_day]

# 辞書を用意し、c["曜日", "選手", "メニュー"]で値にアクセスできるようにする
c = {}
for d in days:
    for m in members:
        for t in trainings:
            c[d,m,t] = cc[days.index(d)][members.index(m)][trainings.index(t)]

(ここでは各曜日ごとに故障リスク値を一定としていますが、週末につれて値が大きくなっていくなどのように設定するとリアルかもしれません。)

選手ごとに重点項目をうまく配置する

選手ごとに、
「この冬で打てるようにならないとやばい」 → 打撃練習中心のメニュー
「線が細いので、筋力をつけたい」　→ 筋トレ中心のメニュー
などといった設定ができるよう、以下のように定数をおきます。
(これも週ごとに自己申告してもらったり、チームで話し合って決めると良さそうです)

scheduling.py


# 走・守・投・筋・打に対する経験値(1~5) 前半・後半で同じ値を設定
ex_day=[[2,1,1,3,4, 2,1,1,3,4],
        [3,3,3,4,4, 3,3,3,4,4],
        [3,1,1,2,3, 3,1,1,2,3],
        [4,2,1,3,3, 4,2,1,3,3],
        [2,4,1,3,4, 2,4,1,3,4],
        [2,2,2,3,3, 2,2,2,3,3],
        [4,4,4,4,4, 4,4,4,4,4],
        [1,1,1,3,1, 1,1,1,3,1],
        [3,3,3,2,1, 3,3,3,2,1],
        [1,1,1,1,1, 1,1,1,1,1],
        [1,2,4,3,1, 1,2,4,3,1],
        [1,1,1,2,4, 1,1,1,2,4],
        [3,3,3,3,3, 3,3,3,3,3],
        [1,2,4,1,1, 1,2,4,1,1],
        [2,1,4,3,1, 2,1,4,3,1],
        [3,2,1,1,1, 3,2,1,1,1],
        [3,2,1,4,1, 3,2,1,4,1],
        [2,1,5,2,1, 2,1,5,2,1],
        [1,3,1,2,4, 1,3,1,2,4],
        [3,3,1,3,3, 3,3,1,3,3]]

# 月・火・水・木・金 の数だけ用意する
ex = [ex_day, ex_day, ex_day, ex_day, ex_day]

# e["曜日", "選手", "メニュー"]で値にアクセスできるようにする　
e = {}

for d in days:
    for m in members:
        for t in trainings:
            e[d, m, t] = ex[days.index(d)][members.index(m)][trainings.index(t)]

定式化 - 変数の設定

曜日・選手ごとに、練習メニューの割り当てを意味する0・1変数を定義します。

scheduling.py

# 数理最適化問題（最大化）を宣言
problem = pulp.LpProblem("Problem-1st", pulp.LpMaximize)

# 変数集合を表す辞書
x = {} # 空の辞書

# 0-1変数を宣言
# {曜日}に、{メンバー}が、{メニュ-}をやれば1、otherwise 0
for d in days:
    for m in members:
        for t in trainings:
            x[d,m,t] = pulp.LpVariable("x({:},{:},{:})".format(d,m,t), 0, 1, pulp.LpInteger)

定式化 - 目的関数の設定

練習メニューによるチーム全体の獲得経験値を最大化したいので、以下のように設定します。

scheduling.py

# 目的関数を定義
problem += pulp.lpSum((e[d,m,t]* x[d,m,t]) for d in days for m in members for t in trainings), "TotalCost"

定式化 - 制約条件

冬の高校球児を取り巻くいろんな制約条件を表現してみます。
以下の4つに関する制約式を考えていきます。

1.練習メニューごとの人数制限
2.1日の練習メニューの構成
3.故障リスク
4.練習のバリエーション

1.練習メニューごとの人数制限を考える

練習メニューと実施場所の関係から、人数に関する制約を以下のように設定します。

scheduling.py


# 走塁・守備練習は5人以上必要
for d in days:
    for t in ["走塁A", "走塁B", "守備A", "守備B"]:
        problem += sum(x[d,m,t] for m in members) >= 5, "Constraint_eq_{:}_{:}".format(d,t)

# 筋トレは最大6人まで
for d in days:
    for t in ["筋力A", "筋力B"]:
        problem += sum(x[d,m,t] for m in members) <= 6, "Constraint_eq_{:}__{:}".format(d,t)

# 打撃練習は6人丁度必要
for d in days:
    for t in ["打撃A", "打撃B"]:
        problem += sum(x[d,m,t] for m in members) == 6, "Constraint_eq_{:}_{:}".format(d,t)

# 投球練習は2人以上必要
for d in days:
    for t in ["投球A", "投球B"]:
        problem += sum(x[d,m,t] for m in members) >= 2, "Constraint_eq_{:}_{:}".format(d,t)

2.1日の練習メニューの構成を考える

練習の実施方法について、以下の二つの条件を設定します。

１日の中で前半、後半に一つづつ割り当てる(2部構成)
前半・後半で別々の練習をする

scheduling.py



# 前半・後半で一個ずつ選ぶように
for d in days:
    for m in members:
        problem += sum(x[d,m,t] for t in ["走塁A", "守備A", "投球A", "筋力A", "打撃A"]) == 1, "Constraint_leq_{:}_{:}_前半".format(d,m)
        problem += sum(x[d,m,t] for t in ["走塁B", "守備B", "投球B", "筋力B", "打撃B"]) == 1, "Constraint_leq_{:}_{:}_後半".format(d,m)

# 前半・後半で別なもの選ぶように
for d in days:
    for m in members:
        problem += sum(x[d,m,t] for t in ["走塁A","走塁B"]) <= 1, "Constraint_leq_{:}_{:}_走塁".format(d,m)
        problem += sum(x[d,m,t] for t in ["守備A","守備B"]) <= 1, "Constraint_leq_{:}_{:}_守備".format(d,m)
        problem += sum(x[d,m,t] for t in ["打撃A","打撃B"]) <= 1, "Constraint_leq_{:}_{:}_打撃".format(d,m)
        problem += sum(x[d,m,t] for t in ["投球A","投球B"]) <= 1, "Constraint_leq_{:}_{:}_投球".format(d,m)
        problem += sum(x[d,m,t] for t in ["筋力A","筋力B"]) <= 1, "Constraint_leq_{:}_{:}_筋力".format(d,m)

3.故障リスクを一定に抑える

選手ごとの故障リスクについて考慮した練習メニューを考えます。先ほど設定した故障リスクの定数を使って、その合計がある一定以下に抑えられるように以下の制約を加えます。ここではとりあえず30に設定します(25以下から順番に試して行って、実行可能な最小値が30でした)。

scheduling.py


# 一人一人の1週間の怪我リスクの総和が30を超えないようにする
for m in members:
    for t in trainings:
        problem += sum(c[d,m,t]*x[d,m,t] for d in days) <= 30, "Constraint_eq_{:}__{:}".format(m,t)

4.いろんな練習が配分されるようにする

上記の制約条件だけだと、選手ごとに経験値がたくさん得られる練習ばかりが選ばれるため、1週間毎日走って打つだけ...というようなスケジュールが組まれてしまいます。

そこで、1週間の中同じ練習ばかり割り当てられないように以下の制約を加えます。

scheduling.py


# １週間で、同じメニューを4回以上やらない
for m in members:
    for t in trainings:
        problem += sum(x[d,m,t] for d in days) <= 2, "Constraint_eq_{:}_{:}".format(m,t)

制約条件は以上です。まとめると以下のような感じです。

計算を実行する処理

定数・目的関数・制約条件が定義できたので、計算を実行するコードを書きます。

scheduling.py


# ソルバー指定
solver = pulp.solvers.PULP_CBC_CMD()

# 時間計測開始
time_start = time.clock()

result_status = problem.solve(solver)

# 時間計測終了
time_stop = time.clock()

結果を表示する処理 - スケジュール出力

いい感じにスケジュールが出力されるように、以下のように書いてみました。
(書き方があまりよくないので、ご指摘いただけると幸いです)

scheduling.py

# 結果表示 ----------------------------------------------------------------------
print("\n")
# チームメイト
print("【チームメイト】\n")
print("members = {:}".format(members))
# 練習メニュー
print("【練習メニュー】\n")
print("trainings = {:}".format(trainings))
# 曜日集合
print("【曜日】\n days = {:}".format(days))

print("Result ------------------------------------------------------------------\n")
print("最適性 = {:}, 目的関数値 = {:}, 計算時間 = {:} (秒)\n"
      .format(pulp.LpStatus[result_status], pulp.value(problem.objective),
              time_stop - time_start))

print("【スケジュール】\n")
for d in days:
    print(d + "曜日 --------------------------\n")
    for m in members:
        check = 0
        for t in trainings:
            if x[d,m,t].value() == 1:
                if check==0:
                    print("{:}  前半練習：{:}".format(m,t))
                    check += 1
                elif check==1:
                    print("{:}  後半練習：{:}\n".format(m,t))
                    check -= 1

プログラム実行

$ python scheduling.py

以下のように出力されます。

以下のような感じのスケジュールになってます。

【月曜日】

選手	前半メニュー	後半メニュー
選手A	筋力	打撃
選手B	打撃	守備
選手C	走塁	打撃
選手D	打撃	走塁
...	...	...

【A選手】に着目して見てみます。

	走	守	投	筋	打
故障リスク	1	1	4	1	1
経験値	2	1	1	3	4

選手Aは、肩に違和感があって今週は打撃を多めに入れたい選手のようです。
1週間の練習スケジュールは以下のようになっていました。

曜日	前半メニュー	後半メニュー
月曜	筋力	打撃
火曜	打撃	走塁
水曜	筋力	打撃
木曜	打撃	走塁
金曜	走塁	筋力

いい感じに経験値が高い筋トレと打撃練習が入っています。
走塁練習は人数が必要なため、割り当てられている感じになっているんだと思います。

【E選手】も見てみます。

	走	守	投	筋	打
故障リスク	4	3	3	1	1
経験値	2	4	1	3	4

打てるようになりたくて、足が痛い選手のようです。
スケジュールは以下のようになってました。

曜日	前半メニュー	後半メニュー
月曜	打撃	守備
火曜	守備	打撃
水曜	守備	走塁
木曜	打撃	守備
金曜	筋力	打撃

足が痛いらしいので水曜日が憂鬱そうですが、走塁は最小限にして打撃練習中心のメニューになっていそうです。

おわりに

筆者(副主将)の現役時代を考えてみると、練習メニューは全てキャプテンに考えてもらっていて、何も力になれず肩身が狭い思いをしていたような気がします。もしあの時に数理最適化の考え方とpythonを知っていれば、もしかしたら力になれたかもしれないなと思いました。

同じような気持ちの高校球児や、練習メニューに悩む監督・コーチなどにこの記事が届けば良いなと思います。

※ 修正すべき点やもっとこう書いたほうがいいなど、ご指摘いただけると幸いです。

コード全体

scheduling.py

import pulp
import time
import string


# 選手・練習メニューなどを定義 ------------------------------------------------------

# A選手からT選手まで(20人)のリスト
members=[chr(i)+"選手" for i in range(65, 65+20)]

# 曜日のリスト
days=["月", "火", "水", "木", "金"]

# 練習メニューのリスト
trainings=["走塁A", "守備A", "投球A", "筋力A", "打撃A",
           "走塁B", "守備B", "投球B", "筋力B", "打撃B"]


# 選手・練習毎の故障リスクを定義 ----------------------------------------------------

cc_pre=[[1,1,4,1,1,1,1,4,1,1],
        [2,1,1,3,1,2,1,1,3,1],
        [3,1,1,1,1,3,1,1,1,1],
        [3,2,1,4,1,3,2,1,4,1],
        [4,3,3,1,1,4,3,3,1,1],
        [1,1,1,1,1,1,1,1,1,1],
        [1,2,4,3,1,1,2,4,3,1],
        [1,1,1,2,4,1,1,1,2,4],
        [3,3,3,3,3,3,3,3,3,3],
        [1,2,4,1,1,1,2,4,1,1], 
        [2,1,4,3,1,2,1,4,3,1],
        [3,2,1,1,1,3,2,1,1,1],
        [3,2,1,4,1,3,2,1,4,1],
        [2,1,5,2,1,2,1,5,2,1],
        [1,4,2,2,4,1,4,2,2,4],
        [1,2,1,3,1,1,2,1,3,1],
        [1,3,1,2,4,1,3,1,2,4],
        [3,3,1,3,3,3,3,1,3,3],
        [1,3,1,2,4,1,3,1,2,4],
        [3,3,1,3,3,3,3,1,3,3]]
cc=[cc_pre, cc_pre, cc_pre, cc_pre, cc_pre]


# 空の辞書を定義し、c["曜日", "メンバー", "メニュー"]でアクセスできるようにする
c = {}

for d in days:
    for m in members:
        for t in trainings:
            c[d,m,t] = cc[days.index(d)][members.index(m)][trainings.index(t)]


# 選手・練習メニューごとに経験値を定義 -----------------------------------------------

ex_pre=[[2,1,1,3,4,2,1,1,3,4],
        [3,3,3,4,4,3,3,3,4,4],
        [3,1,1,2,3,3,1,1,2,3],
        [4,2,1,3,3,4,2,1,3,3],
        [2,4,1,3,4,2,4,1,3,4],
        [2,2,2,3,3,2,2,2,3,3],
        [4,4,4,4,4,4,4,4,4,4],
        [1,1,1,3,1,1,1,1,3,1],
        [3,3,3,2,1,3,3,3,2,1],
        [1,1,1,1,1,1,1,1,1,1],
        [1,2,4,3,1,1,2,4,3,1],
        [1,1,1,2,4,1,1,1,2,4],
        [3,3,3,3,3,3,3,3,3,3],
        [1,2,4,1,1,1,2,4,1,1],
        [2,1,4,3,1,2,1,4,3,1],
        [3,2,1,1,1,3,2,1,1,1],
        [3,2,1,4,1,3,2,1,4,1],
        [2,1,5,2,1,2,1,5,2,1],
        [1,3,1,2,4,1,3,1,2,4],
        [3,3,1,3,3,3,3,1,3,3]]
ex = [ex_pre, ex_pre, ex_pre, ex_pre, ex_pre]

# 空の辞書を定義し、e["曜日", "メンバー", "メニュー"]でアクセスできるようにする
e = {}

for d in days:
    for m in members:
        for t in trainings:
            e[d, m, t] = ex[days.index(d)][members.index(m)][trainings.index(t)]


# 定式化 ------------------------------------------------------------------------


# 数理最適化問題（最大化）を宣言
problem = pulp.LpProblem("Problem-1st", pulp.LpMaximize)

# 変数集合を表す辞書
x = {}

# 0-1変数を宣言
# {曜日}、{メンバー}に、{メニュ-}を割り当てられれば1、otherwise 0
for d in days:
    for m in members:
        for t in trainings:
            x[d,m,t] = pulp.LpVariable("x({:},{:},{:})".format(d,m,t), 0, 1, pulp.LpInteger)


# 目的関数を定義
problem += pulp.lpSum((e[d,m,t]* x[d,m,t]) for d in days for m in members for t in trainings), "TotalCost"


# 制約条件を定義 ----------------------

# 前半・後半で一個ずつ選ぶように
for d in days:
    for m in members:
        problem += sum(x[d,m,t] for t in ["走塁A", "守備A", "投球A", "筋力A", "打撃A"]) == 1, "Constraint_leq_{:}_{:}_前半".format(d,m)
        problem += sum(x[d,m,t] for t in ["走塁B", "守備B", "投球B", "筋力B", "打撃B"]) == 1, "Constraint_leq_{:}_{:}_後半".format(d,m)

# 前半・後半で別なもの選ぶように
for d in days:
    for m in members:
        problem += sum(x[d,m,t] for t in ["走塁A","走塁B"]) <= 1, "Constraint_leq_{:}_{:}_走塁".format(d,m)
        problem += sum(x[d,m,t] for t in ["守備A","守備B"]) <= 1, "Constraint_leq_{:}_{:}_守備".format(d,m)
        problem += sum(x[d,m,t] for t in ["打撃A","打撃B"]) <= 1, "Constraint_leq_{:}_{:}_打撃".format(d,m)
        problem += sum(x[d,m,t] for t in ["投球A","投球B"]) <= 1, "Constraint_leq_{:}_{:}_投球".format(d,m)
        problem += sum(x[d,m,t] for t in ["筋力A","筋力B"]) <= 1, "Constraint_leq_{:}_{:}_筋力".format(d,m)


# 走塁・守備は5人以上必要
for d in days:
    for t in ["走塁A", "走塁B", "守備A", "守備B"]:
        problem += sum(x[d,m,t] for m in members) >= 5, "Constraint_eq_{:}_{:}".format(d,t)
# 筋トレは最大6人まで
for d in days:
    for t in ["筋力A", "筋力B"]:
        problem += sum(x[d,m,t] for m in members) <= 6, "Constraint_eq_{:}__{:}".format(d,t)
# # 打撃は6人以上必要
for d in days:
    for t in ["打撃A", "打撃B"]:
        problem += sum(x[d,m,t] for m in members) == 6, "Constraint_eq_{:}_{:}".format(d,t)
# 投球は2人以上必要
for d in days:
    for t in ["投球A", "投球B"]:
        problem += sum(x[d,m,t] for m in members) >= 2, "Constraint_eq_{:}_{:}".format(d,t)


# 一人一人の1週間の怪我リスクの総和が30を超えないようにする
for m in members:
    problem += sum(c[d,m,t]*x[d,m,t] for d in days for t in trainings) <= 30, "Constraint_eq_{:}__{:}".format(m,t)

# １週間で、同じメニューを4回以上やらない
for m in members:
    for t in trainings:
        problem += sum(x[d,m,t] for d in days) <= 2, "Constraint_eq_{:}_{:}".format(m,t)


# 計算実行 ----------------------------------------------------------------------

# ソルバー指定
solver = pulp.solvers.PULP_CBC_CMD()

# 時間計測開始
time_start = time.clock()
result_status = problem.solve(solver)
# 時間計測終了
time_stop = time.clock()


# 結果表示 ----------------------------------------------------------------------
print("\n")
# チームメイト
print("【チームメイト】\n")
print("members = {:}".format(members))
# 練習メニュー
print("【練習メニュー】\n")
print("trainings = {:}".format(trainings))
# 曜日集合
print("【曜日】\n days = {:}".format(days))

print("Result ------------------------------------------------------------------\n")
print("最適性 = {:}, 目的関数値 = {:}, 計算時間 = {:} (秒)\n"
      .format(pulp.LpStatus[result_status], pulp.value(problem.objective),
              time_stop - time_start))

print("【スケジュール】\n")
for d in days:
    print(d + "曜日 --------------------------\n")
    for m in members:
        check = 0
        for t in trainings:
            if x[d,m,t].value() == 1:
                if check==0:
                    print("{:}  前半練習：{:}".format(m,t))
                    check += 1
                elif check==1:
                    print("{:}  後半練習：{:}\n".format(m,t))
                    check -= 1

参考

Python+PuLPによるタダで仕事に使える数理最適化
 組み合わせ最適化-典型問題と実行方法
 組み合わせ最適化を体系的に知ってpythonで実行してみよう
 組み合わせ最適化を使おう
 組み合わせ最適化-典型問題-勤務スケジューリング問題