表題番号：2001A-085 日付：2002/05/15
研究課題ネットワーク構造（特に通信ネットワーク、ロジスティックスネットを中心に）をもつ組み合わせ最適化問題における費用配分解に関する研究
研究者所属（当時） 資格 氏名
（代表者） 商学部 助教授 毛利　裕昭
研究成果概要
2000年度の特定課題による成果を受けて2001年度には以下の研究成果が得られた。

（１）現実の現象と数学モデルとの乖離に関する問題解決の可能性の模索
　日本OR学会 2001年度春季研究発表会において、実務家から提起された上記問題についての整理を行いその成果を発表した。
さらには、日本OR学会 統合オペレーション　2001/6G3/SG3　合同研究発表会において、この問題についての解決の可能性に
関する方向性を提示した。

（２）ネットワークデザイン問題に関する具体的な費用配分解とアルゴリズムの提示
　ネットワークデザイン問題は、組み合わせ最適化問題の中でも通信ネットワーク、ロジスティックスネットワークだけで
なく幅広い応用をもつ問題である。この問題は、ベーシックな条件のみでも計算量の理論の見地からは、NP-hardのクラス
に属する問題である。The Second International Conference on Nonlinear Analysis and Convex Analysis 2001
においては、ベーシックな条件でのネットワークデザイン問題での費用配分解を提案し、その数学的特性をチェックした上
で、計算量の問題を克服しうる費用配分解計算のアルゴリズムを示した。
　さらに、The Tenth International Colloquium on Numerical Analysis and Computer Science with Applications
においては、基本的ネットワークデザイン問題にさらに、施設配置問題（組み合わせ最適化問題で、計算量の理論からはこの
問題もNP-hardのクラスに属する）の要素を加味した問題について数学的解の性質に関する考察を行い、発表を行った。
　また、あいまいさと不確実性を含む状況の数理的意思決定　京大数理解析研究所研究集会　においては、通信ネットワーク
の処理時間を考慮し、確率過程を数学モデルに導入したネットワークデザイン問題の費用配分解に関する。具体的な解とその
解を求めるアルゴリズムの提示を行った。

（３）性質の良い組み合わせ最適化の構造をもつ費用配分ゲームに関する考察
　上記に示した問題は、数学的性質が計算量の理論の見地をはじめとして良いとは言えないものである。したがって、チャレン
ジすることは非常に意味があると考える。しかし、その一方で、性質の良い組み合わせ最適化の構造をもつ費用配分ゲームの特
性に関して、きちんと整理されているとは言いがたい現状がある。日本応用数理学会２００１年度年会　における発表において
は、性質が良い問題に関する一考察を行った結果を発表した。

●今年度得られた研究成果は、現実と数学モデルとの解決の方向性、ネットワークデザイン問題のいくつかのバリエーションに
　ついて、具体的解と解を計算するに当たってのできる限り計算量の問題解決したアルゴリズムの提示、および、性質の良い問
　題に関する、一つの見地からの整理である。今後の展開として、解の数学的性質を更に詳細にチェックすることとアルゴリズ
　ムの一層の改良、性質の良い問題に関する様々な観点からの整理を行う余地が残されている。