概要
OR-Toolsというライブラリを使用してミーティングの部屋割り当て処理を実装してみようと思います。
OR-Tools
- OR-ToolsとはGoogleが開発したオープンソースの最適化ライブラリで、線形プログラミング・整数線形プログラミング・制約プログラミング様々な最適化アルゴリズムに対応し、配送ルートの最適化、リソースの割り当て、スケジューリングといった問題を解くことができます。
- PythonやC++など様々な言語で使用することができます。詳しくはこちら。
実行環境
- OS: Windows 11
- WSL2 上の Ubuntu 22.04 を使用
- Python: Python 3.10.12(venv にて仮想環境を構築)
OR-Toolsインストール
ubuntu
pip install ortools
コード
- ライブラリをインポートします。
from ortools.sat.python import cp_model
- ミーティングと会議室のデータをそれぞれ用意します。
class Room: # 会議室クラス
def __init__(self, room_id, capacity):
self.room_id = room_id
self.capacity = capacity # キャパシティ
class Meeting: # ミーティングクラス
def __init__(self, meeting_id, start_time, end_time, number):
self.meeting_id = meeting_id
self.start_time = start_time # 開始時間
self.end_time = end_time # 終了時間
self.number = number # 参加者人数
# 会議室の定義
rooms = [
Room(room_id=1, capacity=10),
Room(room_id=2, capacity=20),
Room(room_id=3, capacity=15)
]
# ミーティングの定義
meetings = [
Meeting(meeting_id=1, start_time=9, end_time=10, number=5),
Meeting(meeting_id=2, start_time=10, end_time=11, number=15),
Meeting(meeting_id=3, start_time=11, end_time=12, number=10),
Meeting(meeting_id=4, start_time=9, end_time=10, number=8),
Meeting(meeting_id=5, start_time=10, end_time=11, number=3),
Meeting(meeting_id=6, start_time=11, end_time=12, number=20),
Meeting(meeting_id=7, start_time=9, end_time=10, number=6),
Meeting(meeting_id=8, start_time=10, end_time=11, number=18)
]
- モデルを作成します。
# モデルの初期化
model = cp_model.CpModel()
- 変数を作成します。
# 変数の定義
# 変数 xに全てのミーティングiと会議室rの組み合わせをキーとして、or-toolsで使用されるオブジェクトが値として格納されます
# 部屋割処理り完了後にそれぞれ0 or 1が入ります。
# ミーティングiが会議室rに割り当てられる→x{(i, r)}: 1
# ミーティングiは会議室rに割り当てられない→x{(i, r)}: 0
x = {}
for i in range(len(meetings)):
for r in range(len(rooms)):
x[(i, r)] = model.NewBoolVar(f"meeting_{i}_room_{r}")
- 制約を追加します。
# 制約1: 各ミーティングは必ず1つの部屋に割り当てられる
for i in range(len(meetings)):
model.Add(sum(x[(i, r)] for r in range(len(rooms))) == 1)
# 以下の等式が必ず成り立つようにとsolverに命令を追加しているイメージです
# x{(i, 1)} + x{(i, 2)} + x{(i, 3)} == 1
# 制約2: キャパシティオーバーの部屋に割り当てないようにする
for r in range(len(rooms)):
for i in range(len(meetings)):
model.Add(meetings[i].number <= rooms[r].capacity + (1 - x[(i, r)]) * 1000)
# 上記と同じく不等式が必ず成り立つようにとsolverに命令をしているイメージです
# iがrに割り当てられるとき
# meetings[i].number <= rooms[r].capacity + 0
# iがrに割り当てられない
# meetings[i].number <= rooms[r].capacity + 1000
# 制約3: 同じ時間帯に同じ部屋に複数のミーティングは割り当てられない
for r in range(len(rooms)):
for i in range(len(meetings)):
for j in range(i + 1, len(meetings)):
# 時間が重複する場合
if (meetings[i].start_time < meetings[j].end_time and
meetings[j].start_time < meetings[i].end_time):
# 時間が重複するミーティングが同じ部屋に割り当てられないようにする
model.Add(x[(i, r)] + x[(j, r)] <= 1)
- 部屋割り処理を実行します。
# ソルバーの実行
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
for r in range(len(rooms)):
for i in range(len(meetings)):
# solver.Valuex(x(i,r)) == 1 -> iがrに割り当てられた
# solver.Valuex(x(i,r)) == 0 -> iはrに割り当てられていない
if solver.Value(x[(i, r)]) == 1:
print(f"部屋{rooms[r].room_id} キャパ:{rooms[r].capacity} <- ミーティング{meetings[i].meeting_id} 時間:{meetings[i].start_time}時~{meetings[i].end_time}時 人数:{meetings[i].number}")
- コード全体
from ortools.sat.python import cp_model
class Room:
def __init__(self, room_id, capacity):
self.room_id = room_id
self.capacity = capacity # キャパシティ
class Meeting:
def __init__(self, meeting_id, start_time, end_time, number):
self.meeting_id = meeting_id
self.start_time = start_time # 開始時間
self.end_time = end_time # 終了時間
self.number = number # 参加者人数
def assign_meeting_to_room(meetings, rooms):
# モデルの初期化
model = cp_model.CpModel()
# 変数の定義
# 変数 x[i][r] : ミーティングiが部屋rに割り当てられる場合=1, それ以外=0
x = {}
for i in range(len(meetings)):
for r in range(len(rooms)):
x[(i, r)] = model.NewBoolVar(f"meeting_{i}_room_{r}")
# 制約1: 各ミーティングは必ず1つの部屋に割り当てられる
for i in range(len(meetings)):
model.Add(sum(x[(i, r)] for r in range(len(rooms))) == 1)
# 制約2: キャパシティオーバーの部屋に割り当てないようにする
for r in range(len(rooms)):
for i in range(len(meetings)):
model.Add(meetings[i].number <= rooms[r].capacity + (1 - x[(i, r)]) * 1000)
# 制約3: 同じ時間帯に同じ部屋に複数のミーティングは割り当てられない
for r in range(len(rooms)):
for i in range(len(meetings)):
for j in range(i + 1, len(meetings)):
# 時間が重複する場合
if (meetings[i].start_time < meetings[j].end_time and
meetings[j].start_time < meetings[i].end_time):
model.Add(x[(i, r)] + x[(j, r)] <= 1)
# ソルバーの実行
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
for r in range(len(rooms)):
for i in range(len(meetings)):
if solver.Value(x[(i, r)]) == 1:
print(f"部屋{rooms[r].room_id} キャパ:{rooms[r].capacity} <- ミーティング{meetings[i].meeting_id} 時間:{meetings[i].start_time}時~{meetings[i].end_time}時 人数:{meetings[i].number}")
else:
print("解が見つかりませんでした")
def main():
# 会議室の定義
rooms = [
Room(room_id=1, capacity=10),
Room(room_id=2, capacity=20),
Room(room_id=3, capacity=15)
]
# ミーティングの定義
meetings = [
Meeting(meeting_id=1, start_time=9, end_time=10, number=5),
Meeting(meeting_id=2, start_time=10, end_time=11, number=15),
Meeting(meeting_id=3, start_time=11, end_time=12, number=10),
Meeting(meeting_id=4, start_time=9, end_time=10, number=8),
Meeting(meeting_id=5, start_time=10, end_time=11, number=3),
Meeting(meeting_id=6, start_time=11, end_time=12, number=20),
Meeting(meeting_id=7, start_time=9, end_time=10, number=6),
Meeting(meeting_id=8, start_time=10, end_time=11, number=18)
]
assign_meeting_to_room(meetings, rooms)
if __name__ == "__main__":
main()