Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
67
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

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

これなに

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

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

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

a = pd.read_table(StringIO("""\
曜日\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t日
時間帯\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t夜
必要人数\t2\t3\t3\t2\t3\t3\t2\t3\t3\t1\t2\t2\t2\t3\t3\t2\t4\t4\t2\t4\t4
従業員0\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t
従業員1\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t
従業員2\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○
従業員3\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○
従業員4\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○
従業員5\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t
従業員6\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○
従業員7\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t
従業員8\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○
従業員9\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○""")).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[['曜日','時間帯','結果']])
出力
CPU times: user 7.45 ms, sys: 4.23 ms, total: 11.7 ms
Wall time: 22.8 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
  • 計算時間は23ミリ秒で、厳密に最適な解が得られました。
  • 目的関数(ペナルティ総和)は $0$ なので、すべての条件を満たしています。

以上


参考

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
67
Help us understand the problem. What are the problem?