5.

算を行なし、，比較を試みた.結果として，数値計算

NP に対する優位性が確隠され，PO ,BR のPO と BR とでは，比SI の値とク較する条件をどう決めるかで評価が変わることがわかっラスごとの呼損率の関係や，客の到着率と，呼損率の上た.なお，詳しい条件および結果については，本論文を限を保証するために必要なパップアサイズとの関係につ参照されたい.

M=2 ， 単位サービス

いて，NP , PO ,(b 1 = 1)

として ，BR それぞれの場合について数値計

襲撃学生論文賞受賞論文

要約繊般化グルーピンゲ問題
伊藤稔(東海大学大学院工学研究科経営工学専攻現所属:日本ユニシス)

指導教官羽田隆男助教授

1.

,(1 ，対象 i が，対象 j を中心としたグループ

はじめに

Xij=に含まれる場合\.0，その他の場合多数の対象を，対象聞の類似度に注目して，複数のクとすると，一般化グルーピング問題 (G) は，同次クララスターに分割する問題をとりあげる.

多数の対象を，その対象間の類似度に注目してグルースタ}問題における各グループに，L:̲ GtXij;孟 C， jEN

プ分けをする問題は，同次クラスター問題として古くか'ENら一般に知られており，統計学等の分野に応用されていただし ，ai ( 主主 0，iEN): 対象 t が使用する資る.一方，配送計画や工程のライン編成問題など経営工源の量学的な諸問題に，この向次クラスター問題を適用しようC

主~a i> iEN): 各グループが使用とすると，分割するクラスター数の制約だけでなく，各クラスターごとに使用できる資源に制約が加わる問題となることが多い.

できる資源の総量であるナップザック制約を付け加えて得られる問題，

min L:L: du Xu

たとえば，配送計画では，配送センターの商品を多数

iEN jε N

8.t.の配送先に，複数のトラックで配送しようとすると，各L:
̲̲ xiJ=I , jEN ...・ H ・・ (1)トラックが受けもつ配送先が 1 つのクラスターであり，(G)4J

ndAm 宅'・

Nd・

対象の集合 N={ 1 ， 2 ，...，1I} と，対象 i ，1}, i , jEN…… (5)を考える.

かを判断する 0-1 変数 Xjj ， jEN を，それ以外の変数

0-1 変数 Xij:をと明確に区別するため，

JE三 N 閣の類似度 d ij (値が小さいほど類似していると見なす)

制初(晋0)

C.
.
.
(2)

ここで，対象 j を中心としてグループを構成するか否

一般化グルーピング問題の解法与えられているとき，

2/ 与一

2.

a

Jf間の面からその実用性を検討する.

,

XijE三 {O ，ラスター問題を[一般化グルーピング問題 j と称し，分校限定法にもとづき，より効果的な解法を考え，計算時,21クラスター数と資源に制約のあるクZjj=h/与一

qZH

関係が資源制約となる.
本修士論文では，

jz
N
Lー内の配送先への総配送量とトラックの積載量制限とのe‑‑クラスタWZ

所有するトラック台数がクラスター数の制約，iENが以下では便宜上 0-1 変数曹 j，jEN と表現する.

解法としては，分校限定法の下界値計算に， (1)式を釘的関数に組みこんだラグランジェ緩和間短 (Ll' lx，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

百)オベレーションズ・リサーチ

を考える.そこで， 0-1 変数 Xij ，i , jEN, i*j に関ずる締約条件と， 0-1 変数 Y" jENrc..関する制約条件とに区分し ，10.①の下界値算出方法..②の下界値算出方法(Lplx， 百)を表現し直すと，(Lplx , y):λμ4+fminiZNVj(min ら (dij 一向) XijeN.f eN
刷Is.t.

lλa内j;;?'Ctl

XijE{O , 1} , iEN"。

s.
t.I:'!Ji=k'!J jE{O ,10050
対象の数 njeN

図 11}, j E Nとなる.このラグランジェ緩和問題 (Lplx， 11)

解くことのできる限界範囲の主な計算は，① 0-1 変数 Xtj の 0 ー 1 ナップザッグ問題を n4.

題解き，その値の少ないものから h 個選ぶというもので計算結果によれば，対象数が比較的小さく，グループある.

結論

数が大きい問題に対しては強い下界値の得られる①が，本論文では，上記の緩和問題以外に，下界値を求める方法としてもう 1 つ，② 0-1 変数 Xij を連続変数とした緩和問題を提案している.

逆に，対象の数が比較的多く，グループ数が小さい問題には②が，計算時間の点、で効果的であるといえる.
このことにより，問題パターンごとに下界値の算出方①と②を比較すると，①はより強い下界値が得られ，法を使い分ければ，経済的な計算時間によって大規模な分校限定法の列挙木の拡大を抑える反面回の下界値問題にも対応できることが L 、える.また，ある企業での計算に要する計算量が多い.②は，その逆である.そこ

実際の配送問題(配送先 37 カ所，トラック数 5 台)に適で，どちらの下界値計算が効果的であるか，数値実験に用したところ，実際の問題は，一様乱数を用いた数値実より検証している.さらに，劣勾配法の導入による下界験よりはるかに効率的に，わずか 37秒程度で解けた.こ

値の強化と，のようなことから，本論文で提案している解法は，十分ヒューリスティックな考えにもとづく，上界値の強化も行なっている.に実用に耐えられるものであると判断している.

3. 数値l実験の結果

参芳文献

一般化グルーピング問題 (C) を解く上で，本研究で提案した下界値計算法や上界値強化は，効果的であるという結果が得られた.また，対象の数やグループ数が増[1] 今野浩，鈴木久敏編:整数計画法と組合せ最適化，

日科技連，

OR ライブラリー， No.7 , (1982)[2] Fisher , M. L., and Jaikumar , R.: “ Aえると，当然ながら次第に解きにくくなることがわかっ

Generalized AssignmentHeuristicforVehicle

た‘

Routing ヘ Networks ，

ここで，計算結果を整理するため，対象の数 n とグループ数 h を変化させ，各々の n と h の組合せに対して問Vol. 11 , (1981) , pp.109‑

124[3] Mulvey , J. M. , and Crowder , H. P.:

題の係数を一様乱数で生成した複数の問題群に対して，“ Cluster Analysis:AnApplicationof Lagranｭ数値実験を行なっている.以下のグラフは，下界値算出

gianRelaxation" , Manage. Sci. Vo 1. 25 , No.4,

方法において①，②どちらが有効であるか判断するため，(1979) , pp.
329‑
340.

対象の数と，グループ数の 2 つのパラメータを増加させていき，そのほとんど(1 0例中 8 例)が規定時間内(5[4] Fisher , M. L.:“ The Lagrangian Relaxaｭ
tionMethodforSolvingIntegel'Programming分)に解ける限界を表わしている.ちなみに，使用した

Problemsヘ Manage.

計算機は NEC 大型コンビュータ SX-1E である.

pp.1‑I8

1992 年 IL 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

Sci , Vo 1. 27., No.1 , (1981) ,(51)5&1