階層的ネットワーク(ハブ・アンド・スポークシステム)はネットワークの運営をする上で最も効率的な手法の一つである．殊に大規模なネットワークでは，階層システムを導入することによって，交通流動をその目的地までより効率的に輸送することが可能となる．この階層システムは，高速道路・鉄道・郵便・航空・貨物輸送をはじめとする交通ネットワークに留まらず，いまや，通信・教育機関・医療機関・都市間交易・組織運営にまで導入されるようになっている．階層ネットワークを導入することによって，ネットワーク上の任意の2点を結ぶ全てのODペアを実現するのに必要となるリンクの数を減らすことが可能になり，同じリンク数の2点間輸送ネットワークが提供できるサービスを大きく上回るサービスが提供可能となる．また拠点間(ハブ間)のリンクにおける規模の経済も，階層システム導入の大きなインセンティヴである．これは，階層ネットワークにおいては，交通流がこれら拠点間リンクに集中するゆえ，ネットワークの運営者が，その拠点間のリンクの改良を行うか，それとも小型トラックで輸送していた物資を鉄道で運ぶように転換するというように，より効率性が高い交通機関に転換するかを選択することが可能であることによるものである．

　階層システムは非常に効率性を高くすることが可能なネットワーク構築手法だと認識されてはいるものの，施策の意思決定者が大規模な多段階階層システムを設計するのに資する実用的な手法は現在のところ存在してはいない．それゆえ，意思決定者は，単に地理的な制約ないし経験や慣習にのっとってネットワーク設計に当たっているに過ぎない．しかし，大規模な多段階階層システムは通常何千何万というノードからなる極めて複雑なものになっており，効率的なネットワークの設計に当たっては，何処を輸送拠点(ハブ)にすべきか，いくつのハブを設置すべきか，どのようにハブの階層構造を設計すべきか，それぞれのノードがどのハブと接続されるべきかといった問題に対する適切な解が求められる．

　本研究の目的は，一般的な階層ネットワークの特徴及びその含意を分析することである．そこで，まず，一般的な階層ネットワークの分類と定式化を行った．次いで，十分に多くのノードが存在する条件の下で，階層ネットワークの各タイプについて解くことが出来る実用的なモデルを開発した．さらに，本研究では開発した手法の，現実の階層ネットワークへの適用可能性を検証した．

　本論文では，冒頭の2章(第1章と第2章)で本研究に関連する学問的背景について述べる．第1章では，階層ネットワークの重要性と適用について述べている．階層ネットワークはフローと接続性から，R/U/N，I/U/N，R/M/N，I/M/N，I/M/Dの5種類の特徴的なタイプに分類される．第2章では，階層ネットワークの設計問題に関する広範な文献レビューを行った．このテーマに関する72件の論文をレビューし，内容を簡単に示している．あわせて本研究で活用する発見的探索法の文献レビューも行っている．

　以上を受けて，第3章では，R/U/N，I/U/N，R/M/N，I/M/N，I/M/Dの実用的な各タイプのネットワークを解くための定式化を行った．ここで，1段階の階層ネットワークの定式化においてでさえNP困難問題があることが証明されている(O'Kelly，1987)ことから，先に挙げたの問題を解くにあたり，複数の手法を組み合わせた発見的探索法を適用した．発見的探索法については第4章で検討を行った．まずはR/U/Nネットワークを解く方法論の検討から始めた．というのは，R/U/Nネットワークが最も限定的なネットワーク構成をもっており，それゆえ最も容易に解くことができるものであったからである．筆者はR/U/Nネットワークの設計問題を解くために，タブサーチと遺伝的アルゴリズムを組み合わせたハイブリッドな発見的探索法，M-GATSアルゴリズム(Multilevel Genetic Algorithm Tabu Search Algorithm:多階層遺伝的アルゴリズム・タブサーチアルゴリズム法)を開発した．これは，遺伝的アルゴリズムの部分で最適なハブの数とその配置を定め，一方で，タブサーチ部分を用いてハブ以外のノードをハブに結びつける配分を定めるものである．さらにこれに次ぐ節からは，一般的な階層ネットワークを解く手法の検討を行った．ここでは，2種類のハイブリッド発見的探索法，EM-GATSアルゴリズム(Extended Multilevel Genetic Algorithm Tabu Search Algorithm:拡張多階層遺伝的アルゴリズム・タブサーチアルゴリズム法)，GA-GSアルゴリズム(Genetic Algorithm-Greedy Search Algorithm:遺伝的アルゴリズム・盲目的探索法)について比較検討している．

　第5章では，第4章で提案した手法による計算結果の分析を行った．M-GATSについては，計算実験の結果から，すべての基本水準問題の最適解を求めるのに非常に効率的であることが証明され，また程々に大きな規模の問題(ノード数が200までのネットワーク規模)についてはM-GATSが適用可能であることが実証された．一般化階層ネットワークを解く手法については，筆者は，EM-GATSが妥当な計算時間内に一般化階層ネットワークを解くのに適用可能であることを示した．しかしながら，このEM-GATSによって得られる解は，GA-GSアルゴリズムで得られる解と比べ，劣ることが証明された．GA-GSアルゴリズムはすべてのケースについて最適解を得ることができるものである．そこで可能な配分の厳密な検証によれば，GA-GSアルゴリズムによる解の方が8%効率的なネットワークを求められることがわかった．しかしながら，これには計算時間の制約の問題がある．GA-GSは100ノードの問題を解くのに11日もの時間がかかり，解くことが可能なネットワークの規模はこの程度に限られたものになってしまう．それゆえ，EM-GATSによって得られる解は，問題の規模と計算時間が制約下に収まる範囲での次善の解であるといえる．また，EM-GATSによる解は，意思決定者に，GA-GSによって得られた最適解が種々の要因で実現不可能な場合の代替案としての解を提供できるともいえる．

　第6章では，ネットワークを計算可能な規模の複数のクラスタに分割し，本研究で用いるアルゴリズムで計算が可能なネットワーク規模を拡大するための手法について検討した．ここでは，クラスタリングのアルゴリズムの定式化と提案した定式化を用いて問題を解くための発見的探索法と双方について言及する．本章の末尾では，クラスタリングアルゴリズムを用いた1500ノードの問題の計算結果を示した．その結果，クラスタリングアルゴリズムを用いた場合には，数千ノードからなるネットワークまで拡張しても解を見出すことができることが示された．クラスタリングアルゴリズムによる解は準最適値として5%程度の相違はあるものの，扱うことが可能なネットワーク規模が劇的に拡張されたことを考慮すれば許容されうる程度であると考えられる．

　アルゴリズムの開発に次いで，筆者は本研究の適用可能性について3種類の重要な階層ネットワークを用いて検証した．なおここでは，ネットワーク構造の観点から最も対照的なものとして，貨物輸送ネットワーク(R/U/N)，旅客航空ネットワーク(I/M/D)，都市システム(I/U/N)を対象としている．

　第7章では郵便や貨物輸送ネットワーク(R/U/N)について論じる．このネットワークは，最も交通流が限定される政策を表しており，物資は必ず最下層のハブから送られ，そして，順次最上層のハブに到達するまで輸送され，最上層に着くや今度は逆に最下層の目的地まで同様に順次階層を下って輸送されていくというシステムであり，直接2点間を結ぶことは認められていない．このタイプのネットワークは，交通のコストと運営について効率性を最大化できる一方，ハブ・アンド・スポークシステムをすべて経由するため輸送時間が長くなるという問題点がある．本研究では，データが入手可能であったオーストラリアの郵便ネットワークについて実証分析を行った．ここで用いたネットワークはAPデータセットとも呼ばれ，Ernst and Krishnamoorthy (1998)によって提供された有名なものである．このネットワークを解くに当たっては，単にR/U/Nネットワークへの本研究のモデルの適用可能性の検証に留まらず，モデル自身の妥当性の確認も行っている．多階層構造を用いてすべてのケースについて分析した結果，本研究で開発したモデルによって，上記文献に示された最適解と同一もしくはより改善された解を得ることができることが示された．

　これに対して旅客航空ネットワーク(I/M/D)は最も交通流の限定が緩やかな政策を代表している．航空ネットワークでは，旅客は目的地への直行便に搭乗することもあるいは統合されたハブを経由する乗り換え便に搭乗し安く目的地へ向かうことも可能である．現存するネットワークには，乗換えがある長時間のフライトへの旅客の受忍限度と旅行費用逓減のトレードオフに基づいて成立している．第8章では，中国の国内旅客航空市場におけるハブ・アンド・スポーク構造の最適化問題を対象に，本研究のモデルを適用した．本研究では，中国国内の113空港のうちから地域間ハブならびに中規模ハブにすべき空港とフィーダー空港からハブ空港への接続方法について検討し，その結果と中国民間航空管理局5ヵ年計画との比較を行った．その結果，既往の中国民間航空管理局5ヵ年計画による空港整備計画は妥当なものであるということを示し，また今後の整備についての提言を行った．

　第9章は，実証分析の最後の部分にあたり，階層ネットワークの都市システムへの適用を検討した．都市では，工業，小売業，サービス業などの種々の業種によって多くの機能を有している．これらの機能は都市が富を生み出す基礎である．大都市では，非常に多くの専門的なサービスが提供されさまざまな活動が可能である．反対に小都市や町村部では，提供される機能は非常に限られる．大都市の財・サービスの提供者は，都市内や都市周辺域からの高い需要に支えられ，規模の経済によるコスト縮減効果を享受できる．しかし，小都市に居住し，大都市まで買い物に出かける人は，より多くの交通費用がかかることになる．それゆえ，規模の経済による費用逓減と交通支出に伴う費用増大の間のトレードオフが存在する．本研究のモデルを用いることで，どのような財・サービスがどの規模の都市で提供されることがシステム最適となるかを示すことが可能となった．この理論的結果と機能の集積による費用のトレードオフに関する分析から，都市システムの形成および発展に関する知見についての示唆が得られ，またカリフォルニア州および日本の都市システムについて，計算結果を基に実証的分析を行った．

図1:階層ネットワーク

図2:階層システムの分類

図3:1500ノードのネットワーク計算例

図4:郵便ネットワーク

図5:中国航空ネットワーク

図6:カリフォルニア州都市システム

　キジマナワット・ケラテイ氏の論文は、「一般化階層ネットワークの構築手法:インフラネットワーク及び都市システムを対象とした理論的，方法論的，実証的研究」と題するもので、さまざまな階層システムを統括的に扱うことのできる数学的方法論を開発し、それを航空ネットワーク設計、都市群システムの構造分析などに適用した結果をまとめたものである。

　階層的ネットワークは、ネットワークの運営をする上で最も効率的な手法の一つである．殊に大規模なネットワークでは，階層システムを導入することによって，交通流動をその目的地までより効率的に輸送することが可能となる．この階層システムは，高速道路・鉄道・郵便・航空・貨物輸送をはじめとする交通ネットワークに留まらず，いまや，通信・教育機関・医療機関・都市間交易・組織運営にまで導入されている．

　階層システムは非常に効率性を高くすることが可能なネットワーク構築手法だと認識されてはいるものの，施策の意思決定者が大規模な多段階階層システムを設計するのに資する実用的な手法は現在のところ存在してはいない．それゆえ，意思決定者は，単に地理的な制約ないし経験や慣習にのっとってネットワーク設計に当たっているに過ぎない．しかし，大規模な多段階階層システムは通常何千何万というノードからなる極めて複雑なものになっており，効率的なネットワークの設計に当たっては，何処を輸送拠点(ハブ)にすべきか，いくつのハブを設置すべきか，どのようにハブの階層構造を設計すべきか，それぞれのノードがどのハブと接続されるべきかといった問題に対する適切な解が求められる．

　本論文では，冒頭の2章(第1章と第2章)で本研究に関連する学問的背景について述べる．ここでは，階層ネットワークの重要性と適用について述べている．

第3章では，ネットワークを解くための定式化を行っている．ここで，1段階の階層ネットワークの定式化においてでさえNP困難問題があることが証明されていることから，先に挙げた問題を解くにあたり，複数の手法を組み合わせた発見的探索法を適用した．発見的探索法については第4章で検討を行った．まずはR/U/Nネットワークを解く方法論の検討から始め、さらに一般的な階層ネットワークを解く手法の検討を行っている．第5章では，計算結果の分析を行っている．M-GATSについては，計算実験の結果から，すべての基本水準問題の最適解を求めるのに非常に効率的であることが証明され，また程々に大きな規模の問題についてはM-GATSが適用可能であることが実証された．第6章では，ネットワークを計算可能な規模の複数のクラスタに分割し，本研究で用いるアルゴリズムで計算が可能なネットワーク規模を拡大するための手法について検討した．

　アルゴリズムの開発に次いで，筆者は本研究の適用可能性について3種類の重要な階層ネットワークを用いて検証した．なおここでは，ネットワーク構造の観点から最も対照的なものとして，貨物輸送ネットワーク(R/U/N)，旅客航空ネットワーク(I/M/D)，都市システム(I/U/N)を対象としている．第7章では郵便や貨物輸送ネットワーク(R/U/N)について論じている．本研究では，データが入手可能であったオーストラリアの郵便ネットワークについて実証分析を行っている．第8章では，中国の国内旅客航空市場におけるハブ・アンド・スポーク構造の最適化問題を対象に，本研究のモデルを適用した．第9章は，階層ネットワークの都市システムへの適用を検討した．大都市の財・サービスの提供者は，都市内や都市周辺域からの高い需要に支えられ，規模の経済によるコスト縮減効果を享受できる．しかし，小都市に居住し，大都市まで買い物に出かける人は，より多くの交通費用がかかることになる．それゆえ，規模の経済による費用逓減と交通支出に伴う費用増大の間のトレードオフが存在する．本研究のモデルを用いることで，どのような財・サービスがどの規模の都市で提供されることがシステム最適となるかを示すことが可能となった．この理論的結果と機能の集積による費用のトレードオフに関する分析から，都市システムの形成および発展に関する知見についての示唆が得られ，またカリフォルニア州および日本の都市システムについて，計算結果を基に実証的分析を行っている．

　以上、本研究はきわめて新規性と独自性に富んだものであり、同時に実務的な応用性も非常に高いものと認められる。よって、キジマナワット ケラテイ氏の論文は、博士(工学)の学位請求論文として合格と認められる。