タイムテーブル最適化におけるハイブリッド・アルゴリズムの構築

点击翻译按钮获取中文摘要

本研究課題「タイムテーブル最適化におけるハイブリッド・アルゴリズムの構築」は,タイムテーブル最適化を効率的に解くアルゴリズムの構築を目指すものである.本年度の研究成果は,主に以下の三点である.1.半正定値計画法を利用したタイムテーブル最適化これまで,タイムテーブル最適化に用いられてきたのは主に整数計画法であるが,本研究では線形計画法の拡張である半正定値計画法を利用し,整数計画法では計算時間が多大になってしまう問題に対して高速なアルゴリズムを開発した.2.移動距離最小化がからんだタイムテーブル最適化における高速アルゴリズムタイムテーブル最適化に移動距離最小化の概念がからんだような問題は,通常よりさらに難しくなることが知られている.本研究では,それらのうちある特定のクラスの問題に対して,高速アルゴリズムを開発した.3.ある種のタイムテーブル最適化に適用可能なメタ・ヒューリスティックアルゴリズムある種のタイムテーブル最適化問題は,これまで主に数学の組合せ論の範疇で扱われており,組合せ最適化の観点からは扱われてこなかった.本研究では,この問題に対してメタ・ヒューリスティックの技術を利用したアルゴリズムを開発した.上記の問題はいずれも,従来研究では高速なアルゴリズムが得られていなかった問題であり,本研究で開発したアルゴリズムは非常に有用である.開発したアルゴリズムはいずれも高速に動作し,なおかつ実装が容易であるのも特徴である.