組合せ最適化でナーススケジューリング問題を解く

  • 8
    Like
  • 1
    Comment

これなに

遺伝的アルゴリズムでナーススケジューリング問題(シフト最適化)を解く」を組合せ最適化で解いてみました。

表(シフト希望等)を読む

python
import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars

a = pd.read_html('http://qiita.com/shouta-dev/items/1970c2746c3c30f6b39e')[1].T
a,a.columns = a.iloc[1:],a.iloc[0].tolist()
a.必要人数 = a.必要人数.astype(int)
a.iloc[:,2:] = ~a.iloc[:,2:].isnull()
a.insert(0, '曜日', a.index.str[0])
a.reset_index(drop=True, inplace=True)
a = a.iloc[:,list(range(3,a.shape[1]))+[0,1,2]]
print(a[:3]) # 最初の3行表示
従業員0 従業員1 従業員2 従業員3 従業員4 従業員5 従業員6 従業員7 従業員8 従業員9 曜日 時間帯 必要人数
0 True True False True False True False False False False 2
1 False True False True False True False True False False 3
2 False True False True True True False False True False 3

Pythonで解く

V割当等の 「V…」は変数です。

python
Nコマ,N従業員 = a.shape[0],a.shape[1]-3
L従業員 = list(range(N従業員))
L管理者 = [3,5,9] # 管理者は従業員3, 5, 9
C必要人数差 = 10
C希望不可 = 100
C最低コマ数 = 1
C管理者不足 = 100
C1日2コマ = 10
m = LpProblem() # 数理モデル
V割当 = np.array(addbinvars(Nコマ, N従業員))
a['V必要人数差'] = addvars(Nコマ)
V最低コマ数 = addvars(N従業員)
a['V管理者不足'] = addvars(Nコマ)
V1日2コマ = addvars(N従業員)
m += (C必要人数差 * lpSum(a.V必要人数差)
    + C希望不可 * lpSum(a.apply(lambda r: lpDot(1-r[L従業員],V割当[r.name]), 1))
    + C最低コマ数 * lpSum(V最低コマ数)
    + C管理者不足 * lpSum(a.V管理者不足)
    + C1日2コマ * lpSum(V1日2コマ)) # 目的関数
for _,r in a.iterrows():
    m += r.V必要人数差 >=  (lpSum(V割当[r.name]) - r.必要人数)
    m += r.V必要人数差 >= -(lpSum(V割当[r.name]) - r.必要人数)
    m += lpSum(V割当[r.name,L管理者]) + r.V管理者不足 >= 1
for j,n in enumerate((a.iloc[:,L従業員].sum(0)+1)//2):
    m += lpSum(V割当[:,j]) + V最低コマ数[j] >= n # 希望の半分以上
for _,v in a.groupby('曜日'):
    for j in range(N従業員):
        m += lpSum(V割当[v.index,j]) + V1日2コマ[j] <= 2 # 各曜日で2コマまで
%time m.solve()
R結果 = np.vectorize(value)(V割当).astype(int)
a['結果'] = [''.join(i*j for i,j in zip(r,a.columns)) for r in R結果]
print('目的関数', value(m.objective))
print(a[['曜日','時間帯','結果']])
出力
Wall time: 31.2 ms
目的関数 0.0
   曜日 時間帯                結果
0   月   朝          従業員1従業員5
1   月   昼      従業員3従業員5従業員7
2   月   夜      従業員1従業員3従業員4
3   火   朝          従業員0従業員3
4   火   昼      従業員3従業員5従業員7
5   火   夜      従業員4従業員5従業員8
6   水   朝          従業員0従業員5
7   水   昼      従業員1従業員3従業員5
8   水   夜      従業員3従業員4従業員8
9   木   朝              従業員3
10  木   昼          従業員5従業員7
11  木   夜          従業員8従業員9
12  金   朝          従業員1従業員5
13  金   昼      従業員1従業員7従業員9
14  金   夜      従業員5従業員6従業員8
15  土   朝          従業員0従業員3
16  土   昼  従業員2従業員6従業員7従業員9
17  土   夜  従業員3従業員4従業員6従業員9
18  日   朝          従業員0従業員9
19  日   昼  従業員2従業員3従業員6従業員9
20  日   夜  従業員2従業員3従業員4従業員6
  • 計算時間は30ミリ秒で、厳密に最適な解が得られました。
  • 目的関数(ペナルティ総和)は $0$ なので、すべての条件を満たしています。

以上


参考