緒 言

本章では，2つの特定のノードを有し，その間を連結するエッジの組み合わせ によって経路が構成されるネットワーク経路問題を考える．エッジには各々，距 離やコスト，移動時間などの評価指標が与えられている．本論文における多目的 ネットワークの最適経路問題とは，これらの評価指標が最小となる経路を探索す る問題である．

単目的ネットワークの最適経路の探索には，前述のように Dijkstra[19]や Bellman-Ford[12,22]のアルゴリズムが有効であることが知られている．しかし近 年は単目的ネットワークに関する研究は少なく，多目的ネットワークに注目した 研究が多い．多目的ネットワークにおいては，パレート最適解を探索する研究や，

1つの評価指標に着目し，その他の評価指標を制約とした研究[9,83]が行われてい る．

多目的ネットワークでは，一般的にエッジの評価指標が互いに競合するため，

同時に最小となる経路はほとんどの場合存在しない．よって，多目的ネットワー クに対しパレート最適解を探索することは有効である．Akiba他[6,68]は，制約付 き最適経路のための拡張ダイクストラ法[83]をもとに，2 目的と 3 目的のネット ワークの最適経路問題に対してパレート最適解を探索する拡張ダイクストラ法 を提案した．しかしネットワークに複数の評価指標が存在するために，Akiba 他 の拡張ダイクストラ法では，経路の探索過程が複雑化し，また計算過程で必要と なる記憶領域が急増するために計算負荷が非常に大きくなる．そのため大規模な ネットワークでの探索は困難となる．Akiba他[6,68]は，2目的と3目的のネット ワークに対して拡張ダイクストラ法を効率化したアルゴリズムも提案している．

しかし，その提案法ではすべてのパレート最適解は探索されない場合がある．そ こで，一般化した多目的ネットワークにおいて，すべてのパレート最適解をより 効率的に全探索するアルゴリズムを提案する．本論文では，はじめに探索空間の 削減に有効な性質を検討する．次にその性質を利用して探索空間を削減し，かつ すべてのパレート最適解を探索するアルゴリズムを提案する．はじめに次節で本 論文における多目的ネットワークの最適経路問題を定義し，4.3 節でパレート最 適解を求める基本アルゴリズムを示す．そして，4.4 節で解探索空間を効率良く 削減することで計算高速化と記憶容量削減を図るアルゴリズムを提案する．最後

75

に4.5節で提案アルゴリズムの数値実験による評価を行い，4.6節で本章をまとめ る．

4.2 問題定義

以下に本章で用いる記号及びネットワークの仮定を示す．

記号

n：ノード数

E：エッジe_iの集合，E{e₁,e₂,,e_m} V ：ノードの集合

G：ネットワークG (V,E) 仮定

i) ネットワークはG(V,E)

ii) 各エッジe_iのN 種類のコストは，コスト間及びエッジ間で影響を与えること なく独立に決まる．

iii) 各エッジe_iのN 種類のコストは既知である．

4.2.1 多目的最適経路問題

ノードsからノードtを結ぶ経路を考える．このとき，第i番目のエッジe_i(E) にはN 種類のコストが付与され，コストベクトル (c_i1,c_i2,,c_iN) で表される．

ただし，i1,2,,m，j1,2,,Nに対し，cijはエッジ i における第 j目的関数 の値（コスト）を表し，c_ij 0 である．コスト (c_i1,c_i2,,c_iN) は，ある対象が エッジe_i を移動するとき生じるものとする．例えば対象がエッジ e₁,e₂ を含む経 路を通過した場合，N 種類のコストc₁₁c₂₁, ^c₁₂ ^c₂₂, ,c_1N c_2Nが生じる．

m

i1,2,, に対して，x_i{0,1}をエッジe_iが経路として選択されたときに 1，

そうでなければ0となる二値変数とする．この二値変数を要素とするm次元ベク トル x(x₁,x₂,,x_m) を定義する．

また，対象は同時に1つのエッジのみ通過することとすると，vV に対して 次の等式が成り立つ．

76





















 0, .

, , 1

, ,

1

} ) (

| { } ) (

|

{ otherwise

t v

s v x

x

v e end E e

i v

e start E e

i

i i i i

(4.1)

ここでstart(e_i)とend(e_i)は，それぞれエッジe_iの始点と終点を意味する．ノー ド_sからノードtまでの経路は，(4.1)式を満たす要素x_iから成る_m次元ベクトル

x で表すことができる．X をノード_sからノードtまでの経路xの集合とする．

次に，_{j1,2,,N}に対して，目的関数を





E e

i ij j

i

x c g (x)

と定義する．g_j(x)は，対象が経路xを通過したときに生じる，第 j目的関数の 総コストである．以上より本論文で考察する多目的最適経路問題は，下記で表さ れる．

多目的最適経路問題 N

j1,2,, に対して，

min )

( 



eE i ij j

i

x c g x

s.t. xX .

なお j=1 の場合は，ネットワークの最短経路問題に等しいことに注意されたい．

4.2.2 多目的最適経路問題におけるパレート最適解の定義

本章では，N種類の目的関数を有する一般的なネットワークが対象となる．こ こで，経路の優越関係と本章でのパレート最適解の定義を以下に示す．

経路 x,xX において， j1,2,,Nに対してg_j(x) g_j(x)となり，厳密な 不等式が少なくとも1つ成り立つとき， x は x に優越しているという．集合 X 内で x に優越する他の経路が存在しないとき，x をパレート最適解と呼ぶ．

77