国際会議における部屋割り当て問題のモデル化とその解法
M2013SS003 伊藤喜紀
指導教員：佐々木美裕

1

はじめにかる. 本研究ではこの同じ名のセッションを今後同名セッションという名で呼ぶ.

世界各地で開催されている国際会議の規模は, 大学の部屋を数部屋使って行う小規模なものから, 世界中から研究者が集まる大規模なものまでさまざまである. 大規模な国際会議では, 複数のホテルや国際会議場を発表会場として使用することもある. このような状況の中, 各セッションに参加する人の発表会場間や部屋間の移動を考慮すると,関連が高い内容のセッションが近い部屋で開催されることが好ましい.

図 1 INFORMS の時間割の一部

本研究ではこれらの点に着目し, 各セッションが行われる時限は既知とし, 関連性の高いセッションが全日程を通してなるべく近い部屋に割り当てられるように, 国際会議全日程の最適な部屋割り当てを求めるモデルを提案する.
本研究では, 国際会議における部屋割り当て問題に対し2 つのモデル化を提案し, それらのモデルの精度の検証を行う.

2

国際会議における部屋割り当ての現状

OR の分野でも大規模な国際会議である INFORMS Annual meeting(以下 INFORMS とする) を例に説明する.
INFORMS は毎年開催されている国際会議であり, その前
身は TIMS/ORSA という国際会議である. TIMS/ORSAの開催期間を含むと, INFORMS は 50 年以上前から開催されている歴史のある国際会議である. その長い歴史の中で, INFORMS の 1 回の開催で行われるセッション数は徐々に増加している. 1995 年に開催された会議では 1 時限帯に行うセッション数が 30 にも満たなかったのに対し,2011 年に開催された際には 1 時限帯でセッション数が 69と 1995 年と比べてセッション数が倍以上となっている.
またセッション数の増加に伴い発表も 1 会場ではなく複数の会場を用いて行われている. このセッション数と発表会場の増加の結果, 参加者の移動の負担も年々増していくことになる.
次に 2011 年に開催された INFORMS の時間割の一部の
図 1 を用いて, 国際会議の大まかな流れを説明する. 2011
年の INFORMS は日曜日から水曜日の 4 日間で開催され,図 1 の 1 行目の「SA」は日曜日の 1 時限目であることを示している. 「SA」の次の時間帯は「SB」であり, アルファベットの 1 文字目が曜日を, 2 文字目が時限を表している.
また 1 日の時限数は最高で 5 時限となっている. そして各時限帯には各セッションが割り当てられており, セッションごとに割り当てられた部屋が Room に記載されている.
図 1 はその一部であるが, 本来ならば各時限帯にはそれぞれ 69 のセッションがある. また「SA」, 「SB」の時限帯を見ると同じ名前のセッションが存在していることが分

3

理想的な割り当てのための制約

2 節で説明した国際会議の現状を踏まえたうえで, 参加者の利便性を考慮し, 全てのセッションを部屋に割り当てるために必要とされる制約を 2 点説明する. その際の前提条件として本研究では各セッションが行われる時間をすでに既知とし, 部屋の割り当てのみを考える.
1 同時限帯で関連の高いセッション同士は, なるべく近⃝しい部屋に割り当てる.
2 1 つの部屋に着目した時, 異なる時間帯, 曜日に存在す⃝

る同名セッションは同部屋に割り当てる．
1 の制約は, 同時限帯に存在するセッションの関連性を⃝考慮した制約である. 大きな国際会議では多くの参加者が集まる. その参加者らが研究しているテーマは異なっており, 参加者それぞれが興味のあるセッションが存在するはずである. セッション同士の関連性を考慮して同時限帯の全セッションを各部屋に割り当てることで, 同時限帯の参加者が, 自分の興味のある別のセッションへと移動することの負担を減らすことが出来る.
2 の制約の説明を行う. こちらは異なる時間帯で同次に⃝名セッションが存在することに配慮した制約である. 複数の同名セッションが異なる時間帯に存在している時, それらのセッションを同部屋に割り当てることで参加者の次の時限帯の移動も少なく済み, 参加者の混乱を減らすことが出来る. 上記した 2 点を考慮して, 本研究ではこの国際会議部屋割り当て問題に対し 2 つの定式化を行った.

41 時限における部屋割り当て問題

3 節で説明した制約を考慮した定式化を行った結果, 2 次割り当て問題の手法を用いることで, 国際会議における 1時限の部屋割り当てを行えることが分かったため, 以下にその詳細を示す.

2 節にあるように, ある時限帯に 69 のセッションが開催定式化

4.1される場合もある. 現状 CPLEX で求解するには限界があ

関連度と部屋間の距離は定数であり, 値が小さいほど関連が高く, 部屋間の距離が短いものとする.

[2] や柳浦, 茨木 [4] による著書や二次割り当て問題のライブラリーとなっている QAPLIB[3] などを参考に 3 つの近似解法（多出発局所探索法と禁断探索法, GRASP 法）を実装した. 詳細に関しては予稿のページの都合上省略する.

記号の定義S : セッションの集合
R : 部屋の集合
P : セッション s1 ∈S とセッション s2 ∈S の関連度
D : 部屋 r1 ∈R と部屋 r2 ∈R の距離
変数

二次割り当て問題として 1 時限の割り当てを行った結果を踏まえ, 国際会議全日程の割り当て問題のモデル化を行う. 問題を小さくするためにセッションと部屋をグループ割り当てる

化してモデル化することで, 変数を減らし計算の負担を少

0 : 上記以外

Minimize∑ ∑ ∑∑なく手法の提案をする.

6.1
Ds1 s2 Pr1 r2 xs1 r1 xs2 r2 ,(1)s1 ∈S s2 ∈S r1 ∈R r2 ∈Vi \r1s.t.
∑

セッションと部屋のグループ化

ここでこの発見的解法のモデル化に必要となるセッションと部屋のグループ化について図 2 を用いて説明する. 以下セッションを i ∈ I としそれぞれのグループをセッショr ∈ R, (2)xsr = 1,s∈S∑

国際会議全体の部屋割り当て問題6 1 : セッション s∈Sht を部屋 r∈R に

xsr =ることが分かった. よって本研究では久保, J.A. ペゾロソングループと部屋グループと名づけ, それぞれの記号をセッショングループは j ∈ J, 部屋グループを k ∈ K と定義する.

s ∈ S, (3)xsr = 1,r∈R

セッショングループあるセッションから見て関連が高いセッションが集まっxsr ∈ {0, 1},s ∈ S, r ∈ R (4)目的関数 (1) の意味は, 各セッション同士の優先度と部屋間の距離を最小化する, となる．制約条件 (2), (3) は各セッション s（s∈Sht ）に各部屋 r（r∈R）を必ず 1 つ割り当てる, となり, 制約条件 (4) はバイナリ制約である.

たグループのことをセッショングループとして定義する.
図 2 でセッショングループ j1 ∈ J はセッション i1 ∈ I から見て関連が高いセッションが集まったグループになる.
部屋グループ
近しい部屋同士が集まった集合を部屋グループとして定義する. 何らかの近さの基準を設定し, その近い部屋同士が集まったグループになる.

5

最適化ソフトウェアによる計算実験

4 節で説明した定式化の計算実験を行った. 使用した最適化ソフトウェアは IBM ILOG CPLEX Optimization Studio 12.5.1.0 であり, 計算環境は (プロセッサ：Intel(R)Core(TM)i7 CPU 960 @ 3.20GHz 3.20 GHz
実装メモリ：24.00 GB) となる.
n=セッション数=部屋数とし, CPLEX で計算実験を行う. 定数 P , D に関しては今回はランダムデータを使用した. また目的関数 (1) は非線形であるが, 参考文献 [1] を参考に線形化を行っている.
表 1 CPLEX による計算実験結果

n5

計算時間

1 秒以下

10
1 分 35 秒

6.2

各セッションを各部屋グループに割り当てる

図 2 を用いて発見的解法の考え方を説明する. 使用する記号は 6.1 節と同じ記号を用いる. またセッション i1 ∈ Iと i2 ∈ I の関連度を Pi1 i2 とし, セッションとセッショングループ間の枝の重みを Gij とする.
下に記された図 2 ではセッション i∈I が色分けされている. ここではこの色分けされたセッション同士が関連度

Pi1 i2 が高く, 同じ部屋グループに割り当てられ方が好ましいことを示す. 図 2 ではセッション i1 とセッション i4 な
どのセッション同士が同じ部屋グループに割り当てられることが好ましい. この時, セッションとセッショングルー
プ間の枝の重み Gij を Gi1 i4 =Gi4 i1 =P i1 i4 とすることで20

各セッションから見てどのセッションの関連性が高いのか不明

どうかの重み付けを行う. 同時限に同名セッションが割り当てられている場合や, No Session となっている場合もあn=5, n=10 の場合には 2 分を超えることなく解が出たのに対し, n=20 の場合には 1 週間程 CPLEX で計算を行っても解を求めることが出来なかった.

る為, あるセッション i ∈ I から見て同名セッションであるならば重みを重く, No Session であるならば重みを最低の値に設定する.

上記の重みを全ての枝 Gij に設定し, 部屋グループの部ンとセッショングループ間の枝の記号に関しては 6.1 節と屋数の容量制約を満たすよう, セッショングループに割り同じ記号を用いる. 今回は予稿のページの都合上, 手順 1当てられるセッションの重みの最大化を目指すことで各の基本的な定式化のみ示す.

セッションの関連性の最大化を行う手法となる.

Sk : 各部屋グループの部屋数
以下は決定変数 1 : セッション i∈I はセッショングループj∈J に割り当てられた
0 : 上記以外
yjk : セッショングループ j∈J から部屋グループ k∈K に

xij =

割り当てられたセッション数 1 : セッショングループ j∈J から部屋グループzjk =

0Maximize∑∑k∈K にセッションが割り当てられた: 上記以外Ｇij xij ,図 2 発見的解法の考え方

s.t.
∑
6.3

問題の段階化6.2 節は 1 時限の割り当て問題となる. この問題を参考(5)i∈I j∈Ji ∈ I, (6)xij = 1,j∈Jに, 国際会議割り当て問題を段階化し, 全てのセッション∑を各部屋グループに割り当てる方法について説明する. 各i∈Ixij =∑yjk ,j ∈ J, (7)k∈K

セッションを部屋グループに割り当てる問題を以下グループ割り当て問題と記述する.

∑記号の定義H : 開催日の集合k∈KT : 時限の集合
Sht : 第 h∈H 日の時限 t∈T に開くセッションの集合
R : 部屋グループの集合

zjk ≤ 1,j ∈ J, (8)yjk ≤ M zjk ,j ∈ J, k ∈ K, (9)yjk ≥ zjk ,j ∈ J, k ∈ K, (10)xij ≤ xjj ,i ∈ I, j ∈ J, (11)段階の手順
手順 1 開催日 h1 ∈H の時限 t1 ∈T を選択し, 第 h1 ∈H 日の時限 t1 ∈T のセッション Sh1 t1 を各部屋グループ r∈Rに割り当てるグループ割り当て問題を解く.
手順 2 時限 t∈T を更新し, 次の時限 t2 ∈T においてグループ割り当て問題を解く. その時, 前時限 t1 ∈T に割り当てられたセッションと同名のセッションが存在してい∑yjk ≤ Sk ,k ∈ K, (12)xij ∈ {0, 1},i ∈ I, j ∈ J, (13)zjk ∈ {0, 1},j ∈ J, k ∈ K (14)j∈Jるならばそれを考慮したグループ割り当て問題 (手順1 以降のグループ割り当て問題) を解く.
手順 3 手順 2 を反復し, 全ての h∈H の全ての時限 t∈T で開かれる全セッション Sht を各部屋グループ r∈R に割り当てる.
手順 4 全ての h∈H の全ての時限 t∈T で開かれる全セッション Sht を各部屋に割り当てる部屋割り当て問題を解く.

6.4

グループ割り当て問題の定式化

記号の定義

目的関数 (5) の意味は, セッション i ∈ I とセッショング
ループ j ∈ J 間の枝の重み Gij を最大化することを意味する. 制約条件 (6) は, 各セッション i ∈ I は必ずいずれかのセッショングループ j ∈ J に割り当てられることを表わしている. 制約条件 (7) は, 各セッショングループ j ∈ J に割り当てられたセッション数と各部屋グループ k ∈ K に割り当てられたセッション数が等しいことを表している.
制約条件 (8) は, 各部屋グループ k ∈ K には必ず 1 つの問 題 を 定 式 化 す る に あ た り, 以 下 の 記 号 を 定 義 す る.

セッショングループ j ∈ J からセッション i ∈ I が割り当セッション, セッショングループ, 部屋グループ, セッショてられることを表している. 制約条件 (9)(10) は, 決定変数 zjk の為の制約条件である. 制約条件 (11) は, セッショれる可能性も十分にある.

ングループ jn ∈ J に, いずれかのセッション i ∈ I が割り

上記した中でも 1 番難しい問題が関連度の設定であると当てられるならば, 必ずそのセッショングループ jn ∈ J に本研究では考える. 過去の各セッション間の移動人数や,はセッション jn ∈ I が割り当てられるようにすることを研究論文の参考文献の傾向から関連度を作成する方法があ表している. 制約条件 (12) は, 各部屋グループ k ∈ K にるかもしれないが, いずれも関連度を作成するためのデー割り当てられるセッション数が, 部屋グループ k ∈ K の部

タとして得ることが非常に困難となる.

屋数を超過しないようにすることを表している. 制約条件

(13)(14) は, バイナリ制約である.

8

実際のデータを用いた計算結果

7

おわりに国際会議の部屋割り当て問題を, 2 つの視点からモデル

2011 年度に開催された INFORMS のセッションを用いて計算実験を行った. 今回は日曜日のデータを用いて 1 日化をし, 最終的には割り当て結果として結果を確認することが出来た.の割り当てを行った結果を示す. データの詳細は以下の表

関連度や実際の参加人数などははっきりと分からないた

2 のようになる. また部屋グループに関してはこちらで近い部屋同士のグループを作成した. 関連度に関しては, 実際に数値として得ることが難しいため, 手作業で作成したデータとなっている.

め, 実際の時間割と比較するには見比べて判断するしかな
いが, 今回の研究で得た結果は実際の時間割と割り当て傾向が大きく変化しているところは見られなかった. 今後の課題としては, 7.2 節で上げた問題点に対応していくことが挙げられる.

表 2 日曜日のデータの詳細

参考文献

時限数

セッション数

部屋数

部屋グループ数

4696917[1] E.M. Loiola, N.M.M. de Abreu, P.O. BoaventuraNetto, P. Hahn, T. Querido（2007）: A survey for thequadratic assignment problem , European Journal
日曜日は 4 時限あるため, 今回は 1 時限目である「SA」
of Operational Research 176, 657-690.
を手順 1 として解き, その解を参考に以降の時限の割り当[2] 久保幹雄, J.P. ペドロソ（2009):『メタヒューリスティてを行った. 結果を全て掲載するのはページの都合不可能
クスの数理』, 共立出版株式社.
なため, それぞれの計算時間と実際に計算し出力した結果[3] QAPLIB - A Quadratic Assignment Problem Liの問題点のみ説明する.
brary (http://www.opt.math.tu-graz.ac.at/qaplib/)
7.1 各データの計算時間[4] 柳浦睦憲, 茨木俊秀 (2001):『組み合わせ最適化ーメタ
計算時間は以下の表 3 のようになった. 計算環境に関し戦略を中心としてー』, 朝倉書店.ては 5 章の環境と同じになる.
[5] Y. Li, P.M. Pardalos, M.G.C. Resende (1994): A
表 3 各データの計算時間
データ

計算時間

ＳＡ

5 秒 1748 秒 33
20 秒 50
13 秒 48
1 秒 47ＳＢ
ＳＣＳＤ
部屋割り当て問題

7.2

結果の問題点
本研究のモデルは, 実際のセッション間の移動人数や聴講数を詳細に知ることが難しいために, 部屋の容量制約を考慮しないモデルとなっている.
また今回は, 関連度に関してもあるセッションに対して各セッションがどれだけ関連が高いかを正確に数値として表してはいない. そして部屋の距離といった重みをつける部分に関しても重みの設定が明確ではないため, 重みの設定を変更した時, 割り当て内容が大きく変わる結果が得ら

greedy randomized adaptive search procedure for thequadratic assignment problem , In P. Pardalos, H.
Wolkowicz (eds.), Quadratic assignment and relatedproblems, 237-261.