概要

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()