数理解析研究所講究録
第 1773 巻 2012 年 218-230218

複雑な個数制約の付いた多資源一般化割当問題について
小木曽

由明 1

今堀

慎治 2

柳浦

睦憲 1

1 名古屋大学情報科学研究科計算機数理科学専攻

2 名古屋大学工学研究科計算理工学専攻

概要

本研究では，個数制約の付いた多資源一般化割当問題について考える．個数制約付き多資源一般化割

当問題とは，仕事の割当個数と資源に関する制約条件の下で，複数の仕事を複数のエージェントに割り当て，割当に伴うコストを最小化する問題である．個数制約は，各エージェントに割り当てられた仕事数が指定された候補のいずれかでなければならないというものである．また，資源制約は，各エージェントに割り当てられた仕事が消費する資源量の合計がそのエージェントの資源容量を超えてはならないというものである．
この問題は資源数が 1 以 1–の場合は NP 困難であることが知られている．資源数が の場合については，個$0$

数制約が特別な条件を満たす場合は多項式時間で解け，一般の場合は NP 困難であることを証明した．また，この問題に対して，反復局所探索法に基づくアルゴリズムを提案した．提案手法は，大規模近傍探索法という大きな近傍を効率的に探索する手法を用いている．また，実行不可能解を探索の対象に含め，そのような解の制約違反度を評価するためのペナルティの重みを適応的に更新することで，実行可能領域と実行不可能領域をバランスよく探索する工夫を行っている．般化割当問題と多資源般化割当問題のベンチマーク問題

例を基に作成した問題例に対して，提案アルゴリズムと汎用ソルバー CPLEX を適用し，比較を行った．その結果，問題例の多くにおいて提案アルゴリズムが CPLEX よりも良い結果を得ることを確認した．

くアルゴリズムを提案する．提案予法では，大規模近1傍探索法という大きな近傍を効率的に探索する手法

はじめにを用いている．また，実行不可能解を探索の対象に含個数制約付き多資源一般化割当問題に対するメタ
戦略アルゴリズムを提案する．個数制約付き多資源

一般化割当問題は， 個の仕事を $m$ 人のエージェン
トに割り当てる問題であり，各エージェントが持つ複め，そのような解の制約違反度を評価するためのペナ
ルティの重みを適応的に更新することで，実行可能領域と実行不可能領域をバランスよく探索する工夫を$n$

数の種類の資源に対する制約と割り当てられる仕事数に対する制約を満たしながら割当コストを最小化することが求められる．個数制約付き多資源一般化割当問題は，多資源一般化割当問題に個数制約を付加した問題である．また，多資源一般化割当問題は資源の種類数が 1 であるとき一般化割当問題と呼ばれ，古くから研究されている．一般化割当問題は NP 困難[11] であることが知られている．したがって，個数制
約付き多資源一般化割当問題も NP 困難である．
一般化割当問題や多資源一般化割当問題に対するアルゴリズムは数多く存在する [6,10,13,14,15].

一方，本研究で取り扱う個数制約を付加した多資源一
般化割当問題の研究は著者らが知る限りなされていない．しかし，この問題は，グループ分けなどに活用
でき，現実の応用が数多くあると考えられる．
本稿では，この問題に対して反復局所探索法に基づ行っている．さらに，解の探索を広く行うため，反復局所探索法におけるキックの操作として，あるエー
ジェントに割り当てられている仕事数を大きく変動させるシフトキックと，各エージェントに割り当てられた仕事数を変えることなく複数の仕事の割当先を変動させる交換キックを組み込んでいる．

提案アルゴリズムの性能を評価するため，一般化割
当問題と多資源一般化割当問題のベンチマーク問題

例を基に作成した問題例に対して，提案アルゴリズ
ムと汎用ソルバー CPLEX を適用し，比較を行った．
その結果，問題例の多くにおいて提案アルゴリズムが

CPLEX よりも良い結果を得ることを確認した．
本稿は以下のように構成されている．2 章で個数制約付き多資源一般化割当問題の説明と計算の複雑さの証明を行ったのち，3 章で提案アルゴリズムを説明する，4 章では計算結果を報告し，5 章でこれらについてのまとめを述べる．

219
数制約付き多資源

般化割当問題は以下のように定式化出来る:

2 個数制約付き多資源一般化割当問題

2.1$\Delta$minimizecost$( \sigma)=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}$

(1)

,

問題の定義
subject to$\sum_{j=1}^{n}a_{ijk}x_{ij}\leq b_{ik},$$\forall i\in I,$$\forall k\in K$,

個数制約付き多資源一般化割当問題の定義を(2)以下に与える．入力としてエージェントの集合$I=\{1, \ldots, m\}$とそれらに割り当てる仕事の集合$\sum_{j=1}^{n}x_{ij}\in H_{i}$$J=\{1, \ldots, n\}$, および資源集合 $K=\{1, \ldots, s\}$ が与えられる．また，各 $i\in I,$ $j\in J,$ $k\in K$ に対して仕事

をエージェント$i$

コスト$c_{ij}$

, 仕事

$j$

きに使用する資源
つ資源
源

$k$

$i$

に割り当てたときにかかるをエージェント$k$$i$に割り当てたとの量 $a_{ijk}$ , エージェント$i$に対する資源容量娠が与えられる．各資に関する制約条件として，各エージェント に$i$

計がそのエージェントの資源容量$k$$b_{ik}$の量$a_{ijk}$の合を超えてはならないという資源制約がある．また，仕事の割当個数に関する制約として，エージェント に割り当てることが可能な仕事数の集合瓦が与えられる．例えば，あるエージェント
に割当可能な仕事数が 「 個，5
$i$

$i$

$\forall i\in I$

(3)

,

,

$\sum_{i=1}^{m}x_{ij}=1$,$\forall j\in J$$x_{ij}\in\{0,1\}$,$\forall i\in I,$(4)$\forall j\in J$

.

が持

$k$

割り当てられた仕事が使用する資源,$2$

目的関数 (1) は各仕事をいずれかのエージェントに割り当てた時のコストの総和を表している．また，制約式 (2) は資源制約を表しており，左辺はエージェン
ト$i$に割り当てられた仕事が使用する資源

$k$

の合計

量，右辺はエージェント の資源 に対する容量である．制約式 (3) は個数制約を表しており，左辺はエー
$i$

ジェント

$i$

$k$

に割り当てられた仕事数，右辺は割り当て可能な仕事数の集合である．制約式 (4) は各仕事が丁$H_{i}=\{2,5,7\}$ と個，7 個」 のいずれかであるとき，

度一人のエージェントに割り当てられることを表しなる．以降では便宜上，集合ている．

$h_{i1},$ $h_{i2},$$\ldots$$H_{i}$の要素を小さい順にと記す $(h_{i1}<h_{i2}<\cdots)$ . つまり上の例$h_{i1}=2,$ $h_{i2}=5,$ $h_{i3}=7$ となる．個数制の場合，約とは，各エージェント$i$

そのエージェントに割り当てることが可能な仕事数の集合$H_{i}$のいずれかの要素と一致しなければならないという制約である．この問題の目的は，資源制約と個数制約を満たしながら各仕事をちょうど一つのエージェントに割り当て，割当に伴うコストの合計を最小化することである．出力は仕事のエージェント
への割り当て $\sigma:Jarrow I$ である．
$\sigma(j)=i$ は，仕事がエージェント$i$

23 問題の計算の複雑さに割り当てられた仕事数が$j$に割り当てられていることを表す．

なお，この問題から個数制約を除いた問題を多資源一

般化割当問題といい，さらに資源の種類数が 1 つであ

資源数 $s\geq 1$ の場合には多資源一般化割当問題はNP 困難であることが知られているため，本問題はNP 困難である．
方，資源数 $s=0$ の場合，たとえば割当可能な仕事数が 以下の偶数 (あるいは奇数) 全ての集合であ$n$るような特殊な個数制約を持つ場合にはこの問題は多項式時間で解ける．より一般的に，以下が成り立つ．
定理 1. 資源数 $s=0$ の場合，各エージェント $i\in I$の割当可能な仕事数が $[2l_{1},2r_{i}]$ 内の全ての偶数の$[2l_{i}+1,2r_{i}+1]$ 内の全ての奇数の集合，ま集合か，るとき一般化割当問題という．

たは22 定式化間で解くことが出来る．ただし$[l_{i}, r_{i}]$き，個数制約付き多資源一般化割当問題は多項式時$0\leq l_{i}\leq r_{i}$$i\in I$ント$i$と $j\in J$ の組に対して，仕事$x_{ij}=0$ の値をとる 0-1 変数 $X_{i}j$

ち，

$j$

をエージェ

に割り当てる時に $x_{ij}=1$ , そうでない時に$x_{ij}=1\Leftrightarrow\sigma(j)=i$

内の全ての値の集合のいずれかとなるとを用意する．すなわである．これを用いると，個$l_{i}$と$r_{i}$

はそれぞれを満たす任意の整数である．

証明．この問題を最小コスト完全マッチング問題に帰着することで証明する．

まず，最小コスト完全マッチング問題について以220
下に述べる．入力として， 個の頂点と $m$ 個の辺を$n$持つ無向グラフ $G=(V, E)$ が与えられる．また，各,$\chi=n-\{\sum_{i\in I_{i_{11}t}}l_{i}+\sum_{i\in I_{e.ven}}2l_{i}+\sum_{i\in I_{odd}}(2l_{i}+1)\}$

辺 $(u, v)$ は重み $w(u, v)$ を持つ．出力は辺の部分集合$M$である．ここで，部分集合 $M$ に対して，
内のどの 2 つの異なる辺も端点を共有しないとき，$M$ はマッチングであるという．また，頂点 $v\in V$ がある $e\in M$ の端点であるとき， はマッチされているといい，とくに全頂点がマッチされているマッチン$\tau=\{\begin{array}{ll}\kappa(\nu), \nu--\chi \text{が偶数である，}\kappa(\nu)-1, \text{その他．}\end{array}$$M\subseteq E$$v$

グを完全マッチングという．完全マッチングに含まれる辺 $(u, v)\in M$ の重み和をそのマッチングに対す

次に，頂点集合 $V=V_{1}$ 火。

を定義する:$E_{1}=\{(v_{j}, u_{d}^{i})|v_{j}\in V_{1}, u_{d}^{i}\in V_{2}\}$$E_{even}=\{(u_{d}^{i}, u_{d+1}^{i})|i\in I_{even}$$E_{odd}=\{(u_{d}^{i}, u_{d+1}^{i})|i\in I_{odd}$,,$d=2l_{i}+2,2l_{i}+3,$ $\ldots,$ $2r_{i}\}$ ,$E_{int}=\{(u_{d}^{i}, z_{t})|i\in I_{int}$

ルゴリズム [7], Gabow の $O(mn+n^{2}\log n)$ 時間ア

ルゴリズム [4], Mehlhorn と Sch\"afer の $O(nm\log n)$,$d=2l_{i}+1,2l_{i}+2,$ $\ldots,$ $2r_{i}-1\}$ ,ト完全マッチング問題は多項式時間で解けることが古くから知られており [3], Lawler の $O(n^{3})$ 時間アに対して以下のように辺集合 $E=E_{1}\cup E_{even}\cup E$ $dd^{\cup E_{i}\cup E}ntdummy$

るコストという．この問題の目的は，コストが最小となる完全マッチングを求めることである．最小コス$V_{2}\cup V_{dummy}$,$d=l_{i}+1,$ $l_{i}+2,$ $\ldots,$$t=1,2,$$r_{i},$$E_{dummy}=\{(z_{t}, z_{t+1})|t=1,2, \ldots, \tau-1\}$

時間のアルゴリズム [9], Cook と Rohe の $O(n^{3})$ 時$[2l_{i}, 2r_{i}]$$\tau\}$.

ここで， は仕事に対応する頂点とエージェント

間のアルゴリズム [2] などがある．

便宜上，個数制約が$\ldots,$$E_{1}$

内の全ての偶数の集合に対応する頂点間の辺で，$E_{even}$

は集合 $I_{even}$

$dd)$
$(E$。

内の同一のエージェントに対応する隣り合うとなるエージェントの集合を $I_{even},$ $[2l_{i}+1,2r_{i}+1]$$(I$ $dd)$。

内の全ての奇数の集合となるエージェントの集合

内のエー頂点間の辺である．また， は集合
ジェントに対応する頂点とダミーの頂点間の辺で，を $I_{odd},$$[l_{i}, r_{i}]$ントの集合を

内の全ての値の集合となるエージェ$I_{int}$とする$(l_{i}=r_{i}\Rightarrow i\in I_{int}$とする). つまりエージェント $i\in I_{even}$ の個数制約
は $H_{i}=\{2l_{i}, 2l_{i}+2, \ldots, 2r_{i}\},$ $i\in I_{odd}$ の個数制

約は $H_{i}=\{2l_{i}+1,2l_{i}+3, \ldots, 2r_{i}+1\},$$E_{int}$$E_{dummy}$

は隣り合うダミーの頂点間の辺である．また，各辺の重みを以下のように定める．
$w(v_{j}, u_{d}^{i})=c_{ij}$$i\in I_{int}$の個数制約は $H_{i}=\{l_{i}, l_{i}+1, \ldots, r_{i}\}$ である．

を以下のように用意する:,,$w(u_{d}^{i}, z_{t})=0$,$\forall(u_{d}^{i}, z_{t})\in E_{i}$$w(z_{t}, z_{t+1})=0$,$\forall(z_{t}, z_{t+1})\in E_{dummy}$問題の問題例を以下のように構成する．まず，各仕$V_{2}=V_{even}\cup V_{odd}\cup V_{int}$$\forall(v_{j}, u_{d}^{i})\in E_{1}$$\forall(u_{d}^{i}, u_{d+1}^{i})\in E_{even}\cup E_{odd}$のような問題例に対して最小コスト完全マッチング

意する．次に，各エージェントに対応する頂点集合,$w(u_{d}^{i}, u_{d+1}^{i})=0$
こ事に対応した頂点集合 $V_{1}=\{v_{1}, v_{2}, \ldots, v_{n}\}$ を用$I_{int}$

$t$
。

,

,

.

以下では，任意の完全マッチング $M$ から，コストが等しく実行可能な仕事の割当ることを示す．まず，頂点集合巧 と$(v_{j}, u_{d}^{i})\in M(v_{j}\in V_{1}, u_{d}^{i}\in V_{2})$$V_{even}=\{u_{1}^{i}, u_{2}^{i}, \ldots, u_{2r_{\mathfrak{i}}}^{i}|i\in I_{even}\}$

ジェント

$i$

に仕事

$j$

が定義でき

$\sigma$$V_{2}$の間の辺に対応して，エーを $\sigma(j)=i$ と割り当てる．

こ$V_{odd}=\{u_{1}^{i}, u_{2}^{i}, \ldots, u_{2r.+1}^{i}|i\in I_{odd}\}$$V_{int}=\{u_{1}^{i}, ", .

また，ダミーの頂点.

.

, u_{r_{i}}^{i}|i\in I_{int}\}$こで，完全マッチングの定義から各頂点とマッチするため，ど$vj\in V_{1}$.

$V_{dummy}=\{z_{1}, z_{2}, \ldots, z_{\tau}\}$

丁度ひとつの頂点を設

は$u_{d}^{i}\in V_{2}$の仕事も丁度一人のエージェントに割り当てられける．これらの頂点は仕事に対応する頂点 $v\in V_{1}$ とる．さらに，この割当にかかるコスト

マッチしなかった頂点 $u\in V_{int}$ をマッチさせるため

辺 $(vj, u_{d}^{i})\in M$ に対応する重み $w(vj, u_{d}^{i})$ の総和とに用意する．

なるため，マッチング $M$ の辺重みの総和と一致す$\kappa(\nu)$を$i\ovalbox{\tt\small REJECT}$

以上の最小の偶数と定義すると，用意するダミー頂点の数$\tau$

は次のようになる:る．また，任意の頂点集合 Ki,に対して，辺集合 の定義から頂点$u_{2}^{i},$$\ldots,$$E$$\nu=|V_{int}|-\sum_{i\in I_{int}}l_{i}$,$c_{ij}$$u_{2r_{i}}^{i}$$u_{1}^{i},$

の総和は，

}

$\subseteq V_{even}$$u_{2}^{i},$$\ldots,$$u_{2l_{i}}^{i}$はそれぞれ頂点 $v\in V_{1}$ との辺しか持たない．そのため $M$ においてこれらの頂点は必ず防の頂点,

221とマッチされている．さらに，頂点の定義からエーに添え字の小さい順にマッチしていき，対応する辺を

ジェント

$M$

に対応する頂点の数はエージェント$i$

割当可能な仕事数の上界いない．以$2l_{i}$以上$2r_{i}$$u_{2r_{i}}^{i}$$\ldots,$

$i$

に割り当

以下となる．また，に追加する．その結果，頂点集合 hummy の中で$V_{i}nt$にマッチされずに残る頂点の数が偶数であることを容易に示すことが出来る．そのため，これら残りの頂点同士を $E_{dummy}$ の辺を用いてマッチさせるこのうち，頂点$V_{dummy}$ の全ての頂点をマッチすることが出来とで，$M$ においは偶数個である．

る．これらの辺を $M$ に追加する．以上より任意の実$\{ui, u_{2}^{i}, \ldots, u_{2r_{i}}^{i}\}\subseteq V_{even}$$u_{2l_{i}+1}^{i},$ $u_{2l_{i}+2}^{i},$にまでしか用意されてのことから，エージェント$\}_{-}^{\wedge}$

てられた仕事数は
頂点集合$2r_{i}$$i$から完全マッチング $M$ を定てはこれらのうち偶数個の頂点が防とマッチされ，行可能な仕事の割当

残りの偶数個の頂点同士がマッチされているため，対義できる．このように定義したマッチング $M$ のコス

応するエージェント

トが割当れる．よって$i$には偶数個の仕事が割り当てら$\{u_{1}^{i}, u_{2}^{i}, \ldots, u_{2r_{i}}^{i}\}\subseteq V_{even}$

エージェント $i\in I_{even}$ には$\sigma$$\sigma$のコストと同じであることは自明である．

に対応する

以上より，個数制約付き割当問題と最小コスト完全

以下の偶数マッチング問題は最適値が一致すること，および最小に対しても同様とコスト完全マッチング問題の任意の実行可能解からなる．また，任意の頂点集合
は頂点集合防のいずに対して，頂点のれかの頂点とマッチし，残りの頂点は同じコストを持つ実行可能な割当を作成できること$2l_{1}$以上個の仕事が割り当てられる．

$V_{odd}$$2r_{i}$$\{u_{1}^{i}, u_{2}^{i}, \ldots, u_{r_{i}}^{i}\}\subseteq V_{int}$$u_{1}^{i},$$u_{2}^{i},$$u_{l_{i}}^{i}$$\ldots,$$V_{1}\cup V_{dummy}$

いずれかの頂点とマッチするため，対応するエージェ
ント に割り当てられる仕事数は 11 以上
以下となは個数制約を満たしてる．これらのことより，割当$i$$r_{i}$$\sigma$が証明出来た．問題例および解の変換に必要な計算量が多項式時間であることは自明である．したがって，定理の条件を満たす個数制約付き多資源一般化割
当問題を最小コスト完全マッチング問題に帰着出来
口たいる．すなわち実行可能な仕事の割当を得られるこ
資源数 $s=0$ の場合でも，一般にはこの問題はとが確認できた．
からコスNP 困難である．各エージェントに割当可能な仕事

トの等しい完全マッチング $M$ が定義できること

数が 2 種類に限定された単純な個数制約であっても次に，実行可能な任意の仕事の割当を示す．

$M=\emptyset$$J=1,2,$から始め，$\sigma$$\ldots,$

$n$

の順に

以下の手順に従って $M$ に辺を追加していく．仕事$i$のエージェント $i=\sigma(j)$ への割当に対応し

て，仕事
ント

$i$

$j$

$\iota$こ対応する頂点 $vj\in V_{1}$に対応する頂点$u_{1}^{i},$$u_{2}^{i},$$\ldots$ていないものの中で最小の添え字と，エージェ

のうちマッチし$d$を持つ$u_{d}^{i}$を

NP 困難であることがいえる．
定理 2. 資源数 $s=0$ の場合，各エージェント $i\in I$に割当可能な仕事数が O と 3 に限定されている場合

でも，個数制約付き多資源一般化割当問題は NP 困難である．

$M:=M\cup\{(v_{j}, u_{d}^{i})\}$ とする．どのマッチさせ，

証明．集合分割問題をこの問題に帰着することで証仕事もいずれか一人のエージェントに割り当てら明する．

れているため，頂点集合防に含まれる頂点は頂点集合$V_{2}$のいずれかの頂点とマッチすることとなる．また，割当$\sigma$が個数制約を満たしていること

集合分割問題について以下に述べる．入力として集合 $D=\{1,2, \ldots, n\}$ の部分集合 Si $(i=1,2, \ldots, m)$が与えられる．これらの中から亀の要素が重複しなから，巧の中で $E_{even}\cup E$。dd $UE_{int}$ の辺に接続しいようにいくつかのていない頂点となるようなものが存在す合せの中で，和集合がるかどうかを問う問題である．すなわち，部分集合の$(\{u_{1}^{i}, u_{2}^{i}, \ldots, u_{2l_{:}}^{i}\}\subseteq V_{even}$

など

$)$

は
$F$

全て防の頂点とマッチしている．次に，頂点集合の中で頂点集合防とマッ$\{u_{2l_{i}+1}^{i}, \ldots, u_{2r_{i}}^{i}\}\subseteq V_{even}$$S_{i}$

を選ぶ．そのような$S_{i}$の組$D$

添字集合 $X\subseteq\{1,2, \ldots, m\}$ でチしていない頂点について考える．そのような頂点$S_{i}\cap S_{i^{J=\emptyset}},$$\forall i\neq i’\in X$の数は偶数であり，添え字は連続している．よってこれらの頂点は全て $E_{even}$ の辺を用いてマッチさせる$\bigcup_{i\in X}S_{i}=D$ことが出来る．これらの辺を $M$ に追加する．Kdd についても同様である．次に，頂点集合$V_{int}$の中で頂点集合防とマッチしていない頂点を $V_{dummy}$ の頂点を満たすものがあるか否かを判定する問題で，この問
題は NP 困難であることが知られている．また，集合分割問題は各部分集合$S_{i}$の要素数が 3 つに限定され222ているとき，exact cover by 3-sets と呼ばれるが，この問題も NP 困難であることが知られている [5].
まず，集合 $D$ に対応して個の仕事を用意する．

$n$$N(\sigma)$

内に改善解$\sigma’$があればとする操作を，$\sigma:=\sigma’$

近傍内に改善解が見つからなくなるまで繰り返す方法である．ここで，近傍とは解にある操作を加えることにより得られる解集合のことをいい，近傍の定義のに対応してエージェン
次に，部分集合
ト 1, 2,は $j\in S_{i}$$m$ を用意する．割当コスト

仕方に探索の効率は大きく影響する．局所探索の結ならば O, そうでないならば 1 とする．また，各工一果得られた解を局所最適解とい

ジェント

内には改善解が存在しないことを意味している．一$S_{1},$$S_{2},$$\ldots,$$S_{m}$$c_{ij}$$\ldots,$$i$の個数制約を $H_{i}=\{0, |S_{i}|\}$ とする．

$\mathfrak{h}\backslash$, 局所最適解の近傍が存在す

般化割当問題に対する局所探索の近傍として，シフトる場合，コスト O の仕事の割当が存在することを示

近傍と交換近傍が用いられることが多い．ここで，シす．解 $X$ に含まれる各部分集合

フト近傍 $N_{shift}(\sigma)$ と交換近傍 $N_{swap}(\sigma)$ は

まず，集合分割問題の制約を満たす解

ジェント

$i$

$S_{i}\ovalbox{\tt\small REJECT}$$X$

こ対応するエー} こ部分集合の要素 $j\in S_{i}$ に対応する仕事$N_{shift}(\sigma)=\{\sigma’|$を全て割り当てる．このとき定義より割当コストは O$N_{swap}(\sigma)=\{\sigma’|$

度一人のエージェントに割り当てられ，各エージェン$i$に割り当てられた仕事数はか$0$$|S_{i}|$$\sigma$$\sigma$

先を変更することにより得られる},となる．さらに集合分割問題の定義より各仕事は丁ト

解 ’ は解 のひとつの仕事の割当
解 ’ は解 のふたつの仕事の割当$\sigma$$\sigma$

先を交換することにより得られる}となり個数制約も満たしている．よって，コスト O の仕事の割当である．これらの近傍サイズはシフト近傍が $O(mn)$ ,が存在する．

交換近傍が $O(n^{2})$ である．提案アルゴリズムでは，こ次に，コストが存在する場合，集れらの通常の近傍に加えて連鎖シフト近傍を用いた．

合分割問題の制約を満たす解が存在することを示す．

連鎖シフト近傍 $N_{chain}(\sigma)$ とは $l(l=2,3, \ldots, n)$ 個の仕事の割当$0$

各エージェント$i$$\sigma$} こ対して， において$\sigma$

$i$

に割り当て

の仕事

$j_{1},j_{2},$ $\ldots,j_{l}$の割当先をられた仕事数が正であるとき，かつそのときに限り部とする．割当 のコストがであることから，任意の仕事 とその割当先$i=\sigma(j)$ に対して $j\in S_{i}$ が成り立つ．また， が個$X=\{i||\{j|\sigma(j)=i\}|\geq 1\}$$j$$\sigma$

数制約を満たしていることから，各エージェント に割り当てられた仕事数は かであり，割り当て$i$$S_{i}$,$\sigma’(j_{1}):=\sigma(j_{l})$$|S_{i}|$と変更することによって得られる解$r=2,3,$る．つまり，
当先をエージェント

そして，仕事$j_{1}$$l$$\ldots,$に対して，仕事から$\sigma(j_{r})$の集合であ$\sigma’$$\sigma(j_{r_{-1}})$$j_{r}$の割に変更する．

の割当先をエージェント$\sigma(j_{l})$

に変

こは部分

更するということである．この連鎖シフト近傍の近の要素に対応する仕事が全て割り当てられて傍サイズは $o(n^{l})$ であり，の指数関数的に増加してられた仕事数が集合$l$$\ldots,$$\sigma$$0$$0$$r=2,3,$$\sigma’(j_{r}):=\sigma(j_{r-1}),$

分集合 S を集合分割問題の解に含める．すなわち，$|S_{i}|$であるエージェント$i\ovalbox{\tt\small REJECT}$$l$

いる． においてはどの仕事も丁度一人のエージェン

いく．そのため，改善グラフと呼ばれるアイデアをトに割り当てられていることから，集合 $D$ の各要素用いて探索対象となる解を制限する．これら 3 つのは $X$ の中の丁度ひとつの部分集合に含まれている．

近傍サイズは $|N_{s}hift|\leq|N_{swap1}\leq|N_{Ca}hin|$ となるた$\sigma$$X$ は集合分割問題の制約を満たす．以上のこ
よって，とから，集合分割問題を個数制約付き多資源一般化割

当問題に帰着出来た

口め，$N_{s}hift$の近傍内に改善解が見つからないときのみ

Nswap の探索を行い，また Nshift と Nswap のいずれの近傍内にも改善解が見つからないときのみ $N_{can}hi$の探索を行う．

提案手法では，探索空間を任意の割当

3 提案アルゴリズム$\sigma$の集合とする．すなわち制約を満たさない実行不可能解も探索の対象に含めて探索を行う．ここで，割当 において，任意のエージェント に割り当てられた仕事の集$\sigma$

3.1 提案アルゴリズムの概要$i$

提案アルゴリズムは組合せ最適化問題に対する基

本的な戦略の 1 つである局所探索法に基づいており，
反復局所探索法を基本としている．

局所探索法は，適当な初期解$\sigma$

から始め，近傍合を$J_{i}^{\sigma}=\{j\in J|\sigma(j)=i\}$

223) $\in E$ はエージェントと定義する．局所探索の中で実行不可能領域を探索す(il,

る際，以下のように実行可能解からの各制約の違反度に応じてペナルティを目的関数に付加した pcost

し，仕事$(\sigma)$$j_{2}$をエージェントから仕事 il を外$\sigma(j_{1})$に割り当てること$\sigma(j_{1})$に対応しており，の値で解を評価することにする:

pcost$j_{2}$(5)$E=\{(j_{1},j_{2})|j_{1},j_{2}\in V, \sigma(j_{1})\neq\sigma(j_{2})\}$$(\sigma)=cost(\sigma)$となる．また，各辺 (il,$+ \sum_{i=1}^{m}\sum_{k=1}^{s}(\alpha_{ik}p_{ik}(J_{i}^{\sigma})+\beta_{iq_{i}}(J_{i}^{\sigma}))$,はエージェント
エージェント$p_{ik}(S)= \max\{0,\sum_{j\in S}a_{ijk}-b_{ik}\}$$\forall i\in I,$

ト

,

仕事

$\forall k\in K,$$q_{i}(S)= \min\{||S|-h_{ig}||h_{ig}\in H_{i}\}$$\sigma(j_{1})$$\forall S\subseteq J$$\sigma(j_{1})$

) は重み

から仕事

を持ち，これを外し，仕事 を$w_{j_{1}j_{2}}$$j_{2}$$j_{1}$に割り当てたときのエージェンのコストとペナルティの変化量に対応する．

$j_{1},j_{2},$ $\ldots,j_{l}$に対する連鎖シフト操作は，改善グ

ラフ $G(\sigma)$ 内のサイクル $j_{1}arrow j_{2}arrow\cdotsarrow j_{l}arrow j_{1}$に対応する．ここでサイクルの辺の数は，対応する連,$\forall i\in I,$$\sigma(j_{1})$$j_{2}$.

$\forall S\subseteq J$

鎖シフト操作において割当先を移動する仕事の数となる．簡便のために，

ここで，パラメータ$\alpha_{ik}(>0)$と $\beta_{i}(>0)$ は各制約に$i_{r}=\sigma(j_{r}),$

対するペナルティの重みであり，探索の間に適応的に更新していく．

$r=1,2,$$l$$\ldots,$,$j_{l+1}=j_{1},$ $i_{l+1}=i_{1}$ とする．また，任意のエーとし，反復局所探索法とは，過去の局所探索で得られた局
所最適解の中の良い解$\sigma_{see}d$にランダムな摂動を加ジェント $i\in I$ と仕事の任意の部分集合 $S\subseteq J$ に対してえたものを初期解として，局所探索を反復する方法である．提案アルゴリズムでは，局所最適解$\sigma_{1opt}$に辿り着いたとき，以下のルールに従って新たな初期解を生成する．まず，pcost $(\sigma_{1opt})\leq pcost(\sigma_{seed})$ (ただに対して pcost を評価し，最新のパラメータする) であるとき，ランダムな摂動を加える解$\alpha_{ik},$$pcost_{i}(S)= \sum_{j\in S}c_{ij}+\sum_{k=1}^{s}(\alpha_{ik}p_{ik}(S)+\beta_{iq_{i}}(S))$と定義する．辺 (il,$j_{2}$) $\in E$ の重み$w_{j_{1}j_{2}}$は$\beta_{i}$$w_{j_{1}j_{2}}=pcost_{i_{1}}(J_{i_{1}}^{\sigma}\cup\{j_{2}\}\backslash \{j_{1}\})-pcost_{i_{1}}(J_{i_{1}}^{\sigma})$,$\sigma_{seed}$を$\sigma_{see}d$$:=\sigma_{1opt}$と更新する．提案アルゴリズムでは，ランダムな摂動としてシフトキックと交換キックを用いた．シフトキックは任意のエージェント

$i$

に割

り当てられている複数の仕事の割当先を変更する操作であり，交換キックは異なるエージェントに割り当となる．また，連鎖シフト操作は任意のエージェントに対してひとつの仕事を除き，新しい仕事を割
り当てることの繰り返しとなるため，各エージェン
トに割り当てられた仕事数に変化はない．つまり，$|J_{i_{1}}^{\sigma}\cup\{j_{2}\}\backslash \{j_{1}\}|=|J_{i_{1}}^{\sigma}|$である．ここで，てられたふたつの仕事の割当先の交換を複数回行う操作である．これらシフトキックと交換キックの一に適用する．
方をランダムに選び，解以下の節で提案アルゴリズムの詳細について述べ$\sigma_{see}d$る．32 節では改善グラフについて述べ，33 節では改善グラフを用いた連鎖シフト近傍の探索について，
34 節ではペナルティ重みの更新方法，35 節ではシ
フトキックと交換キックについて述べる．最後に，36
節では提案アルゴリズム全体の枠組みをまとめる．

32

改善グラフ

$\tilde{J}_{rr’}^{\sigma}=J_{i_{r}}^{\sigma}\cup\{j_{r’}\}\backslash \{j_{r}\}$と定義すると，辺の重み$w_{j_{1}j_{2}}$の計算は，$w_{j_{1}j_{2}}=pcost_{i_{1}}(\tilde{J}_{12}^{\sigma})-pcost_{i_{1}}(J_{i_{1}}^{\sigma})$$= \sum_{j\in\overline{J}_{12}^{\sigma}}c_{i_{1}j}+\sum_{k=1}^{s}(\alpha_{i_{1}k}p_{i_{1}k}(\tilde{J}_{12}^{\sigma})+\beta_{i_{1}}q_{i_{1}}(\tilde{J}_{12}^{\sigma}))$$- \sum_{j\in J_{i_{1}}^{\sigma}}c_{i_{1}j}-\sum_{k=1}^{s}(\alpha_{i_{1}k}p_{i_{1}k}(J_{i_{1}}^{\sigma})+\beta_{i_{1}q_{i_{1}}}(J_{i_{1}}^{\sigma}))$$= \sum_{j\in\tilde{J}_{12}^{\sigma}}c_{i_{1}j}-\sum_{j\in J_{i}^{\sigma_{1}}}c_{i_{1}j}$

改善グラフ $G(\sigma)=(V, E)$ は，頂点集合 $V$ と辺$+ \sum_{k=1}^{s}(\alpha_{i_{1}k}p_{i_{1}k}(\tilde{J}_{12}^{\sigma})-\alpha_{i_{1}k}p_{i_{1}k}(J_{i_{1}}^{\sigma}))$

集合 $E$ を持つ有向グラフである．各頂点 $j\in V$ が
仕事 $j\in J$ に対応しており，$V=J$ となる．各辺

224とする．そして辺を以下のように制限したグラフ$=c_{i_{1}j_{2}}-c_{i_{1}j_{1}}$$\overline{G}(\sigma)=(V,\overline{E})$$+ \sum_{k=1}^{s}(\alpha_{i_{1}kp_{i}},k(\overline{J}_{12}^{\sigma})-\alpha_{i_{1}k}p_{i_{1}k}(J_{i_{1}}^{\sigma}))$

(6)

を考える．

$\tilde{E}=\{(j_{1},j_{2})\in E|\mu_{j_{1}j_{2}}=\min_{j’\in J}\mu_{j_{1}j’}\}$となり，実際はコストと資源制約に対するペナルティの変化量の計算のみで良い．各

$i$

と

$k$

の組みに対して現在の解における資源使用量の合計を記憶しておこれは，頂点$j_{1}$.

から出る各辺の中で資源容量を超える資源数が最も少ない辺のみに制限するということ$wj_{1}j_{2}=+\infty$である．また，となる場合，とする．この制限により，近傍内の改善解を逃す可能$(j_{1},j_{2})\not\in\tilde{E}$くことで，式 (6) から 1 つの枝あたり $O(s)$ 時間で重み$w_{j_{1}j_{2}}$を計算することが出来る．

ここで，仕事$j_{1},j_{2},$ $\ldots,j_{l}$操作と改善グラフ$G(\sigma)$に対する連鎖シフト

内の対応するサイクル$j_{1}arrow j_{2}arrow\cdotsarrow j_{l}arrow j_{1}$について考える．任意の $r,$ $r’(r\neq r’\in\{1,2, \ldots, l\})$

に対して

な

$i_{r}\neq i_{r’}$らば，そのサイクルを subset-disjoint と呼ぶ．サイクルが subset-disjoint であるとき，連鎖シフト操作による pcost の変化量は$\sum_{r=1}^{l}pcost_{i_{r}}(\tilde{J}_{r,r+1}^{\sigma})-\sum_{r=1}^{l}pcost_{i_{r}}(J_{i_{r}}^{\sigma})$性は大きくなってしまうが，その分探索の効率が向上
することが期待出来る．

33 改善グラフの探索
本節では，改善グラフ$\tilde{G}(\sigma)=(V,\overline{E})$を用いた連鎖シフト近傍の探索について述べる．ここで述べる

手法は，サイクルの探索を subset-disjoint であるものに限定しない．したがって，サイクルの辺の重み和とサイクルに対応する連鎖シフト操作によるペナル
ティ付きコスト pcost の変化量が必ずしも一致するとは限らない．ただし，辺の数が 3 以下のサイクル
は式 (5) の定義より，常に subset-disjoint となる．ま$= \sum_{r=1}^{l}\{pcost_{i_{r}}(\tilde{J}_{r,r+1}^{\sigma})-pcost_{i_{r}}(J_{i_{r}}^{\sigma})\}$

た，辺数の短いサイクル は subset-disjoint になりやすい傾向にあり，サイクル内の辺数が多くなるほど
subset-disjoint である確率は減少していく．とくに
辺数 $m+1$ 以上のサイクルでは，subset-disjoint と$F$$= \sum_{r=1}^{l}w_{j_{r}j_{r+1}}$となる．このように，連鎖シフト操作による pcost の変化量は，対応するサイクルが subset-disjoint であるとき，サイクルの辺の重み和となる．よって，連鎖
シフト近傍内の改善解を発見するには重み和が負となる subset-disjoint のサイクルを発見できれば良い．

しかしながら，このようなサイクルを発見する問題に制限して探索を行う．

動的計画法に基づいてサイクルの探索を行う．ここで任意の $j_{1},j\in J,$ $l=1,2,$

一方，サイクルがsubset-disjoint であるかどうかを考慮せず，単に重み和が負となるサイクルを発見するのは多項式時間で$\ldots,$$m-1$ に対し

$f^{*}(j_{1},j, l)$ を頂点
から頂点 までの辺数 のて，最小重みパスとする．任意の $j_{1},j\in J$ に対して，$j$$j_{1}$

は一般的に NP 困難である [12].

行うことが出来る [1].

なることはない．そのため，辺数 $m$ 以下のサイクル$f^{*}(j_{1},j, l)$$l$はそのため，改善グラフ内から

重み和が負となるサイクルを発見することで，連鎖シ$f^{*}(j_{1}, j, l)=\{\begin{array}{l}w_{j_{1}j}, l=1,\min_{j\in J}\{f^{*}(j_{1},j’, l-1)+w_{j’j}\},l=2,3, \ldots, m-1\end{array}$フト近傍内の改善解を近似的に探索していく．

(7)

改善グラフの探索効率は辺の数に依存するため，
以下のルールで辺の数を制限する．エージェント$i_{1}=\sigma(j_{1})$から仕事$j_{1}$を外し，仕事$j_{2}$

を加えたと

$l$

き，エージェント 21 の資源容量を超える資源の種類
数を$\mu_{j_{1}j_{2}}=|\{k\in K|p_{i_{1}k}(J_{i_{1}}^{\sigma}\backslash \{j_{1}\}\cup\{j_{2}\})>0\}|$と計算出来る．ここで，式 (7) において最小の値を実現する〆を保持しておき，から 1 までこの値を辿る$f^{*}(j_{1},j, l)$ を実現するパスを復元出来る．
ことで，$f^{*}(j_{1}, j, l)+wjj_{1}$,は辺 $(j, j_{1})$ を含む辺数 $l+1$ のサイクルの中で最小の重み和を表す．したがって，$f^{*}(j_{1},j, l)+wjj_{1}<0$となる $(j_{1},j, l)$ を探索することで改善グラフ内の負の重みをもつサイクルを発見$f^{*}(j_{1},j, l)+wjj_{1}<0$ とすることが出来る．ただし，

225
なるサイクルを発見しても，そのサイクルが subsetdisjoint でない場合は pcost の変化量がサイクルの重てもみ和と同じでないかもしれない．そのため，サイクル...

に対応する連鎖シフト操作による pcost の変化量をまり頂点再計算する必要がある．これらの動作を以下にまとパス

める．これを連鎖シフト近傍探索 (SCS) と呼ぶ．

となる頂点によって計算出来るが，どの $l’=2,3,$$f^{*}(j_{1},j, l’-1)$$arrow j_{l}$$l$$\ldots,$に対しが負となるパス $j_{1}arrow j_{2}arrow$

のみを探索をすることを意味している．つから頂点$j_{1}$$f^{*}(j_{1}, j, l)$

$i’$

$j$

への各長さ

$l’$

の最小重み

$f^{*}(j_{1}, j’, l-1)<0$を計算する際，から出る辺のみに制限して計算を行うということである．そのため，(8) 式は (7) 式よ連鎖シフト近傍探索 (SCS)
入力: 現在の解

出力:$\sigma$$N_{chain}(\sigma)$.
の中に改善解を発見できなければno,” 発見できれば改善解$\sigma’\in N$。hain$(\sigma)$.

Stepl $S:=J$ とする．
ならば “no” と出力し終了する．そStep2

りも効率的に計算出来る．この制限を行っても，グ
ラフ内に負のサイクルが存在するとき，そのような
まサイクルの 1 つを発見することが出来る [8]た，Step4 で $f^{*}(j_{1},j, l)+w_{jj_{1}}$ の増加順にソート
し，ソートした順番に pcost の再計算を行う際も，$f^{*}(j_{1}, j, l)+wjj_{1}<0$$S=\emptyset$

うでなければランダムに仕事 $j_{1}\in S$ を選び，
$S:=S\backslash \{j_{1}\},$

Step3

$j$

のみを再計算の対象とする．

$l:=1$ とする．

全ての $j\in J$ に対して式 (7) を用いて
$f^{*}(j_{1},j, l)$

Step4

となる頂点

34 ペナルティ重みの更新を計算する．

$f^{*}(j_{1},j, l)+wjj_{1}$の増加順に $j\in J$ をソートする．この順番で各 $j\in J$ に対して，サイクルに対応する連鎖シフト操作を行ったときのpcost の変化量を計算する．もし，改善解発見したならば$\sigma$

をを出力し，終了する．
Step5 $l\leq m-2$ ならば $l:=l+1$ とし，Step3 へ．
$\sigma$との更新方法に
本節では，ペナルティ重みのついて述べる．提案アルゴリズムの動作は$\alpha_{ik},$

効果的な値に適宜更新していく必要がある．

初期値として，各$f^{*}(j_{1},j, l)$の計算にかかる時間はアルゴリズム全体で$O(nm|\tilde{E}|)$

時間である

$i$

$:=\beta_{init}$

$\in$

$I,$

に対して

また，局所最適とする$:=\alpha_{init},$解。pt にたどり着くたびにペナルティ重み$\beta_{i}$$\sigma_{1}$$\alpha_{ik}$との更新を行う．ここで，任意の $i\in I,$ $k\in K$ に対し，ペナルティ重みの更新に用いる関数を以下のよう時間かかり，全体ではに定義する:

時間かかる．長さ$l$のサイクルに対する pcost の再計算には 1 つあたり $O(ls)$ 時間かかり，全体では $O(n^{2}m^{2}s)$ 時間かかる．よって全体の計$\rho_{ik}^{inc}(J_{i}^{\sigma_{1opt}})=p_{ik}(J_{i}^{\sigma_{1opt}})/b_{ik}$$\phi_{i}^{inc}(J_{i}^{\sigma_{1opt}})=q_{i}(J_{i}^{\sigma_{1opt}})$

次にこの探索の高速化について述べる．まず，関数$\lambda(x)=\{x+,\infty$,,$\rho_{ik}^{dec}(J_{i}^{\sigma 1opt})=\{\begin{array}{ll}-1, p_{ik}(J_{i}^{\sigma_{1opt}})=0,0, p_{ik}(J_{i}^{\sigma_{1opt}})\neq 0,\end{array}$

算時間は $O(nm(|\tilde{E}|+n\log n+nms))$ 時間となる．

を用いて，$\in K$$k$$\alpha_{ik}$$\beta_{i}$また，Step4 のソートには 1 回あたり $O(n\log n)$$O(n^{2}m\log n)$$\beta_{i}$値に大きく影響される．そのため，これらの値をよりそうでなければ Step2 へ．

このアルゴリズムの計算時間を評価する．

$\beta_{i}$$\alpha_{ik}$,$\phi_{i}^{dec}(J_{i}^{\sigma_{1opt}})=\{\begin{array}{ll}-1, q_{i}(J_{i}^{\sigma_{1opt}})=0,0, q_{i}(J_{i}^{\sigma_{1opt}})\neq 0.\end{array}$$x\geq 0x<0$ ’$f_{-}^{*}(j_{1}, j’, l)=\lambda(f^{*}(j_{1},j’, l))$と定義する．

これはペナルティ重みの更新は，前回ペナルティ重みを更新
した後，局所探索中に移動した解の中に実行可能解があったか否か，および資源制約と個数制約のいずれかを満たす解が存在したか否かによって決定するもの$f_{-}^{*}(j_{1},j, l)=\{\begin{array}{l}\lambda(w_{j_{1}j}), l=1,\min_{j\in J}\{\lambda(f_{-}^{*}(j_{1},j’, l-1)+w_{j’j})\},l=2,3, \ldots, m-1\end{array}$とした．以下にそれぞれの場合に対する更新方法を詳しく述べていく．

(8)

ケース 1: 直前の局所探索中に移動した解の中に資源制約のみを満たす解も個数制約のみを満たす解も存在しなかった場合．

226
任意の $i\in I,$ $k\in K$ に対して能解が存在した場合．
各ペナルティ重み$\beta_{i}$$\alpha_{ik},$を減少させる．更新は$size-inc_{-}\alpha$ケース 1 と同様の方法で行う．ただし，との代わりに $size_{-}dec_{-}\alpha$ と $size_{-}dec_{-}\beta$$size_{-}inc_{-}\beta$$\Gamma_{ik}=\{\begin{array}{l}size_{-}inc_{-}\alpha\cdot\frac{\rho_{ik}^{inc}(J_{i}^{\sigma_{1opt}})}{i’I,k\inK\max_{\in}|\rho_{ik}^{inc},(J_{i}^{\sigma_{1opt}})|},i’I,k’\in K\max_{\in}|\rho_{ik}^{inc},(J_{i}^{\sigma_{1opt}})|>0,0, \text{その他，}\end{array}$$(0<$ size.dec-a $<1,0<size_{-}dec_{-}\beta<1$ はパラメータ) を用い，$\rho_{i}^{nc}(J_{i}^{\sigma_{1opt}})$に

35$\Delta_{i}=\{\begin{array}{l}size_{-}inc_{-}\beta\cdot\frac{\phi_{i}^{inc}(J_{i}^{\sigma_{1opt}})}{\max_{i’\in I}|\phi_{i}^{inc}(J_{i}^{\sigma_{1opt}})|},\max|\phi_{i}^{inc}(J_{i}^{\sigma_{1opt}})|i’\in I">0,0, \text{その他，}\end{array}$と$\rho_{ik}^{dec}(J_{i}^{\sigma_{1opt}})$と$\phi_{i}^{dec}(J_{i}^{\sigma_{1opt}})$$\phi_{i}^{inc}(J_{i}^{\sigma_{1opt}})$

の代わり

を用いる．

ランダムな摂動

本節では，ランダムな摂動について述べる．反復局
を用いてペナルティ重み$\alpha_{ik}$と$\beta_{i}$$:=\alpha_{ik}(1+\Gamma_{ik})$$\alpha_{ik}$

所探索法では，解が局所最適解

を

,

(9)

(10)

$\beta_{i}:=\beta_{i}(1+\Delta_{i})$と増加させる$size-inc_{-}\alpha$
ここで，

$<$

$0$

と

$\sigma_{1opt}$に辿り着いたとき，解にランダムな摂動を加え，解を変更する．そしてその解を初期解とし，再び局所探索を行う．このランダムな摂動は局所探索とは異なり，改悪解への移動も許可し通常の局所探索では到達できない解への移動を目的としている．

$size_{-}inc_{-}\beta>0$ はパラメータである．

提案アルゴリズムでは，ランダムな摂動としてシフケース 2: 直前の局所探索中に移動した解の中にいずれか一方の制約のみを満たす解が存在した場合．

トキックと交換キックの 2 つを用いた．これらの動以下のように各ペナルティ重み

作は解が局所最適解$\alpha_{ik}$と$\beta_{i}$の一方を増加させる．資源制約のみを満たす解が存在し，個数制

重み

と

,

(11)
(12)

$\beta_{i}:=\beta_{i}(1+\Delta_{i})$解の評価は制約違反に応じたペナルティをコストに付加したものを評価値としている．そのため，個数制
約のペナルティの値を縦軸に取り，あるエージェン
こ割り当てられた仕事数を横軸に取ってグラフとし，一方，個数制約のみを満たす解が存在し，資源ト

制約を満たす解が存在しなかったときはを描くと，各$\alpha_{ik}$$:=\alpha_{ik}(1+\Gamma_{ik})$

(13)

,

(14)

$\beta_{i}:=\beta_{i}$とする．ここで，$\Gamma_{ik}$と$\triangle_{i}$にたどり着き，ペナルティの更新を行った直後に行う．

$\beta_{i}$まず，シフトキックについて述べる．提案手法では約を満たす解が存在しなかったときは$\alpha_{ik}:=\alpha_{ik}$$\alpha_{ik}$$\sigma_{1opt}$

はケース 1 で定義したも$i\ovalbox{\tt\small REJECT}$

$g$

に対して

$h_{ig}$と $h_{i,g+1}$ の間に山が出来る．このペナルティの山を越える解への移動は局所探索では起こりにくい．そこで，あるエージェントに割り当てられた仕事数に山を越えるような大きな変更を加えるため，シフトキックを提案した．シフト
キックとは，ランダムに選ばれた任意のエージェントのである．
ケース 3: 直前の局所探索中に移動した解の中に資に割り当てられている複数の仕事の割当先を$i_{1}\in I$

源制約のみを満たす解と個数制約のみを満たす解が変更する操作である．ここで，エージェント

それぞれ存在した場合．

在割り当てられている仕事数に最も近い割り当て可

すべての $i\in I$ と $k\in K$ に対してペナルティ重み

能な仕事数を$h_{i_{1},g}$

エージェント$i_{1}$$\alpha_{ik}$と$\beta_{i}$を$\alpha_{ik}$$\beta_{i}$$:=\alpha_{ik}(1+size_{-}inc_{-}factor\cdot\Gamma_{ik})$$:=\beta_{i}(1+size_{-}inc_{-}f$actor.

はケース 1 で定義と増加させる．ここで， とは$0<$ size-inc.factor
したものであり，また，$\Gamma_{ik}$に割り当てられている仕事数を$\triangleright^{-}$’$g^{*}=1g^{*}\geq 2$,$g^{*}= \arg\min_{g’=1,2,\ldots,|H_{i_{1}}|}\{||J_{i_{1}}^{\sigma}|-h_{i_{1}g’} \}$$\Delta_{i}$$h_{i_{1}}’$のように定義する:$h_{i_{1}}’=\{h_{i_{1},g}^{i_{1},g-1}h.,$$\Delta_{i})$に現. とし，シフトキックを行った後，とする．これらを以,$i_{1}$.

$\leq 1$

パラメータである．
ケース 4: 直前の探索中に移動した解の中に実行可

エージェント$i_{1}$

から$|J_{i_{1}}^{\sigma}|-h_{i_{1}}’$個の仕事をランダムに選び，割当先を変更する．このようにしてエージェント$i_{1}$に割り当てられている仕事数を強制的に$h_{i_{1}}’$

227
個にすることが出来る．なお，複数の仕事の割当先を同一のエージェント $i_{2}\in I$ に変更すると，資源制約を違反しやすくなり，割当に偏りが生じるため，割当先を変更する仕事ごとに割当先をランダムに選ぶ．
シフトキック後の解に対してシフト近傍の探索を行うと，シフトキックによって割当先が変更された仕事が元のエージェントに戻ってしまう可能性がある．

ストが pcost $(\sigma_{1opt})\leq pcost(\sigma_{seed})$ を満たす場合は，$\sigma_{seed}$と更新する．

$:=\sigma_{1opt}$$\sigma_{seed}$に対してシフトキッ

クまたは交換キックをランダムに選び行う．シフト

キックを行った場合は，シフト近傍操作で元の局所最適解に戻ってしまう事があるため，交換近傍の探索から始めることでそのようなサイクリングを防ぐ．これにより得られた新たな初期解に対して同様に局所

そのため，シフトキックによって仕事が移動した割当$I’$ のいずれ
先のエージェント集合 $I’\subset I$ を保持し，探索を行う．終了条件は計算時間があらかじめ定め

かのエージェント $i’$ に含まれている仕事に関する交終了条件を満たしているか否かをチェックする．

た上限を超えたときとし，解の移動が行われるたびに換近傍による探索を近傍内に改善解がなくなるまで行う．この操作は各エージェントに割り当てられた仕事の数を変更することなくペナルティ付きコスト

pcost の改良を行うため，その後のシフト近傍の探索によって仕事の割当先を元に戻してしまうことを防ぐ効果が期待出来る．

次に交換キックについて述べる．これは各エージェントに割り当てられた仕事の数を変えることなく解提案アルゴリズム (SSK-CS)

Stepl 解をランダムに生成する．

$\sigma_{seed}:=\sigma$$\sigma$

する．

Step2

終

$\Gamma$

条件を満たしている場合，暫定解を出力して終了する．

Step3 即時移動戦略によるシフト近傍内の探索をもし，pcost $(\sigma’)<pcost(\sigma)$ となる解行うの移動を行うために用いた．交換キックとは，異な$\sigma’\in N_{shift}(\sigma)$るエージェントに割り当てられたふたっの仕事$(\in J, \sigma(j_{1})\neq\sigma(j_{2}))$$j_{1},j_{2}$をランダムに選び，それらの割当先を交換する操作を複数回行うことである．ここ

とを発見したら，$\sigma:=\sigma’$とし，

Step2 へ．

Step4 即時移動戦略による交換近傍内の探索を行$<pcost(\sigma)$ となる解う．もし，pcost
とし，
Nswap
を発見したら，$(\sigma’)$で，一度交換を行った仕事はそれ以降のキックの対象$\sigma’\in$から除き，交換キックの操作によって割当先を変更された仕事の中に重複はないものとする．交換キック
による摂動の大きさは交換を行う回数に影響される．
そのため交換を行う回数をパラメータ
究では$\gamma$$\gamma$

アルゴリズム SCS を用いた連鎖シフト近傍の探索を行う．もし，pcost $(\sigma’)<pcost(\sigma)$ となる解を発見したら，とし，Step2 へ．
Step6 34 節に述べた方法でペナルティ重み$\beta_{i}$$\alpha_{ik}$との更新を行う．

Step7 pcost $(\sigma)\leq pcost(\sigma_{seed})$ ならば，$\sigma_{seed}:=\sigma$

36 提案アルゴリズム全体の枠組みとする．

本節では，提案アルゴリズムの枠組みをまとめる．

Step8$\sigma_{seed}$に対してアルゴリズム SSK を用いてランダムな摂動を加えることによって得られた

まず，初期解をランダムに作成し，局所探索を行う．局所探索ではシフト近傍，交換近傍，連鎖$\sigma_{start}$

シフト近傍を用いて解の改善を行っていく．

$\sigma:=\sigma’$$\sigma’\in N_{chain}(\sigma)$の値をキックのたびに 2 から 5 の整数から呼ぶ．

$\sigma:=\sigma’$

Step2 へ．

Step5

とし，本研

選ぶこととした．これをシフト交換キック (SSK) と$(\sigma)$

解を$\sigma$とし，Step2 へ．

ここで，交換近傍内の探索は，現在の解のシフト近傍内に改善解がない場合に限って行う．同様に，連鎖シ

4 計算実験

フト近傍はシフト近傍と交換近傍内のいずれにも改善解がない場合に限って探索を行う．探索が局所最適解$\alpha_{ik}$と$\sigma_{1opt}$$\beta_{i}$にたどり着くたびに，ペナルティ重みの更新を行う．ここで，過去の局所最適解の中で良い解をし，更新後の$\sigma_{seed}$$\alpha_{ik}$と$\beta_{i}$(初期値は$\sigma_{seed}=\sigma_{start}$) とを用いたペナルティ付きコ

ここでは，提案アルゴリズム (SSK-CS) と次のアルゴリズムとの比較を行う:(1) 汎用ソルバー CPLEX,(2) 提案アルゴリズムから連鎖シフト近傍を除いたア
ルゴリズム (SSK-noCS). SSK-CS と SSK-noCS 1 は$C$

言語にて実装した．SSK-noCS は連鎖シフト近傍

228
表1
$n$

$m$

$s$

タイプ C の問題例に対する計算結果

SSK-CS
TTB(秒)
Best

SSK-noCS
TTB(秒)
Best
10.08

CPLEX
TTB(秒)
Best$1942^{a}$4.15$1954^{b}$$1954^{(1}$31.81$\overline{100511942^{b}}$
17.57
15.37
11.77
5
8
100
$1942^{b}$$1954^{b}$

100
100
100
100
200
200
200
200
200
200
400
400
400
400
400
400

10
10
20
20

1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

5
5

10
10
20
20
10
10
20
20
40

40

$1421^{b}$$1473^{b}$

1321$1350^{b}$$3462^{b}$$3483^{b}$

2829$2853^{b}$

2433

$m$

$s$

142
1476
1329
1373

14.80

$3462^{b}$

208.8532.05
173.9439.25
179.05930.63658.9619.04
41.05
368.40549.23433.8450.11
406.88145.441021851178.081166.66
863.361084.30
1166.98$3483^{b}$$2827^{b}$

2855$2432^{b}$$4814^{b}$

1148.71$4860^{b}$974.294866$4288^{b}$911.05$4312^{b}$

1161.71

4321
4374

5609
5655

41.13
59.90

$1^{b}$

2461
5612
5648
4837

$2442^{b}$

表2
$n$

58.34
48.55
59.01
153.1312236
274.9491.27
244.4729.51
360.501421475$1^{a}$$1317^{b}$

1351$3462^{a}$

3486
2830

589.90

$-$

$-$

$-$

640.521177.86$5604^{b}$$5636^{b}$
$-$

$-$

$-$

$-$

$-$

タイプ D の問題例に対する計算結果

SSK-noCS

SSK-CSCPLEX
TTB(秒)Best$\overline{10051}$
Best

TTB(秒)Best

TTB(秒)

6371297.68636588.10

100
100
100
100
100
200
200
200
200
200
200
400
400
400
400
400
400

8
5
1
10
8
10
1
20
20
8
1
5
58
1
10
8
10
1
20
8
20
1
10
8
10
1
20
8
20
1
40
8
40

6444
6414
6554

$6308^{b}$$6518^{b}$

12769
12833
12507
12602
$12431^{b}$$12610^{b}$

25080
25234
$24775^{b}$$25057^{b}$$24668^{b}$$24984^{b}$

197.0968.91
115.8017149
225.89122.54218.39512.22492.17497.25133.18326.09846.171115.42101405118131899.74

19541
127.63211.1717963
209.10299.22279.1994.58
185.29532.40340.70232.041185.88858.411199.801038.97115647

6458
6402
6555
6354
6576
12769
12828
12534
12664
12448
12682
25107
25283
24842
25172
24872
25264

$6360^{b}$$6435^{b}$$6395^{b}$$6541^{b}$

6345
6604
$12753^{b}$$12787^{b}$$12472^{b}$$12570^{b}$

18.72
129.10254.91229.05287.33160.69439.35217.96447.61557.40$-$$-$$24994^{b}$$25083^{b}$1094.17116100

$-$

$-$

$-$

$-$

$-$

の探索を除いたこと以外は提案アルゴリズムと同様であり，これら全てのタイプを用いた．個数制約をである．また計算環境は Dell Precision 470, Xeon

以下のように生成した．ランダムに選んだひとつの$3GHz,$ $2MB$ cache, lGB memory である．問題例は，

エージェントを $i’\in I$ とし，それ以外の各エージェ

次の 2 つの方法により作成した:(1) 多資源一般化割

ント $i\in I\backslash \{i’\}$ に対して以下を行う．まず，

当問題のベンチマーク問題例に個数制約をランダムの仕事数 400 の問題例に資源制約と個数制約をラン[1, 5] からランダムに選び， $:=2$ とする．次に，整数を [1, 5] からランダムに選んで，$h_{ig}:=h_{i,g-1}+y$としたのち $g:=g+1$ とする操作を $h_{ig}\geq 2n/m$ とダムに加える．

なるまで繰り返す．はじめにランダムに選んだひとに加える，(2) 一般化割当問題のベンチマーク問題例$h_{i1}$

を

$g$

$y$

まず，多資源一般化割当問題のベンチマーク問題

つのエージェント $i’\in I$ に対しては，次のように個例を利用した生成方法にっいて述べる．多資源 ’ 般

数制約を設けた． に割当可能な仕事数の下限とし化割当問題の問題例のタイプはタイプ C から E ま

て

$i’$

$l$

を $[n/(4m), n/(2m)]$ からランダムに選び，上限

229
表3
$m$

$n$

100
100
100
100
100
100
200
200
200
200
200
200
400
400
400
400
400
400

として

$r$

5
5
10
10
20
20
5
5
10
10
20
20
10

1
8
1
8
1
8
1
8
1
8

10
20
20
40
40

タイプ E の問題例に対する計算結果

SSK-CS$s$

SSK-noCS$12823^{b}$

11711$11904^{b}$$8734^{b}$$11935^{b}$

24956
25040

23431
23615

1

$22725^{b}$

8
1
8
1
8

$23160^{b}$$45800^{b}$

45955$45154^{b}$$45319^{b}$

1

46088

8

$45588^{b}$

77.43
250.88167.79186.8587.02
17168
122.03520.06402.84583.79540.781185.16630.841020.18
1043.52
1012.45796.96を $[n/(2m), 2n/m]$ からランダムに選んで$H_{i’}=\{l, l+1, \ldots, r\}$CPLEX$TTB($ 秒
TTB (秒) Best$\overline{BestTTB(\text{秒^{}J})Best12710^{b}88.1512710^{b}}$$)76$とする． を用意する理由は，
$i’$

11909
8779
12060
24958

229.30130.1515321
72.03
175.7716446
50096$25033^{b}$$3OS.46$$23426^{b}$

36.40
444.45580.2437.10
1088.76$12823^{b}$$11697^{b}$

23592
22784
23352
45805
45998
45187
45465

977.27785.82742.50$45653^{b}$
1119.02
46066
1066460661066.49

限
$n$

$t$

$12710^{a}$215.78185.52
23021

12845
11780
11951
8801
12281

28545
294.0323.51
580.0430769
562.26$24951^{a}$

25046
23468
$23437^{b}$
$-$

24616
45876
$45877^{b}$

58854

1194.00
392.46$-$46745

1188.60

$-$

$-$

$-$

を超えたときとし，計算時間の条件

$t$

は仕事の数

に比例するように $t=3n$ とした．

以外のエージェント

表 1-3 は SSK-CS, SSK-noCS, CPLEX の計算結と同じ生成方法を採ってしまうと，個数制約を満たす解が存在しない問題例となってしまう可能性があり，果である．表中のは仕事数， はエージェ
ント数， は資源の種類数を表している．また，表これを回避するためである．

中の 「 Best」 は計算時間内に各アルゴリズムによっ

全てのエージェントに対して$i’$$r_{nJ}$$r_{m\rfloor}$$r_{s\rfloor}$

次に，一般化割当問題のベンチマーク問題例をて得られた最も良い実行可能解の目的関数値を示し，利用した生成方法について述べる．一般化割当問「TTB」は最も良い実行可能解が得られたときの計算

題の問題例のタイプはタイプ A から E まで 5 つ

時間 (秒) を示している．表中の出力解に 「 」 と記さの種類があるが，それらのうちタイプ A と B は比較的簡単な問題傾向であるため，タイプ C から E
までの 3 つを用いた．まず，資源制約の生成方法

れているのは比較した 3 つのアルゴリズムの中で最を以下に述べる．各 $i\in I,$ $j\in J,$

適解であることを示している．表中の「-」 は計算時$k\in K\backslash \{1\}$に対して $a_{ijk}=3a_{ij1}/4+\delta_{ijk}a_{ij1}/2$ とした．
こで$\delta_{ijk}$

は $[0,1]$ からランダムに選ぶ$b_{ik}=0.8 \sum_{j\in J}a_{ijk}/m$

こまた，とした．個数制約は多資源一

般化割当問題のベンチマーク問題例に対して行った生成方法と同様の方法で生成した．

$b$も良い解であることを示しており，CPLEX の出力解に$\lceil_{a\rfloor}$間内に実行可能解が得られなかったことを示している．

.

これらの表から次のことが観測される:以上からタイプ C, D, E, $n\in\{100,200\},$ $m\in$からなる 36 個の問題例と，
タイプ C, D, E, $n\in\{400\},$ $m\in\{10,20,40\}$ ,$s\in\{1,8\}$ からなる 18 個の問題例の，合計 54 個の問題例を作成し，計算実験を行った．
ペナルティ重みの初期値は
1,$\{5,10,20\},$$s\in\{1,8\}$$\alpha_{init}$$\beta_{init}=1$$=$とし，重みの更新時の各パラメータは

size-inc.$\alpha=0.1,$ $size_{-}dec_{-}\alpha=0.1,$ $size_{-}inc_{-}\beta=$
0.5, $size_{-}dec_{-}\beta=0.1$ , size-inc-factor $=0.1$ とした．また，終了条件は計算時間があらかじめ定めた上と記されているのはその解が問題の厳密な最.

SSK-CS はほとんどの問題において SSKnoCS よりも良い結果を得ることが出来た．
このことから連鎖シフト近傍の有効性を確認することが出来た．

SSK-CS はタイプ

$C$と $E$ の問題例の多くに対して，CPLEX よりも良い解を得ることが出来た．また，タイプ D の問題例に対しては，
CPLEX は 10 問に対して最良解を得ているのに対し，提案手法の SSK-CS は 8 問で最良解を得ている．このように最良解を得た個数
に関しては CPLEX の方がやや勝っているも230のの，仕事数が大きい問題例や，仕事数に対するエージェント数の割合が大きい問題例に対しては提案手法の方が勝っている傾向にある．
このことから提案アルゴリズムはとくに規模の大きな問題例に対してより効果的であると考えられる．

5

まとめ
個数制約付き多資源一般化割当問題の計算の複雑さを明らかにしたのち，発見的解法を提案した．まず，計算の複雑さについては，とくにこの問題が個数制約のみを有する場合に対する計算の複雑さについて考え，個数制約が特別な条件を満たす場合は多項式時間で解けるが，一般の場合は NP 困難であることを示した．次に，この問題に対して反復局所探索法に基づくアルゴリズムを提案した．ベンチマーク問題例を元に作成した問題例に対して計算実験を行ったところ，多くの問題例に対して汎用ソルバー CPLEX より良い結果を得ることが出来た．とくに，大規模な問題例
においては，調べた全てのタイプの問題例に対して汎用ソルバー CPLEX より平均的に良い結果を得ることが出来た．

参考文献[1] R. K. Ahuj , T. L. Magnanti, J. B. Orlin, Net$a$

work Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
[2] W. Cook, A. Rohe, Computing minimumweight perfect matchings. INFORMS J. Comput. 11 (1999) 138-148.
[3] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur
Standards $69B$ (1965) 125-130.
[4] H.N. Gabow, Data structures for weighted
matching and nearest common ancestors withlinking, Proceedings of the First Annual
ACM-SIAM Symposium on Discrete Algorithms (1990) 434-443.
[5] M.R. Garey, D.S. Johnson, Computers andIntractability. A Guide to the Theory of NPCompleteness, W.H. Freeman and Company,
1979.
[6] B. Gavish, H. Pirkul, Algorithms for themulti-resource generalized assignment problem, Management Science 37 (1991) 695-713.
[7] E.L. Lewler, Combinatorial optimization:
Networks and Matroids, Holt, Rinehart andWinston, 1976.
[8] S. Lin, B.W. Kernighan, An effective heuristic
algorithm for the traveling salesman problem,
Oper. Res. 21 (1973) 498-516.
[9] K. Mehlhorn, G. Sch\"afer, Implementation ofweighted matchings in generalgraphs: the power of data structures. In: Algorithm Engineering; WAE-2000; LNCS 1982
(S. N\"aher, D. Wangner, eds.), pp.23-38; also
electronically in the ACM Journal of Experimental Algorithmics 7 (2002) 138-148.
[10] R.M. Nauss, Solving the generalized assignment problem: an optimizing and heuristic
approach, INFORMS J. Comput. 15 (2003)$O(nm\log n)$249-266.
[11] S. Sahni, T. Gonzalez, P-complete approximation problems, J. ACM 23 (1976) 555-565.
[12] P.M. Thompson, J.B. Orlin, The theory ofcyclic transfers, Working Paper No. OR 20089, Operations Res. Center, MIT, Cambridge,

1989.
[13] M. Yagiura, T. Ibaraki, F. Glover, An ejection chain approach for the generalized assignment problem, INFORMS J. Comput. 16(2004) 133-151.
[14] M. Yagiura, T. Ibaraki, F. Glover, A path relinking approach with ejection chains for thegeneralized assignment problem, European J.
Oper. Res. 169 (2006) 548-569.
[15] M. Yagiura, S. Iwasaki, T. Ibaraki, F. Glover,
A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Discrete optimization 1(2004) 87-98.