最短経路問題を解くリアルタイムシステム

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

現在の自動車社会において,目的地まで渋滞を避つつ時間的もしくは距離的に最短な経路を見つけることは,生活をする上で重要な問題である.また,渋滞,工事,事故による通行止め,斜線規制などは,リアルタイムに変化するものである従来の計算幾何学の分野で扱われている最短経路問題では,障害物などの状況はアルゴリズムを実行中は変化しないと仮定され,動的に変化する状況を仮定したアルゴリズムの研究は,ほとんど行なわれていない.しかし,刻一刻と道路の状況,天候,事故情報などが変化する自動車社会における交通網に,従来の最短経路を求めるアルゴリズムを当てはめようとすると1.最短経路を求めている間に道路状況が変化すると,せっかく求めかけた解が意味をもたなくなる.2.いつ終了するとも知れないアルゴリズムのため最短経路が求まった時には,すでに自動車は移動しており,せっかく求めた解が意味をもたなくなる.などの問題が生じる.そこで,本研究では,このような問題を解決するためにリアルタイムシステムの考え方を計算幾何学の分野に導入を考えた.リアルタイムシステムは解を有効な時間内で求めることもさることながら,耐故障性も備えていることが特徴である.しかし,リアルタイムシステムを利用するにあたり次のような問題点が明らかになった.・状況がリアルタイムに変化するので,いつの時点での"最短"であるかという問題.今後は,求めた解の有効時間(有効となる範囲)を動的に求める手法の導入を考えている.