1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

OR-Toolsで部屋割り当て処理を実装する

Last updated at Posted at 2025-07-10

概要

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?