特集「最適化技術に基づく統計的推論」［原著論文］

統計数理（2013）
第 61 巻 第 1 号 79–95
c 2013 統計数理研究所


ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現†

秋田 博紀 ・池上 敦子†（受付 2012 年 12 月 5 日；改訂 2013 年 4 月 12 日；採択 4 月 16 日）

要旨

本論文では，ナース・スケジューリングの解空間把握に取り組む．病棟ナースの勤務表作成
では，各シフトに適切な人数とスキルレベルのナースを揃えると同時に，それぞれのナースの勤務負荷を考慮しなければならない．ナース・スケジューリングは，組合せ最適化問題として解くことが難しい問題として知られてきたが，これに加え，人間が潜在的に考慮している制約や評価尺度も存在することから，コンピュータや最適化アルゴリズムにとって扱いにくい問題でもある．この問題における意思決定を支援するためには，実行可能解空間を直感的に把握でき，その中の良解の分布に関する情報を提供できるような仕組みが必要である．本論文では，
ナース・スケジューリングの部分問題として，1 ナースの最適スケジュールを見つける問題を対象に，この問題の解空間を表現するネットワークを構築する．このネットワークのソースノードからシンクノードまでの全経路は，そのナースの実行可能スケジュールであると同時に，すべての実行可能スケジュールがこのネットワークの経路として含まれる．ある試行解（勤務表）
に対し，他のナースのスケジュールを固定した下での最適スケジュールや上位複数の最良スケ
ジュールを，ネットワーク上の最短路や k 最短路を探索することで得られるようになる．本論
文では，このネットワークの構築方法と実際に構築した結果を報告する．
キーワード： ナース・スケジューリング，解空間，解の可視化，ネットワーク表現，
動的計画．
1. はじめにナース・スケジューリングは，病棟ナースの各日の勤務を決定する勤務表作成問題である．
表 1 に，3 交替制勤務表の例（Ikegami and Niwa, 2003）を示す．
一般に，1 列目にナース名を記載するが，この例ではナース番号を示してある．1 行目には日付，2 行目には曜日を頭文字で示してある．各行における各日の列に，対象ナースのその日の勤務内容の記号（この例では，―は日勤，e は準夜勤，n は深夜勤，+ はセミナ等のその他の勤
務，/は休み）が示される．そして，各列の下には各シフトの勤務人数，各行の右には対象ナー
スのその月における休みの回数や各シフトの勤務回数が示されている．
ナース・スケジューリング研究は，1970 年代にアメリカで始まった（Warner, 1976; Miller etal., 1976; Arther and Ravindran, 1981）が，アルゴリズムの適用だけでは思うようなスケジュー
ルを得ることが難しいことから意思決定支援システムの導入が提案された（Bell et al., 1986）．
†

成蹊大学 理工学部：〒186–8633 東京都武蔵野市吉祥寺北町 3–3–1

統計数理

80
表 1.

第 61 巻

第 1 号 2013

3 交替勤務表の例：3shift-DATA1（Ikegami and Niwa, 2003）

その後，アメリカからはこの問題に関する論文が出版されなくなったが，アメリカでは保険制度の影響でスケジューリングの自由度も低く，ナース・スケジューリング研究の必要性がなくなったからだとも言われる．一方，ナース・スケジューリング問題の解決を望む国は多く，日本では 1996 年に新たなモデルが提案され（池上 他, 1996），1998 年からは日本のみならずイギ
リス，カナダからも一斉に論文（池上・丹羽, 1998; Dowsland, 1998; Jaumard et al., 1998; Millar
and Kiragu, 1998; Nonobe and Ibaraki, 1998）が出始めた．多くの論文は，メタヒューリスティッ
クアルゴリズムを評価するための 1 問題例として求解困難なこの問題を選んだものであったが，その理由にはメタヒューリスティックスの考え方が世に広まった直後だったことも考えられる．
また，当時は，解いた問題例の具体的入力データを公開する論文がほとんど存在しなかった．
Millar and Kiragu（1998）は，ネットワーク構造に基づく整数計画問題としてこの問題に取り組み，問題例データも公開していたが，対象とする問題サイズは非常に小さいもの（8 ナース・2
週間分のスケジューリング）であった．現在では世界中の多くの研究者がナース・スケジューリング問題に取り組み（Burke et al., 2004），ベンチマークサイトも広まっている（University of
Nottingham, 2006）．
ナース・スケジューリングは，何をもって最適な解（勤務表）とするかの定義が難しいだけでなく，例え，定義できたとしても, 解を得ること自体が難しい組合せ最適化問題として知られナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現

81てきた．一方，近年の汎用ソルバーの高性能化から，目的関数や制約条件を規定できれば，厳密最適解を得ることも可能となり，最適解が知られていなかった問題例に対しても最適解を得ることに成功した結果も出てきた（乾・池上, 2010）．従って，今後の研究の興味は，アルゴリ
ズムの構築だけでなく，評価尺度（目的関数）をどのように与え，最適解をどう評価するかや，解の修正の可能性を把握するために多様な解を得ることに向かうと考えられる．
本研究では，それらの方向性の基盤となるものとして，ナース・スケジューリングにおける実行可能解や良解の空間を把握する仕組みを提案する．解の空間を把握するために，ナース 1
人分の最適スケジュールを求める問題を部分問題として扱い，Ikegami and Niwa（2003）が提案した subproblem-centric approach における部分問題の解空間をネットワーク構造で表現することにより，部分問題の最適解を動的計画法で得ることや，良解の複数列挙を可能にする仕組みを提案し，解空間把握や勤務表作成の可能性について議論する．
具体的には，部分問題の全ての実行可能解を動的計画法の考え方に基づいてネットワーク構
造で表す．ナース 1 人分の 1ヶ月の実行可能スケジュールは数 100 万存在すると考えられるが，それらすべてを列挙したり，比較評価しながら各ナースのスケジュールを組合わせていくこと
は，実行時間的に考えても現実的でない．そこで 1 ナースの実行可能スケジュールの全列挙と同等な解表現として，ネットワーク構造を利用し，ネットワーク上に設定したソースノードとシンクノードを結ぶすべての経路が実行可能スケジュールとなると同時に，すべての実行可能
スケジュールがネットワーク上の経路として含まれるようにする方法を提案する．
本論文では，このネットワークの構築方法と，実際に構築した結果，そして，完成したネット
ワークを可視化して解の可能性を把握する仕組みについて報告する．以降，subproblem-centric
approach のことを，部分問題軸アプローチ（池上, 2005）とよぶことにする．
2. ナース・スケジューリング

ナース・スケジューリングにおける制約条件は，各シフトの勤務メンバー構成に関わるシフ
ト制約と，各ナースの勤務負荷に関わるナース制約とに，大きく分けることができる．
シフト制約

毎日のシフトに必要な人数や適切なメンバーを確保するために，合計人数だけでなくスキル
レベルや担当患者等で分けられたナースグループからの「各シフトにおける勤務人数」の上下限を設定する条件である．グループは，ナース集合の部分集合のことであり，1 人のナースが複数のグループに所属している（例えば，あるナースは担当患者により A チームに所属すると同時に，スキルレベル的にはベテラングループに所属するといったように，複数の部分集合の要素となる）ことが一般的である．
シフト制約は，例えば「夜勤には合計で 4 名，A チーム，B チーム，C チームからそれぞれ 1
名以上とし，新人同士の勤務を避け，ベテランが 1 名以上含まれるように考えている」場合，全員，A，B，C，新人，ベテランの 6 種類のグループを設定し，毎日の夜勤に対して，勤務人数の（下限，上限）をそれぞれ，（4,4），（1,2），（1,2），（1,2），（0,1），（1,4）といったように設定する．
ナース制約

各ナースの社会的な生活や健康を守り，士気を保つためにも，休みや勤務の希望を考慮した
り，無理な勤務にならないよう考慮する条件である．
具体的には，各ナースについて大きく以下の 3 つ，そして（3）についてはさらに詳しく 3 つを考える．
（1）各シフトに対する勤務回数や休み回数に上下限を設定する

82

統計数理

第 61 巻

第 1 号 2013（2）セミナ等の確定している勤務，休みや勤務の希望を達成する（3）禁止するシフト並びを避ける
a）同一シフトの連続回数の上下限を設定する
b）同一シフトの勤務間隔日数の上下限を設定する
c）異種シフトを含む禁止シフト並びを避ける
過去の勤務表を観察すると，一般的に，シフト制約が重視され，ナースの休み希望を諦めるといったナース制約の緩和がみられるが，長期的に看護の質を守るためには，ナースの健康や士気を守ることも非常に重要であり，シフト制約とナース制約の両方を満たすことが必要である．
これに関し，Ikegami and Niwa（2003）は，各ナースの心身の健康状態を十分把握した人間でない限り「適切なナース制約の緩和」ができないことに着目した．さらに，シフト制約を全て守った解においては「シフト制約を満たしたままの修正が困難である」のに対し，ナース制約を全て守った解が「適切なナース制約の緩和を可能とする」と同時に「シフト制約をすべて満たした解への修正を容易にする」ことを病院現場で観察した．従って，現場に提供する暫定的な解は，ナース制約を全て守った下で，できる限りシフト制約を満たした解であるべきと主張し，定式化としては，暫定的な目的関数に「シフト制約を違反する度合いの最小化」を設定することを提案した．この提案に基づく定式化を以下に示す．
意思決定変数

1 人のナースの実行可能スケジュールを「そのナースに関する全てのナース制約を満たすス
ケジュール」とし，ナース i が実行可能スケジュール p を割当てられるときに 1，そうでないと
きに 0 となる意思決定変数 λip を使う．
記号

M = {1, 2, . . . , m} : ナース番号の集合．
N = {1, 2, . . . , n} : スケジューリング対象日の集合．
W = {0, 1, . . . , w} : シフト番号の集合（例，0:休み，1:日勤，2:準夜勤，3:深夜勤）．
R = {r| r はグループ } : スキルや担当患者で分けられたグループの集合．
Gr = {i| ナース i はグループ r に所属 }, r ∈ R：グループ r に所属するナースに対応するナー
ス番号の集合．
arjk , r ∈ R, j ∈ N, k ∈ W : j 日のシフト k に対するグループ r からの人数の下限値．
brjk , r ∈ R, j ∈ N, k ∈ W : j 日のシフト k に対するグループ r からの人数の上限値．
Pi : ナース i の実行可能スケジュールの集合．ナース i の実行可能スケジュール．
p ∈ Pi は δipjk（ナース i のスケジュール p において j 日の勤務がシフト k なら 1，そうでなければ 0）を要素とするベクトル (δip10 , . . . , δipjk , . . . , δipnw ) で表現される．
α−rjk , r ∈ R, j ∈ N, k ∈ W : j 日のシフト k に対するグループ r からの人数が下限値 arjk を下回る数を表す変数．
α+rjk , r ∈ R, j ∈ N, k ∈ W : j 日のシフト k に対するグループ r からの人数が上限値 brjk を上回る数を表す変数．
定式化 1

(2.1)

minimize r∈R j∈N k∈W

−
+
+
(wrjk
α−
rjk + wrjk αrjk )ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現

83

subject to(2.2)

arjk − α−
rjk ≤

 

δipjk λip ≤ brjk + α+
rjk ,r ∈ R, j ∈ N, k ∈ Wi∈Gr p∈Pi

(2.3)



λip = 1,

i∈M

p∈Pi

(2.4)
(2.5)

λip = 0 or 1,+α−rjk ，αrjk ≥ 0,i ∈ M, p ∈ Pir ∈ R, j ∈ N, k ∈ W−+
ここで，目的関数（2.1）式の wrjkと wrjkは，人数の過不足に対する重み付けであり，過不足数−+
αrjk , αrjk を（2.2）式で規定している．
（2.3）式は，各ナースの各週にパターンをちょうど 1 つ選
ぶ制約である．
各ナースの実行可能スケジュール集合 Pi の要素数は数 100 万と考えられ，陽的に列挙したり保持することは現実的ではないことから，列生成の仕組みを持つアルゴリズムを意識した定式化といえる．

3. ナース・スケジューリングの部分問題

部分問題軸アプローチでは，1 ナースの最適スケジュールを得る問題を部分問題としている．
与えられた試行解（勤務表）に対し，他のナースのスケジュールを固定した下で，対象ナースのナース制約を満たしつつ「シフト制約を違反する度合い」を最小化する問題として定義している．
そして，イテレーション毎にナース人数分の部分問題を解いて，目的関数値が最も小さくなった部分問題の解を次の試行解に採用することを，局所探索法やそれに基づく探索法（タブ探索など）の仕組みを使って繰り返し，全体の解を改善していく．
Ikegami and Niwa（2003）は， 3 交替制ナース・スケジューリング問題の部分問題を解くために列挙可能な程度の長さの実行可能部分スケジュール（例えば，長さ 7 日であれば高々1000 種類）をあらかじめ用意し，分枝限定法を利用してそれらを組み合わせることにより，質の良い解を与えた．ナース 25 名の問題（Ikegami-3shift-DATA1）については，病院現場で作成された勤務表が 39 のシフト制約と 71 のナース制約を満たしてなかったことに対し，6 つのシフト制
約のみ満たさない勤務表を与えたと報告している．また，その後の Métivier et al.（2009）の論文が，同データにおいて 63 のシフト制約を満たしていないことを考えると，アルゴリズム的にも優れていることがわかる．
一方，Ikegami and Niwa（2003）では，この問題例を解くのに 100 時間（Pentium II，266MHz）を要しており，実行時間が長くなるという問題を抱えると同時に，部分問題における実行可能
解空間を把握するための情報も「実行可能部分スケジュール数」だけに留まっていた．
本論文でも，部分問題における実行可能部分スケジュール（以降，パターン）を基に解空間把握を試みるため，それに対応した新たな定式化を考える．パターンの長さは，隣接する期間のパターンが連結可能か否かでナース制約の（3）を考慮できるよう 7 日とする．これは，一般にナース制約（3）が対象にする日数が 7 日（1 週間）に収まるからである．
図 1 に，実行可能スケジュール例とそれを構成するパターンを示す．
例えば，深夜勤（n）の直後の準夜勤（e）や深夜勤直後 2 日間の日勤（-）が禁止されていた場合，
1 つめのパターンの直後に，3 つめや 4 つめのパターンを連続して行うことは不可能である．

統計数理

84

図 1.

第 61 巻

第 1 号 2013

実行可能スケジュール例とそれを構成する実行可能部分スケジュール（パターン）．

図 2.

短すぎるパターンの例．

一方，制約条件に比べてパターンの長さが短すぎると，対象とする 2 つのパターンを同時に採用できるかは，さらに前後のパターンの情報がないと判定できない．図 2 に示すパターンは，
短すぎて連続する 2 パターン間だけでは条件を満たすか判定できない例である．
1 週間に 1 回は休み（/）が入る（休みの間隔日数の上限が 6）といった条件があった場合，パ
ターン a1 の後にパターン b を連続できるかどうかは，その後のパターンがどのようなものであるかによって異なる．具体的には，パターン c1 であるなら可能だが，パターン c2 であるな
ら不可能である．同様に，パターン b の後にパターン c2 を連続できるかどうかは，その前のパターンがどのようなものであるかによって異なる．
これに対し，ナース制約（3）の対象日数の最大値を n̂ とすると，パターン長が n̂ − 1 以上であれば図 2 に示した状況が発生しないため，隣接期間のパターン間だけで判定できる（ただし，後方に隣接期間のない最終期間に関しては n̂ − 1 以上である必要はない）．
以下に，適正な長さのパターンを利用した場合の定式化を示す．
スケジュール期間内の週の数を q ，h 週に含まれる日の集合を Nh = {j1 , . . . , jnh }，ナースi の h 週のパターンの集合を Pih とし，各パターン p ∈ Pih を δihpjk （ナース i の h 週のパ
ターン p において j 日の勤務がシフト k なら 1，そうでなければ 0）を要素とするベクトル(δihpj1 0 , . . . , δihpjk , . . . , δihpjnhw ) で表現する．また，1 つのパターン p に対する各シフトの数をρihpk =
δihpjk とし，ナース i の 1ヶ月におけるシフト k の勤務回数の下限と上限をそj∈Nh

れぞれ cik , dik , k ∈ W とする．さらに，ナース i の h 週のパターン p と翌週のパターン p の間
の連結可能性を θihpp（可能なら1，そうでなければ 0）で表すことにする．意思決定変数として
は，ナース i の h 週のパターン p を採用するか否かを 1 と 0 で表す λihp を利用する．
定式化 2

(3.1)

Minimizeq r∈G h=1 j∈Nh k∈W

−
+
+
(wrjk
α−
rjk + wrjk αrjk )ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現

85

subject toarjk − α−
rjk ≤

(3.2)

 

δihpjk λihp ≤ brjk + α+rjk ,i∈Gr p∈Pihr ∈ R, h = 1, . . . , q, j ∈ Nh , k ∈ W
 
q

cik ≤

(3.3)

ρihpk λihp ≤ dik ,i ∈ M, k ∈ W

h=1 p∈Pih(3.4)

i ∈ M, h = 1, . . . , q − 1, p ∈ Pih ，p ∈ Pi·h+1λihp + λi·h+1·p ≤ 1 + θihpp ,


(3.5)

λihp = 1,i ∈ M, h = 1, . . . , q

p∈Pih

(3.6)

i ∈ M, h = 1, . . . , q, p ∈ Pih

λihp = 0 or 1,

α−
α+
rjk ，
rjk ≥ 0,(3.7)

r ∈ R, j ∈ N, k ∈ W（3.1），（3.2），（3.5）式は，それぞれ，定式化 1 の（2.1），（2.2），（2.3）式に対応する．
（3.3）式と（3.4）式は，実行可能スケジュールを実行可能部分スケジュール（パターン）に分割したことで考慮できなくなったナース制約（1）と（3）にそれぞれ対応する．
定式化 2 における部分問題をシンプルに示すため，与えられた試行解でナース i 以外のスケ
ジュールを固定した場合のナース i の h 週のパターン p のコスト fihp を以下のように求めて
おく．




 

−
fihp =
max 0, wrjk
δi hp jk λi hp ，arjk − gir δihpjk −i ∈Gr ,i =i p ∈Pi hj∈Nh k∈W r∈G



+
wrjk

gir δihpjk +







δi hp jk λi hp − brjki ∈Gr ,i =i p ∈Pi h

ここで，gir は，ナース i がグループ r のメンバーであれば 1，そうでなければ 0 である値とする（gir = |Gr ∩ {i}|）．
部分問題 i（ナース i）の定式化(3.8)

Minimizeqfihp λihp

h=1 p∈Pihsubject to
(3.9)

cik ≤

q



ρihpk λihp ≤ dik ,k∈W

h=1 p∈Pih(3.10)(3.11)

λihp + λi·h+1·p ≤ 1 + θihpp ,h = 1, . . . , q − 1, p ∈ Pih , p ∈ Pi·h+1λihp = 1,

h = 1, . . . , qp∈Pih(3.12)

λihp = 0 or 1,

h = 1, . . . , q, p ∈ Pih

86

統計数理

第 61 巻

第 1 号 2013

本論文では，この部分問題における実行可能解（実行可能スケジュール）を把握することに焦点を絞る．
4. 動的計画法に基づくネットワーク

前節の部分問題の定式化では，パターンの長さを 1 週間と設定することにより，すべての実「勤務間隔日数」
行可能パターン列挙を容易にすると同時に，ナース制約（3）の「連続勤務回数」「禁止されるシフト並び」といった局所的だが扱い難い条件を，隣接するパターンを参照するだ
けで考慮できる利点がある．
1 週間分の実行可能パターンは，Ikegami and Niwa（2003）の 3 交替制勤務表作成データ（Ikegami-3shift-DATA1）においても 1 ナースの 1 週について数 100（高々1000）程度である．それらのパターンが連結可能か否かも容易にチェックすることができ，θihpp , h = 1, . . . , q − 1,
p ∈ Pih , p ∈ Pi·h+1 をあらかじめマトリックス等に保持しておくことが可能である．
この問題を解くにあたって，2 つの方針が考えられる．1 つ目は，
（3.9）式を緩和した最短路問題を利用する方法であり，2 つ目は，部分問題を直接動的計画法で解く方法である．それぞれを 4.1 節と 4.2 節に示す．
4.1 部分問題の緩和問題
各週のパターンをノードとし，h 週のパターン p と h + 1 週のパターン p に対し，θihpp = 1
であるならアークを設定する．ソースノード s とシンクノード t を加え，すべてのノードを含む集合を V とする．ソースノードから 1 週目のすべてのノード p ∈ Pi1 の間にアークを設定し，q 週目のすべてのノード p ∈ Piq からシンクノードの間にアークを設定する．そして，
これらすべてのアークの集合を A とする．さらに，h 週のノード p に入るアークのコスト
fp p , (p , p) ∈ A, p ∈ V, p ∈ Pih を fihp の値と同じにし，シンクノードの入るアークのコストを 0(fpt = 0) とする．このように構成されたグラフ G = (V, A) 上で最短路問題（Dijkstra, 1959）を解くことを考える．
この最短路問題を解いて得られた解（1ヶ月分のスケジュール）は， 1ヶ月を通した「シフトや休みの回数に関する条件（ナース制約（1））」以外の条件を満たした下での最適解である．よって，
局所的には実行可能であっても，ナース制約（1）を満たしていない可能性があるので，この緩和解を直接利用するわけにはいかない．
そこで，この最短路問題に利用したネットワーク上でソースノードからシンクノードまでの経路を「上位から（3.9）式を満たす解が得られるまで列挙すること」に対応する k 最短路問題を解く．k 最短路問題は，距離の短い方から上位 k 本の経路を探索する問題であり，MPS 法（Martins et al., 1998）等，高速なアルゴリズムも知られている． k 最短路アルゴリズムの終了
条件は「上位 k 番目までの保証ある良解が得られる」だが，この終了条件を「（3.9）式を満たす解が得られる」に修正すればよい．
4.2 動的計画法に基づくネットワークの構築
次に，部分問題を直接動的計画法で解くことを考える．本論文では，部分問題における良解の列挙も行うため，実行可能解を得るにも列挙を必要とする 4.1 節の方法より 1 経路を見つけるだけで実行可能解を得るこちらの方法に重点を置く．
先ず，ナース i の h 週のパターンが p，h 週までのシフト k ∈ W の累積回数が eihk に固定された下で「h 週の子問題」を以下のように表してみる．

ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現87

h 週のパターンと累積回数が固定された下での h 週の子問題(4.1)

gh∗ (p, eihk , k ∈ W ) = min

h−1




fih p λih ph =1 p ∈Nh

subject to
(4.2)

h−1




ρih p k λih p = eihk − ρihpk ,k∈Wh =1 p ∈Pih(4.3)

λih p + λi·h +1·p ≤ 1 + θih p p ,h = 1, . . . , h − 2, p ∈ Pih , p ∈ Pi·h +1

λi·h−1·p ≤ θi·h−1·p p ,

(4.4)



(4.5)

p ∈ Pi·h−1h = 1, . . . , h − 1λih p = 1,p ∈Pih(4.6)

λih p = 0 or 1,h = 1, . . . , h − 1, p ∈ Pih

従って，gh∗ (p, eihk , k ∈ W ) は，1 < h ≤ q ，p ∈ Pih ，任意の eihk , k ∈ W に関して，(4.7)

gh∗ (p, eihk , k ∈ W ) = ∗{gh−1(p , eihk − ρihpk , k ∈ W ) + fi·h−1·p }minp ∈Pi·h−1 ,θi·h−1·p p =1

h = 1 の p ∈ Pi1 (ei1k = ρi1pk , k ∈ W ) に関して，g1∗ (p, ei1k , k ∈ W ) = 0(4.8)と表現できる．
さらに，累積回数 eihk , k ∈ W のみ固定された h 週までの問題の最適値は，(4.9)

min {gh∗ (p, eihk , k ∈ W ) + fihp }p∈Pihとなり，元の部分問題は，以下のように表すことができる．
(4.10)minmin {gq∗ (p, eiqk , k ∈ W ) + fiqp }cik ≤eiqk ≤dik ,k∈W p∈Piq

この問題記述に従って，動的計画法が利用できるネットワーク構築を考える．ネットワーク
を利用する理由は，実行可能スケジュールの構成要素になりえない p ∈ Pih と eihk , k ∈ W の値の組合せが存在することを意識し，gh∗ (p, eihk , k ∈ W ) のための無駄な計算を回避したいからである．
そこで，ネットワークを構成するノードは，各週 h の「パターン p と累積回数 eihk , k ∈ W 」（以降，p, eihk と記述する）に対応させ，ソースノードとシンクノードを加える．ソースノード
からは 1 週目のノード p, ei1k (êi1k = ρi1pk , k ∈ W ) すべてにアークを設定する（1 週目の実行可能パターンは，前月の勤務からの並びも考慮して実行可能なものとする）．シンクノードへは，
cik ≤ eiqk ≤ dik , k ∈ W を満たす q 週のノード p, eiqk からアークを設定する．さらに，h 週のノード
p, eihk から h + 1 週のノード p , ei·h+1·k へは，θihpp = 1，かつ，eihk = ei·h+1·k − ρi·h+1·p k , k ∈ Wが成り立つ場合のみアークを設定する．
従って，できあがったネットワーク上のソースノードがらシンクノードまでのすべての経路
が対象部分問題の実行可能解になるとともに，すべての実行可能解が経路としてこのネット

統計数理

88

第 61 巻

第 1 号 2013

ワークに含まれることになる．さらに，p, eihk に入るアークに fihp をコストとして設定すれば，
ソースノードがらシンクノードまでの最短路は，部分問題における最適解となり，与えられた
勤務表に対し（他のナースのスケジュールは固定した下で），シフトの勤務人数の過不足を最も少なくするような対象ナースのスケジュールを与えることになる．
eihk , k ∈ W の値によっては，前後の週にアークが設定されない場合があるので，ソースノードからの経路やシンクノードへの経路が存在しないノードやアークは対象としない工夫が必要である．例えば，h 週において，以下の条件を満たす eihk を 1 つでも含んでいたら明らかに経路が存在しないノードである．
eihk <hh =1eihk +qh =h+1

min ρih pk ,p∈Pih

min ρih pk > dik ,p∈Pih

eihk >hh =1eihk +

max ρih pk

p∈Pihqh =h+1

max ρih pk < cikp∈Pih

5. ネットワークの構築（4.2）節では，定式化を利用してネットワークの構造を説明したが，ここでは，構築方法についてさらに詳しく述べておく．その理由としては，ネットワークを構成するノード数やアーク数が膨大なため，効率の悪い構築方法を採用すると非常に時間がかかってしまうからである．
例えば，ノードの実行可能性を判定して生成しながら構築する方法では，翌週のノードを生成する際に無駄な列挙と判定が必要となり，1 ナースのネットワークの構築だけでも（利用コン
ピュータにも依存するものの）数時間から数 10 時間を要し，高速に部分問題の解を得たり，解を把握するという目的と相反する．対象月の勤務表作成において，部分問題のネットワークは，
ナース毎に 1 回構築してしまえば，作り直すことなく何度でも利用できるが，できる限り高速に構築できることが望ましいと考え，現時点では数 10 秒程度で構築することを目指す．そこ
で，本研究では，シフトの回数だけに着目した圧縮ネットワークを初めに構築し，その後で，実行可能パターンに対応するノードを持つネットワークに拡張することを考える．
具体的には，ρihpk , k ∈ W と eihk , k ∈ W のそれぞれの値がすべて等しいノードセットを，1つのノード ρ̂ihk , eihk にまとめたネットワークを考え，h + 1 週のノード ρ̂i·h+1·k , ei·h+1·k へは，eihk = ei·h+1·k − ρ̂i·h+1·k が成り立つ場合のみアークを設定する．ソースノードからは 1 週目のすべてのノードにアークを設定し，シンクノードへは，q 週の eiqk が，cik ≤ eiqk ≤ dik , k ∈ Wとなるノードからのみアークを設定する．こうすることにより，ソースノードからシンクノードへの経路は，週を重ねるごとに各シフトに対する勤務累積数を増やしていく推移の可能性を表すと同時に，実行可能な勤務累積数の推移のすべてがこのネットワークの経路として含まれることになる．
別の考え方をすると，1 つのノード ρ̂ihk , eihk には，ρihpk = ρ̂ihk , k ∈ W となる実行可能パターン
p がすべて含まれているので，このノードに入るアークのコストを min{fihp |ρihpk = ρ̂ihk , k ∈ W }と設定すれば，このネットワーク上で最短路を求める問題は，部分問題の定式化の（3.10）式を緩和した問題を解くことになる．本論文では，この圧縮ネットワークのことをシフト回数推移
ネットワークとよぶことにする．
3 交替制勤務表作成データ（Ikegami-3shift-DATA1）を対象に，シフト回数推移ネットワークを構築した（Ikegami-3shift-DATA1 ではセミナの連続勤務数や間隔日数の制約について考慮する必要がなかったため，本論文ではセミナを日勤扱いして考慮することにした）．25 名のナースにおいて，シフトの勤務回数の上下限が大きく異なる 2 名のナースを除けば，ほぼ同じ大ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現
表 2.

3 交替データ（3shift-DATA1）の実行可能パターン（7 日）ネットワークのサイズ．

図 3.

3 交替データ（3shift-DATA1）の実行可能パターン（7 日）ネットワークのサイズ．

89

きさのシフト回数推移ネットワークが構築できた．平均ノード数は 19,793（最小 2,662，最大
23,894），平均アーク数は 327,088（最小 16,966，最大 406,846）であった．ノード数，アーク数
ともに最小となったナースは深夜勤をちょうど 2 回勤務するという条件があり，他のナースの勤務回数上下限の幅や数値が大きく設定されているのに比べて条件がタイトになっていた．
シフト回数推移ネットワークが構築されたら，各ノードを対応する p, eihk に展開し，アークが設定されていた 2 つのノードがそれぞれ含む p, eihk と p , ei·h+1·k が，θhpp = 1 だったならば，
新しいネットワークにもアークを設定する．このようにノードを置き換える（展開する）ことにより，目指していたネットワークを構築することができる．完成したネットワークを実行可能
パターンネットワークとよぶことにする．
前述のデータ（Ikegami-3shift-DATA1）においては，ナース毎に，休み希望やセミナ等の予定が異なることから，実行可能パターンネットワークのサイズも大きなばらつきがあった．表 2に，それぞれのナースに対する部分問題の実行可能パターンネットワークのサイズ（ノード数とアーク数），図 3 にそのグラフを示す．平均ノード数は，22,468（最小 3,234，最大 62,574），
平均アーク数は，885,749（最小 22,816，最大 4,185,872）であった．

統計数理

90

第 61 巻

第 1 号 2013

表 3.

3 交替データ（3shift-DATA1）の実行可能（6 日）パターンネットワークのサイズ．

図 4.

3 交替データ（3shift-DATA1）の実行可能パターン（6 日）ネットワークのサイズ．

このデータでは，ナース制約（3）が対象とする日数の最大が 7 日だったため，パターンの長さは 6 日でも可能である．表 3 と図 4 に示したパターン長を 6 にした場合のネットワークサ
イズを観察すると，そのサイズが小さくなっていることがわかる．これは，パターンの数が長さの階乗のオーダで増えるからだと考えられるが，スケジューリング期間をいくつ（n/7 やn/6）に分けたかにも依存する．この問題例では，パターン長 7 でも 6 でも 5 区間に分かれるが，最終区間の長さがそれぞれ 2 と 6 となり，4 区間までのパターン数が非常に小さい場合には，最終区間のノード数の影響を受けてパターン長 6 の方がサイズが大きくなる場合もあると考えられる．
これまでの研究では，1 ナースの実行可能スケジュールを全列挙したり，その空間がどの程度の大きさであるか把握することが不可能だった．これに対し，提案する実行可能パターンネッ
トワークは，各ナースの実行可能スケジュールを全列挙したのと同等な情報を持つことに成功できた．ネットワークのサイズの違いは，ソースノードからシンクノードへの経路の数の違い，
つまり実行可能スケジュール数の違いを正確に示すわけではないが，大きな依存関係は存在すると考えられる．よって，各ナースのスケジュールの自由度を大まかに捉えることができる．

ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現

91

ナース毎にネットワークのサイズが異なる理由は，ナース制約のパラメータの違いによる．例
えば，ナース 12 のネットワークサイズが非常に小さい理由は前にも簡単に述べたが，多くのナースが準夜勤を 4〜6 回，深夜勤を 2〜4 回もしくは 3〜6 回勤務できるのに対し，準夜勤，深夜勤ともちょうど 2 回勤務するというタイトな設定になっているからだと考えられる．また，休み希望や固定勤務が 5 日以上設定されているナース 2，4，13，14，19 のネットワークサイ
ズは比較的小さく，逆に，休み希望や固定勤務が全く設定されていないナース 1，25 のネット
ワークサイズは大きい傾向がみられる．
問題例にも依存するものの， 1 つのネットワークの構築には，20 秒 ∼ 30 秒程度を要し（Intel（R）Xeon（R）CPU E5335 Quad Core @2.00GHz, Memory 24G），構築アルゴリズムのデータ構
造や実装方法にさらなる工夫が必要だが，これまで知りえなかった情報を生み出すという意味
では，現時点では十分な速さと考える．
ここで提案した構築方法が効率よい理由としては，各週に列挙した高々1000 程度の実行可能パターンと，隣接する週のパターンとの連結可能性を初めに求めておくことにより，シフト回
数推移ネットワークが構築できた時点で，実質的には目指すネットワーク（実行可能パターン
ネットワーク）ができているからだと考える．なお，2 交替制のデータ（Ikegami-2shift-DATA1を緩和した問題：土日連休を 1 回確保する条件を緩和；ナース数 28）についても同様なネットワーク構築に成功している．
ここで利用した 3 交替制データ（Ikegami-3shift-DATA1）は，Ikegami and Niwa（2003）やベン
チマークサイト（University of Nottingham, 2006）で紹介され，多くの研究者に取り組まれてきた問題例である（Métivier et al., 2009）．
6. ネットワークの利用

実行可能パターンネットワークを構築したことで，個々のナースの実行可能スケジュールの空間を把握しやすくなり，各ナースに対する条件の緩和や追加による，実行可能スケジュール
集合の大きさや特徴の変化も把握できるようになった．
また，前述したように，実行可能パターンネットワークのアーク（ノード p, eihk に入るアーク）に h 週にパターン p を採用した場合の各シフトの人数過不足の度合いである fihp をコストとして設定すれば，ソースノードからシンクノードへの最短路は，部分問題における最適解に対応する．構築したネットワークにおいて，ある試行解（あるコスト設定）に対して最短路を得るための実行時間の平均は， 3 交替制データの 7 日パターンのネットワークでは 0.065 秒，
6 日パターンのネットワークでは 0.046 秒であった（Intel（R）Xeon（R）CPU E5335 Quad Core
@2.00GHz, Memory 24G）．この時間もデータ構造等の工夫により短縮が可能だと考える．
部分問題の最適解が最短路問題を解くことによって高速に得られれば，Ikegami and Niwa
（2003）のアルゴリズムの「部分問題を解く分枝限定法」をこれに置き換えることにより，全体の勤務表作成も可能になる．
一方，実行可能パターンネットワークのノード数とアーク数は膨大であり，実際にネットワー
クを表示して視覚的に把握することは難しい．しかし，本来，我々の興味は，その中で現在の勤務表を改善できる可能性のある優れたスケジュール群であると考えられる．そこで，実行可能パターンネットワークに含まれる良解のみを抽出し，それを構成するノードやアークを表示
して，良解空間を提供することを考える．具体的には，実行可能パターンネットワーク上で k
最短路を求め，最適スケジュールを 1 つ得るだけでなく複数の良解を得ることにより, 勤務表の改善案を提案することや, 各ナースにおける勤務変更の可能性把握を支援する．
実行可能パターンネットワーク上の k 最短路（k = 30）を求め，そこで採用されたノードとアー

92

統計数理

図 5.

第 61 巻

第 1 号 2013

k 最短路を構成するノードとアーク．

クで構成されるネットワークのイメージを図 5 に示す（ここでは，問題例のナース 20 のネット
ワークを対象に，便宜的に fihp の値をランダムに与えてコストとして設定した場合の結果を示した）．
ソースノードが前月末の 7 日分のスケジュールを表し，シンクノードが翌月のスケジュールを表す．その他のノードは，左側より 1 週目から 5 週目までの累積シフト回数情報を伴ったパ
ターン（回数情報は非表示）に対応する．ここでは，見やすさのため k = 30 としたが，k = 50，
100 でも高速にネットワークを得ることができる．
さらに，このように良解を含んだ縮小したネットワークを有効に利用すれば，探索空間は狭まり高速なスケジューリングも可能になると考える．

ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現

93

7. おわりに

本論文では，これまで実行可能解の空間の把握が困難だった問題に対し，部分問題の実行可能解のすべてをネットワーク表現することにより，全列挙したのと同等な解の把握を可能とするだけでなく，他のナースに対するスケジュールを固定した下での最適スケジュールや上位の好ましいスケジュールを高速に得る仕組みを構築した．また，このネットワークを利用して部分問題を解くことによる勤務表作成の概要を示した．
最適化技術においては，一般に，目的関数を一意に設定することが求められるが，ナース・スケジューリングをはじめとする，人間の活動が大きくシステムに関わっている問題においては，潜在的な評価尺度が複数存在する場合も多く，目的関数の設定は困難な課題となる．また，
数値化しにくい人間の満足度やバランス感覚の表現も数値演算を基本とする最適化技術では扱いにくい対象である．暫定的に設定した目的関数に対する最適解も，現実に利用されるためには，明示されていなかった制約や評価尺度に対して何らかの調整（修正）が必要となる．
一方，人間にとっての最適な解は 1 つでないと同時に，解を得るためのプロセスが重要であり，自らが作った最適な解であるという納得感が存在しない限り，現場で実際に利用されることはない（田辺 他, 2009）．納得感を実現するためには，最適化アルゴリズムが与えた最適解と，人間にとっては最適であり得たかもしれない解との関係をなんらかの形で提供する必要がある．ある条件の下，最適解とほぼ等しい評価値を持つ解が膨大に存在する場合もあれば，非常に特異な解である場合，さらには，その特異さが現実的には非常に好ましい場合もあれば，不自然な場合もあり得る．
意思決定における納得感を得るためには，選択された解の位置づけ（意味）の把握が重要であり，他に選択できる可能性やその意味を十分に理解し，修正の試行錯誤も含め，問題の解空間全体を把握するというプロセスが必要である．
本研究では，このプロセスを支援する数理的な仕組みの 1 つとして，ネットワーク構造を利用し，実行可能解空間を表現することに取り組み，その人間にとっての最適解を選択できる可能性を広げた．できあがったネットワークを人間にとって視覚的にも把握しやすいよう，意味のある部分に絞り込んで提供するなど，良解の分布に対する情報提供を可能にし，これまでの意思決定において，気づかなかった制約や評価尺度を意識できるようにするといった，人間の思考に調和する最適化，人間の暗黙知に対してロバスト性を持つ最適化の研究につながると考
える．
謝

辞

本論文に貴重なご助言を頂いた査読委員の先生方に心より感謝致します．本研究について議論を頂いた株式会社数理システムの田辺隆人氏，成蹊大学院生の山口淳史さん，井村亮介さんに心より感謝致します．本研究の一部は，文部科学省私立大学戦略的基盤形成支援事業研究費の成果，池上の統計数理研究所客員教授としての成果，政策研究大学院大学客員研究員としての成果を含んでいます．

参 考 文 献Arther, J. L. and Ravindran, A.（1981）. A multiple objective nurse scheduling model, AIIE Transactions, 13, 55–60.
Bell, P. C., Hay, G. and Liang, Y.（1986）. A visual interactive decision support system for workforce

94

統計数理

第 61 巻

第 1 号 2013

（nurse）scheduling, INFOR, 24, 134–145.
Burke, E. K., De Causmaecker, P., Berghe, G. V. and Landeghem, H. V.（2004）. The state of theart of nurse rostering, Journal of Scheduling, 7, 441–499.
Dijkstra, E. W.（1959）. A note on two problems in connection with graphs, Numeriche Mathematics,
1, 269–271.
Dowsland, K. A.（1998）. Nurse scheduling with tabu search and strategic oscillation, European Journal of Operational Research, 106, 393–407.
池上敦子（2005）. ナース・スケジューリング
調査・モデリング・アルゴリズム ，統計数理，53，
231–259．
池上敦子, 丹羽明（1998）. ナース・スケジューリングに有効なアプローチ：2 交替制アルゴリズムにおける実現, Journal of the Operations Research Society of Japan, 41, 572–586.
Ikegami, A. and Niwa, A.（2003）. A subproblem-centric model and approach to the nurse schedulingproblem, Mathematical Programming, 97, 517–541.
池上敦子, 丹羽明, 大倉元宏（1996）. 我が国におけるナース・スケジューリング問題，オペレーション
ズ・リサーチ, 41, 436–442.
乾伸雄，池上敦子（2010）. ナーススケジューリング問題における混合整数線形計画問題と充足性判定
問題による厳密解法の比較，オペレーションズ・リサーチ，55, 706–712.
Jaumard, B., Semet, F. and Vovor, T.（1998）. A generalized linear programming model for nurse
scheduling, European Journal of Operational Research, 107, 1–18.
Martins, E. Q. V., Pascoal, M. M. B. and Santos, J. L. E.（1998）. The k shortest paths problem,
Research Report, The University of Coimbra, Portugal.
Métivier, J., Boizumault, P. and Loudni, S. （2009）. Solving nurse rostering problems using soft
global constraints, Lecture Notes in Computer Science（Principles and Practice of Constraint
Programming ）， 5732, 73–87.
Millar, H.H. and Kiragu, M.（1998）. Cyclic and non-cyclic scheduling of 12 h shift nurses by network
programming, European Journal of Operational Research, 104, 582–592.
Miller, H. E., Pierskalla, W. P. and Rath, G. J.（1976）. Nurse scheduling using mathematical programming, Operations Research, 24, 857–870.
Nonobe, K. and Ibaraki, T.（1998）. A tabu search approach to the constraint satisfaction problem
as a general problem solver, European Journal of Operational Research, 106, 599–623.
田辺隆人，岩永二郎，多田明功，池上敦子（2009）. 「納得」を生み出すスケジューリングアルゴリズムとソフトウエア制約充足を超えて：実行可能領域の直観的把握, スケジューリング・シンポジウ
ム 2009, 169–173，岡山．
University of Nottingham（2006）. Personnel Scheduling Data Sets and Bench-marks, http://www.cs.
nott.ac.uk/tec/NRP/.
Warner, D. M.（1976）. Scheduling nursing personnel according to nursing preference: A mathematicalprogramming approach, Operations Research, 24, 842–856.

Proceedings of the Institute of Statistical Mathematics Vol. 61, No. 1, 79–95 (2013)95

A Network Representation of Feasible Solution Space
for a Subproblem of Nurse Scheduling
Hiroki Akita and Atsuko Ikegami
Faculty of Science and Technology, Seikei University

This paper deals with the nurse scheduling problem. When making a roster for nurses
in a hospital, a scheduler has to assign the required number of nurses with speciﬁed skill
levels to each shift while balancing the workload among the nurses. This problem is known
to be diﬃcult to solve using computers, because it is impossible to explicitly describe allof considerations. This paper describes a system for enumerating good solutions and atool for clarifying the space of feasible solutions in order to help the scheduler’s decision.
First we focus on a subproblem to ﬁnd the optimal schedule or feasible schedules for anurse. We then construct a network in which any path from the source node to the sinknode represents a feasible schedule and all the schedules are included. Given that theother nurses’ schedules are ﬁxed, we can obtain the optimal and other good schedules
for each nurse eﬃciently by ﬁnding the shortest path and the k-shortest paths on thecorresponding network. We also show how to construct the network for a nurse andfeatures of the networks generated for all nurses. Though further studies are needed toreduce the size of the networks in terms of the numbers of nodes and arcs, it will be madeclear that they can be of tremendous help in scheduling nurses eﬃciently.

Key words: Nurse scheduling, search space, visualization, network representation, dynamic programming.