今後の課題

本研究で提案したアルゴリズムはさまざまな仮定の元に実行される．実際の搬送システ ムでは，様々な条件があるため，その仮定をなるべく取り除いたものを今後も考える必要 がある．

搬送要求の数とAGVの台数 ここで提案したアルゴリズムは，搬送要求の数がAGVの 台数が一致している場合についてのみ成立する．AGVの台数が搬送要求の数より 少ない場合，1台のAGVが複数の要求を満たす場合がある．その場合，このアル ゴリズムで仕事の割り当てができない．またAGVの台数が搬送要求の数より多い

場合も同様に余ったAGVをどうするか，あるいはどのAGVを使えば要求を満た すことが出来る場合と出来ない場合があるのかを考慮する必要がある．

動的な動作計画 ここでは動作計画をAGVが移動する前にあらかじめ決定し，その計画 が途中で変更が加えられないことを仮定している．従って，実際の搬送システムを 考慮すると動的な計画変更に耐えうるアルゴリズムを考える必要がある．

計算量 アルゴリズムで動作計画を求めるには最悪kの指数時間かかる．このため，AGV の台数あるいは搬送要求の数によって実時間で解ける問題は限られてしまう．従っ て実際にこのアルゴリズムを使って動作計画を立てるためには，多項式時間で解け るようにアルゴリズムを工夫，あるいは創作する必要がある．

Appendix

補題の証明

( ⇒ )

k本のsからtへのvertex-disjointなパスP1· · ·Pkが与えられるものとする．それぞれ のパスは

Pi =u⁽ⁱ⁾₁ →u⁽ⁱ⁾₂ → · · · →u⁽ⁱ⁾_ri i= 1· · ·k

と表す．但しu⁽ⁱ⁾₁ =s, u⁽ⁱ⁾_ri =tである．

ここで，P1· · ·Pk上のarcを並べ替える．並べ替えのルールはarcのtailを小さい順にす る．但し，tailが同じ場合そのarcが存在するパスの番号が小さい順に並び替える．そし て，並べ替えた順にそれぞれのarcを

w1 →z1, w2 →z2,· · ·, wρ→zρ

とする．ここでk本のパスが与えられているからw1· · ·wkまでは全てsである．なぜな ら一番小さいtailの組の要素はsであり，それがk個存在するから上で述べたような並べ 替えを行なえば，

s=w1 =w2 =· · ·=wk

となる．またwk+1· · ·wρにはソースは存在せず，またvertex-disjointなパスが与えられ ているから同一のものは存在しない．よって

s=w1 =w2 =· · ·=wk < wk+1 <· · ·< wρ

である．またρはarcの数に等しい．その値はパス1本につきri−1本のarcがあるから k本では各パスのarcの数のsummationに等しいので，

ρ=

k

(ri −1)

である．

ここで G上に P というパスを定義する．P を定義するために P に存在する arc の a1· · ·aρを定義する．

a1· · ·akについて

a1 =w1, s,· · ·, s → z1, s,· · ·, s a2 =z1, w2,· · ·, s → z1, z2,· · ·, s

... ... ...

ak =z₁, z2,· · ·, wk → z₁, z2,· · ·, zk ak+1· · ·aρについて

ai =x1,· · ·, xj−1, wi, xj+1,· · ·, xk → x1,· · ·, xj−1, zi, xj+1,· · ·, xk i=k+ 1,· · ·, ρ

ここでx₁,· · ·, xj−1, xj, xj+1,· · ·, xk はai−1 のheadである．なぜならP はa1,· · ·, aρ

で表されるパスであるから，ai−1 の headが ai の tailでなければ P はパスにならない．

よってai−1のheadはaiのtailである．

また，wi =min{x₁,· · ·, xk}である．なぜなら，

まず，a1については，そのtailは全てsの要素からなる組であり，どの要素もその組で最 小であり，w1 =sであるからw1 はaiの中に含まれており，最小である．

aˆi(ˆi= 1,· · ·, i−1)はそのtailの組の中にwˆiが含まれていて一番小さく，そのheadは wˆi をzˆiに置き換えたものであると仮定する．ここでx1,· · ·, xkつまりaiのtailの組の要 素はパス上にある点のどれかであるから，

x1,· · ·, xk ∈ {w₁,· · ·, wρ, t} (4.1) である．なぜならパス上にあるarcのtail はw1,· · ·, wρ で表され，唯一 tailになりえ ないtも含まれるからである．また，ai−1のtailでwi−1 は最小であるから，それをzi−1

に置き換えたai−1のheadのどの要素もwi−1よりも大きい．従ってai−1のheadはaiの tailであるからai のtailつまり

x1,· · ·, xk > wi−1 (4.2) である．

4.1,4.2より，

x1,· · ·, xk ∈ {wi,· · ·, wρ, t} (4.3)

であることが言える．ここでj < k < iであるようなaj, akの時にまたaj のheadがak

のtailである場合，

aj =· · ·wj· · · → · · ·zj· · · ak=· · ·wk· · · → · · ·zk· · ·

のようにaj のtailの要素であるwjがzjに置き換えられる．この時そのzj =wiであっ た場合，aˆi(ˆi= 1,· · ·, i−1)では，wˆiが置き換えられるからwi はai まで置き換えられる ことはない．従って，wiはai のtailに存在する．すなわち，

wiがx1,· · ·, xkに存在する． (4.4) 4.3，4.4よりwi < wi+1<· · ·< wρ< t であることからwiはx1,· · ·, xkに含まれ，すな わちwiはaiのtailに含まれ，その中で最小である．よってai(i= 1,· · ·, ρ)のtailにおい てwi は最小であるといえる．

以上によりa1,· · ·, aρは定義され，PはG上にあるs,· · ·, s → t,· · ·, tのようなパス であり，lj(j = 1,· · ·, k)のようなj番目のdimensionalなarcのlengthの合計をコストに もつ．なぜなら，P 上にある各arcのコストは組の要素を置換するのに使うA上のarcの コストに等しく，またパスのコストは各arcのコストの合計であるからである．

( ⇐ )

G上にパス

P ≡ x⁽¹⁾₁ ,· · ·, x⁽¹⁾_k → x⁽²⁾₁ ,· · ·, x⁽²⁾_k · · · → x^(ρ)₁ ,· · ·, x^(ρ)_k が存在することを仮定する．

ここで，Gの定義からi= 1,· · ·, ρについてまたj ∈ {1,· · ·, k} \ {ˆj}であるようなどの jについても

x⁽ⁱ⁾_ˆj →x_ˆ^(j+1)_j ∈Aでかつ x⁽ⁱ⁾_j =x⁽ⁱ⁺¹⁾_j

となるようなj ∈ {1,· · ·, k}が存在することが言える．

x⁽ⁱ⁾_ˆj →x_ˆ^(j+1)_j ∈Aであるのは，

今P のパス上のarcはAの定義からそのtail の組の1要素を置換した組をheadとして いる．その1要素がˆj番目の点であった場合，arcのtailのˆj番目の要素はx_ˆ⁽ⁱ⁾_j で，head のˆj番目の要素はx⁽ⁱ⁺¹⁾_ˆj である．Aの定義からx⁽ⁱ⁾_ˆj からx⁽ⁱ⁺¹⁾_ˆj へのarcがAに存在するの で，x⁽ⁱ⁾_ˆj →x⁽ⁱ⁺¹⁾_ˆj ∈A, i= 1,· · ·, ρ, j ∈ {1,· · ·, k} のようなˆjは存在する．

さらにx⁽ⁱ⁾_j =x⁽ⁱ⁺¹⁾_j であるようなˆjが存在するのは

ˆj番目の要素だけを変えた組から組へのarcでP は存在しているから組のˆj 番目以外の要 素はそのままであるからx⁽ⁱ⁾_j =x⁽ⁱ⁺¹⁾_j となるようなˆj も存在する．

以上により，P ≡ x⁽¹⁾₁ ,· · ·, x⁽¹⁾_k → x⁽²⁾₁ ,· · ·, x⁽²⁾_k · · · → x^(ρ)₁ ,· · ·, x^(ρ)_k はG上のsか らtまでのvertex-disjointなパスである．なぜなら，

まず先に述べたように，Gの定義から

x_⁽ⁱ⁾_m →x⁽ⁱ⁺¹⁾_m ∈A





i= 1,· · ·, ρ m = 1,· · ·, k のようなarcが存在する．つまり，

x⁽¹⁾_m →x⁽²⁾_m x⁽²⁾_m →x⁽³⁾_m

... x^ρ_m →x^(ρ+1)_m m= 1,· · ·, k

のような arc が存在する．また A の定義より x⁽ⁱ⁾_m < x⁽ⁱ⁺¹⁾_m (m = 1,· · ·, ρ) であるから x⁽¹⁾_m ≤x⁽²⁾_m ≤ · · · ≤x^(ρ)_m である．

ここでP1,· · ·, Pkのパスがvertex-disjointではない場合つまり下のようなxが再び置換 される場合を考える．

· · ·x · · · · · · (4.5)

↓ ...

↓

· · · · · · x· · · (4.6)

4.6のような組で，その前の組からxに置換されたということは4.5から4.6の間ではx

より小さい要素が置換されてきたことになる．ということは4.5におけるxは置換される 要素ではないはずなので4.6まで保存されるから4.6でxが2つ存在することになる．こ れはV の定義に反するため，P1,· · ·, PkはG上のsからtまでのvertex-disjointなパス である．

さらにc^(j)(Pj)はj = 1,· · ·, kについてP のj番目のdimensionalなarcのlengthの合 計である．なぜならAˆに存在するarcのlengthの定義はx⁽ⁱ⁾_ˆj →x⁽ⁱ⁺¹⁾_ˆj ∈Aのコストに等 しい．よってパスPj のコストはx⁽ⁱ⁾_j ,· · ·, x^(ρ)_j までのarcのコストの合計である．

謝辞

最後に本研究を進めるにあたり，指導教官であり，北陸先端科学技術大学院大学情報科 学研究科の平石 邦彦助教授には，終始様々な助言，御指導を頂きました．また同研究室 の宋 少秋助手，高島 康裕助手にも適切な助言，指導を頂きました．ここに深く感謝の意 を表します．