PuLP を使った診察担当院の自動割り振りの検証

はじめに

オンライン診療のバックエンドを担当しています。オンライン診療の予約は件数が多いため、1 つのクリニックではなく、グループを構成する複数のクリニックが分担してオンライン診療を行っています。この分担を決める割り振り作業は、各クリニックの負荷状況（キャパシティ）を考慮し、クリニックの方が手動で行っていたため、負担になっていました。この負担の解決方法として、予約に対して診察担当院を自動で割り振る機能の検証を行いました。

準備

診察担当院と予約を表すデータを用意します。

診察担当院

ある予約時間帯に診察できる枠を定義します。 capacity は診察可能な医師のリソースによって決まっています。また、担当するクリニックは診察可能な診療科（ available_department_ids ）が異なります。

具体的な例として、各クリニックを次のように定義します。

• CLINIC_A は内科と皮膚科のみ診察可能で、ある時間枠で 1 件の診察ができる
• CLINIC_B は内科とアレルギー科のみ診察可能で、ある時間枠で 1 件の診察できる
• CLINIC_C は内科と皮膚科とアレルギー科のみ診察可能で、ある時間枠で 2 件の診察ができる

ソースコードで表すと、次のようになります。

UNASSIGN_NAME = 'unassigned'
MAX_CAPACITY = 9999

# 診療科
departments = {
  'Department_1': '内科',
  'Department_2': '皮膚科',
  'Department_3': 'アレルギー科',
}

# 診察担当院
clinics = [
  {
    # CLINIC_A は内科と皮膚科のみ診察可能で、1人の医師が診察できる
    'name': 'CLINIC_A',
    'available_department_ids': [1, 2],
    'capacity': 1
  },
  {
    # CLINIC_B は内科とアレルギー科のみ診察可能で、1人の医師が診察できる
    'name': 'CLINIC_B',
    'available_department_ids': [1, 3],
    'capacity': 1
  },
  {
    # CLINIC_C は内科と皮膚科とアレルギー科のみ診察可能で、2人の医師が診察できる
    'name': 'CLINIC_C',
    'available_department_ids': [1, 2, 3],
    'capacity': 2
  },
  {
    # UNASSIGN_NAME は診察担当院が決まっていない「未振り分け」を表す
    'name': UNASSIGN_NAME,
    'available_department_ids': [1, 2, 3],
    'capacity': MAX_CAPACITY
  },
]

予約

今回、以下の予約に対して自動割り振りを試します。

• 10:00: 予約 3 件
• 10:15: 予約 4 件

それぞれの予約に対する診療枠は以下の通りです。

id	診察開始時刻	診療科	診察担当院
1	10:00	内科
2	10:00	内科
3	10:00	皮膚科
4	10:15	アレルギー科
5	10:15	アレルギー科
6	10:15	アレルギー科
7	10:15	アレルギー科

これらの予約と診察枠のセットに対して、診察担当院を自動で決めたいと思います。

PuLP を使った最適化

最適化問題を解くためのツールとして、PuLP と呼ばれる Python 用のライブラリがあり、これを用いることで担当院の割り振りを線形計画法として解くことができます。
PuLP を使って最適化問題を解く場合、目的関数と制約条件を決める必要があります。

制約条件としては、 CLINIC_A から CLINIC_C と unassigned のいずれかが割り当てられます。
目的関数は、未振り分けの予約件数が最小になるようにします。しかし、各時間帯には、診察担当院の診療科が一致している必要があります。例えば、 CLINIC_A は内科と皮膚科のみ診察可能なので、内科と皮膚科の予約にのみ割り当てることができます。そのため、目的関数には対応可能な診療科のみ割り当て可能であること、各院の予約キャパシティを超えないことを加えています。

def auto_assignment(clinics, reservations, department_ids, reserved_at_list, all_list):
  x = pulp.LpVariable.dicts('assignment', all_list, lowBound=0, upBound=1, cat=pulp.LpInteger)
  assignment = pulp.LpProblem('assignment', pulp.LpMinimize)

  # 目的関数: 未振り分けの割当が最小になること
  assignment += pulp.lpSum([x[table] for table in all_list if UNASSIGN_NAME == table[0]]), f"Target"

  # 予約に必ず1院は割り当てられること
  for reservation in reservations:
    reservation_id = reservation['reservation_id']
    assignment += (pulp.lpSum([x[table] for table in all_list if reservation_id == table[2]]) == 1, f"Reservation_{reservation}")

  # 各院でキャパシティ以内で割り当てられること
  for clinic in clinics:
    name = clinic['name']
    capacity = clinic['capacity']

    # 未定の場合はキャパシティの制限を行わない
    if name == UNASSIGN_NAME:
      continue

    for reserved_at in reserved_at_list:
      assignment += pulp.lpSum([x[table] for table in all_list if (name == table[0]) and (reserved_at == table[4])]) <= capacity

  # 特定のクリニックは対応可能な診療科にのみ割り当てられること
  for department_id in department_ids:
    assignment += pulp.lpSum([x[table] for table in all_list if not int(table[3].split('_')[-1]) in json.loads(table[1])]) == 0, f"Department_id_{department_id}"

  assignment.solve()
  return [table for table in all_list if x[table].value() == 1.0]

結果

上記を実行すると、以下のような割り当て結果が得られます。
10:00 の３つの予約には、それぞれ CLINIC_A と CLINIC_B と CLINIC_C が割り当てられています。また、10:15 の４つの予約には、 CLINIC_A は診療科が一致しないため割り当てされていません。かつ、 CLINIC_B と CLINIC_C のキャパシティを超えているため、 unassigned に割り当てられています。意図した割り振りが行われていることが確認できました。

id	診察開始時刻	診療科	診察担当院
1	10:00	内科	CLINIC_A
2	10:00	内科	CLINIC_B
3	10:00	皮膚科	CLINIC_C
4	10:15	アレルギー科	CLINIC_B
5	10:15	アレルギー科	CLINIC_C
6	10:15	アレルギー科	CLINIC_C
7	10:15	アレルギー科	unassigned

まとめ

今回は、最適化問題を解くためのツールとして、PuLP を使って診察担当院の自動割り振りを検証してみました。目的関数を設定することで、各院のキャパシティを超えないように、かつ、診療科が一致するように割り振ることができそうです。

実際のコードは Colab に置いていますので、興味のある方はぜひ試してみてください。