組合せ最適化への挑戦録（勤務スケジューリング）8.体裁が整った

#これまでの踏跡
https://qiita.com/wellwell3176/items/ed166482c07d4a667060

#目次

前回の失敗の整理
出力の確認
考察
補足：プログラム全容

#前回の失敗の整理)
まず、前回の考察で「ソルバーによる解式ではなく、どうやら表を作るところが間違っている」ということが分かった。

マルチインデックスは上図のようになっており、この表の[0,0]に該当するのはx(p,m,d,a)=(1,1,1,0)なのだが、
x(p,m,d,a)の先頭に入っているのはx(0,3,1,0)。この差が、表を整形した時にズレを生じさせていた（下図）。

これを直すにはp,m,d,a,x(p,m,d,a).valueの値を揃えて、マルチインデックスに代入すれば良い。
pythonで実装したのが下記。

df_results=df_raw.copy() #元々のマルチインデックスが既に存在するので、これをコピーして結果用に流用する

dict_x = ShiftScheduling.variablesDict() 
#.solveで解いた結果は、問題の中にしか入っていないので、問題.varibaleDict()で辞書型として取り出す。

for d,a in list_da:
  for p,m in list_pm:
    keys_pmda = "x({},{},{},{})".format(p,m,d,a)
    values_pmda=dict_x[keys_pmda]
    r =pulp.value(values_pmda)
#やや迂遠だが、pmdaからキーを作る　⇒ キーで辞書から値を取り出す　⇒　pulp.vaue(値)で変数の解を取り出す、と言う流れ
    df_results.at[(d,a),(p,m)]=r
#後はpmdaと変数解をマルチインデックスに代入して解決

#出力の確認

この結果として得られたデータを改めて表にしたものが上表である。
無事に有給も忌避も完全回避が成功している。

他に必要な機能として必要なものを列記すると、

1.昼勤と夜勤の差が大きい人はあまり良くない。

　具体的には作業者3の事で、昼勤4回、夜勤2回となっている。
　夜勤が少ない分だけ昼勤が増えた、ということでバランスが取れているといえば取れているが、
　最低でも夜勤1回は出ること　を条件に入れたほうが納得されやすいだろう。

2.新人だけでシフトを埋めるのは良くない。

　今回のケースでは3日目の夜勤が7番と8番での作業になっている。
　この2名は新人なので、夜勤をこの2人だけで回すのは良くないだろう。
　新人だけでシフトを埋めてはいけない　を制約条件に入れるべきだ。

3.実際の必要人数は昼勤と夜勤、曜日によって違う

　今回、必要人数は全て2としてきたが、実際には平日・昼勤は多めに必要となる。
　よって、日毎に必要人数が違う情報を入力し、それに基づいてシフトを計算させたい。

これら3つを満たせば、機能としては一段落。
あとは現場の使いやすさを考えて『手修正した後の評価機能』を入れるべきだろう。

#考察
残ってる必要機能

1.　最低でも夜勤1回は出ること

これはさほど難しくない。
「各勤務者の夜勤出勤回数」をlpSumで集め、制約条件として設定すれば良いはず。

２. 新人だけでシフトを埋めてはいけない

これは今までと少し条件式の書き方が変わるはず。
パッと思いつく方法としては、p=1（新人）で固定し、daごとのxの総和を取る方法。
基本データはマルチインデックスが抽出したものであり、pとmはタプルになってるので、そこからp=1のものだけ抜き出せるかどうかがポイントになりそう。

３. 日毎に必要人数が違う

これはまず元データに必要人数を入力しておいて、新たにlist_pmnを作れば行ける気がする
n=必要人数で、d,aに対してlp.sum(x(p,m,d,a)>=nで作れると思う。

４.手修正後の評価機能

この手の勤務スケジュール自動化の現実的な運用での一番の問題は「明確に言語化はしてないけどシフトを組む人の都合で色々とイジりたい箇所がある」事だと思う。

表立って堂々とは言えないけど、AさんとBさんは前にトラブルになったから同じシフトに入れたくないなあ、などなど。
そのため最終的には課長が完成品に微修正を掛けてデータを作ることになるのだが、その際に
「課長が変更した後の勤務表は各種要望をこれだけ満たしていますよ」という評価機能が在ったほうが便利な気がする。

ただ、このあたりはまず基本機能をすべて取り込んでからで問題ないため、後回し。

#プログラム全容

import openpyxl
import pandas as pd
import numpy as np
import pulp
#エクセルファイルからマルチインデックスで読み取り
df_raw= pd.read_excel("/data.xlsx",index_col=[0,1],header=[0,1])

#文字列を全部数字に変換し、各indexとcolumnsにラベルを付けておく。
df_raw.rename(index={"昼":0,"夜":1},level=1,inplace=True)
df_raw.rename(columns={"係長":1,"主任":2,"一般":0,"新人":3},level=0,inplace=True)
df_raw.replace({np.NaN:0,"忌避":1,"有給":2},inplace=True)
df_raw.index.set_names(["date","time"],inplace=True)
df_raw.columns.set_names(["position","member"],inplace=True)

df_raw=df_raw.iloc[:,1:]
df_needs=df_raw.iloc[:,1]
#今回のデータからは不要なので必要人数を切り離す

list_pm = df_raw.columns.to_list()
list_da= df_raw.index.to_list()

#問題の定義
ShiftScheduling = pulp.LpProblem("ShiftScheduling", pulp.LpMinimize)

#変数宣言
x = {}
for p,m in list_pm:
    for d,a in list_da:
            x[p,m,d,a] = pulp.LpVariable("x({:},{:},{:},{:})".format(p,m,d,a), 0, 1, pulp.LpInteger)

#目的関数1 全員の出勤の合計値が小さい方が良い＝全変数の総和が小さい方が良い
obj1= pulp.lpSum(x)

#目的関数2 夜勤忌避の希望が通る方が良い
list_yakin=[]
for p,m in list_pm:
  df_yakin = df_raw[df_raw.loc[:,(p,m)]==1]
  for i in range(len(df_yakin)):
      da_yakin = df_yakin.index
      list_temp = [p,m,da_yakin[i][0],da_yakin[i][1]]
      list_yakin.append(list_temp)
obj2 = pulp.lpSum(x[p,m,d,a] for p,m,d,a in list_yakin)

#目的関数3 有給の希望が通る方が良い
list_yukyu=[]
for p,m in list_pm:
  df_yukyu = df_raw[df_raw.loc[:,(p,m)]==2]
  for i in range(len(df_yukyu)):
      da_yukyu = df_yukyu.index
      list_temp = [p,m,da_yukyu[i][0],da_yukyu[i][1]]
      list_yukyu.append(list_temp)
obj3 = pulp.lpSum(x[p,m,d,a] for p,m,d,a in list_yukyu)

#目的関数4　勤務者間の労働回数はなるべく近いほうが良い
obj4 = pulp.LpVariable("workcount",lowBound=0)

#目的関数の定義
ShiftScheduling += obj1 + obj2 +obj3 + obj4

#制約条件
#制約条件1:全員必ず3回以上出勤
#制約条件4:勤務回数の偏りを減らす(最大値がobj4に格納されるようにする)
for p,m in list_pm:
   ShiftScheduling +=  pulp.lpSum(x[p,m,d,a] for d,a in list_da) >= 3
   ShiftScheduling +=  pulp.lpSum(x[p,m,d,a] for d,a in list_da) <= obj4
  
#制約条件2:全シフトで2人以上出勤
for d,a in list_da:
  ShiftScheduling +=  pulp.lpSum(x[p,m,d,a] for p,m in list_pm) >= 2

#制約条件3:連続出勤不可
list_da1 = list_da[:-1]
list_da2 = list_da[1:]
for i in range(len(list_da1)):
    list_da1[i]=list_da1[i]+list_da2[i]
for p,m in list_pm:
  for d1,a1,d2,a2 in list_da1:
      ShiftScheduling += x[p,m, d1, a1]+x[p,m,d2,a2] <=1

#式を解く
results = ShiftScheduling.solve()

#出力（解けたかどうかの確認）
print("optimality = {:}, target value = {:}".format(pulp.LpStatus[results], pulp.value(ShiftScheduling.objective)))

#出力表を作る作業
df_results=df_raw.copy()
dict_x = ShiftScheduling.variablesDict()

for d,a in list_da:
  for p,m in list_pm:
    keys_pmda = "x({},{},{},{})".format(p,m,d,a)
    values_pmda=dict_x[keys_pmda]
    r =pulp.value(values_pmda)
    df_results.at[(d,a),(p,m)]=r

print(df_results)

今回使用したdata.xlsxは下図の通りのエクセルファイルである。