蘭学生論文賞受覚論文

費畢沙轟飽割当問題駒鯛濾
密林 裕囲郎（東京大学大学院工学系研究科計数二L学専攻 現所属：㈱システム計画研究所）
指導教官 松井知己助教授、、∴、．、∴∴−、
本論文では組合せ最適化問題としてのチャンネル割当問題を紹介し9 整数線形計画法を用いた厳密解法，5−近似解法9 発見的解法を提案する。その主な成果はアルゴリズムの提案と計算実験であるが，本稿では紙面の都合上，要約にとどめる。
・・ こ∴：芋÷ナ1：：・

近年9 携帯電話の普及にともない，大規模なチャンネル割当問題を解く必要が生じてきた①

チャンネル割当問題とはすでに配置されている携帯電話の基地局に対して，電波の干渉を考慮するという条件の元で，チャンネルを割り当てる問題である。ちなみに，携帯電話の基地局は現在関東平野に約10，000

図1 チャンネル割当問題の例個ある。本研究では，電波の干渉を離散化して表現し

本節では厳密解法を一から構築するのではなく，チた問題を扱う㊥ すなわち，基地局を頂点とし，干渉のャンネル割当問題を整数線形計画法に定式化し既存の存在する基地局間を枝で結んだグラフを用いて問題をバッケーージソフトウェアを用いて解を求める。チャン

表す白 またチャンネルの割当は，グラフの頂点に自然ネル割当問題は以下の整数線形計画問題に定式化され数を割り当てることで表現する。この問題を組合せ・最る。目的関数値の上界を祝，下界を／とする。

適化問題としてモデル化した問題が以下の問題である。
辿：単純無向グラフGと自然数の枝重み。

乙ど −； ∴・′、 ∴・∴∴一■

s．t． ∑∬く′＝1，J＝g

旦堕：Gの頂点に割り当てられた自然数の最大値の最づ、化．

∑（∬乙ブlブ∈S）≦1（∀ノ∈C，S∈払），∑（∬zソ＋∬乙州lダ∈S）≦1（ノ∈C，S∈￠2），

範型：グラフGの各頂点に自然数を割り当てる。ただ∬ゴノ≦yJ（∀才∈Ⅴ，∀ノ∈C），

し重み彪の辺で隣接する頂点対に割り当てる自1≧机＋1≧…≧〝〟，

然数対はその差が彪以上でなければならない．

諾わタめ∈軋1）（∀グ∈y，∀ノ∈C）．

この間題をチャンネル割当問題と呼ぶ。匝川はチャ

ただしC＝（1ブ…タ2プ？）であり，Ql，￠2は各々グラフ

ンネル割当問題の例である。太い線は重み2の辺を，（1『，gl）と（y，屈2）の極大クリークの族である。gl（g2）

細い線は重み1の辺を表している。数字は割り当てらはG中の重み1（2）の枝集合を表している。ⅤはGの頂れたチャンネルである。本論文では枝重みとして1ま点集合を表している。上記の整数線形計画問題を既存のたは2の2種類を持つ問題のみを扱うが本論文で得らパッケージソフトウェア（1p＿SOlve2．0）を用いて解いた。

れた結果の多くは一般の重みを持つ問題に拡張できる。

上記のように極大クリークによる不等式などを導入

チャンネル割当問題ほ頂点彩色問題を特殊な場合とすることで，頂点数10の問題例を0．1秒程度で解くこして含む。よってチャンネル割当問題はNP一因難でとが可能になったが，頂点数25の問題例を解くには約あるひ 本論文では，厳密解法，近似解法，発見的解法

1時間を要した。のそれぞれを提案する。
3① 厳密解法
鯛穏。近似解法
本論文では 9 近似解法として以下の頂点除去法を提© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

案し，特定の枝重み付きグラフに対して5−近似解法で案を行ったが本稿では省略する．また本論文では局所あることを証明した．

探索を用いた改善法を2つ提案した．

頂点除去法

改善法1

与えられたグラフにおいて，頂点〃に接続する重み概要の説明にとどめる．すでに可能解が得られてい1の辺の数をd（〃），重み2の辺の数を品（〃）とする．

るとする．チャンネルに頂点を割り当てているとみな払（〃）＋3（あ（〃）が最大となる頂点〃をグラフから除去す

す．一番大きなチャンネルに割り当てられている頂点る．得られたグラフにおいて払（〃）＋3（あ（〃）を再び計を，ランダムに選んだ別のチャンネルに割り当てる．

算しそれが最大となる頂点を再び計算しそれをグラフ

チャンネル制約を満たさなくなる頂点が出現したらそから除去する．以上の操作をグラフが空になるまで繰れらをまとめて別のチャンネルに割り当てる．これをり返す．元のグラフに戻し，頂点が除去された逆順に，繰り返せば，運がよければ，すべての頂点がチャンネすなわち最後に除去された頂点を最初にチャンネル割

ル制約を満たす割当を得られる．このとき割当に使う当する．このとき，制約条件を満たす範囲で最小のチチャンネルが1つ少なくなる．これを繰り返す．

ャンネルを割り当てる．

改善法2

すでに可能解が得られているとする．チャンネルに頂点数500〜10000個の問題例に対する計算実験の結果，頂点除去法による解の目的関数値は，最適値の頂点を割り当てているとみなす．チャンネルの区間を1．2倍程度でおさえられていることが分かった．

ランダムに選ぶ．選ばれた区間に割り当てられている

5．発見的解法

チャンネルをひっくり返す（区間内で逆順に割り当て

本論文における発見的解法の章では，「構築法」とる）．運がよければ区間の端とその隣に割り当てられ「改善法」それぞれを複数提案し，計算実験によって，ている頂点を同じチャンネルに割り当てることができその良い組み合わせ方について考察を行なった．頂点

る．このとき割当に使うチャンネルが1つ（あるいは除去法は構築法の1つである．もう1つの構築法の提2つ）少なくなる．これを繰り返す．

学会に届いたORの本
最近，出版社より学会宛に下記の本が届いていは，その書評をお寄せください．お読みになったます．ご興味をお持ちになり，「書評をしてみたうえで，1カ月以内に書評をお寄せくださった方い」とお考えの読者諸兄におかれましては，どうには，その本を進呈いたします．なにとぞご協力

ぞご連絡ください．郵便またはFaxにて，（1）氏をよろしくお願いいたします．加えて，読者諸氏による書評の投稿も歓迎いたします．みなさんが名，（2）連絡先住所，電話番号，（e−mailアドレス）（3）所属，（4）専門分野，（5）ご希望の書籍名
1冊，をご連絡くだされば，書籍をお送りいたしお手元にお持ちの本の中から，OR学会誌に相応ます（基本的に先着順）．その本にOR誌の読者連絡先：OR学会事務局

しいものについて書評をお寄せください．に紹介すべき所見がある，とご判断なさった場合

Fax：03（3815）3352
OR献本リスト

著

者

書

Systems：IdeasandSchemesofOptim−

izationMethodsforStrategicPlanningand Operationes Management
NonsmoothApproachto Optimization Kluwer
Problems with Equilibrium Con−

Outrata，J．Kocvara，M．
Zowe，J．

straints：Theory，Applications，andNumericalResults

DavidJ．Hand
SaulD．Jacka

Statistics in Finance

著
梅田富雄
時永祥三
菊池康也

1999年1月号

出 版 社

名OperationsResearchinTransportation

Belenky，A．S．

者

書

名

経営システム工学 研究の進め方
Excelによる経営データ処理
企業物流 地位向上の条件© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

ISDN0¶7923−5157−6

0−7923−5170−3

EdwardArnold
Limited
出 版 社
培風館

値 段
￥ 2，900

九州大学出版会￥1，800

税務経理協会￥ 2，500

45