sig sai 2010 12 04 04 Recent site activity jsaisigsai

Differential Evolution を用いたナーススケジューリング

串田淳一

_, 大場和久

_, 亀井且有

_,

立命館大学情報理工学部^†_, 日本福祉大学健康科学部^††_, 1 は じ め に

ナーススケジューリング問題（Nursing Scheduling Problem: NSP）は ，病 院 に 勤 務 す る 病 棟 看 護 師 一ヶ月 の 勤 務 表 を 様々な 制 約 の 下 で 作 成 す る 問 題 で あ る ．勤 務 表 作 成 は 多 く の 制 約 条 件 や 看 護 師 か ら の 要 望 を 考 慮 し て 作 成 す る た め ，手 作 業 に よ る 作 成 が 困 難 で あ る ．そ の た め ，作 成 に は 多 大 な 労 力 と 時 間 を 費 や し て お り，作 成 者 に とっ て 大 き な 負 担 と なって い る ．こ の よ う な 背 景 か ら 自 動 化 に 対 す る ニ ー ズ が 高 く，こ れ ま で に 様々 な_NSPの 研 究 が 行 わ れ て い る^{1, 2)} ．

NSPに お い て は ，こ れ ま で に 遺 伝 的 ア ル ゴ リ ズ ム（Genetic Algorithm: GA）に 代 表 さ れ る 進 化 的 計 算 手 法 を 用 い た 解 法 が 成 果 を 挙 げ て い る ． GA^{に よって}NSPを 解 決 す る 場 合 ，一 般 的 に は GAの 各 個 体 に 様々な 勤 務 シ フ ト を 符 号 化 し ，そ れ ら を 交 叉 や 突 然 変 異 に よって 進 化 さ せ つ つ 最 適 解 を 探 索 し て い く．そ の 際 ，勤 務 シ フ ト 作 成 に 必 要 な ル ー ル は「 制 約 」，で き る だ け 実 現 さ せ た い 要 望 は「 評 価 関 数 」と し て 表 現 さ れ ．こ れ ら を 基 準 に 各 個 体 を 評 価 す る³⁾ ．

一 方 ，近 年 で は 進 化 計 算 の 分 野 に お い て_GA に 変 わ る 新 た な 最 適 化 手 法 と し て ，Differential Evolution (DE)が 注 目 さ れ て い る ，_DEは 実 数 値 最 適 化 問 題 を 対 象 と し た 探 索 手 法 で あ り，個 体 間 の 差 分 を 利 用 す る 差 分 操 作 に よ り 探 索 を 行 う．_DEは 制 御 パ ラ メ ー タ の 数 が 少 な く 設 定 が 容 易 で あ り，主 に 連 続 変 数 最 適 化 の 分 野 で ，有 効 性 の 検 証 が 確 認 さ れ て い る^{4, 5)} ．本 論 文 で は ， Differential Evolution(DE)^をNSPに 適 用 し ，勤 務 表 作 成 者 で あ る 看 護 師 長 の 要 求 を 満 た す 勤 務 表 を 作 成 す る 手 法 を 提 案 す る ．提 案 手 法 で は 順 序 An approach to Nurse Scheduling Problem with Dif- ferential Evolution

† Jun-ichi KUSHIDA

†† Kazuhisa OBA

† Katsuari KAMEI

College of Information Science and Engineering, Ritsumeikan University (†)

Faculty of Health Sciences,Nihon Fukushi University (††)

表 現 を 用 い た コ ー ディン グ 方 法 に よ り 解 を 整 数 値 列 で 表 現 し ，差 分 操 作 に よ り 個 体 集 団 を 進 化 さ せ る ．最 後 に ，数 値 実 験 を 行 い 提 案 手 法 の 実 用 性 を 評 価 す る ．

2 DEの ア ル ゴ リ ズ ム

DE^{で は}DE/base/num pair/crossの よ う に 表 記 し ，そ の 特 徴 を 示 す．_baseは 差 分 操 作 時 の 基 本 個 体 の 選 び 方 ，_{num pair}は 差 分 の 際 に 選 ば れ る 個 体 対 の 数 ，_crossは 交 叉 方 法 で ，DE/rand/1/bin の よ う に 表 記 す る ．DE/rand/1/bin^{は ，}DE^{で あ} る こ と ，差 分 変 位 親 個 体 を 作 る 際 に 元 と な る 基 本 個 体 を ラ ン ダ ム に 選 ぶ こ と ，差 分 を 取 る 際 に 選 ば れ る 個 体 対 が₁で あ る こ と ，交 叉 方 法 が 一 様 交 叉 で あ る こ と を 示 す．

以 下 に ，_ND次 元 の 実 数 値 空 間 ，_NP個 の 個 体 x_i(i = 1, 2, . . . , N_P)を 与 え た 場 合 の ，個 体 の 選 び 方 が ラ ン ダ ム ，差 分 を 取 る 際 に 選 ば れ る 個 体 対 が₁，交 叉 の 長 さ の 決 定 方 法 が 指 数 的 な 二 点 交 叉 で あ るDE/rand/1/expア ル ゴ リ ズ ム を 示 す． (S1) N_P個 の 個 体 を ，各 次 元 の 定 義 域 に お い て

ラ ン ダ ム に 生 成 し て 世 代_{g = 1}と す る ．ま た ， 最終世代，収束の条件を終了条件に設定する． (S2) 各 個 体 の 関 数 値 を 計 算 す る ．

(S3) 差 分 変 位 親 個 体v_iを 生 成 す る ．

(S3-1) ^{対 象 親 個 体x}i^{と は 異 な る}3^{個 体x}P1,i^，

x_P2,i，x_P3,iを 同 じ 個 体 が 重 な ら な い よ う に ラ ン ダ ム で 選 択 ．

(S3-2) ^式(1)に よって 差 分 変 位 親 個 体v_iを 生 成 す る ．こ こ で_Sは 差 分 の 伸 縮 を 表 す ス ケ ー リ ン グ ファク タ で あ る ．式₍₁₎よ り_Sの 値 が 大 き い ほ ど 差 分 変 位 親 個 体 に 対 す る 差 分 の 影 響 が 大 き く 現 れ る ．

v_{i= xP}

1,i^{+ S(x}P2,i^{− x}P3,i^{) (1)}

v12

v11

v10

v9

v8

v7

v6

v5

v4

v3

v2

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12

v1

u12

u11

u10

u9

u8

u7

u6

u5

u4

u3

u2

u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12

u1

v

u

x12

x11

x10

x9

x8

x7

x6

x5

x4

x3

x2

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12

x1

x

Start point

CR

rand_j≤ randj>CR

Fig. 1 DE^{の 二 点 交 叉}

(S4) 両 親 の 交 叉 に よって 子 個 体u_iを 生 成 す る ． 最 初 に 交 叉 の 始 点 を 決 め る ．次 に ，繰 り 返 し 発 生 さ せ た₀か ら₁の 大 き さ の 乱 数 が 連 続 で 交 叉 率_CR以 下 で あ る 回 数 を_lと し て ，始 点 を 含 め ず_l個 目 ま で の 要 素 を 交 叉 に よ り 交 換 す る ．こ の と き ，第_ND要 素 が_l個 の 中 に 含 ま れ た 場 合 は ，第₁要 素 に 戻って 同 様 の 操 作 を 続 け る ．子 個 体 の 成 分 と し て ，始 点 を 含 め て_{(l + 1)}個 の 差 分 変 位 親 個 体v_iの 成 分 が 用 い ら れ ，そ れ 以 外 の_{(ND− (l + 1))}個 の 成 分 は 対 象 親 個 体x_iの 成 分 が 用 い ら れ る（₁）．_CR の 値 が 大 き い ほ ど 子 個 体 の 成 分 に 差 分 変 位 親 個 体 の 成 分 が 使 用 さ れ る 割 合 が 多 く な る ． (S5) ^{対 象 親 個 体x}i^{と 子 個 体u}iの 関 数 値 を 比 較

し ，良 い 方 を 次 世 代 のx_iと し て 残 す． (S6) 終 了 条 件 を 満 た し て い な け れ ば ，_{g = g + 1}

と し て_(S3)に 戻 る ．

3 ナ ー ス ス ケ ジュー リ ン グ 問 題 3.1 NSP^{の 定 式 化}

NSPは 表 を 使った ス ケ ジュー リ ン グ 問 題 で ，人 数_m，日 数_nと し た と き ，勤 務 形 態 を 要 素 と す る m^× n行 列 を 決 定 す る 問 題 で あ る ．作 成 者 の 要 求 を 満 た す 勤 務 表 を 作 成 す る た め に は ，重 要 度 の 異 な る 様々な 制 約 を 考 慮 す る 必 要 が あ る ．本 稿 で は ，₃交 替 制₍日 勤 ，準 夜 勤 ，深 夜 勤₎の 勤 務 表 作 成 問 題 で 用 い ら れ る 制 約 条 件 を 整 理 し ，評 価 項 目 の 定 式 化 を 行 う⁶⁾ ．

以 下 に 定 式 化 で 用 い る 集 合 を 示 す．ま た ，各 評 価 項 目 の 評 価 関 数 を ，そ れ ぞ れ_F1，_F2，_F3，_F4， F5^，F6^，F7^{と す る ．}

M = {i | i ∈ (nurse1, nurse2, . . . , nursem)} (2) D = {j | j ∈ (1, 2, . . . , n)} (3) W = {k | k ∈ (work1, work2, . . . , workw)} (4) G = {g | g ∈ (group1, group2, . . . , groupq)} (5) P = {(k_l¹, . . . , k_l^h) | k¹_l, . . . , k^h_l ∈ W ，

l ∈ (1, 2, . . . , p)，h ∈ (2, 3, . . . , n)} (6)

こ こ で ，_Mは ス ケ ジュー ル 対 象 と な る 看 護 師 の 集 合 ，_Dは ス ケ ジュー ル 対 象 と な る 日 の 集 合 ， Wは 勤 務 形 態 の 集 合 を 表 し ，_mは 総 看 護 師 数 ，_n は₁ヶ月 の 日 数 ，_wは と り 得 る 勤 務 形 態 の 総 数 で あ る ．ま た ，_Gは グ ル ー プ の 集 合 を 表 し ，_qは グ ル ー プ の 総 数 で あ る ．グ ル ー プ と は ス キ ル レ ベ ル や 業 務 上 の 所 属 チ ー ム ご と で 構 成 さ れ る 看 護 師 の グ ル ー プ を 指 す．ま た ，_Pは 禁 止 パ タ ー ン の 集 合 を 表 し ，そ の 要 素 で あ る 勤 務 形 態_k¹

l^{,. . . ,kh}l

は ，_l番 目 の 禁 止 パ タ ー ン を 表 す．_pは 禁 止 パ タ ー ン の 総 数 で あ る ．こ の 他 に ，グ ル ー プ_gに 所 属 す る 看 護 師 の 集 合 を_Mg，_j日 に 勤 務 形 態_kを 行 い グ ル ー プ_gに 所 属 す る 看 護 師 の 集 合 を_Mg,j^k と す る ． ま た ，_x^k_i,jを 看 護 師_iの_j日 が 勤 務 形 態_kの と き に ， 1，そ う で な い と き ，₀を と る_0-1変 数 と す る ．

(1)勤 務 パ タ ー ン 負 荷 の 軽 減

  勤 務 パ タ ー ン と は ，看 護 師 一 人 に 注 目 し た と き ，「 日 勤・深 夜 勤 」，「 深 夜 勤・準 夜 勤・休 日 」の よ う に 複 数 日 に わ た る 勤 務 形 態 の 系 列 を い う． 勤 務 パ タ ー ン の 評 価 は ，隔 たった 日 の 間 の 依 存 関 係 が 低 く，連 続₃日 程 度 で 十 分 評 価 で き る ．そ こ で ，₃日 間 の 全 勤 務 パ タ ー ン₆₄通 り を ，_{Table 1} に 示 す よ う に ，₄種 類 に 分 類 す る ．_α，_β，_γは ， 評 価 の 重 要 度 を 表 す 重 み パ ラ メ ー タ で あ る（ た だ し ，0 < α < β < γ < ^∞）．し た がって ，評 価 関 数_F1は 式₍₇₎で 与 え る ．

F₁ =^∑

i∈M

∑

j∈D

a_i,j (7)

こ こ で ，_ai,jは 看 護 師_iに お け る_j日 の 勤 務 パ タ ー ン 評 価 値 を 表 し ，評 価 は 当 日 と 前 日 ，前々日 の 勤 務 パ タ ー ン で 評 価 す る ．

(2)禁 止 パ タ ー ン の 低 減

  こ こ で は ，評 価 項 目₍₁₎で 考 慮 で き な い 禁 止 パ タ ー ン を 低 減 す る こ と を 目 的 と し て い る ．禁 止 パ タ ー ン の 例 と し て ，「 土 日 祝 の 日 勤 の 翌 日 の 深

Table 1 勤 務 パ タ ー ン の 例

パ タ ー ン タ イ プ 評 価 値_ai,j 例

最 優 先 パ タ ー ン ₀ 「 日 深 準 」「 準 休 休 」 優 先 パ タ ー ン _α 「 準 休 日 」「 休 日 深 」 妥 協 パ タ ー ン _β 「 日 準 準 」「 日 休 準 」 抑 止 パ タ ー ン _γ 「 休 休 深 」「 準 日 休 」

夜 勤 は 禁 止 」，「 研 修 の 翌 日 の 深 夜 勤 は 禁 止 」，「 土 日 祝 の 連 続 日 勤 は 禁 止 」，「 希 望 休 日 の 前 日 の 準 夜 勤 は 禁 止 」等 が あ る ．そ こ で ，そ れ ぞ れ の 制 約 条 件 に お い て ，各 看 護 師 の₁ヶ月 の ス ケ ジュー ル 内 に 禁 止 パ タ ー ン が 割 り 付 け ら れ て い る 回 数 を ペ ナ ル ティと し て 課 す．し た がって ，評 価 関 数 F₂^{は 式}(8)^{で 与 え る ．}

F2=^∑

i∈M

∑

(k¹_l,...,k^h_l)∈P n−h+1_∑

j=1

max{

∑h ϵ=1

x^k_i,j+ϵ−1^ϵl

−(h − 1), 0} (8)

(3)必 要 日 数 の 確 保

  必 要 日 数 と は ，個 人 が 一ヶ月 に 各 勤 務 形 態 を 行 う 日 数 の こ と で あ る ．評 価 項 目₍₃₎で は ，_Table 2に 示 す よ う な 制 約 条 件 が あ る ．そ こ で ，そ れ ぞ れ の 制 約 条 件 に お い て ，勤 務 形 態_kの 必 要 日 数 の 上 下 限 を 違 反 す る 日 数 を ペ ナ ル ティと し て 課 す． し た がって ，評 価 関 数_F3は 式₍₉₎で 与 え る ．

F3= ^∑

i∈M

∑

k∈W

{max(^∑

j∈D

x^k_i,j− b^k_i, 0) + max(c^k_i

−^∑

j∈D

x^k_i,j, 0)} (9)

  た だ し ，

b^k_i^{：看 護 師}i^が1ヶ月 に 勤 務 形 態_kを 割 り 付 け ら れ る 日 数 の 上 限 値 ，

c^k_i^{：看 護 師}i^が1ヶ月 に 勤 務 形 態_kを 割 り 付 け ら れ る 日 数 の 下 限 値 ．

(4)勤 務 間 隔 の 均 等 化

  評 価 項 目₍₄₎の 制 約 条 件 は ，連 続 す る 日 数 に お け る 勤 務 形 態₍休 日 も 含 む₎の 回 数 の 過 不 足 を 禁 止 す る も の で あ る ．制 約 条 件 と し て ，「 休 日 を₅日 間 に₁回 以 上 割 り 付 け る 」，「 深 夜 勤 を₆日 間 に₀∼ 1回 に 抑 え る 」な ど が あ る ．そ こ で ，そ れ ぞ れ の

Table 2 各 個 人 の 必 要 日 数 条 件 の 例

勤 務 形 態 必 要 日 数

深 夜 勤 _4∼5

夜 勤 _8∼9

休 日 土 日 祝 の 数

制 約 条 件 に お い て ，勤 務 形 態_kを_hk日 間 に 割 り 付 け る 回 数 の 上 下 限 を 違 反 し た 回 数 を ペ ナ ル ティ と し て 課 す．し た がって ，評 価 関 数_F4は 式₍₁₁₎で 与 え る ．

F4= ^∑

i∈M

∑

k∈W n−h_∑k+1

j=1

{max(

hk

∑

ϵ=0

x^k_i,j+ϵ− sk, 0) (10)

+max(tk−

h_k

∑

ϵ=0

x^k_i,j+ϵ, 0)}

  た だ し ，

hk^{：勤 務 形 態}kの 評 価 対 象 と な る 期 間 ，

s_k^{：勤 務 形 態}k^がh_k日 間 に 割 り 付 け ら れ る 日 数 の 上 限 値 ，

t_k^{：勤 務 形 態}k^がh_k日 間 に 割 り 付 け ら れ る 日 数 の 下 限 値 ．

(5)必 要 人 数 の 確 保

  必 要 人 数 と は ，₁日 に 各 勤 務 形 態 で 勤 務 す る 必 要 な 人 数 の こ と で あ る ．評 価 項 目₍₅₎で は ，_Table 3に 示 す よ う な 制 約 条 件 が あ る ．そ こ で ，そ れ ぞ れ の 制 約 条 件 に お い て ，勤 務 形 態_kの 必 要 人 数 の 上 下 限 を 違 反 す る 人 数 を ペ ナ ル ティと し て 課 す． し た がって ，評 価 関 数_F5は 式₍₁₁₎で 与 え る ．

F5=^∑

j∈D

∑

k∈W

{max(^∑

i∈M

x^ki,j− d^kj, 0) + max(e^kj

−^∑

i∈M

x^ki,j, 0)} (11)

  た だ し ，

d^k_j^：j日 に 勤 務 形 態_kを 割 り 付 け る 人 数 の 上 限 値 ， e^k_j^：j日 に 勤 務 形 態_kを 割 り 付 け る 人 数 の 下 限 値 ．

(6)グ ル ー プ 必 要 人 数 の 確 保

  毎 日 の 看 護 の 質 を 保 持 す る た め ，ス キ ル レ ベ ル や 所 属 チ ー ム を 考 慮 し て 各 勤 務 形 態 に 必 要 な メ ン バ ー 人 数 に す る こ と が 必 要 で あ る ．評 価 項 目₍₆₎の 制 約 条 件 に は ，「 深 夜 勤 に 新 人 は₀∼₁人 で

Table 3 各 日 の 必 要 人 数 条 件 の 例

勤 務 形 態 必 要 人 数

準 夜 勤 ₃

深 夜 勤 ₃

日 勤_{(平 日) 11∼13} 日 勤_{(土 日 祝) 3}

割 り 付 け る 」，「 準 夜 勤 に ベ テ ラ ン は₁∼₂人 で 割 り 付 け る 」，「 日 勤 に ベ テ ラ ン は₁∼₂人 で 割 り 付 け る 」等 が あ る ．こ れ ら の 制 約 条 件 は ，各 勤 務 形 態 で 一 定 以 上 の 看 護 の 質 を 維 持 す る た め ，各 グ ル ー プ か ら の 人 数 の 上 下 限 を 設 定 し て い る ． そ こ で ，そ れ ぞ れ の 制 約 条 件 に お い て ，勤 務 形 態_kに 対 す る グ ル ー プ_gの 人 数 の 上 下 限 を 違 反 す る 人 数 を ペ ナ ル ティと し て 課 す．し た がって ，評 価 関 数_F6は 式₍₁₂₎で 与 え る ．

F6=^∑

j∈D

∑

k∈W

∑

g∈G

{max(^∑

i∈Mg

x^ki,j− u^kr,j, 0) +

max(vr,j^k − ^∑

i∈Mg

x^ki,j, 0)} (12)

た だ し ，

u^k_g,j^：j日 に 勤 務 形 態_kを 行 う グ ル ー プ_gの 人 数 上 限 値 ，

v_g,j^{k ：}j日 に 勤 務 形 態_kを 行 う グ ル ー プ_gの 人 数 下 限 値 ．

(7)看 護 の 質 の 維 持

  看 護 の 質 は ，業 務 に 支 障 を 起 こ さ な い よ う， 一 定 レ ベ ル の 看 護 の 質 を 維 持 し ，ま た ，日 に よっ て 偏 り を 少 な く す る 必 要 が あ る ．本 研 究 で は 看 護 師 の ス キ ル レ ベ ル を₁∼₁₀の₁₀段 階 で 評 価 す る ．し た がって ，各 勤 務 形 態 ご と に 各 看 護 師 の ス キ ル レ ベ ル の 総 和 が 最 低 看 護 レ ベ ル を 満 た す こ と を 目 的 と し た ．評 価 関 数_F7は 式₍₁₃₎で 与 え る ．

F7=^∑

j∈D

∑

k∈W

∑

g∈G

max(Lmin^k_g,j− ^∑

i∈M_g,j^k

Li, 0) (13)

  た だ し ，

L_i^{：看 護 師}iの ス キ ル レ ベ ル ，

Lmin^k_g,j^{：グ ル ー プ}g^{に お け る}j日 の 勤 務 形 態_kの 最 低 看 護 レ ベ ル 値 ，

3.2 制 約 条 件 の 分 類

前 節 で 述 べ た 制 約 条 件 に は ，法 律 の 尊 守 や 看 護 の 質 と いった 必 ず 満 た さ な け れ ば 制 約_(Hard制 約₎と ，な る べ く 満 た し た い が 必 ず し も 満 た さ な く て も よ い 制 約_(Soft制 約₎が 存 在 す る ．こ れ ら の 評 価 関 数 は 解 探 索 を 行 う 上 で 互 い に 影 響 を 及 ぼ し あ う た め ，同 時 に 最 適 化 す る こ と は 困 難 で あ る ．そ こ で 本 手 法 で は ，こ れ ら の 制 約 を_{Table 4} に 示 す よ う に 分 類 す る ．

Table 4 Hard^{制 約 と}Soft^{制 約}

Hard 制 約 Soft 制 約

(2) 禁 止 パ タ ー ン の 低 減 (1) 勤 務 パ タ ー ン 負 荷 の 軽 減 (3) 必 要 日 数 の 確 保 (4) 勤 務 間 隔 の 均 等 化 (4) 必 要 人 数 の 確 保 (6) グ ル ー プ 必 要 人 数 の 確 保

(7) 看 護 の 質 の 維 持

4 DEの NSP へ の 適 用 4.1 ^{適 用 方 法}

一 般 に 最 適 化 問 題 は ，解 候 補 の 集 合 ，制 約 条 件 ，目 的 関 数 の 三 つ か ら 定 義 さ れ る ．_DEを 最 適 化 問 題 に 適 用 す る た め に は ，_GAと 同 様 に 解 候 補 は 染 色 体 に ，目 的 関 数 は 適 応 度 関 数 に 対 応 付 け る 必 要 が あ る ．制 約 条 件 は 染 色 体 に 組 み 込 む か ， ペ ナ ル ティ関 数 と し て 適 応 度 関 数 に 組 み 込 む 必 要 が あ る⁷⁾ ．本 手 法 で は ，_Hard制 約 の う ち 必 要 人 数 の 確 保 を 常 に 満 た す よ う に コ ー ド 化_/遺 伝 演 算 を 行 う．ま た ，他 の_Hard制 約 お よ び_Soft制 約 の 評 価 関 数 を 合 成 し て 複 数 の 目 的 関 数 を 設 計 し ， こ れ ら を 基 準 に 各 個 体 を 評 価 す る ．

目 的 関 数 を 式₍₁₄₎∼₍₁₆₎に 示 す．

min H₁ = F₂+ F₃ (14) min H₂ = F₁+ F₄ (15) min H3 = F6+ F7 (16)

こ こ で ，_H1は 必 要 人 数 の 確 保 を 除 い た_Hard制 約 の評価関数を合成した目的関数，_H2，_H3は_Soft制 約 の 評 価 関 数 を 合 成 し た 目 的 関 数 と す る ．な お ， 全ての制約を完全に満たす解を最適解とした場合， 解 候 補 と 最 適 解 と の 距 離 は 式₍₁₇₎で 求 め ら れ る ．

distance = ∥H∥ , H = (H1, H2, H3) (17)

4.2 コ ー ディン グ 方 法 と 遺 伝 演 算

本 手 法 で は_Hard制 約 で あ る 必 要 人 数 の 確 保 を 常 に 満 た す た め に ，順 列 表 現⁸⁾ を 用 い た コ ー ディン グ 法 を 提 案 す る ．_{Fig. 2}に コ ー ディン グ 例 を 示 す．一 般 的 な_DEで は 個 体 の 遺 伝 子 が 実 数 値 で あ る の に 対 し ，本 手 法 で の_DEで は 個 体 の 遺 伝 子 は 要 員 特 定 値 と し て 整 数 値 と す る ．提 案 す る コ ー ディン グ 方 法 で は 表₁つ を₁個 体 と し て 表 現 し ，各 日 の 日 勤 ，準 夜 勤 ，深 夜 勤 の 必 要 勤 務 者 を 順 序 表 現 で 決 定 す る こ と に よ り，各 勤 務 者 が 重 複 す る こ と な く 各 勤 務 に 選 択 さ れ る ．ま た ， DEの 遺 伝 操 作 で あ る 差 分 変 位・交 叉 を 行って も 必 要 人 数 の 確 保 を 満 た し た ま ま 新 た な 解 を 生 成 す る こ と が で き る ．

Fig. 2 コ ー ディン グ 例

ま た ，_DEの 遺 伝 演 算 で は ，差 分 変 異 親 個 体 を 生 成 す る 際 ，ベ ク ト ル 差 分 や ベ ク ト ル 和 を 求 め る ．そ の た め ，差 分 変 異 親 個 体 の 要 員 特 定 値 が ， 実 数 と な る 可 能 性 が あ る ．実 数 値 と なった 要 員 特 定 値 は ，小 数 点 以 下 の 切 り 捨 て ，切 り 上 げ，又 は 四 捨 五 入 な ど に よ り，整 数 値 に 変 換 す る ． 4.3 世 代 交 代 の 条 件

DEの ア ル ゴ リ ズ ム で は 対 象 親 個 体 と 子 個 体 を 比 較 し 次 世 代 へ 残 す 個 体 を 決 定 す る ．こ こ で は ， 対 象 親 個 体 の 目 的 関 数 の 値 を そ れ ぞ れ_H^P

1 ^，H2^P，

H₃^P と し ，子 個 体 の 目 的 関 数 の 値 を そ れ ぞ れ_H1^C， H₂^C，H₃^C と す る ．本 手 法 で は 世 代 交 代 の 条 件 と し て 以 下 を 考 え る ．

条 件_{1 H1}^C_{< H1}^P_{∧ H2}^C_{< H2}^P_{∧ H3}^C _{< H3}^P 条 件_{2 H1}^C_{< H1}^P_{∨ H2}^C_{< H2}^P_{∨ H3}^C _{< H3}^P 条 件_{3 H1}^C_{< H1}^P_{∨ (H2}^C _{< H2}^P_{∧ H3}^C _{< H3}^P₎

条 件₁で は ，子 個 体 の 全 て の 目 的 関 数 値 が 対 象 親 個 体 よ り も 改 善 さ れ て い れ ば ，子 個 体 が 次 世 代 と し て 選 択 さ れ る ．

条 件₂で は ，目 的 関 数_{H1, H2, H3}の う ち ，い ず れ か の 目 的 関 数 が 対 象 親 個 体 よ り も 改 善 さ れ て

い れ ば ，子 個 体 が 次 世 代 と し て 選 択 さ れ る ．条 件₁よ り も 世 代 交 代 の た め の 制 約 が 緩 和 さ れ る た め ，個 体 が 進 化 し 易 く な る と 考 え ら れ る ．し か し な が ら ，全 て の 関 数 値 が 世 代 と と も に 改 善 さ れ る 保 障 は な い ．

条 件₃で は ，世 代 交 代 の た め に_H2と_H3は 同 時 に 改善される必要がある．一方，_H1は単独でも改善 されれば世代交代できるため，個体集団では_H1が H2, H3よ り も 早 く 改 善 さ れ る こ と が 期 待 で き る ． 4.4 ^{突 然 変 異}

本 手 法 で は 、個 体 の 要 素（ 要 員 特 定 値 ）が 整 数 値 で あ る た め ，各 個 体 の 同 一 の 次 元 に つ い て の 要 員 特 定 値 が 全 て 同 じ 値 に な り 易 い ．同 じ に なった 次 元（ 固 定 次 元 ）で は ，個 体 間 の 差 分 が 生 ま れ な い た め ，そ れ 以 上 解 を 改 善 で き な い ．そ こ で 本 手 法 で は ，各 世 代 終 了 時 に ，固 定 次 元 の 遺 伝 子 を ラ ン ダ ム で 変 更 す る 突 然 変 異 を 行 う． 各 個 体 に 対 し ，全 て の 個 体 間 で 遺 伝 子 が 同 じ 値 と なって い る 次 元 に の み ，_Pmの 確 率 で 要 員 特 定 値 を ラ ン ダ ム で 他 の 値 に 変 更 す る ．

5 数 値 実 験

5.1 NSP^{の 問 題 設 定}

本 稿 で は ，ス ケ ジュー リ ン グ 期 間₃₀日 ，看 護 師 数₂₃人 で 構 成 さ れ る 勤 務 表 を 対 象 と す る ．_{Fig. 2} に 初 期 ス ケ ジュー ル を 示 す．勤 務 表 作 成 前 に す で に わ かって い る 箇 所 は 希₍希 望 休 暇₎，会₍会 議₎， 研₍研 修₎と し て 示 さ れ て い る ．ま た ，看 護 師 の ス キ ル は 身 分 ，経 験 に よ り 大 き く ベ テ ラ ン ，中 堅 ，新 人 に 分 類 さ れ て い る ．₄列 目 は 師 長 に₁₀段 階 で 評 価 さ れ た ス キ ル レ ベ ル を あ ら わ す．各 評 価 項 目 の 制 約 条 件 を_{Table 5}に 示 す．勤 務 パ タ ー ン 評 価 値 の パ タ ー ン タ イ プ ご と の 重 み は_{α = 1}， β = 2^，γ = 7^{と し た ．}

5.2 実 験 結 果 と 考 察

DE^{のアルゴリズムは}2^{章で述べた}DE/rand/1/exp^， 各 パ ラ メ ー タ は_S=0.4，_{CR = 0.9}，_{Pm= 0.01}，個 体 数_NP=50，打 ち 切 り 世 代 は₁₀₀₀₀₀世 代 と し て 実 験 を 行った ．こ こ で は ，各 世 代 で_Hard制 約 に 関 す る 目 的 関 数_H1が 最 も 小 さ い 解 と な る 個 体 を 最 良 解 と す る ．ま た ，そ れ ら が 複 数 存 在 す る 場 合 は_distanceが 最 も 小 さ い 解 を そ の 世 代 の 最 良 解 と す る ．ま た ，_H1が₀と な る 解_(Hard制 約 を 完 全 に 満 た す 解₎を 実 行 可 能 解 と す る ．

Table 5 NSP^{の 制 約 条 件}

  評 価 項 目 の 分 類   制 約 条 件 の 内 容

勤 務 パ タ ー ン 負 荷 の 軽 減 「 日 日 深 準 休 休 」の パ タ ー ン を で き る 限 り 割 り 振 る 禁 止 パ タ ー ン の 低 減 「 研 修・深 夜 勤 」パ タ ー ン を 禁 止

必 要 日 数 の 確 保 休 日 を11 日 割 り 振 る 深 夜 勤 を3∼4 日 割 り 振 る 準 夜 勤 を3∼4 日 割 り 振 る

夜 勤（ 準 夜 勤 ，深 夜 勤 ）を7∼8 日 割 り 振 る 勤 務 間 隔 の 均 等 化 休 日 を6 日 間 に 1∼6 回

夜 勤（ 準 夜 勤 ，深 夜 勤 ）を6 日 間 に 0∼4 回 必 要 人 数 の 確 保 日 勤 は 平 日10∼11 人 ，土 曜 6 人 ，日 祝 5 人

準 夜 勤 は 各 日_{3 人} 深 夜 勤 は 各 日_{3 人}

グ ル ー プ 必 要 人 数 の 確 保 日 勤 は 新 人 を 各 日_{1∼2 人}

深 夜 勤 ，準 夜 勤 は ベ テ ラ ン を 各 日_{1∼3 人} 深 夜 勤 ，準 夜 勤 は 各 チ ー ム か ら 各 日_{1∼2 人}

看 護 の 質 の 維 持 準 夜 勤 ，深 夜 勤 そ れ ぞ れ の 最 低 看 護 レ ベ ル_{16 を 満 た す} 日 勤 の 最 低 看 護 レ ベ ル 平 日54，土 曜 33，日 祝 28 を 満 た す

各 チ ー ム の 準 夜 勤 ，深 夜 勤 そ れ ぞ れ の 最 低 看 護 レ ベ ル_{8 を 満 た す} 各 チ ー ム の 最 低 日 勤 看 護 レ ベ ル 平 日20，土 日 祝 8 を 満 た す

࿯ ᣣ ␸ ࿯ ᣣ ࿯ ᣣ ࿯ ᣣ ␸ ࿯ ᣣ

㪥㪸㫄㪼 㪪㫂㫀㫃㫃 㪫㪼㪸㫄 㪣_㫀 㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉 㪈㪊 㪈㪋 㪈㪌 㪈㪍 㪈㪎 㪈㪏 㪈㪐 㪉㪇 㪉㪈 㪉㪉 㪉㪊 㪉㪋 㪉㪌 㪉㪍 㪉㪎 㪉㪏 㪉㪐 㪊㪇

䉴䉺䉾䊐㪘 䊔䊁䊤䊮 㪘 㪐 䋺 Ꮧ Ꮧ ળ ળ Ꮧ

䉴䉺䉾䊐㪙 䊔䊁䊤䊮 㪙 㪐 䋺 ળ ળ ળ Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪚 䊔䊁䊤䊮 㪘 㪐 䋺 Ꮧ Ꮧ Ꮧ Ꮧ ળ ળ ળ ળ ળ ળ

䉴䉺䉾䊐㪛 䊔䊁䊤䊮 㪙 㪏 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪜 䊔䊁䊤䊮 㪙 㪏 䋺 Ꮧ Ꮧ Ꮧ Ꮧ ળ Ꮧ

䉴䉺䉾䊐㪝 䊔䊁䊤䊮 㪘 㪏 䋺 Ꮧ Ꮧ ળ Ꮧ Ꮧ Ꮧ ળ ⎇ ળ

䉴䉺䉾䊐㪞 䊔䊁䊤䊮 㪘 㪎 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪟 䊔䊁䊤䊮 㪙 㪎 䋺 Ꮧ Ꮧ ળ ળ

䉴䉺䉾䊐㪠 䊔䊁䊤䊮 㪘 㪎 䋺 Ꮧ Ꮧ Ꮧ ળ ળ ળ ⎇ ળ

䉴䉺䉾䊐㪡 䊔䊁䊤䊮 㪘 㪏 䋺 ળ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪢 䊔䊁䊤䊮 㪘 㪎 䋺 Ꮧ Ꮧ Ꮧ Ꮧ ળ Ꮧ

䉴䉺䉾䊐㪣 ਛၷ 㪙 㪌 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪤 ਛၷ 㪘 㪍 䋺 Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪥 䊔䊁䊤䊮 㪘 㪏 䋺 Ꮧ Ꮧ

䉴䉺䉾䊐㪦 䊔䊁䊤䊮 㪙 㪏 䋺 Ꮧ ળ Ꮧ ⎇ Ꮧ Ꮧ

䉴䉺䉾䊐㪧 ਛၷ 㪘 㪌 䋺 ળ Ꮧ

䉴䉺䉾䊐㪨 䊔䊁䊤䊮 㪘 㪎 䋺 ળ

䉴䉺䉾䊐㪩 ਛၷ 㪙 㪍 䋺 Ꮧ Ꮧ Ꮧ ળ

䉴䉺䉾䊐㪪 ᣂੱ 㪙 㪈 䋺

䉴䉺䉾䊐㪫 ᣂੱ 㪙 㪉 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪬 ਛၷ 㪙 㪋 䋺 Ꮧ Ꮧ ⎇

䉴䉺䉾䊐㪭 ᣂੱ 㪘 㪊 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

䉴䉺䉾䊐㪮 ਛၷ 㪙 㪋 䋺 Ꮧ Ꮧ Ꮧ Ꮧ Ꮧ

Fig. 3 初 期 ス ケ ジュー ル

ま ず，各 条 件 を 用 い た 場 合 で の 実 験 結 果 を_Fig. 4^，Fig. 5^，Fig. 6に そ れ ぞ れ 示 す．条 件₁の 場 合 で は 世 代 交 代 が 起 こ る 回 数 が 少 な く，終 盤 の 世 代 で は ほ と ん ど 解 が 改 善 さ れ て い な い ．ま た ， 最 良 解 の_H1が₀と なって い な い た め ，実 行 可 能 解 を 発 見 で き て い な い こ と が 分 か る ．条 件₂の 場 合 で は ，各 目 的 関 数 値 は ほ ぼ 均 等 に 改 善 さ れ い る ． し か し な が ら ，終 了 世 代 ま で に_H1が₀と なって い な い た め ，条 件₁の 場 合 と 同 様 に 実 行 可 能 解 は 発 見 で き て い な い ．条 件₃の 場 合 で は ，前 半 の 世 代 で は 各 目 的 関 数 値 は ほ ぼ 均 等 に 改 善 さ れ ，₆₀₀₀₀ 世 代 頃 に_H1が₀と な り 実 行 可 能 解 を 発 見 で き て い る ．そ の 後 は 各 関 数 値 は 変 化 が な く 一 定 値 に 収 束 し て い る ．

㪇 㪌㪇 㪈㪇㪇 㪈㪌㪇 㪉㪇㪇 㪉㪌㪇 㪊㪇㪇 㪊㪌㪇

㪇 㪉㪇㪇㪇㪇 㪋㪇㪇㪇㪇 㪍㪇㪇㪇㪇 㪏㪇㪇㪇㪇 㪈㪇㪇㪇㪇㪇

਎ઍ

㑐ᢙ୯

H₁

H₂ H₃

Fig. 4 ^{条 件}1で の 最 良 解 の 関 数 値

㪇 㪌㪇 㪈㪇㪇 㪈㪌㪇 㪉㪇㪇 㪉㪌㪇 㪊㪇㪇 㪊㪌㪇

㪇 㪉㪇㪇㪇㪇 㪋㪇㪇㪇㪇 㪍㪇㪇㪇㪇 㪏㪇㪇㪇㪇 㪈㪇㪇㪇㪇㪇

਎ઍ

㑐ᢙ୯

H₁

H₂ H₃

Fig. 5 ^{条 件}2で の 最 良 解 の 関 数 値

次 に ，_{Fig. 7}に 最 良 解 の_distanceを 示 す．序 盤 の 世 代 で は ，条 件₁で 最 も 早 く_distanceが 減 少 し て い る ．そ の 後 は ，条 件₃で 条 件₁よ り も 小 さ い distanceと な る 解 を 発 見 し て い る ．探 索 終 盤 で は

㪇 㪌㪇 㪈㪇㪇 㪈㪌㪇 㪉㪇㪇 㪉㪌㪇 㪊㪇㪇 㪊㪌㪇

㪇 㪉㪇㪇㪇㪇 㪋㪇㪇㪇㪇 㪍㪇㪇㪇㪇 㪏㪇㪇㪇㪇 㪈㪇㪇㪇㪇㪇

਎ઍ

㑐ᢙ୯

H₁

H₂ H₃

Fig. 6 ^{条 件}3で の 最 良 解 の 関 数 値

条 件₂が 最 小 と な り，最 も 最 適 解 に 近 い 解 を 発 見 し て い る ．し か し な が ら 条 件₂の 最 良 解 は_Hard制 約 を 満 た し て お ら ず，実 際 に は 使 用 で き な い 勤 務 表 と なって い る ．

以 上 の 結 果 よ り，条 件₃で 実 用 的 な 勤 務 表 を 作 成 す る た め に は ，各 目 的 関 数 の 改 善 し 易 さ を 考 慮 す る 必 要 が あ る と い え る ．ま た ，各 条 件 で は 解 探 索 の 進 み 具 合 に よって 探 索 効 率 が 異 な る た め ，こ れ ら を 組 み 合 わ せ る こ と で 探 索 効 率 を 向 上 さ せ ，よ り_distanceの 小 さ い 実 行 可 能 解 を 発 見 で き る と 考 え ら れ る ．

最 後 に ，_{Fig. 8}に 条 件₃で 得 ら れ た 最 良 解 の 例 を 示 す．こ の 勤 務 表 で は 必 要 日 数 の 確 保 は 完 全 に 満 た さ れ ，各 日 の ス キ ル レ ベ ル の 合 計 も ほ ぼ Table 5の 条 件 を 満 た し て い る こ と が 確 認 で き る ．

㪇 㪈㪇㪇 㪉㪇㪇 㪊㪇㪇 㪋㪇㪇 㪌㪇㪇

㪇 㪉㪇㪇㪇㪇 㪋㪇㪇㪇㪇 㪍㪇㪇㪇㪇 㪏㪇㪇㪇㪇 㪈㪇㪇㪇㪇㪇

਎ઍ

distance

᧦ઙ 㪈

᧦ઙ 㪉

᧦ઙ 㪊

Fig. 7 各 条 件 で の 最 良 解 の_distance

Fig. 8 ^{条 件}3で 得 ら れ た 最 良 解 の 例

6 お わ り に

本 稿 で はDifferential Evolution^をNSP^{に 適 用 し ，} 勤 務 表 作 成 者 の 要 求 を 満 た す 勤 務 表 を 作 成 す る 手 法 を 提 案 し た ．提 案 手 法 で は ，_Hard制 約 の 一 部 を 満 た す コ ー ド 化 を 用 い ，他 の_Hard制 約 お よ び Soft制 約 の 評 価 関 数 を 合 成 し て 複 数 の 目 的 関 数 を 設 計 し ，こ れ ら を 基 準 に 各 個 体 を 評 価 し 個 体 集 団 を 進 化 さ せ た ．実 験 結 果 よ り，_Soft制 約 の 目 的 関 数 を_Hard制 約 の 目 的 関 数 よ り 改 善 し 難 く す る こ と で ，_Hard制 約 が 優 先 的 に 改 善 さ れ ，終 了 世 代 ま で に_Hard制 約 を 満 た し た 最 良 解 を 発 見 で き る こ と を 確 認 し た ．今 後 は ，提 案 手 法 で 作 成 し た 勤 務 表 と 看 護 師 長 が 実 際 に 作 成 し た 表 と の 比 較 ，_DEの パ ラ メ ー タ に 関 す る 検 証 を 行 い ，実 用 的 な 勤 務 表 生 成 シ ス テ ム の 構 築 を 目 指 し た い ． 参 考 文 献

1) 大 谷 慎 ，長 谷 山 美 紀 ，北 島 秀 夫：ナ ー ス ス ケ ジュー リ ン グ 問 題 のGAによる解法に関する考察， 電 子 情 報 通 信 学 会 技 術 研 究 報 告. ITS 101(625), 125-130 (2002)

2) 池 上 敦 子 ，丹 羽 明：ナ ー ス・ス ケ ジュー リ ン グ に 有 効 な ア プ ロ ー チ : 2 交 替 制 ア ル ゴ リ ズ ム に お け る 実 現 ，Journal of the Operations Research Society of Japan 41(4), 572-588 (1998)

3) 坂 口 琢 哉：地 域 型 遺 伝 的 ア ル ゴ リ ズ ム を 用 い た ナ ー ス ス ケ ジュー リ ン グ，情 報 処 理 学 会 研 究

報 告. MPS, 数 理 モ デ ル 化 と 問 題 解 決 研 究 報 告 2007(128), 247-250 (2007)

4) Price, K.V., Storn, R. and Lampinen, J.: Differ- ential Evolution: A Practical Approach to Global Optimization. Springer-Verlag, London, UK (2005) 5) Storn, R. and Price, K.: Differential evolution - a simple and effcient adaptive scheme for global opti- mization over continuous spaces, Technical Report TR-95-012, ICSI (1995)

6) 糸賀健，坂倉義明，谷口典之，星野孝総，亀井且 有：ナ ー ス ス ケ ジュー リ ン グ 問 題 に お け る 探 索 空 間 を 考 慮 し た 進 化 的 計 算 手 法 の 一 考 察 ，第_14回イ ン テ リ ジェン ト・シ ス テ ム・シ ン ポ ジ ウ ム 講 演 論 文 集 ，pp.151-154 (2004)

7) 北 野 宏 明：遺 伝 的 ア ル ゴ リ ズ ム 2，産 業 図 書 株 式 会 社₍₁₉₉₅₎

8) 伊庭斉志：遺伝的アルゴリズムの基礎，オーム社 (1994)