[ 初めての方へ | 一覧(最新更新順) | 全文検索 | 過去ログ ]
『希望する予約枠への割り付け』（SAN）
ワクチンの職場接種の準備を進めています。
社内で希望者のとりまとめを始めたものの、
接種枠に対する個人割付のロジックでコケてしまっています。
vbaによる処理になると思われるのですが、
ご教示いただけますと幸いです。
■最低限実現したいこと
・打ち手は5人
・1人当たり1時間に50人に接種が可能
・1日における医師の稼働時間は4時間（4コマ）
・接種希望者の想定は1万人
・接種希望日は第３希望まで募るが、接種時間の割付は抽選式
■可能であれば実現したいこと（上から希望順）
・複数の組織から提出される希望者リストを偏りを少なく 割付処理を行いたい ・とりまとめ組織単位での希望承認優先度設定（高・中・低） ・接種出力数の調整に対応 6/25 25接種/時間×5名 6/26 35接種/時間×5名 6/27以降 50接種/時間×5名
■現在発出しているとりまとめ様式(1部署最大300名程度の記入）
行 ____A____ ____B___ ___C___ ___D___ 1 社員番号 氏名 第１希望 第２希望 第３希望 2 1234567 山田花子 6/25 6/28 6/30 3 1111112 田中太郎 6/30 6/25 7/1 4 1111113 川田正夫 7/1 7/2 6/30 5 2134567 坂東三郎 6/25 6/30 （空欄） 6 ： ： ： ：
＜ 使用 Excel：Excel2016、使用 OS：Windows10 ＞
おはようございます。 なかなか今日的な課題ですね。 これはかなり前倒しで希望が集まりそうですね。
骨格としては、次のような感じになるのではないかと思います。
「第一希望」について希望日ごとに分類
・各接種希望日の制限人数まで、抽選で割当
・割当者は確定
・外れ者は、「第一希望外れ者」に留保
「第一希望外れ者」について、第二希望ごとに分類
・各接種日の制限人数の残りまで、抽選で割当
・割当者は確定
・外れ者は、「第2希望外れ者」に留保
「第2希望外れ者」について、第3希望ごとに分類
・各接種日の制限人数の残りまで、抽選で割当
・割当者は確定
・外れ者は、抽選で、制限人数の残りがある日に割当
ただし、 ＞・とりまとめ組織単位での希望承認優先度設定（高・中・低） というのがよく分かりませんでした。
これは、 ・組織ごとに、上記の「抽選で」という場合の優先度を設定するということですか？ つまり、その組織の人はすべて同様の優先度を決めるということですか？ ・それとも、組織毎にこれはという人は、優先度を高くしてくれ、というような話ですか？ 例えば、上位職はできるだけ優先してくれとか、ですか？
細かい論点はまだありますが、取りあえず。
（γ） 2021/06/18(金) 06:51
これは、いわゆる「クラス編成問題」と言われるもので、 [[20201117181651]]で紹介したような手法で、 "各人の希望に沿った満足度の合計を最大化させる"ことで、 最適解を得られることが知られています。（線形計画法の活用）
解くには、なんらかのソルバーを使いますが、Excelのソルバーは、 「200個の変数セルと100件の制約条件」という制約があるようなので、 今回のケースでは、とても間に合いそうもありません。
またまた顰蹙ものの、外部ツールを使って試したところ、 変数12万の問題も解くことができました。 （実行時間2分程度。組織別優先度は未反映。各人の希望はランダムに設定。） ですからシステム部門に依頼すれば、たぶん解くことが可能だと思います。
もちろん、ExcelVBAでも妥当な解を見つけることは可能かと思います。 （γ） 2021/06/18(金) 07:13
＞・とりまとめ組織単位での希望承認優先度設定（高・中・低）というのがよく分かりませんでした。
この点について補足させていただきますと、
とりまとめ様式は各組織に同じものを配布していますが、
事務局側での割り振りの際に、
Ａ．お客様対応を行わなければならない組織（優先度高）
Ｂ．一定数の出社が必要な組織（優先度中）
Ｃ，柔軟な在宅勤務の活用が可能な組織（優先度低）
に分けて、組織所属によって個人の希望に対する当選率を上げたいという考え方です。
過去ログのクラス編成問題というものも参照してみますが、
私もなにせvbaは昔取った杵柄みたいに仕事を振られており、
ソルバーについても改めて学習します。
日々勉強は必要ということですね。
（SAN） 2021/06/18(金) 07:56
お偉いさんの希望日から決めていくだけですよね？ 私には、単に優先順を付けて、並び変えるだけじゃないかと思えるんですが。。
ちょっと分からないのが「接種時間」。 ご提示のとりまとめ表にそんな希望データって無いですが。
＞ ・複数の組織から提出される希望者リストを偏りを少なく 同順位の関係にあるものは乱数で散らばらさせれば、自動的にばらつきますけども。
（半平太） 2021/06/18(金) 20:30
＞ ・接種出力数の調整に対応 ＞ 6/25 25接種/時間×5名 ＞ 6/26 35接種/時間×5名 ＞ 6/27以降 50接種/時間×5名
考えたら、この条件が曖昧だなぁ。
6/27以降、いつまであるんですか？ 10,000名に対して、日数の余裕は絶無？（それだと すんごく難しいことになる）
（半平太） 2021/06/18(金) 21:52
とりあえず
「第一希望」について希望日ごとに分類
・各接種希望日の制限人数まで、抽選で割当
・割当者は確定
・外れ者は、「第一希望外れ者」に留保
「第一希望外れ者」について、第二希望ごとに分類
・各接種日の制限人数の残りまで、抽選で割当
・割当者は確定
・外れ者は、「第2希望外れ者」に留保
「第2希望外れ者」について、第3希望ごとに分類
・各接種日の制限人数の残りまで、抽選で割当
・割当者は確定
・外れ者は、抽選で、制限人数の残りがある日に割当
の考え方で関数とソートを組み合わせてマンパワーで無理やり組みました。
この後別のエリアなどで接種やるぞ。となるとげんなりします…。
（SAN） 2021/06/19(土) 00:08
＞ 「第2希望外れ者」について、第3希望ごとに分類 ＞ : : : ＞ ・外れ者は、抽選で、制限人数の残りがある日に割当
ここの考え方は、結局、希望通りにならない人が出ても已むを得ないって趣旨ですよね？ ※できるだけ少ないに越したことはないですが、 何が理想的なのか誰も分からないから問題は起きないです。 もし分かる人が居るならそのロジックを教えてもらえばいいですが、多分居ない。
そうなると、やっぱり簡単な気がします。
ところで「希望承認優先度設定（高・中・低）」は実際に設定作業をやったのですか？
私としては、こんな考えで作ろうと思っていますけど。 高の人から第1希望〜第3希望まで優先的に考慮し、次に 中の人の 第1希望〜第3希望まで優先的に考慮し、次に 低の人の 第1希望〜第3希望まで優先的に考慮し、最後に あぶれた人達を制限人数の残りがある日に割当
（半平太） 2021/06/19(土) 08:00
希望承認優先度設定（高・中・低）については抽選に利用する乱数に整数で優先度を加算して得点の上位から枠数を埋めるという処理にしています。
（SAN） 2021/06/19(土) 08:39
＞希望承認優先度設定（高・中・低）については抽選に利用する乱数に ＞整数で優先度を加算して得点の上位から枠数を埋めるという処理にしています。
低のデータはいちいち入力するのも面倒だと思うので 高・中区分だけ入れて、ないものが低と考えて処理すればいいですかね。 ※まぁ、これはデータの作り方であって、考え方に影響がある訳ではないですが。
ところで、私はお偉いさんから優先割当を考えていますが、そこがそちらとの違いとなりそう。
＞関数とソートを組み合わせてマンパワーで無理やり組みました。 結局、もう終わったと考えていいんでしょうか？ 新たに作っても意味ないなら、私はこれば終わりにします(無駄なことはやらない主義なので）
これからちょっと出かけます。
（半平太） 2021/06/19(土) 09:01
日付別の接種予定数を下図のような塩梅で設定する。(実際の日に合わせて手作成）
<サンプル> 行 ___N___ ___O___ _P_ _Q_ _R_ __S__ 1 予定日 予定数 高 中 低 空き 2 6月25日 500 3 6月26日 700 4 6月27日 1000 5 6月28日 1000 6 6月29日 1000 7 6月30日 1000 8 7月1日 1000 9 7月2日 1000 10 7月3日 1000 11 7月4日 1000 12 7月5日 500
承認優先度等のデータは、以下のレイアウトにして入力する ※承認優先度は1,2,3とし、空白セルは「3」とみなして処理する。
<レイアウト> 行 ___A___ ____B____ ____C____ ___D___ ____E____ ___F___ ___G___ ___H___ __I__ __J__ __K__ 1 社番 氏名 第１希望 第2希望 第３希望 高中低 決定日 満足度 乱数 キー 元行 2 1234567 山田花子 6月25日 6月28日 6月30日 1 3 1111112 田中太郎 6月30日 6月25日 7月1日 2 4 1111113 川田正夫 7月1日 7月2日 6月30日 2 5 2134567 坂東00001 6月25日 6月30日 2
並べ替えキーを作成 → 承認優先度>乱数>第1希望日>第2希望日>第3希望日
<実行後イメージ> 行 ___A___ ____B____ ____C____ ___D___ ____E____ ___F___ ___G___ ___H___ _____I_____ ___________J___________ __K__ 1 社番 氏名 第１希望 第2希望 第３希望 高中低 決定日 満足度 乱数 キー 元行 2 1234567 山田花子 6月25日 6月28日 6月30日 1 6月25日 1 0.409577313 KY101410443724437544377 2 3 1111112 田中太郎 6月30日 6月25日 7月1日 2 6月30日 1 0.284741874 KY201285443774437244378 3 4 1111113 川田正夫 7月1日 7月2日 6月30日 2 7月1日 1 0.929762813 KY201930443784437944377 4 5 2134567 坂東00001 6月25日 6月30日 2 6月25日 1 0.425083224 KY201425443724437700000 5
Sub arrangeToVaccine()
Dim fixedDate
Dim Happiness
Dim adminR As Range
Dim adminV
Dim dayAppliedR As Range
Dim dayAppliedV
Dim StatusV
Dim staRank
Dim Priority
Dim posStart(1 To 3)
Dim posEnd(1 To 3)
Dim staRow, priCol
Dim matchedRow
Dim numApplicant, i
numApplicant = Cells(Rows.Count, "A").End(xlUp).Row - 1
Application.ScreenUpdating = False
'承認優先度が入っていないものは3と見なす。
On Error Resume Next
Range("F2").Resize(numApplicant).SpecialCells(xlCellTypeBlanks).Value = 3
On Error GoTo 0
With Range("I2").Resize(numApplicant)
.FormulaR1C1 = "=RAND()"
.Value = .Value
With .Offset(, 1)
.FormulaR1C1 = "=""KY""&RC[-4]&TEXT((1+RC[-1])*1000,""00000"")&TEXT(RC[-7],""00000"")&" & _
"TEXT(RC[-6],""00000"")&TEXT(RC[-5],""00000"")"
.Value = .Value
End With
End With
Range("K2").Value = 2
Range("K2").AutoFill Destination:=Range("K2").Resize(numApplicant), Type:=xlFillSeries
'キーで並べ替える
With ActiveSheet
.Sort.SortFields.Clear
.Sort.SortFields.Add Key:=.Range("J2"), SortOn:=xlSortOnValues, Order:=xlAscending
With .Sort
.SetRange ActiveSheet.Range("A2:K2").Resize(numApplicant)
.Header = xlNo
.SortMethod = xlStroke
.Apply
End With
End With
'出力エリアをクリアする
Range("G2:H2").Resize(numApplicant).ClearContents
Application.ScreenUpdating = True
Set adminR = Range("N2", Cells(Rows.Count, "N").End(xlUp).Offset(, 5))
adminR.Resize(, 5).Offset(, 2).ClearContents
Set dayAppliedR = Range("C2:E2").Resize(numApplicant)
dayAppliedV = dayAppliedR.Value2
StatusV = Range("F2").Resize(numApplicant).Value
fixedDate = Range("G2").Resize(numApplicant).Value
Happiness = Range("H2").Resize(numApplicant).Value
'承認優先度別にチェックすべき行(初行と終行）を事前に算出する
posStart(1) = 1
posEnd(1) = Application.Match(1, Range("F2").Resize(numApplicant))
posStart(2) = posEnd(1) + 1
posEnd(2) = Application.Match(2, Range("F2").Resize(numApplicant))
posStart(3) = posEnd(2) + 1
posEnd(3) = Application.Match(8 ^ 8, Range("F2").Resize(numApplicant))
'予定数を空数欄移行(空きの初期値をセット)
adminR.Columns(6) = adminR.Columns(2).Value
'集計エリアの配列を作る
adminV = adminR.Value
'偉い人順に、第1〜3希望の中に接種可能日があれば割付けしていく
For staRank = 1 To 3 '平社員は最後(＝3）に検討する
For staRow = posStart(staRank) To posEnd(staRank)
For priCol = 1 To 3
If fixedDate(staRow, 1) = "" And dayAppliedR(staRow, priCol) <> "" Then
'未定且つ希望日が残っているケース
matchedRow = Application.Match(dayAppliedR(staRow, priCol), adminR.Columns(1), 0)
If IsNumeric(matchedRow) Then '希望日が接種予定日に存在する場合(正常）
If adminV(matchedRow, 6) > 0 Then '空きがあれば
adminV(matchedRow, 6) = adminV(matchedRow, 6) - 1
adminV(matchedRow, staRank + 2) = adminV(matchedRow, staRank + 2) + 1
fixedDate(staRow, 1) = dayAppliedR(staRow, priCol) '決定日
Happiness(staRow, 1) = priCol '希望合致度
Exit For
End If
End If
End If
Next priCol
Next staRow
' Call dispResult(fixedDate, adminR, adminV, numApplicant): Stop'中間チェック
Next staRank
'希望には添えなかった人を強制割当
For staRow = 1 To numApplicant
If fixedDate(staRow, 1) = "" Then
For i = 1 To UBound(adminV)
If adminV(i, 6) > 0 Then '空き枠あり
adminV(i, 6) = adminV(i, 6) - 1
staRank = StatusV(staRow, 1)
adminV(i, staRank + 2) = adminV(i, staRank + 2) + 1
fixedDate(staRow, 1) = adminV(i, 1)
Exit For
End If
Next i
End If
Next staRow
'結果打ち出し
Application.ScreenUpdating = False
dispResult fixedDate, adminR, adminV, numApplicant, Happiness
'元の並びに変える
With ActiveSheet
.Sort.SortFields.Clear
.Sort.SortFields.Add Key:=.Range("K2"), SortOn:=xlSortOnValues, Order:=xlAscending
With .Sort
.SetRange ActiveSheet.Range("A2:K2").Resize(numApplicant)
.Header = xlNo
.SortMethod = xlStroke
.Apply
End With
End With
Application.ScreenUpdating = True
End Sub
Private Sub dispResult(fixedDate, adminR, adminV, numApplicant, Happiness)
Range("G2").Resize(numApplicant) = fixedDate
Range("H2").Resize(numApplicant) = Happiness
adminR.Value = adminV
End Sub
（半平太） 2021/06/19(土) 16:49
集計結果のイメージをアップし忘れました。 m(__)m
<実行後 イメージ> 行 ___N___ ___O___ _P_ _Q_ _R_ __S__ 1 予定日 予定数 高 中 低 空き 2 6月25日 500 75 182 243 0 3 6月26日 700 52 199 449 0 4 6月27日 1000 51 216 733 0 5 6月28日 1000 59 219 722 0 6 6月29日 1000 76 200 724 0 7 6月30日 1000 76 201 723 0 8 7月1日 1000 55 172 773 0 9 7月2日 1000 61 212 727 0 10 7月3日 1000 55 178 767 0 11 7月4日 1000 74 190 736 0 12 7月5日 500 81 175 244 0
（半平太） 2021/06/19(土) 16:52
＞ ＞ 「第2希望外れ者」について、第3希望ごとに分類 ＞ ＞ : : : ＞ ＞ ・外れ者は、抽選で、制限人数の残りがある日に割当 ＞ ここの考え方は、結局、希望通りにならない人が出ても已むを得ないって趣旨ですよね？
ここの所はちょっとラフ過ぎました。
希望通りになった人の他の希望日をチェックして、 強制的に割振りられてしまった不幸な人の日付と一致するものがあれば その日と交換して上げるようにすると少し改善される余地があります。
まぁ、今のところはアイデアだけですけども。
（半平太） 2021/06/19(土) 22:13
半平太さん作成のコードは、色々な企業で使えるかも知れないと思いました。
参考までに、「満足度」を下記の様に仮に定めて実験してみました。
優先順位1(高）優先順位2(中）優先順位3(低）
第1希望どおりのとき 100 * 1.2 100 100 * 0.8
第2希望どおりのとき 80 * 1.2 80 80 * 0.8
第3希望どおりのとき 30 * 1.2 30 30 * 0.8
それ以外 -1000 -1000 -1000
対象者1万人として、 ・半平太さんのものは、 977,716点 ・私の最適化利用のものは、 990,740点でした。
(2021/06/19(土) 22:13で半平太さんが書かれていることを、 最適化ツールは自動でやってくれるということかと思います。）
最適化が若干効いてはいますが、驚くほどの差ではありませんでした。 一過性の作業であり、さほど気にする話でも無いと思います。
それに、私のはExcelの範疇外ですから、回答としては零点でしょう。
・更に言えば、上記はリクエストがランダムにばらけた場合の比較であり、 むしろ特殊なケースと言えなくもないわけです。 ・実際には、希望が前半に固まってしまうことのほうが普通でしょうし、 接種側の要請により、希望に拘わらず前倒しで埋めてください、 と言う話もあるでしょうから、 ・そうした場合は、最適化したほうが満足度は高いとはいえ、本人の希望との 合致による満足度はさして重要なものではなくなるでしょう。
少々の精密性よりも、
・自分がそれなりに納得できるロジックで、
・迅速に実行することが大切でしょう。
■ただ、こうした例のように、Excelの出来る範囲に限定せず、色々な道具に トライする機会は、今後増えそうな気はしています。 企業のなかに、データサイエンス的な仕事をされている部門があるかも しれませんが、その人たちにとっては、上記のような話はきっと日常茶飯の 簡単な話なのかもしれません。
線形計画法の応用例として記憶に留める方がおられれば幸いです。 （むろん、PythonでもGLPK(GNU Linear Programming Kit)を呼び出すパーケージが ありますから、同様の計算は可能です。）
(余談) 米国では接種券の事前交付ということはやっていませんし、 接種の予約システムも当初は相当バグがあったそうだが、 相当前から準備し、スピード重視で進めたそうである（実質重視）。 また、接種履歴を自治体側が情報としてもつことは無いそうです。 求めに応じて接種証明は発行するそうですが。（個人情報に対する考え方の違い）
米国では最近、接種率を上げるために、1.5億円相当が当たるクジを実施する州も あるやに聞きます。7月4日を目処に接種目標を掲げているようです。 わが国は、伝統的にワクチン接種を巡るトラブルなどもあって、どの程度まで 接種率が行くのか注目されるところですね。 （γ） 2021/06/21(月) 21:20
試算に使ったコードを参考までに。（VBAではありませんので注意下さい）
using CSV using DataFrames using JuMP using GLPK using Random
function test()
person = 10000
d = 11
Random.seed!(4649) # 乱数のシーズ（乱数固定の目的）
# 接種希望日(テストケースの作成)
req = zeros(Int32,person,3)
for k in 1:person
req[k,:] = randperm(d)[1:3] # 1〜11の中からランダムに3個取り出す
end
# 優先度
priority = zeros(Int32,person)
for k in 1:person
priority[k] = rand(1:3) # 1〜3をランダムに入れる
end
# 各日の接種人数制約
power = zeros(Int32,d)
power .= 1000 # 平常は1000人
power[1] = 500 # 初日は 500人
power[2] = 700 # 2日目は 700人
# 事前に満足度係数を算定しておく
satisfaction = zeros(Float64,person,d)
for p in 1:person
ratio = [1.2, 1.0, 0.8][priority[p]]
for k in 1:d
satisfaction[p,k] = -1000.0
req[p,1] == k && ( satisfaction[p,k] = 100.0 * ratio)
req[p,2] == k && ( satisfaction[p,k] = 80.0 * ratio)
req[p,3] == k && ( satisfaction[p,k] = 30.0 * ratio )
end
end
model = Model();
set_optimizer(model, GLPK.Optimizer);
# 使用変数
@variable(model, x[1:person,1:d], Bin) # 0か1をとる二次元配列
# 制約条件
@constraint(model, sum(x,dims=2) .== 1 ) # 職員はどこかの接種日を割り当てる
@constraint(model, sum(x,dims=1)[1,:] .<= power ) # 接種日ごとの制限人数内
# 目的変数は各人満足度の総合計（これを最大化）
@objective(model, Max, sum( (satisfaction[p,k] * x[p,k]) for p = 1:person, k = 1:d) )
optimize!(model) # 最適化ツールを用いた実行
# 結果の取り出し
kekka = zeros(Int32,person,d)
for p in 1:person, k in 1:d
kekka[p,k] = Int32(value(x[p,k]))
end
# 結果のCSV保存
DataFrame(kekka) |> CSV.write("output1.csv",delim=',',writeheader=true)
DataFrame(req) |> CSV.write("req1.csv",delim=',',writeheader=true)
DataFrame(satisfaction) |> CSV.write("satisfaction1.csv",delim=',',writeheader=true)
priority2 = reshape(priority,size(priority)[1],1)
DataFrame(priority2) |> CSV.write("priority1.csv",delim=',',writeheader=true)
end
@time test()
（γ） 2021/06/21(月) 21:24
[ 一覧(最新更新順) ]
YukiWiki 1.6.7 Copyright (C) 2000,2001 by Hiroshi Yuki.
Modified by kazu.